Publications of Juan Pablo Vielma

Submitted

1. Imposing connectivity constraints in forest planning models. R. Carvajal, M. Constantino, M. Goycoolea, J. P. Vielma and A. Weintraub. Submitted for publication, 2011.
2. Computational experiments with cross and crooked cross cuts. S. Dash, O. Günlük and J. P. Vielma. Submitted for publication, 2011.
3. Strong dual for conic mixed-integer programs. D. Morán, S. S. Dey and J. P. Vielma. Submitted for publication, 2011.
4. On the Chvátal-Gomory closure of a compact convex set. D. Dadush, S. S. Dey and J. P. Vielma. Submitted for publication, 2011.

Peer Reviewed Journal Articles

1. Mixed integer linear programming formulations for probabilistic constraints. J. P. Vielma, S. Ahmed and G. Nemhauser. To appear in Operations Research Letters, 2012.
2. Fitting piecewise linear continuous functions. A. Toriello and J. P. Vielma. European Journal of Operational Research 219, 2012. pp. 86-95.
3. An integer linear programming approach for bilinear integer programming. A. S. Freire, E. Moreno and J. P. Vielma. Operations Research Letters 40, 2012. pp. 74-77.
4. 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.
5. The split closure of a strictly convex body. D. Dadush, S. S. Dey and J. P. Vielma. Operations Research Letters 39, 2011. pp. 121-126.
6. 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.
7. A note on `A superior representation method for piecewise linear functions' . J. P. Vielma, S. Ahmed and G. Nemhauser. INFORMS Journal on Computing 22, 2010. pp. 493-497.
8. 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.
9. Evaluating alternative approaches for solving the area restriction model in harvest scheduling. M. Goycoolea, A. Murray, J. P. Vielma and A. Weintraub. Forest Science 55, 2009. pp. 149-165.
10. 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.
11. Nonconvex, lower semicontinuous piecewise linear optimization. J. P. Vielma, A. Keha and G. Nemhauser. Discrete Optimization 5, 2008. pp. 467-488.
12. A constructive characterization of the split closure of a mixed integer linear program. J. P. Vielma. Operations Research Letters 35, 2007. pp. 29-35.
13. Improving computational capabilities for addressing volume constraints in forest harvest scheduling problems. J. P. Vielma, A. Murray, D. Ryan and A. Weintraub. European Journal of Operational Research 176, 2007. pp. 1246-1264.

Peer Reviewed Conference Proceeding Articles

1. On the Chvátal-Gomory Closure of a compact convex set. D. Dadush, S. S. Dey and J. P. Vielma. Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization (IPCO 2011), Lecture Notes in Computer Science Vol. 6655 (O. Günlük and G. J. Woeginger, editors), 2011. pp. 130-142.
2. The Chvátal-Gomory closure of an ellipsoid is a polyhedron. S. S. Dey and J. P. Vielma. Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization (IPCO 2010), Lecture Notes in Computer Science Vol. 6080 (F. Eisenbrand and F. B. Shepherd, editors), 2010. pp. 327-340.
3. Risk control in ultimate pits using conditional simulations. J. P. Vielma, D. Espinoza and E. Moreno. Proceedings of the 34th International Symposium on Application of Computers and Operations Research in The Mineral Industry (APCOM 2009), 2009. pp. 107-114.
4. Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. J. P. Vielma and G. Nemhauser. Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO 2008), Lecture Notes in Computer Science Vol. 5035 (A. Lodi, A. Panconesi and G. Rinaldi, editors), 2008. pp. 199-213.
5. Improved solution techniques for multi-period area-based forest harvest scheduling problems. J. P. Vielma, A. Murray, D. Ryan and A. Weintraub. Proceedings of the 10th Symposium for Systems Analysis in Forest Resources (SSAFR'03), USDA Forest Services General Technical Report PNW-GTR-656 (M. Bevers and T.M. Barrett, editors), 2005. pp. 285-290.

Other Publications

1. Mixed integer programming approaches for nonlinear and stochastic programming. J. P. Vielma. Ph.D. Thesis, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 2009.
2. Comparing alternative formulations for the ARM. J. P. Vielma, M. Goycoolea, A. Murray and A. Weintraub. To appear in Proceedings of the 12th Symposium for Systems Analysis in Forest Resources (SSAFR'06), 2006.
3. Restricciones de volumen elásticas para un problema de planificación forestal con restricciones de área en múltiples períodos. J. P. Vielma. Mathematical Engineering Thesis (In Spanish), Department of Mathematical Engineering, University of Chile, Santiago, Chile, 2003.
4. Improved solution techniques for multi-period area-based forest harvest scheduling problems. J. P. Vielma, A. Murray, D. Ryan and A. Weintraub. Proceedings of the 38th Annual Conference of the Operational Research Society of New Zealand (ORSNZ'03), 2003. pp. 21-28.

Publication Details

Mixed integer linear programming formulations for probabilistic constraints

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.

Fitting piecewise linear continuous functions

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.

An integer linear programming approach for bilinear integer programming

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.

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.

This paper was a finalist for the 2010 INFORMS Junior Faculty Interest Group Paper Competition.

The split closure of a strictly convex body

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.

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.

A note on `A superior representation method for piecewise linear functions'

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.

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.

Evaluating alternative approaches for solving the area restriction model in harvest scheduling

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.

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.

In November 2007 this paper received the Optimization Society Student Paper Prize, from the INFORMS Optimization Society.

Nonconvex, lower semicontinuous piecewise linear optimization

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.

A constructive characterization of the split closure of a mixed integer linear program

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.

Improving computational capabilities for addressing volume constraints in forest harvest scheduling problems

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.

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

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.

Risk control in ultimate pits using conditional simulations

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.

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.

Improved solution techniques for multi-period area-based forest harvest scheduling problems

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.

Mixed integer programming approaches for nonlinear and stochastic programming

Comparing alternative formulations for the ARM

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.

Restricciones de volumen elásticas para un problema de planificación forestal con restricciones de área en múltiples períodos

Improved solution techniques for multi-period area-based forest harvest scheduling problems

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.

Imposing connectivity constraints in forest planning models

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.

Computational experiments with cross and crooked cross cuts

In a recent paper, Dash, Dey and Günlük (2010) showed that many families of inequalities for the two-row continuous group relaxation and variants of this relaxation are cross cuts or crooked cross cuts, both of which generalize split cuts. Li and Richard (2008) recently studied $t$-branch split cuts for mixed-integer programs for integers $t\ge 1$. Split cuts are just 1-branch split cuts, and cross cuts are 2-branch split cuts. In this paper, we study whether cross and crooked cross 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 also study whether such cuts obtained from two simplex tableau rows at a time can strengthen the bounds obtained by GMI cuts based on single tableau rows. We give positive answers to both these questions for MIPLIB 3.0 problems.

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.

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.