| Title:
|
A contribution to Balas' algorithm (English) |
| Author:
|
Hrouda, Jaroslav |
| Language:
|
English |
| Journal:
|
Aplikace matematiky |
| ISSN:
|
0373-6725 |
| Volume:
|
16 |
| Issue:
|
5 |
| Year:
|
1971 |
| Pages:
|
336-353 |
| Summary lang:
|
English |
| Summary lang:
|
Czech |
| . |
| Category:
|
math |
| . |
| Summary:
|
The article gives an alternative destription of the Balas' algorithm (for the solution of the zero-one linear programming problem) suitable as a propedeutics for our next article. In addition, is systematizes and generalizes some older tests. () |
| MSC:
|
65K05 |
| MSC:
|
90C10 |
| idZBL:
|
Zbl 0246.90032 |
| idMR:
|
MR0465173 |
| DOI:
|
10.21136/AM.1971.103366 |
| . |
| Date available:
|
2008-05-20T17:51:34Z |
| Last updated:
|
2020-07-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/103366 |
| . |
| Reference:
|
[1] Balas E.: An additive algorithm for solving linear programs with zero-one variables.Operations Research 13 (1965), No 4, 517-546. Zbl 0194.19903, MR 0183535, 10.1287/opre.13.4.517 |
| Reference:
|
[2] Balas E.: Discrete programming by the filter method.Operations Research 15 (1967), No 5, 915-957. Zbl 0153.21401, MR 0281492, 10.1287/opre.15.5.915 |
| Reference:
|
[3] Bertier P., Nghiem P. T.: Résolution de problèmes en variables bivalentes.(Algorithms de Balas et procédure SEP). SEMA, Paris, Note D.S, No 33, 1965. |
| Reference:
|
[4] Brauer K. M.: A note on the efficiency of Balas' algorithm.Operations Research 15 (1967), No 6, 1169-1171. 10.1287/opre.15.6.1169 |
| Reference:
|
[5] Byrne J. L., Proll L. G.: Initialising Geoffrion's implicit enumeration algorithm for the zero-one linear programming problem.The Computer Journal 12 (1969), No 4, 381 - 384. Zbl 0185.42504, MR 0253527, 10.1093/comjnl/12.4.381 |
| Reference:
|
[6] Fleischmann B.: Computational experience with the algorithm of Balas.Operations Research 15 (1967), No 1, 153-155. 10.1287/opre.15.1.153 |
| Reference:
|
[7] Freeman R. J.: Computational experience with a Balasian integer programming algorithm.Operations Research 14 (1966), No 5, 935-941. 10.1287/opre.14.5.935 |
| Reference:
|
[8] Geoffrion A. M.: Integer programming by implicit enumeration and Balas' method.SIAM Review 9 (1967), No 2, 178-190. Zbl 0213.44702, MR 0213156, 10.1137/1009031 |
| Reference:
|
[9] Geoffrion A. M.: An improved implicit enumeration approach for integer programming.Operations Research 17 (1969), No 3, 437-454. Zbl 0174.20801, 10.1287/opre.17.3.437 |
| Reference:
|
[10] Glover F.: A multiphase-dual algorithm for the zero-one integer programming problem.Operations Research 13 (1965), No 6, 879-919. Zbl 0163.41301, 10.1287/opre.13.6.879 |
| Reference:
|
[11] Glover F.: Surrogate constraints.Operations Research 16 (1968), No 4, 741 - 749. Zbl 0165.22602, MR 0250670, 10.1287/opre.16.4.741 |
| Reference:
|
[12] Glover F., Zionts S.: A note on the additive algorithm of Balas.Operations Research 13 (1965), No 4, 546-549. Zbl 0196.22705, MR 0183536, 10.1287/opre.13.4.546 |
| Reference:
|
[13] Golomb S. W., Baumert L. D.: Backtrack programming.Journal ACM 12 (1965), No 4, 516-524. Zbl 0139.12305, MR 0195585, 10.1145/321296.321300 |
| Reference:
|
[14] Gue R. L., Liggett J. C., Cain K. C.: Analysis of algorithms for the zero-one programming problem.Communications ACM 11 (1968), No 12, 837-844. 10.1145/364175.364209 |
| Reference:
|
[15] Hrouda J.: Jeden popis Balasova aditivního algoritmu se zřetelem k programování.Ekonomicko-matematický obzor 5 (1969), No 1, 45-59. MR 0242481 |
| Reference:
|
[16] Hrouda J.: Staging in Balas' algorithm.This issue, 354-369. Zbl 0243.90025, MR 0465174 |
| Reference:
|
[17] Hrouda J.: Tři příspěvky k bivalentnímu lineárnímu programování.Příloha k výzkumné zprávě VZ-321/70, VÚTECHP, Praha 1970. |
| Reference:
|
[18] Корбут А. А., Финкелъштейн Ю. Ю.: Дискретное программирование.Наука, Москва 1969. Zbl 1149.62317 |
| Reference:
|
[19] Lemke C. E., Spielberg K.: Direct search algorithms for zero-one and mixed-integer programming.Operations Research 15 (1967), No 5, 892-914. Zbl 0168.18201, MR 0281494, 10.1287/opre.15.5.892 |
| Reference:
|
[20] Petersen C. C.: Computational experience with variants of the Balas algorithm applied to the selection of R & D projects.Management Science 13 (1967), No 9, 736-750. |
| Reference:
|
[21] Walker R. J.: An enumerative technique for a class of combinatorial problems.Proceedings of Symposia in Applied Mathematics, vol. 10 (eds. R. Bellman, M. Hall), Providence 1960, 91-94. Zbl 0096.00603, MR 0121306 |
| Reference:
|
[22] : Výzkumná zpráva VZ-124/68.(řešitel J. Hrouda). VÚTECHP, Praha 1968. |
| Reference:
|
[23] : Výzkumná zpráva VZ-211/69.(řešitel J. Tesař). VÚTECHP, Praha 1969, 42-46. |
| . |
