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?

  • 2
    $\begingroup$ Removing the slack has in general no value. However, for a specific implementation it might be worthwhile. $\endgroup$ – ErlingMOSEK Jan 29 '20 at 8:21
  • $\begingroup$ 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. $\endgroup$ – Mostafa Mar 28 '20 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.