Solving multistage quantified linear optimization problems with the alpha–beta nested Benders decomposition

Quantified linear programs (QLPs) are linear programs with variables being either existentially or universally quantified. QLPs are convex multistage decision problems on the one side, and two-person zero-sum games between an existential and a universal player on the other side. Solutions of feasibl...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Ulf Lorenz, Jan Wolf
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2015
Materias:	90C46 90C47 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/5b08a36d74fd4e89b12c632614eefe02
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:5b08a36d74fd4e89b12c632614eefe02
record_format	dspace
spelling	oai:doaj.org-article:5b08a36d74fd4e89b12c632614eefe022021-12-02T05:00:46ZSolving multistage quantified linear optimization problems with the alpha–beta nested Benders decomposition2192-440610.1007/s13675-015-0038-7https://doaj.org/article/5b08a36d74fd4e89b12c632614eefe022015-11-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000502https://doaj.org/toc/2192-4406Quantified linear programs (QLPs) are linear programs with variables being either existentially or universally quantified. QLPs are convex multistage decision problems on the one side, and two-person zero-sum games between an existential and a universal player on the other side. Solutions of feasible QLPs are so-called winning strategies for the existential player that specify how to react on moves—fixations of universally quantified variables—of the universal player to certainly win the game. To find a certain best one among different winning strategies, we propose the extension of the QLP decision problem by an objective function. To solve the resulting QLP optimization problem, we exploit the problem’s hybrid nature and combine linear programming techniques with solution techniques from game-tree search. As a result, we present an extension of the nested Benders decomposition algorithm by the αβ-heuristic and move-ordering, two techniques that are successfully used in game-tree search to solve minimax trees. We furthermore exploit solution information from QLP relaxations obtained by quantifier shifting. The applicability is examined in an experimental evaluation.Ulf LorenzJan WolfElsevierarticle90C4690C47Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 3, Iss 4, Pp 349-370 (2015)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C46 90C47 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C46 90C47 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Ulf Lorenz Jan Wolf Solving multistage quantified linear optimization problems with the alpha–beta nested Benders decomposition
description	Quantified linear programs (QLPs) are linear programs with variables being either existentially or universally quantified. QLPs are convex multistage decision problems on the one side, and two-person zero-sum games between an existential and a universal player on the other side. Solutions of feasible QLPs are so-called winning strategies for the existential player that specify how to react on moves—fixations of universally quantified variables—of the universal player to certainly win the game. To find a certain best one among different winning strategies, we propose the extension of the QLP decision problem by an objective function. To solve the resulting QLP optimization problem, we exploit the problem’s hybrid nature and combine linear programming techniques with solution techniques from game-tree search. As a result, we present an extension of the nested Benders decomposition algorithm by the αβ-heuristic and move-ordering, two techniques that are successfully used in game-tree search to solve minimax trees. We furthermore exploit solution information from QLP relaxations obtained by quantifier shifting. The applicability is examined in an experimental evaluation.
format	article
author	Ulf Lorenz Jan Wolf
author_facet	Ulf Lorenz Jan Wolf
author_sort	Ulf Lorenz
title	Solving multistage quantified linear optimization problems with the alpha–beta nested Benders decomposition
title_short	Solving multistage quantified linear optimization problems with the alpha–beta nested Benders decomposition
title_full	Solving multistage quantified linear optimization problems with the alpha–beta nested Benders decomposition
title_fullStr	Solving multistage quantified linear optimization problems with the alpha–beta nested Benders decomposition
title_full_unstemmed	Solving multistage quantified linear optimization problems with the alpha–beta nested Benders decomposition
title_sort	solving multistage quantified linear optimization problems with the alpha–beta nested benders decomposition
publisher	Elsevier
publishDate	2015
url	https://doaj.org/article/5b08a36d74fd4e89b12c632614eefe02
work_keys_str_mv	AT ulflorenz solvingmultistagequantifiedlinearoptimizationproblemswiththealphabetanestedbendersdecomposition AT janwolf solvingmultistagequantifiedlinearoptimizationproblemswiththealphabetanestedbendersdecomposition
_version_	1718400829303554048

Solving multistage quantified linear optimization problems with the alpha–beta nested Benders decomposition

Ejemplares similares