Physical Sciences and Mathematics Commons^™

Polyhedral Approximations Of Quadratic Semi-Assignment Problems, Disjunctive Programs, And Base-2 Expansions Of Integer Variables, Frank Muldoon

All Dissertations

This research is concerned with developing improved representations for special families of mixed-discrete programming problems. Such problems can typically be modeled using different mathematical forms, and the representation employed can greatly influence the problem's ability to be solved. Generally speaking, it is desired to obtain mixed 0-1 linear forms whose continuous relaxations provide tight polyhedral outer-approximations to the convex hulls of feasible solutions. This dissertation makes contributions to three distinct problems, providing new forms that improve upon published works.
The first emphasis is on devising solution procedures for the classical quadratic semi-assignment problem(QSAP), which is an NP-hard 0-1 quadratic program. …