Search

Set-valued optimization using the set approach is a research topic of high interest due to its practical relevance and numerous interdependencies to other fields of optimization. However, it is a very difficult task to solve these optimization problems even for specific cases. In this paper, we study set-valued optimization problems and develop a multiobjective optimization problem that is strongly related to it. We prove that the set of weakly minimal solutions of this subproblem is closely related to the set of weakly minimal elements of the set-valued optimization problem and that these sets can get arbitrarily close in a certain sense. Subsequently, we introduce a concept of approximations of the solution set of the set-valued optimization problem. We define a quality measure in the image space that can be used to compare finite approximations of this kind and outline a procedure to enhance a given approximation. We conclude the paper with some numerical examples. [ABSTRACT FROM AUTHOR]

Pareto frontiers of bicriteria continuous convex problems can be efficiently computed and optimal theoretical performance bounds have been established. In the case of bicriteria mixed-integer problems, the approximation of the Pareto frontier becomes, however, significantly harder. In this paper, we propose a new algorithm for approximating the Pareto frontier of bicriteria mixed-integer programs with convex constraints. Such Pareto frontiers are composed of patches of solutions with shared assignments for the discrete variables. By adaptively creating such a patchwork, our algorithm is able to create approximations that converge quickly to the true Pareto frontier. As a quality measure, we use the difference in hypervolume between the approximation and the true Pareto frontier. At least a certain number of patches is required to obtain an approximation with a given quality. This patch complexity gives a lower bound on the number of required computations. We show that our algorithm performs a number of optimization steps that are of a similar order as this lower bound. We provide an efficient MIP-based implementation of this algorithm. The efficiency of our algorithm is illustrated with numerical results showing that our algorithm has a strong theoretical performance guarantee while being competitive with other state-of-the-art approaches in practice. [ABSTRACT FROM AUTHOR]

Benson's outer approximation algorithm and its variants are the most frequently used methods for solving linear multiobjective optimization problems. These algorithms have two intertwined parts: single-objective linear optimization on one hand, and a combinatorial part closely related to vertex enumeration on the other. Their separation provides a deeper insight into Benson's algorithm, and points toward a dual approach. Two skeletal algorithms are defined which focus on the combinatorial part. Using different single-objective optimization problems yields different algorithms, such as a sequential convex hull algorithm, another version of Benson's algorithm with the theoretically best possible iteration count, and the dual algorithm of Ehrgott et al. [A dual variant of Benson's 'outer approximation algorithm' for multiple objective linear programming. J Glob Optim. 2012;52:757–778]. The implemented version is well suited to handle highly degenerate problems where there are many linear dependencies among the constraints. On problems with 10 or more objectives, it shows a significant increase in efficiency compared to Bensolve – due to the reduced number of iterations and the improved combinatorial handling. [ABSTRACT FROM AUTHOR]

In this paper, we consider a nonsmooth vector optimization problem involving locally Lipschitz generalized approximate convex functions and find some relations between approximate convexity and generalized approximate convexity. We establish relationships between vector variational inequalities and nonsmooth vector optimization problem using the generalized approximate convexity as a tool. [ABSTRACT FROM AUTHOR]

In this paper, we focus on approximating convex compact bodies. For a convex body described as the feasible set in objective space of a multiple objective programme, we show that finding it is equivalent to finding the non-dominated set of a multiple objective programme. This equivalence implies that convex bodies can be approximated using multiple objective optimization algorithms. Therefore, we propose a revised outer approximation algorithm for convex multiple objective programming problems to approximate convex bodies. Finally, we apply the algorithm to solve reachable sets of control systems and use numerical examples to show the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

In this work, we combine outer-approximation (OA) and bundle method algorithms for dealingwithmixed-integer non-linear programming (MINLP) problems with nonsmooth convex objective and constraint functions. As the convergence analysis of OA methods relies strongly on the differentiability of the involved functions, OA algorithms may fail to solve general nonsmooth convex MINLP problems. In order to obtain OA algorithms that are convergent regardless the structure of the convex functions, we solve the underlying OA's non-linear subproblems by a specialized bundle method that provides necessary information to cut off previously visited (non-optimal) integer points. This property is crucial for proving (finite) convergence of OA algorithms. We illustrate the numerical performance of the given proposal on a class of hybrid robust and chanceconstrained problems that involve a random variable with finite support. [ABSTRACT FROM AUTHOR]

We survey approximation issues matching ideas and tools from the fields of polynomial approximation, moderately exponential computation and fixed parameter tractability aiming at designing approximation algorithms achieving ratios unachievable in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. This research programme, despite its relative youth, is becoming very active in computer science and in combinatorial optimization and motivates extensive research. [ABSTRACT FROM PUBLISHER]

In this article, we present a primal-dual 3-approximation algorithm for the stochastic priority facility location problem. Combined with greedy augmentation procedure, such performance factor is further improved to 1.8526. [ABSTRACT FROM PUBLISHER]

This article deals with multicriteria optimization models and algorithms of movement scheduling for many objects to synchronize their movement (2CMSS problem). The model consists of two parts: (1) node–disjoint path planning visiting specified nodes for K objects with a given vector of intermediate nodes for each one (NDSP problem); (2) movement synchronization in some intermediate nodes (MS problem). For synchronous movement, two categories of criteria are defined: time of movement and ‘distance’ of K-moved objects from the movement pattern. We defined the problem as a discrete-continuous, non-linear, two-criteria mathematical programming problem. We proposed to use a two-stage algorithm to solve the 2CMSS problem (as lexicographic solution): At first we have to find the vector of node–disjoint shortest paths for K objects visiting intermediate nodes to set optimal paths under the assumption that we use maximal possible velocities on each arc belonging to a path for each object (solution of the NDSP problem), and next we try to decrease the values of velocities to optimize the second criterion (synchronization, solution of the MS problem). Experimental analyses of effectiveness and complexity of the algorithms are presented. [ABSTRACT FROM AUTHOR]

The fundamental theorem of linear programming (LP) states that every feasible linear program that is bounded below has an optimal solution in a zero-dimensional face (a vertex) of the feasible polyhedron. We extend this result in two directions. We find a larger class of objective functions for which vertex optimality holds, and we give conditions guaranteeing the existence of an optimal solution in a larger family of faces of the feasible polyhedron. Our results also extend, with a very simple proof, the Frank-Wolfe theorem on the existence of an optimal solution to a Quadratic Program that is bounded below. We then apply our results to build up a general framework for obtaining upper and lower bounds and constant factor approximation algorithms for optimization problems. Furthermore, we show that several known results providing continuous formulations for discrete optimization problems can be easily derived and generalized with our extension of the fundamental theorem of Linear Programming. Finally, by exploiting the equivalence between continuous and discrete formulations of the problem of minimizing a function on a polyhedron, we prove polynomial-time solvability and present efficient algorithms for several new classes of continuous optimization problems. [ABSTRACT FROM AUTHOR]