Mixed Integer Linear Programming Task
A Mixed Integer Linear Programming Task is a integer programming task that accepts a mixed integer program (a integer program that is a mixed mathematical optimization program with both linear equality and inequality constraints.).
- AKA: MIP, MILP.
- Context:
- It can be solved by a Mixed Integer Programming System (that implements a Mixed Integer Programming Algorithm).
- See: Mixed Integer Program, Linear Programming.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/integer_programming#Variants Retrieved:2015-6-20.
- Mixed integer linear programming (MILP) involves problems in which only some of the variables, [math]\displaystyle{ x_i }[/math] , are constrained to be integers, while other variables are allowed to be non-integers.
Zero-one linear programming involves problems in which the variables are restricted to be either 0 or 1. Note that any bounded integer variable can be expressed as a combination of binary variables. For example, given an integer variable, [math]\displaystyle{ 0\le x\le U }[/math], the variable can be expressed using [math]\displaystyle{ \lfloor \log_2U\rfloor+1 }[/math] binary variables: : [math]\displaystyle{ x = x_1+2x_2+4x_3+\ldots+2^{\lfloor \log_2U\rfloor}x_{\lfloor \log_2U\rfloor+1}. }[/math]
- Mixed integer linear programming (MILP) involves problems in which only some of the variables, [math]\displaystyle{ x_i }[/math] , are constrained to be integers, while other variables are allowed to be non-integers.
2010
- http://www.aimms.com/operations-research/mathematical-programming/mixed-integer-programming/
- Mixed integer programming (MIP) problems involve the Optimization of a linear objective function, subject to linear equality and inequality constraints. Some or all of the variables are required to be integer. Mixed integer programming problems are in general more difficult to solve than linear programming problems but AIMMS Integer Programming Software is equipped with the best high-performance solvers available.
1997
- http://www.cs.sandia.gov/opt/survey/mip.html
- QUOTE: A mixed-integer program is the minimization or maximization of a linear function subject to linear constraints.
- QUOTE: A mixed-integer program is the minimization or maximization of a linear function subject to linear constraints.
T
minimize c x
subject to A x = b
1 1
A x <= b
2 2
l <= x <= u for i = 1 … n
i i i
x_j integer for all j in D which is a subset of {1...n},
where A is a m x n matrix, A is an m x n matrix, m + m = m.
1 1 2 2 1 2
- If all the variables can be rational (the set D is empty), this is a linear programming problem, which can be solved in polynomial time. In practice linear programs can be solved efficiently for reasonable-sized problems, or even for big problems with special structure. However when some or all of the variables must be integer, corresponding to pure integer and mixed integer programming respectively, the problem becomes NP-complete (formally intractible).
- For the sake of this discussion, assume that all variables must be integral. The general methods can be easily extended to the mixed-integer case.