0-1 Programming – Optimization Online

Beyond Hand-Derived Inequalities: Decision Diagrams for Cut Generation in Binary Polynomial Optimization

Published: 2026/07/31

Margarita P Castro

0-1 Programming, Cutting Plane Approaches, Integer Programming binary polynomial optimization, cutting planes, decision diagrams

We study cutting-plane generation for binary polynomial optimization (BPO), whose feasible region is the multilinear set of a hypergraph. Strong inequalities for this set—such as two-links, flowers, and odd $\beta$-cycles—are classically hand-derived for fixed support patterns. Instead, we propose a decision-diagram (DD) approach: for any chosen support, it separates a facet-defining cut in the local … Read more

Polyhedral Bounds for Forbidden-Vertices Sets and No-Good Cut Relaxations

Published: 2026/07/02

Gustavo Angulo

(Mixed) Integer Linear Programming, 0-1 Programming, Linear Programming forbidden-vertices polytopes, no-good cuts, polyhedral complexity

We study the convex hull obtained after deleting prescribed vertices from the binary cube. The analysis separates three regimes according to the number of deleted vertices. When this number is fixed, both the original-space facet count and the linear extension complexity remain linear in the ambient dimension, up to constants depending only on the number … Read more

Advancing Branch-and-Price for Graph Coloring: New Pricing Strategies and Benchmark Results

Published: 2026/06/10

0-1 Programming, Combinatorial Optimization, Integer Programming branch-and-price, decision diagrams, exact algorithm, graph coloring problem

This paper proposes BPCOL+, an exact branch-and-price algorithm for the Graph Coloring Problem. The algorithm is both novel and highly effective, integrating enhanced pricing strategies within Zero-Suppressed Binary Decision Diagrams (ZDDs) to efficiently solve the pricing problem associated with the maximal-stable-set-based set-covering formulation. After computing upper and lower bounds at the root node using heuristic … Read more

Enhancing the separation of rank-1 Chvátal-Gomory cuts from knapsack sets

Published: 2026/04/20

0-1 Programming, Branch and Cut Algorithms, Integer Programming chvatal-gomory cuts, cutting planes, generalized assignment problem, knapsack problem

We present an exact method for separating Chvátal-Gomory cuts from binary knapsack sets, consisting of two steps: i) enumerating a finite set of possible optimal multipliers for the knapsack constraint; ii) for each candidate, adjusting optimally the remaining multipliers. We prove that ii) can be formulated as a binary knapsack problem, leading to a pseudopolynomial-time … Read more

Characterization of Knapsack Polytopes using Minimal Cover Inequalities

Published: 2026/03/03

0-1 Programming convex hull, Knapsack, Minimal cover inequality, polyhedron

In this paper, we compare the strength of alternate formulations (polyhedra) of the binary knapsack set. We introduce a specific class of knapsack sets for which we prove that the polyhedra based on their minimal cover inequalities (together with the bounds on the variables) are strictly contained inside the polyhedra defined by their continuous knapsack … Read more

Clique Probing For Mixed-Integer-Programs

Published: 2026/01/11, Updated: 2026/01/29

(Mixed) Integer Linear Programming, 0-1 Programming, Integer Programming mixed-integer programming, presolving, Probing

Probing is an important presolving technique in mixed-integer programming solvers. It selects binary variables, tentatively fixes them to 0 and 1, and performs propagation to deduce additional variable fixings, bound tightenings, substitutions, and implications. In this work, we propose clique probing instead of probing on individual variables, we select cliques, a set of binary variables … Read more

Weight reduction inequalities revisited

Published: 2025/12/18, Updated: 2026/02/03

0-1 Programming 0-1 Knapsack, convex hull, facets, knapsack polytope, Weight division inequalities

In this paper, we propose an extension of the classical weight reduction inequalities for the binary knapsack polytope for settings where the maximum-weight item in the associated pack is not unique. We derive sufficient conditions under which the extended inequalities are facet-defining and identify conditions under which they strictly dominate the original weight reduction inequalities. … Read more

A Dual Riemannian ADMM Algorithm for Low-Rank SDPs with Unit Diagonal

Published: 2025/12/04

Jie Wang

0-1 Programming, Semi-definite Programming alternating direction method of multipliers, augmented lagrangian method, Burer-Monteiro factorization, low-rank solution, manifold optimization, moment-SOS relaxation, polynomial optimization, semidefinite programming

This paper proposes a dual Riemannian alternating direction method of multipliers (ADMM) for solving low-rank semidefinite programs with unit diagonal constraints. We recast the ADMM subproblem as a Riemannian optimization problem over the oblique manifold by performing the Burer-Monteiro factorization. Global convergence of the algorithm is established assuming that the subproblem is solved to certain … Read more

Structure-Preserving Symmetry Presolving for Mixed-Binary Linear Problems

Published: 2025/11/19, Updated: 2026/03/10

(Mixed) Integer Linear Programming, 0-1 Programming Schreier-Sims table, stable set problem, symmetry handling

This paper investigates a presolving method for handling symmetries in mixed-binary programs, based on inequalities computed from so-called Schreier-Sims tables. We show that an iterative application of this method together with merging variables will produce an instance for which the symmetry group is trivial. We then prove that the problem structure can be preserved for … Read more

Projection-width as a structural parameter for discrete separable optimization

Published: 2025/11/05, Updated: 2026/02/05

Alberto Del Pia

(Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, 0-1 Programming

While several classes of integer linear optimization problems are known to be solvable in polynomial time, far fewer tractability results exist for integer nonlinear optimization. In this work, we narrow this gap by identifying a broad class of discrete nonlinear optimization problems that admit polynomial-time algorithms. Central to our approach is the notion of projection-width, … Read more