Integer programming: Difference between revisions

Revision as of 06:16, 30 September 2024

Revision as of 06:17, 30 September 2024

Line 1:

{{Short description|A mathematical optimization problem restricted to integers}}

An '''integer programming''' problem is a [[mathematical optimization]] or [[Constraint satisfaction problem|feasibility]] program in which some or all of the variables are restricted to be [[integer]]s. 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 function (calculus)|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]].<ref>{{cite book

| first = Richard M. |last = Karp

|chapter = Reducibility among Combinatorial Problems

| author-link = Richard M. Karp

| chapter-url = http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf

| title = Complexity of Computer Computations

| editor = R. E. Miller |editor2=J. W. Thatcher |editor3=J.D. Bohlinger

| publisher = New York: Plenum

| pages = 85–103

| year = 1972

| doi = 10.1007/978-1-4684-2001-2_9

| isbn = 978-1-4684-2003-6

}}</ref>

If some decision variables are not discrete, the problem is known as a '''mixed-integer programming''' problem.<ref>{{cite web |url=http://macc.mcmaster.ca/maccfiles/chachuatnotes/07-MILP-I_handout.pdf |title=Mixed-Integer Linear Programming (MILP): Model Formulation |access-date=16 April 2018}}</ref>

Canonical and standard form for ILP(Interger Linear Programming)