Combinatorial Optimization

Finding Minimal Discretizations in Dynamic Discretization Discovery for Continuous-Time Service Network Design

  • Tom Wüllner
  • Alexander Helber
    • Categories Combinatorial Optimization, Network Optimization, Transportation Tags , , ,

    The dynamic discretization discovery framework is a powerful tool for solving network design problems with a temporal component by iteratively refining a time-discretized model. Existing approaches refine the time discretization in ways that guarantee eventual termination. However, refinement choices are not unique, and better choices can yield smaller and easier-to-solve time-discretized models. We pose the … Read more

    From Computational Certification to Exact Coordinates: Heilbronn’s Triangle Problem on the Unit Square Using Mixed-Integer Optimization

  • Nathan Sudermann-Merx
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Integer Programming Tags , , , ,

    We develop an optimize-then-refine framework for the classical Heilbronn triangle problem that integrates global mixed-integer nonlinear programming with exact symbolic computation. A novel symmetry-breaking strategy, together with the exploitation of structural properties of determinants, yields a substantially stronger optimization model: for n=9, the problem can be solved to certified global optimality in 15 minutes on … Read more

    Branch-and-Cut for Mixed-Integer Linear Decision-Dependent Robust Optimization

  • Henri Lefebvre
  • Martin Schmidt
  • Simon Stevens
  • Johannes Thürauf
    • Categories Bilevel Optimization, Branch and Cut Algorithms, Robust Optimization Tags , , , , ,

    Decision-dependent robust optimization (DDRO) problems are usually tackled by reformulating them using a strong-duality theorem for the uncertainty set model. If the uncertainty set is, however, described by a mixed-integer linear model, dualization techniques cannot be applied and the literature on solution methods is very scarce. In this paper, we exploit the equivalence of DDRO … Read more

    Modeling Binary Relations in Piecewise-Linear Approximations

  • Kristin Braun
  • Robert Burlacu
  • Tobias Kuen
  • kristinarolsing
    • Categories Combinatorial Optimization, Global Optimization Theory, Nonlinear Optimization Tags , , , , ,

    Over the last decades, using piecewise-linear mixed-integer relaxations of nonlinear expressions has become a strong alternative to spatial branching for solving mixed-integer nonlinear programs. Since these relaxations give rise to large numbers of binary variables that encode interval selections, strengthening them is crucial. We investigate how to exploit the resulting combinatorial structure by integrating cutting-plane … Read more

    Dantzig-Wolfe and Arc-Flow Reformulations: A Systematic Comparison

  • Daniel Yamin
  • Willem-Jan van Hoeve
  • Ted K. Ralphs
    • Categories Combinatorial Optimization, Integer Programming

    Dantzig-Wolfe reformulation is a widely used technique for obtaining stronger relaxations in the context of branch-and-bound methods for solving integer optimization problems. Arc-Flow reformulations are a lesser known technique related to dynamic programming that has experienced a resurgence as result of the recent popularization of decision diagrams as a tool for solving integer programs. Although … Read more

    The colored knapsack problem: structural properties and exact algorithms

  • Fabio Ciccarelli
  • Alexander Helber
  • Erik Mühmer
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Dynamic Programming Tags , , , ,

    We introduce and study a novel generalization of the classical Knapsack Problem (KP), called the Colored Knapsack Problem (CKP). In this problem, the items are partitioned into classes of colors and the packed items need to be ordered such that no consecutive items are of the same color. We establish that the problem is weakly … Read more

    Exact and Heuristic Methods for Gamma-Robust Min-Max Problems

  • Yasmine Beck
    • Categories Bilevel Optimization, Combinatorial Optimization, Robust Optimization Tags , , , ,

    Bilevel optimization is a powerful tool for modeling hierarchical decision-making processes, which arise in various real-world applications. Due to their nested structure, however, bilevel problems are intrinsically hard to solve—even if all variables are continuous and all parameters of the problem are exactly known. Further challenges arise if mixed-integer aspects and problems under uncertainty are … Read more

    A Structural Equivalence of Symmetric TSP to a Constrained Group Steiner Tree Problem

  • Yılmaz Arslanoğlu
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms Tags , , , ,

    We present a brief structural equivalence between the symmetric TSP and a constrained Group Steiner Tree Problem (cGSTP) defined on a simplicial incidence graph. Given the complete weighted graph on the city set V, we form the bipartite incidence graph between triangles and edges. Selecting an admissible, disk-like set of triangles induces a unique boundary … Read more

    Inverse Optimization Without Inverse Optimization: Direct Solution Prediction with Transformer Models

  • Macarena Navarro
  • Willem-Jan van Hoeve
  • Karan Singh
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    We present an end-to-end framework for generating solutions to combinatorial optimization problems with unknown components using transformer-based sequence-to-sequence neural networks. Our framework learns directly from past solutions and incorporates the known components, such as hard constraints, via a constraint reasoning module, yielding a constrained learning scheme. The trained model generates new solutions that are structurally … Read more

    A first approximation algorithm for the Bin Packing Problem with Setups

  • Fabio Ciccarelli
  • Roberto Baldacci
  • Stefano Coniglio
  • Valerio Dose
  • Fabio Furini
    • Categories Approximation Algorithms, Combinatorial Optimization

    We study constant-factor approximation algorithms for the Bin Packing Problem with Setups (BPPS). First, we show that adaptations of classical BPP heuristics can have arbitrarily poor worst-case performance on BPPS instances. Then, we propose a two-phase heuristic for the BPPS that applies an α-approximation algorithm for the BPP to the items of each class and … Read more