03. Integer Linear Programming.md

Branch and Bound

The B&B method is a divide and conquer approach where we partition the feasible region into subregions and locally resolve the problem. We begin by dividing the region into subsets and finding a minimum local optimal solution for each of these subsets. Then, we can further partition the subregions recursively and repeat the process. We can determine to stop the partition of a node (subregion) iff:

• proving that it's empty
• the objective function value won't decrease if we search
• finding a local optimal solution

In an ILP case, we initially find the candidate solution for the linear relaxation and then divide it based on its integer approximation.

Gomory Cuts

A Gomory cut is a linear inequality that is used to cut off fractional solutions in a mixed-integer linear programming problem. It is derived from the simplex tableau and is used to restrict the feasible region to only include integer solutions. The idea is to focus on optimal not integer solution and progressively "cut away" fractional parts until reaching integer optimal solution.

We define a Gomory Cut as in the integer form:

$$x_{B[r]}+\sum_{j \mid x_j \in \mathbb{N}}\left\lfloor\bar{a}_{r j}\right\rfloor x_j \leq\left\lfloor\bar{b}_r\right\rfloor$$

and in fractional form:

$$\sum_{j:x_j \in N} ((a_{rj} - \lfloor a_{rj} \rfloor) x_j) \geq (b_r - \lfloor b_r \rfloor)$$

Where $r$ represents a row in matrix $A$, $N$ is the set of non basic variables, and $a$ and $b$ are respectively the left and right hand side coefficients of the equation in the system. The Gomory cut is a cutting plane that is violated by the optimal solution of the linear relaxation, but is satisfied by all the integer solutions of the original problem.

We will add in the Tableau the fraction form of the gomory cut adding a slack variable.

If the ILP has a finite number of optimal solutions, the Cutting Plane Method with Gomory Cuts is guaranteed to find an optimal solution.