Module lift_project 

Lift-and-Project Cuts for 0-1 Mixed-Integer Programming

Implements the Balas-Ceria-Cornuéjols (BCC, 1993) lift-and-project procedure for generating strong cutting planes from LP relaxation solutions.

Theory

Given a 0-1 MIP with LP relaxation solution x̄ ∉ {0,1}^n, the lift-and-project procedure generates a valid inequality π·x ≥ π₀ that:

• Is violated at x̄ (i.e., π·x̄ < π₀)
• Is satisfied at all feasible 0-1 integer solutions

The cut exploits the disjunction x_j = 0 OR x_j = 1 for a fractional variable j. By dualising the LP restricted to each branch and combining via a convex multiplier λ = x̄_j, we obtain a cut that is valid for the convex hull of feasible integer points.

Algorithm (per variable j, per constraint row i)

The BCC formula for a constraint row i with a[i][j] ≠ 0:

Define:

• f_j = x̄_j ∈ (0, 1) (fractional value)
• r_i = b_i - Σ_k a_{ik} · x̄_k (constraint slack at x̄, ≥ 0 for LP feasible)

When a[i][j] > 0, the BCC disjunctive cut from row i is:

π · x ≥ π₀ where π = a[i], π₀ = a_i · x̄ - r_i · f_j / (1 - f_j)

Violation at x̄: π · x̄ − π₀ = r_i · f_j / (1 − f_j) ≥ 0.

When the structural constraints are all tight (r_i = 0 for every row i with a[i][j] ≠ 0), the structural rows give zero violation. To handle this case the generator augments the constraint system with the variable bound rows 0 ≤ x_j ≤ 1 (written as -x_k ≤ 0 and x_k ≤ 1 for each integer variable k ≠ j). The bound row x_k ≤ 1 for k ≠ j has:

dot_ax = x̄_k, r_i = 1 − x̄_k > 0 (since x̄_k < 1), a_{ij} = 0

which provides a non-degenerate row when combined with variable j.

References

• Balas, E., Ceria, S., & Cornuéjols, G. (1993). “A lift-and-project cutting plane algorithm for mixed 0–1 programs.” Mathematical Programming, 58(1-3), 295-324.
• Balas, E. (1979). “Disjunctive programming.” Annals of Discrete Mathematics, 5, 3–51.

Structs

LiftProjectConfig

Configuration for the lift-and-project cut generator.

LiftProjectCut

A single lift-and-project cut of the form π · x ≥ π₀.

LiftProjectGenerator

Generator for Balas-Ceria-Cornuéjols lift-and-project cuts.

Enums

VariableSelectionStrategy

Strategy for selecting which fractional variable to lift-and-project on.

Functions

cut_satisfied_at_integer

Verify that a cut is satisfied at an integer 0-1 point.

ls_strengthen

Apply Lovász-Schrijver (LS) strengthening to a lift-and-project cut.