The formulations and results presented here (and in Section 4.1) have been implemented and obtained using the Mosel algebraic modeling language (version 1.4.1) and the default version of the Xpress-MP Optimizer MIP solver (version 15.30). In particular the separation algorithm used to generate the (l, S) inequalities (4.13) has been directly coded in Mosel. See http://www.dashoptimization.com for more information about this software. All the tests reported here have been carried out on a 1.7 GHz PC (centrino) with 1 GB of RAM running under Windows XP

Apart from the multi-commodity reformulation, the reformulations of the single-item problems WW-U and LS-U used here are studied in detail in Chapter 7. The WW-CC reformulation is studied in Chapter 9. Appropriate references to these results are given in these chapters. An introduction to the techniques used to prove that some valid inequalities suffice to describe the convex hull of solutions to a model is given in Section 6.4. For a general presentation of the various techniques that can be used to prove that some valid inequalities are facet defining, and for related topics, we refer the reader to Nemhauser and Wolsey [126]

Sections 4.1 The multi-commodity reformulation for fixed charge network flow problems, implemented and tested in Section 4.1.1, was proposed by Rardin and Choe [145].

Section 6.4 A simple example demonstrating the different convex hull proof techniques can be found in Section 6.2 of Wolsey [193]. The classical primal dual method (5) is due to Edmonds [60], and the very useful approach (8) isattributed to Lovasz [109]. Total unimodularity is also treated in most of the books cited above. Proposition 6.6 is due to Ghoula-Houri [74].

Apart from the multi-commodity reformulation, the reformulations of the single-item problems WW-U and LS-U used here are studied in detail in Chapter 7. The WW-CC reformulation is studied in Chapter 9. Appropriate references to these results are given in these chapters. An introduction to the techniques used to prove that some valid inequalities suffice to describe the convex hull of solutions to a model is given in Section 6.4. For a general presentation of the various techniques that can be used to prove that some valid inequalities are facet defining, and for related topics, we refer the reader to Nemhauser and Wolsey [126].