Sensitivity analysis for knapsack problems: A negative result. (English) Zbl 0895.90155
Summary: We show that, for any pair of knapsack problems, there is a single problem whose optimal solution corresponds to each problem of the pair, for two adjacent right-hand sides.
MSC:
| 90C27 | Combinatorial optimization |
| 90C31 | Sensitivity, stability, parametric optimization |
| 90C09 | Boolean programming |
References:
| [1] | Babayev, D. A.; Glover, F., Aggregation of nonnegative integer-valued equations, Discrete Appl. Math., 8, 125-130 (1984) · Zbl 0536.90064 |
| [2] | Babayev, D. A.; Mardanov, S. S., Sequential and simultaneous aggregation of diophantine equations, Discrete Appl. Math., 50, 209-220 (1994) · Zbl 0801.11014 |
| [3] | Blair, C., Sensitivity analysis for knapsack problems: a negative result, (Working Paper 96-131 (September 1996), University of Illinois Bureau of Economics and Business Research) · Zbl 0895.90155 |
| [4] | Bradley, G. H., Transformation of integer programs to knapsack problems, Discrete Math., 1, 29-45 (1971) · Zbl 0219.90033 |
| [5] | Elimam, A.; Elmaghraby, S., On the reduction method for integer programs, Discrete Appl. Math., 12, 241-260 (1985) · Zbl 0607.90063 |
| [6] | Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco · Zbl 0411.68039 |
| [7] | Glover, F., New results on equivalent integer programming formulations, Math. Programming, 8, 84-90 (1975) · Zbl 0303.90040 |
| [8] | Glover, F.; Babayev, D. A., New results for aggregating integer-valued equations, Ann. Oper. Res., 58, 227-242 (1995) · Zbl 0836.11010 |
| [9] | Greenberg, H., A new reduction method in integer programming, Discrete Appl. Math., 21, 169-172 (1988) · Zbl 0664.90063 |
| [10] | Padberg, M. W., Equivalent knapsack-type formulation of bounded integer programs: an alternative approach, Naval Res. Logist. Quart., 19, 699-708 (1972) · Zbl 0251.90028 |
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.
