4
$\begingroup$

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: CPLEX 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?

$\endgroup$

1 Answer 1

10
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ If you can upgrade to CPLEX 20.1, the MIP emphasis switch (which previously had values 0 through 4) has a new value (5 = "Heuristic") which one IBM employee has characterized as "heuristics on steroids". That said, I second Erwin's suggestion to cook up a heuristic method of your own to get a starting solution. If you cannot come up with a heuristic that generates a feasible solution, using your knowledge of the model, it's likely the model is infeasible. $\endgroup$
    – prubin
    Jun 18, 2021 at 15:58
  • $\begingroup$ Ok, thanks to both of you! Next days (when I'll have time to work on that problem), I'll try your solutions/hints! $\endgroup$
    – rainbow
    Jun 18, 2021 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.