On the Ray-based procedure for determining initial bound in branch and bound method

Abstract

In our talk we present an algorithm for determining initial bound for the Branch and Bound (B&B) method. The idea of the algorithm is based on the use of the "ray" introduced in the "ray-method" developed for solving integer programming problems [2], [3]. Instead of solving a common integer programming problem we use the main idea of the ray-method to nd an integer feasible solution of integer linear programming (ILP) problem along the ray as close to optimal solution of re- laxation problem, as possible. Objective value obtained in this way may be used as initial bound for B&B method. The algorithm has been implemented in the frame of educational package WinGULF [1] for linear and linear-fractional programming and has been tested on various ILP problems. Computational experiments with the algorithm proposed show that such preprocessing procedure in many cases re- sults an integer feasible solution very close to the solution of relaxation problem. Initial bound for branch and bound method determined in this way often can signif- icantly decrease the size of the tree to be searched and in this manner can improve performance of the B&B method.