Testing weak optimality of a given solution in interval linear programming revisited: NP-hardness proof, algorithm and some polynomial cases
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2017
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916991546163200 |
|---|---|
| author | Rada, Miroslav Hladík, Milan Garajová, Elif |
| author_facet | Rada, Miroslav Hladík, Milan Garajová, Elif |
| contents | 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. Interval linear programs with inequality constraints only can be processed in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1712_00350 |
| institution | arXiv |
| publishDate | 2017 |
| record_format | arxiv |
| spellingShingle | Testing weak optimality of a given solution in interval linear programming revisited: NP-hardness proof, algorithm and some polynomial cases Rada, Miroslav Hladík, Milan Garajová, Elif Optimization and Control 65G40, 90C31 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. Interval linear programs with inequality constraints only can be processed in polynomial time. |
| title | Testing weak optimality of a given solution in interval linear programming revisited: NP-hardness proof, algorithm and some polynomial cases |
| topic | Optimization and Control 65G40, 90C31 |
| url | https://arxiv.org/abs/1712.00350 |