Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse
Technical Report,01 May 2015,30 Apr 2018
University of Wisconsin Madison United States
Pagination or Media Count:
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.
- Operations Research