A Lagrangian based branch-and-bound algorithm for production-transportation problems

We propose a branch-and-bound algorithm of Falk-Soland's type for solving t he minimum cost production-transportation problem with concave production c osts. To accelerate the convergence of the algorithm, we reinforce the boun ding operation using a Lagrangian relaxation, which is a concave minimizati on but yields a tighter bound than the usual linear programming relaxation in O(mn log n) additional time. Computational results indicate that the alg orithm can solve fairly large scale problems.