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

In a production-location problem the sum of linear transportation and non-linear concave production cost is to be minimized subject to production capacity and demand constraints. In order to tackle this problem a branch-and-bound algorithm is proposed. The bounding strategy in this algorithm is innovative using a linear programming and Lagrangean relaxation as first and second stage, respectively. The bound obtained by this two-stage approach improves previously known bounds, a theoretical result which is confirmed by numerical tests. The paper is concluded by suggesting an even better bound, which, however, was not tested at the time of publication with numerical data.