Exact solution of multicommodity network optimization problems with general step cost functions

We describe an exact solution procedure, based on the use of standard LP so ftware, for multicommodity network optimization problems with general disco ntinuous step-increasing cost functions. This class of problems includes th e so-called single-facility and multiple-facility capacitated network loadi ng problems as special cases. The proposed procedure may be viewed as a spe cialization of the well-known BENDERS partitioning procedure, leading to it eratively solving an integer 0-1 linear programming relaxed subproblem whic h is progressively augmented through constraint generation. We propose an i mproved implementation of the constraint generation principle where, at eac h step, several (O(N)) new constraints are included into the current proble m, thanks to which the total number of iterations is greatly reduced (never exceeding 15 in all the test problems treated). We report on systematic co mputational experiments for networks up to 20 nodes, 37 links and cost func tions with an average six steps per link. (C) 1999 Elsevier Science B.V. Al l rights reserved.