Column generation for extended formulations

Working in an extended variable space allows one to develop tighter reformulations for mixed integer programs. However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. Then, one can work with inner approximations defined and improved by generating...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Ruslan Sadykov, François Vanderbeck
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2013
Materias:	97N60 Mathematical Programming 97N80 Mathematical software, Computer Programs 97M40 Operations research, economics Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/7d3a0c157efc41329107d521091858b3
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:7d3a0c157efc41329107d521091858b3
record_format	dspace
spelling	oai:doaj.org-article:7d3a0c157efc41329107d521091858b32021-12-02T05:00:35ZColumn generation for extended formulations2192-440610.1007/s13675-013-0009-9https://doaj.org/article/7d3a0c157efc41329107d521091858b32013-05-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000137https://doaj.org/toc/2192-4406Working in an extended variable space allows one to develop tighter reformulations for mixed integer programs. However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. Then, one can work with inner approximations defined and improved by generating dynamically variables and constraints. When the extended formulation stems from subproblems’ reformulations, one can implement column generation for the extended formulation using a Dantzig–Wolfe decomposition paradigm. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current restricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solutions. This so-called “column-and-row generation” procedure is revisited here in a unifying presentation that generalizes the column generation algorithm and extends to the case of working with an approximate extended formulation. The interest of the approach is evaluated numerically on machine scheduling, bin packing, generalized assignment, and multi-echelon lot-sizing problems. We compare a direct handling of the extended formulation, a standard column generation approach, and the “column-and-row generation” procedure, highlighting a key benefit of the latter: lifting pricing problem solutions in the space of the extended formulation permits their recombination into new subproblem solutions and results in faster convergence.Ruslan SadykovFrançois VanderbeckElsevierarticle97N60 Mathematical Programming97N80 Mathematical software, Computer Programs97M40 Operations research, economicsApplied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 1, Iss 1, Pp 81-115 (2013)
institution	DOAJ
collection	DOAJ
language	EN
topic	97N60 Mathematical Programming 97N80 Mathematical software, Computer Programs 97M40 Operations research, economics Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	97N60 Mathematical Programming 97N80 Mathematical software, Computer Programs 97M40 Operations research, economics Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Ruslan Sadykov François Vanderbeck Column generation for extended formulations
description	Working in an extended variable space allows one to develop tighter reformulations for mixed integer programs. However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. Then, one can work with inner approximations defined and improved by generating dynamically variables and constraints. When the extended formulation stems from subproblems’ reformulations, one can implement column generation for the extended formulation using a Dantzig–Wolfe decomposition paradigm. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current restricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solutions. This so-called “column-and-row generation” procedure is revisited here in a unifying presentation that generalizes the column generation algorithm and extends to the case of working with an approximate extended formulation. The interest of the approach is evaluated numerically on machine scheduling, bin packing, generalized assignment, and multi-echelon lot-sizing problems. We compare a direct handling of the extended formulation, a standard column generation approach, and the “column-and-row generation” procedure, highlighting a key benefit of the latter: lifting pricing problem solutions in the space of the extended formulation permits their recombination into new subproblem solutions and results in faster convergence.
format	article
author	Ruslan Sadykov François Vanderbeck
author_facet	Ruslan Sadykov François Vanderbeck
author_sort	Ruslan Sadykov
title	Column generation for extended formulations
title_short	Column generation for extended formulations
title_full	Column generation for extended formulations
title_fullStr	Column generation for extended formulations
title_full_unstemmed	Column generation for extended formulations
title_sort	column generation for extended formulations
publisher	Elsevier
publishDate	2013
url	https://doaj.org/article/7d3a0c157efc41329107d521091858b3
work_keys_str_mv	AT ruslansadykov columngenerationforextendedformulations AT francoisvanderbeck columngenerationforextendedformulations
_version_	1718400838617006080

Column generation for extended formulations

Ejemplares similares