hrcak mascot   Srce   HID

Original scientific paper

THE RAY-METHOD: THEORETICAL BACKGROUND AND COMPUTATIONAL RESULTS

Erik Bajalinov ; Institute of Mathematics and Informatics, University College of Nyíregyháza, Nyíregyháza, Hungary
Anett Rácz ; Faculty of Informatics, Debrecen University, Debrecen, Hungary

Fulltext: english, pdf (407 KB) pages 137-149 downloads: 312* cite
APA 6th Edition
Bajalinov, E. & Rácz, A. (2012). THE RAY-METHOD: THEORETICAL BACKGROUND AND COMPUTATIONAL RESULTS. Croatian Operational Research Review, 3 (1), 137-149. Retrieved from https://hrcak.srce.hr/96810
MLA 8th Edition
Bajalinov, Erik and Anett Rácz. "THE RAY-METHOD: THEORETICAL BACKGROUND AND COMPUTATIONAL RESULTS." Croatian Operational Research Review, vol. 3, no. 1, 2012, pp. 137-149. https://hrcak.srce.hr/96810. Accessed 18 Oct. 2019.
Chicago 17th Edition
Bajalinov, Erik and Anett Rácz. "THE RAY-METHOD: THEORETICAL BACKGROUND AND COMPUTATIONAL RESULTS." Croatian Operational Research Review 3, no. 1 (2012): 137-149. https://hrcak.srce.hr/96810
Harvard
Bajalinov, E., and Rácz, A. (2012). 'THE RAY-METHOD: THEORETICAL BACKGROUND AND COMPUTATIONAL RESULTS', Croatian Operational Research Review, 3(1), pp. 137-149. Available at: https://hrcak.srce.hr/96810 (Accessed 18 October 2019)
Vancouver
Bajalinov E, Rácz A. THE RAY-METHOD: THEORETICAL BACKGROUND AND COMPUTATIONAL RESULTS. Croatian Operational Research Review [Internet]. 2012 [cited 2019 October 18];3(1):137-149. Available from: https://hrcak.srce.hr/96810
IEEE
E. Bajalinov and A. Rácz, "THE RAY-METHOD: THEORETICAL BACKGROUND AND COMPUTATIONAL RESULTS", Croatian Operational Research Review, vol.3, no. 1, pp. 137-149, 2012. [Online]. Available: https://hrcak.srce.hr/96810. [Accessed: 18 October 2019]

Abstracts
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 [13], [14]. Instead of solving a common integer programming problem we use the main idea of the ray-method to find an integer feasible solution of
integer linear programming (ILP) problem along the ray as close to optimal solution of relaxation problem, as possible. Objective value obtained in this way may be used as an initial bound for B&B
method. The algorithm has been implemented in the frame of educational package WinGULF [3] for linear and linear-fractional programming and has been tested on various ILP problems. Then inspired by the results obtained we implemented the method using the so-called callable library of CPLEX package by IBM. omputational experiments with the algorithm proposed show that such preprocessing procedure in many cases results 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 significantly decrease the size of the binary tree to be searched and in this manner can improve performance of the B&B method.

Keywords
branch and bound; integer programming

Hrčak ID: 96810

URI
https://hrcak.srce.hr/96810

Visits: 454 *