I wrote a MIP model in C++ and let the solver looking for feasible solutions. I plan to write some lines of code to know when the solver finds the best IP solution. Could someone give me hints or examples of how to do it. I guess it should be simple.

asked 21 May '16, 11:52

Duc%20Minh%20Vu's gravatar image

Duc Minh Vu
21115
accept rate: 0%


You can write an incumbent callback and keep the last time a new incumbent found each time it's invoked.

//Global variable
IloNum bestSolnTime;

ILOINCUMBENTCALLBACK0(BestSolnCPUTimeCallback)
{
   bestSolnTime= cplex.getTime();
}

//In the main method and before the cplex.solve() method
cplex.use(BestSolnCPUTimeCallback(env));
IloNum startTime = cplex.getTime();

//In the main method and after the cplex.solve() method
IloNum bestSolnDuration = bestSolnTime - startTime;

PS. I've not checked the code, but I guess it should work with no or few modifications. Also, if you are using multiple threads, you need to make all the necessary changes to make sure that the global variable is handled properly by the threads.

link

answered 21 May '16, 12:32

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

edited 22 May '16, 14:35

I just saw that callbacks have their own getTime() method. So it would be a good idea to check both ways of getting the current time to make sure everything is fine.

(21 May '16, 12:37) Ehsan ♦

Thank you so much. I will check your suggestion.

(21 May '16, 12:56) Duc Minh Vu

I tried your suggestion, and it works. I just do not understand why using callback function reduces the performance a lot. E.g. without the callback function, CPLEX stops after 100 secs, but with the callback function, it runs at least 300 secs.

p/s: for newbie and anyone who is interested in the question: change cplex.use(BestSolnCPUTimeCallback); to cplex.use(BestSolnCPUTimeCallback(env)); to make the code work.

(21 May '16, 16:31) Duc Minh Vu

By Default, control callbacks disable the dynamic search, which improves the search process considerably. To make sure that's the case, run your code without the callback, but disable the dynamic search manually and see if you have the same CPU time.

(22 May '16, 00:11) Ehsan ♦

BTW, thanks for finding and reporting the error in the code. I updated to post to reflect on that.

(22 May '16, 00:30) Ehsan ♦

Just a word of caution: the incumbent callback is called every time a new feasible solution is found. Therefore, the proposed code will give you the time of the last found feasible solution. If you want to know the time you found the optimal solution you need to check the value of the solution CPLEX has found and compare that to the incumbent

(22 May '16, 09:11) Sune

Excerpt from the CPLEX documentation:

After CPLEX finds an integer solution, it does the following:

  • It makes that integer solution the incumbent solution and that node the incumbent node.

  • It makes the value of the objective function at that node (modified by the objective difference parameter) the new cutoff value.

  • It prunes from the tree all subproblems for which the value of the objective function is no better than the incumbent.

Based on the above, the only logical conclusion is that a new incumbent is in fact the best integer solution found so far.

(22 May '16, 09:34) Ehsan ♦

Gurobi does a better job of defining the incumbent (excerpt from here):

Let us denote the best integer solution found at any point in the search as the incumbent. At the start of the search, we have no incumbent. If the integer feasible solution that we have just found has a better objective function value than the current incumbent (or if we have no incumbent), then we record this solution as the new incumbent, along with its objective function value. Otherwise, no incumbent update is necessary and we simply proceed with the search.

(22 May '16, 09:39) Ehsan ♦

You are probably right. I was looking at this page. It describes how you can use the incumbent callback as a filter. It says "During the populate procedure, the incumbent callback is called each time a new solution is found, even if the new solution does not improve the objective value of the incumbent". I'm not sure if that is specific to that particular application og not, though.

(22 May '16, 13:15) Sune

I think this applies only to the instances that you want to create a solution pool and solve the model via the populate() method, not the solve() method. To me, the "even if ..." part emphasizes that it's otherwise for the solve() method.

(22 May '16, 15:00) Ehsan ♦
1

As Daniel Junglas points out in this thread, an info callback (which does not turn off dynamic search or switch from parallel to sequential mode) might be a better choice, albeit slightly less accurate.

(23 May '16, 11:09) Paul Rubin ♦♦

Thanks Paul. The CPX_PARAM_INTSOLFILEPREFIX parameter is interesting. However, Daniel didn't provide enough information on how to use the information callback. I checked the documentation and the best information it could return is the objective value of the best integer solution found so far.

(23 May '16, 14:19) Ehsan ♦
showing 5 of 12 show 7 more comments
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
×8

Asked: 21 May '16, 11:52

Seen: 961 times

Last updated: 23 May '16, 14:19

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