Improving the efficiency of the Branch and Bound algorithm for integer programming based on "flatness" information

Simple item page
dc.contributor.authorDerpich, Ivan
dc.contributor.authorVera, Jorge R.
dc.date.accessioned2024-01-10T13:13:44Z
dc.date.available2024-01-10T13:13:44Z
dc.date.issued2006
dc.description.abstractThis paper describes a strategy for defining priorities for the branching variables in a Branch and Bound algorithm. The strategy is based on shape information about the polyhedron over which we are optimizing. This information is related to measures of the integer width, as provided by the so called "Flatness Theorem". Our selection rule uses that knowledge to define branching priorities on the variables. Computational results with simulated small to medium size integer problems are presented, as well with multi-knapsack problems. These show savings of about 40% in CPU time, as well as in nodes generated in the search tree, and compare favorably with respect to other standard branching rules. (c) 2005 Elsevier B.V. All rights reserved.
dc.fechaingreso.objetodigital2024-04-16
dc.format.extent10 páginas
dc.fuente.origenWOS
dc.identifier.doi10.1016/j.ejor.2005.02.051
dc.identifier.issn0377-2217
dc.identifier.urihttps://doi.org/10.1016/j.ejor.2005.02.051
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/78333
dc.identifier.wosidWOS:000239252600007
dc.information.autorucIngeniería;Vera JR;S/I;100240
dc.issue.numero1
dc.language.isoen
dc.nota.accesocontenido parcial
dc.pagina.final101
dc.pagina.inicio92
dc.publisherELSEVIER SCIENCE BV
dc.revistaEUROPEAN JOURNAL OF OPERATIONAL RESEARCH
dc.rightsacceso restringido
dc.subjectdiscrete optimization
dc.subjectBranch and Bound
dc.titleImproving the efficiency of the Branch and Bound algorithm for integer programming based on "flatness" information
dc.typeartículo
dc.volumen174
sipa.codpersvinculados100240
sipa.indexWOS
sipa.indexScopus
sipa.trazabilidadCarga SIPA;09-01-2024
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Improving the efficiency of the Branch and Bound algorithm for integer programming based on flatness information.pdf
Size:
2.43 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas