Mixed Integer Linear Programming Task

From GM-RKB
(Redirected from MIP)
Jump to navigation Jump to search

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.).



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]

2010

1997

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.