SOLVING MULTICOMMODITY INTEGRAL FLOW PROBLEMS BY SIMULATED ALLOCATION

The paper discusses a stochastic approach. called Simulated Allocation (SA), to the capacitated and uncapacitated multicommodity integral fl ow allocation problems. Since such problems are in general NP-complete , effective heuristic approaches are of interest, and SA is one of the m. The idea of SA has its origin in discrete event simulation of alter native call routing in telecommunication networks. We describe an impl ementation of SA and illustrate its effectiveness by means of numerica l examples including multiple knapsack problem and network design. Num erical experiments indicate that SA is capable of bypassing local mini ma of the problem objective function, and allows for achieving reasona ble solutions in a reasonable time.