Test sets and inequalities for integer programs: extended abstract
Please always quote using this URN: urn:nbn:de:0297-zib-2021
- This paper presents some connections between test sets and valid inequalities of integer programs. The reason for establishing such relationships is the hope that information (even partial) on one of these objects can be used to get information on the other and vice versa. We approach this study from two directions: On the one hand we examine the geometric process by which the secondary polytope associated with a matrix $A$ transforms to the state polytope as we pass from linear programs that have $A$ as coefficient matrix to the associated integer programs. The second direction establishes the notion of classes of augmentation vectors parallel to the well known concept of classes of facet defining inequalities for integer programs. We show how certain inequalities for integer programs can be derived from test sets for these programs.
Download full text files
Additional Services
| Author: | Rekha R. Thomas, Robert Weismantel |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 1995/12/06 |
| Series (Serial Number): | ZIB-Report (SC-95-36) |
| ZIB-Reportnumber: | SC-95-36 |
| Published in: | Appeared in: Integer Programming and Combinatorial Optimization. 5th Int. IPCO Conf. Vancouver, British Columbia, June, 1996. W. H. Cunningham et al. (eds.) Springer 1996. Lecture Notes in Computer Science, 1084, pp. 16-30 |
