Integer Programs

The special methods we’ve learned so far to solve linear problems work for continuous problems, in which the variables can take any real value. However, there are some problems in which variables should be integers.

Integer problems

For example, when we want to know the number of workers needed to accomplish a task or the number of soda cans a business owner should buy for their store, the solution can’t be a fraction. It should be an integer number.

Linear problems that are restricted to integer solutions are commonly called integer problems, and the field that studies the solution to those problems is integer programming. Formally, these problems are defined as linear problems with an additional constraint.

$$\begin{gathered} \underset{\mathbf{x}}{\min }\mathbf{c}{\mathbf{x}}^{\mathrm{\top }} \\ s\mathrm{.}t\mathrm{.}:P{\mathbf{x}}^{\mathrm{\top }}\le \mathbf{p} \\ Q{\mathbf{x}}^{\mathrm{\top }}=\mathbf{q} \\ \mathbf{x}\in {\mathbb{Z}}^n \end{gathered}$$ ...