Publications of Juan Pablo Vielma

Peer Reviewed Journal Articles

• A lifted linear programming branch-and-bound algorithm for mixed integer conic quadratic programs. Juan Pablo Vielma, Shabbir Ahmed and George L. Nemhauser. INFORMS Journal on Computing 20, pp. 438-450, 2008.


• Nonconvex, lower semicontinuous piecewise linear optimization. Juan Pablo Vielma, Ahmet B. Keha and George L. Nemhauser. Discrete Optimization 5, pp. 467-488, 2008.


• A constructive characterization of the split closure of a mixed integer linear program. Juan Pablo Vielma. Operations Research Letters 35, pp. 29-35, 2007.


• Improving computational capabilities for addressing volume constraints in forest harvest scheduling problems. Juan Pablo Vielma, Alan T. Murray, David M. Ryan and Andres Weintraub. European Journal of Operational Research 176, pp. 1246-1264, 2007.

Refereed Papers in Proceedings

• Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Juan Pablo Vielma and George L. 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), pp. 199-213, 2008.


• Improved solution techniques for multi-period area-based forest harvest scheduling problems. Juan Pablo Vielma, Alan T. Murray, David M. Ryan and Andres 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), pp. 285-290, 2005.

Papers in Proceedings

• Improved solution techniques for multi-period area-based forest harvest scheduling problems. Juan Pablo Vielma, Alan T. Murray, David M. Ryan and Andres Weintraub. Proceedings of the 38th Annual Conference of the Operational Research Society of New Zealand (ORSNZ'03), pp. 21-28, 2003.

Forthcoming

• Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Juan Pablo Vielma and George L. Nemhauser. Submitted for publication, 2008.


• Evaluating alternative approaches for solving the area restriction model in harvest scheduling. Marcos Goycoolea, Alan T. Murray, Juan Pablo Vielma and Andres Weintraub. Submitted for publication, 2007.

Publication Details

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.

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.

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.

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 linear in m. We give sufficient conditions for constructing formulations for these constraints with a number of binary variables and extra constraints logarithmic in m. Using these conditions we introduce the first 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.

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.