Finding a bounded mixed-integer solution to a system of dual network inequalities

被引：3
|
作者：
Butkovic, P. [1 ]
机构：
[1] Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England
来源：
OPERATIONS RESEARCH LETTERS | 2008年 / 36卷 / 05期
基金：
英国工程与自然科学研究理事会;
关键词：
Eigenvector; Dual network inequalities; Max-algebra;
D O I：
10.1016/j.orl.2008.04.004
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We show that using max-algebraic techniques it is possible to generate the set of all solutions to a system of inequalities x(i) - x(j) >= b(ij), i,j = 1,..., n using n generators. This efficient description enables us to develop a pseudopolynomial algorithm which either finds a bounded mixed-integer solution, or decides that no such solution exists. (c) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码：623 / 627
页数：5
相关论文
共 50 条
12345