Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming

An elementary, but fundamental, operation in disjunctive programming is a basic step, which is the intersection of two disjunctions to form a new disjunction. Basic steps bring a disjunctive set in regular form closer to its disjunctive normal form and, in turn, produce relaxations that are at least...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	DimitriJ. Papageorgiou, Francisco Trespalacios
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2018
Materias:	90C11 Mixed integer programming Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/e96e23b9be534d01b99b1c340a647d6c
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:e96e23b9be534d01b99b1c340a647d6c
record_format	dspace
spelling	oai:doaj.org-article:e96e23b9be534d01b99b1c340a647d6c2021-12-02T05:01:05ZPseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming2192-440610.1007/s13675-017-0088-0https://doaj.org/article/e96e23b9be534d01b99b1c340a647d6c2018-03-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000952https://doaj.org/toc/2192-4406An elementary, but fundamental, operation in disjunctive programming is a basic step, which is the intersection of two disjunctions to form a new disjunction. Basic steps bring a disjunctive set in regular form closer to its disjunctive normal form and, in turn, produce relaxations that are at least as tight. An open question is: What are guaranteed bounds on the improvement from a basic step? In this paper, using properties of a convex disjunctive program’s hull reformulation and multipliers from Lagrangian decomposition, we introduce an operation called a pseudo basic step and use it to provide provable bounds on this improvement along with techniques to exploit this information when solving a disjunctive program as a convex MINLP. Numerical examples illustrate the practical benefits of these bounds. In particular, on a set of K-means clustering instances, we make significant bound improvements relative to state-of-the-art commercial mixed-integer programming solvers.DimitriJ. PapageorgiouFrancisco TrespalaciosElsevierarticle90C11 Mixed integer programmingApplied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 6, Iss 1, Pp 55-83 (2018)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C11 Mixed integer programming Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C11 Mixed integer programming Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 DimitriJ. Papageorgiou Francisco Trespalacios Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming
description	An elementary, but fundamental, operation in disjunctive programming is a basic step, which is the intersection of two disjunctions to form a new disjunction. Basic steps bring a disjunctive set in regular form closer to its disjunctive normal form and, in turn, produce relaxations that are at least as tight. An open question is: What are guaranteed bounds on the improvement from a basic step? In this paper, using properties of a convex disjunctive program’s hull reformulation and multipliers from Lagrangian decomposition, we introduce an operation called a pseudo basic step and use it to provide provable bounds on this improvement along with techniques to exploit this information when solving a disjunctive program as a convex MINLP. Numerical examples illustrate the practical benefits of these bounds. In particular, on a set of K-means clustering instances, we make significant bound improvements relative to state-of-the-art commercial mixed-integer programming solvers.
format	article
author	DimitriJ. Papageorgiou Francisco Trespalacios
author_facet	DimitriJ. Papageorgiou Francisco Trespalacios
author_sort	DimitriJ. Papageorgiou
title	Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming
title_short	Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming
title_full	Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming
title_fullStr	Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming
title_full_unstemmed	Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming
title_sort	pseudo basic steps: bound improvement guarantees from lagrangian decomposition in convex disjunctive programming
publisher	Elsevier
publishDate	2018
url	https://doaj.org/article/e96e23b9be534d01b99b1c340a647d6c
work_keys_str_mv	AT dimitrijpapageorgiou pseudobasicstepsboundimprovementguaranteesfromlagrangiandecompositioninconvexdisjunctiveprogramming AT franciscotrespalacios pseudobasicstepsboundimprovementguaranteesfromlagrangiandecompositioninconvexdisjunctiveprogramming
_version_	1718400864210649088

Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming

Ejemplares similares