INTERVAL-CONSTRAINED MATRIX BALANCING

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.