Integer programming

Integer programming is a special kind of math problem where we try to find the best solution, but some of the answers have to be whole numbers — like counting one, two, or three items, instead of fractions like half an apple. This makes the problem trickier to solve than regular math puzzles where answers can be any number.

One common type is called integer linear programming, where both the goal and the rules of the problem are straight-line equations, but the answers still need to be whole numbers. This kind of problem shows up in many real-life situations, like figuring out the best way to pack things into boxes or deciding how many of each product to make in a factory.

Integer programming is very hard to solve quickly, especially when the answers must be either zero or one — like yes or no choices. This version is one of a group of famously difficult problems in computer science, which means that finding fast answers gets much harder as the puzzles grow bigger. Sometimes, not all variables need to be whole numbers, leading to what's called mixed-integer programming.

Canonical and standard form for ILPs

Integer linear programs can be written in two main ways: canonical form and standard form. In canonical form, we try to make the largest possible value from a set of whole numbers, while following certain rules.

To change a problem into standard form, we might add extra helper numbers called slack variables to turn rules that say “less than or equal to” into rules that say “equals.” This makes solving the problem easier for computers.

Example

This example shows a problem where we want to find the best whole number answers. We look for points that follow certain rules, like not going past lines on a graph. The best whole number answers here are (1, 2) and (2, 2), both giving the same top score. The best point if we allowed any numbers would be (1.8, 2.8), but this does not use whole numbers and so is not allowed here.

Main article: Convex hull See also: Projection into simplex

Proof of NP-hardness

Integer programming is a challenging problem to solve quickly because it is NP-hard. This means that solving it is as hard as solving one of the toughest problems in computer science.

To show this, we can connect integer programming to another problem called the minimum vertex cover. In a graph, a vertex cover is a set of points (vertices) such that every line connecting two points (an edge) includes at least one point from this set. We can create an integer programming problem that finds the smallest vertex cover by using special rules. If we solve this integer programming problem, we also solve the vertex cover problem, proving how difficult integer programming can be.

Variants

Mixed-integer linear programming (MILP) is a type of problem where only some numbers need to be whole, while others can be any number. This makes solving the problem more flexible.

Zero–one linear programming, also called binary integer programming, is a special case where numbers can only be 0 or 1. Any whole number can be shown using just 0s and 1s, which helps in solving many different kinds of problems.

binary variables

Applications

Integer programming is used when we need to make exact calculations or decisions, like counting whole numbers. For example, you can't build half a car, so we need to use whole numbers when planning how many cars to make.

This type of math helps with many real-world problems. It can be used to plan how farms grow crops without using more resources than they have. It also helps schedule buses and trains, making sure each route has the right vehicle and driver. It can even design phone networks, deciding how many lines to use and how strong they should be. All these problems need exact numbers, which is why integer programming is so useful.

Main articles: graph, production planning, GSM, Cash flow matching, Energy system, UAV, guidance, Transit map, layouting

Algorithms

The simplest way to solve an integer programming problem is to ignore the rule that answers must be whole numbers, solve it normally, and then round the result. However, this might not give the best answer or even a valid answer that meets all the rules.

One special case where rounding works perfectly is when the problem’s setup has a property called “total unimodularity.” If this is true, a common solving method called the simplex algorithm will naturally give whole-number answers without any rounding needed.

When total unimodularity doesn’t apply, more advanced techniques are used. One approach is the “branch and bound” method, which systematically checks possible whole-number combinations. Another is the “cutting plane” method, which adds new rules to the problem step by step to push the answer closer to whole numbers. These methods can guarantee finding the best possible answer, though they might take longer for very complex problems.

For problems with only a few variables, there are clever shortcuts. For example, when there are just two variables to solve, scientists found a way in 1981 to solve it efficiently. Even for more variables, there are methods that break the problem into smaller, easier pieces to solve.

Sparse integer programming

In integer programming, the matrix that defines the problem is often sparse, meaning it has many empty spaces. This happens especially when the matrix has a block structure, which is common in many real-world uses. Researchers found in 2018 that integer programming can be solved more efficiently when considering the sparsity of the matrix. This means the time it takes to solve the problem depends on certain features of the matrix, not on all the details, making it faster for large problems.