Valid Inequalities, Cutting Planes, and Integrality of the Knapsack Polytope

Stefan M. Stefanov ()
Additional contact information
Stefan M. Stefanov: South-West University Neofit Rilski

Chapter Chapter 14 in Separable Optimization, 2021, pp 265-280 from Springer

Abstract: Abstract In this chapter, the so-called knapsack problem and knapsack polytopeKnapsackpolytope, defined by linear inequality/inequalities and bounds on the variables, are considered. Some important concepts and preliminaries are given at the beginning. As we have observed, knapsack polytope is a feasible region of some problems considered in Part One and Part Two of this book. Some results connected with the generation of valid and dominating inequalities (including the modular arithmetic approach) and cutting planes are presented. Necessary and sufficient conditions are also proved for the knapsack polytope to be integral. Such integrality criteria are useful because the optimal solution to a linear programming problem, when it is solvable, is attained at a vertex of the feasible polytope/polyhedron, and in the case of integrality of the knapsack polytope, the integer problem and the corresponding continuous problem have the same solution(s).

Date: 2021
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spochp:978-3-030-78401-0_14

Ordering information: This item can be ordered from
http://www.springer.com/9783030784010

DOI: 10.1007/978-3-030-78401-0_14

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().