\input zb-basic
\input zb-ioport
\iteman{io-port 01488895}
\itemau{Yang, X.Q.; Mees, A.I.; Campbell, K.}
\itemti{Simulated annealing and penalty methods for binary multicommodity flow problems.}
\itemso{Yang, Xiaoqi (ed.) et al., Progress in optimization. Contributions from Australasia. Papers of the 5th optimization days (OD) mini-conference, Univ. of Western Australia, Perth, Australia, June 29-30, 1998. Dordrecht: Kluwer Academic Publishers. Appl. Optim. 39, 93-105 (2000).}
\itemab
Summary: Multicommodity Flow (MCF) problems are an important class of combinatorial optimisation problems which can be used to model practical situations such as computer networks, traffic systems and warehouse allocation. The discrete MCF problem is NP-Hard. Many methods have been presented which attempt to find solutions to combinatorial problems such as the discrete MCF problem within a reasonable time frame. In this paper we look at the binary MCF problem and its representation using linear and nonlinear penalty methods. We implement the simulated annealing algorithm to find approximate solutions to the minimum cost problem, and compare the performance of variants of the algorithm on a set of test networks. Simulated annealing requires the definition of a neighborhood of a solution: to enable this, we introduce the painted multi-path algorithm.
\itemrv{~}
\itemcc{}
\itemut{multicommodity flow; simulated annealing; painted multi-path algorithm; network optimization; penalty function}
\itemli{}
\end