Mix Integer Linear Programming

Mixed integer linear programming (MIP) refers to an integer linear programming in which one part of the decision variables must be integer and the other part can not take integers.

A linear optimization problem is a problem of the following form:

Minimize or maximize the objective function

$MAX(min)z=\sum_{j=1}^{n}c_{j}x_{j}$

subject to the constraints

$\begin{array}{c} &s.t.\quad\begin{cases}\sum\limits_{j=1}^n a_{ij}x_j \leq (or \geq, =) b_i & (i=1,2,3,\cdots, m)\\x_j \geq 0 & (j=1,2,3,\cdots,n)\end{cases} \end{array}$

Among them, some or all of , , ..., are integers

Many typical problems also reflect the wide background of integer programming. For example, Knapsack (or loading) problem, Fixed cost problem, effective expedition problem (coverage problem of Combinatorics), delivery problem, etc. Therefore, the application scope of integer programming is also extremely wide. It has many applications not only in industrial and engineering design and scientific research, but also in computer design, system reliability, coding and economic analysis. At present, the branch and bound method and cut plane method are two successful methods to solve integer programming problems .