Some Facets of the Tri-Index Assignment Polytope.
Abstract
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 problem's 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1984
- Accession Number
- ADA149195
Entities
People
- E. Balas
- M. J. Saltzman
Organizations
- Carnegie Mellon University