Milan Hladík. Complexity of necessary efficiency in interval linear programming and multiobjective linear programming. Optim. Lett., 6(5):893–899, 2012.
[PDF] [gzipped postscript] [postscript] [HTML]
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.
@article{Hla2012b,
author = "Milan Hlad\'{\i}k",
title = "Complexity of necessary efficiency in interval linear programming and multiobjective linear programming",
journal = "Optim. Lett.",
fjournal = "Optimization Letters",
pages = "893-899",
volume = "6",
number = "5",
year = "2012",
doi = "10.1007/s11590-011-0315-1",
url = "https://doi.org/10.1007/s11590-011-0315-1",
bib2html_dl_html = "https://link.springer.com/article/10.1007/s11590-011-0315-1",
bib2html_dl_pdf = "https://rdcu.be/cnoVA",
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.",
keywords = "Multiobjective linear programming, interval matrix, efficient solution, NP-completeness",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44