Totally Unimodular Stochastic Programs

Nan Kong (kongeng.usf.edu)
Andrew Schaefer (schaeferie.pitt.edu)
Shabbir Ahmed (sahmedisye.gatech.edu)

Abstract: We consider totally unimodular stochastic programs, that is, stochastic programs whose extensive-form constraint matrix is totally unimodular. We generalize the notion of total unimodularity to apply to sets of matrics and provide properties of such sets. Using this notion, we give several sufficient conditions for specific classes of problems. When solving such problems using the L-shaped method it is not clear whether the integrality restrictions should be imposed on the master problem. Such restrictions will make each master problem more difficult to solve. On the other hand, solving the linear relaxation of the master typically means sending fractional (and unlikely optimal) solutions to the subproblems, perhaps leading to more iterations. Our computational results investigate this trade-off and provide insight into which stragtegy is preferable under a variety of circumstances.

Keywords: Stochastic Integer Programming; Total Unimodularity; L-shaped Method

Category 1: Stochastic Programming

Citation:

Download: [PDF]

Entry Submitted: 05/05/2006
Entry Accepted: 05/05/2006
Entry Last Modified: 05/05/2006

Modify/Update this entry