On the Boolean Quadric Forest Polytope

We study the Boolean Quadric Forest Polytope, namely, the convex hull of the "extended" edge incidence-vectors of forests of a complete graph "extended" by the usual linearization of the quadratic terms. Our motivation is to provide a mathematical foundation for attacking the minimum quadratic-cost forest problem via branch-and-cut methods of in eger programming.We determine several families of facets of the Boolean Quadric Forest Polytope and relate them to the Boolean Quadric Polytope as well as the Forest Polytope. We give polynomial-time separation procedures for some of the families

By: Jonathan Lee, Janny Leung

Published in: INFOR Journal, volume 42, (no 2), pages 125-141 in 2004

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .