In this paper a quadratic programming problem is considered. It contains, as special cases, formulations of constrained matrix problems with unknown row and column totals, and classical spatial price equilibrium problems with congestion. An equilibration algorithm, which is of the relaxation type, is introduced into the problem. It resolves the system into subproblems, which in turn, can be solved exactly, even in the presence of upper bounds. Also provided is computational experience for several large-scale examples. This work identifies the equivalency between constrained matrix problems and spatial price equilibrium problems which had been postulated, but, heretofore, not made.
Get full access to this article
View all access options for this article.
References
1.
BacharachM, 1970Biproportional Scaling and Input-Output Change (Cambridge University Press, Cambridge)
2.
BachemAKorteB, 1978, “Algorithm for quadratic optimization over transportation polytopes”Zeitschrift für angewandte Mathematik und Mechanik58T459–T461
3.
BachemAKorteB, 1980, “Minimum norm problems over transportation polytopes”Linear Algebra and Its Applications31102–118
4.
BattenD, 1983Spatial Analysis of Interacting Economies (Kluwer-Nijhoff, Boston, MA)
5.
BoyceD EHewingsG J D, 1980, “Interregional commodity flow, input-output and transportation modelling: an entropy formulation”, paper presented at the First World Regional Science Congress, Cambridge, MA; copy available from D E Boyce, Department of Civil Engineering, University of Illinois, Urbana, IL, USA
6.
CottleR W, 1984, “Application of a block successive overrelaxation method to a class of constrained matrix problems”, Mathematical Programming Eds CottleR WKelmansonM LKorteB (North-Holland, Amsterdam) pp 89–103
7.
CottleR WDuvallS GZikanK, 1986, “A Lagrangean relaxation algorithm for the constrained matrix problem”Naval Research Logistics Quarterly3355–76
8.
DaceyM PNorcliffeA, 1977, “A flexible doubly-constrained trip distribution model”Transportation Science11203–204
9.
DafermosSNagurneyA, 1985, “Isomorphism between spatial price and traffic network equilibrium models”, LCDS 85–17, Brown University, Providence, RI
10.
DafermosSNagurneyA, forthcoming, “Supply and demand equilibration algorithms for a class of market equilibrium problems”, to appearTransportation Science
11.
DafermosSSparrowF T, 1969, “The traffic assignment problem for a general network”Journal of Research of National Bureau of Standards73B(2) 91–118
12.
ErikssonJ, 1980, “A note on solution of large sparse maximum entropy problems with linear equality constraints”Mathematical Programming18146–154
13.
ErlanderSJornstenK OLundgrenJ T, 1985, “On the estimation of trip matrices in the case of missing and uncertain data”Transportation Research19B(2) 123–141
14.
FreundDSaxenaU, 1984, “An algorithm for a class of discrete maximum entropy problems”Operations Research33210–215
15.
GuderF, 1987, “Pairwise reactive SOR algorithm for quadratic programming of transshipment spatial price equilibrium problems”, forthcomingMathematical Programming
16.
HallefjordAJornstenK, 1985, “A note on relaxed gravity models”Environment and Planning A17597–603
17.
HallefjordAJornstenK, 1986, “Gravity models with multiple objectives—theory and applications”Transportation Research20B19–40
18.
HarriganFBuchananI, 1984, “Quadratic programming approach to input-output estimation and simulation”Journal of Regional Science24(3) 339–358
19.
HarriganFMcNicollI, 1986, “Data use and the simulation of regional input-output matrices”Environment and Planning A181061–1076
20.
HewingsG J D, 1984, “The role of prior information in updating regional input-output models”Socio-Economic Planning Science18319–336
21.
JeffersonT RScottC H, 1979, “The analysis of entropy models with equality and inequality constraints”Transportation Research13B123–132
22.
JonesP CSaigalRSchneiderM, 1986, “A variable dimension homotopy on networks for computing linear spatial equilibria”Discrete Applied Mathematics13131–156
23.
KimT JBoyceD EHewingsG J D, 1980, “Combined input-output and commodity flow models for inter-regional development planning: insights from a Korean application”Geog. Anal.15330–342
24.
LecomberJ R, 1975, “A critique of methods of adjusting, updating, and projecting matrices”, Estimating and Projecting Input-Output Coefficients Eds AllenR I GGosslingW F (Input-Output Publishing Company, London) pp 1–25
25.
NagurneyA, 1987a, “Computational comparisons of spatial price equilibrium methods”Journal of Regional Science27(1) 55–76
26.
NagurneyA, 1987b, “An algorithm for the classical spatial price equilibrium problem”Operations Research Letters6(2) 93–98
27.
OhuchiAKajiI, 1981, “An algorithm for the Hitchcock transportation problem with quadratic cost functions”Journal of Operations Research Society of Japan24170–181
28.
OhuchiAKajiI, 1984, “Lagrangean dual coordinatewise maximization for network transportation problems with quadratic costs”Network14525–530
29.
PangJ SLeeP L, 1981, “A parametric linear complementarity technique for the computation of equilibrium prices in single commodity trade flows”Mathematical Programming2081–102
30.
PerssonH, 1986, “Algorithm 12: Solving the entropy maximization problem with equality and inequality constraints”Environment and Planning A181665–1676
31.
PressWFlanneryB FTeukolskyS AVetterlingW T (Eds), 1986Numerical Recipes (Cambridge University Press, Cambridge)
32.
SamuelsonP A, 1952, “A spatial price equilibrium and linear programming”American Economic Review42283–303
33.
SchneiderMZeniosS, 1987, “A comparative study of algorithms for matrix balancing”, Department of Decision Sciences, WP:86–10-04, The Wharton School, University of Pennsylvania, Philadelphia, PA, USA
34.
SnickarsFWeibullJ W, 1977, “A minimum information principle, theory and practice”Regional Science and Urban Economics7137–168
35.
StoneR, 1951, “Simple transaction models, information, and computing”The Review of Economic StudiesXIX(2) (49) 67–84
36.
TakayamaTJudgeG G, 1971Spatial and Temporal Price and Allocation Models (North-Holland, Amsterdam)
37.
Van der SluisA, 1969, “Condition numbers and equilibration of matrices”Numerische Mathematik1414–23
38.
WilsonA G, 1970Entropy in Urban and Regional Modelling (Pion, London)
39.
ZangwillW I, 1969Nonlinear Programming—A Unified Approach (Prentice-Hall, Englewood Cliffs, NJ)
40.
ZeniosS ADrudAMulveyJ M, 1986, “Balancing some large social accounting matrices with nonlinear network programming”, technical report, Department of Civil Engineering, Princeton University, Princeton, NJ, USA
