Integer programming: Difference between revisions

Revision as of 03:45, 21 May 2023

Revision as of 05:36, 21 May 2023

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]]. A good example of mixed integer linear programming (MILP) is railway crew scheduling problem, which is a classic NP-hard and nondeterministic polynomial time problem.<ref>{{Cite journal |last=Pang |first=Shinsiong |last2=Chen |first2=Mu-Chen |date=2023-06-01 |title=Optimize railway crew scheduling by using modified bacterial foraging algorithm |url=https://www.sciencedirect.com/science/article/pii/S0360835223002425 |journal=Computers & Industrial Engineering |language=en |volume=180 |pages=109218 |doi=10.1016/j.cie.2023.109218 |issn=0360-8352}}</ref>

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]].