Covering problems are well studied in the Operations Research literature under the assumption that both the set of users and the set of potential facilities are finite. In this paper we address the following variant, which leads to a Mixed Integer Nonlinear Program (MINLP): locations of p facilities are sought along the edges of a … Read more
The Euclidean Steiner Tree Problem in dimension greater than two is notoriously difficult. The successful methods for exact solution are not based on mathematical-optimization methods — rather, they involve very sophisticated enumeration. There are two types of mathematical-optimization formulations in the literature, and it is an understatement to say that neither scales well enough to … Read more
We complete the complexity classification by degree of minimizing a polynomial in two variables over the integer points in a polyhedron. Previous work shows that in two variables, optimizing a quadratic polynomial over the integer points in a polyhedral region can be done in polynomial time, while optimizing a quartic polynomial in the same type … Read more
The MVE estimator is an important tool in robust regression and outlier detection in statistics. We develop fast and efficient algorithms for the MVE estimator problem and discuss how they can be implemented efficiently. The novelty of our approach stems from the recent developments in the first-order algorithms for solving the related Minimum Volume Enclosing … Read more
We propose a feasible active set method for convex quadratic programming problems with non-negativity constraints. This method is specifically designed to be embedded into a branch-and-bound algorithm for convex quadratic mixed integer programming problems. The branch-and-bound algorithm generalizes the approach for unconstrained convex quadratic integer programming proposed by Buchheim, Caprara and Lodi to the presence … Read more
This note presents a theoretical analysis of disjunctive constraints featuring unbounded variables. In this framework, classical modeling techniques, including big-M approaches, are not applicable. We introduce a lifted second-order cone formulation of such on/off constraints and discuss related constraint qualification issues. A solution is proposed to avoid solvers’ failure. CitationH. L. Hijazi and L.Liberti “Constraint … Read more
This paper presents a relatively “unfettered” method for finding global optima to constrained nonlinear programs. The method reformulates the given program into a bi-objective mixed-integer program that is then solved for the Nash equilibrium. A numerical example (whose solution provides a new benchmark against which other algorithms may be assessed) is included to illustrate the … Read more
In this paper we provide a unified treatment of general two-term disjunctions on cross-sections of the second-order cone. We derive a closed-form expression for a convex inequality that is valid for such a disjunctive set and show that this inequality is sufficient to characterize the closed convex hull of all two-term disjunctions on ellipsoids and … Read more
A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown—by several authors using different techniques—that the convex hull of the intersection of an ellipsoid, $\E$, and a split disjunction, $(l – x_j)(x_j – u) \le 0$ with $l < u$, equals the intersection ... Read more
The Quadratic Knapsack Problem (QKP) is a well-known NP-hard combinatorial optimisation problem, with many practical applications. We present a ‘cut-and-branch’ algorithm for the QKP, in which a cutting-plane phase is followed by a branch-and-bound phase. The cutting-plane phase is more sophisticated than the existing ones in the literature, incorporating several classes of cutting planes, two … Read more