Our website is made possible by displaying online advertisements to our visitors.
Please consider supporting us by disabling your ad blocker.
Integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear.
Integer programming is NP-complete. In particular, the special case of 0–1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.[1]
If some decision variables are not discrete, the problem is known as a mixed-integer programming problem.[2]
- ^ Karp, Richard M. (1972). "Reducibility among Combinatorial Problems" (PDF). In R. E. Miller; J. W. Thatcher; J.D. Bohlinger (eds.). Complexity of Computer Computations. New York: Plenum. pp. 85–103. doi:10.1007/978-1-4684-2001-2_9. ISBN 978-1-4684-2003-6.
- ^ "Mixed-Integer Linear Programming (MILP): Model Formulation" (PDF). Retrieved 16 April 2018.
Previous Page Next Page
برمجة الأعداد الصحيحة Arabic Programació lineal entera Catalan Celočíselné programování Czech Heltalsprogrammering Danish Ganzzahlige lineare Optimierung German Programación en enteros Spanish بهینهسازی خطی عدد صحیح FA Optimisation linéaire en nombres entiers French Pemrograman integer ID 整数計画問題 Japanese
