Search

Submodular maximization is a NP-hard combinatorial optimization problem regularly used in machine learning and data mining with large-scale data sets. To quantify the running time of approximation algorithms, the query complexity and adaptive complexity are two important measures, where the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially many function evaluations in parallel. These two concepts reasonably quantify the efficiency and practicability of parallel computation. In this paper, we consider the problem of maximizing a nonnegative monotone DR-submodular function over a bounded integer lattice with a cardinality constraint in a value oracle model. Prior to our work, Soma and Yoshida (Math Program 172:539–563, 2018) have studied this problem and present an approximation algorithm with almost optimal approximate ratio and the same adaptivity and query complexity. We develop two novel algorithms, called low query algorithm and low adaptivity algorithm, which have approximation ratios equal to Soma and Yoshida (2018), but reach a new record of query complexity and adaptivity. As for methods, compared with the threshold greedy in Soma and Yoshida (2018), the low query algorithm reduces the number of possible thresholds and improves both the adaptivity and query complexity. The low adaptivity algorithm further integrates a vector sequencing technique to accelerate adaptive complexity in an exponential manner while only making logarithmic sacrifices on oracle queries. [ABSTRACT FROM AUTHOR]

In this paper, we study the multi-period distributed generation planning problem in a multistage hierarchical distribution network. We first formulate the problem as a non-convex mixed-integer nonlinear programming problem. Since the proposed model is non-convex and generally hard to solve, we convexify the model based on semi-definite programming. Then, we use a customized Benders’ decomposition method with valid cuts to solve the convex relaxation model. Computational results show that the proposed algorithm provides an efficient way to solve the problem for relatively large-scale networks. [ABSTRACT FROM AUTHOR]

Nowadays, large part of the technical knowledge associated with collapses of slabs is based on past failures of bridges, floors, flat roofs and balconies. Collapse mechanisms tend to often differ from each other due to unique features which make it difficult to derive a generalised technique that can predict the right mechanism. This paper proposes a novel algorithm for tackling the problem of detection of collapse mechanisms, which is part of a pseudo-lower bound method for assessing concrete slabs in bridges and buildings. The problem is generalised to a combinatorial one, and the solution is based on a set of well-known combinatorial optimization algorithms. The proposed approach enables an identification of the domain of existence of yield-lines potentially leading to collapse. The output provides an estimation of a hampered domain of feasible yield-lines through which engineers can quickly identify zones of the slab and directions in which yield-lines leading to collapse are more likely to occur. Numerical applications of the algorithm are presented herein. [ABSTRACT FROM AUTHOR]

In this paper, we propose to study a wide class of combinatorial optimization problems called combinatorial optimization problems with labelling. First, we give a combinatorial method to deal with the labelling version of some classical combinatorial optimization problems including minimum vertex cover, maximum independent set, minimum dominating set and minimum set cover, and convert the labelling problems into the original problems by polynomial-time reduction. We show that, although the labelling version of these problem seems more universal than their original counterparts, they are actually equivalent to the corresponding original problem from an algorithmic point of view. Moreover, we generalize the greedy approach for solving submodular cover problem to its labelling version, and as simple applications of our new method, we use it to solve the labelling versions of the minimum weighted spanning tree and connected vertex cover problem in a unified way. [ABSTRACT FROM AUTHOR]

Finding complete subgraphs in a graph, that is, cliques, is a key problem and has many real-world applications, e.g., finding communities in social networks, clustering gene expression data, modeling ecological niches in food webs, and describing chemicals in a substance. The problem of finding the largest clique in a graph is a well-known difficult combinatorial optimization problem and is called the maximum clique problem. In this paper, we formulate a very convenient continuous characterization of the maximum clique problem based on the symmetric rank-one non-negative approximation of a given matrix and build a one-to-one correspondence between stationary points of our formulation and cliques of a given graph. In particular, we show that the local (resp. global) minima of the continuous problem corresponds to the maximal (resp. maximum) cliques of the given graph. We also propose a new and efficient clique finding algorithm based on our continuous formulation and test it on the DIMACS data sets to show that the new algorithm outperforms other existing algorithms based on the Motzkin-Straus formulation and can compete with a sophisticated combinatorial heuristic. [ABSTRACT FROM AUTHOR]

Modern radars are highly flexible systems, relying on digital antennas to dynamically control the radar beam shape and position through electronic circuits. Radar surveillance is performed by sequential emission of different radar beams. Optimization of radar surveillance requires finding a minimal subset of radar beams, which covers and ensures detection over the surveillance space, among a collection of available radar beams with different shapes and positions, thus minimizing the required scanning time. Optimal radar surveillance can be modelled by grid covering, a specific geometric case of set covering where the universe set is laid out on a grid, representing the radar surveillance space, which must be covered using available subsets, representing the radar beams detection areas. While the set cover problem is generally difficult to solve optimally, certain geometric cases can be optimized in polynomial time. This paper studies the theoretical complexity of grid cover problems used for modelling radar surveillance, proving that unidimensional grids can be covered by strongly polynomial algorithms based on dynamic programming, whereas optimal covering of bidimensional grids is generally non-deterministic polynomially hard. [ABSTRACT FROM AUTHOR]

This paper concerns with some variants of the inverse obnoxious median location problem on tree networks, where the aim is either to augment or to reduce the edge lengths at the minimum total cost such that a prespecified subset of vertices becomes an obnoxious multi-facility median location with respect to the perturbed edge lengths. For both augmentation and reduction models, under the rectilinear norm and the sum-type Hamming distance, we develop novel combinatorial algorithms with polynomial time complexities. Particularly, if the underlying tree is an extended star graph, then the problems can be solved in linear time. [ABSTRACT FROM AUTHOR]

This paper introduces the biologically inspired concept of hidden genes genetic algorithms; they search for optimal solutions to global optimization problems of multimodal objective functions with a variable number of design variables. A fixed chromosome length is assumed for all solutions in the population. Each chromosome is divided into effective and ineffective segments. The effective segment includes the design variables for that solution. The ineffective segment includes only hidden genes. Hidden genes are excluded in objective function evaluations. The effect of the hidden genes on the convergence of the genetic algorithm is studied. Two test cases are presented. [ABSTRACT FROM AUTHOR]

This paper considers a stochastic variational inequality problem (SVIP). We first formulate SVIP as an optimization problem (ERM problem) that minimizes the expected residual of the so-called regularized gap function. Then, we focus on a SVIP subclass in which the function involved is assumed to be affine. We study the properties of the ERM problem and propose a quasi-Monte Carlo method for solving the problem. Comprehensive convergence analysis is included as well. [ABSTRACT FROM AUTHOR]

In this paper we propose a reduced vertex result for the robust solution of uncertain semidefinite optimization problems subject to interval uncertainty. If the number of decision variables is m and the size of the coefficient matrices in the linear matrix inequality constraints is n× n, a direct vertex approach would require satisfaction of 2 n( m+1)( n+1)/2 vertex constraints: a huge number, even for small values of n and m. The conditions derived here are instead based on the introduction of m slack variables and a subset of vertex coefficient matrices of cardinality 2 n−1, thus reducing the problem to a practically manageable size, at least for small n. A similar size reduction is also obtained for a class of problems with affinely dependent interval uncertainty. [ABSTRACT FROM AUTHOR]

In this paper, we deal with regularity conditions formulated by making use of the quasirelative interior and/or of the quasi-interior of the sets involved, guaranteeing strong duality for a convex optimization problem with cone (and equality) constraints and its Lagrange dual. We discuss also some recent results on this topic, which are proved to have either superfluous or contradictory assumptions. Several examples illustrate the theoretical considerations. [ABSTRACT FROM AUTHOR]

Optimality in the range space is expressed as a tangency condition for an affine set and a cone. In a previous paper, an algorithm was introduced that reaches tangency keeping the two sets nonintersecting. Here,we introduce an exact finite-convergence evolutive algorithm that reaches tangency while keeping the two sets intersecting. In the process of developing the algorithm, we add some completion to the theory (e.g., the description of the contact polytope). Furthermore, we introduce a new formula to express the maximum, which is the primal counterpart of the dual formula introduced in a previous paper. [ABSTRACT FROM AUTHOR]

Neural networks consist of highly interconnected and parallel nonlinear processing elements that are shown to be extremely effective in computation. This paper presents an architecture of recurrent neural networks that can be used to solve several classes of optimization problems. More specifically, a modified Hopfield network is developed and its internal parameters are computed explicitly using the valid-subspace technique. These parameters guarantee the convergence of the network to the equilibrium points, which represent a solution of the problem considered. The problems that can be treated by the proposed approach include combinatorial optimization problems, dynamic programming problems, and nonlinear optimization problems. [ABSTRACT FROM AUTHOR]

The multidimensional assignment problem (MAP) is an NP-hard combinatorial optimization problem occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal objective function cost of random instances of the MAP goes to zero as the problem size increases, when assignment costs are independent exponentially or uniformly distributed random variables. We prove also that the mean optimal solution goes to negative infinity when assignment costs are independent normally distributed random variables [ABSTRACT FROM AUTHOR]

This paper investigates the cost requirement for a space debris collecting mission aimed at removing heavy debris from low Earth orbits. The problem mixes combinatorial optimization to select the debris among a list of candidates and functional optimization to define the orbital manoeuvres. The solving methodology proceeds in two steps: Firstly, a specific transfer strategy with impulsive manoeuvres is defined so that the problem becomes of finite dimension; secondly the problem is linearized around an initial reference solution. A Branch and Bound algorithm is then applied iteratively to optimize simultaneously the debris selection and the orbital manoeuvres, yielding a new reference solution. The optimal solutions found are close to the initial guess despite a very complicated design space. The method is exemplified on a representative application case. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new method, namely the level-value estimation method, for finding global minimizer of continuous optimization problem. For this purpose, we define the variance function and the mean deviation function, both depend on a level value of the objective function to be minimized. These functions have some good properties when Newton's method is used to solve a variance equation resulting by setting the variance function to zero. We prove that the largest root of the variance equation equals the global minimal value of the corresponding optimization problem. We also propose an implementable algorithm of the level-value estimation method where importance sampling is used to calculate integrals of the variance function and the mean deviation function. The main idea of the cross-entropy method is used to update the parameters of sample distribution at each iteration. The implementable level-value estimation method has been verified to satisfy the convergent conditions of the inexact Newton method for solving a single variable nonlinear equation. Thus, convergence is guaranteed. The numerical results indicate that the proposed method is applicable and efficient in solving global optimization problems. [ABSTRACT FROM AUTHOR]

In this short note, we present a new proof of a classical algorithm for finding the projection of a point on the standard simplex. The new proof is based only on elementary geometric arguments. [ABSTRACT FROM AUTHOR]

In this paper, we deal with the sensitivity analysis in vector optimization. More specifically, formulae for inner and outer evaluating the S-derivative of the efficient point multifunction in parametric vector optimization problems are established. These estimating formulae are presented via the set of efficient/weakly efficient points of the S-derivative of the original multifunction, a composite multifunction of the objective function and the constraint mapping. The elaboration of the formulae in vector optimization problems, having multifunction constraints and semiinfinite constraints, is also undertaken. Furthermore, examples are provided for analyzing and illustrating the obtained results. [ABSTRACT FROM AUTHOR]

In this paper, we introduce locally absolutely continuous functions of two variables and functions of two variables of locally finite variation defined on an unbounded interval. We generalize Helly's principle of choice to functions of locally finite variation and apply this principle to an infinite-horizon optimal control problem of the Goursat-Darboux type. [ABSTRACT FROM AUTHOR]

In this paper, we reformulate a nonlinear semidefinite programming problem into an optimization problem with a matrix equality constraint. We apply a lower-order penalization approach to the reformulated problem. Necessary and sufficient conditions that guarantee the global (local) exactness of the lower-order penalty functions are derived. Convergence results of the optimal values and optimal solutions of the penalty problems to those of the original semidefinite program are established. Since the penalty functions may not be smooth or even locally Lipschitz, we invoke the Ekeland variational principle to derive necessary optimality conditions for the penalty problems. Under certain conditions, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original semidefinite program. [ABSTRACT FROM AUTHOR]

In this marketing-oriented era where manufacturers maximize profits through customer satisfaction, there is an increasing need to design a product line rather than a single product. By offering a product line, the manufacturer can customize his or her products to the needs of a variety of segments in order to maximize profits by satisfying more customers than a single product would. When the amount of data on customer preferences or possible product configurations is large and no analytical relations can be established, the problem of an optimal product line design becomes very difficult and there are no traditional methods to solve it. In this paper, we show that the usage of genetic algorithms, a mathematical heuristics mimicking the process of biological evolution, can solve efficiently the problem. Special domain operators were developed to help the genetic algorithm mitigate cannibalization and enhance the algorithm's local search abilities. Using manufacturer's profits as the criteria for fitness in evaluating chromosomes, the usage of domain specific operators was found to be highly beneficial with better final results. Also, we have hybridized the genetic algorithm with a linear programming postprocessing step to fine tune the prices of products in the product line. Attacking the core difficulty of cannibalization in the algorithm, the operators introduced in this work are unique. [ABSTRACT FROM AUTHOR]

Computing the chromatic number of a graph is an NP-hard problem. For random graphs and some other classes of graphs, estimators of the expected chromatic number have been well studied. In this paper, a new 0–1 integer programming formulation for the graph coloring problem is presented. The proposed new formulation is used to develop a method that generates graphs of known chromatic number by using the KKT optimality conditions of a related continuous nonlinear program. [ABSTRACT FROM AUTHOR]

We study the problems of maximizing a monotone non-submodular function subject to two types of constraints, either an independent system constraint or a p-matroid constraint. These problems often occur in the context of combinatorial optimization, operations research, economics and especially, machine learning and data science. Using the generalized curvature α and the submodularity ratio γ or the diminishing returns ratio ξ , we analyze the performances of the widely used greedy algorithm, which yields theoretical approximation guarantees of 1 α [ 1 - (1 - α γ K) k ] and ξ p + α ξ for the two types of constraints, respectively, where k, K are, respectively, the minimum and maximum cardinalities of a maximal independent set in the independent system, and p is the minimum number of matroids such that the independent system can be expressed as the intersection of p matroids. When the constraint is a cardinality one, our result maintains the same approximation ratio as that in Bian et al. (Proceedings of the 34th international conference on machine learning, pp 498–507, 2017); however, the proof is much simpler owning to the new definition of the greedy curvature. In the case of a single matroid constraint, our result is competitive compared with the existing ones in Chen et al. (Proceedings of the 35th international conference on machine learning, pp 804–813, 2018) and Gatmiry and Rodriguez (Non-submodular function maximization subject to a matroid constraint, with applications, 2018. arXiv:1811.07863v4). In addition, we bound the generalized curvature, the submodularity ratio and the diminishing returns ratio for several important real-world applications. Computational experiments are also provided supporting our analyses. [ABSTRACT FROM AUTHOR]

We prove a sufficient global optimality condition for the problem of minimizing a quadratic function subject to quadratic equality constraints where the variables are allowed to take values -1 and 1. We extend the condition to quadratic problems with matrix variables and orthonormality constraints, and in particular to the quadratic assignment problem. [ABSTRACT FROM AUTHOR]

The goal of a melon harvesting robot is to maximize the number of melons it harvests given a progressive speed. Selecting the sequence of melons that yields this maximum is an example of the orienteering problem with time windows. We present a dynamic programming-based algorithm that yields a strictly optimal solution to this problem. In contrast to similar methods, this algorithm utilizes the unique properties of the robotic harvesting task, such as uniform gain per vertex and time windows, to expand domination criteria and quicken the optimal path selection process. We prove that the complexity of this algorithm is linearithmic in the number of melons and can be implemented online if there is a bound on the density. The results of this algorithm are demonstrated to be significantly better than the standard heuristic solution for a wide range of harvesting robot scenarios. [ABSTRACT FROM AUTHOR]

We discuss recent positive experiences applying convex feasibility algorithms of Douglas-Rachford type to highly combinatorial and far from convex problems. [ABSTRACT FROM AUTHOR]

An element-free Galerkin method is presented to analyze isotropic and laminated composite plates. This method employs the moving least square technique to approximate functions. In the analysis procedure, a collocation method is used to enforce boundary conditions. A consistent multi-objective optimization procedure is also applied. The function introduced here consists of minimizing the weight and cost, as well as of maximizing the load. A genetic algorithm is used for the optimization process. [ABSTRACT FROM AUTHOR]

Rollout algorithms are heuristic algorithms that can be applied to solve deterministic and stochastic dynamic programming problems. The basic idea is to use the cost obtained by applying a well known heuristic, called the base policy, to approximate the value of the optimal cost-to-go. We develop a theoretical approach to prove, for the 0-1 knapsack problem, that the minimum performance ratio of the rollout algorithms tends to be significantly greater when the performance ratio of the corresponding base policy is poor and that the worst-case performance ratio is significantly better than the one of the corresponding base policies. [ABSTRACT FROM AUTHOR]

Connectedness of efficient solutions is a powerful property in multiple objective combinatorial optimization since it allows the construction of the complete efficient set using neighborhood search techniques. However, we show that many classical multiple objective combinatorial optimization problems do not possess the connectedness property in general, including, among others, knapsack problems (and even several special cases) and linear assignment problems. We also extend known non-connectedness results for several optimization problems on graphs like shortest path, spanning tree and minimum cost flow problems. Different concepts of connectedness are discussed in a formal setting, and numerical tests are performed for two variants of the knapsack problem to analyze the likelihood with which non-connected adjacency graphs occur in randomly generated instances. [ABSTRACT FROM AUTHOR]

We address the route selection problem for Unmanned Air Vehicles (UAV) under multiple objectives. We consider a general case for this problem, where the UAV has to visit several targets and return to the base. We model this problem as a combination of two combinatorial problems. First, the path to be followed between each pair of targets should be determined. We model this as a multi-objective shortest path problem. Additionally, we need to determine the order of the targets to be visited. We model this as a multi-objective traveling salesperson problem (MOTSP). The overall problem is a combination of these two problems, which we define as a generalized MOTSP. We develop an exact interactive approach to identify the best paths and the best tour of a decision maker under a linear utility function. [ABSTRACT FROM AUTHOR]

Approximation schemes for functional optimization problems with admissible solutions dependent on a large number d of variables are investigated. Suboptimal solutions are considered, expressed as linear combinations of n-tuples from a basis set of simple computational units with adjustable parameters. Different choices of basis sets are compared, which allow one to obtain suboptimal solutions using a number n of basis functions that does not grow “fast” with the number d of variables in the admissible decision functions for a fixed desired accuracy. In these cases, one mitigates the “curse of dimensionality,” which often makes unfeasible traditional linear approximation techniques for functional optimization problems, when admissible solutions depend on a large number d of variables. [ABSTRACT FROM AUTHOR]

Stochastic global search algorithms such as genetic algorithms are used to attack difficult combinatorial optimization problems. However, genetic algorithms suffer from the lack of a convergence proof. This means that it is difficult to establish reliable algorithm braking criteria without extensive a priori knowledge of the solution space. The hybrid genetic algorithm presented here combines a genetic algorithm with simulated annealing in order to overcome the algorithm convergence problem. The genetic algorithm runs inside the simulated annealing algorithm and provides convergence via a Boltzmann cooling process. The hybrid algorithm was used successfully to solve a classical 30-city traveling salesman problem; it consistently outperformed both a conventional genetic algorithm and a conventional simulated annealing algorithm. [ABSTRACT FROM AUTHOR]

We consider a bilevel optimization problem where the upper level is a scalar optimization problem and the lower level is a vector optimization problem. For the lower level, we deal with weakly efficient solutions. We approach our problem using a suitable penalty function which vanishes over the weakly efficient solutions of the lower-level vector optimization problem and which is nonnegative over its feasible set. Then,we use an exterior penalty method. [ABSTRACT FROM AUTHOR]

This article studies the continuous modular design (MD) problem. First, the article presents duality results for problem (MD) based upon the Wolfe duality theory for nonlinear programming. From these results, an optimality test for problem (MD) is derived that consists of solving a single, balanced transportation problem. Second, the article shows that two well-known optimization approaches, generalized Benders decomposition and the separable programming approach of linear programming, each have the potential to solve efficiently large instances of problem (MD). [ABSTRACT FROM AUTHOR]

The knapsack problem (KP) is generalized taking into account a precedence relation between items. Such a relation can be represented by means of a directed acyclic graph, where nodes correspond to items in a one-to-one way. As in ordinary KPs, each item is associated with profit and weight, the knapsack has a fixed capacity, and the problem is to determine the set of items to be included in the knapsack. However, each item can be adopted only when all of its predecessors have been included in the knapsack. The knapsack problem with such an additional set of constraints is referred to as the precedence-constrained knapsack problem (PCKP). We present some dynamic programming algorithms that can solve small PCKPs to optimality, as well as a preprocessing method to reduce the size of the problem. Combining these, we are able to solve PCKPs with up to 2000 items in less than a few minutes of CPU time. [ABSTRACT FROM AUTHOR]