Skip to: Content | Navigation | Footer
It is well known that selecting a good Mixed Integer Programming (MIP) formulation is crucial for an effective solution with state-of-the art solvers. While best practices and guidelines for constructing good formulations abound, there is rarely a systematic construction leading to the best possible formulation. We introduce embedding formulations and complexity as a new MIP formulation paradigm for systematically constructing formulations for disjunctive constraints that are optimal with respect to size. More specifically, they yield the smallest possible ideal formulation (i.e. one whose LP relaxation has integral extreme points) among all formulations that only use 0-1 auxiliary variables. We use the paradigm to characterize optimal formulations for SOS2 constraints and certain piecewise linear functions of two variables. We also show that the resulting formulations can provide a significant computational advantage over all known formulations for piecewise linear functions.
To appear in Management Science, 2017.
[PDF] [DOI:10.1287/mnsc.2017.2856]
Juan Pablo Vielma, Iain Dunning, Joey Huchette and Miles Lubin
In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma, Ahmed and Nemhauser (2008) and Hijazi, Bonami and Ouorou (2013) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on an extended or lifted polyhedral relaxation of the Lorentz cone by Ben-Tal and Nemirovski (2001) that is extremely economical, but whose approximation quality cannot be iteratively improved. The second is based on a lifted polyhedral relaxation of the euclidean ball that can be constructed using techniques introduced by Tawarmalani and Sahinidis (2005). This relaxation is less economical, but its approximation quality can be iteratively improved. Unfortunately, while the approach of Vielma, Ahmed and Nemhauser is applicable for general MICQP problems, the approach of Hijazi, Bonami and Ouorou can only be used for MICQP problems with convex quadratic constraints. In this paper we show how a homogenization procedure can be combined with the technique by Tawarmalani and Sahinidis to adapt the extended formulation used by Hijazi, Bonami and Ouorou to a class of conic mixed integer programming problems that include general MICQP problems. We then compare the effectiveness of this new extended formulation against traditional and extended formulation-based algorithms for MICQP. We find that this new formulation can be used to improve various LP-based algorithms. In particular, the formulation provides an easy-to-implement procedure that, in our benchmarks, significantly improved the performance of commercial MICQP solvers.
Mathematical Programming Computation 9, 2017. pp. 369-418.
[PDF] [DOI:10.1007/s12532-016-0113-y][BibTeX]
Sina Modaresi and Juan Pablo Vielma
In this paper we consider an aggregation technique introduced by Yıldıran, 2009 to study the convex hull of regions defined by two quadratic inequalities or by a conic quadratic and a quadratic inequality. Yıldıran shows how to characterize the convex hull of open sets defined by two strict quadratic inequalities using Linear Matrix Inequalities (LMI). We show how this aggregation technique can be easily extended to yield valid conic quadratic inequalities for the convex hull of open sets defined by two strict quadratic inequalities or by a strict conic quadratic and a strict quadratic inequality. We also show that for sets defined by a strict conic quadratic and a strict quadratic inequality, under one additional containment assumption, these valid inequalities characterize the convex hull exactly. We also show that under certain topological assumptions, the results from the open setting can be extended to characterize the closed convex hull of sets defined with non-strict conic and quadratic inequalities.
Mathematical Programming 164, 2017. pp. 383-409.
[PDF] [DOI:10.1007/s10107-016-1084-5][BibTeX]
Miles Lubin, Emre Yamangil, Russell Bent and Juan Pablo Vielma
Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this \textit{extended formulation} we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro.
To appear in Mathematical Programming, 2017.
[PDF] [DOI:10.1007/s10107-017-1191-y]
Miles Lubin, Ilias Zadik and Juan Pablo Vielma
We consider the question of which nonconvex sets can be represented exactly as the feasible sets of mixed-integer convex optimization problems. We state the first complete characterization for the case when the number of possible integer assignments is finite. We develop a characterization for the more general case of unbounded integer variables together with a simple necessary condition for representability which we use to prove the first known negative results. Finally, we study representability of subsets of the natural numbers, developing insight towards a more complete understanding of what modeling power can be gained by using convex sets instead of polyhedral sets; the latter case has been completely characterized in the context of mixed-integer linear optimization.
In F. Eisenbrand and J. Könemann, editors, Proceedings of the 19th Conference on Integer Programming and Combinatorial Optimization (IPCO 2017), Lecture Notes in Computer Science 10328, 2017. pp. 392-404.
Joey Huchette and Juan Pablo Vielma
We present novel mixed-integer programming (MIP) formulations for (nonconvex) piecewise linear functions. Leveraging recent advances in the systematic construction of MIP formulations for disjunctive sets, we derive new formulations for univariate functions using a geometric approach, and for bivariate functions using a combinatorial approach. All formulations derived are small (logarithmic in the number of piecewise segments of the function domain) and strong, and we present extensive computational experiments in which they offer substantial computational performance gains over existing approaches. We characterize the connection between our geometric and combinatorial formulation approaches, and explore the benefits and drawbacks of both. Finally, we present PiecewiseLinearOpt, an extension of the JuMP modeling language in Julia that implements our models (alongside other formulations from the literature) through a high-level interface, hiding the complexity of the formulations from the end-user.
Submitted for publication, 2017.
Miles Lubin, Ilias Zadik and Juan Pablo Vielma
Characterizations of the sets with mixed integer programming (MIP) formulations using only rational linear inequalities (rational MILP representable) and those with formulations that use arbitrary closed convex constraints (MICP representable) were given by Jeroslow and Lowe (1984), and Lubin, Zadik and Vielma (2017). The latter also showed that even MICP representable subsets of the natural numbers can be more irregular than rational MILP representable ones, unless certain rationality is imposed on the formulation. In this work we show that for MICP representable subsets of the natural numbers, a cleaner version of the rationality condition from Lubin, Zadik and Vielma (2017) still results in the same periodical behavior appearing in rational MILP representable sets after a finite number of points are excluded. We further establish corresponding results for compact convex sets, the epigraphs of certain functions with compact domain and the graphs of certain piecewise linear functions with unbounded domains. We then show that MICP representable sets that are unions of an infinite family of convex sets with the same volume are unions of translations of a finite sub-family. Finally, we conjecture that all MICP representable sets are (possibly infinite) unions of homothetic copies of a finite number of convex sets.
Submitted for publication, 2017.
There is often a significant trade-off between formulation strength and size in mixed integer programming (MIP). When modelling convex disjunctive constraints (e.g. unions of convex sets) this trade-off can be resolved by adding auxiliary continuous variables. However, adding these variables can result in a deterioration of the computational effectiveness of the formulation. For this reason, there has been considerable interest in constructing strong formulations that do not use continuous auxiliary variables. We introduce a technique to construct formulations without these detrimental continuous auxiliary variables. To develop this technique we introduce a natural non-polyhedral generalization of the Cayley embedding of a family of polytopes and show it inherits many geometric properties of the original embedding. We then show how the associated formulation technique can be used to construct small and strong formulation for a wide range of disjunctive constraints. In particular, we show it can recover and generalize all known strong formulations without continuous auxiliary variables.
Submitted for publication, 2017.
Joey Huchette and Juan Pablo Vielma
An important problem in optimization is the construction of mixed-integer programming (MIP) formulations of disjunctive constraints that are both strong and small. Motivated by lower bounds on the number of integer variables that are required by traditional MIP formulations, we present a more general mixed-integer branching formulation framework. Our approach maintains favorable algorithmic properties of traditional MIP formulations: in particular, amenability to branch-and-bound and branch-and-cut algorithms. Our main technical result gives an explicit linear inequality description for both traditional MIP and mixed-integer branching formulations for a wide range of disjunctive constraints. The formulations obtained from this description have linear programming relaxations that are as strong as possible and generalize some of the most computationally effective formulations for piecewise linear functions and other disjunctive constraints. We use this result to produce a strong mixed-integer branching formulation for any disjunctive constraint that uses only two integer variables and a linear number of extra constraints. We sharpen this result for univariate piecewise linear functions and annulus constraints arising in power systems and robotics, producing strong mixed-integer branching formulations that use only two integer variables and a constant (less than or equal to 6) number of general inequality constraints. Along the way, we produce two strong logarithmic-sized traditional MIP formulations for the annulus constraint using our main technical result, illustrating its broader utility in the traditional MIP setting.
Submitted for publication, 2017.
Sina Modaresi, Mustafa R. Kılınç and Juan Pablo Vielma
We study the generalization of split and intersection cuts from Mixed Integer Linear Programming to the realm of Mixed Integer Non-linear Programming. Constructing such cuts requires calculating the convex hull of the difference of two convex sets with specific geometric structures. We introduce two techniques to give precise characterizations of such convex hulls and use them to construct split and intersection cuts for several classes of sets. In particular, we give simple formulas for split cuts for essentially all convex quadratic sets and for intersection cuts for a wide variety of convex quadratic sets.
Mathematical Programming 155, 2016. pp. 575-611.
[PDF] [DOI:10.1007/s10107-015-0866-5][BibTeX]
Miles Lubin, Emre Yamangil, Russell Bent and Juan Pablo Vielma
We present a unifying framework for generating extended formulations for the polyhedral outer approximations used in algorithms for mixed-integer convex programming (MICP). Extended formulations lead to fewer iterations of outer approximation algorithms and generally faster solution times. First, we observe that all MICP instances from the MINLPLIB2 benchmark library are conic representable with standard symmetric and nonsymmetric cones. Conic reformulations are shown to be effective extended formulations themselves because they encode separability structure. For mixed-integer conic-representable problems, we provide the first outer approximation algorithm with finite-time convergence guarantees, opening a path for the use of conic solvers for continuous relaxations. We then connect the popular modeling framework of disciplined convex programming (DCP) to the existence of extended formulations independent of conic representability. We present evidence that our approach can yield significant gains in practice, with the solution of a number of open instances from the MINLPLIB2 benchmark library.
In Q. Louveaux and M. Skutella, editors, Proceedings of the 18th Conference on Integer Programming and Combinatorial Optimization (IPCO 2016), Lecture Notes in Computer Science 9682, 2016. pp. 102-113.
Joey Huchette and Juan Pablo Vielma
We present a framework for constructing small, strong mixed-integer formulations for disjunctive constraints. Our approach is a generalization of the logarithmically-sized formulations of Vielma and Nemhauser for SOS2 constraints, and we offer a complete characterization of its expressive power. We apply the framework to a variety of disjunctive constraints, producing novel, small, and strong formulations for outer approximations of multilinear terms, generalizations of special ordered sets, piecewise linear functions over a variety of domains, and obstacle avoidance constraints.
Submitted for publication, 2016.
Denis Saure and Juan Pablo Vielma
Questionnaires for adaptive choice-based conjoint analysis aim at minimizing some measure of the uncertainty associated with estimates of preference parameters (e.g. partworths). Bayesian approaches to conjoint analysis quantify this uncertainty with a multivariate distribution that is updated after the respondent answers. Unfortunately, this update often requires multidimensional integration, which effectively reduces the adaptive selection of questions to impractical enumeration. An alternative approach is the polyhedral method by Toubia et al. (2004), which quantifies the uncertainty through a (convex) polyhedron. The approach has a simple geometric interpretation, and allows for quick credibility-region updates and effective optimization-based heuristics for adaptive \qsel. However, its performance deteriorates with high response-error rates. Available adaptations to this method do not preserve all of the geometric simplicity and interpretability of the original approach. We show how, by using normal approximations to posterior distributions, one can include response-error in an approximate Bayesian approach that is as intuitive as the polyhedral approach, and allows the use of effective optimization-based techniques for adaptive question selection. This ellipsoidal approach extends the effectiveness of the polyhedral approach to the high error-rate setting and provides a simple geometric interpretation (from which the method derives its name) of Bayesian approaches.} Our results precisely quantify the relationship between the most popular efficiency criterion and heuristic guidelines promoted in extant work. We illustrate the superiority of the ellipsoidal method through extensive numerical experiments.
Submitted for publication, 2016.
A wide range of problems can be modeled as Mixed Integer Linear Programming (MILP) problems using standard formulation techniques. However, in some cases the resulting MILP can be either too weak or to large to be effectively solved by state of the art solvers. In this survey we review advanced MILP formulation techniques that result in stronger and/or smaller formulations for a wide class of problems.
SIAM Review 57, 2015. pp. 3-57.
[PDF] [DOI:10.1137/130915303][BibTeX]
Daniel Dadush, Santanu S. Dey and Juan Pablo Vielma
In this paper, we show that the Chvatal-Gomory closure of any compact convex set is a rational polytope. This resolves an open question of Schrijver 1980 for irrational polytopes, and generalizes the same result for the case of rational polytopes (Schrijver 1980), rational ellipsoids (Dey and Vielma 2010) and strictly convex bodies (Dadush, Dey and Vielma 2010).
An extended abstract of this work can be found here.
In 2011 Daniel Dadush received the INFORMS Optimization Society Student Paper Prize for this paper.
This paper was a finalist for the 2011 INFORMS Junior Faculty Interest Group Paper Competition.
Mathematical Programming 145, 2014. pp. 327-348.
[PDF] [DOI:10.1007/s10107-013-0649-9][BibTeX]
Rodolfo Carvajal, Miguel Constantino, Marcos Goycoolea, Juan Pablo Vielma and Andres Weintraub
Connectivity requirements are a common component of forest planning models, with important examples arising in wildlife habitat protection. In harvest scheduling models, one way of addressing preservation concerns consists in requiring that large contiguous patches of mature forest are maintained. In the context of nature reserve design, it is common practice to select connected regions of forest in such a way as to maximize the number of species and habitats protected. While a number of integer programming formulations have been proposed for these forest planning problems, most are impractical in that they fail to solve reasonably sized scheduling instances. We present a new integer programming methodology and test an implementation of it on five medium-sized forest instances publicly available in the FMOS repository. Our approach allows us to obtain near-optimal solutions for multiple time-period instances in less than four hours.
Operations Research 61, 2013. pp. 824-836.
[PDF] [DOI:10.1287/opre.2013.1183][BibTeX]
Diego Morán, Santanu S. Dey and Juan Pablo Vielma
Mixed-integer conic programming is a generalization of mixed-integer linear programming. In this paper, we present an extension of the duality theory for mixed-integer linear programming to the case of mixed-integer conic programming. In particular, we construct a subadditive dual for mixed-integer conic programming problems. Under a simple condition on the primal problem, we are able to prove strong duality.
In 2012 Diego Morán received the INFORMS Optimization Society Student Paper Prize for this paper.
SIAM Journal on Optimization 22, 2012. pp. 1136-1150.
[PDF] [DOI:10.1137/110840868][BibTeX]
Sajad Modaresi, Denis Saure and Juan Pablo Vielma
We study a family of sequential decision problems under model uncertainty in which, at each period, the decision maker faces a different instance of a combinatorial optimization problem. Instances differ in their objective coefficient vectors, which are unobserved prior to implementation. These vectors however are known to be random draws from a common and initially unknown distribution function. By implementing different solutions, the decision maker extracts information about the objective function, but at the same time experiences the cost associated with said solutions. We show that balancing the implied exploration vs exploitation trade-off requires addressing critical challenges not present in previous studies: in addition to determining exploration frequencies, the decision maker faces the issue of what to explore and how to do so. Our work provides clear answers to both questions. In particular, we show that efficient data collection might be achieved by solving a new class of combinatorial problems, which we refer to as Optimality Cover Problem (OCP). We establish a fundamental limit on the performance of any admissible policy, which relates to the solution to OCP. Using the insight derived from such a bound, we develop a family of policies and establish theoretical guarantees for their performances, which we contrast against the fundamental bound. These policies admit asynchronous versions, ensuring implementability.
This paper won the second prize in the 2013 INFORMS Junior Faculty Interest Group Paper Competition.
Submitted for publication, 2012.
Daniel Dadush, Santanu S. Dey and Juan Pablo Vielma
In this paper, we prove that the Chvátal-Gomory closure of a set obtained as an intersection of a strictly convex body and a rational polyhedron is a polyhedron. Thus, we generalize a result of Schrijver which shows that the Chvátal-Gomory closure of a rational polyhedron is a polyhedron.
This paper was a finalist for the 2010 INFORMS Junior Faculty Interest Group Paper Competition.
Mathematics of Operations Research 36, 2011. pp. 227-239.
[PDF] [DOI:10.1287/moor.1110.0488][BibTeX]
Juan Pablo Vielma and George L. Nemhauser
Many combinatorial constraints over continuous variables such as SOS1 and SOS2 constraints can be interpreted as disjunctive constraints that restrict the variables to lie in the union of a finite number of specially structured polyhedra. Known mixed integer binary formulations for these constraints have a number of binary variables and extra constraints linear in the number of polyhedra. We give sufficient conditions for constructing formulations for these constraints with a number of binary variables and extra constraints logarithmic in the number of polyhedra. Using these conditions we introduce mixed integer binary formulations for SOS1 and SOS2 constraints that have a number of binary variables and extra constraints logarithmic in the number of continuous variables. We also introduce the first mixed integer binary formulations for piecewise linear functions of one and two variables that use a number of binary variables and extra constraints logarithmic in the number of linear pieces of the functions. We prove that the new formulations for piecewise linear functions have favorable tightness properties and present computational results showing that they can significantly outperform other mixed integer binary formulations.
An extended abstract of this work can be found here.
Mathematical Programming 128, 2011. pp. 49-72.
[PDF] [DOI:10.1007/s10107-009-0295-4][BibTeX]
Daniel Dadush, Santanu S. Dey and Juan Pablo Vielma
In this paper, we show that the Chvatal-Gomory closure of any compact convex set is a rational polytope. This resolves an open question of Schrijver 1980 for irrational polytopes, and generalizes the same result for the case of rational polytopes (Schrijver 1980), rational ellipsoids (Dey and Vielma 2010) and strictly convex bodies (Dadush, Dey and Vielma 2010).
In O. Günlük and G. J. Woeginger, editors, Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization (IPCO 2011), Lecture Notes in Computer Science 6655, 2011. pp. 130-142.
Juan Pablo Vielma, Shabbir Ahmed and George L. Nemhauser
We study the modeling of non-convex piecewise linear functions as Mixed Integer Programming (MIP) problems. We review several new and existing MIP formulations for continuous piecewise linear functions with special attention paid to multivariate non-separable functions. We compare these formulations with respect to their theoretical properties and their relative computational performance. In addition, we study the extension of these formulations to lower semicontinuous piecewise linear functions.
Operations Research 58, 2010. pp. 303-315.
[PDF] [DOI:10.1287/opre.1090.0721][BibTeX]
Santanu S. Dey and Juan Pablo Vielma
It is well-know that the Chvátal-Gomory (CG) closure of a rational polyhedron is a rational polyhedron. In this paper, we show that the CG closure of an bounded full-dimensional ellipsoid, described by rational data, is a rational polytope. To the best of our knowledge, this is the first extension of the polyhedrality of the CG closure to a non-polyhedral set. A key feature of the proof is to verify that all non-integral points on the boundary of ellipsoids can be separated by some CG cut. Given a point u on the boundary of an ellipsoid that cannot be trivially separated using the CG cut parallel to its supporting hyperplane, the proof constructs a sequences of CG cuts that eventually separate u. The polyhedrality of the CG closure is established using this separation result and a compactness argument. The proof also establishes some sufficient conditions for the polyhedrality result for general compact convex sets.
In F. Eisenbrand and F. B. Shepherd, editors, Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization (IPCO 2010), Lecture Notes in Computer Science 6080, 2010. pp. 327-340.
Juan Pablo Vielma, Shabbir Ahmed and George L. Nemhauser
This paper develops a linear programming based branch-and-bound algorithm for mixed integer conic quadratic programs. The algorithm is based on a higher dimensional or lifted polyhedral relaxation of conic quadratic constraints introduced by Ben-Tal and Nemirovski. The algorithm is different from other linear programming based branch-and-bound algorithms for mixed integer nonlinear programs in that, it is not based on cuts from gradient inequalities and it sometimes branches on integer feasible solutions. The algorithm is tested on a series of portfolio optimization problems. It is shown that it significantly outperforms commercial and open source solvers based on both linear and nonlinear relaxations.
In 2007 I received the INFORMS Optimization Society Student Paper Prize for this paper.
INFORMS Journal on Computing 20, 2008. pp. 438-450.
[PDF] [DOI:10.1016/10.1287/ijoc.1070.0256][BibTeX]
Juan Pablo Vielma and George L. Nemhauser
Many combinatorial constraints over continuous variables such as SOS1 and SOS2 constraints can be interpreted as disjunctive constraints that restrict the variables to lie in the union of m specially structured polyhedra. Known mixed integer binary formulations for these constraints have a number of binary variables and extra constraints that is linear in m. We give sufficient conditions for constructing formulations for these constraints with a number of binary variables and extra constraints that is logarithmic in m. Using these conditions we introduce the first mixed integer binary formulations for SOS1 and SOS2 constraints that use a number of binary variables and extra constraints that is logarithmic in the number of continuous variables. We also introduce the first mixed integer binary formulations for piecewise linear functions of one and two variables that use a number of binary variables and extra constraints that is logarithmic in the number of linear pieces of the functions. We prove that the new formulations for piecewise linear functions have favorable tightness properties and present computational results showing that they can significantly outperform other mixed integer binary formulations.
The full version of this work can be found here.
In A. Lodi, A. Panconesi and G. Rinaldi, editors, Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO 2008), Lecture Notes in Computer Science 5035, 2008. pp. 199-213.