Abstract: In this paper, a new algorithm relaxation-strategy-based modification branch-and-bound algorithm is developed for a type of solving the minimum cost transportation production problem with concave production costs. The major improvement of the proposed new method is that modification algorithm reinforces the bounding operation using a Lagrangian relaxation, which is a concave minimization but obtains a tighter bound than the usual linear programming relaxation. Some computational results are included. Computation results indicate that the algorithm can solve fairly large scale problems. 

Key words: branch-and-bound algorithm, transportation-production problem, Lagrangian
relaxation