column generation

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

    Lexicographic Branch-and-Bound Column Search

  • Andreas Bärmann
  • Alexander Müller
  • Dieter Weninger
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Scheduling Tags , , , , ,

    We present an exact generic method for solving the pricing problem in a column generation approach, which we call branch-and-bound column search. It searches the space of all feasible columns via a branch-and-bound tree search and returns all columns with a reduced-cost value below a certainthreshold. The approach is based on an idea from Krumke … Read more

    Capacity planning with uncertain endogenous technology learning

  • Tushar Rathi
  • Qi Zhang
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , , , ,

    Optimal capacity expansion requires complex decision-making, often influenced by technology learning, which represents the reduction in expansion cost due to factors such as cumulative installed capacity. However, having perfect foresight over the technology cost reduction is highly unlikely. In this work, we develop a multistage stochastic programming framework to model capacity planning problems with endogenous … Read more

    Operation of an ambulance fleet under uncertainty

  • Victor Hugo Nascimento
  • Vincent Guigues
  • Anton J. Kleywegt
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , , , ,

    We introduce two new optimization models for the dispatch of ambulances. These models are to our knowledge the first providing a full modelling of the operation of an ambulance fleet, taking into account all or almost all constraints of the problem. The first model, called the ambulance selection problem, is used when an emergency call … Read more

    An efficient solution methodology for the airport slot allocation problem with preprocessing and column generation

  • Paula Fermín Cueto
  • Sergio García
  • Miguel F. Anjos
    • Categories Airline Optimization, Scheduling, Transportation Tags , , , ,

    Airport coordination is a demand control mechanism that maximizes the use of existing infrastructure at congested airports. Aircraft operators submit a list of regular flights that they wish to operate over a five to seven-month period and a designated coordinator is responsible for allocating the available airport slots, which represent the permission to operate a … Read more

    Integer programming column generation: Accelerating branch-and-price using a novel pricing scheme for finding high-quality solutions in set covering, packing, and partitioning problems

  • Stephen J. Maher
  • Elina Rönnberg
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    Large-neighbourhood search (LNS) heuristics are important mathematical programming techniques that search for primal feasible solutions by solving an auxiliary problem with a restricted feasible region. Extending such powerful generic LNS heuristics to the branch- and-price context is inherently challenging. The most prominent challenges arise from the fact that in branch-and-price algorithms, columns are generated with … Read more