Linear programming – link to NP-complete problem

It is not possible to add the new link because it would replace an existing, longer link.

Line 1:

== Integer unknowns ==

If all of the unknown variables are required to be integers, then the problem is called an [[integer programming]] (IP) or '''integer linear programming''' (ILP) problem. In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in many practical situations (those with bounded variables) [[NP-hard]]. '''0–1 integer programming''' or '''binary integer programming''' (BIP) is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This problem is also classified as NP-hard, and in fact the decision version was one of [[Karp's 21 NP-complete ~~problems~~]].

If only some of the unknown variables are required to be integers, then the problem is called a '''mixed integer (linear) programming''' (MIP or MILP) problem. These are generally also NP-hard because they are even more general than ILP programs.

@@ Line 1: / Line 1: @@
 == Integer unknowns ==
-If all of the unknown variables are required to be integers, then the problem is called an [[integer programming]] (IP) or '''integer linear programming''' (ILP) problem.  In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in many practical situations (those with bounded variables) [[NP-hard]]. '''0–1 integer programming''' or '''binary integer programming''' (BIP) is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This problem is also classified as NP-hard, and in fact the decision version was one of [[Karp's 21 NP-complete problems]].
+If all of the unknown variables are required to be integers, then the problem is called an [[integer programming]] (IP) or '''integer linear programming''' (ILP) problem.  In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in many practical situations (those with bounded variables) [[NP-hard]]. '''0–1 integer programming''' or '''binary integer programming''' (BIP) is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This problem is also classified as NP-hard, and in fact the decision version was one of Karp's 21 [[NP-complete problem]]s.
 If only some of the unknown variables are required to be integers, then the problem is called a '''mixed integer (linear) programming''' (MIP or MILP) problem.  These are generally also NP-hard because they are even more general than ILP programs.