0-1 Programming

Inductive Linearization for Binary Quadratic Programs with Linear Constraints: A Computational Study

  • Sven Mallach
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Quadratic Programming Tags , , ,

    The computational performance of inductive linearizations for binary quadratic programs in combination with a mixed-integer programming solver is investigated for several combinatorial optimization problems and established benchmark instances. Apparently, a few of these are solved to optimality for the first time. Citationpreprint (no internal series / number): University of Bonn, Germany June 11, 2021ArticleDownload View … Read more

    Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets

  • Alberto Del Pia
  • Jeff Linderoth
  • Haoran Zhu
    • Categories 0-1 Programming, Cutting Plane Approaches Tags , ,

    We propose a method to generate cutting-planes from multiple covers of knapsack constraints. The covers may come from different knapsack inequalities if the weights in the inequalities form a totally-ordered set. Thus, we introduce and study the structure of a totally-ordered multiple knapsack set. The valid multi-cover inequalities we derive for its convex hull have … Read more

    Multilinear Sets with Two Monomials and Cardinality Constraints

  • Rui Chen
  • Sanjeeb Dash
  • Oktay Gunluk
    • Categories 0-1 Programming, Cutting Plane Approaches Tags , ,

    Binary polynomial optimization is equivalent to the problem of minimizing a linear function over the intersection of the multilinear set with a polyhedron. Many families of valid inequalities for the multilinear set are available in the literature, though giving a polyhedral characterization of the convex hull is not tractable in general as binary polynomial optimization … Read more

    Total Coloring and Total Matching: Polyhedra and Facets

  • Luca Ferrarini
  • Stefano Gualandi
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Cutting Plane Approaches Tags , , ,

    A total coloring of a graph G = (V, E) is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the end-points and the edge itself receive different colors. Any valid total coloring induces a partition of the … Read more

    Retail Store Layout Optimization for Maximum Product Visibility

  • Evren Gul
  • Alvin Lim
  • Jiefeng Xu
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Facility Planning and Design

    It is well-established that increased product visibility to shoppers leads to higher sales for retailers. In this study, we propose an optimization methodology which assigns product categories and subcategories to store locations and sublocations to maximize the overall visibility of products to shoppers. The methodology is hierarchically developed to meet strategic and tactical layout planning … Read more

    Integer Programming Methods for Solving Binary Interdiction Games

  • Jose L. Walteros
  • Ningji Wei
    • Categories 0-1 Programming Tags , , , ,

    This paper studies a general class of interdiction problems in which the solution space of both the leader and follower are characterized by two discrete sets denoted the leader’s strategy set and the follower’s structure set. In this setting, the interaction between any strategy-structure pair is assumed to be binary, in the sense that the … Read more

    SOS-SDP: an Exact Solver for Minimum Sum-of-Squares Clustering

  • Veronica Piccialli
  • Antonio M. Sudoso
  • Angelika Wiegele
    • Categories 0-1 Programming, Quadratic Programming, Semi-definite Programming

    The minimum sum-of-squares clustering problem (MSSC) consists in partitioning n observations into k clusters in order to minimize the sum of squared distances from the points to the centroid of their cluster. In this paper, we propose an exact algorithm for the MSSC problem based on the branch-and-bound technique. The lower bound is computed by … Read more

    Lower Bounds on the Size of General Branch-and-Bound Trees

  • Santanu S. Dey
  • Yatharth Dubey
  • Marco Molinaro
    • Categories 0-1 Programming, Branch and Cut Algorithms, Global Optimization Theory Tags , ,

    A \emph{general branch-and-bound tree} is a branch-and-bound tree which is allowed to use general disjunctions of the form $\pi^{\top} x \leq \pi_0 \,\vee\, \pi^{\top}x \geq \pi_0 + 1$, where $\pi$ is an integer vector and $\pi_0$ is an integer scalar, to create child nodes. We construct a packing instance, a set covering instance, and a … Read more

    Set characterizations and convex extensions for geometric convex-hull proofs

  • Andreas Bärmann
  • Oskar Schneider
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Polyhedra Tags , , , ,

    In the present work, we consider Zuckerberg’s method for geometric convex-hull proofs introduced in [Geometric proofs for convex hull defining formulations, Operations Research Letters 44(5), 625–629 (2016)]. It has only been scarcely adopted in the literature so far, despite the great flexibility in designing algorithmic proofs for the completeness of polyhedral descriptions that it offers. … Read more

    Worst-case analysis of clique MIPs

  • Austin Buchanan
  • Jose L. Walteros
  • Mohammad Javad Naderi
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Combinatorial Optimization

    The usual integer programming formulation for the maximum clique problem has several undesirable properties, including a weak LP relaxation, a quadratic number of constraints and nonzeros when applied to sparse graphs, and poor guarantees on the number of branch-and-bound nodes needed to solve it. With this as motivation, we propose new mixed integer programs (MIPs) … Read more