%0 Journal Article
%T Accelerating the B&B algorithm for integer programming based on flatness information: an approach applied to the multidimensional knapsack problem
%A Derpich
%A Ivan S.
%A Sep¨²lveda
%A Juan M.
%J -
%D 2017
%R 10.17535/crorr.2017.0008
%X Sa£¿etak 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
%K integer programming
%K branch-and-bound method
%K branching rule
%K algorithm efficiency
%U https://hrcak.srce.hr/index.php?show=clanak&id_clanak_jezik=267766