3
1

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 15 Apr '14, 05:43

Andrea%20T's gravatar image

Andrea T
384418
accept rate: 0%

4

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.

(15 Apr '14, 05:50) Marco Luebbecke ♦

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.

link

answered 15 Apr '14, 08:40

Philipp%20Christophel's gravatar image

Philipp Chri...
1.0k27
accept rate: 22%

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

read model.lp 
write model.pre 
read model.pre 
write model_pre.lp

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

link

answered 22 Apr '14, 23:09

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×191
×56

Asked: 15 Apr '14, 05:43

Seen: 2,792 times

Last updated: 22 Apr '14, 23:09

OR-Exchange! Your site for questions, answers, and announcements about operations research.