Lagrangian decomposition or variable splitting can strengthen the bounds of MILPs by splitting the problem into smaller sub-problems in which the integrality constraints are enforced.

This talk presents our results of applying variable splitting to the fixed cost transportation problem (FCTP) as well as the single commodity fixed charge network flow problem (SCFCNFP). Both of which are flow problems, in which the demand and supply of the vertices in a graph must be obeyed, minimizing a per unit of flow cost and an initial cost on the edges (the initial cost has to be payed if the edge is used in the solution). The experiments include examining how, different decompositions, adding cuts to the sub-problems, and to the master problem, affect the strength of the bounds and performance of the algorithm.