0-1 Programming

Recycling Valid Inequalities for Robust Combinatorial Optimization with Budget Uncertainty

  • Christina Büsing
  • Timo Gersing
  • Arie M.C.A. Koster
    • Categories 0-1 Programming, Polyhedra, Robust Optimization Tags , , , ,

    Robust combinatorial optimization with budget uncertainty is one of the most popular approaches for integrating uncertainty into optimization problems. The existence of a compact reformulation for (mixed-integer) linear programs and positive complexity results give the impression that these problems are relatively easy to solve. However, the practical performance of the reformulation is quite poor when … Read more

    On solving the MAX-SAT using sum of squares

  • Lennart Sinjorgo
  • Renata Sotirov
    • Categories 0-1 Programming, Branch and Cut Algorithms, Semi-definite Programming Tags , , , ,

    We consider semidefinite programming (SDP) approaches for solving the maximum satisfiabilityproblem (MAX-SAT) and the weighted partial MAX-SAT. It is widely known that SDP is well-suitedto approximate the (MAX-)2-SAT. Our work shows the potential of SDP also for other satisfiabilityproblems, by being competitive with some of the best solvers in the yearly MAX-SAT competition.Our solver combines … Read more

    Semi-Infinite Generalized Disjunctive and Mixed Integer Convex Programs with(out) Uncertainty

  • Manish Bansal
    • Categories 0-1 Programming, Convex Optimization, Semi-infinite Programming

    In this paper, we introduce semi-infinite generalized disjunctive programs that are defined by logical propositions along with disjunctions of sets of logical equations and infinite number of algebraic inequalities. We denote these programs by SIGDPs. For SIGDPs with linear and convex inequalities, we present new reformulations: semi-infinite mixed-binary/disjunctive linear programs and semi-infinite mixed-binary/disjunctive convex programs, … Read more

    Recognition of Facets for Knapsack Polytope is DP-complete

  • Haoran Zhu
    • Categories 0-1 Programming, Integer Programming Tags , , ,

    DP  is a complexity class that is the class of all languages that are the intersection of a language in NP and a language in co-NP, as coined by Papadimitriou and Yannakakis. In this paper, we will establish that, recognizing a facet for the knapsack polytope is DP-complete, as conjectured by Hartvigsen and Zemel in … Read more

    The Largest Unsolved QAP Instance Tai256c Can Be Converted into A 256-dimensional Simple BQOP with A Single Cardinality Constraint

  • Koichi Fujii
  • Sunyoung Kim
  • Masakazu Kojima
  • Hans D Mittelmann
  • Yuji Shinano
    • Categories 0-1 Programming, Branch and Cut Algorithms, Semi-definite Programming Tags , , , , ,

    Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB; a 1.48\% gap remains between the best known feasible objective value and lower bound of the unknown optimal value. This paper shows that the instance can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which … Read more

    A binary linear programming approach for supporting administrative territorial consolidation

  • Radu Buzatu
  • Igor Mandric
    • Categories 0-1 Programming, Combinatorial Optimization, Linear Programming Tags , , ,

    The objective of this paper is to develop a scalable binary linear programming model for finding the optimal aggregation of communes into spatially contiguous administrative territorial units (ATUs) constrained on certain balancing criteria. The requirement for the ATUs to be contiguous represents the main computational bottleneck and, therefore, it prevents one from using such models … Read more

    Revisiting local branching with a machine learning lens

  • Defeng Liu
  • Matteo Fischetti
  • Andrea Lodi
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Integer Programming Tags , ,

    Finding high-quality solutions to mixed-integer linear programming problems (MILPs) is of great importance for many practical applications. In this respect, the refinement heuristic local branching (LB) has been proposed to produce improving solutions and has been highly influential for the development of local search methods in MILP. The algorithm iteratively explores a sequence of solution … Read more

    Relaxations and Cutting Planes for Linear Programs with Complementarity Constraints

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

    We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based on identifying vertex covers of the conflict graph of the instance and generalizes the extended reformulation-linearization technique of Nguyen, Richard, and Tawarmalani to instances with general complementarity conditions between variables. We demonstrate … Read more

    Using Multiple Reference Vectors and Objective Scaling in the Feasibility Pump

  • Timo Berthold
  • Gioni Mexi
  • Domenico Salvagnin
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming Tags ,

    The Feasibility Pump (FP) is one of the best-known primal heuristics for mixed-integer programming (MIP): more than 15 papers suggested various modifications of all of its steps. So far, no variant considered information across multiple iterations, but all instead maintained the principle to optimize towards a single reference integer point. In this paper, we evaluate … Read more