Publications

Selected |All by Type | All by Topic

Published

  1. Embedding Formulations and Complexity for Unions of Polyhedra. J. P. Vielma. To appear in Management Science, 2017.
    • 2015 INFORMS JFIG Paper Competition, First Prize.
    • 2017 INFORMS Computing Society (ICS) Prize.
  2. Extended Formulations in Mixed Integer Conic Quadratic Programming. J. P. Vielma, I. Dunning, J. Huchette and M. Lubin. Mathematical Programming Computation 9, 2017. pp. 369-418.
  3. Convex hull of two quadratic or a conic quadratic and a quadratic inequality. S. Modaresi and J. P. Vielma. Mathematical Programming 164, 2017. pp. 383-409.
  4. Polyhedral approximation in mixed-integer convex optimization. M. Lubin, E. Yamangil, R. Bent and J. P. Vielma. To appear in Mathematical Programming, 2017.
  5. Mixed-integer convex representability. M. Lubin, I. Zadik and J. P. Vielma. 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.
  6. Intersection cuts for nonlinear integer programming: convexification techniques for structured sets. S. Modaresi, M. R. Kılınç and J. P. Vielma. Mathematical Programming 155, 2016. pp. 575-611.
  7. Extended Formulations in Mixed-Integer Convex Programming. M. Lubin, E. Yamangil, R. Bent and J. P. Vielma. 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.
  8. Mixed integer linear programming formulation techniques. J. P. Vielma. SIAM Review 57, 2015. pp. 3-57.
  9. On the Chvátal-Gomory closure of a compact convex set. D. Dadush, S. S. Dey and J. P. Vielma. Mathematical Programming 145, 2014. pp. 327-348.
    • 2011 INFORMS JFIG Paper Competition, Finalist.
  10. Imposing connectivity constraints in forest planning models. R. Carvajal, M. Constantino, M. Goycoolea, J. P. Vielma and A. Weintraub. Operations Research 61, 2013. pp. 824-836.
    • 2015 Best Publication Award in Natural Resources, INFORMS Section on Energy, Natural Resources, and the Environment.
  11. Strong dual for conic mixed-integer programs. D. Morán, S. S. Dey and J. P. Vielma. SIAM Journal on Optimization 22, 2012. pp. 1136-1150.
  12. The Chvátal-Gomory closure of a strictly convex body. D. Dadush, S. S. Dey and J. P. Vielma. Mathematics of Operations Research 36, 2011. pp. 227-239.
    • 2010 INFORMS JFIG Paper Competition, Finalist.
  13. Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. J. P. Vielma and G. Nemhauser. Mathematical Programming 128, 2011. pp. 49-72.
    • 2017 INFORMS Computing Society (ICS) Prize.
  14. On the Chvátal-Gomory closure of a compact convex set. D. Dadush, S. S. Dey and J. P. Vielma. 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.
  15. Mixed-integer models for nonseparable piecewise linear optimization: unifying framework and extensions. J. P. Vielma, S. Ahmed and G. Nemhauser. Operations Research 58, 2010. pp. 303-315.
    • 2017 INFORMS Computing Society (ICS) Prize.
  16. The Chvátal-Gomory closure of an ellipsoid is a polyhedron. S. S. Dey and J. P. Vielma. 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.
  17. A lifted linear programming branch-and-bound algorithm for mixed integer conic quadratic programs. J. P. Vielma, S. Ahmed and G. Nemhauser. INFORMS Journal on Computing 20, 2008. pp. 438-450.
    • 2007 INFORMS Optimization Society Student Paper Prize.
  18. Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. J. P. Vielma and G. Nemhauser. 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.

Submitted

  1. Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools. J. Huchette and J. P. Vielma. Submitted for publication, 2017.
  2. Regularity in mixed-integer convex representability. M. Lubin, I. Zadik and J. P. Vielma. Submitted for publication, 2017.
  3. Small and strong formulations for unions of convex sets from the Cayley Embedding. J. P. Vielma. Submitted for publication, 2017.
  4. A mixed-integer branching approach for very small formulations of disjunctive constraints. J. Huchette and J. P. Vielma. Submitted for publication, 2017.
  5. A combinatorial approach for small and strong formulations of disjunctive constraints. J. Huchette and J. P. Vielma. Submitted for publication, 2016.
  6. Ellipsoidal methods for adaptive choice-based conjoint analysis. D. Saure and J. P. Vielma. Submitted for publication, 2016.
  7. Learning in combinatorial optimization: what and how to explore. S. Modaresi, D. Saure and J. P. Vielma. Submitted for publication, 2012.
    • 2013 INFORMS JFIG Paper Competition, Second Prize.



Publication Details



Embedding Formulations and Complexity for Unions of Polyhedra

Juan Pablo Vielma

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]



Extended Formulations in Mixed Integer Conic Quadratic Programming

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]



Convex hull of two quadratic or a conic quadratic and a quadratic inequality

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]



Polyhedral approximation in mixed-integer convex optimization

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]



Mixed-integer convex representability

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.

[PDF][BibTeX]



Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools

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.

[PDF]



Regularity in mixed-integer convex representability

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.

[PDF]



Small and strong formulations for unions of convex sets from the Cayley Embedding

Juan Pablo Vielma

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.

[PDF]



A mixed-integer branching approach for very small formulations of disjunctive constraints

Joey Huchette and Juan Pablo Vielma

We study the existence and construction of very small formulations for disjunctive constraints in optimization problems: that is, formulations that use very few integer variables and extra constraints. To accomplish this, we present a novel mixed-integer branching formulation framework, which preserves many of the favorable algorithmic properties of a traditional mixed-integer programming formulation, including amenability to the branch-and-bound algorithm and the generation of cutting planes. We show that any disjunctive constraint can be formulated with only two integer variables in this framework. Additionally, we give an explicit geometric construction for ideal formulations for the broad class of combinatorial disjunctive constraints, which should be of independent interest. We use this result to construct ideal mixed-integer branching formulations for any combinatorial disjunctive constraint with two control variables and only a linear number of facets. Finally, we give a ideal mixed-integer branching formulation for the SOS2 constraint with only two integer variables and four general inequality constraints.

Submitted for publication, 2017.

[PDF]



Intersection cuts for nonlinear integer programming: convexification techniques for structured sets

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]



Extended Formulations in Mixed-Integer Convex Programming

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.

[PDF][BibTeX]



A combinatorial approach for small and strong formulations of disjunctive constraints

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.

[PDF]



Ellipsoidal methods for adaptive choice-based conjoint analysis

Denis Saure and Juan Pablo Vielma

Questionnaires for adaptive choice-based conjoint analysis aim at minimizing some measure of the uncer- tainty associated with 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 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 uncertainty-region updates and effective optimization-based heuristics for adaptive question selection. However, its performance deteriorates with high 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 ellipsoidal uncertainty sets, one can include respondent error and develop a purely geometric approach that is as intuitive as the polyhedral approach, but nearly matches what a Bayesian approach would do. This ellipsoidal approach extends the effectiveness of the polyhedral approach to the high response error setting and provides a geometric interpretation of Bayesian approaches. In addition, it allows designing practical, near-optimal question selection methods. These methods are based on a precise relation between the D-efficiency criterion and heuristic guidelines promoted in extant work. We show the superiority of the ellipsoidal method through exhaustive numerical experiments.

Submitted for publication, 2016.

[PDF]



Mixed integer linear programming formulation techniques

Juan Pablo Vielma

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]



On the Chvátal-Gomory closure of a compact convex set

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]



Imposing connectivity constraints in forest planning models

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]



Strong dual for conic mixed-integer programs

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]



Learning in combinatorial optimization: what and how to explore

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.

[PDF]



The Chvátal-Gomory closure of a strictly convex body

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]



Modeling disjunctive constraints with a logarithmic number of binary variables and constraints

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]



On the Chvátal-Gomory closure of a compact convex set

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.

[PDF][BibTeX]



Mixed-integer models for nonseparable piecewise linear optimization: unifying framework and extensions

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]



The Chvátal-Gomory closure of an ellipsoid is a polyhedron

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.

[PDF][BibTeX]



A lifted linear programming branch-and-bound algorithm for mixed integer conic quadratic programs

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]



Modeling disjunctive constraints with a logarithmic number of binary variables and constraints

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.

[PDF] [DOI:10.1016/10.1007/978-3-540-68891-4_14][BibTeX]