Originally posted by: hllsen

Hello,

To generate multiple feasible solutions mid-optimization, we stop the optim procedure with node or tolerance parameter and use the populate procedure; however, we realized when we use populate in mid-optimization, it leads considerable slow down in the rest of the optimization (31s vs 397s). We suspect the culprit is the parameters populate procedure modifies internally. Specifically, the ones related to cut generation since the number of applied MIR cuts at the end of the optimization procedure is 1340 without populate and there is no cut print-out at the end of optimization if we use populate mid-optimization. Or populate (phase II) creates its own B&B tree and the subsequent optimization call starts from the B&B of the populate procedure instead of continuing from the first optim call.

I attach the interactive optimization outputs for the following code snippet with and without populate:

cplex

read curprob.lp

set mip limit node 0

set empha mip 3

optim

populate

set defaults

set mip tol mipgap 0.005

optim

How can we prevent this from happening (i.e., still want to use populate but want to keep the performance of the optimization procedure more or less the same)? Or  is there a way to "really" reset the parameters to defaults so that optimization procedure continues from the first B&B tree in a similar way? Any other suggestions on how to obtain the desired effect would be very much appreciated.

Thank you for answers.
h.

In general it is not a good idea to call 'optimize' after 'populate'. Even if all parameters are reset, CPLEX skips certain things in populate that cannot be recovered in an 'optimize' call afterwards. A very simple example is this:

In 'populate' the root node is solved with cuts settings that are a lot less aggressive than in defaults. If 'populate' stops after the root node then an ensuing 'optimize' will not redo the root node. So we will not have the same cuts and since cuts in the tree are separated a lot less aggressively than at the root, it may take a long time to raise the dual bound to the same value.

What you should probably do in the 'optimize' after 'populate' is to set CPX_PARAM_ADVIND=2. This makes CPLEX start from scratch but keeps all feasible solutions found so far and adds them as MIP start.

Originally posted by: hllsen

Thanks for the reply Daniel. In fact my example was a simplified one and we want to use the populate process many times within the optimization. We tried ADINV parameter but since we start from scratch each time, the re-optimization takes too much time to reach the last optimality gap.

We also tried to use the populate procedure on a clone of the main optimization model (so that the 'phase II' of populate doesn't touch the B&B tree of the main optimization and main optimization continues from the point where it was stopped). However, since cloning only clones the problem, not the whole CPLEX state, this time populate starts with 'phase I' to solve the clone from scratch (again re-optimization takes a lot of time). Considering the fact that the original model is already solved, if there was a way to clone the whole state of model, populate would directly continue with 'phase II', we would get our solutions and then continue the optimization of the main model from the point we stopped it. Can you think of a way to achieve this?

I did not think a lot about this yet but I have a crazy idea (which will not work on Windows): Use fork() to create a copy of your process. Then in one process continue by just calling CPXmipopt() again, in the other process call CPXpopulate(). This will require some synchronization between the two processes but maybe it is possible.

Originally posted by: hllsen

Thanks for the rapid response Daniel! Well, I assume if it comes to using forks, this means what we want to do is not really possible using the existing CPLEX routines/functions. I'll accept your answer but I am afraid we can't use forks since this is a small part of a huge code.

fork()ing should not affect the rest of the code at all. But I agree that maybe it is overkill to do so. And yes, you are right, CPLEX has no means to clone its current state, sorry.

When you tried running populate on a clone, did you try adding the best known solution as a MIP start? Or maybe all solutions from the pool (in reverse order)? And maybe tweaked some parameters so that CPLEX would quickly create a large tree and thus have a large number of nodes to populate from?

Also, are you running populate because it happens to produce good solutions or because you just need a large number of feasible solutions?

Originally posted by: hllsen

Yeah I don't think we can justify the usage of fork().

Yeap, we add all previous solutions to the clone and can see that the best one is selected and the rest is still kept in the solution pool. Didn't try to modify any parameters to be honest since re-optimizing was not a real option for us (it takes long as we keep decreasing the EpGap parameter).

We need a number of near optimality-tolerance feasible solutions. Populate creates a large number of solutions (very fast  if it is only the 'phase II') and the solutions are not that bad. Basically we don't want to effect the optimization time (i.e., we want it to be as fast as possible) and spend a couple of seconds to increase the number of solutions then continue the optimization. To put it other way, we want to have the cake and eat it too :)