A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs
ArticleDownload View PDF
0-1 Programming
Recognition of Facets for Knapsack Polytope is DP-complete
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
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
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
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
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
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
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
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
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