6
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Removing the slack has in general no value. However, for a specific implementation it might be worthwhile. $\endgroup$
    – ErlingMOSEK
    Jan 29, 2020 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, 2020 at 6:10

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.