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

• Authors: ARORA Ritu , GUPTA Kavita
• Languages of publication: EN

Abstracts

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.

Keywords

EN

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

• Publisher: Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
• Journal: Operations Research and Decisions
• Year: 2018
• Volume: 28
• Issue: 2
• Pages: 5-21

Contributors

author

ARORA Ritu

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

author

GUPTA Kavita

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

References

• BARD J.F., FALK J.E., An explicit solution to the multilevel programming problem, Comp. Oper. Res., 1982, 9, 77–100.
• 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.
• BHARGAVA S., Solving linear fractional multilevel programs, Oper. Res. Dec., 2014, 24,1, 1–17.
• BIENSTOCK D., Computational study of a family of mixed integer quadratic programming problems, Math. Progr., 1996, 74, 121–140.
• CALVETE H.I., GALE C., Local optimality in quasiconcave bilevel programming, Monog. Semin. Matem. Gracia de Galdeano, 2003, 27, 153–160.
• 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.
• CANDLER W., NORTON R., Multilevel programming, Technical Report 20, World Bank Development Research Centre, Washington, D.C., 1977.
• CHARNES A., COOPER W.W., Programming with linear fractional functional, Naval Res. Log. Quart., 1962, 9, 181–186.
• CLAASSEN G.D.H., Mixed integer (0–1) fractional programming for decision support in paper production industry, Omega, 2014, 43, 21–29.
• 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.
• 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.
• DINKELBACH W., On non-linear fractional programming, Manage. Sci., 1967, 13, 492–498.
• FALK J.E., SOLAND R.M., An algorithm for solving separable non-convex programming problems, Manage. Sci., 1969, 15, 550–569.
• 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.
• LAND A.H., DOIG A.G., An automatic method for solving discrete programming problems, Econometrica, 1960, 28, 497–520.
• LU J., HAN J., HU Y., ZHANG G., Multilevel decision making. A survey, Inf. Sci., 2016, (346–347), 463–487.
• 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.
• MAROTI G., A branch and bound approach for robust railway time tabling, Public Transp., 2017, 9 (1–2), 73–94.
• MATHUR K., PURI M.C., On bilevel fractional programming, Optimization, 1995, 35, 215–226.
• MIGDALAS A., PARDALOS P.M., VARBRAND P., Multilevel optimization. Algorithms and Applications, Vol. 20, Springer, 1998.
• MURTY K.G., Solving the fixed charge problem by ranking the extreme points, Oper. Res., 1969, 16, 268–279.
• 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.
• 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.
• SCHIABLE S., Fractional programming applications and algorithms, Eur. J. Oper. Res., 1981, 7, 111–120.
• SWARUP K., Linear fractional functional programming, Oper. Res., 1965, 13 (6), 1029–1036.
• WHITE D.J., ANANDALINGAM G., A penalty function approach for solving bilevel linear programs, J. Global Opt., 1993, 3, 397–419.
• BARD J.F., FALK J.E., An explicit solution to the multilevel programming problem, Comp. Oper. Res., 1982, 9, 77–100.
• 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.
• BHARGAVA S., Solving linear fractional multilevel programs, Oper. Res. Dec., 2014, 24,1, 1–17.
• BIENSTOCK D., Computational study of a family of mixed integer quadratic programming problems, Math. Progr., 1996, 74, 121–140.
• CALVETE H.I., GALE C., Local optimality in quasiconcave bilevel programming, Monog. Semin. Matem. Gracia de Galdeano, 2003, 27, 153–160.
• 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.
• CANDLER W., NORTON R., Multilevel programming, Technical Report 20, World Bank Development Research Centre, Washington, D.C., 1977.
• CHARNES A., COOPER W.W., Programming with linear fractional functional, Naval Res. Log. Quart., 1962, 9, 181–186.
• CLAASSEN G.D.H., Mixed integer (0–1) fractional programming for decision support in paper production industry, Omega, 2014, 43, 21–29.
• 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.
• 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.
• DINKELBACH W., On non-linear fractional programming, Manage. Sci., 1967, 13, 492–498.
• FALK J.E., SOLAND R.M., An algorithm for solving separable non-convex programming problems, Manage. Sci., 1969, 15, 550–569.
• 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.
• LAND A.H., DOIG A.G., An automatic method for solving discrete programming problems, Econometrica, 1960, 28, 497–520.
• LU J., HAN J., HU Y., ZHANG G., Multilevel decision making. A survey, Inf. Sci., 2016, (346–347), 463–487.
• 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.
• MAROTI G., A branch and bound approach for robust railway time tabling, Public Transp., 2017, 9 (1–2), 73–94.
• MATHUR K., PURI M.C., On bilevel fractional programming, Optimization, 1995, 35, 215–226.
• MIGDALAS A., PARDALOS P.M., VARBRAND P., Multilevel optimization. Algorithms and Applications, Vol. 20, Springer, 1998.
• MURTY K.G., Solving the fixed charge problem by ranking the extreme points, Oper. Res., 1969, 16, 268–279.
• 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.
• 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.
• SCHIABLE S., Fractional programming applications and algorithms, Eur. J. Oper. Res., 1981, 7, 111–120.
• SWARUP K., Linear fractional functional programming, Oper. Res., 1965, 13 (6), 1029–1036.
• WHITE D.J., ANANDALINGAM G., A penalty function approach for solving bilevel linear programs, J. Global Opt., 1993, 3, 397–419.

Identifiers

DOI

10.5277/ord180201