Combinatorial Optimization

Robust combinatorial optimization problems with knapsack constraints under interdiction uncertainty

  • Alejandro Crema
    • Categories Approximation Algorithms, Combinatorial Optimization, Robust Optimization Tags , , , ,

    We present an algorithm for finding near-optimal solutions to robust combinatorial optimization problems with knapsack constraints under interdiction uncertainty. We incorporate a heuristic for generating feasible solutions in a standard row generation approach. Experimental results are presented for set covering, simple plant location, and min-knapsack problems under a discrete-budgeted interdiction uncertainty set introduced in this … Read more

    Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty

  • Jérémy Omer
  • Michael Poss
    • Categories Combinatorial Optimization, Robust Optimization Tags , , ,

    Given a nominal combinatorial optimization problem, we consider a robust two-stages variant with polyhedral cost uncertainty, called Decision-Dependent Information Discovery (DDID). In the first stage, DDID selects a subset of uncertain cost coefficients to be observed, and in the second-stage, DDID selects a solution to the nominal problem, where the remaining cost coefficients are still … Read more

    Minimum-Peak-Cost Flows Over Time

  • Mariia Anapolska
  • Christina Büsing
  • Felix Engelhardt
  • Timo Gersing
  • Sabrina Schmitz
  • Sophia Wrede
    • Categories Combinatorial Optimization, Network Optimization Tags , , , ,

    Peak cost is a novel objective for flows over time that describes the amount of workforce necessary to run a system. We focus on minimising peak costs in the context of maximum temporally repeated flows and formulate the corresponding MPC-MTRF problem. First, we discuss the limitations that emerge when restricting the solution space to integral … Read more

    Cover-based inequalities for the single-source capacitated facility location problem with customer preferences

  • Christina Büsing
  • Markus Leitner
  • Sophia Wrede
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    The single-source capacitated facility location problem with customer preferences (SSCFLPCP) is known to be strongly NP-hard. Computational tests imply that state-of-the-art solvers struggle with computing exact solutions. In this paper, we contribute two novel preprocessing methods which reduce the size of the considered integer programming formulation, and introduce sets of valid inequalities which decrease the … Read more

    Bounding the number and the diameter of optimal compact Black-majority districts

  • Samuel Kroger
  • Hamidreza Validi
  • Illya V. Hicks
  • Tyler Perini
    • Categories Applications - OR and Management Sciences, Branch and Cut Algorithms, Combinatorial Optimization Tags , , ,

    Section 2 of the Voting Rights Act (VRA) prohibits voting practices that minimize or cancel out minority voting strength. While this section provides no clear framework for avoiding minority vote dilution and creating minority-majority districts, the Supreme Court proposed the Gingles test in the 1986 case Thornberg v Gingles. The Gingles test provides three conditions … Read more

    The Rectangular Spiral or the n_1 × n_2 × · · · × n_k Points Problem

  • Marco Ripà
    • Categories Bound-constrained Optimization, Combinatorial Optimization, Graphs and Matroids Tags , , , , , , ,

    A generalization of Ripà’s square spiral solution for the n × n × ··· × n Points Upper Bound Problem. Additionally, we provide a non-trivial lower bound for the k-dimensional n_1 × n_2 × ··· × n_k Points Problem. In this way, we can build a range in which, with certainty, all the best possible … Read more

    A Row-wise Algorithm for Graph Realization

  • Rolf van der Hulst
  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Graphs and Matroids, Network Optimization Tags , , , , ,

    Given a \(\{0,1\}\)-matrix \(M\), the graph realization problem for \(M\) asks if there exists a spanning forest such that the columns of \(M\) are incidence vectors of paths in the forest. The problem is closely related to the recognition of network matrices, which are a large subclass of totally unimodular matrices and have many applications … Read more

    Application of the Lovász-Schrijver Operator to Compact Stable Set Integer Programs

  • Federico Battista
  • Fabrizio Rossi
  • Stefano Smriglio
    • Categories 0-1 Programming, Combinatorial Optimization, Semi-definite Programming Tags , ,

    The Lov\’asz theta function $\theta(G)$ provides a very good upper bound on the stability number of a graph $G$. It can be computed in polynomial time by solving a semidefinite program (SDP), which also turns out to be fairly tractable in practice. Consequently, $\theta(G)$ achieves a hard-to-beat trade-off between computational effort and strength of the … Read more

    Spatial branching for a special class of convex MIQO problems

  • Pietro Belotti
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms Tags , ,

    In the branch-and-bound algorithm, branching is the key step to deal with the nonconvexity of the problem. For Mixed Integer Linear Optimization (MILO) problems and, in general, Mixed Integer Nonlinear Optimization (MINLO) problems whose continuous relaxation is convex, branching on integer and binary variables suffices, because fixing all integer variables yields a convex relaxation. General, … Read more

    A Multi-Reference Relaxation Enforced Neighborhood Search Heuristic in SCIP

  • Suresh Bolusani
  • Gioni Mexi
  • Mathieu Besançon
  • Mark Turner
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Optimization Software and Modeling Systems Tags , , ,

    This paper proposes and evaluates a Multi-Reference Relaxation Enforced Neighborhood Search (MRENS) heuristic within the SCIP solver. This study marks the first integration and evaluation of MRENS in a full-fledged MILP solver, specifically coupled with the recently-introduced Lagromory separator for generating multiple reference solutions. Computational experiments on the MIPLIB 2017 benchmark set show that MRENS, … Read more