Tightening Linear Programming Relaxations with Valid Inequalities

142 concepts107 papers1 proposal

Discrete optimization problems—such as Mixed-Integer Linear Programs (MILPs)—are fundamentally difficult because of the combinatorial explosion of potential solutions. To find the global optimum without checking every single combination, modern solvers rely on a continuous shortcut: the Linear Programming (LP) relaxation. By temporarily dropping the requirement that variables must be integers, the solver can rapidly solve a continuous version of the problem to compute bounds and guide its search.

However, this shortcut has a major vulnerability. If the boundaries of the continuous relaxation are too loose, the optimal continuous solution will often land on a fractional value far away from any real integer solution. This forces the solver to split the problem into a massive, deeply nested tree of sub-problems (branch-and-bound).

The core idea of constraint strengthening is to prevent this explosion by narrowing the gap between the continuous relaxation and discrete reality. By mathematically deriving additional constraints—known as valid inequalities or cutting planes—researchers can slice away fractional regions of the search space without removing a single valid integer solution.

   Loose Relaxation            Tightened with Cuts          True Convex Hull
     /-----------\                 /-----------\              /-----------\
    /  .       .  \               /  .       .  \            /  .       .  \
   /               \             /===============\          /               \
  /    .       .    \           /    .       .    \        /    .       .    \
 /                   \         /                   \      /-----------------\
 ---------------------         ---------------------      ---------------------
 (Fractional corners          (Cuts slice away the        (The ideal, tightest
  waste solver time)           fractional corners)         possible boundaries)

The Geometry of a Cut

To understand why valid inequalities work, it helps to view them geometrically. The feasible region of an LP relaxation forms a multi-dimensional polygon called a polytope. The true integer solutions sit inside this polytope like a grid of discrete points. A naive mathematical formulation often creates a loose boundary, leaving large "empty" corners that contain fractional points but no integer points.

A valid inequality acts as a geometric blade that carves off these empty corners. The gold standard of these constraints is a facet-defining inequality. As explained by Oktay Gunluk et al. in Network design arc set with variable upper bounds, facet-defining inequalities represent the tightest possible linear boundaries for the convex hull of integer solutions.

When a solver incorporates these high-dimensional boundaries, the continuous relaxation is forced to align tightly with the discrete points. In fact, Max Klimm et al. demonstrate in Valid Cuts for the Design of Potential-based Flow Networks that sufficiently strong valid inequalities can occasionally resolve complex optimization problems entirely at the initial root node of the search tree, completely bypassing the need for expensive branch-and-bound exploration.

Replacing the Big-M Bottleneck

A classic culprit behind loose relaxations is the "Big-M" constraint. This is a modeling technique where a large constant ($M$) is used to turn a constraint on or off based on a binary decision variable (e.g., $x \le M \cdot y$). While simple to write, Big-M constraints introduce massive regions of fractional space, severely weakening the LP relaxation.

To fix this, researchers design alternative structural formulations that inherently provide tighter bounds:

  • Perspective Relaxations: Instead of relying on a flat Big-M boundary, perspective relaxations exploit the underlying non-linear or convex structures of a problem. Alper Atamtürk et al. demonstrate this in Safe screening rules for L0-regression from Perspective Relaxations, using perspective relaxations to mathematically guarantee when variables can be excluded. This structural tightness allows them to eliminate an average of 76% of variables before the primary optimization even begins.
  • Partitioned Formulations: In neural network verification, where piecewise-linear functions like ReLUs introduce combinatorial complexity, standard Big-M encodings slow down solvers. In Partition-Based Formulations for Mixed-Integer Optimization of Trained ReLU Neural Networks, Calvin Tsay et al. show that grouping node inputs into structured partitions yields significantly sharper bounds, bridging the gap between loose formulations and the computationally expensive convex hull.

Lifting and Combinatorial Covers

Systematically generating valid inequalities often requires a process called lifting. This technique takes a valid inequality derived from a simplified, lower-dimensional version of a problem (such as a single knapsack constraint) and mathematically modifies its coefficients so that it becomes valid and highly restrictive for the full, higher-dimensional problem.

Siddharth Prasad explores this mechanism in New Sequence-Independent Lifting Techniques for Cover Inequalities and When They Induce Facets, introducing piecewise-constant lifting functions. The author demonstrates that these step-function approaches strictly dominate traditional linear slopes, providing tighter bounds that eliminate larger swathes of the fractional search space.

Similarly, Santanu Dey et al. in Solving Sparse Separable Bilinear Programs Using Lifted Bilinear Cover Inequalities introduce lifted bilinear cover inequalities. By injecting these structural cuts at the very beginning of the optimization process, the authors significantly accelerate how fast a solver can close the "optimality gap"—the distance between the best known integer solution and the continuous relaxation bound.

Dominance and Disjunctive Logic

While traditional cutting planes focus on cutting off fractional solutions, a parallel strategy targets the elimination of sub-optimal integer solutions.

In Dominance inequalities for scheduling around an unrestrictive common due date, Anne-Elisabeth Falq et al. introduce dominance inequalities. Instead of looking at the continuous relaxation, these constraints use the algebraic structure of the problem to prove that certain integer configurations are mathematically inferior to their neighbors. By adding these inequalities, the solver can instantly discard massive branches of the search tree without having to evaluate them exhaustively.

       [Standard Cut]                           [Dominance Cut]
 Slices away fractional space             Slices away integer space
that lacks discrete solutions.           proven to be sub-optimal.

       /-----------\                            /-----------\
      /  .       .  \                          /  .       x  \
     /===============\                        /           x   \
    /    .       .    \                      /    .       x    \
   /                   \                    /             x     \
   ---------------------                    ---------------------
                                            (Discarded branches)

When problems involve logical "either-or" conditions, solvers can leverage disjunctive cuts. These cuts translate discrete logical choices directly into linear approximations. As shown by Jan Kronqvist et al. in A disjunctive cut strengthening technique for convex MINLP, embedding disjunctive integer logic directly into linear approximations strictly dominates standard cutting techniques, reducing the number of iterations required to solve complex non-linear optimization problems by nearly three-fold.

By understanding the geometric and algebraic structures that link continuous relaxations to discrete choices, researchers can continue to design cuts that transform intractable combinatorial explosions into highly efficient, structured searches.

Key Foundational Work

A branch and cut algorithm for the VRP with satellite facilities (1998) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_valid_inequalities_25d8054b,
  title = {valid inequalities},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/valid-inequalities/rdr_25d8054bf2ea44ce8cdeda1e9fd58c2b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-13},
}

This exact version (version 1, frozen text):

@misc{lacuna_valid_inequalities_25d8054b_v1,
  title = {valid inequalities},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/valid-inequalities/rdr_25d8054bf2ea44ce8cdeda1e9fd58c2b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-13},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake