Integer programming: Difference between revisions

Revision as of 05:36, 21 May 2023

Revision as of 16:11, 29 May 2023

Line 2:

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]]{{Reference needed|date=May 2023}}. 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]].

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>