column generation

A novel passenger recovery approach for the integrated airline recovery problem

  • Stephen J. Maher
    • Categories (Mixed) Integer Linear Programming, Airline Optimization Tags , , ,

    Schedule disruptions require airlines to intervene through the process of recovery; this involves modifications to the planned schedule, aircraft routings, crew pairings and passenger itineraries. Passenger recovery is generally considered as the final stage in this process, and hence passengers experience unnecessarily large impacts resulting from flight delays and cancellations. Most recovery approaches considering passengers … Read more

    A cutting surface algorithm for semi-infinite convex programming with an application to moment robust optimization

  • Sanjay Mehrotra
  • Dávid Papp
    • Categories Robust Optimization, Semi-infinite Programming, Stochastic Programming Tags , , , , , , ,

    We first present and analyze a central cutting surface algorithm for general semi-infinite convex optimization problems, and use it to develop an algorithm for distributionally robust optimization problems in which the uncertainty set consists of probability distributions with given bounds on their moments. The cutting surface algorithm is also applicable to problems with non-differentiable semi-infinite … Read more

    Acceleration and Stabilization Techniques for Column Generation Applied to Capacitated Resource Management Problems

  • Alper Uygur
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Scheduling Tags , , ,

    This research presents a very efficient method of solving a broad class of large-scale capacitated resource management problems by introducing a new formulation and decomposition. A heuristic called Likelihood of Assignment is utilized not only to find high quality initial integer feasible solutions, but also to guide the Branch-and-Price (B&P) Algorithm towards stabilization. Although Column … Read more

    Exact algorithms for the Traveling Salesman Problem with Draft Limits

  • Maria Battarra
  • Artur Alves Pessoa
  • Anand Subramanian
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Integer Programming Tags , , , ,

    This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance … Read more

    Solving the integrated airline recovery problem using column-and-row generation

  • Stephen J. Maher
    • Categories (Mixed) Integer Linear Programming, Airline Optimization Tags , ,

    Airline recovery presents very large and difficult problems requiring high quality solutions within very short time limits. To improve computational performance, the complete airline recovery problem is generally formulated as a series of sequential stages. While the sequential approach greatly simplifies the complete recovery problem, there is no guarantee of global optimality or solution quality. … Read more

    Using the primal-dual interior point algorithm within the branch-price-and-cut method

  • Jacek Gondzio
  • Pedro Munari
    • Categories Integer Programming Tags , , ,

    Branch-price-and-cut has proven to be a powerful method for solving integer programming problems. It combines decomposition techniques with the generation of both columns and valid inequalities and relies on strong bounds to guide the search in the branch-and-bound tree. In this paper, we present how to improve the performance of a branch-price-and-cut method by using … Read more

    On parallelizing dual decomposition in stochastic integer programming

  • Miles Lubin
  • Kipp Martin
  • Burhaneddin Sandikçi
  • Cosmin G. Petra
    • Categories Nonsmooth Optimization, Parallel Algorithms, Stochastic Programming Tags , , , , ,

    For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Car\o{}e and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parallel execution by identifying a formulation that permits the parallel solution of the \textit{master} program by using structure-exploiting interior-point solvers. Our results demonstrate the potential … Read more

    Automatic Dantzig-Wolfe Reformulation of Mixed Integer Programs

  • Martin Bergner
  • Alberto Caprara
  • Alberto Ceselli
  • Fabio Furini
  • Marco E. Lübbecke
  • Enrico Malaguti
  • Emiliano Traversi
    • Categories (Mixed) Integer Linear Programming Tags , , , , ,

    Dantzig-Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method is not implemented in any state-of-the-art MIP solver as it is considered to require structural problem knowledge and tailoring to this structure. We provide a computational proof-of-concept that the reformulation can be automated. That … Read more

    A new warmstarting strategy for the primal-dual column generation method

  • Jacek Gondzio
  • Pablo Gonzalez-Brevis
    • Categories Cutting Plane Approaches, Linear Programming Tags , , , ,

    This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after … Read more

    Improved Column Generation for Highly Degenerate Master Problems

  • Jacques Desrosiers
  • Jean-Bertrand Gauthier
  • Marco E. Lübbecke
    • Categories (Mixed) Integer Linear Programming, Linear Programming Tags , ,

    Column generation for solving linear programs with a huge number of variables alternates between solving a master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to suffer from degeneracy of the master problem, exposing what is called the tailing-off effect. Inspired by recent advances in … Read more