Reflections on generating (disjunctive) cuts

We consider the problem of constructing generic supporting hyperplanes to be used within a (branch and) bound-and-cut algorithm. We review some of the properties that these hyperplanes should enjoy. It is generally admitted that they should cut a parasitic point generated during the process. We argu...

Description complète

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Florent Cadoux, Claude Lemaréchal
Format:	article
Langue:	EN
Publié:	Elsevier 2013
Sujets:	52A41 90C11 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Accès en ligne:	https://doaj.org/article/5732b43850a545a9af5d3d75315544b9
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

id	oai:doaj.org-article:5732b43850a545a9af5d3d75315544b9
record_format	dspace
spelling	oai:doaj.org-article:5732b43850a545a9af5d3d75315544b92021-12-02T05:00:34ZReflections on generating (disjunctive) cuts2192-440610.1007/s13675-012-0006-4https://doaj.org/article/5732b43850a545a9af5d3d75315544b92013-05-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000113https://doaj.org/toc/2192-4406We consider the problem of constructing generic supporting hyperplanes to be used within a (branch and) bound-and-cut algorithm. We review some of the properties that these hyperplanes should enjoy. It is generally admitted that they should cut a parasitic point generated during the process. We argue that the advantages of restricting supports to cuts might be over-balanced by their drawbacks. Said otherwise, the cutting paradigm entails the reverse polar, which may not have definite advantages over the ordinary polar (associated with supports). In fact, we believe that moderate attention should be paid to the current relaxed solution, which plays only a temporary role in the process. We propose approaches to constructing supports, in such a way that the cutting property comes out as a by-product. In particular, squeezing the objective function is most desirable; but cuts merely based on the objective function, being parallel to each other all along the iterations, are generally recognized as inefficient. We propose a mechanism to revive the idea.Florent CadouxClaude LemaréchalElsevierarticle52A4190C11Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 1, Iss 1, Pp 51-69 (2013)
institution	DOAJ
collection	DOAJ
language	EN
topic	52A41 90C11 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	52A41 90C11 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Florent Cadoux Claude Lemaréchal Reflections on generating (disjunctive) cuts
description	We consider the problem of constructing generic supporting hyperplanes to be used within a (branch and) bound-and-cut algorithm. We review some of the properties that these hyperplanes should enjoy. It is generally admitted that they should cut a parasitic point generated during the process. We argue that the advantages of restricting supports to cuts might be over-balanced by their drawbacks. Said otherwise, the cutting paradigm entails the reverse polar, which may not have definite advantages over the ordinary polar (associated with supports). In fact, we believe that moderate attention should be paid to the current relaxed solution, which plays only a temporary role in the process. We propose approaches to constructing supports, in such a way that the cutting property comes out as a by-product. In particular, squeezing the objective function is most desirable; but cuts merely based on the objective function, being parallel to each other all along the iterations, are generally recognized as inefficient. We propose a mechanism to revive the idea.
format	article
author	Florent Cadoux Claude Lemaréchal
author_facet	Florent Cadoux Claude Lemaréchal
author_sort	Florent Cadoux
title	Reflections on generating (disjunctive) cuts
title_short	Reflections on generating (disjunctive) cuts
title_full	Reflections on generating (disjunctive) cuts
title_fullStr	Reflections on generating (disjunctive) cuts
title_full_unstemmed	Reflections on generating (disjunctive) cuts
title_sort	reflections on generating (disjunctive) cuts
publisher	Elsevier
publishDate	2013
url	https://doaj.org/article/5732b43850a545a9af5d3d75315544b9
work_keys_str_mv	AT florentcadoux reflectionsongeneratingdisjunctivecuts AT claudelemarechal reflectionsongeneratingdisjunctivecuts
_version_	1718400828518170624

Reflections on generating (disjunctive) cuts

Documents similaires