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

dc.contributor.authorBajalinov, Erik
dc.contributor.authorRácz, Anett
dc.date.accessioned2013-04-30T09:59:52Z
dc.date.available2013-04-30T09:59:52Z
dc.date.conferenceend2009-12-17
dc.date.conferencestart2008-12-15
dc.date.issued2013-04-30
dc.description.abstractIn 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.cityVeszprémen_US
dc.description.conferencetypeInternationalen_US
dc.description.countryHungaryen_US
dc.identifier.urihttp://hdl.handle.net/123456789/306
dc.language.isoenen_US
dc.subjectIPen_US
dc.subjectB&Ben_US
dc.subjectInitial bounden_US
dc.titleOn the Ray-based procedure for determining initial bound in branch and bound methoden_US
dc.title.conferenceInternational Conference Advanced Algorithms (VOCAL 2008)en_US
dc.type.classLectureen_US
dc.type.specificationScientificen_US

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Bajalinov_Racz_Vocal_2008.pdf
Size:
116.23 KB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description: