  For many mixed-integer programming (MIP) problems, high-quality dual bounds
can be obtained either through advanced formulation techniques coupled with a
state-of-the-art MIP solver, or through semidefinite programming (SDP)
relaxation hierarchies. In this paper, we introduce an alternative bounding
approach that exploits the "combinatorial implosion" effect by solving portions
of the original problem and aggregating this information to obtain a global
dual bound. We apply this technique to the one-dimensional and two-dimensional
floor layout problems and compare it with the bounds generated by both
state-of-the-art MIP solvers and by SDP relaxations. Specifically, we prove
that the bounds obtained through the proposed technique are at least as good as
those obtained through SDP relaxations, and present computational results that
these bounds can be significantly stronger and easier to compute than these
alternative strategies, particularly for very difficult problem instances.
