Loading...
Please wait, while we are loading the content...
Similar Documents
On the complexity of sequentially lifting cover inequalities for the knapsack polytope
| Content Provider | Semantic Scholar |
|---|---|
| Author | Chen, Wei-Kun Dai, Yu-Hong |
| Copyright Year | 2018 |
| Abstract | The well-known sequentially lifted cover inequality is widely employed in solving mixed integer programs. However, it is still an open question whether a sequentially lifted cover inequality can be computed in polynomial time for a given minimal cover (Gu, Nemhauser, and Savelsbergh, INFORMS J. Comput., 26: 117--123, 1999). We show that this problem is NP-hard, thus giving a negative answer to the question. |
| File Format | PDF HTM / HTML |
| DOI | 10.1007/s11425-019-9538-1 |
| Alternate Webpage(s) | https://arxiv.org/pdf/1811.10010v2.pdf |
| Alternate Webpage(s) | https://doi.org/10.1007/s11425-019-9538-1 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
