Abstract
We present an approximation algorithm for solving large 0–1 integer programming problems whereA is 0–1 and whereb is integer. The method can be viewed as a dual coordinate search for solving the LP-relaxation, reformulated as an unconstrained nonlinear problem, and an approximation scheme working together with this method. The approximation scheme works by adjusting the costs as little as possible so that the new problem has an integer solution. The degree of approximation is determined by a parameter, and for different levels of approximation the resulting algorithm can be interpreted in terms of linear programming, dynamic programming, and as a greedy algorithm. The algorithm is used in the CARMEN system for airline crew scheduling used by several major airlines, and we show that the algorithm performs well for large set covering problems, in comparison to the CPLEX system, in terms of both time and quality. We also present results on some well known difficult set covering problems that have appeared in the literature.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E.H.L. Aarts and J.H.M. Korst,Simulated Annealing and Boltzmann Machines (Wiley, 1989).
J.P. Arabeyre, J. Fearnley, F.C. Steiger and W. Teather, The Airline Crew scheduling problem: A survey, Transp. Sci. 3(1969)140–163.
D. Avis, A note on some computationally difficult set covering problems, Math. Progr. 18(1980)138–145.
E. Balas and A. Ho, Set covering algorithms using cutting planes, heuristics and subgradient optimization: a computational study, Math. Progr. Study 12(1980)37–60.
U. Bertele and F. Brioschi,Nonserial Dynamic Programming (Academic Press, 1972).
V. Chvatal, A greedy-heuristic for the set-covering problem, Math. Oper. Res. 4(1979)233–235.
CPLEX Reference Manual (CPLEX Optimization Inc., 1992).
J. Derosiers, Y. Dumas, M.M. Solomon and F. Soumis, Time constrained routing and scheduling, in:Handbooks in Operations Research and Management Science, volume onNetworks (North-Holland, 1993), to be published.
M.M. Etschmaier and D.F. Mathaisel, Airline scheduling: an overview, Transp. Sci. 19(1985)127–138.
T.A. Feo and M.G.C. Resende, A probabilistic heuristic for a computational difficult set covering problem, Oper. Res. Lett. 8(1989)67–71.
D.R. Fulkerson, G.L. Nemhauser and L.E. Trotter, Jr., Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of Steiner triple systems, Math. Progr. Study 7(1974)72–81.
M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, 1979).
T.C. Hu,Integer Programming and Network Flows (Addison-Wesley, 1969).
N. Karmarkar, M.G.C. Resende and K.G. Ramakrishnan, An interior point algorithm to solve computationally difficult set covering problems, Math. Progr. 52(1991)597–618.
S. Lavoie, M. Minoux and E. Odier, A new approach for crew pairing problems with an application to air transportation, Euro. J. Oper. Res. 35(1988)45–58.
G.L. Nemhauser and L.A. Wolsey,Integer and Combinational Optimization (Wiley, 1988).
A. Schrijver,Theory of Linear and Integer Programming (Wiley, 1986).
M. Syslo, N. Deo and J.S. Kowalik,Discrete Optimization Algorithms (Prentice-Hall, 1983).
D. Wedelin, Probabilistic networks and combinatorial optimization, Technical report 49, Department of Computing Science, Chalmers University of Technology (1989).
D. Wedelin, Probabilistic inference, combinatorial optimization and the discovery of causal structure from data, Ph.D Thesis, Department of Computing Science, Chalmers University of Technology (1993).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wedelin, D. An algorithm for large scale 0–1 integer programming with application to airline crew scheduling. Ann Oper Res 57, 283–301 (1995). https://doi.org/10.1007/BF02099703
Issue Date:
DOI: https://doi.org/10.1007/BF02099703