Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse
Abstract
This report summarizes the research findings obtained in the project Strengthened Benders Cuts for Stochastic Integer Programs withContinuous Recourse. The first topic investigated was a comparison of the strength of relaxation obtained when using split cuts to improvea mixed-integer programming formulation in an extended vs. in a projected space. In general, split cuts in the extended space can lead tobetter relaxations. This has implications for stochastic integer programming in that it implies that one should seek to find split cuts valid forthe Benders subproblems before projecting to obtain Benders cuts in the space of first-stage variables. On the other hand, using split cutson the master problem also has a potential benefit in that doing so can combine relaxations from multiple scenarios. These findings alsomotivated investigation into new techniques for using extended formulations to obtain improved valid inequalities. Finally, specializedtechniques were investigated for solving a particular class of stochastic integer program known as the vehicle routing problem withstochastic demands. In particular, improved valid inequalities and a relaxed pricing scheme were discovered to be effective at reducing theintegrality gap of such problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 15, 2018
- Accession Number
- AD1067611
Entities
People
- James Luedtke
- Oktay Gimluk
- Sanjeeb Dash
Organizations
- University of Wisconsin–Madison