Originally posted by: Rafael Colares

Hello, I am using CPLEX 12.8 with C++ API to solve a MIP.
This MIP has an objective function that looks like min sum(i in I)x[i] , where x[i] are all binary variables. It follows that by definition, any feasible solution has an integer value as objective value.
However, while looking at the log file of cplex, I can see that in many nodes of the Branch and Bound tree, the difference between a candidate solution value and the objective value of the node is less than 1. This means that following this branch is worthless since the best solution I can found from this node will have, at best, the same objective value as my known candidate...

Example : at some node n, I find an objective value of 33.2 while my candidate solution has value 34. I would like to cutoff this node and not look at any descendent nodes from n...

The easiest way I came up with was calling method prune() through a branchCallback. However, activating this kind of callbacks disables Dual Reductions which are particularly strong in my model. Is it possible to do what I am looking for, without disabling such dual reductions?

Thank you in advance!
 

CPLEX should actually do this automatically for you. So it might be better to figure out why it does not do that. When you say "my candidate solution has value 34", does that mean there currently is an incumbent with objective value 34? If not, where does this value 34 come from?

Can you share a log file that shows this problem?

Originally posted by: Rafael Colares

Hi Daniel,

Yes, the value comes from an incumbent solution... In my program I have x variables and y variables and both should be binary (but only x variables appear on the objective function). However, declaring y to be binary, automatically imposes x to be also binary (it also works if I declare only x as binary). This comes from some special mathematical properties of my model that are not relevant for the purpose of this discussion.

You are saying that if I declare both variables (or even just the ones that appear on the objective function) as binaries, cplex would do this on its own? The problem here, is that I have seen some big difference of performances when declaring either just x or just y as binaries...

Example of log_file: node 11651  should have been cutoff...

CPXPARAM_TimeLimit                               7200
CPXPARAM_Threads                                 1
Tried aggregator 1 time.
MIP Presolve eliminated 600 rows and 360 columns.
Reduced MIP has 7980 rows, 5640 columns, and 46560 nonzeros.
Reduced MIP has 3600 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (24.59 ticks)
Found incumbent of value 116.000000 after 0.04 sec. (54.51 ticks)
Probing time = 0.00 sec. (4.13 ticks)
Tried aggregator 1 time.
Reduced MIP has 7980 rows, 5640 columns, and 46560 nonzeros.
Reduced MIP has 5640 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (32.00 ticks)
Probing time = 0.00 sec. (4.13 ticks)
Clique table members: 6900.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.59 sec. (572.22 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

........

  11593  4748       50.9121   374       52.0000       49.1771  7916116    5.43%
  11612  4753       50.9537   383       52.0000       49.1782  7926714    5.43%
Elapsed time = 2786.62 sec. (2944463.98 ticks, tree = 159.38 MB, solutions = 13)
  11633  4755       49.7572   361       52.0000       49.1854  7938361    5.41%
  11651  4761       51.3206   375       52.0000       49.1865  7949110    5.41%
  11672  4770       49.5652   305       52.0000       49.1897  7957791    5.40%
  11692  4775       50.3306   439       52.0000       49.1916  7967539    5.40%

Thank you!

Just to be sure I got this correctly: You don't declare the x variables as binary? They are only "implied binary" because the y variables are binary?

Originally posted by: Rafael Colares

Yes, exactly. I had a look onto CPX_PARAM_OBJDIF and indeed it seems to be what I am looking for... If I got it right, this parameter would cutoff nodes that are at most "CPX_PARAM_OBJDIF" from the current incumbent value? Then, I should set this parameter to 1-EPS, for instance?

Correct, setting to 1-eps should cut off anything that is not at least 1 better than the incumbent.

Maybe CPX_PARAM_OBJDIF is what you are looking for?