Testing weak optimality of a given solution in interval linear programming revisited: NP-hardness proof, algorithm and some polynomial cases

2017/12/01 by Rada, Miroslav, Hladík, Milan, Garajová, Elif · 1 citation
#65G40 #90C31 #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1712.00350

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. Interval linear programs with inequality constraints only can be processed in polynomial time.

Cited by

• Counterfactual explanations for linear optimization

Related

• Interval Linear Programming under Transformations: Optimal Solutions and\n Optimal Value Range
• Interval Linear Algebra and Computational Complexity
• Efficiently expressing feasibility problems in Linear Systems, as feasibility problems in Asymptotic-Linear-Programs
• Repeating Patterns in Linear Programs that express NP-Complete Problems
• Interval regularization for imprecise linear algebraic equations