Originally posted by: gtoptimizer

Hey all,

What is the formula used to compute the "estimated integer objective *" for a node in a branch-and-cut tree (assuming it is common knowledge)?

Is this the same value based on which the "Best Estimate" node selection strategy chooses the next node to process?

Thanks in advance!

* as returned by CPXgetcallbacknodeinfo with whichinfo equal to CPX_CALLBACK_INFO_NODE_ESTIMATE

Originally posted by: EdKlotz

The specifics of the node estimate calculation for the estimated integer objective CPLEX uses is not publicized.   Here's the fundamental idea.  Best estimate looks at the node LP objective, then adjusts it to account
for the number and sum of integer infeasibilities to derive an adjusted objective that estimates the likely objective
of an integer feasible solution found at the node.   Thus, in a minimization problem, a node LP with an objective of 150
and one integer infeasibility of value 10 is likely to have a more favorable estimated objective than another node LP with
objective 130 but with 100 integer infeasibilities with sum of infeasibilities of 1000.   By contrast, best estimate node
selection just considers the node LP objective values of 150 and 130 without considering the amount of integer
infeasibility repair needed to find an integer feasible solution.
 

Regarding publicly known strategies for calculating node estimates, try

Land, A. and Powell, S., Computer codes for problems of integer programming, in P.L. Hammer, E.L. Johnson, and B.H. Korte, editors, Discrete Optimization II, Annals of Discrete Mathematics Volume 5, North Holland, Amsterdam, 1979, pages 221-269.

More generally, for a list of papers that contain information about some of the foundational ideas on which CPLEX is based, take a look at https://www-304.ibm.com/support/docview.wss?uid=swg21400019

Originally posted by: gtoptimizer

Thanks! Very useful references.