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. In this type, 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. 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 find the biggest value we can from a group of whole numbers, while following some rules.

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

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.

Main article: Convex hull See also: Projection into simplex

Proof of NP-hardness

Integer programming is a hard problem to solve quickly because it is NP-hard. This means solving it is very tough, like one of the hardest problems in computer science.

We can show this by connecting integer programming to another problem called the minimum vertex cover. In a graph, a vertex cover is a group of points (vertices) where every line connecting two points (an edge) includes at least one point from this group. We can make an integer programming problem to find the smallest vertex cover using special rules. If we solve this integer programming problem, we also solve the vertex cover problem, showing 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 solve it without the rule that answers must be whole numbers, and then round the result. However, this might not give the best answer or even a valid answer.

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 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 often has many empty spaces. This is called sparse. This happens a lot when the matrix has a block structure, which is common in real-world uses. In 2018, researchers found that integer programming can be solved faster when looking at the empty spaces in the matrix. This means the time it takes to solve the problem depends on some features of the matrix, not every detail, which makes it quicker for big problems.