We present a penalty-based algorithm that solves the multicommodity flow problem as a sequence of a finite number of scaling phases. The basis of the algorithm is simple and consists of iteratively detecting and sendi...
详细信息
We present a penalty-based algorithm that solves the multicommodity flow problem as a sequence of a finite number of scaling phases. The basis of the algorithm is simple and consists of iteratively detecting and sending flow around negative cost cycles. Two parameters control the algorithm's behavior: the penalty parameter and the scaling parameter. In the epsilon-scaling phase, where epsilon is a function of the penalty and scaling parameters, the algorithm determines an E-optimal solution;a solution in which complementary slackness conditions are satisfied to within epsilon. We analyze the performance of the algorithm from both the theoretical and practical perspectives. The computational results support the theoretical behavior of the algorithm. They also demonstrate the efficiency of the algorithm for solving problem instances of different structure and size.
暂无评论