On the complexity of sequentially lifting cover inequalities for the knapsack polytope

Wei Kun Chen; Yu Hong Dai

doi:10.1007/s11425-019-9538-1

On the complexity of sequentially lifting cover inequalities for the knapsack polytope

Wei Kun Chen, Yu Hong Dai^*

^*Corresponding author for this work

School of Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

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 et al. (1999)). We show that this problem is NP-hard, thus giving a negative answer to the question.

Original language	English
Pages (from-to)	211-220
Number of pages	10
Journal	Science China Mathematics
Volume	64
Issue number	1
DOIs	https://doi.org/10.1007/s11425-019-9538-1
Publication status	Published - Jan 2021

Keywords

90C11
90C27
complexity
integer programming
lifting problem
sequentially lifted cover inequality

Access to Document

10.1007/s11425-019-9538-1

Cite this

@article{e38612ac5bf84372be5acfb00009e3ef,

title = "On the complexity of sequentially lifting cover inequalities for the knapsack polytope",

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 et al. (1999)). We show that this problem is NP-hard, thus giving a negative answer to the question.",

keywords = "90C11, 90C27, complexity, integer programming, lifting problem, sequentially lifted cover inequality",

author = "Chen, {Wei Kun} and Dai, {Yu Hong}",

note = "Publisher Copyright: {\textcopyright} 2020, Science China Press and Springer-Verlag GmbH Germany, part of Springer Nature.",

year = "2021",

month = jan,

doi = "10.1007/s11425-019-9538-1",

language = "English",

volume = "64",

pages = "211--220",

journal = "Science China Mathematics",

issn = "1674-7283",

publisher = "Science Press",

number = "1",

}

TY - JOUR

T1 - On the complexity of sequentially lifting cover inequalities for the knapsack polytope

AU - Chen, Wei Kun

AU - Dai, Yu Hong

PY - 2021/1

Y1 - 2021/1

N2 - 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 et al. (1999)). We show that this problem is NP-hard, thus giving a negative answer to the question.

AB - 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 et al. (1999)). We show that this problem is NP-hard, thus giving a negative answer to the question.

KW - 90C11

KW - 90C27

KW - complexity

KW - integer programming

KW - lifting problem

KW - sequentially lifted cover inequality

UR - http://www.scopus.com/inward/record.url?scp=85083776478&partnerID=8YFLogxK

U2 - 10.1007/s11425-019-9538-1

DO - 10.1007/s11425-019-9538-1

M3 - Article

AN - SCOPUS:85083776478

SN - 1674-7283

VL - 64

SP - 211

EP - 220

JO - Science China Mathematics

JF - Science China Mathematics

IS - 1

ER -

On the complexity of sequentially lifting cover inequalities for the knapsack polytope

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this