4
$\begingroup$

I have a variable that can be defined as a sum of other variables. Should I create this variable and add a constraint that they are sum of the other variables or should use the minimum number of variables and use the sum each time?

Anybody having some intuition and experience regarding these choices.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Using duplicate expressions will increase the number of nonzero elements in the matrix. If the sum is not very short, it is usually cheaper to have a few more variables and constraints than to have a denser problem. LP/MIP solvers like sparse problems. $\endgroup$ – Erwin Kalvelagen Dec 10 '20 at 15:31
  • $\begingroup$ Can you add a small example (using MathJax) to clarify what you mean? The two comments so far are essentially answering different questions. If you can clarify, probably one or both of the commenters can convert their comment into an answer. $\endgroup$ – LarrySnyder610♦ Dec 10 '20 at 15:59
  • $\begingroup$ I'm thinking of the case where I use the aggregate variables in constraints and sometimes reuse them in multiple constraints. But some constraints also require the none aggregate variables. But I hear from @ErwinKalvelagen that I should care more about the density than the number of variables. Which is acturaly the answer I'm looking for $\endgroup$ – Peter Mølgaard Pallesen Dec 10 '20 at 21:15
  • 3
    $\begingroup$ Indeed. A different way of putting this is: the number of nonzero elements nz is often a better indicator for the size of an LP model than the number of rows or columns. $\endgroup$ – Erwin Kalvelagen Dec 10 '20 at 22:09
5
$\begingroup$

We use this method in Octeract Engine, and on a test set of ~3,000 problems it's better ~50% of the time, and worse for the remaining 50%.

I wish a had an explanation for you - we have yet to discover a reason or pattern as to why it's worse (one would expect it to be better most of the time).

Since you ask about best practices, we resorted to using machine learning to make the decision every time, which worked out pretty well.

Improve this answer
$\endgroup$
6
$\begingroup$

In my experience, it does not matter much for in terms of speed. The reason is that the size of an optimization really does not correlate with the time it takes to solve the model. There are even examples, where an equivalent formulation with significantly less variables and constraints is significantly harder to solve (see e.g. here.

Therefore, I always add those aggregate variables since they make the modeling cleaner. Then I give it to the solver and see whether it solves according to the performance that I need. If yes, great. If not, they you may want to have another look at the model formulation (and other details like computer hardware, solver parameters etc.) to see whether there are any improvements to be had.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Agree. Having a model that is more readable is also easier to maintain and improve on which have a lot of value also! $\endgroup$ – Michael Lindahl Dec 11 '20 at 9:26

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.