Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Publication
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
Polyhedral Approximations Of Quadratic Semi-Assignment Problems, Disjunctive Programs, And Base-2 Expansions Of Integer Variables, Frank Muldoon
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. …
Convex Hull Characterization Of Special Polytopes In N-Ary Variables, Ruobing Shen
Convex Hull Characterization Of Special Polytopes In N-Ary Variables, Ruobing Shen
All Theses
This paper characterizes the convex hull of the set of n-ary vectors that are lexicographically less than or equal to a given such vector. A polynomial number of facets is shown to be sufficient to describe the convex hull. These facets generalize the family of cover inequalities for the binary case. They allow for advances relative to both the modeling of integer variables using base-n expansions, and the solving of n-ary knapsack problems with weakly super-decreasing coefficients.