Does adding constraint to an optimization model make it solve faster?

Question

Some say adding constraints cuts the feasible region smaller hence the same solver terminates faster due to the less search effort. Others say it adds more complexity to the problem and it may take longer to solve.

Personally, I think it depends on the model and the algorithm that is solving it. For instance, adding constraints to a linear program may add more vertices to the polyhedron that represents the feasible region. Consequently, the Simplex algorithm may take longer as it pivots over more extreme points.

To what extent do we know the effect of adding constraint to any given mathematical model and solution algorithm?

Answer 1

There's no single answer to the question of whether adding constraints will help or hurt.

If we have a MIP formulation of the TSP and we remove the subtour-elimination constraints, the resulting MIP is easy; now add the subtour-elimination constraints back in, and the problem gets much harder.

On the other hand, if we have a MIP formulation and we add constraints forcing all the decision variables to equal some known feasible solution, then the resulting problem is trivial; it got much easier.

(I know your post asked the much more interesting and nuanced question of what is known about the effect of adding constraints ... I'm purposely avoiding that part. :) )

Answer 2

We don't, that's why many optimisation problems are NP-Hard (or vice-versa). Some tricks are known to work most of the time, such as RLT or Gomory cuts, but even then we need to pick the "right" constraints out of all the possible options, and to add the "right" number of constraints, otherwise:

• Number of iterations is improved, but each iteration is too slow, or
• Number of iterations is pretty much the same, but each iteration is, again, too slow, or
• The model becomes numerically unstable/infeasible, or
• Number of iterations is actually larger and slower, due to some chaotic change in how the change in the problem interacted with the solver's algorithms.

What we do know for sure is that removing certain types of constraints the "right way" is always good, e.g., symbolically eliminating singleton constraints.

Answer 3

Depends on the model itself as you mentioned. Adding constraints would help the model to define its search space but there is also a possibility where you may not find a solution in your search space at all.