Bilevel Programming and Linear Approximation of Solving Minimum Concave Cost Multicommodity Flow Problem

概要

論文の詳細を見る
A heuristic approach is presented to solve allocation problem of distribution system, which is characterized as Minimum Concave-cost Multi-commodity Flow (MCMF) problem. Such MCMF problem is differentiated into uncapacitated and capacitated problem, as well as single and multisource network. This researh proposes solution of solving capacitated and multisource problem, while Gallo’s algorithm of solving single source and uncapacitated problem is treated to verify the proposed methods. The multisource and uncapacitated problems are solved by bilevel programming which is basically based on the theorem of Destination Spanning Tree, while the capacitated one is solved by linear approximation. Linear approximation is also used to solve uncapacitated problem and confirm the result of bilevel programming. Both methods are represented in Network Representation technique, in which some dummy nodes and links are added to the physical network in order to represent all components of mathematical model. Some cases are discussed to show the application of both methods.