Mfcttrf

Often there are many alternatives ways for formulating a MIP. For example:

1. The model contains inequality constraints that must hold with equality in an optimal solution.


2. The model contains continuous variables that will necessarily be integer in an optimal (or just integer feasible) solution.


3. The model contains variables that have a value of at most 1 in an optimal solution.

In these cases, the modeler can decide whether to (1) include the constraints as equality constraints or not, (2) declare the variables as integer or continuous variables and (3) to declare the variables with upper bounds of 1 or not. When using commercial solvers, I have noticed that the performance may vary significantly dependent on such choices. Hence, I am wondering whether there are any rules of thumb for formulating MIPs in solvers. More generally, what information is valuable to solvers and what information may even hurt performance?

I’m assuming that we want our models to be solved as quickly as possible. If that is the case, then the honest answer is: you need to try the models out and see.

To give you a concrete example (see here): through what I thought was a super-clever reformulation, I was able to remove 85% of the variables in the problem, and I thought that this would make it super fast. However the performance was orders(!!) of magnitude worse than before, because the original problem was symmetric, and the new one was not.

I always try to put the tightest upper bound I have, make my big-M as small as possible, use continuous over binary/integer when I can, but honestly, you cannot know anything for sure until you test it.

Perhaps you are only talking about MILPs, but you don't say, so I will say something of interest for MINLPs.

Regarding point 1:

• Suppose your model has a convex nonlinear inequality constraint, $f(x) le c$, i.e., $f(x)$ is convex.

and

• It is known that the constraint will be active at the optimum, of any continuous relaxation i.e., $f(x) = c$, for instance because the continuous relaxations are concave programs with compact constraints, thereby having global optimum at an extreme of the constraints

Then you are usually better off entering the constraint as an inequality rather than as an equality. That is because the inequality constraint is convex, and generally much easier for an optimizer to deal with than a nonlinear equality constraint, which is a non-convex constraint. You might think you'd be doing the optimizer a favor by specifying the equality constraint, thereby cleaving off $f(x) < c$ from consideration, but such a "favor" will usually backfire.

However, in the case of a linear equality constraint known to hold with equality at the optimum of the original problem, or a continuous relaxation, I think it would generally be better, and in any event, not worse (except for (un)lucky "stars aligning" cases), to specify such a linear constraint as an equality constraint.

Regarding point 3, I have a pretty hard time imagining it would be better to not provide an upper bound of 1 than to provide it when you know the optimal variable value is at most 1. But I suppose for some particular model and solver, the stars could always align such that specifying such an upper bound slowed things down.

I will leave others to comment on point 2.