I'm formulating a large MILP to solve a problem which resembles a directed graph. I have options to reduce the number of variables, but making my implementation code more complicated.

For example, a simple vertex conservation constraint could be implemented as follows, where v1 is the value of the vertex and $in1.*$ are incoming arcs, and $out1.*$ are the outgoing args:

$$in1.1 + in 1.2 + in1.3 = v1$$ $$v1 = out1.1 + out1.2 $$

Technically I could eliminate the $v1$ variable and simply equate the two to achieve the same result:

$$in1.1 + in 1.2 + in1.3 = out1.1 + out1.2$$

However this complicates my code and as well as my interpretation of the solution (eg. I have to manually calculate the value of $v1$ afterwards). Also, I would hope that any decent solver would eliminate a variable for each equality constraint via substitution, suggesting that the equality constraints do not add any difficulty to the optimization.

As an extreme case, obviously an LP with this constraint:

$$x1 = .....$$

should be no more or less difficult than an LP with these constraints:

$$x1 = .....$$

$$x2 = x1 + 123$$

$$x3 = x2 + 234$$

Since the values of $x2$ and $x3$ are directly determined by $x1$. In general I would expect that any equality constraint such as:

$$x1 + x2 + x3 + x4 = 0$$

would be eliminated simply by substituting $x1$ with $(-x2 - x3 - x4)$ throughout all constraints and objective function.

My questions:

1) Is it correct that that equality constraints do not increase the difficult of optimization problems (LP/MILP at least)? Any exceptions to this?

2) If so, would I be correct to assume that there is no downside to formulating a problem with an easier implementation which uses more variables, but constrained by equality?

  • $\begingroup$ In programming they say "premature optimization is the root of all evil", which in this case means you should try doing it the easy way (in terms of implementation) and only complicate the implementation if you really need a runtime improvement. $\endgroup$
    – littleO
    Aug 6 '17 at 3:14

If you are asking whether additional equation constraints increase difficulty (as opposed to whether equations are any better or worse than inequalities), the answer is a resounding "maybe". On the one hand, more equations may mean more rows in the constraint matrix, which may make decomposition of the matrix, updates to the basis matrix etc. slower due to requiring more operations (and consuming more RAM). Adding auxiliary variables also means more columns (more storage, somewhat more work per iteration). On the other hand, additional constraints may make the constraint matrix sparser, and modern solvers handle sparse matrices faster than dense ones.

Keep in mind, though, that modern solvers tend to do a "presolve" step, in which the problem you fed the solver is transformed into an equivalent but possibly more compact version. During presolve, some rows and columns may be eliminated from the constraint matrix, by a variety of techniques. The presolver may recognize that, in your example, $v1$ can be eliminated algebraically. It might also recognize that some combination of constraints and/or objective coefficients imply that certain variables must take specific values, and eliminate them. A particular presolver might also look at your problem and decide not to eliminate $v1$ because doing so would turn two sparse constraints into one denser constraint.

Back when men were men and computers had vacuum tubes (except the newfangled ones, which had those transistor things), squeezing a formulation down to something compact was important. Today, I would advocate for using the most convenient and/or human-readable model (meaning, in your case, leaving $v1$ in) and letting the presolver decide. That's my personal practice, for several reasons:

  1. the people who write the presolver are smarter than I am;
  2. the presolver is considerably less likely to make a mistake compacting the model than I am to make an algebra error doing so; and
  3. my original model (before any "cleverness" on my part) tends to be both easier to explain to other people and easier to maintain (if it needs changing down the road).

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.