ONLINE AND OFF-LINE VERTEX ENUMERATION BY ADJACENCY LISTS

被引：55

作者：

CHEN, PC

HANSEN, P

JAUMARD, B

机构：

[1] GERAD,MONTREAL H3C 3A7,QUEBEC,CANADA

[2] ECOLE POLYTECH,MONTREAL H3C 3A7,QUEBEC,CANADA

来源：

OPERATIONS RESEARCH LETTERS | 1991年 / 10卷 / 07期

基金：

加拿大自然科学与工程研究理事会;

关键词：

VERTEX ENUMERATION; CUTTING-PLANE; GLOBAL OPTIMIZATION; CONCAVE PROGRAMMING;

D O I：

10.1016/0167-6377(91)90042-N

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We propose a new algorithm to solve the on-line vertex enumeration problem for polytopes, doing all computations in n-space, where n is the dimension of the polytope. This algorithm exploits adjacency lists between vertices and uses no simplex tableaux. It can handle the cases of empty or degenerate polyhedra. A theoretical and numerical comparison with existing approaches for off-line vertex enumeration is presented.

引用

页码：403 / 409

页数：7

共 11 条

[1] THE COMPLEXITY OF VERTEX ENUMERATION METHODS [J].