How to determine basis stability in interval linear programming

被引：43

作者：

Hladik, Milan ^{[1
,2
]}

机构：

[1] Charles Univ Prague, Fac Math & Phys, Dept Appl Math, CR-11800 Prague, Czech Republic

[2] Univ Econ, Fac Informat & Stat, Dept Econometr, Prague 13067, Czech Republic

来源：

OPTIMIZATION LETTERS | 2014年 / 8卷 / 01期

关键词：

Linear programming; Linear interval systems; Interval analysis; Basis stability; SYSTEMS; BOUNDS;

D O I：

10.1007/s11590-012-0589-y

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Interval linear programming (ILP) was introduced in order to deal with linear programming problems with uncertainties that are modelled by ranges of admissible values. Basic tasks in ILP such as calculating the optimal value bounds or set of all possible solutions may be computationally very expensive. However, if some basis stability criterion holds true then the problems becomes much more easy to solve. In this paper, we propose a method for testing basis stability. Even though the method is exponential in the worst case (not surprisingly due to NP-hardness of the problem), it is fast in many cases.

引用

页码：375 / 389

页数：15