Originally posted by: mshpd

Hi

I am trying to solve an MIP problem, where I have around 2.3 million binary variables and around 56k constraints. It is an assignment problem, modelled as a multi commodity network flow problem.

Root relaxation is completed in around 1200 seconds. And further integer solutions are obtained in around 800 seconds with the MIP gap reducing to about 40% in that time.

But after that, the branch and bound process is taking up a lot of time  without giving any significant reduction in gap. Within branch and bound, "CPLEX Solve LP Relaxation" is taking up the large chunk of run time.

So far , i have run the problem for 18 hours (max) without any significant improvement.  What are my possible methods to tune the problem?

So far I am using the following settings:

CPXPARAM_LPMethod                                4

CPXPARAM_QPMethod                                4

CPXPARAM_MIP_Strategy_Branch                     1

CPXPARAM_MIP_Tolerances_MIPGap                   0.050000000000000003

CPXPARAM_MIP_Display                             4

CPXPARAM_MIP_Interval                            1

CPXPARAM_MIP_Strategy_StartAlgorithm             4

CPXPARAM_MIP_Strategy_SubAlgorithm               4

CPXPARAM_MIP_Strategy_VariableSelect             3

CPXPARAM_Emphasis_MIP                            1

CPXPARAM_MIP_Strategy_FPHeur                     1

CPXPARAM_MIP_Strategy_Search                     2

Is there any likelihood your model exhibits a significant degree of symmetry (different assignments with identical costs and impacts)? If so, you could try cranking up the symmetry breaking parameter (CPXPARAM_Preprocessing_Symmetry).

Also, it might help to know whether the incumbent is not moving, the best bound is changing very slowly or both.

Originally posted by: mshpd

Hi

The costs associated with different assignments are similar, but not exactly equal. What i mean to say is that, the difference between them are very small in magnitude. 

About, the best bound and incumbent, During the branch and bound process, both are not moving. Then i tried solution polishing after 10 nodes. In that case, the incumbent began to move but the best bound remained non moving.

Thanks

It could well be that improvement in the bound is inhibited because "near symmetry" makes the LP relaxations in various parts of the tree rather similar. I suspect the symmetry breaking switch would not help much with that.

You specified MIP Emphasis 1, which stresses finding feasible solutions at the cost of making progress on the bound. You might want to consider running for a limited time with emphasis 1, to try to get a decent incumbent, and then switch to emphasis 2 or 3 to try to make progress on the bound. Calling solve a second time after changing only parameters (not changing the model itself) should resume with the same tree.

Originally posted by: mshpd

Hi

Thank you for the suggestion. But i couldn't observe any favorable results.

I tried out having an initial run with MIP emphasis as 1 (Feasibility) for an hour and then shift to 2 and 3. In both situations, i was not able to find any improvement in the run. Both the incumbent value as well as the best bound value remained the same . 

Thanks

Well, sometimes the LP relaxation of a MIP model is inherently "weak" (loose), in which case you are basically screwed when it comes to bound improvement. I'm fishing here, but your model does not by any chance contain "big M" constraints, does it?

Originally posted by: mshpd

Hi

In fact, we use a high penalty in the objective function to ensure that an activity is taken up at least once. I believe that qualifies as a big M variable.

Thanks

I think a large objective coefficient is usually less damaging than a large constraint coefficient, but I also believe it could still cause problems. Is there a reason why you use a penalty term rather than just adding a constraint that every activity be taken up at least once? Are there more activities than capacity (meaning some activities will necessarily not be done and thus incur the penalty)?
 

Originally posted by: mshpd

Hi.

Yes. That is the idea. All activities are not necessarily taken up. But we have to maximize the number of activities to be taken up. Hence, we have been using a penalty in the objective function.

Also, i am happy to report that with emphasis on optimality (mipemphasis-2) and using solution polishing , i have been able to bring down the time of solving and could get results within reasonable time. 

I have also turned off the crossover for barrier optimiser. Are there any drawbacks for turning off the crossover for barrier optimiser?

Thank you

Originally posted by: EdKlotz

If those penalty variables have much larger objective coefficients than all the other variables in the model, you might be better off first just optimizing over the penalty variables, then using the result of that run with the rest of the problem.   While I agree with Paul that big Ms in the objective are less harmful than in the constraints, they still can cause trouble.   By solving for them separately, you get several benefits:

1)  You no longer need to use the big M coefficient in the objective.   Since all the objective coefficients are now large, you can rescale the objective.   If all the objective coefficients are the same big M value, you can rescale all the coefficients to 1.

2)  The final solution to this first optimization is a feasible solution for the next optimization, which consists of the constraints of the first optimization plus the additional constraint based on the optimal objective of the first solve.

3)   You also get a cut that tightens the second optimization, e.g. if your first objective is to minimize the sum of the penalty variables and that results in z* as the optimal objective value, you add the constraint that the sum of the penalty variables >= z* for the second objective.

Originally posted by: mshpd

Hi

Thank you for the suggestion.

I am currently trying to model in this method. But i had a doubt regarding setting the constraint for the second problem.(Regarding your point 3).  Shouldn't the sum of penalty variables be <=Z* to obtain the second objective. Kindly throw some light on this aspect

Thanks

Originally posted by: EdKlotz

If you know that the penalty variables totally dominate the other parts of the objective, then you are correct regarding adding a constraint that the sum of the penalty variables <= Z* (or actually == Z*).   However, if that is not the case, i.e. the optimal solutions for the combined objective actually take on some penalties above their minimum values in exchange for improvements in the other objective, then the cut I described is correct.

Originally posted by: mshpd

Hi

Thanks for clarifying.

I tried out this method. But the initial problem for minimizing penalty, in itself is consuming more time than the combined problem (original method).

I have also faced some issues with the original combined problem. When the problem size was increased further, the existing tuning parameters were not being helpful.

The solver is running for more than a day and still not giving any solutions. The solution polishing stage itself has been going on for 24 hours.

Please find the log for combined problem attached. 

Thanks

I take it you already checked that barrier is the fastest for solving the root relaxation and the node relaxations?

Originally posted by: mshpd

Hi

Yes. I tried with the different combinations possible. For the root node, default setting will also end up with barrier. So, i stuck with barrier method.

Thanks

Originally posted by: EdKlotz

Please upload the node log of the run.   Paul's comments about near symmetry could indeed explain the lack of progress in the best bound.   I have a few suggestions to try based on the thread so far.

1)  Try running with default MIP emphasis and default variableselect along with the other parameters you currently use.   Variableselect 3 can be effective, but it also slows down the rate of node throughput.  Maybe you can start to make more progress in the best bound if CPLEX can simply process more nodes.

2)  Instead of solution polishing to make progress in the incumbent, try periodically applying the RINS heuristics, say every 100-200  nodes.   This is a local search heuristic, and based on your description of the model, it may be effective at improving on existing solutions.

3)  Try running with all cuts set to 2 and probing set to 3.   Those settings can help move the best bound faster.

4)  If the costs are similar, try creating a different version of the model where the costs are the same, and solve that, possibly with aggressive symmetry detection.  If that model solves much faster, that result helps you in two ways.   First, it confirms that the slight differences are in play regarding the challenging aspect of the model.   Second, you can take the optimal solution from this easier model and use it as a MIP start for the version with slightly different costs.   Given that you quoted a gap of 40%, I wouldn't be surprised if this gave you a better solution.

5)  Try creating a smaller version of this model with the same characteristics so you can do more tests in less time.

6)  Have a look at the paper and presentation here:

https://www.ibm.com/developerworks/community/blogs/jfp/entry/practical_guidelines_for_solving_difficult_mixed_integer_programs?lang=en

for some general tactics on getting better MIP performance.

Originally posted by: mshpd

Hi

I was able to improve the performance of the model with setting emphasis on optimality and using solution polishing.

1. Using default settings, i observed more or less the same time for solving the model compared to setting emphasis on optimality. So, i believe it is also a viable setting for getting solution.

2. I have tried RINS. But the time to reach optima is very high compared to Solution polishing

5. I could solve smaller models in reasonable time. But when the number of variables increased, the model tend to become very slow.

I am yet to try out settings 3 and 4.

Thank you for the resources as well

Thank you

Originally posted by: EdKlotz

You combination of setting MIP emphasis to optimality and using solution polishing makes sense; the first setting works well to move the best bound, while the second works well to move the incumbent.   I'm a bit surprised by your negative results with RINS and positive results with solution polishing, since RINS is an important part of solution polishing.    Regarding the smaller models doing well, certainly performance can degrade as problem size increases, but I urge you to compare the node logs of the smaller and larger models; they may shed light on something about the larger runs that you can remedy.

Originally posted by: mshpd

Hi

I am observing that when i run my problem to optimality, the final result value is better than the best bound (by a slight decimal value, but still) . That is at optima, the gap is negative. 

I am solving an MIP with minimisation objective. 

Is this normal behavior or whether there are any problems with my modelling?

Please find attached the observed line in the log.

Thanks

Looks like rounding error to me. I would ignore it.

Originally posted by: mshpd

Thank you