Geodesic
The Benders method and parametrization of the right-hand sides in the mixed integer linear programming problem
Applications of Mathematics, Tome 21 (1976) no. 5, pp. 327-364
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

The problem indicated in the title is solved by means of a Bendersian dual decomposition method. The algorithm proposed is procedurally conformal with the well-known Benders algorithm. The problem is solved approximately in the sense of $\epsilon$-suboptimality for special cases of the general parametric problem. The Benders method (also for point optimization) is generalized for an unbounded set of integer variables and equality constraint conditions. The method is illustrated by a numerical example.
The problem indicated in the title is solved by means of a Bendersian dual decomposition method. The algorithm proposed is procedurally conformal with the well-known Benders algorithm. The problem is solved approximately in the sense of $\epsilon$-suboptimality for special cases of the general parametric problem. The Benders method (also for point optimization) is generalized for an unbounded set of integer variables and equality constraint conditions. The method is illustrated by a numerical example.
DOI : 10.21136/AM.1976.103656
Classification : 90C10 
@article{10_21136_AM_1976_103656,
     author = {Hrouda, Jaroslav},
     title = {The {Benders} method and parametrization of the right-hand sides in the mixed integer linear programming problem},
     journal = {Applications of Mathematics},
     pages = {327--364},
     year = {1976},
     volume = {21},
     number = {5},
     doi = {10.21136/AM.1976.103656},
     zbl = {0357.90041},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/AM.1976.103656/}
}
TY  - JOUR
AU  - Hrouda, Jaroslav
TI  - The Benders method and parametrization of the right-hand sides in the mixed integer linear programming problem
JO  - Applications of Mathematics
PY  - 1976
SP  - 327
EP  - 364
VL  - 21
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.21136/AM.1976.103656/
DO  - 10.21136/AM.1976.103656
LA  - en
ID  - 10_21136_AM_1976_103656
ER  - 
%0 Journal Article
%A Hrouda, Jaroslav
%T The Benders method and parametrization of the right-hand sides in the mixed integer linear programming problem
%J Applications of Mathematics
%D 1976
%P 327-364
%V 21
%N 5
%U http://geodesic.mathdoc.fr/articles/10.21136/AM.1976.103656/
%R 10.21136/AM.1976.103656
%G en
%F 10_21136_AM_1976_103656
Hrouda, Jaroslav. The Benders method and parametrization of the right-hand sides in the mixed integer linear programming problem. Applications of Mathematics, Tome 21 (1976) no. 5, pp. 327-364. doi: 10.21136/AM.1976.103656

[1] Белоусов E. Г.: Некоторые вопросы теории выпуклых множеств и целочисленного программирования. Иссл. по мат. экон. и смеж. вопр., Моск. унив., Москва 1971, 207-276. | Zbl

[2] Белоусов E. Г.: Об ограниченности и разрешимости задачи полиномиального целочисленного программирования. Вопр. экон.-мат. моделир., Моск. унив., Москва 1973, 299-312. | Zbl

[3] Белоусов E. Г., Бабыков Г. H.: Некоторые свойства задачи выпуклого целочисленного программирования. Моделирование экономических процессов, 1969, вып. 4, 363-390. | Zbl

[4] Голъштейн E. Г., Юдин Д. Б.: Новые направления в линейном программировании. Советское радио, Москва 1966. | Zbl

[5] Gould F. J., Rubin D. S.: Rationalizing discrete programs. Operations Research 21 (1973), No 1, 343-345. | MR | Zbl

[6] Grabowski W.: O rozwiązalności problemu programowania liniowego w liczbach całkowitych. Zeszyty naukowe Szkoły głownej plan. i stat., 1972, No 86, 71 - 79. | MR

[7] Юдин Д. Б., Голъштейн E. Г.: Линейное программирование. Физматгиз, Москва 1963. | Zbl

[8] Meyer R. R.: On the existence of optimal solutions to integer and mixed-integer programming problems. Mathematical Programming 7 (1974), No 2, 223 - 235. | DOI | MR | Zbl

[9] Широнин B. M.: О регулярности задачи целочисленного программирования. Вопр. экон.-мат. моделир., Моск. унив., Москва 1973, 313 - 328. | Zbl

[10] Balinski M. L.: Integer programming: methods, uses, computation. Management Science 12 (1965), No 3, 253-313. | MR | Zbl

[11] Bellmore M., Frank R. S.: The pathology of the Benders' partitioning algorithm applied to the fixed-charge Hitchcock transportation problem. Working paper HBS-73-15, Graduate School of Business Administration, Harvard Univ.

[12] Benders J. F.: Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4 (1962), 238-252. | DOI | MR | Zbl

[13] Etschmaier M. M., Richardson R. J.: Improving efficiency of Benders' decomposition algorithm for a special problem in transportation. Technical report No 14, University of Pittsburgh, 1973, 37 pp.

[14] Garfinkel R. S., Nemhauser G. L.: Integer programming. J. Wiley, New York 1972. | MR | Zbl

[15] Geoffrion A. M.: Elements of large-scale mathematical programming. Management Science 16 (1970), No 11, I. 652-675, II. 676-691. | DOI | Zbl

[16] Geoffrion A. M.: Generalized Benders decomposition. Working paper No 159, Western Manag. Sci. Inst., UCLA, 1971. | MR

[17] Geoffrion A. M., Graves G. W.: Multicommodity distribution system design by Benders decomposition. Management Science 20 (1974), No 5, 822-844. | DOI | MR | Zbl

[18] Geoffrion A. M., Marsten R. E.: Integer programming algorithms: a framework and state-of-the-art survey. Management Science 18 (1972), No 9, 465-491. | DOI | MR | Zbl

[19] Hrouda J.: Modified Benders' algorithm. Ekonomicko-matematický obzor 11 (1975), No 4, 423-443. (In Czech.) | MR

[20] Mc Daniel D., Devine M.: Alternative Benders-based partitioning procedures for mixed integer programming. ORSA Meeting, Milwaukee 1973, 12 pp. (mimeograph).

[21] Zoutendijk G.: Mixed integer programming and the warehouse allocation problem. Applications Math. Progr. Techniques (Beale ed.), English Universities Press, 1970. | MR

[22] Bowman V. J., Jr.: Sensitivity analysis in linear integer programming. A reprint from 1912 AIIE Technical papers.

[23] Frank C. R.: Parametric programming in integers. Operations Research Verfahren 3 (1967), p. 167. | Zbl

[24] Gomory R. E., Baumol W. J.: Integer programming and pricing. Econometrica 28 (1960), 521-550. | DOI | MR | Zbl

[25] Hrouda J.: The parametrization in the mixed integer linear programming problem. Dissertation, Praha 1973, 115 pp. (In Czech.)

[26] Hrouda J.: Parametrizing the right-hand sides in the mixed integer linear programming. 3rd conference on mathematical methods in econometrics (Zadov), EÚ ČSAV, Praha 1974, 151-165. (In Czech.)

[27] Hrouda J.: A parametric variant of the Benders method in the mixed integer linear programming. Research Report No VZ 666/74, VÚTECHP, Praha 1974, 45-61. (In Czech.)

[28] Jensen R. E.: Sensitivity analysis and integer linear programming. The Accounting Review 43 (1968), No 3, 425-446.

[29] Nauss R. M.: Parametric integer programming. Working paper No 226, Western Manag. Sci. Inst., UCLA, 1975.

[30] Noltemeier H.: Sensitivitätsanalyse bei diskreten linearen Optimierungsproblemen. Springer, Berlin 1970. | MR | Zbl

[31] Piper C. J., Zoltners A. A.: Implicit enumeration based algorithms for postoptimizing zero-one programs. Management Science Reseach Report No 313, Carnegie-Mellon University, 1973.

[32] Roodman G. M.: Postoptimality analysis in zero-one programming by implicit enumeration. Naval Res. Log. Quart. 19 (1972), No 3, 435-447. | DOI | MR | Zbl

[33] Roodman G. M.: Postoptimality analysis in integer programming by implicit enumeration: the mixed integer case. Naval Res. Log. Quart. 21 (1974), No 4, 595-607. | DOI | MR

[34] Trávníček J.: An approach to the solution of the parametric zero-one integer programming problem with the parameter in one right-hand side. Ekonomicko-matematický obzor 8 (1972), No 1, 83-98. (In Czech.) | MR

[35] Trávníček J.: Parametric zero-one programming with the parametrized objective function. Ekonomicko-matematický obzor 8 (1972), No 4, 417-425. (In Czech.) | MR

Cité par Sources :