New Exact Techniques Applied to a Class of Network Flow Formulations

We propose a number of solution techniques for general network flow formulations derived from Dantzig-Wolfe decompositions. We present an arc selection method to derive reduced network flow models that may potentially provide good feasible solutions. This method is explored as a variable selection rule for branching. With the aim of improving reduced-cost variable-fixing, we also propose a method to produce different dual solutions of network flow models and provide conditions that guarantee the correctness of the method. We embed the proposed techniques in an innovative branch-and-price method for network flow formulations, and test it on the cutting stock problem. In our computational experiments, 162 out of 237 open benchmark instances are solved to proven optimality within a reasonable computational time, consistently improving previous results in the literature.