Lifting cover inequalities for the precedence-constrained knapsack problem

This paper considers the polyhedral structure of the precedence-constrained knapsack problem, which is a knapsack problem with precedence constraints imposed on the set of variables. The problem itself appears in many applications. Moreover, since the precedence constraints appear in many important integer programming problems, the polyhedral results can be used to develop cutting-plane algorithms for more general applications. In this paper, we propose a modification of the cover inequality, which explicitly considers the precedence constraints. A combinatorial, easily implementable lifting procedure of the modified cover inequality is given. The procedure can generate strong cuts very easily. We also propose an additional lifting procedure, which is a generalization of the lifting procedure for cover inequalities. Some properties of the lifted inequality are analyzed and the problem of finding an optimal order of lifting is also addressed.
Publisher
ELSEVIER SCIENCE BV
Issue Date
1997-02
Language
ENG
Citation

DISCRETE APPLIED MATHEMATICS, v.72, no.3, pp.219 - 241

ISSN
0166-218X
URI
http://hdl.handle.net/10203/7579
Appears in Collection
IE-Journal Papers(저널논문)
  • Hit : 475
  • Download : 16
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 14 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0