# confusing results of two models with different complexity

i have two models that address the same problem.

the first one is : the second one is: for different instances for the same size (n=30) i found the following results ( the first column on the left is for the first model , the second column is for the second model). It seems illogical that a model with o(n3) variables and constraints consumes less time than a model with o(n2) variables and constraints. Could these results be explained ? or the use of multiple binary variables instead of of low variables could reduce time?

• Would you see this or this links? – A.Omidi Oct 18 '20 at 7:19

## 1 Answer

There are a number of possible explanations (not mutually exclusive). The larger model might have a tighter continuous relaxation. (You can test that by relaxing the integrality restrictions and solving both LPs.) Assuming you are using a solver that has a presolve stage, there may be something in the first model that allows the presolver to tighten things in a way it cannot do in the second model. The solver may generate cuts that are more productive in the first model than in the second (or not available / not relevant in the second). Also, there may be an element of luck involved (particularly if your time comparison is based on a single problem instance).

Integer programs are perverse beasts.

• A very nice (and simple) example is presented in optimization-online.org/DB_FILE/2011/06/3050.pdf The problem in Example 1 is an infeasible compact MIQCP problem. Proving infeasibility (whether by B&B or cuts) requires exponentially many iterations, but there is a (polynomially large) extended formulation that can solve in polynomial time. – mtanneau Oct 17 '20 at 22:41
• so the use of 2 binary variables for the first model and a continuous flow variable and only one binary could affect the branch and bound tree size while solving? and for instances with larger size could we theorically have inversed results due to the complexity of the first model complexity – fathese Oct 19 '20 at 8:34