A common way to produce a convex relaxation of a Mixed Integer Quadratically Constrained Program (MIQCP) is to lift the problem into a higher dimensional space by introducing variables $Y_{ij}$ to represent each of the products $x_i x_j$ of variables appearing in a quadratic form. One advantage of such extended relaxations is that they can … 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
This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, … Read more
Many industrial problems can be naturally formulated using Mixed Integer Nonlinear Programming (MINLP). Motivated by the demand for Open-Source solvers for real-world MINLP problems, we have developed a spatial Branch-and-Bound software package named COUENNE (Convex Over- and Under-ENvelopes for Nonlinear Estimation). In this paper, we present the structure of couenne and discuss in detail our … Read more
The submodular knapsack set is the discrete lower level set of a submodular function. The modular case reduces to the classical linear 0-1 knapsack set. One motivation for studying the submodular knapsack polytope is to address 0-1 programming problems with uncertain coefficients. Under various assumptions, a probabilistic constraint on 0-1 variables can be modeled as … Read more
We study mixed integer nonlinear programs (MINLP)s that are driven by a collection of indicator variables where each indicator variable controls a subset of the decision variables. An indicator variable, when it is “turned off”, forces some of the decision variables to assume fixed values, and, when it is “turned on”, forces them to belong … Read more
We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide a polynomial-time algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r is a constant that depends on certain Frobenius numbers of the individual … Read more
We propose a solution method for a water-network optimization problem using a nonconvex continuous NLP (nonlinear programming) relaxation and a MINLP (mixed integer nonlinear programming) search. Our approach employs a relatively simple and accurate model that pays some attention to the requirements of the solvers that we employ. Our view is that in doing so, … Read more
This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, … Read more
In this work, we consider a classification problem where the objects to be classified are bags of instances which are vectors measuring d different attributes. The classification rule is defined in terms of a ball, whose center and radius are the parameters to be computed. Given a bag, it is assigned to the positive class … Read more