Mixed Integer Linear Programming Task

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

(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]

   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.