Integer programming means that the variables (all or part) in the planning are limited to integers. If the variables in a linear model are limited to integers, it is called integer linear programming. The popular methods for solving integer programming are often only suitable for integer linear programming.

A mathematical programming that requires all or part of the variables in the solution of a problem to be integers. The composition of constraints can be subdivided into linear, quadratic and nonlinear integer programming.

definition

In linear programming problems, some optimal solutions may be fractions or decimals, but for some specific problems, it is often required that the solutions of some variables must be integers. For example, when the variable represents the number of machines, the number of workers or the number of cars loaded, etc. In order to meet the requirements of integers, at first glance, it seems that only the obtained non-integers need to be rounded. In fact, integers are not necessarily feasible optimal solutions, so there should be a special method to solve integer programming.

In integer programming, if all variables are limited to integers, it is called pure integer programming; If only some variables are limited to integers, it is called mixed integer programming. A special case of integer programming is 0 1 programming whose variables are limited to 0 or 1. Unlike linear programming problems, integer and 0 1 programming problems have not yet found a general polynomial solution.

Development history

Since R.E. Gomory put forward the cutting plane method in 1958, integer programming has become an independent branch. In the past 30 years, people have developed many methods to solve various problems. The most typical method to solve integer programming is to generate a related problem step by step, which is called the derivative of the original problem. Every derivative problem is accompanied by a relaxation problem that is easier to solve than it (derivative problem is called the source problem of relaxation problem).

Determine the destination of its source problem by solving the relaxation problem, that is, whether to abandon the source problem or generate one or more of its own derivative problems to replace it. Then, select a derivative problem of the original problem that has not been abandoned or replaced, and repeat the above steps until there are no unresolved derivative problems. At present, the more successful and popular methods are branch and bound method and cutting plane method, both of which are formed under the above framework.