Integer Linear Programming Task
An Integer Linear Programming Task is a linear programming task that is a integer programming task and can accept an integer linear optimization program.
- Context:
- It is an NP-hard Task.
- It can be solved by an Integer Linear Programming Algorithm.
- It can range, depending on the Variable Domain,
- from being a Binary Integer Programming Task (BIP), if all of the Unknown Variable are Binary Variables.
- to being a Mixed Integer Programming Task (MIP), if only some Unknown Variables are Integer Variables.
- If only some of the unknown variables are required to be integers, then the problem is called a mixed integer programming (MIP) problem.
- See: Integrality Constraint, ILP Relaxation.
References
2012
- http://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns
- QUOTE: If the unknown variables are all 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.
There are however some important subclasses of IP and MIP problems that are efficiently solvable, most notably problems where the constraint matrix is totally unimodular and the right-hand sides of the constraints are integers.
- QUOTE: If the unknown variables are all 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.
2009
- (Martins et al., 2009) ⇒ André Martins, Noah A. Smith, and Eric P. Xing. (2009). “Concise Integer Linear Programming Formulations for Dependency Parsing.” In: Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP.
- QUOTE: We formulate the problem of non-projective dependency parsing as a polynomial-sized integer linear program.
1998
- (Schrijver, 1998) ⇒ Alexander Schrijver. (1998). “Theory of Linear and Integer Programming." Wiley. ISBN:0471982326
- In this chapter we describe some introductory theory for integer linear programming.
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.
There are however some important subclasses of IP and MIP problems that are efficiently solvable, most notably problems where the constraint matrix is totally unimodular and the right-hand sides of the constraints are integers or – more general – where the system has the total dual integrality (TDI) property.
Advanced algorithms for solving integer linear programs include:
- cutting-plane method.
- branch and bound.
- branch and cut.
- branch and price.
- if the problem has some extra structure, it may be possible to apply delayed column generation.
- Such integer-programming algorithms are discussed by Padberg and in Beasley.
- 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.