Original scientific paper
https://doi.org/10.17535/crorr.2017.0008
Accelerating the B&B algorithm for integer programming based on flatness information: an approach applied to the multidimensional knapsack problem
Ivan S. Derpich
orcid.org/0000-0001-9759-7285
; Industrial Engineering Department, Universidad de Santiago de Chile, 3363 Av.Estación Central, Santiago, Chile
Juan M. Sepúlveda
orcid.org/0000-0003-3755-0981
; Industrial Engineering Department, Universidad de Santiago de Chile, 3363 Av.Estación Central, Santiago, Chile
Abstract
This paper presents a new branching rule based on the flatness of a polyhedron associated to the set of constraints in an integer linear programming problem. The rule called Flatness II is a heuristic technique used with the branch-and-bound method. The rule is concerned with the minimum integer width vector. Empirical evidence supports the conjecture that the direction with the highest value of the vector’s components indicates a suitable branching direction. The paper provides theoretical results demonstrating that the columns of the matrix A corresponding to a set of constraints Ax≤b may be used to estimate the minimum integer width vector; this fact is used for constructing a new version of the branching rule as was reported in a previous paper by the authors. In addition, the new rule uses a branching direction that chooses the child node closest to the integer value (either up or down). Thus, it uses a variable rule for descending the tree. Every time a new sub-problem is solved, the list of remaining unsolved sub-problems is analyzed, with priority given to those problems with a minimum objective function value estimate. The conclusions of the work are based on knapsack problems from the knapsack OR-Library. From the results, it is concluded that the new rule Flatness II presents low execution times and minimal number of nodes generated.
Keywords
integer programming; branch-and-bound method; branching rule; algorithm efficiency
Hrčak ID:
181653
URI
Publication date:
15.4.2017.
Visits: 1.595 *