Integer linear optimization: Cutting Planes 4

Idea

The cutting plane algorithm was developed in 1950 by Delbert Ray Fulkerson and George Dantzig and later costumized by Egon Balas and Ralph Gomory. Today it is one of the standart methodes for solving a integer optimisation problem. The basic idea behind this methode is to treat your linear programm not as usual as an integer linear programm. Instead you should consider it as a LP-Relaxation and add further inequalities untill an integer solution is found.

Example

max $x_{1}+2x_{2}$

s.t. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2x_{1}+x_{2} \leq 10

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{1}+x_{2} \leq 5

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1} \leq 4

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}\geq0

integer

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}\geq0

integer