Compact Extended Linear Programming Models by Giuseppe Lancia & Paolo Serafini

Author:Giuseppe Lancia & Paolo Serafini
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham

The Dantzig–Wolfe decomposition works as follows. We have to solve an ILP problem of the following form

(6.34)

where is a finite, although very large, set. Let , i.e.,

(6.35)

and suppose also that the external description of P is given by

(6.36)

Taking into account (6.35) the convex relaxation of (6.34) can be written as

(6.37)

If we restrict to be binary then (6.37) is exactly (6.34). The new formulation of ( ) has the drawback of requiring a very large number of variables. However, this drawback is compensated in many cases by the fact that we have split the problem constraints in (6.34) into the explicit constraints and the implicit constraints and it is possible to deal with them separately as we are going to show. Since the number of variables is very large we have to employ a column generation technique. The dual of (6.37) is

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.