Originally posted by: QiuFeng

Hi guys, I have 2 confusions about CPXgetbestobjval.

1.

According to the manual: The routine CPXgetbestobjval accesses the currently best known bound of all the remaining open nodes in a branch & cut tree.

But the manual also says: for a MIP "when a problem has been solved to optimality, this value matches the optimal solution value. "

I understand that Branch&Bound process stops when LB = UB . But sometimes the UB is obtained(in a minimization problem) by heuristics. In this case, the LB might always be smaller than the UB. If this happens, the value returned by CPXgetbestobjval can not match the optimal solution value.

2.

CPXgetsolnpoolobjval will return the incumbent if -1 is specified in the arguments. I guess the optimal solution is the incumbent at the end of Branch&Bound process, frequently.
However, in my experiments, there are always difference between the value returned by CPXgetbestobjval and the value by CPXgetsolnpoolobjval. CPXgetsolnpoolobjval is always 0.001-0.003 bigger than CPXgetbestobjval. Is this because the accuracy or I missed something here.

Thanks in advance!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

1. In a minimization problem, CPXgetbestobjval() will return the best known global lower bound for the objective function (this may in some cases actually be a bit larger than the best LP bound of all remaining open nodes; the manual will be corrected with the next CPLEX version). A MIP has been solved to optimality, if it has been proven that no better solution than the current incumbent exists. This means that CPXgetbestobjval() will return the same objective value as the incumbent value. So, the statement in the manual is correct. How the incumbent has been found (by heuristics, as a MIP start, or as LP solution in the tree) is irrelevant for this question.

2. Yes, CPXgetsolnpoolobjval() will return the incumbent objective value if you specify -1 as the solution number. The incumbent is the best feasible solution found so far in the optimization process. At the end of the solving process, this is then of course the optimal solution to the problem instance.
The fact that in your case the incumbent value and the best dual bound differ slightly is most probably the effect of the "mipgap" parameter. This parameter is set to 1e-4 by default, which means that the optimization process stops whenever the relative difference between the incumbent value and the dual bound is smaller than 1e-4. If your objective values are at least 10, then an absolute difference of 0.001 is within the mipgap tolerance. In this case, your solution status should be "optimal within tolerances" rather than "optimal". You can continue the search to find the optimal solution (or prove the optimality of the current incumbent) by setting the "mipgap" parameter to 0.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: QiuFeng

Thank you, Tobias.

Here is another related question:

I'm try to record all the feasible solutions found during branch&bound. I was using incumbent callback to do that. Incumbent call back function is supposed to be called whenever an integer solution is found, as described in the manual.

However, Looking at the feasible solutions I recorded, I noticed that the solutions found later always has a better objective value than those found earlier in B&B process. This is "surprising" to me because I don't see why the feasible solutions are found in an objective-improving order. How CPLEX can do this? Or is that because the callback is called only when an integer solution with better objective value is found? If this is the case, How can I record all feasible solutions found during branch&bound?

Thanks a lot!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

When CPLEX finds a solution, it will implicitly set an objective cutoff. This means that all inferior solutions will be treated as infeasible by CPLEX, and consequently, CPLEX will only produce a chain of solutions with improving objective value.

If you want to collect solutions, you can use the incumbent callback as you described. But there is a much easier way since CPLEX 11: the solution pool. If you want to have all solutions that CPLEX discovered while solving the problem, just set the solution pool capacity to infinity, and after the solve stopped, query the solutions from the pool.

If you really want to have all feasible solutions to your problem, you need to use the "populate" feature of CPLEX, together with the solution pool as described above. You can set the populate parameters in such a way that all solutions are accepted, even the ones with very bad objective value.

Note that "all" solutions has a very special meaning if continuous variables are involved. Namely, if there are continuous variables, you will typically have an infinite amount of feasible solution vectors. Of course, CPLEX cannot generate all of those. "All" for CPLEX only means all combinations of values for the integer variables for which at least one assignment to the continuous variables exist to make the overall solution vector feasible. For each integer variable assignment, CPLEX will use an optimal assignment to the continuous variables to complement the solution.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: QiuFeng

Thanks! populate is what I'm using now. Setting solution capacity to infinity and solving it may fit my purpose better. I'm trying to track all solutions found by CPLEX during B&B. In the progress report printed out to screen, there is a line periodically showing up,
"Elapsed real time = 4564.52 sec. (tree size = 333.09 MB, solutions = 1.7e+05)"
The "solutions" here means improving solutions? or all solutions cplex found so far?

thanks and have a good weekend!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The "solutions = x" line denotes the total number of solutions that have been added to the solution pool (some of them may have been discarded due to the solution pool capacity). For regular search, this is the number of improving solutions found, but with populate this is the total number of solutions found for your model, because populate also generates sub-optimal solutions.
#CPLEXOptimizers
#DecisionOptimization