Context: I am trying to solve a hard MIP problem for which I want to apply RINS in the first phase of solve (for about 30 minutes) and then apply Solution Polishing.

Problem: However, when the cutoff time for solution polishing is reached, I see a cutoff in the log file and the optimization stops even though the gap is very high. This does not happen if I remove RINS. I suspect this happens because RINS sets the objective cutoff based on objective value of the current incumbent. I am pasting the solver log below for reference.

Question: Is there a way of being able to use RINS and polishing both in a same run, with RINS running in phase 1 and polishing in phase 2 without stopping the optimization?

LOG
Found incumbent of value -1.8400260e+09 after 1497.56 sec. (506818.92 ticks)
*     0+    0                      -6.22229e+08 -5082567.9764            99.18%
Found incumbent of value -6.2222884e+08 after 1663.41 sec. (555865.80 ticks)
      0     0        cutoff        -6.22229e+08 -5082567.9764   101011   99.18%
Elapsed time = 1801.08 sec. (599903.47 ticks, tree = 0.01 MB, solutions = 15)

Starting condition for polishing reached (PolishAfterTime). Starting solution polishing.

Clique cuts applied: 53 Cover cuts applied: 226 Implied bound cuts applied: 790 Flow cuts applied: 2475 Mixed integer rounding cuts applied: 3183 Flow path cuts applied: 258 Zero-half cuts applied: 74 Gomory fractional cuts applied: 23

Root node processing (before b&c): Real time = 1801.92 sec. (600049.86 ticks) Parallel b&c, 32 threads: Real time = 6.08 sec. (128.66 ticks) Sync time (average) = 0.06 sec. Wait time (average) = 1.97 sec. ------------ Total (root+branch&cut) = 1808.00 sec. (600178.52 ticks)

Solution pool: 15 solutions saved.

MIP - Integer optimal solution: Objective = -6.2222884063e+08 Solution time = 1808.03 sec. Iterations = 101011 Nodes = 0 Deterministic time = 600181.79 ticks (331.95 ticks/sec)

asked 18 Apr '18, 09:52

AMIT_HOODA's gravatar image

AMIT_HOODA
111
accept rate: 0%

edited 18 Apr '18, 13:47

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412

I assume from the log that you are maximizing (you did not say). Try printing the best node value (upper bound) after CPLEX terminates. The log indicates an optimum was found in the first phase, so I suspect CPLEX tightened the bound enough to prove optimality.

(18 Apr '18, 13:51) Paul Rubin ♦♦

Yes, its a maximization problem. This is not the optimum. The actual optimim if I run the problem for hours is 1.1 e 07 . If I run it for more than 1800 seconds in phase 1, it will find a better solution and terminate before polishing. This is because the RINS heuristic sets the cutoff to current objective value and the CPLEX solve does not exit RINS clearly before moving into polishing. It looks more like a CPLEX bug unless there's a workaround to it.

(19 Apr '18, 04:03) AMIT_HOODA

I see your program printing a message about starting polishing. Did this happen after the first solve call returned, or did you print this while the RINS run was still going? How do you tell CPLEX when to terminate the first phase? Do you set a time limit for it?

(19 Apr '18, 16:08) Paul Rubin ♦♦

In CPLEX, you can tell when to start polishing. My run terminates when the polishing starts. In the above example, I set the polishing start to 1800, so polishing starts at 1800 but as there is cutoff, the optimization terminates.

(20 Apr '18, 09:53) AMIT_HOODA

You said in a comment that the actual optimal value is 1.1e7. Do you really mean positive 1.1e7? The log shows a fairly large negative upper bound (which is not specifically tied to the incumbent value).

(20 Apr '18, 16:19) Paul Rubin ♦♦

Also, just to be safe, did you set any nondefault limits on the run (time, memory, nodes, number of integer solutions, absolute or relative gap)?

(20 Apr '18, 16:32) Paul Rubin ♦♦

Its actually negative 1.1 e07

(27 Apr '18, 07:16) AMIT_HOODA
showing 5 of 7 show 2 more comments

Have you tried printing out the best bound after CPLEX terminates. (I wish that CPLEX did this automatically, but it doesn't.) That might help determine why CPLEX thinks the wrong solution is optimal. I'm skeptical about RINS messing up the cutoff, because RINS is designed to run periodically in the search tree, and I've never heard of (let alone experienced) it messing up the best bound value.

Meanwhile, as a workaround, what happens if you stop the solution after 30 minutes., then start a fresh solve and invoke polishing there? As long as only parameters have changed (no changes to the model object), CPLEX will resume with the existing search tree. Assuming the node bounds are correct, that should be "uncorrupted" by RINS.

link

answered 27 Apr '18, 15:53

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

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:

×3
×1
×1
×1

Asked: 18 Apr '18, 09:52

Seen: 234 times

Last updated: 27 Apr '18, 15:53

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