3
$\begingroup$

Is the substitution method expected to reduce the computation cost? We know it will reduce the number of variables and constraints.

I mean by substitution method is to eliminate the equality constraints when possible.

A simple illustrative example might be:

minimize z
Subject to:
z=x-2
0<x<1

This can be reduced to:

minimize x-2
Subject to:
0<x<1

When I use the substitution on a large problem, the computation time decreases if I use gurobipy but increases if I use CVXPY

$\endgroup$

1 Answer 1

4
$\begingroup$

If you have a long equality constraint $x=\sum_j a_j y_j$ and $x$ appears multiple times in your model, performing the substitution can greatly increase the number of nonzero coefficients in the constraint matrix, and that typically hurts the performance.

$\endgroup$
3
  • 1
    $\begingroup$ Agree with that as it reduces variables but Dr @RobPratt won't it increase the rows to process? $\endgroup$
    – Sutanu
    Dec 3, 2022 at 14:47
  • 1
    $\begingroup$ Perhaps it depends upon solver whether they are using dynamic column generation or row generation. That may explain perf diff between gurobipy and cvxpy $\endgroup$
    – Sutanu
    Dec 3, 2022 at 14:56
  • 1
    $\begingroup$ @Sutanu yes there is a trade-off., but having one “extra” variable and constraint to significantly reduce density of several other constraints is usually a good thing. $\endgroup$
    – RobPratt
    Dec 3, 2022 at 14:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.