A Note on Degeneracy in Integer Linear Programming Problem
作者:
MooresBrian,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1988)
卷期:
Volume 39,
issue 12
页码: 1175-1178
ISSN:0160-5682
年代: 1988
DOI:10.1057/jors.1988.194
出版商: Taylor&Francis
关键词: integer;programming;simulation
数据来源: Taylor
摘要:
AbstractA set of three batches of 1000 randomly produced integer linear programming problems of different sizes was solved using a partial enumeration algorithm. That particular algorithm involves the initial ordering of the variables according to their attractiveness when considered individually. The results reveal that, as might have been expected, the most attractive variables appear very much more frequently than do the less attractive. Perhaps less expected is the fact that the average number of variables appearing in the optimum solution is considerably less than might have been anticipated. Thus, for example, the average number of variables which appear in a set of problems featuring 20 variables and 10 constraints is only 4.14, as against the 10 one would have been expecting in continuous LP problems of that size. It is argued that it is this inherent characteristic which results in truncation solution procedures being as effective as they are.
点击下载:
PDF (1965KB)
返 回