Skip to: Content | Navigation | Footer
Ilias Zadik, Miles Lubin and Juan Pablo Vielma
Mixed-integer convex representable (MICP-R) sets are those sets that can be represented exactly through a mixed-integer convex programming formulation. Following up on recent work by Lubin et al. (2017, 2020) we investigate structural geometric properties of MICP-R sets, which strongly differentiate them from the class of mixed-integer linear representable sets (MILP-R). First, we provide an example of an MICP-R set which is the countably infinite union of convex sets with countably infinitely many different recession cones. This is in sharp contrast with MILP-R sets which are at most infinite unions of polyhedra that share the same recession cone. Second, we provide an example of an MICP-R set which is the countably infinite union of polytopes all of which have different shapes (no pair is combinatorially equivalent, which implies they are not affine transformations of each other). Again, this is in sharp contrast with MILP-R sets which are at most infinite unions of polyhedra that are all translations of a finite subset of themselves. Interestingly, we show that a countably infinite union of convex sets sharing the same volume can be MICP-R only if the sets are all translations of a finite subset of themselves (i.e. the natural conceptual analogue to the MILP-R case).
Mathematical Programming 204, 2024. pp. 739-752.
[PDF] [DOI:10.1007/s10107-023-01946-4][BibTeX]
Lea Kapelevich, Erling D. Andersen and Juan Pablo Vielma
The recent interior point algorithm by Dahl and Andersen, 2021 for nonsymmetric cones requires derivative information from the conjugate of the barrier function of the cones in the problem. Besides a few special cases, there is no indication of when this information is efficient to evaluate. We show how to compute the gradient of the conjugate barrier function for seven useful nonsymmetric cones. In some cases this is helpful for deriving closed-form expressions for the inverse Hessian operator for the primal barrier.
Journal of Optimization Theory and Applications 202, 2024. pp. 271-295.
[PDF] [DOI:10.1007/s10957-022-02076-1][BibTeX]
Miles Lubin, Oscar Dowson, Joaquim Dias Garcia, Joey Huchette, Benoît Legat and Juan Pablo Vielma
JuMP is an algebraic modeling language embedded in the Julia programming language. JuMP allows users to model optimization problems of a variety of kinds, including linear programming, integer programming, conic optimization, semidefinite programming, and nonlinear programming, and handles the low-level details of communicating with solvers. After nearly 10 years in development, JuMP 1.0 was released in March, 2022. In this short communication, we highlight the improvements to JuMP from recent releases up to and including 1.0.
Mathematical Programming Computation 15, 2023. pp. 581-589.
[PDF] [DOI:10.1007/s12532-023-00239-3][BibTeX]
Chris Coey, Lea Kapelevich and Juan Pablo Vielma
In recent work, we provide computational arguments for expanding the class of proper cones recognized by conic optimization solvers, to permit simpler, smaller, more natural conic formulations. We define an exotic cone as a proper cone for which we can implement a small set of tractable (i.e. fast, numerically stable, analytic) oracles for a logarithmically homogeneous self-concordant barrier for the cone or for its dual cone. Our extensible, open source conic interior point solver, Hypatia, allows modeling and solving any conic optimization problem over a Cartesian product of exotic cones. In this paper, we introduce Hypatia's interior point algorithm. Our algorithm is based on that of Skajaa and Ye [2015], which we generalize by handling exotic cones without tractable primal oracles. With the goal of improving iteration count and solve time in practice, we propose a sequence of four enhancements to the interior point stepping procedure of Skajaa and Ye [2015]: (1) loosening the central path proximity condition, (2) adjusting the directions using a third order directional derivative barrier oracle, (3) performing a backtracking search on a curve, and (4) combining the prediction and centering directions. We implement 23 useful exotic cones in Hypatia. We summarize the complexity of computing oracles for these cones, showing that our new third order oracle is not a bottleneck, and we derive efficient and numerically stable oracle implementations for several cones. We generate a diverse benchmark set of 379 conic problems from 37 different applied examples. Our computational testing shows that each stepping enhancement improves Hypatia's iteration count and solve time. Altogether, the enhancements reduce the shifted geometric means of iteration count and solve time by over 80% and 70% respectively.
Mathematical Programming Computation 15, 2023. pp. 53-101.
[PDF] [DOI:10.1007/s12532-022-00226-0][BibTeX]
Lea Kapelevich, Chris Coey and Juan Pablo Vielma
In polynomial optimization problems, nonnegativity constraints are typically handled using the sum of squares condition. This can be efficiently enforced using semidefinite programming formulations, or as more recently proposed by Papp and Yildiz 2019, using the sum of squares cone directly in a nonsymmetric interior point algorithm. Beyond nonnegativity, more complicated polynomial constraints (in particular, generalizations of the positive semidefinite, second order and l1-norm cones) can also be modeled through structured sum of squares programs. We take a different approach and propose using more specialized polynomial cones instead. This can result in lower dimensional formulations, more efficient oracles for interior point methods, or self-concordant barriers with lower parameters. In most cases, these algorithmic advantages also translate to faster solving times in practice.
Mathematical Programming 199, 2023. pp. 1417-1429.
[PDF] [DOI:10.1007/s10107-022-01831-6][BibTeX]
Andrea Lodi, Mathieu Tanneau and Juan Pablo Vielma
This paper studies disjunctive cutting planes in Mixed-Integer Conic Programming. Building on conic duality, we formulate a cut-generating conic program for separating disjunctive cuts, and investigate the impact of the normalization condition on its resolution. In particular, we show that a careful selection of normalization guarantees its solvability and conic strong duality. Then, we highlight the shortcomings of separating conic-infeasible points in an outer-approximation context, and propose conic extensions to the classical lifting and monoidal strengthening procedures. Finally, we assess the computational behavior of various normalization conditions in terms of gap closed, computing time and cut sparsity. In the process, we show that our approach is competitive with the internal lift-and-project cuts of a state-of-the-art solver.
Mathematical Programming 199, 2023. pp. 671-719.
[PDF] [DOI:10.1007/s10107-022-01844-1][BibTeX]
Chris Coey, Lea Kapelevich and Juan Pablo Vielma
Spectral functions on Euclidean Jordan algebras arise frequently in convex models. Despite the success of primal-dual conic interior point solvers, there has been little work on enabling direct support for spectral cones, i.e. proper nonsymmetric cones defined from epigraphs and perspectives of spectral functions. We propose simple logarithmically homogeneous barriers for spectral cones and we derive efficient, numerically stable procedures for evaluating barrier oracles such as inverse Hessian operators. For two useful classes of spectral cones - the root-determinant cones and the matrix monotone derivative cones - we show that the barriers are self-concordant, with nearly optimal parameters. We implement these cones and oracles in our open source solver Hypatia, and we write simple, natural formulations for four applied problems. Our computational benchmarks demonstrate that Hypatia often solves the natural formulations more efficiently than advanced solvers such as MOSEK 9 solve equivalent extended formulations written using only the cones these solvers support.
Mathematics of Operations Research 48, 2022. pp. 1906-1933.
[PDF] [DOI:10.1287/moor.2022.1324][BibTeX]
Chris Coey, Lea Kapelevich and Juan Pablo Vielma
Many convex optimization problems can be represented through conic extended formulations with auxiliary variables and constraints using only the small number of standard cones recognized by advanced conic solvers such as MOSEK 9. Such extended formulations are often significantly larger and more complex than equivalent conic natural formulations, which can use a much broader class of exotic cones. We define an exotic cone as a proper cone for which we can implement tractable logarithmically homogeneous self-concordant barrier oracles for either the cone or its dual cone. In this paper we introduce Hypatia, a highly-configurable open-source conic primal-dual interior point solver with a generic interface for exotic cones. Hypatia is written in Julia and accessible through JuMP, and currently implements around two dozen useful predefined cones (some with multiple variants). We define some of Hypatia's exotic cones, and for conic constraints over these cones, we analyze techniques for constructing equivalent representations using the standard cones. For optimization problems from a variety of applications, we introduce natural formulations using these exotic cones, and we show that the natural formulations are simpler and lower-dimensional than the equivalent extended formulations. Our computational experiments demonstrate the potential advantages, especially in terms of solve time and memory usage, of solving the natural formulations with Hypatia compared to solving the extended formulations with either Hypatia or MOSEK 9.
INFORMS Journal on Computing 34, 2022. pp. 2686-2699.
[PDF] [DOI:10.1287/ijoc.2022.1202][BibTeX]
Theodore P. Papalexopoulos, Christian Tjandraatmadja, Ross Anderson, Juan Pablo Vielma and David Belanger
Discrete black-box optimization problems are challenging for model-based optimization (MBO) algorithms, such as Bayesian optimization, due to the size of the search space and the need to satisfy combinatorial constraints. In particular, these methods require repeatedly solving a complex discrete global optimization problem in the inner loop, where popular heuristic inner-loop solvers introduce approximations and are difficult to adapt to combinatorial constraints. In response, we propose NN+MILP, a general discrete MBO framework using piecewise-linear neural networks as surrogate models and mixed-integer linear programming (MILP) to optimize the acquisition function. MILP provides optimality guarantees and a versatile declarative language for domain-specific constraints. We test our approach on a range of unconstrained and constrained problems, including DNA binding and the NAS-Bench-101 neural architecture search benchmark. NN+MILP surpasses or matches the performance of algorithms tailored to the domain at hand, with global optimization of the acquisition problem running in a few minutes using only standard software packages and hardware.
In K. Chaudhuri and S. Jegelka and L. Song and C. Szepesvaria and G. Niu and S. Sabato, editors, Proceedings of the 39th International Conference on Machine Learning (ICML 2022), Proceedings of Machine Learning Research 162, 2022. pp. 17295-17322.
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.
Operations Research 71, 2022. pp. 1835-1856.
[PDF] [DOI:10.1287/opre.2019.1973][BibTeX]
Miles Lubin, Juan Pablo Vielma and Ilias Zadik
Motivated by recent advances in solution methods for mixed-integer convex optimization (MICP), we study the fundamental and open question of which sets can be represented exactly as feasible regions of MICP problems. We establish several results in this direction, including the first complete characterization for the mixed-binary case and a simple necessary condition for the general case. We use the latter to derive the first non-representability results for various non-convex sets such as the set of rank-1 matrices and the set of prime numbers. Finally, in correspondence with the seminal work on mixed-integer linear representability by Jeroslow and Lowe, we study the representability question under rationality assumptions. Under these rationality assumptions, we establish that representable sets obey strong regularity properties such as periodicity, and we provide a complete characterization of representable subsets of the natural numbers and of representable compact sets. Interestingly, in the case of subsets of natural numbers, our results provide a clear separation between the mathematical modeling power of mixed-integer linear and mixed-integer convex optimization. In the case of compact sets, our results imply that using unbounded integer variables is necessary only for modeling unbounded sets.
Mathematics of Operations Research 47, 2021. pp. 720-749.
[PDF] [DOI:10.1287/moor.2021.1146][BibTeX]
Christian Tjandraatmadja, Ross Anderson, Joey Huchette, Will Ma, Krunal Patel and Juan Pablo Vielma
We improve the effectiveness of propagation- and linear-optimization-based neural network verification algorithms with a new tightened convex relaxation for ReLU neurons. Unlike previous single-neuron relaxations which focus only on the univariate input space of the ReLU, our method considers the multivariate input space of the affine pre-activation function preceding the ReLU. Using results from submodularity and convex geometry, we derive an explicit description of the tightest possible convex relaxation when this multivariate input is over a box domain. We show that our convex relaxation is significantly stronger than the commonly used univariate-input relaxation which has been proposed as a natural convex relaxation barrier for verification. While our description of the relaxation may require an exponential number of inequalities, we show that they can be separated in linear time and hence can be efficiently incorporated into optimization algorithms on an as-needed basis. Based on this novel relaxation, we design two polynomial-time algorithms for neural network verification: a linear-programming-based algorithm that leverages the full power of our relaxation, and a fast propagation algorithm that generalizes existing approaches. In both cases, we show that for a modest increase in computational effort, our strengthened relaxation enables us to verify a significantly larger number of instances compared to similar algorithms.
In H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin, editors, Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Advances in Neural Information Processing Systems 33, 2020. pp. 21675-21686.
Magdalena Bennett, Juan Pablo Vielma and José R. Zubizarreta
In this paper, we present a new way of matching in observational studies that overcomes three limitations of existing matching approaches. First, it directly balances covariates with multi-valued treatments without explicitly estimating the generalized propensity score. Second, it builds self-weighted matched samples that are representative of a target population by design. Third, it can handle large data sets, with hundreds of thousands of observations, in a couple of minutes. The key insights of this new approach to matching are balancing the treatment groups relative to a target population and positing a linear-sized mixed integer formulation of the matching problem. 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 formulation can be used for matching with distributional covariate balance in polynomial time under certain assumptions on the covariates and that it can handle large data sets in practice even when the assumptions are not satisfied. This algorithmic characterization is key to handling large data sets. We illustrate this new approach to matching in both a simulation study and an observational study of the impact of an earthquake on educational attainment. With this approach, the results after matching can be visualized with simple and transparent graphical displays: while increasing levels of exposure to the earthquake have a negative impact on school attendance, there is no effect on college admission test scores.
Journal of Computational and Graphical Statistics 29, 2020. pp. 744-757.
[PDF] [DOI:10.1080/10618600.2020.1753532][BibTeX]
Ross Anderson, Joey Huchette, Will Ma, Christian Tjandraatmadja and Juan Pablo Vielma
We present strong mixed-integer programming (MIP) formulations for high-dimensional piecewise linear functions that correspond to trained neural networks. These formulations can be used for a number of important tasks, such as verifying that an image classification network is robust to adversarial inputs, or solving decision problems where the objective function is a machine learning model. We present a generic framework, which may be of independent interest, that provides a way to construct sharp or ideal formulations for the maximum of d affine functions over arbitrary polyhedral input domains. We apply this result to derive MIP formulations for a number of the most popular nonlinear operations (e.g. ReLU and max pooling) that are strictly stronger than other approaches from the literature. We corroborate this computationally, showing that our formulations are able to offer substantial improvements in solve time on verification tasks for image classification networks.
Mathematical Programming 183, 2020. pp. 3-39.
[PDF] [DOI:10.1007/s10107-020-01474-5][BibTeX]
Chris Coey, Miles Lubin and Juan Pablo Vielma
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.
Mathematical Programming Computation 12, 2020. pp. 249-293.
[PDF] [DOI:10.1007/s12532-020-00178-3][BibTeX]
Sajad Modaresi, Denis Saure and Juan Pablo Vielma
We study dynamic decision-making under uncertainty when, at each period, a decision-maker implements a solution to a combinatorial optimization problem. The objective coefficient vectors of said problem, which are unobserved prior to implementation, vary from period to period. These vectors, however, are known to be random draws from an initially unknown distribution with known range. By implementing different solutions, the decision-maker extracts information about the underlying distribution, but at the same time experiences the cost associated with said solutions. We show that resolving the implied exploration versus exploitation trade-off efficiently is related to solving a Lower Bound Problem (LBP), which simultaneously answers the questions of what to explore and how to do so. We establish a fundamental limit on the asymptotic performance of any admissible policy that is proportional to the optimal objective value of the LBP problem. We show that such a lower bound might be asymptotically attained by policies that adaptively reconstruct and solve LBP at an exponentially decreasing frequency. Because LBP is likely intractable in practice, we propose policies that instead reconstruct and solve a proxy for LBP, which we call the Optimality Cover Problem (OCP). We provide strong evidence of the practical tractability of OCP which implies that the proposed policies can be implemented in real-time. We test the performance of the proposed policies through extensive numerical experiments and show that they significantly outperform relevant benchmarks in the long-term and are competitive in the short-term.
Operations Research 68, 2020. pp. 1285-1624.
[PDF] [DOI:10.1287/opre.2019.1926][BibTeX]
Joey Huchette and Juan Pablo Vielma
We give an explicit geometric way to build ideal mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of the normal directions of all hyperplanes spanned (in a r-dimensional linear space) by a set of directions determined by the extreme points shared among the alternatives. The resulting MIP formulation is ideal, and has exactly r integer variables and 2 x (# of spanning hyperplanes) general inequality constraints. We use this result to derive novel logarithmic-sized ideal MIP formulations for discontinuous piecewise linear functions and the annulus constraint arising in robotics and power systems problems.
Operations Research Letters 47, 2019. pp. 601-606.
[PDF] [DOI:10.1016/j.orl.2019.10.003][BibTeX]
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 question selection. 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.
Operations Research 67, 2019. pp. 295-597.
[PDF] [DOI:10.1287/opre.20181790][BibTeX]
Joey Huchette and Juan Pablo Vielma
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.
Mathematics of Operations Research 44, 2019. pp. 767-1144.
[PDF] [DOI:10.1287/moor.2018.0946][BibTeX]
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.
Mathematical Programming 177, 2019. pp. 21-53.
[PDF] [DOI:10.1007/s10107-018-1258-4][BibTeX]
Ross Anderson, Joey Huchette, Christian Tjandraatmadja and Juan Pablo Vielma
We present an ideal mixed-integer programming (MIP) formulation for a rectified linear unit (ReLU) appearing in a trained neural network. Our formulation requires a single binary variable and no additional continuous variables beyond the input and output variables of the ReLU. We contrast it with an ideal "extended" formulation with a linear number of additional continuous variables, derived through standard techniques. An apparent drawback of our formulation is that it requires an exponential number of inequality constraints, but we provide a routine to separate the inequalities in linear time. We also prove that these exponentially-many constraints are facet-defining under mild conditions. Finally, we present computational results showing that dynamically separating from the exponential inequalities 1) is much more computationally efficient and scalable than the extended formulation, 2) decreases the solve time of a state-of-the-art MIP solver by a factor of 7 on smaller instances, and 3) nearly matches the dual bounds of a state-of-the-art MIP solver on harder instances, after just a few rounds of separation and in orders of magnitude less time.
In A. Lodi and V. Nagarajan, editors, Proceedings of the 20th Conference on Integer Programming and Combinatorial Optimization (IPCO 2019), Lecture Notes in Computer Science 11480, 2019. pp. 27-42.
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.
Management Science 64, 2018. pp. 4721-4734.
[PDF] [DOI:10.1287/mnsc.2017.2856][BibTeX]
Joey Huchette, Santanu S. Dey and Juan Pablo Vielma
The floor layout problem (FLP) tasks a designer with positioning a collection of rectangular boxes on a fixed floor in such a way that minimizes total communication costs between the components. While several mixed integer programming (MIP) formulations for this problem have been developed, it remains extremely challenging from a computational perspective. This work takes a systematic approach to constructing MIP formulations and valid inequalities for the FLP that unifies and recovers all known formulations for it. In addition, the approach yields new formulations that can provide a significant computational advantage and can solve previously unsolved instances. While the construction approach focuses on the FLP, it also exemplifies generic formulation techniques that should prove useful for broader classes of problems.
INFOR: Information Systems and Operational Research 56, 2018. pp. 392-433.
[PDF] [DOI:10.1080/03155986.2017.1346916][BibTeX]
Joey Huchette, Santanu S. Dey and Juan Pablo Vielma
For many Mixed-Integer Programming (MIP) problems, high-quality dual bounds can obtained either through advanced formulation techniques coupled with a state-of-the-art MIP solver, or through Semidefinite Programming (SDP) relaxation hierarchies. In this paper, we introduce an alternative bounding approach that exploits the "combinatorial implosion" effect by solving portions of the original problem and aggregating this information to obtain a global dual bound. We apply this technique to the one-dimensional and two-dimensional floor layout problems and compare it with the bounds generated by both state-of-the-art MIP solvers and by SDP relaxations. Specifically, we prove that the bounds obtained through the proposed technique are at least as good as those obtained through SDP relaxations, and present computational results that these bounds can be significantly stronger and easier to compute than these alternative strategies, particularly for very difficult problem instances.
INFOR: Information Systems and Operational Research 56, 2018. pp. 457-481.
[PDF] [DOI:10.1080/03155986.2017.1363592][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.
Mathematical Programming 172, 2018. pp. 139-168.
[PDF] [DOI:10.1007/s10107-017-1191-y][BibTeX]
Jarrett Revels, Tim Besard, Valentin Churavy, Bjorn De Sutter and Juan Pablo Vielma
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.
Proceedings of the Workshop on Systems for ML and Open Source Software at NeurIPS 2018 (NeurIPS MLSys 2018), 2018.
José R. Zubizarreta, Çınar Kılcıoğlu and Juan Pablo Vielma
, 2018.
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, 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
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.
, 2017.
Luis Rademacher, Alejandro Toriello and Juan Pablo Vielma
We consider the natural generalizations of packing and covering polyhedra in infinite dimensions, and study issues related to duality and integrality of extreme points for these sets. Using appropriate finite truncations we give conditions under which complementary slackness holds for primal/dual pairs of the infinite linear programming problems associated with infinite packing and covering polyhedra. We also give conditions under which the extreme points are integral. We illustrate an application of our results on an infinite-horizon lot-sizing problem.
Operations Research Letters 44, 2016. pp. 225-230.
[PDF] [DOI:10.1016/j.orl.2016.01.005][BibTeX]
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.
Carter Mundell, Juan Pablo Vielma and Tauhid Zaman
The rapid growth of the availability of wearable biosensors has created the opportunity for using biological signals to measure worker performance. An important question is how to use such signals to not just measure, but actually predict worker performance on a task under stressful and potentially high risk conditions. Here we show that the biological signal known as galvanic skin response (GSR) allows such a prediction. We conduct an experiment where subjects answer arithmetic questions under low and high stress conditions while having their GSR monitored using a wearable biosensor. Using only the GSR measured under low stress conditions, we are able to predict which subjects will perform well under high stress conditions, achieving an area under the curve (AUC) of 0.76. If we try to make similar predictions without using any biometric signals, the AUC barely exceeds 0.50. Our result suggests that performance in high stress conditions can be predicted using signals obtained from wearable biosensors in low stress conditions.
, 2016.
David Scott Hunter , Juan Pablo Vielma and Tauhid Zaman
We consider the problem of selecting a portfolio of entries of fixed cardinality for contests with top-heavy payoff structures, i.e. most of the winnings go to the top-ranked entries. This framework is general and can be used to model a variety of problems, such as movie studios selecting movies to produce, venture capital firms picking start-up companies to invest in, or individuals selecting lineups for daily fantasy sports contests, which is the example we focus on here. We model the portfolio selection task as a combinatorial optimization problem with a submodular objective function, which is given by the probability of at least one entry winning. We then show that this probability 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. Building on this, we then consider a scenario where the entries are given by sums of constrained resources and present an integer programming formulation to construct the entries. Our formulation uses principles based on our theoretical analysis to construct entries: we maximize the expected score of an entry subject to a lower bound on its variance and an upper bound on its correlation with previously constructed entries. To demonstrate the effectiveness of our integer programming approach, we apply it to daily fantasy sports contests that have top-heavy payoff structures. We find that our approach performs well in practice. Using our integer programming approach, we are able to rank in the top-ten multiple times in hockey and baseball contests with thousands of competing entries. Our approach can easily be extended to other problems with constrained resources and a top-heavy payoff structure.
Submitted for publication, 2016.
Miles Lubin, Daniel Bienstock and Juan Pablo Vielma
We examine the convexity and tractability of the two-sided linear chance constraint model under Gaussian uncertainty. We show that these constraints can be applied directly to model a larger class of nonlinear chance constraints as well as provide a reasonable approximation for a challenging class of quadratic chance constraints of direct interest for applications in power systems. With a view towards practical computations, we develop a second-order cone outer approximation of the two-sided chance constraint with provably small approximation error.
, 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]
Sina Modaresi, Mustafa R. Kılınç and Juan Pablo Vielma
In this paper we study split cuts and extended formulations for Mixed Integer Conic Quadratic Programming (MICQP) and their relation to the Conic Mixed Integer Rounding (CMIR) cuts. We show that the CMIR is a linear split cut for the polyhedral portion of an extended formulation of a quadratic set and that it can be weaker than the nonlinear split cut of the same quadratic set. However, we also show that by exploiting the power of their extended formulation, families of CMIRs can be significantly stronger than the associated family of nonlinear split cuts.
Operations Research Letters 43, 2015. pp. 10-15.
[PDF] [DOI:10.1016/j.orl.2014.10.006][BibTeX]
Nathalie E. Jamett, Luis A. Cisternas and Juan Pablo Vielma
The aim of this study is two-fold: first, to analyze the effect of stochastic uncertainty in the design of flotation circuits and second, to analyze different strategies for the solution of a two-stage stochastic problem applied to a copper flotation circuit. The paper begins by introducing a stochastic optimization problem whose aim is to find the best configuration of superstructure, equipment design and operational conditions, such as residence time and stream flows. Variability is considered in the copper price and ore grade. This variability is represented by scenarios with their respective probability of occurrence. The resulting optimization problem is a two-stage stochastic mixed integer nonlinear program (TS-MINLP), which can be extremely challenging to solve. For this reason, several solvers for this problem are compared and two stochastic programming methodologies are applied. The combination of these techniques allows the production of high quality solutions and an analysis of their sensitivity to epistemic uncertainty. The results show that the stochastic problem gives better designs because it allows operational parameters to adapt to the uncertainty of the parameters. The results also show that the flotation circuit structure can vary with the feed grade and copper price. The sensitivity analysis shows small to moderate variability with epistemically uncertain parameters.
Chemical Engineering Science 134, 2015. pp. 850-860.
[PDF] [DOI:10.1016/j.ces.2015.06.010][BibTeX]
Guido Lagos, Daniel Espinoza, Eduardo Moreno and Juan Pablo Vielma
In this paper we consider the restriction of coherent and distortion risk measures to the spaces of linear and affine linear random variables and the robust uncertainty sets associated to these risk measures. In this context we study two variants of the permutahull uncertainty set introduced by Bertsimas and Brown for finite probability spaces. The first variant considers the extension of the permutahull to non-atomic distributions and the second variant considers scalings of the permutahull. In particular, by studying expansions of the permutahull we are able to show that there are measures that are distortion risk measures over the space of linear random variables that cannot be extended to a distortion risk measures over all random variables. We also present preliminary computational results illustrating that using expansions of the permutahull could help mitigate estimation errors.
European Journal of Operational Research 241, 2015. pp. 771-782.
[PDF] [DOI:10.1016/j.ejor.2014.09.024][BibTeX]
Sina Modaresi, Juan Pablo Vielma and Tauhid Zaman
Today, having a strong social media presence is an important issue for large and small companies. A key social media challenge faced by these companies' marketing teams is how to maximize the impressions or views of the content they post in a social network. Optimizing the posting time of content to increase impressions is an approach not considered before because it was not clear how to systematically select the optimal posting time and what would be the potential gain in impressions. In this work we show how to select posting times to maximize impressions and the potential gains of this strategic timing. We use data from several Twitter users to build a model for how users view content in a social network. With this model we are able to provide a simple equation that gives the impression probability for a piece of content as a function of its posting time. We show that for several real social media users strategic timing can significantly increase impressions. Furthermore, this increase in impressions comes at no cost because choosing the time to post is free. In addition, all calculations use publicly available data, so this approach can be implemented very easily. Finally, we consider the situation where strategic timing becomes widely adopted and posting times are scheduled by an online application. This situation leads to potentially intractable optimization problems and a natural trade-off between aggregate performance and fairness objectives. However, we show that surprisingly, increasing fairness actually seems to improve aggregate performance in this setting. In addition, we show that solutions that are nearly optimal for both objectives can be easily constructed.
, 2015.
Sanjeeb Dash, Oktay Günlük and Juan Pablo Vielma
In this paper, we study whether cuts obtained from two simplex tableau rows at a time can strengthen the bounds obtained by GMI cuts based on single tableau rows. We also study whether cross and crooked cross cuts, which generalize split cuts, can be separated in an effective manner for practical MIPs and can yield a non-trivial improvement over the bounds obtained by split cuts. We give positive answers to both these questions for MIPLIB 3.0 problems. Cross cuts are a special case of the $t$-branch split cuts studied by Li and Richard (2008). Split cuts are 1-branch split cuts, and cross cuts are 2-branch split cuts. Crooked cross cuts were introduced by Dash, Dey and Gunluk (2010) and were shown to dominate cross cuts in Dash, Gunluk and Molinaro (2012).
INFORMS Journal on Computing 26, 2014. pp. 780-797.
[PDF] [DOI:10.1287/ijoc.2014.0598][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.
Mathematical Programming 145, 2014. pp. 327-348.
[PDF] [DOI:10.1007/s10107-013-0649-9][BibTeX]
Sercan Yıldız and Juan Pablo Vielma
The standard way to represent a choice between n alternatives in Mixed Integer Programming is through n binary variables that add up to one. Unfortunately, this approach commonly leads to unbalanced branch-and-bound trees and diminished solver performance. In this paper, we present an encoding formulation framework that encompasses and expands existing approaches to mitigate this behavior. Through this framework, we generalize the incremental formulation for piecewise linear functions to any finite union of polyhedra with identical recession cones.
Operations Research Letters 41, 2013. pp. 654-658.
[PDF] [DOI:10.1016/j.orl.2013.09.004][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]
Daniel Espinoza, Guido Lagos, Eduardo Moreno and Juan Pablo Vielma
During early phases of open-pit mining production planning many parameters are uncertain, and since the mining operation is performed only once, any evaluations based only on on average outcomes neglects the very real chance of obtaining an outcome that is below average. Taking into account also that operation costs are considerable and the mining horizon usually extends over several decades it is clear that open-pit production planning is a risky endeavor. In this work we take a risk-averse approach on tackling uncertainty in the ore-grades. We consider an extended Ultimate-Pit problem, where extraction and processing decisions have to be taken. We apply and compare the risk-hedging performance of two approaches from optimization under uncertainty: minimize Conditional Value-at-Risk (CVaR) and minimization of a combination of expected value and CVaR. Additionally, we compare two decision schemes: a static variant, where all decisions have to be taken �now�, and a two-stage or recourse variant, where we take extraction decisions now, then we see the real ore-grade, and just then processing decision is taken. Our working assumption is that we have available a large number of ore-grade scenarios. Computational results on one small size vein-type mine illustrate how minimizing average loss provides good on-average results at the cost of having high probability of obtaining undesired outcomes; and on the other hand our proposed approaches control the risk by providing solutions with a controllable probability of obtaining undesired outcomes. Results also show the great risk-hedging potential of using multi-stage decision schemes.
In J. F. Costa, J. Koppe and R. Peroni, editors, Proceedings of the 36th International Symposium on Application of Computers and Operations Research in The Mineral Industry (APCOM 2013), 2013. pp. 492-501.
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]
Juan Pablo Vielma, Shabbir Ahmed and George L. Nemhauser
We introduce two new formulations for probabilistic constraints based on extended disjunctive formulations. These formulations obtain significant strength by considering multiple rows of the probabilistic constraints together. The theoretical properties of the first formulation can be used to construct hierarchies of relaxations for probabilistic constraints, while the second formulation provides a computational advantage over other formulations. We illustrate the properties of the formulations with computational results.
Operations Research Letters 40, 2012. pp. 153-158.
[PDF] [DOI:10.1016/j.orl.2012.01.007][BibTeX]
Alejandro Toriello and Juan Pablo Vielma
We consider the problem of fitting a continuous piecewise linear function to a finite set of data points. We review convex continuous fitting models, and then introduce mixed-binary models that generalize the continuous ones by introducing variability in the regions defining the best-fit function's domain. We also study the additional constraints required to impose convexity on the best-fit function.
European Journal of Operational Research 219, 2012. pp. 86-95.
[PDF] [DOI:10.1016/j.ejor.2011.12.030][BibTeX]
Alexandre S. Freire, Eduardo Moreno and Juan Pablo Vielma
We introduce a new Integer Linear Programming (ILP) approach for solving Integer Programming (IP) problems with bilinear objectives and linear constraints. The approach relies on a series of ILP approximations of the bilinear IP. We compare this approach with standard linearization techniques on random instances and a set of real-world product bundling problems.
Operations Research Letters 40, 2012. pp. 74-77.
[PDF] [DOI:10.1016/j.orl.2011.12.004][BibTeX]
Nathalie E. Jamett, Juan Pablo Vielma and Luis A. Cisternas
The objective of the present study was to develop a procedure for flotation circuit design including uncertainty and water efficiency. The design process considers two stages: 1) optimal process design without consider water consumption, and 2) efficient use of water considering property integration. For the flotation circuit design, we applied stochastic programming. In the optimization problem, it is desired to find the optimal configuration, equipment design and operational conditions of a circuit with multiple stages (rougher, scavenger, cleaner). The problem includes uncertainty in the feed composition and in the metal price. Each uncertain parameter is characterized probabilistically using scenarios with different occurrence probabilities. Then, considering the solutions to different scenarios, property integration is used to design the water integration system. Three properties are included: pH, oxygen concentration, and conductivity. The application of procedure to an example, show that including uncertainty in the design process can be useful in finding better design and the property integration method can be extended to use in mineral processing. The novelty of this work is the integration of both methodologies and the application of these tools to mineral processing.
In I. D. Lockhart Bogle and M. Fairweather, editors, Proceedings of the 22nd European Symposium on Computer Aided Process Engineering (Escape 22), Computer-Aided Chemical Engineering 30, 2012. pp. 1277-1281.
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.
Mathematics of Operations Research 36, 2011. pp. 227-239.
[PDF] [DOI:10.1287/moor.1110.0488][BibTeX]
Daniel Dadush, Santanu S. Dey and Juan Pablo Vielma
The Chvátal-Gomory closure and the split closure of a rational polyhedron are rational polyhedra. It was recently shown that the Chvátal-Gomory closure of strictly convex body is also a rational polytope. In this note, we show that the split closure of a strictly convex body is defined by a finite number of split disjunctions, but is not necessarily polyhedral. We also give a closed form expression in the original variable space of a split cut for full dimensional ellipsoids.
Operations Research Letters 39, 2011. pp. 121-126.
[PDF] [DOI:10.1016/j.orl.2011.02.002][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
This paper studies two Mixed Integer Linear Programming (MILP) formulations for piecewise linear functions considered in Li et al. (2009). Although the ideas used to construct one of these formulations are theoretically interesting and could eventually provide a computational advantage, we show that their use in modeling piecewise linear functions yields a poor MILP formulation. We specifically show that neither of the formulations in Li et al. (2009) have a favorable strength property shared by all standard MILP formulations for piecewise linear functions. We also show that both formulations in Li et al. (2009) are significantly outperformed computationally by standard MILP formulations.
INFORMS Journal on Computing 22, 2010. pp. 493-497.
[PDF] [DOI:10.1287/ijoc.1100.0379][BibTeX]
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.
Marcos Goycoolea, Alan T. Murray, Juan Pablo Vielma and Andres Weintraub
We survey three integer-programming approaches for solving the area restriction model (ARM) for harvest scheduling. We describe and analyze each of these approaches in detail, comparing them both from a modeling and computational point of view. In our analysis of these formulations as modeling tools we show how each can be extended to incorporate additional harvest scheduling concerns. In our computational analysis we illustrate the strengths and weaknesses of each formulation as a practical optimization tool by studying harvest scheduling in three North American forests.
Forest Science 55, 2009. pp. 149-165.
Juan Pablo Vielma, Daniel Espinoza and Eduardo Moreno
In this work we study how to incorporate risk control to the generation of ultimate pits when orebodies are modeled through a �nite number of conditional simulations. To control risk we consider a chance constraint on the value of the ultimate pit. We incorporate this measure into the generation of ultimate pits by solving a stochastic programming version of the ultimate pit problem. We compare this stochastic programming problem to previous approaches such as generating the ultimate pit for each simulation and the hybrid pit approach introduced by Whittle and Bozorgebrahimi. We also study the effect of using different number of simulations in the generation and evaluation of ultimate pits.
Proceedings of the 34th International Symposium on Application of Computers and Operations Research in The Mineral Industry (APCOM 2009), 2009. pp. 107-114.
Ph.D. Thesis, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 2009.
[Available at smartech.gatech.edu]
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.
INFORMS Journal on Computing 20, 2008. pp. 438-450.
[PDF] [DOI:10.1016/10.1287/ijoc.1070.0256][BibTeX]
Juan Pablo Vielma, Ahmet B. Keha and George L. Nemhauser
A branch-and-cut algorithm for solving linear problems with continuous separable piecewise linear cost functions was developed in 2005 by Keha et. al. This algorithm is based on valid inequalities for an SOS2 based formulation of the problem. In this paper we study the extension of the algorithm to the case where the cost function is only lower semicontinuous. We extend the SOS2 based formulation to the lower semicontinuous case and show how the inequalities introduced by Keha et. al. can also be used for this new formulation. We also introduce a simple generalization of one of the inequalities introduced by Keha et. al. Furthermore, we study the discontinuities caused by fixed charge jumps and introduce two new valid inequalities by extending classical results for fixed charge linear problems. Finally, we report computational results showing how the addition of the developed inequalities can significantly improve the performance of CPLEX when solving these kinds of problems.
Discrete Optimization 5, 2008. pp. 467-488.
[PDF] [DOI:10.1016/j.disopt.2007.07.001][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.
[PDF] [DOI:10.1016/10.1007/978-3-540-68891-4_14][BibTeX]
Two independent proofs of the polyhedrality of the split closure of Mixed Integer Linear Program have been previously presented. Unfortunately neither of these proofs is constructive. In this paper, we present a constructive version of this proof. We also show that split cuts dominate a family of inequalities introduced by K�ppe and Weismantel.
An extended version of this paper can be found here.
Operations Research Letters 35, 2007. pp. 29-35.
[PDF] [DOI:10.1016/j.orl.2005.12.005][BibTeX]
Juan Pablo Vielma, Alan T. Murray, David M. Ryan and Andres Weintraub
Forest Harvest Scheduling problems incorporating area-based restrictions have been of great practical interest for several years, but only recently have advances been made that allow them to be efficiently solved. One significant development has made use of formulation strengthening using the Cluster Packing Problem. This improved formulation has allowed medium sized problems to be easily solved, but when restrictions on volume production over time are added, problem difficulty increases substantially. In this paper we study the degrading effect of certain types of volume constraints and propose methods for reducing this effect. Developed methods include the use of constraint branching, the use of elastic constraints with dynamic penalty adjustment and a simple integer allocation heuristic. Application results are presented to illustrate the computational improvement afforded by the use of these methods.
European Journal of Operational Research 176, 2007. pp. 1246-1264.
[PDF] [DOI:10.1016/j.ejor.2005.09.016][BibTeX]
Juan Pablo Vielma, Marcos Goycoolea, Alan T. Murray and Andres Weintraub
In this article we study the effectiveness of alternative integer programming formulations for area constrained harvest scheduling, known as the area restriction model (ARM). Empirical assessment of the effect of area constraints on the optimal objective value of these alternative approaches is carried out, focusing on the root Linear Programming relaxation. We also examine how this relates to the effectiveness of these formulations when solved by a commercial solver, CPLEX.
To appear in Proceedings of the 12th Symposium for Systems Analysis in Forest Resources (SSAFR'06), 2006.
Juan Pablo Vielma, Alan T. Murray, David M. Ryan and Andres Weintraub
Area-based harvest scheduling models, where management decisions are made for relatively small units subject to amaximum harvest area restriction, are known to be very difficult to solve by exact techniques. Previous research has developed good approaches for solving small and medium sized forestry applications based on projecting the problem onto a cluster graph for which cliques can be applied. However, as multiple time periods become of interest, current approaches encounter difficulties preventing successful identification of optimal solutions. In this paper we present an approach for elasticizing timber demand constraints, which lends itself to an efficient solution technique. It is also possible using this approach to examine trade-offs between objective value performance and maintaining demand constraints.
In M. Bevers and T.M. Barrett, editors, Proceedings of the 10th Symposium for Systems Analysis in Forest Resources (SSAFR'03), USDA Forest Services General Technical Report PNW-GTR-656, 2005. pp. 285-290.
Mathematical Engineering Thesis (In Spanish), Department of Mathematical Engineering, University of Chile, Santiago, Chile, 2003.
Juan Pablo Vielma, Alan T. Murray, David M. Ryan and Andres Weintraub
Area-based forest harvest scheduling models, where management decisions are made for relatively small units subject to a maximum harvest area restriction, are known to be very difficult to solve by exact techniques. Previous research has developed good approaches for solving small and medium sized forestry applications based on projecting the problem onto a cluster graph for which cliques can be applied. However, as multiple time periods become of interest, current approaches encounter difficulties preventing successful identification of optimal solutions. In this paper we present an approach for elasticizing timber demand constraints, which lends itself to an efficient solution technique. It is also possible using this approach to examine trade-offs between objective value performance and maintaining demand constraints.
Proceedings of the 38th Annual Conference of the Operational Research Society of New Zealand (ORSNZ'03), 2003. pp. 21-28.