On Some Difficult Linear Programs Coming from Set Partitioning

        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.

By: Francisco Barahona, Ranga Anbil

Published in: Discrete Applied Mathematics, volume 118, (no 1-2), pages 3-11 in 2002

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .