Solving multicommodity integral flow problems by simulated allocation

Michał Pióro , Piotr Gajowniczek

Abstract

The paper discusses a stochastic approach, called Simulated Allocation (SA), to the capacitated and uncapacitated multicommodity integral flow allocation problems. Since such problems are in general NP‐complete, effective heuristic approaches are of interest, and SA is one of them. The idea of SA has its origin in discrete event simulation of alternative call routing in telecommunication networks. We describe an implementation of SA and illustrate its effectiveness by means of numerical examples including multiple knapsack problem and network design. Numerical experiments indicate that SA is capable of bypassing local minima of the problem objective function, and allows for achieving reasonable solutions in a reasonable time.
Author Michał Pióro (FEIT / IT)
Michał Pióro,,
- The Institute of Telecommunications
, Piotr Gajowniczek (FEIT / IT)
Piotr Gajowniczek,,
- The Institute of Telecommunications
Journal seriesTelecommunication Systems, ISSN 1018-4864, [1572-9451 (electronic version)]
Issue year1997
Vol7
No1-3
Pages17-28
Keywords in EnglishArtificial Intelligence (incl. Robotics), Business Information Systems, Computer Communication Networks, Probability Theory and Stochastic Processes
ASJC Classification2208 Electrical and Electronic Engineering
DOIDOI:10.1023/A:1019151707785
URL http://link.springer.com/article/10.1023/A%3A1019151707785
Languageen angielski
File
1997 Pióro Gajowniczek Solving multicommodity integral flow.pdf 200.33 KB
Score (nominal)20
Score sourcejournalList
Publication indicators WoS Citations = 8; GS Citations = 34.0; Scopus SNIP (Source Normalised Impact per Paper): 2014 = 1.174; WoS Impact Factor: 2006 = 0.33 (2) - 2007=0.577 (5)
Citation count*34 (2020-05-27)
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?