Bicriteria Network Optimization Problems

Naoki KATOH  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E75-A   No.3   pp.321-329
Publication Date: 1992/03/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: INVITED PAPER (Special Section on the 4th Karuizawa Workshop on Circuits and Systems)
network algorithms,  multiobjective program,  

Full Text: PDF>>
Buy this Article

This paper presents a survey on bicriteria network optimization problems. When there are two conflicting criteria that evaluate the solution, the bicriteria optimization is to find a solution for which these criteria are both acceptably satisfied. Standard approaches to these problems are to combine these two criteria into an aggregated single criterion. Among such problems, this paper first deals with the case in which the aggregated objective function, denoted h(f1(x), f2(x)), is convex in original two objectives f1(x) and f2(x), and, as its special case, it reviews a strongly polynomial algorithm for the bicriteria minimum-cost circulation problem. It then discusses the case in which h is concave and demonstrates that a parametric approach is effective for this case. Several interesting applications in network optimization that belong to this class are also introduced. Finally we deal with the minimum range problems which seek to find a solution such that weights of the components used in the solution are most uniform. We shall present efficient algorithms for solving these problems arised in network optimization.