# Bender's Decomposition for Mixed Integer Programs

Say I have 2 LPs, LP_1 and LP_2 which have real and integer variables and a staircase structure (i.e. the solution and feasible region of LP_2 depends on the solution of LP_1).

$LP_1$ has the form

$\min c_1 (x_1 + z_1)$
$s.t.$
$A_1 (x_1 + z_1) = b_1$
$x_1, z_1 \geq 0$
$x_1, \in \mathbb{R^{n_1^{real}}}, z_1 \in \mathbb{Z^{n_1^{int}}}$

and the second LP $LP_2$ has the form

$\min c_2 (x_2 z_2)$
$s.t.$
$A_2 (x_2 + z_2) + E_2 (x_1 + z_1) = b_2$
$x_2, z_2 \geq 0$
$x_2, \in \mathbb{R^{n_2^{real}}}, z_2 \in \mathbb{Z^{n_2^{int}}}$

Given a trial solution $x_1, z_1$, how can I solve $LP_2$ and then generate a cutting plane using Bender's Decomposition to add to $LP_1$? Any advice is appreciated - I believe the answer involves "lifting" though I'm not sure on what it is and why it works.

-