VARIABLE ELIMINATION IN LINEAR CONSTRAINTS

被引:20
作者
CHANDRU, V
机构
关键词
D O I
10.1093/comjnl/36.5.463
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Gauss and Fourier have together provided us with the essential techniques for symbolic computation with linear arithmetic constraints over the reals and the rationals. These variable elimination techniques for linear constraints have particular significance in the context of constraint logic programming languages that have been developed in recent years. Variable elimination in linear equations (Gaussian Elimination) is a fundamental technique in computational linear algebra and is therefore quite familiar to most of us. Elimination in linear inequalities (Fourier Elimination), on the other hand, is intimately related to polyhedral theory and aspects of linear programming that are not quite as familiar. In addition, the high complexity of elimination in inequalities has forced the consideration of intricate specializations of Fourier's original method. The intent of this survey article is to acquaint the reader with these connections and developments. The latter part of the article dwells on the thesis that variable elimination in linear constraints over the reals extends quite naturally to constraints in certain discrete domains.
引用
收藏
页码:463 / 472
页数:10
相关论文
共 56 条
[1]  
Abhyankar SS., 1990, MATH SURVEYS MONOGRA, DOI DOI 10.1090/SURV/035
[2]  
ARAQUE JR, 1991, CC9111 IIEES PURD U
[3]  
ASPVALL BI, 1979, FOCS, P205
[4]  
BANNERJEE U, 1988, DEPENDENCE ANAL SUPE
[5]   THE ELLIPSOID METHOD - A SURVEY [J].
BLAND, RG ;
GOLDFARB, D ;
TODD, MJ .
OPERATIONS RESEARCH, 1981, 29 (06) :1039-1091
[6]  
BLEDSOE WW, 1974, ATP18 U TEX MATH DEP
[7]  
CERNIKOV RN, 1961, SOV MATH DOKL, V2, P1099
[8]   NUMBER OF PRIME IMPLICANTS [J].
CHANDRA, AK ;
MARKOWSKY, G .
DISCRETE MATHEMATICS, 1978, 24 (01) :7-11
[9]  
CHANDRU V, OPTIMIZATION METHODS
[10]   MANY HARD EXAMPLES FOR RESOLUTION [J].
CHVATAL, V ;
SZEMEREDI, E .
JOURNAL OF THE ACM, 1988, 35 (04) :759-768