Lifting for the integer knapsack cover polyhedron

Wei-Kun Chen (), Liang Chen () and Yu-Hong Dai ()
Additional contact information
Wei-Kun Chen: Beijing Institute of Technology
Liang Chen: Chinese Academy of Sciences
Yu-Hong Dai: Chinese Academy of Sciences

Journal of Global Optimization, 2023, vol. 86, issue 1, No 9, 205-249

Abstract: Abstract We consider the integer knapsack cover polyhedron which is the convex hull of the set consisting of n-dimensional nonnegative integer vectors that satisfy one linear constraint. We study the sequentially lifted (SL) inequality, derived by the sequential lifting from a seed inequality containing a single variable, and provide bounds on the lifting coefficients, which is useful in solving the separation problem of the SL inequalities. The proposed SL inequality is shown to dominate the well-known mixed integer rounding (MIR) inequality under certain conditions. We show that the problem of computing the coefficients for an SL inequality is $$\mathcal{N}\mathcal{P}$$ N P -hard but can be solved by a pseudo-polynomial time algorithm. As a by-product of analysis, we provide new conditions to guarantee the MIR inequality to be facet-defining for the considered polyhedron and prove that in general, the problem of deciding whether an MIR inequality defines a facet is $$\mathcal{N}\mathcal{P}$$ N P -complete. Finally, we perform numerical experiments to evaluate the performance and impact of using the proposed SL inequalities as cutting planes in solving mixed integer linear programming problems. Numerical results demonstrate that the proposed SL cuts are much more effective than the MIR cuts in terms of strengthening the problem formulation and improving the solution efficiency. Moreover, when applied to solve random and real application problems, the proposed SL cuts demonstrate the benefit in reducing the solution time.

Keywords: Integer programming; Cutting plane; Sequential lifting; MIR inequality; Separation algorithm; 90C11; 90C27 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01252-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:86:y:2023:i:1:d:10.1007_s10898-022-01252-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-022-01252-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().