3. Integer Programming

Integer Programming

Formally, a integer programming problem can be defined as follows: Input:

• A set of linear constraints, $A\vec{x}\le \vec{b}$.
• A linear objective function, $f:{\mathbb{R}}^n\to \mathbb{R}$. Output: A solution $\vec{x}\in ({\mathbb{Z}}^{\ge 0}{)}^n$ such that:

1. $\vec{x}$ satisfies the constraints $A\vec{x}\le \vec{b}$
2. $f(\vec{x})$ is maximal

Example: Maximal Matchings

Given the situation below: We want to maximise the number of connections in the graph.

1. For each edge $(i,j)$ between worker $i$ and task $j$, let $x_{i,j}$ be some numerical value. We also add the constraint $x_{i,j}\le 1$ for all edges $(i,j)$.
2. Construct a constraint for each worker $i\in \{a,b,c,d,e,f\}$. $x_{i,A}+x_{i,B}+x_{i,C}+x_{i,D}\le \text{capacity of }i$
3. Construct a constraint for each task $j\in \{A,B,C,D\}$. $x_{a,j}+x_{b,j}+x_{c,j}+x_{d,j}+x_{e,j}+x_{f,j}\ge \text{requirements for }j$
4. Add an objective to maximise the number of connections: $\text{Maximise }{\sum }_{i,j}{x}_{i,j}$
5. An optimal solution to the resulting integer program corresponds to the maximal matching of workers to tasks.

Integer Programming is NP-hard

Theorem: SAT is polynomially reducible to the Integer Programming problem. Proof: Given a formula $F$ in CNF:

1. We want to construct an integer program $I{P}_F$ such that: $F\text{ is satisfiable}⟺I{P}_F\text{ has an integer solution}$
2. For each propositional variable $P$, let $x_P$ and $x_{\neg P}$ be numerical variables.
3. Convert each clause into a linear constraint: $\boxed{\begin{array}{c}(P\vee Q\vee \neg R)\\ (\neg P\vee Q\vee R)\\ (\neg Q\vee S)\end{array}}\to \boxed{\begin{array}{c}(x_p+x_q+x_{\neg r})\ge 1\\ (x_{\neg p}+x_q+x_r)\ge 1\\ (x_{\neg q}+x_s)\ge 1\end{array}}$
4. For each propositional variable, add the following constraint:

&= 1 \ x_r + x_{\neg r} &= 1 \ x_s + x_{\neg s} &= 1 \end{aligned}$$

5. We can easily verify that: $F\text{ is satisfiable}⟺I{P}_F\text{ has an integer solution}$ Hence $\text{SAT}{\le }_p\text{IP}$.

Branch-and-Bound

Branch-and-Bound (Algorithm)

$\text{BRANCH-AND-BOUND}(LP)$:

1. Find a solution $\vec{a}$ to the linear relaxation of $LP$.
2. If $\vec{a}\in {\mathbb{Z}}^n$: Return solution $\vec{a}$
3. Otherwise choose a non-integer $x_i=a_i$ on which we branch.
   1. Let ${\vec{a}}_L=BRANCH-AND-BOUND(LP\cup \{x_i\le \lfloor a_i\rfloor \})$
   2. Let ${\vec{a}}_R=BRANCH-AND-BOUND(LP\cup \{x_i\ge \lceil a_i\rceil \})$
   3. If $f({\vec{a}}_L)\ge f({\vec{a}}_R)$: Return solution ${\vec{a}}_L$
   4. Else return solution ${\vec{a}}_R$

Link to original

Likely will not come up on an exam.

Or otherwise, we would be provided with a calculator. You can use https://www.zweigmedia.com/utilities/lpg/ to calculate these.

An example is shown below:

Other Variants of Linear Programming

• Mixed Integer Linear Programming (MLP): Hybrid of an integer program and a classic linear program Some variables are required to be integers but not all
• Zero-one integer programming A restriction of Integer Programming where all variables can either be zero or one