A simplicial branch-and-bound algorithm for productiontransportation problems with inseparable concave production cost

In this paper, we develop a simplicial branch-and-bound algorithm for gener-ating globally optimal solutions to concave minimization problems with low rank nonconvex structures. We propose to remove all additional constraints imposed on the usual linear programming relaxed problem. Therefore, in each bounding operation, we solve a linear programming problem whose constraints are exactly the same as the target problem. Although the lower bound worsens as a natu-ral consequence, we oset this weakness by using an inexpensive bound tightening procedure based on Lagrangian relaxation. After giving a proof of the convergence, we report a numerical comparison with existing algorithms