5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The complexity of the linear programme depends on the number of its rows/constraints, but in the mixed-integer linear programme having more variables (with tighter bounds) or constraints could help solve the model faster. $\endgroup$ – A.Omidi Feb 1 at 12:02
  • $\begingroup$ So I should only focus on tight bounds when the variable is non-binary. $\endgroup$ – anoop Feb 1 at 13:44
  • 2
    $\begingroup$ Just a small note: pulp is not a solver, it is a modeling environment. When you use pulp, you are calling a solver, such as CPLEX or Gurobi. $\endgroup$ – LarrySnyder610 Feb 1 at 14:00
  • $\begingroup$ If you know that a variable must be 0, it is best to just omit it from the formulation instead of forcing it to 0. $\endgroup$ – RobPratt Feb 1 at 20:45
  • $\begingroup$ actually in my problem value of $X$ is decided by other boolean and continuous variables, but I know the case when It has to be zero. $\endgroup$ – anoop Feb 1 at 20:57
7
$\begingroup$

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).

| improve this answer | |
$\endgroup$
  • $\begingroup$ " if you are wrong about it being zero in an optimal solution, you might cut off the true optimum" what about the case when I am sure, will it help the solver to solve faster. $\endgroup$ – anoop Feb 1 at 20:38
  • $\begingroup$ Possibly, if the presolver cannot figure out the same thing. At any rate, if you are positive, it should not hurt to try. $\endgroup$ – prubin Feb 2 at 21:22
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Actually in my problem $$\sum_i b_{i,j} = 0 \implies X_j = 0$$ else diffrent value of $X$ but if I don't add this constant then also solver seems to find $X = 0$ because of lower bound now should I add above constraint or not. $\endgroup$ – anoop Feb 2 at 6:49
  • $\begingroup$ This implies that your system is loosely constrained, i.e., that the value of your objective doesn't change even if you remove some constraints. However, these other constraints might be important for the logical consistency of your problem, so you shouldn't remove them if that's the case. If your objective is always zero, adding a constraint that imposes that can help, but only if you are certain that this should always be the case. $\endgroup$ – Nikos Kazazakis Feb 2 at 13:56
  • $\begingroup$ While it is true for (mixed) integer programs that tighter bounds typically (not necessarily always) stengthen the formulation and thus restrict the search space I don't think it is a true statement that tighter bounds avoid degeneracy (a term that applies for linear programs). So the first sentence in this reply should probably be reworded. $\endgroup$ – Philipp Christophel Feb 3 at 8:07
  • $\begingroup$ Degeneracy is equally applicable to LPs and MILPs, as it simply means we have multiple global solutions. The reasons can differ between the two classes, but in both cases tightening variable bounds (which could also be integer variable bounds) can help avoid said degeneracy. It's hard of course to make general statements for these things because there are always edge cases, but I think the statement is true enough to be a general guideline. $\endgroup$ – Nikos Kazazakis Feb 3 at 16:44

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.