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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Agree with that as it reduces variables but Dr @RobPratt won't it increase the rows to process? $\endgroup$
    – Sutanu Majumdar
    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 Majumdar
    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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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