Hi, I have an algorithm that decompose a MILP model in lots of smaller integer problems. I expected these problems to be easy to solve and, in fact, for most of them, the solver quicly finds the optimal solution stating that it used "0 MIP simplex iterations" and generated "0 branc&bound nodes". The solver I've been using is CPLEX. My question is: if the solver does not employ either the simplex or the B&B scheme, then how does it actually solve the problems? I think it just uses some presolving heuristics, or it solves them by inspection. Would I be correct? TIA
asked
Andrea T |

As Marco already pointed out, the most likely thing is that the presolver solved the problem. A simplified explanation of what happens is that the presolver was able to tighten all bounds so much that all variables become fixed. This can be done with primal (feasibility) arguments or dual (optimality) arguments and might not be obvious if you look at the model yourself since the presolver will also "try out" setting variables to 0 and 1 (probing) and analyze the consequences. Another possible explanation that Marco pointed out, if you have no objective function or all variables with an objective coefficient become fixed any solution found results in optimal. And primal heuristics that ry to find feasible solutions are typically run before even solving the root node relaxation and maybe even before starting the presolver. A third but much less likely possibility is that the solver found a dual (lower) bound (through more or less complicated argument) and was able to find a matching feasible solution through primal heuristics which would also result in optimality before the root node relaxation was solved. A last possibility I can think of is that the solver under the hood used some special algorithm to solve your problems, for example, a knapsack solver. Depending on how a specific solver treats such a situation it might not report any nodes or simplex iterations.
answered
Philipp Chri... |

It is hard to know which techniques CPLEX used at the root node to solve your models without seeing the models. I can only confirm that the simplex hasn't been run if iteration count is 0. In order to understand better, you could look at the presolved models. For instance, in cplex interactive, you can do
assuming your initial model is model.lp. You can then look at model_pre.lp to see what's left after presolve. It may be that presolve eliminates all the rows and columns, in which case the problem is solved by presolve only. It may be that presolve does not eliminate all rows and columns, in which case the presolved model is solved by a heuristic
answered
jfpuget |

you give the answer yourself. presolve and also heuristics work (not only) at the root node. When, say, the objective function is 0 (i.e., you have a feasibility problem), you know the first solution you find is optimal.