Trade off between number of constraints and bounds of a variable

Question

I am not familiar with the inner working of the solvers. I mostly use the python pulp or IBM CPLEX solver.

For fast execution time, what should be the priority, fewer constraints and loosely bounded variables or more constraints and tightly bounded variables?

For example, if I have a variable $X$ which, due to linearization, gets a value range between $[-M, +M]$ and its lower bound is $0$, so that its bounds are $[0, +M]$. Let's say it is a minimization problem and $X$ is somehow used in the objective function, so the solver will end up assigning value $0$ to it since it is the lowest.

My question is, will it be any help if I add constraints that bound the value of $X \in [0,0]$, does solver perform better in this case than previously?

Answer 1

This will depend to some extent on the specific solver you are using. Contemporary solvers have presolve stages. If you add constraints that are redundant, presolve will often weed them out. Solvers also use some form of "active set" technology, meaning that constraints that are not binding for most or all of the search will be held off to the side and will not slow the solver as much as constraints that are actively involved in pivoting. So I think a reasonable rule of thumb is this: be cautious adding constraints that are obviously redundant (although they do sometimes help), but do not worry too much about adding constraints that might tighten things.

That said, if your variable X is automatically going to take value zero (appears in the objective with positive coefficient and does not appear in any constraints where a positive value of X would allow beneficial values for other variables), the presolver will likely fix it at zero. So forcing it to zero may not be helpful (and runs the risk that, if you are wrong about it being zero in an optimal solution, you might cut off the true optimum).

Answer 2

Tighter variable bounds are always helpful as they help restrict the search space and avoid degeneracy.

More constraints are often very helpful, especially for MILPs, because they help reduce the viable number of integer combinations. Constraints are also used to tighten variable bounds through constraint propagation.

There are however a couple of things to watch out for:

• Solvers are much more efficient when solving sparse problems, i.e., problems with many small constraints, vs fewer but more dense ones. One of the reasons is that factorising sparse matrices tends to be easier.

• Redundant constraints can cause numerical issues, but they are removed by the solver at the presolving stage.

• If a variable is supposed to be unbounded, setting its bounds to a large number is actually worse than setting no bounds at all, because there are special presolving techniques for unbounded variables.

With respect to your question, it doesn't matter how you fix the variable if you are using a commercial solver like CPLEX. The types of constraints you describe are called singletons, and presolvers use that information to fix the variable and remove it from the problem altogether, along with the constraints. If you fix the bounds instead, the solver will do the same thing.