Combinatorial Optimization

Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching

  • Selin Bayramoglu
  • George L. Nemhauser
  • Nikolaos Sahinidis
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms Tags , ,

    Machine learning is increasingly used to improve decisions within branch-and-bound algorithms for mixed-integer programming. Many existing approaches rely on deep learning, which often requires very large training datasets and substantial computational resources for both training and deployment, typically with GPU parallelization. In this work, we take a different path by developing interpretable models that are … Read more

    On vehicle routing problems with stochastic demands — Scenario-optimal recourse policies

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Branch and Cut Algorithms, Stochastic Programming, Transportation Tags , ,

    Two-Stage Vehicle Routing Problems with Stochastic Demands (VRPSDs) form a class of stochastic combinatorial optimization problems where routes are planned in advance, demands are revealed upon vehicle arrival, and recourse actions are triggered whenever capacity is exceeded. Following recent works, we consider VRPSDs where demands are given by an empirical probability distribution of scenarios. Existing … Read more

    New Proofs of Exact LP Reformulations for Binary Polynomial Optimization with Bounded Treewidth

  • Sourabh Kumar Choudhary
  • Santanu S. Dey
  • Nikolaos Sahinidis
    • Categories Combinatorial Optimization Tags , ,

    In this work, we revisit binary polynomial optimization (BPO) problems with limited treewidth of the associated graph. We provide alternate proofs of the exactness of a reformulated linear program (LP) with O(n.2^d) variables, n being the number of variables and d being the treewidth of the associated graph. The first proof relies on expressing any … Read more

    Hardness of some optimization problems over correlation polyhedra

  • Alberto Caprara
  • Fabio Furini
  • Claudio Gentile
  • Leo Liberti
  • Andrea Lodi
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra Tags , , ,

    We prove the NP-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the n×n rank-one matrices over {0, 1}. The problems are: membership, rank of the decomposition, and a “relaxed rank” obtained from relaxing the zero-norm expression for the rank to an ℓ1 norm. … Read more

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