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

Loading...
Thumbnail Image

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.

Description

Keywords

Citation

Endorsement

Review

Supplemented By

Referenced By