Combinatorial Optimization

Cluster branching for vehicle routing problems

  • Joao Marcos P Silva
  • Eduardo Uchoa
  • Anand Subramanian
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , ,

    This article introduces Cluster Branching, a novel branching strategy for exact algorithms solving Vehicle Routing Problems (VRPs). While branching is crucial for the efficiency of branch-and-bound-based algorithms, existing branching types such as Edge Branching, CutSet Branching, and Ryan&Foster Branching have their limitations. The proposed branching strategy aggregates multiple edge variables into higher-level decision structures corresponding … Read more

    Interdiction of minimum spanning trees and other matroid bases

  • Noah Weninger
  • Ricardo Fukasawa
    • Categories 0-1 Programming, Dynamic Programming, Graphs and Matroids Tags , , , , , ,

    In the minimum spanning tree (MST) interdiction problem, we are given a graph \(G=(V,E)\) with edge weights, and want to find some \(X\subseteq E\) satisfying a knapsack constraint such that the MST weight in \((V,E\setminus X)\) is maximized. Since MSTs of \(G\) are the minimum weight bases in the graphic matroid of \(G\), this problem … Read more

    Computational Methods for the Household Assignment Problem

  • Ulf Friedrich
  • Lucas Moschen
  • Ralf Münnich
  • Martin Schmidt
    • Categories Applications - OR and Management Sciences, Approximation Algorithms, Integer Programming Tags , , , ,

    We consider the household assignment problem as it occurs in the geo-referencing step of spatial microsimulation models. The resulting model is a maximum weight matching problem with additional side constraints. For real-world instances such as the one for the city of Trier in Germany, the number of binary variables exceeds 10^9, and the resulting instances … Read more

    A General Framework for Sequential Batch-Testing

  • Rayen Tan
  • Alex Xu
  • Viswanath Nagarajan
    • Categories Approximation Algorithms, Combinatorial Optimization

    We consider sequential testing problems that involve a system of \(n\) stochastic components, each of which is either working or faulty with independent probability. The overall state of the system is a function of the state of its individual components, and the goal is to determine the system state by testing its components at the … Read more

    Globally Convergent Derivative-Free Methods in Nonconvex Optimization with and without Noise

  • Dat Tran
    • Categories Approximation Algorithms, Global Optimization Applications, Unconstrained Optimization

    This paper addresses the study of nonconvex derivative-free optimization problems, where only information of either smooth objective functions or their noisy approximations is available. General derivative-free methods are proposed for minimizing differentiable (not necessarily convex) functions with globally Lipschitz continuous gradients, where the accuracy of approximate gradients is interacting with stepsizes and exact gradient values. … Read more

    Efficient Project Scheduling with Autonomous Learning Opportunities

  • Alessandro Hill
  • Thomas Vossen
    • Categories Combinatorial Optimization, Scheduling

    We consider novel project scheduling problems in which the experience gained from completing selected activities can be used to accelerate subsequent activities. Given a set of potential learning opportunities, our model aims to identify the opportunities that result in a maximum reduction of the project makespan when scheduled in sequence. Accounting for the impact of … Read more

    On the integrality gap of the Complete Metric Steiner Tree Problem via a novel formulation

  • Ambrogio Maria Bernardelli
  • Eleonora Vercesi
  • Stefano Gualandi
  • Monaldo Mastrolilli
  • Luca Maria Gambardella
    • Categories Combinatorial Optimization, Graphs and Matroids, Linear Programming Tags , ,

    In this work, we study the metric Steiner Tree problem on graphs focusing on computing lower bounds for the integrality gap of the bi-directed cut (DCUT) formulation and introducing a novel formulation, the Complete Metric (CM) model, specifically designed to address the weakness of the DCUT formulation on metric instances. A key contribution of our … Read more

    Relay-Hub Network Design for Consolidation Planning Under Demand Variability

  • Onkar Anand Kulkarni
  • Mathieu Dahan
    • Categories Branch and Cut Algorithms, Supply Chain Management, Transportation Tags , , , , , ,

    Problem description: We study the problem of designing large-scale resilient relay logistics hub networks. We propose a model of Capacitated Relay Network Design under Stochastic Demand and Consolidation-Based Routing (CRND-SDCR), which aims to improve a network’s efficiency and resilience against commodity demand variability through integrating tactical decisions. Methodology: We formulate CRND-SDCR as a two-stage stochastic … Read more

    Solving the parallel processor scheduling and bin packing problems with contiguity constraints: mathematical models and computational studies

  • FB Akcay
  • Maxence Delorme
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    The parallel processor scheduling and bin packing problems with contiguity constraints are important in the field of combinatorial optimization because both problems can be used as components of effective exact decomposition approaches for several two-dimensional packing problems. In this study, we provide an extensive review of existing mathematical formulations for the two problems, together with … Read more