We present well known properties related to the topology of Steiner minimal trees and to the geometric position of Steiner points, and investigate their application in the main exact algorithms that have been proposed for the Euclidean Steiner problem. We discuss the difficulty in the application of properties that were very successfully applied to solve … Read more
We present a model development framework and numerical solution approach to the general problem-class of packing convex objects into optimized convex containers. Specifically, here we discuss the problem of packing ovals (egg-shaped objects, defined here as generalized ellipses) into optimized regular polygons in R”. Our solution strategy is based on the use of embedded Lagrange … Read more
LSP(n), the largest small polygon with n vertices, is defined as the polygon of unit diameter that has maximal area A(n). Finding the configuration LSP(n) and the corresponding A(n) for even values n >= 6 is a long-standing challenge that leads to an interesting class of nonlinear optimization problems. We present numerical solution estimates for … Read more
Semidefinite programming relaxations complement polyhedral relaxations for quadratic optimization, but global optimization solvers built on polyhedral relaxations cannot fully exploit this advantage. This paper develops linear outer-approximations of semidefinite constraints that can be effectively integrated into global solvers. The difference from previous work is that our proposed cuts are (i) sparser with respect to the … Read more
In real life applications optimization problems with more than one objective function are often of interest. Next to handling multiple objective functions, another challenge is to deal with uncertainties concerning the realization of the decision variables. One approach to handle these uncertainties is to consider the objectives as set-valued functions. Hence, the image of one … Read more
In this paper, we consider the nonconvex quadratic optimization problem with a single quadratic constraint. First we give a theoretical characterization of the local non-global minimizers. Then we extend the recent characterization of the global minimizer via a generalized eigenvalue problem to the local non-global minimizers. Finally, we use these results to derive an efficient … Read more
Decades of advances in mixed-integer linear programming (MILP) and recent development in mixed-integer second-order-cone programming (MISOCP) have translated very mildly to progresses in global solving nonconvex mixed-integer quadratically constrained programs (MIQCP). In this paper we propose a new approach, namely Compact Disjunctive Approximation (CDA), to approximate nonconvex MIQCP to arbitrary precision by convex MIQCPs, which … Read more
Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvatal rank. We show that almost all known cutting planes have Chvatal rank 1. All these inequalities have an associated hypergraph that is beta-acyclic, thus, … Read more
The generalized problem of moments is a conic linear optimization problem over the convex cone of positive Borel measures with given support. It has a large variety of applications, including global optimization of polynomials and rational functions, options pricing in finance, constructing quadrature schemes for numerical integration, and distributionally robust optimization. A usual solution approach, … Read more
We treat the Feature Selection problem in the Support Vector Machine (SVM) framework by adopting an optimization model based on use of the $\ell_0$ pseudo–norm. The objective is to control the number of non-zero components of normal vector to the separating hyperplane, while maintaining satisfactory classification accuracy. In our model the polyhedral norm $\|.\|_{[k]}$, intermediate … Read more