Minimal covers, minimal sets and canonical facets of the posynomial knapsack polytope. (English) Zbl 0555.90077
The authors investigate the problem of irredundant equivalent representation of 0-1 solution to a posynomial inequality and the facial structure of its convex hull. The results are comparable (but not identical) with those already obtained for the knapsack constraint. In the second part of the paper necessary, sufficient, and necessary and sufficient conditions for a constraint induced by a minimal set to be a canonical facet of the polynomial knapsack polytope are given, where the last conditions are valid only for the inequalities having the simple form \(x_ j\leq 1\).
Reviewer: N.I.Yanev
Keywords:
minimal covers; extended covering constraints; facet; irredundant equivalent representation; posynomial inequality; polynomial knapsack polytopeReferences:
| [1] | Balas, E., Facets of the knapsack polytope, Math. Programming, 8, 146-164 (1975) · Zbl 0316.90046 |
| [2] | Balas, E.; Jeroslow, R., On the structure of the unit hypercube, (MSRR No. 198 (August-December 1969), Carnegie-Mellon University: Carnegie-Mellon University Pittsburgh, PA), published as Canonical cuts on the unit hypercube, SIAM J> Appl. Math. 23 (1972) 61-69 · Zbl 0237.52004 |
| [3] | Glover, F., Unit coefficient inequalities for zero-one programming, (MSRS No. 73-7 (July 1973), University of Colorado: University of Colorado Boulder, CO) |
| [4] | Granot, F.; Hammer, P. L., On the use of boolean functions in 0-1 programming, (ORM No. 70 (August 1970), Technion: Technion Haifa), 154-184, published in: Methods Operations Res. XII (1971) · Zbl 0253.90038 |
| [5] | Hammer, P. L.; Johnson, E. L.; Peled, U. N., Facets of regular 0-1 polytopes, Math. Programming, 8, 179-206 (1975) · Zbl 0314.90064 |
| [6] | Nemhauser, G. L.; Trotter, L. E., Properties of vertex packing and independence system polyhedra, Math. Programming, 6, 1, 48-61 (1974) · Zbl 0281.90072 |
| [7] | Padberg, M. W., On the facial structure of set packing polyhedra, Math. Programming, 5, 199-216 (1973) · Zbl 0272.90041 |
| [8] | Padberg, M. W., A note on zero-one programming, Operations Res., 23, 833-837 (1975) · Zbl 0311.90053 |
| [9] | Padberg, M. W., \((1, k)\)-Configurations and facets for packing problems, Math. Programming, 18, 94-99 (1980) · Zbl 0431.90050 |
| [10] | Wolsey, L. A., Faces for a linear inequality in 0-1 variables, Math. Programming, 8, 165-178 (1975) · Zbl 0314.90063 |
| [11] | Wolsey, L. A., Facets and strong valid inequalities for integer programs, Operations Res., 24, 367-372 (1976) · Zbl 0339.90036 |
| [12] | Zemel, E., Lifting the facets of 0-1 polytopes, Math. Programming, 15, 268-277 (1978) · Zbl 0428.90042 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
