Complexity of necessary efficiency in interval linear programming and multiobjective linear programming
2012
Abstract
We present some complexity results on checking necessary efficiency in interval multiobjective linear programming. Supposing that objective function coefficients perturb within prescribed intervals, a feasible point x* is called necessarily efficient if it is efficient for all instances of interval data.
We show that the problem of checking necessary efficiency is co-NP-complete even for the case of only one objective. Provided that x* is a non-degenerate basic solution, the problem is polynomially solvable for one objective, but remains co-NP-hard in the general case.
Some open problems are mentioned at the end of the paper.