A capacitated multi-commodity network design problem: A solution method for finding a lower bound using valid inequalities

Network design problems with multi-commodities and capacitated links, such as communication networks, road networks, transportation networks and so on, are often experienced. They are translated so-called capacitated multi-commodity network design problems. The authors present a new solution method for finding a lower bound of the capacitated multi-commodity network design problem. A lower bound is used for branch and bound solution methods and for the guarantee of heuristic solution precision. The present new lower bound solution method consists; (1) finding cutset constraints from cutsets on the network; (2) finding cutting plains derived from cutset constraints; (3) approximately finding dual solutions of the problem with cutting planes. Numerical examples are given to illustrate efficiency of the solution method. [In Japanese.]