column generation

Crew Scheduling and Routing Problem in Road Restoration via Branch-and-Price Algorithms

  • Alfredo Moreno
  • Pedro Munari
  • Douglas Alem
    • Categories Applications - OR and Management Sciences, Transportation Tags , , , ,

    This paper addresses the single crew scheduling and routing problem in the context of road network repair and restoration, which is critical in assisting complex post-disaster decisions in humanitarian logistics settings. We present three novel formulations for this problem, which are the first suitable for column generation and branch-and-price (BP) algorithms. Specifically, our first formulation … Read more

    Integrating Public Transport in Sustainable Last-Mile Delivery: Column Generation Approaches

  • Diego Delle Donne
  • Alberto Santini
  • Claudia Archetti
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Production and Logistics Tags , , , ,

    We tackle the problem of coordinating a three-echelon last-mile delivery system. In the first echelon, trucks transport parcels from distribution centres outside the city to public transport stops. In the second echelon, the parcels move on public transport and reach the city centre. In the third echelon, zero-emission vehicles pick up the parcels at public … Read more

    Kantorovich and Zalgaller (1951): the 0-th Column Generation Algorithm

  • Eduardo Uchoa
  • Ruslan Sadykov
    • Categories Other Topics Tags , ,

    This article delves into the early development of the Column Generation technique. It begins with Kantorovich’s classic 1939 work, correcting widespread misconceptions about his contributions to the Cutting Stock Problem. Then, it brings to light Kantorovich and Zalgaller’s lesser-known 1951 book, which is revealed to contain a complete Column Generation algorithm. The article also places … Read more

    Submodular Dispatching with Multiple Vehicles

  • Ignacio Erazo
  • Alejandro Toriello
    • Categories Integer Programming, Production and Logistics, Transportation Tags , , , ,

    Motivated by applications in e-commerce logistics and production planning where orders (or items, or jobs) arrive at different times and must be dispatched or processed in batches, we consider a multi-vehicle dispatching problem that captures the tension between waiting for orders to arrive and the economies of scale due to batching. Our model extends the … Read more

    Column Generation in Column-and-Constraint Generation for Adjustable Robust Optimization with Interdiction-Type Linking Constraints

  • Henri Lefebvre
  • Martin Schmidt
  • Johannes Thürauf
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , , ,

    Adjustable robust optimization (ARO) is a powerful tool to model problems that have uncertain data and that feature a two-stage decision-making process. Computationally, they are often addressed using the column-and-constraint generation (CCG) algorithm introduced by Zeng and Zhao (2013). While it was empirically shown that the algorithm scales well if all second-stage decisions are continuous, … Read more

    On the Partial Convexification of the Low-Rank Spectral Optimization: Rank Bounds and Algorithms

  • Yongchun Li
  • Weijun Xie
    • Categories Integer Programming Tags , , , ,

    A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective subject to multiple two-sided linear matrix inequalities intersected with a low-rank and spectral constrained domain set. Although solving LSOP is, in general, NP-hard, its partial convexification (i.e., replacing the domain set by its convex hull) termed “LSOP-R”, is often tractable and yields a high-quality solution. … Read more

    Column Elimination for Capacitated Vehicle Routing Problems

  • Anthony Karahalios
  • Willem-Jan van Hoeve
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Dynamic Programming Tags , , ,

    We introduce a column elimination procedure for the capacitated vehicle routing problem. Our procedure maintains a decision diagram to represent a relaxation of the set of feasible routes, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram and yields a dual bound. The … Read more

    A Column Generation Approach for the Lexicographic Optimization of Intra-Hospital Transports

  • Andreas Bärmann
  • Alexander Martin
  • Alexander Müller
  • Dieter Weninger
    • Categories Integer Programming, Multi-Criteria Optimization, Transportation Tags , , , , ,

    Over the last fewyears, the efficient design of processes in hospitals and medical facilities has received more and more attention, particularly when the improvement of the processes is aimed at relieving theworkload of medical staff. To this end,we have developed a method to determine optimal allocations of intra-hospital transports to hospital transport employees. When optimizing … Read more

    Decremental State-Space Relaxations for the Basic Traveling Salesman Problem with a Drone

  • Marcos Blufstein
  • Gonzalo Lera-Romero
  • Francisco J. Soulignac
    • Categories Dynamic Programming, Transportation Tags , , , , ,

    Truck-and-drone routing problems have become an important topic of research in the last decade due to their applications for last-mile deliveries. Despite the large number of publications in this area, the most efficient exact algorithms designed thus far struggle to solve the benchmark instances with 39 or more customers. This fact is true even for … Read more

    COIL: A Deep Architecture for Column Generation

  • Behrouz Babaki
  • Sanjay Dominik Jena
    • Categories Linear Programming Tags , , ,

    Column generation is a popular method to solve large-scale linear programs with an exponential number of variables. Several important applications, such as the vehicle routing problem, rely on this technique in order to be solved. However, in practice, column generation methods suffer from slow convergence (i.e. they require too many iterations). Stabilization techniques, which carefully … Read more