Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse
Abstract
Stochastic integer programs (SIPs) are very large scale integer programs that model discrete optimization problems under uncertainty. SIPs have been used in many applciations, including transportation, manufacturing, power generation, and military operations. SIPs are challenging to solve using standard integer programming tools because they simultaneously consider a large number of outcome scenarios. To address this difficulty, decomposition methods are employed to obtain lower bounds for use within a branch-and-bound framework. Two common decomposition approaches are dual decomposition and Benders decomposition. Each of these techniques has its limitations. Dual decomposition requires solving integer programming subproblems, and therefore computing a single relaxation bound can be very time-consuming. Benders decomposition uses linear programming (LP) subproblems, but the resulting relaxations are often weak, leading to impractically large branch-and-bound trees. In this project we investigate techniques to improve the cuts used within Benders decomposition, with the goal of obtaining relaxations nearly as strong as those obtained by dual decomposition, but while preserving the use of efficient LP subproblems. A natural approach to improving upon Benders cuts (we call it project-and-cut) is to generate Benders cuts to approximate the feasible region of the Benders reformulation, and then use integrality information to derive valid inequalities for this formulation. We investigate an alternative approach, which we refer to as cut-and-project, in which valid inequalities that use integrality constraints of the first-stage decision variables are derived and added to the second-stage subproblems. The resulting tightened LPs are then used to obtain stronger Benders cuts. An advantage of this approach is that cuts exploiting problem structure can easily be incorporated. We propose to study the relative strengths of the relaxations obtained using these two approaches, in particular when the valid inequalities used are split cuts. We first show that the relaxations are equivalent when considering a single split disjunction, but when considering multiple split disjunctions, obtaining the cuts in the extended space (as in cut-and-project) can lead to a strictly better relaxation. We will also investigate techniques for most effectively using cutting planes within a decomposition framework. We plan to perform extensive computational experiments to compare the use of the same family of cuts in cut-and-project and project-and-cut. One goal is to understand problem characteristics that will tend to favor one method over another. We will also investigate alternative approaches for using cuts in the two approaches, and possibly for combining the two approaches together. Finally, we will use the insights gained from this study to investigate possible further applications of the proposed cut-and-project framework. One possibility is to explore whether the use of the cut-and-project framework can also be useful in robust integer programming models, which often also possess the projection structure used in decomposition methods for SIP. Another question we wish to explore is whether or not it is possible to construct extended formulations of different classes of integer programming problems for the explicit purpose of generating cuts in that extended variable space, and then projecting the resulting improved formulation. In the SIP context, the extensive form was a naturally given extended variable space formulation. We will investigate the possibility of constructing extended formulations for other types of problems where such a natural extended formulation is not already given.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141512268
Entities
People
- James Luedtke
Organizations
- Office of Naval Research
- United States Navy
- University of Wisconsin System