1
$\begingroup$

When encoding a problem into a Mixed Integer formula one faces a trade-off between embedding domain knowledge which might require new helper variables to express the constraints thereby growing the formulation.

Are you aware of any rule of thumb for mixed integer (Linear, Quadratic or Non-linear) problems whether encoding some additional constraint is worth the number of variables and constraints?

For MILP i might imagine it to look like the product of the simplex iteration time of the two variants times some function of the size of the possibilty space on both variants.

$\endgroup$
1
  • 1
    $\begingroup$ Are you asking about alternative ways of formulating a constraint or about whether or not to include a constraint that is implied by the existing constraints (but might help the solver)? An example of what you have in mind might help. $\endgroup$
    – prubin
    Nov 15, 2021 at 22:21

1 Answer 1

4
$\begingroup$

Unfortunately it's a trial and error game. If and only if (pun intended) we try to solve the leanest version of the model and that doesn't work, we then start adding redundant constraints.

The reason is simple: it's easy to make the model more complicated, but simplifying it is much harder.

In global optimisation, the more constraints we have the easiest the problem becomes to solve (usually but not always). By "easier" here I mean that:

  • We explore fewer nodes

  • We find better feasible solutions earlier during branch and bound

However, there is a crossover point where the additional constraints increase the cost of computations so much, that we're better off not adding any more constraints.

This cost depends on:

  • Any redundant constraints the solver decides to add on top of our constraints

  • How fast the solver we are using is

  • Chaotic effects such as the solver having more (or less) trouble factorising the equations for no obvious reason, or the solver picking different variables to branch on, leading to very unexpected outcomes.

  • Making it harder/easier for the solver to satisfy feasibility because of numerics.

At the solver level, we do this dynamically. We have a pool of cuts, and on every node we add the minimum number of redundant constraints that are likely to have great impact. That number (as well as the choice of constraints) are adjusted dynamically during the solving process through heuristics as well as trial and error. This means we'll try some stuff out, and if worked well, great. If it didn't, even though we expected it to, the solver will adjust its decision making according to the data.

At the solver level we also do presolve before we start solving. This involves running dozens of different algorithms usually with the intent of extracting some useful information out of some constraints and then dropping them altogether, so it's not obvious to the modeller what constraints the solver will find "useful".

A rule of thumb is to write a correct model and let the solver do its job. If that doesn't work, your hint that redundant constraints are not likely to help is if the solver is already showing slow iterations, i.e., it's already struggling with the size of the problem. If iterations are blazing fast but it's getting stuck on the same numbers, adding more constraints might help but this can also be a sign that actual constraints might be missing, not just redundant ones.

When we do decide that adding more constraints is the way to go, the rule of thumb is: don't try to outsmart the solver. Dozens of people spent thousands of hours putting that thing together. The new information shouldn't be redundant constraints that the solver can add itself, it should be information about the behaviour of the system the model is describing.

$\endgroup$

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.