| Title:
|
The Benders method and parametrization of the right-hand sides in the mixed integer linear programming problem (English) |
| Author:
|
Hrouda, Jaroslav |
| Language:
|
English |
| Journal:
|
Aplikace matematiky |
| ISSN:
|
0373-6725 |
| Volume:
|
21 |
| Issue:
|
5 |
| Year:
|
1976 |
| Pages:
|
327-364 |
| Summary lang:
|
English |
| Summary lang:
|
Czech |
| Summary lang:
|
Russian |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. () |
| MSC:
|
90C10 |
| idZBL:
|
Zbl 0357.90041 |
| DOI:
|
10.21136/AM.1976.103656 |
| . |
| Date available:
|
2008-05-20T18:05:35Z |
| Last updated:
|
2020-07-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/103656 |
| . |
| Reference:
|
[1] Белоусов E. Г.: Некоторые вопросы теории выпуклых множеств и целочисленного программирования.Иссл. по мат. экон. и смеж. вопр., Моск. унив., Москва 1971, 207-276. Zbl 1170.92344 |
| Reference:
|
[2] Белоусов E. Г.: Об ограниченности и разрешимости задачи полиномиального целочисленного программирования.Вопр. экон.-мат. моделир., Моск. унив., Москва 1973, 299-312. Zbl 1170.01397 |
| Reference:
|
[3] Белоусов E. Г., Бабыков Г. H.: Некоторые свойства задачи выпуклого целочисленного программирования.Моделирование экономических процессов, 1969, вып. 4, 363-390. Zbl 1149.62317 |
| Reference:
|
[4] Голъштейн E. Г., Юдин Д. Б.: Новые направления в линейном программировании.Советское радио, Москва 1966. Zbl 1155.78304 |
| Reference:
|
[5] Gould F. J., Rubin D. S.: Rationalizing discrete programs.Operations Research 21 (1973), No 1, 343-345. Zbl 0259.90025, MR 0354005 |
| Reference:
|
[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 0373599 |
| Reference:
|
[7] Юдин Д. Б., Голъштейн E. Г.: Линейное программирование.Физматгиз, Москва 1963. Zbl 1145.93303 |
| Reference:
|
[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. Zbl 0292.90036, MR 0373602, 10.1007/BF01585518 |
| Reference:
|
[9] Широнин B. M.: О регулярности задачи целочисленного программирования.Вопр. экон.-мат. моделир., Моск. унив., Москва 1973, 313 - 328. Zbl 1170.01397 |
| Reference:
|
[10] Balinski M. L.: Integer programming: methods, uses, computation.Management Science 12 (1965), No 3, 253-313. Zbl 0129.12004, MR 0192924 |
| Reference:
|
[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. |
| Reference:
|
[12] Benders J. F.: Partitioning procedures for solving mixed-variables programming problems.Numerische Mathematik 4 (1962), 238-252. Zbl 0109.38302, MR 0147303, 10.1007/BF01386316 |
| Reference:
|
[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. |
| Reference:
|
[14] Garfinkel R. S., Nemhauser G. L.: Integer programming.J. Wiley, New York 1972. Zbl 0259.90022, MR 0381688 |
| Reference:
|
[15] Geoffrion A. M.: Elements of large-scale mathematical programming.Management Science 16 (1970), No 11, I. 652-675, II. 676-691. Zbl 0209.22801, 10.1287/mnsc.16.11.652 |
| Reference:
|
[16] Geoffrion A. M.: Generalized Benders decomposition.Working paper No 159, Western Manag. Sci. Inst., UCLA, 1971. MR 0327310 |
| Reference:
|
[17] Geoffrion A. M., Graves G. W.: Multicommodity distribution system design by Benders decomposition.Management Science 20 (1974), No 5, 822-844. Zbl 0304.90122, MR 0329614, 10.1287/mnsc.20.5.822 |
| Reference:
|
[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. Zbl 0238.90043, MR 0309548, 10.1287/mnsc.18.9.465 |
| Reference:
|
[19] Hrouda J.: Modified Benders' algorithm.Ekonomicko-matematický obzor 11 (1975), No 4, 423-443. (In Czech.) MR 0489864 |
| Reference:
|
[20] Mc Daniel D., Devine M.: Alternative Benders-based partitioning procedures for mixed integer programming.ORSA Meeting, Milwaukee 1973, 12 pp. (mimeograph). |
| Reference:
|
[21] Zoutendijk G.: Mixed integer programming and the warehouse allocation problem.Applications Math. Progr. Techniques (Beale ed.), English Universities Press, 1970. MR 0347367 |
| Reference:
|
[22] Bowman V. J., Jr.: Sensitivity analysis in linear integer programming.A reprint from 1912 AIIE Technical papers. |
| Reference:
|
[23] Frank C. R.: Parametric programming in integers.Operations Research Verfahren 3 (1967), p. 167. Zbl 0235.90039 |
| Reference:
|
[24] Gomory R. E., Baumol W. J.: Integer programming and pricing.Econometrica 28 (1960), 521-550. Zbl 0095.14502, MR 0115822, 10.2307/1910130 |
| Reference:
|
[25] Hrouda J.: The parametrization in the mixed integer linear programming problem.Dissertation, Praha 1973, 115 pp. (In Czech.) |
| Reference:
|
[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.) |
| Reference:
|
[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.) |
| Reference:
|
[28] Jensen R. E.: Sensitivity analysis and integer linear programming.The Accounting Review 43 (1968), No 3, 425-446. |
| Reference:
|
[29] Nauss R. M.: Parametric integer programming.Working paper No 226, Western Manag. Sci. Inst., UCLA, 1975. |
| Reference:
|
[30] Noltemeier H.: Sensitivitätsanalyse bei diskreten linearen Optimierungsproblemen.Springer, Berlin 1970. Zbl 0203.52204, MR 0281495 |
| Reference:
|
[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. |
| Reference:
|
[32] Roodman G. M.: Postoptimality analysis in zero-one programming by implicit enumeration.Naval Res. Log. Quart. 19 (1972), No 3, 435-447. Zbl 0262.90047, MR 0316089, 10.1002/nav.3800190304 |
| Reference:
|
[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. MR 0368756, 10.1002/nav.3800210404 |
| Reference:
|
[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 0300644 |
| Reference:
|
[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 0314458 |
| . |
