Originally posted by: MarekGrzes

Hello,

An example output of the MIP solver is below. It solves a tiny MIP problem where I use HeuristicCallback to improve the current integer solution. In this particular example, my heuristic improves the solution at the very beginning, but the value of the Best Integer solution printed in the subsequent iterations is not affected. Is that correct? I would expect the Best Integer column in the log to be at least as high as the integer value that I compute in my HeuristicCallback? Also, I would expect that B&B pruning should take my new lower bound found value into account as well. I use the following method in the HeuristicCallback to pass the new solution to cplex:

protected void setSolution(ilog.concert.IloNumVar[] ,
                           double[] ,
                           double )

I verified my code and I cannot see a bug. Perhaps the log that I see is a normal thing, but then, it would mean that B&B does not use my improved lower bound for pruning? Please see part of my question in the log below as well (in bold).

Thank you,
Marek



Probing time =    0.00 sec.
Clique table members: 2.
MIP emphasis: balance optimality and feasibility.
MIP search method: traditional branch-and-cut.
Parallel mode: none, using 1 thread.
Root relaxation solution time =    0.00 sec.

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap         Variable B NodeID Parent  Depth

*     0+    0                          -11.0000                      8     ---
      0     0        6.6113     4      -11.0000        6.6113        8  160.10%
Warning: Control callbacks may disable some MIP features.

(HERE, MY HEURISTIC CALLBACK FINDS AN INTEGER SOLUTION WITH THE VALUE OF 0.7026. WHY THE IMPROVED LOWER BOUND DOES NOT SHOW UP IN THE ITERATIONS THAT FOLLOW? IS IT USED FOR PRUNING BY B&C?)

*     0+    0                           -2.1893        6.6113        8  401.98%
      0     0        5.4608     5       -2.1893      Cuts: 17       18  349.44%
      0     0        5.0458     9       -2.1893       Cuts: 6       27  330.48%
      0     0        4.1427     8       -2.1893      Cuts: 10       35  289.23%
      0     0        3.6090     8       -2.1893       Cuts: 9       39  264.85%
      0     0        3.3056     4       -2.1893    MIRcuts: 5       42  250.99%
*     0+    0                            0.0000        3.3056       42     ---
      0     0        3.3023     6        0.0000       Cuts: 2       44     ---
      0     0        3.0609     6        0.0000    MIRcuts: 3       48     ---
*     0+    0                            0.1725        3.0609       48     ---
      0     0        2.9431     5        0.1725       Cuts: 4       51     ---
      0     0        2.9398     7        0.1725       Cuts: 3       53     ---
      0     0        2.8151     8        0.1725    MIRcuts: 3       58     ---
      0     0        2.6437     5        0.1725       Cuts: 8       65     ---
      0     0        2.5164     9        0.1725       Cuts: 8       70     ---
*     0+    0                            0.7026        2.5164       70  258.15%
      0     0        cutoff              0.7026        0.7026       70    0.00%                        0             0
Elapsed real time =  52.83 sec. (tree size =  0.00 MB, solutions = 5)

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MarekGrzes

Hello,

I would like to add that my implementation is in Java.

In the meantime, I found out that setSolution() requires all variables, i.e., I need to sent all variables that I have in my model combined in one array. In my initial implementation, I was forwarding integer variables and their values only. Unfortunately, cplex keeps ignoring my integer solution even if I forward all variables and their values to setSolution(). Is there any way to display the exact reason why integer solution is ignored by cplex?

Thanks,

Marek

 

#CPLEXOptimizers
#DecisionOptimization

When you say your heuristic callback finds an integer-feasible solution "here", how sure are you that the callback is called between the preceding and following output lines? In my experience, the display/print of System.out can lag behind other threads.

The docs say that a heuristic callback, if present, is called

... after each node subproblem has been solved, including any cuts that may have been newly generated.

Everything in the output you showed occurred at the root node, and your incumbent (0.7026) did indeed appear at or near the end of root node processing. The earlier lines reflect CPLEX adding cuts it derived from the root LP, and that (properly) occurs before the heuristic callback is called.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MarekGrzes

#CPLEXOptimizers
#DecisionOptimization

I forgot that a heuristic callback is handled differently at the root node than at other nodes (called earlier and more often). I agree that the log suggests your solution is not being accepted by CPLEX. Since CPLEX eventually finds an incumbent with what seems to be the same objective value as the first heuristic solution, it seems that your solution is mostly correct. I just wonder if perhaps there is a tolerance problem with it.

Here's an experiment that might shed some light. When your heuristic callback is called the first time, record the new solution in memory and abort the solver. Use IloCplex.addMIPStart to set your heuristic solution as a starting incumbent, and call solve again. Early in the log you will get a message saying either that the solution is accepted or rejected (or possibly accepted after repair). If the message is not that it is accepted, then we'll know that CPLEX does not believe your solution is feasible.

An alternative to use addMIPStart, which might be more informative, would be to fix the lower and upper bounds of the variables at the values specified by the heuristic solution and then run the conflict refiner to see if there is a conflict (and, if so, where the conflict lies).

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MarekGrzes

Dear Paul,

Thank you for your reply. addMIPStart is indeed a good way of verifying feasibility.

Best,

Marek

#CPLEXOptimizers
#DecisionOptimization