Sandwich approach

• LP opt solution provides lb

• Any feasible ip solution

provides a ub

Let zk be opt solution at node k

If zk integral and < zbest, new zbest

Otherwise

zk >= zbest, “fathom” node

the search tree is reduced

or

zk < zbest, “branch”

the search tree grows

zLP

zbest IP

zopt

Previous slide

Next slide

Back to first slide

View graphic version