2
$\begingroup$

i have two models that address the same problem.

the first one is :

enter image description here

the second one is:
enter image description here

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).
enter image description here

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Would you see this or this links? $\endgroup$ – A.Omidi Oct 18 '20 at 7:19
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ – mtanneau Oct 17 '20 at 22:41
  • $\begingroup$ 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 $\endgroup$ – fathese Oct 19 '20 at 8:34

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.