Integer linear optimization: Cutting Planes 2

Idea

The Idea of the Cutting Plane is to add Restrictions (the Cutting Planes) to contract the solution space more and more to get integers. These restrictions cut of the non-integer parts of the solution.

Approach

First of all you should divide your restrictions trough the greates common factor.

Example: 6x1 – 15x2 <= 120

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow

3 x1 – 5 x2 <= 40

(1) You search for the continous Optimum with the Simplex Algorithm. If your solution is integer you are finished.

(2) Otherwise you have to insert Cutting Planes

Your source row is the one with the greates non integer part.

Row r:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): BV_r+\sum (a_{ij}*NBV_j) = b_r

Converting r to: You have to break all $a_{rj}$ and $b_{j}$ into the integer part $g_{rj}$ and the rest (non integer) $f_{j}$.

$a_{ij}=g_{ij}+f_{ij}$ $\qquad$ (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0 \leq f_{ij} < 1

)

$b_{i}=g_{i}+f_{i}$ $\qquad$ (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0 \leq f_i < 1

)

We convert r to:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): BV_r+\sum ((f_{rj} + g_{rj})*NBV_j) = g_r + f_r

Take the integer parts on the right side of the formula

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum(f_{rj}*NBV_j) = g_r + f_r - \sum(g_{rj}*NBV_j)-BV_r

Merge the integer parts into the slack variable $y_{neu}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_{neu} = g_r - \sum(g_{rj}*NBV_j)-BV_r