branch-and-price

An Overview of Nested Decomposition for Multi-Level Optimization Problems

  • Stephen J. Maher
  • Ibrahim Muter
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , , ,

    Nested multi-level structures are frequently encountered in many real-world optimization problems. Decomposition techniques are a commonly applied approach used to handle nested multi-level structures; however, the typical problem-specific focus of such techniques has led to numerous specialized formulations and solution methods. This lack of generalized results for nested multi-level optimization problems is addressed in this … Read more

    Interval Scheduling with Economies of Scale

  • Christopher Muir
  • Alejandro Toriello
    • Categories Dynamic Programming, Integer Programming, Scheduling Tags , , ,

    Motivated by applications in cloud computing, we study interval scheduling problems exhibiting economies of scale. An instance is given by a set of jobs, each with start time, end time, and a function representing the cost of scheduling a subset of jobs on the same machine. Specifically, we focus on the max-weight function and non-negative, … Read more

    The vehicle allocation problem: alternative formulation and branch-and-price method

  • Alysson Machado Costa
  • Cesar Alvarez Cruz
  • Reinaldo Morabito
  • Pedro Munari
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    The Vehicle Allocation Problem (VAP) consists of repositioning empty vehicles across a set of terminals over a given planning horizon so as to maximize the profits generated from serving demand for transportation of goods between pair of terminals. This problem has been classically modeled using an extended space-time network which captures the staging of the … Read more

    A branch-and-price method for the vehicle allocation problem

  • Cesar Alvarez Cruz
  • Reinaldo Morabito
  • Pedro Munari
    • Categories Applications - OR and Management Sciences, Integer Programming, Transportation Tags , , , ,

    The Vehicle Allocation Problem (VAP) consists of allocating a fleet of vehicles to attend to the expected demand for freight transportation between terminals along a finite multiperiod planning horizon. The objective is to maximize the profits generated for the completed services. The previous deterministic and stochastic approaches used heuristic procedures and approximations for solving large-scale … Read more

    A multicommodity flow model for rerouting and retiming trains in real-time to reduce reactionary delay in complex station areas

  • Matthias Ehrgott
  • Stephen J. Maher
  • Edwin Reynolds
  • Anthony Patman
  • Judith Y.T. Wang
    • Categories Transportation Tags , , ,

    By rerouting and retiming trains in real-time, the propagation of reactionary delay in complex station areas can be reduced. In this study, we propose a new optimisation model and solution algorithm that can be used to determine the best combination of route and schedule changes to make. Whilst several models have been proposed to tackle … Read more

    The SCIP Optimization Suite 7.0

  • Daniel Anderson
  • Ksenia Bestuzheva
  • Wei-Kun Chen
  • Leon Eifler
  • Gerald Gamrath
  • Maxime Gasse
  • Ambros Gleixner
  • Gregor Hendel
  • Christopher Hojny
  • Thorsten Koch
  • Pierre Le Bodic
  • Stephen J. Maher
  • Frederic Matter
  • Matthias Miltenberger
  • Marc E. Pfetsch
  • Felipe Serrano
  • Dieter Weninger
  • Jakob Witzig
  • Patrick Gemander
  • Leona Gottwald
  • Katrin Halbig
  • Erik Mühmer
  • Benjamin Müller
  • Franziska Schlösser
  • Yuji Shinano
  • Christine Tawfik
  • Stefan Vigerske
  • Fabian Wegscheider
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , , , , , , , , , , ,

    The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies … Read more

    Exact Methods for the Traveling Salesman Problem with Drone

  • Roberto Roberti
  • Mario Ruthmair
    • Categories (Mixed) Integer Linear Programming, Dynamic Programming, Transportation Tags , , , ,

    Efficiently handling last-mile deliveries becomes more and more important nowadays. Using drones to support classical vehicles allows improving delivery schedules as long as efficient solution methods to plan last-mile deliveries with drones are available. We study exact solution approaches for some variants of the traveling salesman problem with drone (TSP-D) in which a truck and … Read more

    Feeder Routing for Air-to-Air Refueling Operations

  • Christoph Hansknecht
  • Imke Joormann
  • Bernd Korn
  • Fabian Morscheck
  • Sebastian Stiller
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , , ,

    We consider the problem of routing a fleet of feeders for civil air-to-air refueling operations. In the air-to-air refueling problem, a fixed set of cruisers requires refueling by a fleet of feeders at fixed locations and fixed points in time. A typical objective function is to minimize the fuel consumption or the total number of … Read more

    A branch and price algorithm for the resource constrained home health care vehicle routing problem

  • Neda Tanoumand
  • Tonguç Ünlüyurt
    • Categories Integer Programming, Linear Programming Tags , , ,

    We consider the vehicle routing problem with resource constraints motivated by a home health care application. We propose a branch and price algorithm to solve the problem. In our problem, we consider different types of patients that require a nurse or a health aid or both. The patients can be serviced by the appropriate vehicles … Read more

    An Iterative Re-optimization Framework for the Dynamic Vehicle Routing Problem with Roaming Delivery Locations

  • Gizem Ozbaygin
  • Martin Savelsbergh
    • Categories Network Optimization, Transportation Tags , , ,

    Branch-and-price has established itself as an effective solution methodology for a wide variety of planning problems. We investigate its potential as a solution method- ology for solving operational problems. Specifically, we explore its potential in the context of a dynamic variant of the vehicle routing problem with roaming delivery locations, in which customer itineraries may … Read more