Mixed Integer Programming

An Integer Programming problem is a mathematical optimization problem of which some or all of the variables are limited to be integral numbers. In a lot of settings the term Integer Programming refers to Integer Linear Programming also known as mixed integer programming. Integer programming is NP-hard. A special case is the 0-1 integer linear programming, in which the unknown values are binary. This is one of the 21 NP-complete problems of Karp.

In linear programming problems, all the variables are real numbers. In problems constrains and the function remain linear, but some or all of the variables are integers. So while linear programming has continuous variables, Integer programming has discrete (integer) variables and Binary Integer programming problems have binary variables. Mixed Integer programming problems have discrete and continuous variables, examples are numbers, 0/1 decisions. Non-linear conditions can be formulated as linear. (if-then conditions) Integer problems are much harder to solve than continuous problems. Discrete problems are often NP-complete. (no polygonal algorithm) The amount of solutions is limited in most cases, but limited can still be a large number.

Some examples of Integer Programming problems are: designing distribution networks, transportation planning, determination of series size in production, shift-schedules, frequency assignment in telecommunication, gate distribution in the aviation industry and determining the consistency of software releases.

To avoid any confusion, the simplex method, which can be used for normal linear programming problems, is not enough for solving integer linear programming problems. There are also no dual integer linear programming models and there are no sensitivity analyses that can be applied to integer linear programming models. In short; most of the common methods for solving linear programming problems, cannot be applied to integer programming.

A concrete example of an integer programming problem is the knapsack problem. In the knapsack problem there is a bag that can carry a maximum amount of kilograms. Then there are a few items that you want to fit in the bag. Every item has its own weight and its own value. The objective here is to a few items in the bag with the highest possible value possible. The decision problem form of the knapsack problem lies in the question: Can a value of at least X be achieved without exceeding the weight Y. The knapsack problem is a fairly simple and imaginative example of the knapsack problem. Most real life problems are far more complex.

For more information regarding , please visit