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 , , , ,

    We call an optimization problem an optimization problem with controllable uncertainty if a) it contains uncertain input data and b) prior to deciding the optimization variables, the optimizer can for a certain cost reduce the scenario set of this uncertain data. In particular, we are interested in situations where each uncertain parameter is a priori … 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

    Heuristic Approaches for Scheduling in Parallel Machine Environments

  • Kyriakos Bitsis
  • Konstantinos Kaparis
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Meta Heuristics Tags , ,

    Efficient and effective scheduling is crucial for ensuring the productivity and competitiveness of production lines, contributing significantly to organizational sustainability. This study addresses the scheduling challenges faced by a UK-based steel reinforcement manufacturer. We propose a heuristic algorithm to tackle a multistage flexible flow shop scheduling problem, where each stage consists of parallel unrelated machines. … 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

    An Extension of the Bertsimas & Sim Result for Discrete, Linear, and Γ-Robust Min-Max Problems

  • Yasmine Beck
  • Ivana Ljubić
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Robust Optimization Tags , , , ,

    Due to their nested structure, bilevel problems are intrinsically hard to solve – even if all variables are continuous and all parameters of the problem are exactly known. In this paper, we study mixed-integer linear bilevel problems with lower-level objective uncertainty, which we address using the notion of Γ-robustness. We provide an extension of the … 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