Geodesic
A contribution to Balas' algorithm
Applications of Mathematics, Tome 16 (1971) no. 5, pp. 336-353
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/AM.1971.103366
Classification : 65K05, 90C10 
@article{10_21136_AM_1971_103366,
     author = {Hrouda, Jaroslav},
     title = {A contribution to {Balas'} algorithm},
     journal = {Applications of Mathematics},
     pages = {336--353},
     year = {1971},
     volume = {16},
     number = {5},
     doi = {10.21136/AM.1971.103366},
     mrnumber = {0465173},
     zbl = {0246.90032},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/AM.1971.103366/}
}
TY  - JOUR
AU  - Hrouda, Jaroslav
TI  - A contribution to Balas' algorithm
JO  - Applications of Mathematics
PY  - 1971
SP  - 336
EP  - 353
VL  - 16
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.21136/AM.1971.103366/
DO  - 10.21136/AM.1971.103366
LA  - en
ID  - 10_21136_AM_1971_103366
ER  - 
%0 Journal Article
%A Hrouda, Jaroslav
%T A contribution to Balas' algorithm
%J Applications of Mathematics
%D 1971
%P 336-353
%V 16
%N 5
%U http://geodesic.mathdoc.fr/articles/10.21136/AM.1971.103366/
%R 10.21136/AM.1971.103366
%G en
%F 10_21136_AM_1971_103366
Hrouda, Jaroslav. A contribution to Balas' algorithm. Applications of Mathematics, Tome 16 (1971) no. 5, pp. 336-353. doi: 10.21136/AM.1971.103366

[1] Balas E.: An additive algorithm for solving linear programs with zero-one variables. Operations Research 13 (1965), No 4, 517-546. | DOI | MR | Zbl

[2] Balas E.: Discrete programming by the filter method. Operations Research 15 (1967), No 5, 915-957. | DOI | MR | Zbl

[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.

[4] Brauer K. M.: A note on the efficiency of Balas' algorithm. Operations Research 15 (1967), No 6, 1169-1171. | DOI

[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. | DOI | MR | Zbl

[6] Fleischmann B.: Computational experience with the algorithm of Balas. Operations Research 15 (1967), No 1, 153-155. | DOI

[7] Freeman R. J.: Computational experience with a Balasian integer programming algorithm. Operations Research 14 (1966), No 5, 935-941. | DOI

[8] Geoffrion A. M.: Integer programming by implicit enumeration and Balas' method. SIAM Review 9 (1967), No 2, 178-190. | DOI | MR | Zbl

[9] Geoffrion A. M.: An improved implicit enumeration approach for integer programming. Operations Research 17 (1969), No 3, 437-454. | DOI | Zbl

[10] Glover F.: A multiphase-dual algorithm for the zero-one integer programming problem. Operations Research 13 (1965), No 6, 879-919. | DOI | Zbl

[11] Glover F.: Surrogate constraints. Operations Research 16 (1968), No 4, 741 - 749. | DOI | MR | Zbl

[12] Glover F., Zionts S.: A note on the additive algorithm of Balas. Operations Research 13 (1965), No 4, 546-549. | DOI | MR | Zbl

[13] Golomb S. W., Baumert L. D.: Backtrack programming. Journal ACM 12 (1965), No 4, 516-524. | DOI | MR | Zbl

[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. | DOI

[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

[16] Hrouda J.: Staging in Balas' algorithm. This issue, 354-369. | MR | Zbl

[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.

[18] Корбут А. А., Финкелъштейн Ю. Ю.: Дискретное программирование. Наука, Москва 1969. | Zbl

[19] Lemke C. E., Spielberg K.: Direct search algorithms for zero-one and mixed-integer programming. Operations Research 15 (1967), No 5, 892-914. | DOI | MR | Zbl

[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.

[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. | MR | Zbl

[22] Výzkumná zpráva VZ-124/68. (řešitel J. Hrouda). VÚTECHP, Praha 1968.

[23] Výzkumná zpráva VZ-211/69. (řešitel J. Tesař). VÚTECHP, Praha 1969, 42-46.

Cité par Sources :