2
$\begingroup$

I have a few questions about mathematical modeling (MILPs mainly). My understanding is that the complexity of a model is primarily determined by the number of decision variables, rather than the number of constraints. Am I right about that?if so, would it be beneficial to include constraints that seems to be naturally hold true, or to include constraints that should not naturally hold due to the nature of the objective function and the types of variables? These acting as cut constraint or can make the problem runs worse?

$\endgroup$
3
  • 1
    $\begingroup$ What do you mean by "include constraints that should not naturally hold"? $\endgroup$
    – prubin
    May 6, 2023 at 21:24
  • 1
    $\begingroup$ @Rainbow, maybe this link would interest you. $\endgroup$
    – A.Omidi
    May 7, 2023 at 5:50
  • $\begingroup$ Adding constraints can help because they may cut off something (or, indirectly, they can help the solver generate better cuts). But they can make the LPs more difficult. The trade-off can only be evaluated by trying it out. A basic rule when solving MIP models is trying out many alternatives. $\endgroup$ May 7, 2023 at 14:04

2 Answers 2

4
$\begingroup$

First, please note that the only valid generalization regarding MILP models is that there are no other valid generalizations besides this one.

That said, it is often (usually?) the case that increasing the number of variables does more to increase solution time than does increasing the number of constraints. There are at least two contributing factors. One factor is that most solvers use a "presolve" stage to simplify the model, which includes fixing models that can be fixed and eliminating redundant constraints. I suspect that it is somewhat easier to detect a redundant constraint than it is to fix a variable. The other factor is that modern solvers may use active set methods or may set aside constraints that have not been binding for a while and revisit them (possibly reactivating them and possibly setting aside other constraints) on the fly. Thus the solver may be working with the full set of variables but with only a subset of constraints.

As far as adding constraints, with integer programs the addition of a seemingly redundant constraint sometimes helps the solver fix integer variables earlier ... sometimes. It very much depends on the specific model and the specific constraint.

$\endgroup$
2
$\begingroup$

Constraints are like if-then-else type logic. These can be helpful as cuts (as you've mentioned), reducing the feasible region, setting bounds which may lead to faster solution time and smaller difference between the solution & true optimal.
Conversely large number of constraints (too many dual variables) can make finding a solution impossible in polynomial time (infeasible). The later happens when constraints are contradictory or quadratic with polynomial degree.
If you are introducing constraints that naturally do not hold you may constraint certain variables while leaving other variables uncovered. This may lead the solver to converge to a feasible solution by maximizing/minimizing variables that are not covered by constraints. Such solutions may not be optimal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.