Doubleton Elimination

Presolve Reductions 1 implementation

Given equality constraint ax + by = c with two variables:

  1. Solve for y: y = (c - ax) / b
  2. Substitute y in objective: c_x x + c_y y → c_x x + c_y(c-ax)/b
  3. Substitute y in all constraints containing y
  4. Transfer bounds: l_y ≤ y ≤ u_y becomes bounds on x
  5. Remove row and column y from problem

Mathematical Formulation

Original: min c_x·x + c_y·y s.t. ax + by = c, bounds After: min (c_x - c_y·a/b)x + c_y·c/b, modified bounds on x Postsolve recovers y = (c - ax)/b from optimal x*

Complexity

Time: O(nnz(col_y)) per doubleton - updating all rows with y Typically reduces problem size significantly when equality rows exist Cascading effect: may create new singletons or doubletons

Implementations

CoinUtils