Milan Hladík's Publications:

Complexity of necessary efficiency in interval linear programming and multiobjective linear programming

Milan Hladík. Complexity of necessary efficiency in interval linear programming and multiobjective linear programming. Optim. Lett., 6(5):893–899, 2012.

Download

[PDF] [gzipped postscript] [postscript] [HTML] 

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.

BibTeX

@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 Feb 07, 2024 09:31:18