\part{Integer programming}

\chapter{Integer programs}

Some optimization problems require solutions to be integers; such an optimization problem is called an \emph{integer program (IP)}. There are different types of IPs that one may encounter.
\begin{itemize}
	\item Pure IP; All variables are restricted to $\mathbb{Z}$
	\item Binary IP; All variables are restricted to $\{0,1\}$
	\item Mixed IP; Some ariables are restricted to $\mathbb{Z}$
\end{itemize}

This part will only consider Linear integer programs for simplicity.


\chapter{Branch-and-bound method}

\section{Main idea}
A naive approach of a 'first approximation' is to relax any integer number requirements to real number requirements and solve the relevant LP.
Imagine the index $\mathbf{x}_j$ of the 'optimal solution' is not an integer, we \emph{branch} into two 'subproblems' with additional constraints $\mathbf{x}_{j} \leq \lfloor \mathbf{x}_{j} \rfloor$ and $\mathbf{x}_{j} \geq \lfloor \mathbf{x}_{j} \rfloor +1$ respectively.



When a subproblem yields an 'integer optimal solution', it i called a candidate solution, since it has potential to be the overall solution. THis subproblem can't be improved further, so we call it 'fathomed'. We also fathom subproblems that are infeasible or unbounded.


The best candidate solution is called the 'incumbent solution', and the incumbent solution once all subproblems have been fathomed is the optimal solution.

With candidate solutions, for min problems, our optimal value is \emph{bounded} by the optimal value of the current incumbent solution's optimal value. Therefore, if a subproblem produces a result above this value, it fails to replace the incumbent solution. If it is less than this bound and it is an integer solution, it becomes the new incumbent solution.

\section{Algorithm}

\chapter{Hungarian method}

Assignment problem

\[X = \{ (\mathbf{X} : m\times m ) :  \sum^{m}_{j=1} X_{ij}  \land \sum^{m}_{i=1} X_{ij} \land \mathbf{X}_{ij} \in \{0,1\} \}\]
\[f(\mathbf{X}) =\sum^{m}_{i=1} \sum^{m}_{j=1} \mathbf{C}_{ij} \mathbf{X}_{ij}\]

It gets its name due to the amount of Hungarian mathematicians working on the problem (the martians)



\chapter{Cutting plane method}
pick row in final tableau with RHS not an integer
Add 'the cut' of this row as a new constraint, continue with dual simplex method
Repeat until integer solution obtained