Intersection cuts from multiple rows: a disjunctive programming approach

We address the issue of generating cutting planes for mixed integer programs from multiple rows of the simplex tableau with the tools of disjunctive programming. A cut from q rows of the simplex tableau is an intersection cut from a q-dimensional parametric cross-polytope, which can also be viewed a...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Egon Balas, Andrea Qualizza
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2013
Materias:	90C10 90C11 90C27 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/3d9c31ceab644ecab7c0a6c95cc0d7a6
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:3d9c31ceab644ecab7c0a6c95cc0d7a6
record_format	dspace
spelling	oai:doaj.org-article:3d9c31ceab644ecab7c0a6c95cc0d7a62021-12-02T05:00:34ZIntersection cuts from multiple rows: a disjunctive programming approach2192-440610.1007/s13675-013-0008-xhttps://doaj.org/article/3d9c31ceab644ecab7c0a6c95cc0d7a62013-05-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000101https://doaj.org/toc/2192-4406We address the issue of generating cutting planes for mixed integer programs from multiple rows of the simplex tableau with the tools of disjunctive programming. A cut from q rows of the simplex tableau is an intersection cut from a q-dimensional parametric cross-polytope, which can also be viewed as a disjunctive cut from a 2q-term disjunction. We define the disjunctive hull of the q-row problem, describe its relation to the integer hull, and show how to generate its facets. For the case of binary basic variables, we derive cuts from the stronger disjunctions whose terms are equations. We give cut strengthening procedures using the integrality of the nonbasic variables for both the integer and the binary case. Finally, we discuss some computational experiments.Egon BalasAndrea QualizzaElsevierarticle90C1090C1190C27Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 1, Iss 1, Pp 3-49 (2013)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C10 90C11 90C27 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C10 90C11 90C27 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Egon Balas Andrea Qualizza Intersection cuts from multiple rows: a disjunctive programming approach
description	We address the issue of generating cutting planes for mixed integer programs from multiple rows of the simplex tableau with the tools of disjunctive programming. A cut from q rows of the simplex tableau is an intersection cut from a q-dimensional parametric cross-polytope, which can also be viewed as a disjunctive cut from a 2q-term disjunction. We define the disjunctive hull of the q-row problem, describe its relation to the integer hull, and show how to generate its facets. For the case of binary basic variables, we derive cuts from the stronger disjunctions whose terms are equations. We give cut strengthening procedures using the integrality of the nonbasic variables for both the integer and the binary case. Finally, we discuss some computational experiments.
format	article
author	Egon Balas Andrea Qualizza
author_facet	Egon Balas Andrea Qualizza
author_sort	Egon Balas
title	Intersection cuts from multiple rows: a disjunctive programming approach
title_short	Intersection cuts from multiple rows: a disjunctive programming approach
title_full	Intersection cuts from multiple rows: a disjunctive programming approach
title_fullStr	Intersection cuts from multiple rows: a disjunctive programming approach
title_full_unstemmed	Intersection cuts from multiple rows: a disjunctive programming approach
title_sort	intersection cuts from multiple rows: a disjunctive programming approach
publisher	Elsevier
publishDate	2013
url	https://doaj.org/article/3d9c31ceab644ecab7c0a6c95cc0d7a6
work_keys_str_mv	AT egonbalas intersectioncutsfrommultiplerowsadisjunctiveprogrammingapproach AT andreaqualizza intersectioncutsfrommultiplerowsadisjunctiveprogrammingapproach
_version_	1718400823283679232

Intersection cuts from multiple rows: a disjunctive programming approach

Ejemplares similares