Originally posted by: gtli

Hi, I have a general question about B&B algorithm in CPLEX. Although I know that B&B algorithm is based on solving linear relaxations for nodes in the B&B tree, suppose I have some other way of obtaining lower bounds rather than using the linear relaxations, is there anyway to overwrite the linear relaxation lower bound under the CPLEX B&B algorithm frame? Thanks!

Hypothetically, you could use a branch callback to take over branching. In the callback, ask CPLEX how it would branch (there is a function for that) and create those branches, but with your bounds. The function that creates a branch takes a bounds as an argument. CPLEX will still solve the node LP at a child (unless it is pruned first). I'm not positive, but I think that if your bound is tighter than the LP bound, yours will be used.

Originally posted by: gtli

It seems that the bound won't completely replace the LP relaxation bound, at least in calculating relative gaps.  Thanks!

Well, that's rude of CPLEX! Maybe someone from IBM can comment on it.

Meanwhile, a workaround that might work (but also might make things worse) would be to change minimize f(x) to minimize z with a constraint z = f(x). In the branch constraint, rather than (or in addition to) passing the new objective bound B as an argument, you could also add a new lower bound B for z (in addition to whatever changes are made when separating the node). That should force CPLEX to use B in gap calculations (unless it finds a bound tighter than B).

It's often not a good idea to add a constraint like f(x) >= B to a problem where you are minimizing f(x), because it causes primal degeneracy/multiple dual solutions (or vice versa? -- still waiting for the morning coffee to kick in). I'm not sure if playing the game of minimizing z and tweaking its lower bound avoids that issue or not, but you could try and see.