Combinatorial Optimization

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 a mixed-integer nonlinear programming (MINLP) approach for the classical Heilbronn triangle problem, demonstrating the capability of modern global optimization solvers to tackle challenging combinatorial geometry problems. A symmetry-breaking strategy based on boundary structure yields a substantially stronger model: for n=9, we compute an epsilon-globally optimal point in 15 minutes on a standard desktop … 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
  • Kristina Rolsing
    • 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

    Optimization over Trained Neural Networks: Going Large with Gradient-Based Algorithms

  • Jiatai Tong
  • Yilin Zhu
  • Thiago Serra
  • Samuel Burer
    • Categories (Mixed) Integer Linear Programming, Meta Heuristics, Polyhedra

    When optimizing a nonlinear objective, one can employ a neural network as a surrogate for the nonlinear function. However, the resulting optimization model can be time-consuming to solve globally with exact methods. As a result, local search that exploits the neural-network structure has been employed to find good solutions within a reasonable time limit. For … Read more