Strong and compact relaxations in the original space using a compact extended formulation

For certain integer programs, one way to obtain a strong dual bound is to use an extended formulation and then solve the associated linear programming relaxation. The classical way to obtain a bound of the same value in the original variable space is through the use of Benders’ algorithm. Here, we p...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Mathieu Van Vyve, Laurence A. Wolsey
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2013
Materias:	Production Site Extended Formulation Decomposition Algorithm Valid Inequality Linear Programming Relaxation Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/cd52db78cd6145d39f64f83427059510
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:cd52db78cd6145d39f64f83427059510
record_format	dspace
spelling	oai:doaj.org-article:cd52db78cd6145d39f64f834270595102021-12-02T05:00:35ZStrong and compact relaxations in the original space using a compact extended formulation2192-440610.1007/s13675-012-0004-6https://doaj.org/article/cd52db78cd6145d39f64f834270595102013-05-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000125https://doaj.org/toc/2192-4406For certain integer programs, one way to obtain a strong dual bound is to use an extended formulation and then solve the associated linear programming relaxation. The classical way to obtain a bound of the same value in the original variable space is through the use of Benders’ algorithm. Here, we propose an alternative approach based on a decomposition of the dual optimal solution of the extended formulation linear program. An example of the approach using the multi-commodity formulation of a two-level production/transportation problem is presented.Mathieu Van VyveLaurence A. WolseyElsevierarticleProduction SiteExtended FormulationDecomposition AlgorithmValid InequalityLinear Programming RelaxationApplied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 1, Iss 1, Pp 71-80 (2013)
institution	DOAJ
collection	DOAJ
language	EN
topic	Production Site Extended Formulation Decomposition Algorithm Valid Inequality Linear Programming Relaxation Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	Production Site Extended Formulation Decomposition Algorithm Valid Inequality Linear Programming Relaxation Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Mathieu Van Vyve Laurence A. Wolsey Strong and compact relaxations in the original space using a compact extended formulation
description	For certain integer programs, one way to obtain a strong dual bound is to use an extended formulation and then solve the associated linear programming relaxation. The classical way to obtain a bound of the same value in the original variable space is through the use of Benders’ algorithm. Here, we propose an alternative approach based on a decomposition of the dual optimal solution of the extended formulation linear program. An example of the approach using the multi-commodity formulation of a two-level production/transportation problem is presented.
format	article
author	Mathieu Van Vyve Laurence A. Wolsey
author_facet	Mathieu Van Vyve Laurence A. Wolsey
author_sort	Mathieu Van Vyve
title	Strong and compact relaxations in the original space using a compact extended formulation
title_short	Strong and compact relaxations in the original space using a compact extended formulation
title_full	Strong and compact relaxations in the original space using a compact extended formulation
title_fullStr	Strong and compact relaxations in the original space using a compact extended formulation
title_full_unstemmed	Strong and compact relaxations in the original space using a compact extended formulation
title_sort	strong and compact relaxations in the original space using a compact extended formulation
publisher	Elsevier
publishDate	2013
url	https://doaj.org/article/cd52db78cd6145d39f64f83427059510
work_keys_str_mv	AT mathieuvanvyve strongandcompactrelaxationsintheoriginalspaceusingacompactextendedformulation AT laurenceawolsey strongandcompactrelaxationsintheoriginalspaceusingacompactextendedformulation
_version_	1718400854640295936

Strong and compact relaxations in the original space using a compact extended formulation

Ejemplares similares