Combinatorial Optimization

Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach

  • Nathan Benedetto Proença
  • Marcel K. de Carli Silva
  • Levent Tunçel
    • Categories Approximation Algorithms, Optimization Software and Modeling Systems, Semi-definite Programming

    We present experimental work on a primal-dual framework simultaneously approximating maximum cut and weighted fractional cut-covering instances. In this primal-dual framework, we solve a semidefinite programming (SDP) relaxation to either the maximum cut problem or to the weighted fractional cut-covering problem, and then independently sample a collection of cuts via the random-hyperplane technique. We then … Read more

    Finding Short Paths on Simple Polytopes

  • Alexander Black
  • Raphael Steiner
    • Categories Combinatorial Optimization, Linear Programming, Polyhedra Tags , , , , ,

    We prove that computing a shortest monotone path to the optimum of a linear program over a simple polytope is NP-hard, thus resolving a 2022 open question of De Loera, Kafer, and Sanit\`{a}. As a consequence, finding a shortest sequence of pivots to an optimal basis with the simplex method is NP-hard. In fact, we … Read more

    Enhancing the separation of rank-1 Chvátal-Gomory cuts from knapsack sets

  • Giacomo Maggiorano
  • Stefano Gualandi
  • Pasquale Avella
    • Categories 0-1 Programming, Branch and Cut Algorithms, Integer Programming Tags , , ,

    We present an exact method for separating Chvátal-Gomory cuts from binary knapsack sets, consisting of two steps: i) enumerating a finite set of possible optimal multipliers for the knapsack constraint; ii) for each candidate, adjusting optimally the remaining multipliers. We prove that ii) can be formulated as a binary knapsack problem, leading to a pseudopolynomial-time … Read more

    Pseudo-Compact Formulations and Branch-and-Cut Approaches for the Capacitated Vehicle Routing Problem with Stochastic Demands

  • Caio Tomazella
  • Pedro Munari
  • Reinaldo Morabito
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Stochastic Programming Tags , , ,

    In this paper, we address the Capacitated Vehicle Routing Problem with Stochastic Demands (CVRPSD), in which routes are planned a priori and recourse actions are performed to ensure demand fulfillment. These recourse actions are defined through policies and may include replenishment trips or demand backlogging subject to penalties. We develop the first family of pseudo-compact … Read more

    Paving and computing the set of nondominated points for the bi-objective 0/1 uncapacitated facility location problem

  • Xavier Gandibleux
  • Anthony Przybylski
    • Categories Combinatorial Optimization, Multi-Criteria Optimization Tags , , , , ,

    The paper presents a three-phase algorithm to compute the set of nondominated points for the binary version of the uncapacitated facility location problem with two objectives. The first phase constructs a paving in objective space which is a collection of boxes that covers all nondominated points. The paving procedure is a branch and bound algorithm … Read more

    A cut-based mixed integer programming formulation for the hop-constrained cheapest path problem

  • Hamidreza Validi
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , ,

    Given a simple graph G = (V, E) with edge cost c ∈ ℝ^|E|, a positive integer h, source s ∈ V and terminal t ∈ V, the hop-constrained cheapest path problem (HCCP) seeks to find an s–t path of length at most h hops with the cheapest cost. This paper proposes a cut-based mixed … Read more

    Machine-learning-enhanced strategies to generate subtour elimination constraints for the symmetric traveling salesman problem

  • FB Akcay
  • Maxence Delorme
  • Ulrich Pferschy
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    We present a machine learning (ML) component designed to enhance the well-known branch-and-cut (B&C) framework for the symmetric traveling salesman problem (TSP) in which only the subtour elimination constraints (SECs) violated by previously found integer solutions are considered. The objective of the ML component is to identify which SECs, from a pool of candidates, will … Read more

    Adaptive Subproblem Selection in Benders Decomposition for Survivable Network Design Problems

  • Tim Donkiewicz
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Network Optimization

    Scenario-based optimization problems can be solved via Benders decomposition, which separates first-stage (master problem) decisions from second-stage (subproblem) recourse actions and iteratively refines the master problem with Benders cuts. In conventional Benders decomposition, all subproblems are solved at each iteration. For problems with many scenarios, solving only a selected subset can reduce computation. We quantify … Read more

    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