Integer programming

Integer programming is a section of mathematical programming in which all or some of the variables are additionally subject to a restriction of integerness .

The simplest method for solving an integer programming problem is to reduce it to a linear programming problem with checking the result for integer.

Boolean programming
The special case of the problem of integer linear programming includes problems where the variables X can take on only two values ​​— 0 and 1. The corresponding problems are often called problems of Boolean programming. The most well-known of these tasks are the assignment problem (which employee should be assigned to which job), the route selection problem (the traveling salesman problem, the postman's task), the maximum matching problem, etc. Integer programming is used to solve the development problem of a company in which 0 or 1 means the purchase of any equipment.

To solve problems of this type, specific algorithms are being developed based on combinatorics, graphs, etc.

Integer linear programs can be expressed either in canonical form or standard form (both as defined below), which are different from each other. An integer linear program in canonical form is expressed thus (note that it is the x vector which is to be decided)

and an ILP in standard form is expressed as

where are vectors and is a matrix. As with linear programs, ILPs not in standard form can be converted to standard form by eliminating inequalities, introducing slack variables (s) and replacing variables that are not sign-constrained with the difference of two sign-constrained variables.