Some Facets of the Tri-Index Assignment Polytope.
Management science research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
Given three disjoint n-sets and the family of all weighted triplets that contain exactly one element of each set, the 3- index assignment or 3-dimensional matching problem asks for a minimum-weight subcollection of triplets that covers exactly i.e., partitions the union of the three sets. Unlike the common 2-index assignment problem, the 3-index problem is NP-complete. In this paper we examine the facial structure of the 3-index assignment polytope the convex hull of feasible solutions to the problem with the aid of the intersection graph of the coefficient matrix of the problems constraint set. In particular, we describe the cliques of the intersection graph as belonging to three distinct classes, and show that cliques in two of three classes induce inequalities that define facets of our polytope. Furthermore, we give an 0 n to the 4th power procedure note that the number of variables is n cubed for finding a facet-defining clique-inequality violated by a given noninteger solution to the linear programming relaxation of the 3-index assignment problem, or showing that no such inequality exists.
- Theoretical Mathematics