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

Derpich I.; Vera, JR

Abstract

This 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. © 2005 Elsevier B.V. All rights reserved.

Más información

Título según WOS: Improving the efficiency of the Branch and Bound algorithm for integer programming based on "flatness" information
Título según SCOPUS: Improving the efficiency of the Branch and Bound algorithm for integer programming based on "flatness" information
Título de la Revista: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volumen: 174
Número: 1
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 2006
Página de inicio: 92
Página final: 101
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S0377221705002614
DOI:

10.1016/j.ejor.2005.02.051

Notas: ISI, SCOPUS