Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$
$ 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.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.