column generation

Hub Network Design Problem with Capacity, Congestion and Stochastic Demand Considerations

  • Vedat Bayram
  • Barış Yıldız
  • M. Saleh Farham
    • Categories Second-Order Cone Programming, Stochastic Programming, Transportation Tags , , , , , , ,

    We introduce the hub network design problem with congestion, capacity, and stochastic demand considerations (HNDC), which generalizes the classical hub location problem in several directions. In particular, we extend state-of-the-art by integrating capacity acquisition decision and congestion cost effect into the problem and allowing dynamic routing for origin-destination pairs. Connecting strategic and operational level decisions, … Read more

    The SCIP Optimization Suite 8.0

  • Ksenia Bestuzheva
  • Mathieu Besançon
  • Wei-Kun Chen
  • Antonia Chmiela
  • Tim Donkiewicz
  • Jasper van Doornmalen
  • Leon Eifler
  • Oliver Gaul
  • Gerald Gamrath
  • Ambros Gleixner
  • Leona Gottwald
  • Christoph Graczyk
  • Katrin Halbig
  • Alexander Hoen
  • Christopher Hojny
  • Rolf van der Hulst
  • Thorsten Koch
  • Marco E. Lübbecke
  • Stephen J. Maher
  • Frederic Matter
  • Erik Mühmer
  • Benjamin Müller
  • Marc E. Pfetsch
  • Daniel Rehfeldt
  • Steffan Schlein
  • Franziska Schlösser
  • Felipe Serrano
  • Yuji Shinano
  • Boro Sofranac
  • Mark Turner
  • Stefan Vigerske
  • Fabian Wegscheider
  • Philipp Wellner
  • Dieter Weninger
  • Jakob Witzig
    • Categories Branch and Cut Algorithms, Integer Programming, Optimization Software and Modeling Systems 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 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type … Read more

    Freight-on-Transit for urban last-mile deliveries: A Strategic Planning Approach

  • Diego Delle Donne
  • Laurent Alfandari
  • Claudia Archetti
  • Ivana Ljubić
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Transportation Tags , , ,

    We study a delivery strategy for last-mile deliveries in urban areas which combines freight transportation with mass mobility systems with the goal of creating synergies contrasting negative externalities caused by transportation. The idea is to use the residual capacity on public transport means for moving freights within the city. In particular, the system is such … Read more

    A Column Generation Scheme for Distributionally Robust Multi-Item Newsvendor Problems

  • Shanshan Wang
  • Erick Delage
    • Categories Applications - OR and Management Sciences, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , ,

    In this paper, we study a distributionally robust multi-item newsvendor problem, where the demand distribution is unknown but specified with a general event-wise ambiguity set. Using the event-wise affine decision rules, we can obtain a conservative approximation formulation of the problem, which can typically be further reformulated as a linear program. In order to efficiently … Read more

    Network Migration Problem: A Hybrid Logic-based Benders Decomposition

  • Maryam Daryalal
  • Hamed Pouya
    • Categories Applications - OR and Management Sciences Tags , , , , ,

    Telecommunication networks frequently face technological advancements and need to upgrade their infrastructure. Adapting legacy networks to the latest technology requires synchronized technicians responsible for migrating the equipment. The goal of the network migration problem is to find an optimal plan for this process. This is a defining step in the customer acquisition of telecommunications service … Read more

    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

    Adjustable robust optimization with objective uncertainty

  • Boris Detienne
  • Henri Lefebvre
  • Enrico Malaguti
  • Michele Monaci
    • Categories Applications - OR and Management Sciences, Convex Optimization, Robust Optimization Tags , , , , ,

    In this work, we study optimization problems where some cost parameters are not known at decision time and the decision flow is modeled as a two-stage process within a robust optimization setting. We address general problems in which all constraints (including those linking the first and the second stages) are defined by convex functions and … 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

    A Chance-Constrained Two-Echelon Vehicle Routing Problem with Stochastic Demands

  • Nico Dellaert
  • Joris Kinable
  • Alexandre M. Florio
  • Natasja Sluijk
  • Tom Van Woensel
    • Categories Applications - OR and Management Sciences, Transportation Tags , , ,

    Two-echelon distribution systems are often considered in city logistics to maintain economies of scale and satisfy the emission zone requirements in the cities. In this work, we formulate the two-echelon vehicle routing problem with stochastic demands as a chance-constrained stochastic optimization problem, where the total demand of the customers in each second-echelon route should fit … Read more

    Improving Column-Generation for Vehicle Routing Problems via Random Coloring and Parallelization

  • Viswanath Nagarajan
  • Siqian Shen
  • Miao Yu
    • Categories Network Optimization, Parallel Algorithms, Transportation Tags , , , ,

    We consider a variant of the Vehicle Routing Problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation based linear-programming relaxation … Read more