Facets of the Three-Index Assignment Polytope. Revision.
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 this paper examines the facial 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 the three classes induce inequalities that define facets of our polytope. Furthermore, we give an O (to the 4th power) procedure (note that the number of variables is cubed) for finding a facet-defining cliques-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. We then describe the odd holes of the intersection graph and identify two classes of facets associated with odd holes that are easy to generate. One class has coefficients of 0 or 1, the other class coefficients of 0, 1 or 2. No odd hole inequality has left hand side coefficients greater than two. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1986
- Accession Number
- ADA176142
Entities
People
- Egon Balas
- Matthew J. Saltzman
Organizations
- Carnegie Mellon University