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.
• Context:
  • It can be solved by a Mixed Integer Programming System that can solve a Mixed Integer Programming Algorithm.
• See: Mixed Integer Program, Linear Programming.

---

---

References

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.

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.

---

---