Another pedagogy for mixed-integer Gomory

We present a version of GMI (Gomory mixed-integer) cuts in a way so that they are derived with respect to a “dual form” mixed-integer optimization problem and applied on the standard-form primal side as columns, using the primal simplex algorithm. This follows the general scheme of He and Lee, who d...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Jon Lee, Angelika Wiegele
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2017
Materias:	90C10 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/3030c8f5d9d94635b4d8ef0752cfb254
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:3030c8f5d9d94635b4d8ef0752cfb254
record_format	dspace
spelling	oai:doaj.org-article:3030c8f5d9d94635b4d8ef0752cfb2542021-12-02T05:01:03ZAnother pedagogy for mixed-integer Gomory2192-440610.1007/s13675-017-0085-3https://doaj.org/article/3030c8f5d9d94635b4d8ef0752cfb2542017-12-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000885https://doaj.org/toc/2192-4406We present a version of GMI (Gomory mixed-integer) cuts in a way so that they are derived with respect to a “dual form” mixed-integer optimization problem and applied on the standard-form primal side as columns, using the primal simplex algorithm. This follows the general scheme of He and Lee, who did the case of Gomory pure-integer cuts. Our input mixed-integer problem is not in standard form, and so our cuts are derived rather differently from how they are normally derived. A convenient way to develop GMI cuts is from MIR (mixed-integer rounding) cuts, which are developed from 2-dimensional BMI (basic mixed-integer) cuts, which involve a nonnegative continuous variable and an integer variable. The non-negativity of the continuous variable is not the right tool for us, as our starting point (the “dual form” mixed-integer optimization problem) has no non-negativity. So we work out a different 2-dimensional starting point, a pair of somewhat arbitrary inequalities in one continuous and one integer variable. In the end, we follow the approach of He and Lee, getting now a finitely converging primal simplex column-generation algorithm for mixed-integer optimization problems.Jon LeeAngelika WiegeleElsevierarticle90C10Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 5, Iss 4, Pp 455-466 (2017)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C10 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C10 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Jon Lee Angelika Wiegele Another pedagogy for mixed-integer Gomory
description	We present a version of GMI (Gomory mixed-integer) cuts in a way so that they are derived with respect to a “dual form” mixed-integer optimization problem and applied on the standard-form primal side as columns, using the primal simplex algorithm. This follows the general scheme of He and Lee, who did the case of Gomory pure-integer cuts. Our input mixed-integer problem is not in standard form, and so our cuts are derived rather differently from how they are normally derived. A convenient way to develop GMI cuts is from MIR (mixed-integer rounding) cuts, which are developed from 2-dimensional BMI (basic mixed-integer) cuts, which involve a nonnegative continuous variable and an integer variable. The non-negativity of the continuous variable is not the right tool for us, as our starting point (the “dual form” mixed-integer optimization problem) has no non-negativity. So we work out a different 2-dimensional starting point, a pair of somewhat arbitrary inequalities in one continuous and one integer variable. In the end, we follow the approach of He and Lee, getting now a finitely converging primal simplex column-generation algorithm for mixed-integer optimization problems.
format	article
author	Jon Lee Angelika Wiegele
author_facet	Jon Lee Angelika Wiegele
author_sort	Jon Lee
title	Another pedagogy for mixed-integer Gomory
title_short	Another pedagogy for mixed-integer Gomory
title_full	Another pedagogy for mixed-integer Gomory
title_fullStr	Another pedagogy for mixed-integer Gomory
title_full_unstemmed	Another pedagogy for mixed-integer Gomory
title_sort	another pedagogy for mixed-integer gomory
publisher	Elsevier
publishDate	2017
url	https://doaj.org/article/3030c8f5d9d94635b4d8ef0752cfb254
work_keys_str_mv	AT jonlee anotherpedagogyformixedintegergomory AT angelikawiegele anotherpedagogyformixedintegergomory
_version_	1718400820711522304

Another pedagogy for mixed-integer Gomory

Ejemplares similares