Determining initial bound by "Ray-method" in branch and bound procedure
In this paper we present an algorithm for determining initial bound for the Branch and Bound (B&B) method. The idea of this algorithm is based on the use of "ray" as introduced in the "ray-method" developed for solving integer linear programming problems [11], [12]. Instead o...
Elmentve itt :
| Szerző: | |
|---|---|
| Testületi szerző: | |
| Dokumentumtípus: | Cikk |
| Megjelent: |
2009
|
| Sorozat: | Acta cybernetica
19 No. 1 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Tárgyszavak: | |
| doi: | 10.14232/actacyb.19.1.2009.9 |
| Online Access: | http://acta.bibl.u-szeged.hu/12857 |
| LEADER | 01624nab a2200241 i 4500 | ||
|---|---|---|---|
| 001 | acta12857 | ||
| 005 | 20220617102207.0 | ||
| 008 | 161015s2009 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 024 | 7 | |a 10.14232/actacyb.19.1.2009.9 |2 doi | |
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Rácz Anett | |
| 245 | 1 | 0 | |a Determining initial bound by "Ray-method" in branch and bound procedure |h [elektronikus dokumentum] / |c Rácz Anett |
| 260 | |c 2009 | ||
| 300 | |a 135-146 | ||
| 490 | 0 | |a Acta cybernetica |v 19 No. 1 | |
| 520 | 3 | |a In this paper we present an algorithm for determining initial bound for the Branch and Bound (B&B) method. The idea of this algorithm is based on the use of "ray" as introduced in the "ray-method" developed for solving integer linear programming problems [11], [12]. Instead of solving an integer programming problem we use the main idea of the ray-method to find an integer feasible solution of an integer linear programming problem along the ray as close to an optimal solution of the relaxation problem as possible. The objective value obtained in this manner may be used as an initial bound for the B&B method. It is well known that getting a "good bound" as soon as possible can often significantly increase the performance of the B&B method. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Számítástechnika, Kibernetika | ||
| 710 | |a Conference for PhD Students in Computer Science (6.) (2008) (Szeged) | ||
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/12857/1/actacyb_19_1_2009_9.pdf |z Dokumentum-elérés |