Paper Info
Title
Testing weak optimality of a given solution in interval linear programming revisited: NP-hardness proof, algorithm and some polynomially-solvable cases
Abstract
We address the problem of testing weak optimality of a given solution of a given interval linear program. The problem was recently wrongly stated to be polynomially solvable. We disprove it. We show that the problem is NP-hard in general. We propose a new algorithm for the problem, based on orthant decomposition and solving linear systems. Running time of the algorithm is exponential in the number of equality constraints. In particular, the proposed algorithm runs in polynomial time for interval linear programs with no equality constraints.
Year
DOI
Venue
2019
10.1007/s11590-018-1289-z
Optimization Letters
Keywords
DocType
Volume
Interval linear programming, Weakly optimal solution, Weak optimality testing
Journal
13
Issue
ISSN
Citations 
4
1862-4480
0
PageRank 
References 
Authors
0.34
14
3
Name
Order
Citations
PageRank
Miroslav Rada100.68
Milan Hladík226836.33
Elif Garajová331.44