On the Ray-based procedure for determining initial bound in branch and bound method
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.