Originally posted by: ORA17

Hello Cplex Experts,

I have a NP Hard MIP problem with many binary and integer variables. I have attached log file for your reference. 

I observed that getting first feasible integer solution is taking more than 1 hour and after that converging very very slowly and it takes forever to solve it to optimality.

I have used below parameters:

cplex.SetParam(Cplex.IntParam.RootAlg, 4);
cplex.SetParam(Cplex.IntParam.NodeAlg, 2);
cplex.SetParam(Cplex.IntParam.BarCrossAlg, 2);

I have used .NET concert and CPLEX 12.6 version.

Any parameter tuning suggestion for this problem?

To get an initial incumbent sooner, you can try switching the MIP emphasis (IloCplex.Param.Emphasis.MIP) to finding a feasible solution (1 or 4) and/or turn on the feasibility pump (IloCplex.Param.MIP.Strategy.FPHeur, values 1 or 2). You could also code a heuristic outside of CPLEX to get a good starting solution, then feed that to CPLEX as an initial incumbent.

I think the bigger problem is the slow convergence of the lower bound. The first feasible solution CPLEX finds has what I would call a pretty good gap (< 4%), and it gets down to a little over 2%. If you are satisfied with that size gap, you can just set the relative gap tolerance and let CPLEX stop when it gets the gap down that low. If you are set on attaining proven optimality, you might look at how much symmetry your model has. Symmetry is one possible reason (but by no means the only one) for slow movement in the bound. If your model has visible symmetry, you can either try to mitigate it by adding symmetry-breaking constraints, or you can try setting the symmetry breaking parameter (IloCplex.Param.Preprocessing.Symmetry) to progressively higher values (1-5).

Originally posted by: ORA17

Hello Prof Rubin @paulrubin,

Thank you for your reply. I have tried to solve my problem with below parameters settings. But now looks like time to get solution with 5% gap taking even more time. Log file attached. Thanks. Could you please suggest where I am going wrong?

                model.SetParam(Cplex.IntParam.RootAlg, 4);
                model.SetParam(Cplex.IntParam.NodeAlg, 2);
                model.SetParam(Cplex.IntParam.BarCrossAlg, 2);
                model.SetParam(Cplex.DoubleParam.EpGap, 0.05);
                model.SetParam(Cplex.IntParam.MIPEmphasis, 1);
                model.SetParam(Cplex.IntParam.MIP.Strategy.FPHeur, 1);
                model.SetParam(Cplex.IntParam.HeurFreq, 1);
                model.SetParam(Cplex.IntParam.CutPass, 1);
                model.SetParam(Cplex.IntParam.Probe, 3);
                model.SetParam(Cplex.Param.Preprocessing.Symmetry, 1);

The feasibility pump took longer to get an incumbent than your first run did (and got a worse incumbent), so I would turn that off again.

Changes to the presolve options resulted in a larger problem (more rows, more columns, more nonzeros), which might or might not pay for itself in terms of a tighter bound. The root relaxation solutions time went up from 181 seconds to 246 seconds, indicating the larger model is more difficult to solve even as an LP. What really stands out, though, is that once CPLEX starts branching your node throughput is much lower. In your first run, CPLEX is averaging around 0.3 seconds per node. In your second run, it is around 6.6 seconds per node.

So, in addition to getting rid of the feasibility pump, I would suggest removing the HeurFreq, CutPass and Probe settings, and see if the throughput picks up again. If it does, you can try adding those settings one at a time and see if they help.

Originally posted by: T_O

Please let me add that you should never call a single MIP instance "NP hard". Any single MIP instance can be solved in constant time (obviously).

We call MIP "NP hard", because every problem from NP can be converted in polynomial time to a MIP instance showing that MIP is at least as expressive as NP.