MARC状态：已编 文献类型：西文图书 浏览次数：79
- 题名/责任者:
- Extracting Embedded Generalized networks from Linear Programming problems / by Gerald G.Brown, Richard D.McBride, R.Kevin Wood.
- 出版发行项:
- [S.l. : Defense Technical Information Center], 1984.
- 载体形态项:
- 21 p. : ill. ; 28 cm.
- 个人责任者:
- Brown, Gerald G.
- 附加个人名称:
- McBride, Richard D.
- 附加个人名称:
- Wood, R. Kevin.
- 附加团体名称:
- Naval Postgraduated School.
- 论题主题:
- Matrices(mathematics)
- 论题主题:
- Theoretical Mathematics.
- 论题主题:
- Computer Systems.
- 中图法分类号:
- O221.1
- 一般附注:
- "september 1984."
- 一般附注:
- Prepared for Naval Postgraduate School.
- 一般附注:
- Cover title.
- 书目附注:
- Includes bibliographical references.
- 摘要附注:
- If a linear program (LP) possesses a large generalized network (GN) submatrix, this structure can be exploited to decrease solution time. The problems of definding maximum sets of GN constraints and finding maximum embedded GN submatrices are shown to be NP-complete indicating that reliable, efficient solution of these problems is difficult. Therefore, efficient heuristic algorithms are developed for identifying such structure and are tested on a selection of twenty-three real-world problems. The best of four algorithms for identifying GN constraint sets finds a set which is maximum in twelve cases and average 99.1% of maximum. On average, the GN constraints identified comprise more than 62.3% of the total constraints in these problems. The algorithm for identifying embedded GN submatrices finds submatrices whose sizes, rows plus columns, average 96.8% of an LP upper bound. Over 91.3% of the total constraint matrix was identified as a GN submatrix in these problems, on average. Originator supplied keywords include: embedded networks, computational complexity, and large-scale optimization.
- 随书光盘:
全部MARC细节信息>>
东5层4区