6

I was reading Tobias Achterberg's thesis, and on page 138 he mentions the following presolving technique for linear equations (I'm slightly paraphrasing Example 10.2):

Consider the equation $4x_1+7x_2+3x_3+s=20$ with $s\geq0$, and assume that $s$ does not appear in other constraints. Then, we replace the equation with the inequality $4x_1+7x_2+3x_3\leq20$.

What are the benefits of doing this? Sure, this way we remove a variable from the problem, but won't an equivalent variable just be added back in when we bring the MIP to canonical form in order to apply dual simplex?

Nikos Kazazakis
  • 12,121
  • 17
  • 59
  • 2
    Removing the slack has in general no value. However, for a specific implementation it might be worthwhile. – ErlingMOSEK Jan 29 '20 at 08:21
  • I would like to add that if you go for solving the model with a commercial solver, there is no benefit in omitting the slack variable since the solver will add it again. – Mostafa Mar 28 '20 at 06:10

0 Answers0