Integer programming: Difference between revisions

Content deleted Content added
No edit summary
Tags: Reverted Visual edit
Reverting edit(s) by 150.242.16.66 (talk) to rev. 1244641219 by 185.104.138.52: test edits (RW 16.1)
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|integersinteger]]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 |last=Karp |first=Richard M. |author-link=Richard M. Karp |title=Complexity of Computer Computations |publisher=New York: Plenum |year=1972 |isbn=978-1-4684-2003-6 |editor=R. E. Miller |pages=85–103 |chapter=Reducibility among Combinatorial Problems |doi=10.1007/978-1-4684-2001-2_9 |editor2=J. W. Thatcher |editor3=J.D. Bohlinger |chapter-url=http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf}}</ref>
| 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 |title=Mixed-Integer Linear Programming (MILP): Model Formulation |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>
 
<u>==Canonical and standard form for ILP(Interger Linear Programming)</u>ILPs==
 
<u>Canonical and standard form for ILP(Interger Linear Programming)</u>
 
In integer linear programming, the ''canonical form'' is distinct from the ''standard form''. An integer linear program in canonical form is expressed thus (note that it is the <math>\mathbf{x}</math> vector which is to be decided):<ref name="optBook">{{cite book|last1=Papadimitriou|first1=C. H.|author1-link=Christos Papadimitriou|last2=Steiglitz|first2= K.|author2-link=Kenneth Steiglitz|title=Combinatorial optimization: algorithms and complexity|year=1998|publisher=Dover|___location=Mineola, NY|isbn=0486402584}}</ref>