Airline Optimization

On some difficult linear programs coming from Set Partitioning

  • Ranga Anbil
  • Francisco Barahona
    • Categories Airline Optimization, Combinatorial Optimization Tags , ,

    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 … Read more

    A Parallel, Linear Programming Based Heuristic for Large Scale Set Partitioning Problems

  • Eva Lee
  • Jeff Linderoth
  • Martin Savelsbergh
    • Categories 0-1 Programming, Airline Optimization, Parallel Algorithms Tags , ,

    We describe a parallel, linear programming and implication based heuristic for solving set partitioning problems on distributed memory computer architectures. Our implementation is carefully designed to exploit parallelism to greatest advantage in advanced techniques like preprocessing and probing, primal heuristics, and cut generation. A primal-dual subproblem simplex method is used for solving the linear programming … Read more