An Effective Deflected Subgradient Optimization Scheme for Implementing Column Generation for Large-Scale Airline Crew Scheduling Problems

References

• Amor H. B., Desrosiers J., Carvalho J. M. V. Dual-optimal inequalities for stabilized column generation. Oper. Res. (2006) 54(3):454–463Link, Google Scholar
• Baker B. M., Sheasby J. Accelerating the convergence of subgradient optimisation. Eur. J. Oper. Res. (1999) 117:134–144Crossref, Google Scholar
• Barahona F., Anbil R. The volume algorithm: Producing primal solutions with a subgradient method. Math. Programming (2000) 87(3):385–399Crossref, Google Scholar
• Barahona F., Anbil R. On some difficult linear programs coming from set partitioning. Discrete Appl. Math. (2002) 118:3–11Crossref, Google Scholar
• Barnes E., Chen V., Gopalakrishnan B., Johnson E. L. A least-squares primal-dual algorithm for solving linear programming problems. Oper. Res. Lett. (2002) 30:289–294Crossref, Google Scholar
• Barnhart C., Johnson E. L., Nemhauser G. L., Savelsbergh M. W. P., Vance P. H. Branch-and-price: Column generation for solving huge integer programs. Oper. Res. (1998) 46(3):316–329Link, Google Scholar
• Bazaraa M. S., Sherali H. D., Shetty C. M.Nonlinear Programming: Theory and Algorithms (2006) 3rd ed.(John Wiley & Sons, New York) Crossref, Google Scholar
• Beasley J. OR-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. (1990) 41(11):1069–1072Crossref, Google Scholar
• Carvalho J. M. V. Using extra dual cuts to accelerate column generation. INFORMS J. Comput. (2005) 17(2):175–182Link, Google Scholar
• Desrosiers J., Dumas Y., Solomon M. M., Soumis F., Ball M. O., Magnanti T. L., Monma C. L., Nehmhauser G. L. Time constrained routing and scheduling. Handbook in Operations Research/Management Science, Network Routing (1995) 8(Elsevier Science, Amsterdam) 35–139Google Scholar
• Elhallaoui I., Villeneuve D., Soumis F., Desaulniers G. Dynamic aggregation of set-partitioning constraints in column generation. Oper. Res. (2005) 53(4):632–645Link, Google Scholar
• Gunluk O., Kimbrel T., Ladanyi L., Schieber B., Sorkin G. B. Vehicle routing and staffing for sedan service. (2004) . http://www.optimization-online.orgGoogle Scholar
• Hjorring C. Solving larger crew pairing problems. Proc. TRISTAN V: The Fifth Triennial Sympos. Transportation Anal. (2004) Le Gosier, GuadeloupeGoogle Scholar
• Hu J., Johnson E. L. Computational results with a primal-dual subproblem simplex method—A new formulation and decomposition algorithm. Oper. Res. Lett. (1999) 25:149–157Crossref, Google Scholar
• Kelley J. E. The cutting-plane method for solving convex programs. SIAM J. Appl. Math. (1960) 8:703–712Crossref, Google Scholar
• Klabjan D., Johnson E. L., Nemhauser G. L., Gelman E., Ramaswamy S. Airline crew scheduling with regularity. Transportation Sci. (2001) 35(4):359–374Link, Google Scholar
• Klabjan D., Johnson E. L., Nemhauser G. L., Gelman E., Ramaswamy S. Airline crew scheduling with time windows and plane-count constraints. Transportation Sci. (2002) 36(3):337–348Link, Google Scholar
• Kohl N. Solving the world's largest crew scheduling problem. ORbit Extra, Danish Oper. Res. Soc. (2003) 4(Special Issue, August):8–12Google Scholar
• Lim C., Sherali H. D. Convergence and computational analyses for some variable target value and subgradient deflection methods. Comput. Optim. Appl. (2006) 34(3):409–428Crossref, Google Scholar
• Makri A., Klabjan D. A new pricing scheme for airline crew scheduling. INFORMS J. Comput. (2004) 16(1):56–67Link, Google Scholar
• Merle O. D., Villeneuve D., Desrosiers J., Hansen P. Stabilized column generation. Discrete Math. (1999) 237:229–237Crossref, Google Scholar
• Nemhauser G. L., Wolsey L. A.Integer and Combinatorial Optimization (1999) 2nd ed.(Wiley Interscience, New York) Google Scholar
• Sherali H. D., Choi G. Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs. Oper. Res. Lett. (1996) 19:105–113Crossref, Google Scholar
• Sherali H. D., Lim C. On embedding the volume algorithm in a variable target value method. Oper. Res. Lett. (2004) 32:455–462Crossref, Google Scholar
• Sherali H. D., Choi G., Tuncbilek C. H. A variable target value method for nondifferentiable optimization. Oper. Res. Lett. (2000) 26:1–8Crossref, Google Scholar
• Vance P. H., Atamurk A., Barnhart C., Gelman E., Johnson E. L., Krishna A., Mahidhara D., Nemhauser G. L., Rebello R. A heuristic branch-and-price approach for the airline crew pairing problem. (1997) . Technical Report LEC-97-06, Department of Industrial and Systems Engineering, Georgia Institute of Technology, AtlantaGoogle Scholar