Integer Programming Task
Jump to navigation
Jump to search
An Integer Programming Task is a mathematical optimization task that accepts an integer optimization program.
- Example(s):
- Counter-Example(s):
- See: Constraint Satisfaction Problem, Linear Programming, NP-Hard, Karp's 21 NP-Complete Problems.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/linear_programming#Integer_unknowns Retrieved:2015-12-24.
- 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 programming (MIP) problem. These are generally also NP-hard because they are even more general than ILP programs. …
- 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.
2014
- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/integer_programming Retrieved:2014-9-26.
- An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. 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.
Integer programming is NP-hard. A special case, 0-1 integer linear programming, in which unknowns are binary, is one of Karp's 21 NP-complete problems.
- An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. 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.