If a mathematical program (be it linear or nonlinear) has many symmetric optima, solving it via Branch-and-Bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for automatically finding the formulation group of any given Mixed-Integer Nonlinear Program, and reformulating the problem so … Read more
We improve the best known lower bounds on the distance between two points of a Morse cluster in $\mathbb{R}^3$, with $\rho \in [4.967,15]$. Our method is a generalization of the one applied to the Lennard-Jones potential in~\cite{Schac}, and it also leads to improvements of lower bounds for the energy of a Morse cluster. Some of … Read more
In this paper, we develop a convexification tool that enables the construction of convex hulls for orthogonal disjunctive sets using convex extensions and disjunctive programming techniques. A distinguishing feature of our technique is that, unlike most applications of disjunctive programming, it does not require the introduction of new variables in the relaxation. We develop and … Read more
Non-Convex Quadratic Programming with Box Constraints is a fundamental NP-hard global optimisation problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We prove several fundamental results concerned with these convex sets: we determine their dimension, characterise their extreme points and vertices, show their invariance under certain affine transformations, … Read more
The convex cone of $n \times n$ completely positive (CPP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CPP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for $n \le 4$ only, every DNN matrix is CPP. … Read more
Given a 0-1 integer programming problem, several authors have introduced sequential relaxation techniques — based on linear and/or semidefinite programming — that generate the convex hull of integer points in at most $n$ steps. In this paper, we introduce a sequential relaxation technique, which is based on $p$-order cone programming ($1 \le p \le \infty$). … Read more
In this paper we propose a Fully Polynomial Time Approximation Scheme (FPTAS) for a class of optimization problems where the feasible region is a polyhedral one and the objective function is the sum or product of linear ratio functions. The class includes the well known ones of Linear (Sum-of-Ratios) Fractional Programming and Multiplicative Programming. Article … Read more
We present semidefinite relaxations of nonconvex, box-constrained quadratic programming, which incorporate the first- and second-order necessary optimality conditions. We compare these relaxations with a basic semidefinite relaxation due to Shor, particularly in the context of branch-and-bound to determine a global optimal solution, where it is shown empirically that the new relaxations are significantly stronger. We … Read more
We describe a major update of our Matlab freeware GloptiPoly for parsing generalized problems of moments and solving them numerically with semidefinite programming. Citation 28 June 2007 Article Download View GloptiPoly 3: moments, optimization and semidefinite programming
In this paper, simple linear programming procedure is proposed for generating all efficient extreme points and all efficient extreme rays of a multiple objective linear programming problem (V P). As an application we solve the linear multiplicative programming associated with the problem (VP). Citation submitted Article Download View Generating All Efficient Extreme Points in Multiple … Read more