0-1 Programming

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

    Solving large-scale unit-commitment problems using dual dynamic programming and open-source solvers

  • Bruno Colonetti
  • Samuel Brito
  • Erlon Finardi
  • Victor M. Zavala
  • Lucas Picarelli
    • Categories 0-1 Programming, Applications - Science and Engineering, Dynamic Programming Tags , , ,

    The astonishing dimensions and complexity of power systems render them impossible to be managed without the help of cutting-edge software. Due to a lack of scalable, reliable and well documented free and open-source solutions, system operators, regulators, and government agencies often rely on proprietary software to provide them information that ultimately will be used to … Read more

    Efficient Propagation Techniques for Handling Cyclic Symmetries in Binary Programs

  • Jasper van Doornmalen
  • Christopher Hojny
    • Categories 0-1 Programming Tags , , ,

    The presence of symmetries of binary programs typically degrade the performance of branch-and-bound solvers. In this article, we derive efficient variable fixing algorithms to discard symmetric solutions from the search space based on propagation techniques for cyclic groups. Our algorithms come with the guarantee to find all possible variable fixings that can be derived from … Read more

    The polytope of binary sequences with bounded variation

  • Christoph Buchheim
  • Maja Hügging
    • Categories 0-1 Programming, Polyhedra Tags , , ,

    We investigate the problem of optimizing a linear objective function over the set of all binary vectors of length n with bounded variation, where the latter is defined as the number of pairs of consecutive entries with different value. This problem arises naturally in many applications, e.g., in unit commitment problems or when discretizing binary … Read more

    Rank-one Boolean tensor factorization and the multilinear polytope

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories 0-1 Programming, Cutting Plane Approaches, Linear Programming Tags , , ,

    We consider the NP-hard problem of approximating a tensor with binary entries by a rank-one tensor, referred to as rank-one Boolean tensor factorization problem. We formulate this problem, in an extended space of variables, as the problem of minimizing a linear function over a highly structured multilinear set. Leveraging on our prior results regarding the … Read more

    Lower bound on size of branch-and-bound trees for solving lot-sizing problem

  • Santanu S. Dey
  • Prachi Shah
    • Categories 0-1 Programming, Integer Programming Tags , ,

    We show that there exists a family of instances of the lot-sizing problem, such that any branch-and-bound tree that solves them requires an exponential number of nodes, even in the case when the branchings are performed on general split disjunctions. ArticleDownload View PDF