Locally Ideal LP Formulations II

In this chapter we continue our investigations into the locally ideal linearization of the major problem classes from Chapters 1 and 2. In particular, we study here the VLSI circuit layout design problem, a general model that comprises all BQPSs considered so far, the quadratic assignment problem and its symmetric relative. Except for the symmetric quadratic assignment problem, complete characterizations of the associated local polytopes are obtained. Like in the case of our results of Chapter 4, these local polytopes are of interest on their own whenever the substructures that we study occur in a quadratic zero-one optimization problem. In all cases we obtain from the locally ideal linearization formulations of the respective problems that in most cases improve on existing formulations for these problems.