Robust combinatorial optimization under budgeted–ellipsoidal uncertainty

In the field of robust optimization, uncertain data are modeled by uncertainty sets which contain all relevant outcomes of the uncertain problem parameters. The complexity of the related robust problem depends strongly on the shape of the chosen set. Two popular classes of uncertainty are budgeted u...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Jannis Kurtz
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2018
Materias:	90C27 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/7bc3d85d82254367a34083aefe5f5fe4
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:7bc3d85d82254367a34083aefe5f5fe4
record_format	dspace
spelling	oai:doaj.org-article:7bc3d85d82254367a34083aefe5f5fe42021-12-02T05:01:08ZRobust combinatorial optimization under budgeted–ellipsoidal uncertainty2192-440610.1007/s13675-018-0097-7https://doaj.org/article/7bc3d85d82254367a34083aefe5f5fe42018-12-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001052https://doaj.org/toc/2192-4406In the field of robust optimization, uncertain data are modeled by uncertainty sets which contain all relevant outcomes of the uncertain problem parameters. The complexity of the related robust problem depends strongly on the shape of the chosen set. Two popular classes of uncertainty are budgeted uncertainty and ellipsoidal uncertainty. In this paper, we introduce a new uncertainty class which is a combination of both. More precisely, we consider ellipsoidal uncertainty sets with the additional restriction that at most a certain number of ellipsoid axes can be used at the same time to describe a scenario. We define a discrete and a convex variant of the latter set and prove that in both cases the corresponding robust min–max problem is NP-hard for several combinatorial problems. Furthermore, we prove that for uncorrelated budgeted–ellipsoidal uncertainty in both cases the min–max problem can be solved in polynomial time for several combinatorial problems if the number of axes which can be used at the same time is fixed. We derive exact solution methods and formulations for the problem which we test on random instances of the knapsack problem and of the shortest path problem.Jannis KurtzElsevierarticle90C27Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 6, Iss 4, Pp 315-337 (2018)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C27 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C27 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Jannis Kurtz Robust combinatorial optimization under budgeted–ellipsoidal uncertainty
description	In the field of robust optimization, uncertain data are modeled by uncertainty sets which contain all relevant outcomes of the uncertain problem parameters. The complexity of the related robust problem depends strongly on the shape of the chosen set. Two popular classes of uncertainty are budgeted uncertainty and ellipsoidal uncertainty. In this paper, we introduce a new uncertainty class which is a combination of both. More precisely, we consider ellipsoidal uncertainty sets with the additional restriction that at most a certain number of ellipsoid axes can be used at the same time to describe a scenario. We define a discrete and a convex variant of the latter set and prove that in both cases the corresponding robust min–max problem is NP-hard for several combinatorial problems. Furthermore, we prove that for uncorrelated budgeted–ellipsoidal uncertainty in both cases the min–max problem can be solved in polynomial time for several combinatorial problems if the number of axes which can be used at the same time is fixed. We derive exact solution methods and formulations for the problem which we test on random instances of the knapsack problem and of the shortest path problem.
format	article
author	Jannis Kurtz
author_facet	Jannis Kurtz
author_sort	Jannis Kurtz
title	Robust combinatorial optimization under budgeted–ellipsoidal uncertainty
title_short	Robust combinatorial optimization under budgeted–ellipsoidal uncertainty
title_full	Robust combinatorial optimization under budgeted–ellipsoidal uncertainty
title_fullStr	Robust combinatorial optimization under budgeted–ellipsoidal uncertainty
title_full_unstemmed	Robust combinatorial optimization under budgeted–ellipsoidal uncertainty
title_sort	robust combinatorial optimization under budgeted–ellipsoidal uncertainty
publisher	Elsevier
publishDate	2018
url	https://doaj.org/article/7bc3d85d82254367a34083aefe5f5fe4
work_keys_str_mv	AT janniskurtz robustcombinatorialoptimizationunderbudgetedellipsoidaluncertainty
_version_	1718400837591498752

Robust combinatorial optimization under budgeted–ellipsoidal uncertainty

Ejemplares similares