CPLEX log always the same after hours ("Gap" and "Best Integer" always blanks)

Question

I'm using the Java API of CPLEX 12.6.1 (with license) to solve a MILP (Mixed-Integer Linear Programming) maximization problem.

The point is that, after 21 hours, CPLEX has consumed 32 GB of RAM and the whole (30 GB) Swapping Memory.

While CPLEX runs I'm able to see its "log" output, and I saw that:

• the "Gap" coloumn is always blank;
• the "Best Integer" coloumn is always blank;

so, no solution has been found.

Moreover (after the first few seconds where it changes a bit), the value in "Best Bound" coloumn is always the same (equal to 52.2911) during the 21 hours.

This is the beginning of the CPLEX output LOG:

How could I solve this problem?

I already increased the absolute and the relative MIP GAP (I set both of them to 0.1), but without solving.

Are there any parameters which can I tune to help CPLEX to find a solution?

Answer 1

Diagnosis: Cplex can not find a feasible solution. Interesting, as 1788 binary variables is not extremely large.

You can play a bit with mipemphasis option. (In general, I am not a fan of using all kinds of solver options, but this option is one of the very few I use on a regular basis). May be fpheur (feasibility pump) is also worth looking at.

There are also other things you can do:

• Make the model more elastic. I.e. relax (some) constraints while putting penalties in the objective. Branch-and-bound algorithms work much better once there is a feasible solution. Also, this method may find some borderline infeasible solutions that are acceptable.

• Try to invent a heuristic that can construct an initial feasible solution, and pass this on using MIPSTART. This may or may not be a difficult task.

Of course, if your model has no integer feasible solution, nothing will work. Unfortunately, proving a MIP model is integer infeasible is often quite difficult and time-consuming.