# Do equality constraints in an LP/MILP increase the difficulty of the program?

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?

• 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. Aug 6 '17 at 3:14

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: