Combinatorial Optimization

Advancing Branch-and-Price for Graph Coloring: New Pricing Strategies and Benchmark Results

  • Mingming Zheng
  • Roberto Baldacci
  • Fabio Furini
  • Qinghua Wu
    • Categories 0-1 Programming, Combinatorial Optimization, Integer Programming Tags , , ,

    This paper proposes BPCOL+, an exact branch-and-price algorithm for the Graph Coloring Problem. The algorithm is both novel and highly effective, integrating enhanced pricing strategies within Zero-Suppressed Binary Decision Diagrams (ZDDs) to efficiently solve the pricing problem associated with the maximal-stable-set-based set-covering formulation. After computing upper and lower bounds at the root node using heuristic … Read more

    Exact Approaches for the Maximum Mortality Rate Clique Problem

  • Parisa Vaghfi Mohebbi
  • Yajun Lu
  • Balabhaskar Balasundaram
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Branch and Cut Algorithms Tags , , ,

    This paper develops exact solution methods for the maximum mortality rate clique problem, which aims to identify a cluster of diseases in a comorbidity graph associated with the highest mortality rate among patients whose healthcare encounters are recorded in electronic health records. We establish the NP-hardness of the problem and propose two mixed-integer linear programming … Read more

    Objective Domain Reduction for Enhancing Solver Performance on Challenging Integer Programs

  • Aadya Bhattarai
  • Lagnajita Basu
  • Tapas Das
  • Kimia Keshanian
  • Hadi Charkhgard
    • Categories Combinatorial Optimization, Integer Programming, Transportation Tags , , , ,

    In this study, we explore how the domain of objective function values for challenging integer programs can be reduced and whether such a reduction can improve the solution process. Our work is motivated by binary search, a technique that efficiently narrows a search space by repeatedly halving it through feasibility checks. Building on this idea, … Read more

    Prophets in Parallel: Dynamic Cut Minimization in Series-Parallel Graphs

  • William Frendreiss
  • Alejandro Toriello
    • Categories Combinatorial Optimization, Dynamic Programming Tags , , ,

    We introduce a sequential version of the minimum $s$-$t$ cut problem, defined by a directed graph with source $s$ and sink $t$, and nonnegative random variables for each arc representing arc weights. We start with a working set $S = \{s\}$ and observe weight realizations for outgoing arcs from $S$ only. We choose to either … Read more

    Convex Hulls of Binary Reflected Gray Code Intervals

  • Gustavo Angulo
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Polyhedra Tags , ,

    The binary reflected Gray code orders the vertices of the unit hypercube along a Hamiltonian path in which consecutive vertices differ in exactly one coordinate. While Gray codes have been extensively studied from a combinatorial perspective, much less is known about the polyhedral structure of convex hulls of contiguous subpaths of this order. This paper … Read more

    Exact Methods for Solving k-Delete Recoverable Robust 0–1 Problems Under Budgeted Uncertainty

  • Yasmine Beck
  • Christina Büsing
  • Ivana Ljubić
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Robust Optimization

    We study the k-delete recoverable robust 0–1 problem in which a decision-maker solves a combinatorial optimization problem subject to objective uncertainty. The model follows a two-stage robust setup. The decision-maker first commits to an initial plan and may then revoke up to k components of this decision after the uncertainty is revealed. The underlying uncertainty … Read more

    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