Hello,

I really wonder how CPLEX and/or Gurobi deal with pure satisfaction integer problems. I can't get my hand on any article or documentation with details on the topic, if you do, don't hesitate and redirect me.

For instance, I cannot see how cutting planes methods can help on a decision problem since improving the relaxation and the upper-bounds do not help quitting branches in that case (no objective).

What are the mechanisms and information computed by that the commercial solvers to reach efficiently feasible solutions, or to conclude on the infeasibility ?

Is that linked maybe to the dual problem, if it is unbounded, then the primal is infeasible ? I'm really guessing here so correct me if needed :)

Thanks !

asked 23 Oct '15, 13:50

Astoupayne's gravatar image

Astoupayne
314
accept rate: 0%


I suspect only someone from IBM or Gurobi can give a definitive answer. AFAIK, CPLEX treats satisfaction problems fundamentally the same way it treats any other MILP.

Bear in mind that the defaults for many CPLEX parameter settings boil down to "use your best judgment". So if certain types of cutting planes are ineffective on satisfaction problems, CPLEX will likely detect this early on and dial down or eliminate the effort spent on them. Besides cutting planes, CPLEX also has some heuristics in its arsenal. If it is struggling to find a feasible solution, it may ramp up the effort spent on some of those.

As a user, you can also tweak some parameters to push for a quick feasible solution. In particular, switching the MIP emphasis parameter to "feasibility" or "hidden feasible solutions" might pay dividends, as might a change to the RINS heuristic frequency.

link

answered 23 Oct '15, 19:55

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Thank you very much for this answer @(Paul Rubin). You're right, my question could have been even more general : how do solvers reach the first feasible solution for any integer program ?

So there are heuristics that try to do so and that might work. If the heuristics fail, the branching starts and the cutting planes are added in the hope to discover that one of the relaxation solutions is an integer solution ? The chances of that happening being reinforced by all the cutting planes added ? Is that the way to see it ?

In the case of satisfaction problems, how do they manage to conclude on the infeasibility of a given model ? Is that the conjunction of cutting planes (found during the branching) that are valid for the whole problem that lead to an impossibility ? Or just a full exploration of the seach tree accelerated by a lot of infeasible relaxations ? Or something else (dual analysis...) ?

Thanks again :)

link

answered 24 Oct '15, 17:37

Astoupayne's gravatar image

Astoupayne
314
accept rate: 0%

Heuristics may be applied throughout the search tree, not just at the root node. An infeasible problem is recognized as infeasible when all nodes in the search tree have been pruned due to infeasibility.

(25 Oct '15, 10:56) Paul Rubin ♦♦
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:

×231
×191
×101
×22

Asked: 23 Oct '15, 13:50

Seen: 1,206 times

Last updated: 25 Oct '15, 10:56

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