Solving time for a network problem

[Minh Vu Duc]

Dear Gurobiers,

I have a multi-commodity flow model and two variants: one with continuous flow variables (0 \leq x^{k}_{ij} \leq 1 )and one with integer flow variables (x^{k}_{ij} \in {0,1}). 

I observe that solver spends much more time at the root node with the continuous model is much than the integer model. I do not understand why?

Continuous model:

Presolved: 10155 rows, 298771 columns, 892859 nonzeros

Variable types: 297044 continuous, 1727 integer (0 binary)

....

  176692    2.5817410e+07   0.000000e+00   0.000000e+00    451s

Root relaxation: objective 2.581741e+07, 176692 iterations, 449.27 seconds

Integer model:

Presolved: 10155 rows, 298771 columns, 892859 nonzeros

Variable types: 0 continuous, 298771 integer (297044 binary)

....

   89210    2.5817410e+07   0.000000e+00   0.000000e+00     24s

Root relaxation: objective 2.581741e+07, 89210 iterations, 22.47 seconds

It seems that it not only happens with this particular instance but also other instances. So I want to know what is the possible reason. 

Thanks,

Lessi.

[Tobias Achterberg]

Hard to say. First, I am really surprised that presolve seems to run identical in the two
formulations. I would have guessed that with the binary formulation presolve can do much
more than with the continuous one.

The relaxation solve is somehow influenced by the variable types as well, so it can happen
that the two solves are different even though the LP relaxation is completely the same.
But maybe, the relaxation is not identical in terms of the actual coefficients. It could
be that with the binary variables you get tighter coefficients, which can speed up the LP
solve.

Regards,

Tobias

[Minh Vu Duc]

Thank Tobias,

It is the same model in terms of variables and coefficients except for the type of flow variables. It formulates a capacitated multi-commodity fixed cost network design problem.

In addition, the solver reaches 1% gap much faster with the binary-flow-variable formulation than with continuous-flow-variable formulation.

Regards,

Minh

Vào 01:33:58 UTC-5 Thứ Sáu, ngày 22 tháng 9 năm 2017, Tobias Achterberg đã viết: