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 条
12