We present a cutting-plane algorithm to improve the lower bounds for the multicommodity capacitated fixed charge network design problem. Specifically, the cutting-plane method incorporates generalizations of well-known valid inequalities, as well as new families, all based on cutsets of the network. We present experimental results showing the effectiveness of the cutting-plane procedure and the impact of individual cut families in terms of computational time and lower bound improvement.

We consider a multi-echelon location-distribution problem arising from an actual application in fast delivery service. We propose a heuristic that exploits a simple plant location relaxation of a MIP formulation of the problem to solve a large-scale actual application. The heuristic combines DUALOC with a variable neighborhood descent.

Cutset inequalities are an important family of valid inequalities for network design problems. This article presents a lifting procedure to strengthen cutset inequalities by solving shortest-path problems. It also shows that cutset inequalities are a special case of a more general class of inequalities, known as feasibility constraints, for which the lifting procedure is also valid. A Benders decomposition framework is used to show the efficiency of the procedure both for the general feasibility constraints and for the cutset inequalities.