## Publications

Selected |All by Type | All by Topic

### Published

1. Ellipsoidal methods for adaptive choice-based conjoint analysis. D. Saure and J. P. Vielma. To appear in Operations Research, 2018.
2. A combinatorial approach for small and strong formulations of disjunctive constraints. J. Huchette and J. P. Vielma. To appear in Mathematics of Operations Research, 2018.
3. Small and strong formulations for unions of convex sets from the Cayley Embedding. J. P. Vielma. To appear in Mathematical Programming, 2018.
4. 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.
5. 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.
• Cone disaggregation technique in this paper has been adopted by CPLEX v12.6.2, Gurobi v6.5, SCIP v4.0 and Xpress v8.0.
6. 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.
7. Polyhedral approximation in mixed-integer convex optimization. M. Lubin, E. Yamangil, R. Bent and J. P. Vielma. To appear in Mathematical Programming, 2017.
8. 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.
9. 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.
10. 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.
11. Mixed integer linear programming formulation techniques. J. P. Vielma. SIAM Review 57, 2015. pp. 3-57.
12. 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.
13. 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.
14. 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.
15. 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.
16. 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.
17. 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.
18. 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.
19. 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.
20. 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.
21. 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. Outer Approximation With Conic Certificates For Mixed-Integer Convex Problems. C. Coey, M. Lubin and J. P. Vielma. Submitted for publication, 2018.
2. Building Representative Matched Samples with Multi-valued Treatments in Large Observational Studies: Analysis of the Impact of an Earthquake on Educational Attainment. M. Bennett, J. P. Vielma and J. R. Zubizarreta. Submitted for publication, 2018.
3. Dynamic Automatic Differentiation of GPU Broadcast Kernels. J. Revels, T. Besard, V. Churavy, B. De Sutter and J. P. Vielma. Submitted for publication, 2018.
4. Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools. J. Huchette and J. P. Vielma. Submitted for publication, 2017.
5. Regularity in mixed-integer convex representability. M. Lubin, I. Zadik and J. P. Vielma. Submitted for publication, 2017.
6. Picking winners in daily fantasy sports using integer programming. D. S. Hunter , J. P. Vielma and T. Zaman. Technical Report, 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

### Ellipsoidal methods for adaptive choice-based conjoint analysis

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.

To appear in Operations Research, 2018.

[PDF]

### A combinatorial approach for small and strong formulations of disjunctive constraints

We present a framework for constructing strong mixed-integer programming formulations for logical 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.

To appear in Mathematics of Operations Research, 2018.

[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 modeling convex disjunctive constraints (e.g. unions of convex sets), adding auxiliary continuous variables can sometimes help resolve this trade-off. However, standard formulations that use such auxiliary continuous variables can have a worse-than-expected computational effectiveness, which is often attributed precisely to these auxiliary continuous variables. 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.

To appear in Mathematical Programming, 2018.

### Outer Approximation With Conic Certificates For Mixed-Integer Convex Problems

A mixed-integer convex (MI-convex) optimization problem is one that becomes convex when all integrality constraints are relaxed. We present a branch-and-bound LP outer approximation algorithm for an MI-convex problem transformed to MI-conic form. The polyhedral relaxations are refined with K* cuts} derived from conic certificates for continuous primal-dual conic subproblems. Under the assumption that all subproblems are well-posed, the algorithm detects infeasibility or unboundedness or returns an optimal solution in finite time. Using properties of the conic certificates, we show that the K* cuts imply certain practically-relevant guarantees about the quality of the polyhedral relaxations, and demonstrate how to maintain helpful guarantees when the LP solver uses a positive feasibility tolerance. We discuss how to disaggregate K* cuts in order to tighten the polyhedral relaxations and thereby improve the speed of convergence, and propose fast heuristic methods of obtaining useful K* cuts. Our new open source MI-conic solver Pajarito uses an external mixed-integer linear (MILP) solver to manage the search tree and an external continuous conic solver for subproblems. Benchmarking on a library of mixed-integer second-order cone (MISOCP) problems, we find that Pajarito greatly outperforms Bonmin (the leading open source alternative) and is competitive with CPLEX's specialized MISOCP algorithm. We demonstrate the robustness of Pajarito by solving diverse MI-conic problems involving mixtures of positive semidefinite, second-order, and exponential cones, and provide evidence for the practical value of our analyses and enhancements of K* cuts.

Submitted for publication, 2018.

[PDF]

### Building Representative Matched Samples with Multi-valued Treatments in Large Observational Studies: Analysis of the Impact of an Earthquake on Educational Attainment

What is the impact of an earthquake on the educational attainment of high school students? In this paper, we address this question using a unique data set and new matching methods. In particular, we use an administrative census of the same students measured before and after the 2010 Chilean earthquake. We propose and analyze new matching methods that overcome three challenges of existing approaches. These challenges relate to multi-valued treatments, external validity, and large data sets. Applying the idea of template matching of Silber et al. (2014), and leveraging recent developments in optimization, these new methods allow us: (i) to handle multi-valued treatments without estimation of the generalized propensity score; (ii) to build self-weighted matched samples that are representative of a target population by design; and (iii) to work with much larger data sets than other similar methods. For this, we use a linear-sized mixed integer programming formulation for matching with distributional covariate balance. We formally show that this formulation is more effective than alternative quadratic-sized formulations, as its reduction in size does not affect its strength from the standpoint of its linear programming relaxation. We also show that this linear-sized formulation can be used for matching with distributional covariate balance in polynomial time under certain structural assumptions on the covariates and that it can handle larger data sets in practice even when the assumptions are not satisfied. In fact, with this formulation, we can handle data sets with hundreds of thousands of observations in a couple of minutes. We implement this formulation in the package designmatch for R. The results from our case study are striking: while increasing levels of exposure to the earthquake have a negative impact on school attendance, there is no effect on university admission test scores.

Submitted for publication, 2018.

[PDF]

### Dynamic Automatic Differentiation of GPU Broadcast Kernels

We show how forward-mode automatic differentiation (AD) can be employed within larger reverse-mode computations to dynamically differentiate broadcast operations in a GPU-friendly manner. Our technique fully exploits the broadcast Jacobian's inherent sparsity structure, and unlike a pure reverse-mode approach, this mixed-mode'' approach does not require a backwards pass over the broadcasted operation's subgraph, obviating the need for several reverse-mode-specific programmability restrictions on user-authored broadcast operations. Most notably, this approach allows broadcast fusion in primal code despite the presence of data-dependent control flow. We discuss an experiment in which a Julia implementation of our technique outperformed pure reverse-mode TensorFlow and Julia implementations for differentiating through broadcast operations within an HM-LSTM cell update calculation.

Submitted for publication, 2018.

[PDF]

### 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.
2015 INFORMS JFIG Paper Competition, First Prize
2017 INFORMS Computing Society (ICS) Prize

To appear in Management Science, 2017.

### Extended Formulations in Mixed Integer Conic Quadratic Programming

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.
Cone disaggregation technique in this paper has been adopted by CPLEX v12.6.2, Gurobi v6.5, SCIP v4.0 and Xpress v8.0

Mathematical Programming Computation 9, 2017. pp. 369-418.

Mathematical Programming 164, 2017. pp. 383-409.

### Polyhedral approximation in mixed-integer convex optimization

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.

### 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.

### Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools

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]

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

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.

### Extended Formulations in Mixed-Integer Convex Programming

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.

### Picking winners in daily fantasy sports using integer programming

We consider the problem of selecting a portfolio of entries of fixed cardinality for a winner take all contest such that the probability of at least one entry winning is maximized. This framework is very general and can be used to model a variety of problems, such as movie studios selecting movies to produce, drug companies choosing drugs to develop, or venture capital firms picking start-up companies in which to invest. We model this as a combinatorial optimization problem with a submodular objective function, which is the probability of winning. We then show that the objective function can be approximated using only pairwise marginal probabilities of the entries winning when there is a certain structure on their joint distribution. We consider a model where the entries are jointly Gaussian random variables and present a closed form approximation to the objective function. We then consider a model where the entries are given by sums of constrained resources and present a greedy integer programming formulation to construct the entries. Our formulation uses three principles to construct entries: maximize the expected score of an entry, lower bound its variance, and upper bound its correlation with previously constructed entries. To demonstrate the effectiveness of our greedy integer programming formulation, we apply it to daily fantasy sports contests that have top heavy payoff structures (i.e. most of the winnings go to the top ranked entries). We find that the entries produced by our approach perform well in practice and are even able to come in first place in contests with thousands of entries. Our approach can easily be extended to other problems with a winner take all type of payoff structure.

, 2016.

### 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.

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

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.
2011 INFORMS JFIG Paper Competition, Finalist

Mathematical Programming 145, 2014. pp. 327-348.

### 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.
2015 Best Publication Award in Natural Resources, INFORMS Section on Energy, Natural Resources, and the Environment

Operations Research 61, 2013. pp. 824-836.

### Strong dual for conic mixed-integer programs

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.

### Learning in combinatorial optimization: what and how to explore

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.
2013 INFORMS JFIG Paper Competition, Second Prize

Submitted for publication, 2012.

[PDF]

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

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.
2010 INFORMS JFIG Paper Competition, Finalist

Mathematics of Operations Research 36, 2011. pp. 227-239.

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

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.
2017 INFORMS Computing Society (ICS) Prize

Mathematical Programming 128, 2011. pp. 49-72.

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

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.

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

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.
2017 INFORMS Computing Society (ICS) Prize

Operations Research 58, 2010. pp. 303-315.

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

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.

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

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.
2007 INFORMS Optimization Society Student Paper Prize

INFORMS Journal on Computing 20, 2008. pp. 438-450.

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

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.