Combinatorial Optimization

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

    Equity-Driven Workload Allocation for Crowdsourced Last-Mile Delivery

  • Abhay Sobhanan
  • Hadi Charkhgard
  • Iman Dayarian
    • Categories Meta Heuristics, Multi-Criteria Optimization, Transportation Tags , , , ,

    Crowdshipping, a rapidly growing approach in Last-Mile Delivery (LMD), relies on independent crowdworkers for delivery orders. Building a sustainable network of crowdshippers is essential for the survival and growth of such systems, while their participation is primarily motivated by fair pay. Additionally, the financial well-being of crowdworkers is sensitive to fair compensation, especially for those … Read more

    Local Convergence Analysis for Nonisolated Solutions to Derivative-Free Methods of Optimization

  • Dat Tran
    • Categories Approximation Algorithms, Nonlinear Optimization, Unconstrained Optimization

    This paper provides a local convergence analysis for newly developed derivative-free methods in problems of smooth nonconvex optimization. We focus here on local convergence to local minimizers, which might be nonisolated and hence more challenging for convergence analysis. The main results provide efficient conditions for local convergence to arbitrary local minimizers under the fulfillment of … Read more

    Compact Mixed Integer Programming Formulations for the Minimum Biclique Cover Problem

  • Bruno Burin
  • Hamidreza Validi
  • Bochuan Lyu
  • Illya V. Hicks
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , ,

    Given a simple graph G = (V, E) with vertex set V and edge set E, the minimum biclique cover problem seeks to cover all edges of the graph with a minimum number of bicliques (i.e., complete bipartite subgraphs). This paper proposes two compact mixed integer programming (MIP) formulations for solving the minimum biclique cover … Read more