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

• Published in: Operations research letters 1999-08, Vol.25 (1), p.15-23
• Main Authors: Gabrel, V., Knippel, A., Minoux, M.
• Format: Article
• Language: English
• Subjects: Applied sciences; Benders method; Computer Science; Exact sciences and technology; Flows in networks. Combinatorial problems; Multicommodity flows; Multiple constraint generation; Operational research and scientific management; Operational research. Management science; Optimum network design
• ISSN: 0167-6377; 1872-7468
• DOI: 10.1016/S0167-6377(99)00020-6

We describe an exact solution procedure, based on the use of standard LP software, for multicommodity network optimization problems with general discontinuous step-increasing cost functions. This class of problems includes the so-called single-facility and multiple-facility capacitated network loading problems as special cases. The proposed procedure may be viewed as a specialization of the well-known BENDERS partitioning procedure, leading to iteratively solving an integer 0–1 linear programming relaxed subproblem which is progressively augmented through constraint generation. We propose an improved implementation of the constraint generation principle where, at each step, several (O( N)) new constraints are included into the current problem, thanks to which the total number of iterations is greatly reduced (never exceeding 15 in all the test problems treated). We report on systematic computational experiments for networks up to 20 nodes, 37 links and cost functions with an average six steps per link.