Abstract
We now turn to the subject of integer linear programming, or integer programming for short. integer programming, which permits non-integer values of the solution variables, is known to be “easy” in the sense of having known algorithms with worst-case runtime that is polynomial in the size of the problem instance. By contrast, integer programming (as well as the hybrid known as mixed integer linear programming) requires that at least some solution variables have their values restricted to be integers. The problem then becomes “hard”: there is no known algorithm that guarantees a worst-case runtime that is polynomial in the instance size.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
T. C. Hu, L. Landa, and M.-T. Shing, “The Unbounded Knapsack Problem,” Research Trends in Combinatorial Optimization, 2009, pp. 201–217.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Hu, T.C., Kahng, A.B. (2016). The Knapsack Problem. In: Linear and Integer Programming Made Easy. Springer, Cham. https://doi.org/10.1007/978-3-319-24001-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-24001-5_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23999-6
Online ISBN: 978-3-319-24001-5
eBook Packages: EngineeringEngineering (R0)