Integer programming

Integer programming (IP) is a branch of mathematical optimization where some or all of the variables are restricted to be integers.

The most studied special case is integer linear programming (ILP), where the objective function and constraints are linear. Unlike linear programming, where variables can take any real value, the integer constraint makes IP problems significantly harder to solve.

Integer programming is widely used in economics, logistics, production planning, and other fields where variables are inherently discrete (e.g., the number of units produced or the number of employees).

Definition and terminology

A general integer linear programming problem can be written as follows:

Find a vector $x$ that:

maximizes (or minimizes) $c^{T}x$

subject to:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$ (all components of vector $x$ are integers)

where $x$ is the vector of variables, $c$ and $b$ are vectors, and $A$ is the matrix of coefficients.

Depending on the constraints on the variables, the following types of problems are distinguished:

• Pure integer programming: all variables must be integers.
• Mixed-integer programming (MIP): only some of the variables are required to be integers.
• Binary (0-1) programming: variables can only take the values 0 or 1, which allows for modeling "yes/no" logical decisions.

Key properties and complexity

Computational complexity

In the general case, integer linear programming is an NP-hard problem. This means that there is no known algorithm capable of finding an exact optimal solution for an arbitrary IP problem in polynomial time. The difficulty arises from the combinatorial nature of the problem, as the number of possible integer solutions can grow exponentially with the number of variables.

Relationship with linear programming (LP relaxation)

For any IP problem, one can formulate its linear relaxation—a linear programming (LP) problem in which the integer constraint on the variables is dropped. The solution to the LP relaxation has two important properties:

1. It can be found much more quickly (in polynomial time).
2. The optimal value of the objective function of the LP relaxation provides a bound (an upper bound for a maximization problem and a lower bound for a minimization problem) for the optimal value of the original integer problem.

However, simply rounding the fractional solution of the LP relaxation to the nearest integers generally does not lead to an optimal, or even feasible, solution for the integer problem.

Total unimodularity property

There is an important class of ILP problems that can be solved as easily as their LP relaxations. These are problems where the constraint matrix $A$ is totally unimodular (i.e., the determinant of any of its square submatrices is 0, +1, or −1). If the matrix $A$ is totally unimodular and the vector $b$ is integer-valued, then all vertices of the feasible region's polyhedron for the LP relaxation will automatically be integer-valued. Consequently, the solution found by the simplex method will be an integer solution. Examples of such problems include the transportation problem and the assignment problem.

Solution methods

To solve general IP problems that do not possess the total unimodularity property, exact methods based on the idea of implicit enumeration have been developed.

• Branch and Bound — the primary exact method, based on systematically partitioning the set of feasible solutions into subsets (branching) and pruning those subsets that are guaranteed not to contain an optimal solution. LP relaxation is used to estimate the potential of these subsets.

• Cutting Plane Method (Gomory's method) — an iterative approach that sequentially adds new linear constraints ("cuts") to the problem. These cuts "cut off" fractional solutions of the LP relaxation without removing any feasible integer solutions, gradually bringing the feasible region of the LP relaxation closer to the convex hull of the integer solutions.

Modern solvers typically use hybrid algorithms, such as Branch and Cut, which combines the advantages of both approaches.

Examples and applications

Integer programming allows for modeling many classic combinatorial optimization problems.

• Knapsack problem: a classic 0-1 programming problem where one must select a set of items with the maximum total value without exceeding a total weight limit.
• Traveling salesman problem: the problem of finding the shortest route that visits a given set of cities. It can be formulated as an integer programming problem where variables correspond to including graph edges in the final route.

Thanks to its flexibility, IP is one of the most sought-after tools in operations research and is applied in areas such as:

• Logistics and supply chain management: optimizing transportation routes, warehouse placement, and inventory management.
• Production planning: creating production schedules, resource allocation, and equipment loading.
• Finance and economics: portfolio optimization and capital budgeting.
• Telecommunications and energy: designing communication networks and scheduling power plant operations.

See also

• Linear programming
• Branch and Bound