On the Ray-based procedure for determining initial bound in branch and bound method
| dc.contributor.author | Bajalinov, Erik | |
| dc.contributor.author | Rácz, Anett | |
| dc.date.accessioned | 2013-04-30T09:59:52Z | |
| dc.date.available | 2013-04-30T09:59:52Z | |
| dc.date.conferenceend | 2009-12-17 | |
| dc.date.conferencestart | 2008-12-15 | |
| dc.date.issued | 2013-04-30 | |
| dc.description.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. | en_US |
| dc.description.city | Veszprém | en_US |
| dc.description.conferencetype | International | en_US |
| dc.description.country | Hungary | en_US |
| dc.identifier.uri | http://hdl.handle.net/123456789/306 | |
| dc.language.iso | en | en_US |
| dc.subject | IP | en_US |
| dc.subject | B&B | en_US |
| dc.subject | Initial bound | en_US |
| dc.title | On the Ray-based procedure for determining initial bound in branch and bound method | en_US |
| dc.title.conference | International Conference Advanced Algorithms (VOCAL 2008) | en_US |
| dc.type.class | Lecture | en_US |
| dc.type.specification | Scientific | en_US |