On some difficult linear programs coming from Set Partitioning

Francisco Barahona (barahonus.ibm.com)
ranga anbil (anbilcl.com)

Abstract: We deal with the linear programming relaxation of set partitioning problems arising in airline crew scheduling. Some of these linear programs have been extremely difficult to solve with the traditional algorithms. We have used an extension of the subgradient algorithm, the volume algorithm, to produce primal solutions that might violate the constraints by at most 2%, and that are within 1% of the lower bound. This method is fast, requires minimal storage, and can be parallelized in a straightforward way.

Keywords: Subgradient algorithm, volume algorithm, large scale linear programming

Category 1: Applications -- OR and Management Sciences (Airline Optimization )

Category 2: Combinatorial Optimization (Other )

Citation: IBM Research Report RC21410

Download: [Postscript]

Entry Submitted: 01/31/2001
Entry Accepted: 01/31/2001
Entry Last Modified: 01/31/2001

Modify/Update this entry