Branch and bound algorithm for discrete multi- level linear fractional programming problem

• Autorzy: Arora R. , Gupta K.

Identyfikatory

DOI

10.5277/ord180201

• Języki publikacji: EN

Abstrakty

EN

An algorithm is proposed to find an integer solution for bilevel linear fractional programming problem with discrete variables. The method develops a cut that removes the integer solutions which are not bilevel feasible. The proposed method is extended from bilevel to multilevel linear fractional programming problems with discrete variables. The solution procedure for both the algorithms is elucidated in the paper.

Słowa kluczowe

EN

linear fractional programming problem; bilevel programming; multilevel programming; discrete variables; integer solution; branch and bound cut

PL

programowanie dwustopniowe; programowanie wielopoziomowe; zmienne dyskretne

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Operations Research and Decisions
• Rocznik: 2018
• Tom: Vol. 28, No. 2
• Strony: 5--21
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Arora R.

• Department of Mathematics, Keshav Mahavidyalaya, University of Delhi, H-4-5 Zone, Road No. 43, Pitampura Near Sainik Vihar, Delhi 110034, India

autor

Gupta K.

• Department of Mathematics, Kirori Mal College, University of Delhi, Delhi 110007, India

Bibliografia

• [1] BARD J.F., FALK J.E., An explicit solution to the multilevel programming problem, Comp. Oper. Res., 1982, 9, 77–100.
• [2] BARD J.F., MOORE J.J., A branch and bound algorithm for the bilevel programming problem, SIAM J. Sci. Stat. Comp., 1990, 11, 281–292.
• [3] BHARGAVA S., Solving linear fractional multilevel programs, Oper. Res. Dec., 2014, 24,1, 1–17.
• [4] BIENSTOCK D., Computational study of a family of mixed integer quadratic programming problems, Math. Progr., 1996, 74, 121–140.
• [5] CALVETE H.I., GALE C., Local optimality in quasiconcave bilevel programming, Monog. Semin. Matem. Gracia de Galdeano, 2003, 27, 153–160.
• [6] CALVETE H.I., GALE C., A penalty method for solving bilevel linear fractional/linear programming problem, Asia Pacific J. Oper. Res., 2004, 21, 2, 207–224.
• [7] CANDLER W., NORTON R., Multilevel programming, Technical Report 20, World Bank Development Research Centre, Washington, D.C., 1977.
• [8] CHARNES A., COOPER W.W., Programming with linear fractional functional, Naval Res. Log. Quart., 1962, 9, 181–186.
• [9] CLAASSEN G.D.H., Mixed integer (0–1) fractional programming for decision support in paper production industry, Omega, 2014, 43, 21–29.
• [10] COSTA L.H.M., PRATA B.A., RAMOS H.M., CASTRO M.A.H., A branch and bound algorithm for optimal pump scheduling in water distribution networks, Water Res. Manage., 2016, 30 (3), 1037–1052.
• [11] DEMPE S., KALASHNIKOV V., RIOS-MERCADO R.Z., Discrete bilevel programming. Application to a natural gas cash-out problem, Eur. J. Oper. Res., 2005, 166 (2), 469–488.
• [12] DINKELBACH W., On non-linear fractional programming, Manage. Sci., 1967, 13, 492–498.
• [13] FALK J.E., SOLAND R.M., An algorithm for solving separable non-convex programming problems, Manage. Sci., 1969, 15, 550–569.
• [14] HERNANDEZ M., GOMEZ T., MOLINA J., LEON M.A., Applications of multi-criteria techniques to plan the harvest of a forest taken into account different kinds of objectives, Intelligence Systems in Environmental Management. Theory and Applications, Part of the Intelligent Systems Reference Library Book Series, ISRL, 2017, 113, 367–383.
• [15] LAND A.H., DOIG A.G., An automatic method for solving discrete programming problems, Econometrica, 1960, 28, 497–520.
• [16] LU J., HAN J., HU Y., ZHANG G., Multilevel decision making. A survey, Inf. Sci., 2016, (346–347), 463–487.
• [17] LUEDTKE J., A branch and cut decomposition algorithm for solving chance-constrained mathematical programs with finite support, Math. Prog., 2014, 146 (1–2), 219–244.
• [18] MAROTI G., A branch and bound approach for robust railway time tabling, Public Transp., 2017, 9 (1–2), 73–94.
• [19] MATHUR K., PURI M.C., On bilevel fractional programming, Optimization, 1995, 35, 215–226.
• [20] MIGDALAS A., PARDALOS P.M., VARBRAND P., Multilevel optimization. Algorithms and Applications, Vol. 20, Springer, 1998.
• [21] MURTY K.G., Solving the fixed charge problem by ranking the extreme points, Oper. Res., 1969, 16, 268–279.
• [22] PAL B.B., GUPTA S., A genetic algorithm based fuzzy goal programming approach for solving fractional bilevel programming problems, Int. J. Oper. Res., 2012, 14, 4, 453–471.
• [23] PEREZ J.C., CARRILLO M.H., MONTOYA-TORRES J.R., Multi-criteria approaches for urban passenger transport systems. A literature review, Ann. Oper. Res., 2015, 226 (1), 69–87.
• [24] SCHIABLE S., Fractional programming applications and algorithms, Eur. J. Oper. Res., 1981, 7, 111–120.
• [25] SWARUP K., Linear fractional functional programming, Oper. Res., 1965, 13 (6), 1029–1036.
• [26] WHITE D.J., ANANDALINGAM G., A penalty function approach for solving bilevel linear programs, J. Global Opt., 1993, 3, 397–419.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).