PL EN


2018 | 28 | 2 | 5-21
Article title

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

Content
Title variants
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.
Year
Volume
28
Issue
2
Pages
5-21
Physical description
Contributors
author
  • Department of Mathematics, Keshav Mahavidyalaya, University of Delhi, H-4-5 Zone, Road No. 43, Pitampura Near Sainik Vihar, Delhi 110034, India, ritunarora@yahoo.in
author
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.
Document Type
Publication order reference
Identifiers
YADDA identifier
bwmeta1.element.desklight-63888c61-bae9-41f8-9867-367f7eadaa36
JavaScript is turned off in your web browser. Turn it on to take full advantage of this site, then refresh the page.