Combinatorial Optimization

DeLuxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods

  • Yu Yang
    • Categories Branch and Cut Algorithms, Integer Programming, Transportation

    In this paper, we propose an innovative variable fixing strategy called deep Lagrangian underestimate fixing (DeLuxing). It is a highly effective approach for removing unnecessary variables in column-generation (CG)-based exact methods used to solve challenging discrete optimization problems commonly encountered in various industries, including vehicle routing problems (VRPs). DeLuxing employs a novel linear programming (LP) … Read more

    Optimal Multi-Agent Pickup and Delivery Using Branch-and-Cut-and-Price

  • Edward Lam
    • Categories Branch and Cut Algorithms, Integer Programming, Transportation

    Given a set of agents and a set of pickup-delivery requests located on a two-dimensional map, the Multi-Agent Pickup and Delivery problem assigns the requests to the agents such that every agent moves from its start location to the locations of its assigned requests and finally to its end location without colliding into any other … Read more

    Robust Optimization Under Controllable Uncertainty

  • Eva Ley
  • Rebecca Marx
  • Maximilian Merkert
  • Tim Niemann
  • Sebastian Stiller
    • Categories Combinatorial Optimization, Robust Optimization Tags , , , , , ,

    Applications for optimization with uncertain data in practice often feature a possibility to reduce the uncertainty at a given query cost, e.g., by conducting measurements, surveys, or paying a third party in advance to limit the deviations. To model this type of applications we introduce the concept of optimization problems under controllable uncertainty (OCU). For … Read more

    Delay-Resistant Robust Vehicle Routing with Heterogeneous Time Windows

  • Lukas Schürmann
  • Tim Niemann
  • Petra Mutzel
  • Andreas M. Tillmann
  • Sebastian Stiller
    • Categories Combinatorial Optimization, Integer Programming, Transportation Tags , , ,

    We consider a robust variant of the vehicle routing problem with heterogeneous time windows (RVRP-HTW) with a focus on delay-resistant solutions. Here, customers have different availability time windows for every vehicle and must be provided with a preferably tight appointment window for the planned service. Different vehicles are a possibility to model different days on … Read more

    Structured Pruning of Neural Networks for Constraints Learning

  • Matteo Cacciola
  • Andrea Lodi
  • Antonio Frangioni
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Optimization in Data Science Tags , ,

    In recent years, the integration of Machine Learning (ML) models with Operation Research (OR) tools has gained popularity across diverse applications, including cancer treatment, algorithmic configuration, and chemical process optimization. In this domain, the combination of ML and OR often relies on representing the ML model output using Mixed Integer Programming (MIP) formulations. Numerous studies … Read more

    Recycling Valid Inequalities for Robust Combinatorial Optimization with Budget Uncertainty

  • Christina Büsing
  • Timo Gersing
  • Arie M.C.A. Koster
    • Categories 0-1 Programming, Polyhedra, Robust Optimization Tags , , , ,

    Robust combinatorial optimization with budget uncertainty is one of the most popular approaches for integrating uncertainty into optimization problems. The existence of a compact reformulation for (mixed-integer) linear programs and positive complexity results give the impression that these problems are relatively easy to solve. However, the practical performance of the reformulation is quite poor when … Read more

    Mind the \(\tilde{O}\): asymptotically better, but still impractical, quantum distributed algorithms

  • David E. Bernal Neira
    • Categories Combinatorial Optimization, Graphs and Matroids Tags , , , ,

    \(\) The CONGEST and CONGEST-CLIQUE models have been carefully studied to represent situations where the communication bandwidth between processors in a network is severely limited. Messages of only \( O(log(n)) \) bits of information each may be sent between processors in each round. The quantum versions of these models allow the processors instead to communicate … Read more

    The set partitioning problem in a quantum context

  • Rafael Farias Cacao
  • Lucas Ramos Cardoso Tinoco Cortez
  • Jackson Forner
  • Hamidreza Validi
  • Ismael de Farias
  • Illya V. Hicks
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Integer Programming

    The set partitioning problem and its decision variant (i.e., the exact cover problem) are combinatorial optimization problems that were historically crucial in the quantum optimization community. This problem is also employed in the main problem of the branch-and-price approach in many real-world optimization problems, including, but not limited to, redistricting and scheduling. Motivated by recent … Read more

    On Integrality in Semidefinite Programming for Discrete Optimization

  • Frank de Meijer
  • Renata Sotirov
    • Categories Combinatorial Optimization, Quadratic Programming, Semi-definite Programming Tags , , , ,

    It is well-known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a … Read more