A Technique for the Solution of Massive Set Covering Problems, with Application to Airline Crew Scheduling

Jerrold Rubin
Additional contact information
Jerrold Rubin: Philadelphia Scientific Center, IBM Corp., Philadelphia, Pennsylvania

Transportation Science, 1973, vol. 7, issue 1, 34-48

Abstract: Recent set covering algorithms have been able to solve problems for which the constraint matrix has as many as 10 columns. Unfortunately, in certain applications, the number of columns is combinatorially dependent on the number of rows, and can reach many orders of magnitude greater, for 500--1,000 rows. For these problems, the constraint matrix cannot be generated, much less solved, unless severe ad hoc limitations are imposed. It stems clear that we must reluctantly abandon the search for the true mathematical optimum in such cases. One method of attack is to use a set covering algorithm repeatedly on much smaller matrices extracted from the overall problem, generating columns as needed. Such an approach has been used on an airline crew-scheduling problem, with excellent practical success on test cases involving close to 1,000 rows. It utilizes some techniques that are more generally applicable, and some that make use of the structure of the crew-scheduling problem, and that therefore are specific to it.

Date: 1973
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.7.1.34 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:7:y:1973:i:1:p:34-48

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().