INTERVAL-CONSTRAINED MATRIX BALANCING

被引:7
作者
CENSOR, Y [1 ]
ZENIOS, SA [1 ]
机构
[1] UNIV PENN,WHARTON SCH,DEPT DECIS SCI,PHILADELPHIA,PA 19104
基金
美国国家科学基金会;
关键词
D O I
10.1016/0024-3795(91)90182-V
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We define two interval-constrained matrix balancing problems. The models encompass several known formulations of problems that appear in regional input-output analysis, estimation of traffic over transportation and telecommunications networks, and estimation of social accounting matrices. We develop primal-dual, row-action algorithms for the solution of these models and establish their convergence. Both algorithms generalize existing scaling algorithms for equality-constrained matrix balancing problems. One of the algorithms is a generalization of the well-known procedure for matrix balancing called RAS that can handle the range constraints (and is thus called Range-RAS). The structure of the problem makes the algorithm suitable for implementation on massively parallel computers. Details of our implementation on a Connection Machine CM-2 are given. Numerical results for the solution of problems of size up to 500 x 500 are given, and the performance of the algorithm is compared with that of RAS.
引用
收藏
页码:393 / 421
页数:29
相关论文
共 26 条
[1]  
Bachem A., 1981, Metrika, V28, P273, DOI 10.1007/BF01902901
[2]   RAS-ALGORITHM [J].
BACHEM, A ;
KORTE, B .
COMPUTING, 1979, 23 (02) :189-198
[3]  
BACHEM A, 1981, UNTERNEHMENSPLANUNG, P117
[4]   AN AXIOMATIC APPROACH TO PROPORTIONALITY BETWEEN MATRICES [J].
BALINSKI, ML ;
DEMANGE, G .
MATHEMATICS OF OPERATIONS RESEARCH, 1989, 14 (04) :700-719
[5]   ALGORITHMS FOR PROPORTIONAL MATRICES IN REALS AND INTEGERS [J].
BALINSKI, ML ;
DEMANGE, G .
MATHEMATICAL PROGRAMMING, 1989, 45 (02) :193-210
[6]  
Bertsekas DP., 1989, PARALLEL DISTRIBUTED
[7]  
BLELLOCH GE, 1988, THESIS MIT CAMBRIDGE
[8]   ESTIMATION OF LARGE SOCIAL ACCOUNT MATRICES [J].
BYRON, RP .
JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES A-STATISTICS IN SOCIETY, 1978, 141 :359-367
[9]   AN ITERATIVE ROW-ACTION METHOD FOR INTERVAL CONVEX-PROGRAMMING [J].
CENSOR, Y ;
LENT, A .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1981, 34 (03) :321-353
[10]  
CENSOR Y, 1990, NUMERICAL ANAL MATH, P145