IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v69y2017i1d10.1007_s10898-016-0487-4.html
   My bibliography  Save this article

Fractional 0–1 programming: applications and algorithms

Author

Listed:
  • Juan S. Borrero

    (University of Pittsburgh)

  • Colin Gillen

    (University of Pittsburgh)

  • Oleg A. Prokopyev

    (University of Pittsburgh
    National Research University Higher School of Economics)

Abstract

We consider a class of nonlinear integer optimization problems commonly known as fractional 0–1 programming problems (also, often referred to as hyperbolic 0–1 programming problems), where the objective is to optimize the sum of ratios of affine functions subject to a set of linear constraints. Such problems arise in diverse applications across different fields, and have been the subject of study in a number of papers during the past few decades. In this survey we overview the literature on fractional 0–1 programs including their applications, related computational complexity issues and solution methods including exact, approximation and heuristic algorithms.

Suggested Citation

  • Juan S. Borrero & Colin Gillen & Oleg A. Prokopyev, 2017. "Fractional 0–1 programming: applications and algorithms," Journal of Global Optimization, Springer, vol. 69(1), pages 255-282, September.
    • Handle: RePEc:spr:jglopt:v:69:y:2017:i:1:d:10.1007_s10898-016-0487-4
    DOI: 10.1007/s10898-016-0487-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-016-0487-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-016-0487-4?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Samyukta Sethuraman & Sergiy Butenko, 2015. "The maximum ratio clique problem," Computational Management Science, Springer, vol. 12(1), pages 197-218, January.
    2. Zied Jemai & Adel Elomri & Asma Ghaffari & Yves Dallery, 2012. "Coalition Formation and Cost Allocation for Joint Replenishment Systems," Post-Print hal-01672397, HAL.
    3. Fred Glover & Eugene Woolsey, 1974. "Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program," Operations Research, INFORMS, vol. 22(1), pages 180-182, February.
    4. Warren P. Adams & Stephen M. Henry, 2012. "Base-2 Expansions for Linearizing Products of Functions of Discrete Variables," Operations Research, INFORMS, vol. 60(6), pages 1477-1490, December.
    5. Andrew C. Trapp & Renata A. Konrad, 2015. "Finding diverse optima and near-optima to binary integer programs," IISE Transactions, Taylor & Francis Journals, vol. 47(11), pages 1300-1312, November.
    6. Andrew Trapp & Oleg A. Prokopyev & Stanislav Busygin, 2010. "Finding checkerboard patterns via fractional 0–1 programming," Journal of Combinatorial Optimization, Springer, vol. 20(1), pages 1-26, July.
    7. A. Charnes & W. W. Cooper, 1963. "Programming with linear fractional functionals," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 10(1), pages 273-274, March.
    8. Lawrence J. Watters, 1967. "Letter to the Editor—Reduction of Integer Polynomial Programming Problems to Zero-One Linear Programming Problems," Operations Research, INFORMS, vol. 15(6), pages 1171-1174, December.
    9. Edoardo Amaldi & Sandro Bosio & Federico Malucelli & Di Yuan, 2011. "Solving Nonlinear Covering Problems Arising in WLAN Design," Operations Research, INFORMS, vol. 59(1), pages 173-187, February.
    10. Chang, Ching-Ter, 2001. "On the polynomial mixed 0-1 fractional programming problems," European Journal of Operational Research, Elsevier, vol. 131(1), pages 224-227, May.
    11. Juan José Miranda Bront & Isabel Méndez-Díaz & Gustavo Vulcano, 2009. "A Column Generation Algorithm for Choice-Based Network Revenue Management," Operations Research, INFORMS, vol. 57(3), pages 769-784, June.
    12. Amiri, Ali & Rolland, Erik & Barkhi, Reza, 1999. "Bandwidth packing with queuing delay costs: Bounding and heuristic solution procedures," European Journal of Operational Research, Elsevier, vol. 112(3), pages 635-645, February.
    13. Prokopyev, Oleg A. & Kong, Nan & Martinez-Torres, Dayna L., 2009. "The equitable dispersion problem," European Journal of Operational Research, Elsevier, vol. 197(1), pages 59-67, August.
    14. Fred Glover, 1975. "Improved Linear Integer Programming Formulations of Nonlinear Integer Problems," Management Science, INFORMS, vol. 22(4), pages 455-460, December.
    15. Wu, Tai-Hsi, 1997. "A note on a global approach for general 0-1 fractional programming," European Journal of Operational Research, Elsevier, vol. 101(1), pages 220-223, August.
    16. John D. C. Little, 1961. "A Proof for the Queuing Formula: L = (lambda) W," Operations Research, INFORMS, vol. 9(3), pages 383-387, June.
    17. Warren P. Adams & Hanif D. Sherali, 1986. "A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems," Management Science, INFORMS, vol. 32(10), pages 1274-1290, October.
    18. Gary Kochenberger & Jin-Kao Hao & Fred Glover & Mark Lewis & Zhipeng Lü & Haibo Wang & Yang Wang, 2014. "The unconstrained binary quadratic programming problem: a survey," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 58-81, July.
    19. Li, Han-Lin, 1994. "A global approach for general 0-1 fractional programming," European Journal of Operational Research, Elsevier, vol. 73(3), pages 590-596, March.
    20. Shivaram Subramanian & Hanif Sherali, 2010. "A fractional programming approach for retail category price optimization," Journal of Global Optimization, Springer, vol. 48(2), pages 263-277, October.
    21. James M. Davis & Guillermo Gallego & Huseyin Topaloglu, 2014. "Assortment Optimization Under Variants of the Nested Logit Model," Operations Research, INFORMS, vol. 62(2), pages 250-273, April.
    22. Siegfried Schaible, 1976. "Fractional Programming. II, On Dinkelbach's Algorithm," Management Science, INFORMS, vol. 22(8), pages 868-873, April.
    23. Gabriel R. Bitran & Thomas L. Magnanti, 1976. "Duality and Sensitivity Analysis for Fractional Programs," Operations Research, INFORMS, vol. 24(4), pages 675-699, August.
    24. Bennett Fox, 1969. "Letter to the Editor—Finding Minimal Cost-Time Ratio Circuits," Operations Research, INFORMS, vol. 17(3), pages 546-551, June.
    25. Mary W. Cooper, 1981. "A Survey of Methods for Pure Nonlinear Integer Programming," Management Science, INFORMS, vol. 27(3), pages 353-361, March.
    26. Jinil Han & Kyungsik Lee & Chungmok Lee & Sungsoo Park, 2013. "Exact Algorithms for a Bandwidth Packing Problem with Queueing Delay Guarantees," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 585-596, August.
    27. Oleksii Ursulenko & Sergiy Butenko & Oleg Prokopyev, 2013. "A global optimization algorithm for solving the minimum multiple ratio spanning tree problem," Journal of Global Optimization, Springer, vol. 56(3), pages 1029-1043, July.
    28. Stanislav Busygin & Oleg A. Prokopyev & Panos M. Pardalos, 2005. "Feature Selection for Consistent Biclustering via Fractional 0–1 Programming," Journal of Combinatorial Optimization, Springer, vol. 10(1), pages 7-21, August.
    29. Y. Almogy & O. Levin, 1971. "A Class of Fractional Programming Problems," Operations Research, INFORMS, vol. 19(1), pages 57-67, February.
    30. P. C. Gilmore & R. E. Gomory, 1963. "A Linear Programming Approach to the Cutting Stock Problem---Part II," Operations Research, INFORMS, vol. 11(6), pages 863-888, December.
    31. Nimrod Megiddo, 1979. "Combinatorial Optimization with Rational Objective Functions," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 414-424, November.
    32. Werner Dinkelbach, 1967. "On Nonlinear Fractional Programming," Management Science, INFORMS, vol. 13(7), pages 492-498, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Larsson, Torbjörn & Quttineh, Nils-Hassan, 2023. "One-parametric analysis of column-oriented linear programs," Operations Research Perspectives, Elsevier, vol. 10(C).
    2. Jose Joaquin del Pozo-Antúnez & Francisco Fernández-Navarro & Horacio Molina-Sánchez & Antonio Ariza-Montes & Mariano Carbonero-Ruz, 2021. "The Machine-Part Cell Formation Problem with Non-Binary Values: A MILP Model and a Case of Study in the Accounting Profession," Mathematics, MDPI, vol. 9(15), pages 1-16, July.
    3. Weerasena, Lakmali & Shier, Douglas & Tonkyn, David & McFeaters, Mark & Collins, Christopher, 2023. "A sequential approach to reserve design with compactness and contiguity considerations," Ecological Modelling, Elsevier, vol. 478(C).
    4. Andrés Gómez & Oleg A. Prokopyev, 2021. "A Mixed-Integer Fractional Optimization Approach to Best Subset Selection," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 551-565, May.
    5. Gerelt Tserenjigmid, 2021. "The Order-Dependent Luce Model," Management Science, INFORMS, vol. 67(11), pages 6915-6933, November.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Erfan Mehmanchi & Andrés Gómez & Oleg A. Prokopyev, 2019. "Fractional 0–1 programs: links between mixed-integer linear and conic quadratic formulations," Journal of Global Optimization, Springer, vol. 75(2), pages 273-339, October.
    2. M. Hosein Zare & Juan S. Borrero & Bo Zeng & Oleg A. Prokopyev, 2019. "A note on linearized reformulations for a class of bilevel linear integer problems," Annals of Operations Research, Springer, vol. 272(1), pages 99-117, January.
    3. Samyukta Sethuraman & Sergiy Butenko, 2015. "The maximum ratio clique problem," Computational Management Science, Springer, vol. 12(1), pages 197-218, January.
    4. Warren Adams & Hanif Sherali, 2005. "A Hierarchy of Relaxations Leading to the Convex Hull Representation for General Discrete Optimization Problems," Annals of Operations Research, Springer, vol. 140(1), pages 21-47, November.
    5. Shaoning Han & Andrés Gómez & Oleg A. Prokopyev, 2022. "Fractional 0–1 programming and submodularity," Journal of Global Optimization, Springer, vol. 84(1), pages 77-93, September.
    6. Alper Atamtürk & Andrés Gómez, 2020. "Submodularity in Conic Quadratic Mixed 0–1 Optimization," Operations Research, INFORMS, vol. 68(2), pages 609-630, March.
    7. Strauss, Arne K. & Klein, Robert & Steinhardt, Claudius, 2018. "A review of choice-based revenue management: Theory and methods," European Journal of Operational Research, Elsevier, vol. 271(2), pages 375-387.
    8. Tien Mai & Arunesh Sinha, 2022. "Safe Delivery of Critical Services in Areas with Volatile Security Situation via a Stackelberg Game Approach," Papers 2204.11451, arXiv.org.
    9. Laurent Alfandari & Alborz Hassanzadeh & Ivana Ljubić, 2021. "An Exact Method for Assortment Optimization under the Nested Logit Model," Working Papers hal-02463159, HAL.
    10. Andrés Gómez & Oleg A. Prokopyev, 2021. "A Mixed-Integer Fractional Optimization Approach to Best Subset Selection," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 551-565, May.
    11. Billionnet, Alain, 2004. "Mixed integer programming for the 0-1 maximum probability model," European Journal of Operational Research, Elsevier, vol. 156(1), pages 83-91, July.
    12. Sven Mallach, 2018. "Compact linearization for binary quadratic problems subject to assignment constraints," 4OR, Springer, vol. 16(3), pages 295-309, September.
    13. S. Morteza Mirdehghan & Hassan Rostamzadeh, 2016. "Finding the Efficiency Status and Efficient Projection in Multiobjective Linear Fractional Programming: A Linear Programming Technique," Journal of Optimization, Hindawi, vol. 2016, pages 1-8, September.
    14. Alfandari, Laurent & Hassanzadeh, Alborz & Ljubic, Ivana, 2020. "An Exact Method for Assortment Optimization under the Nested Logit Model," ESSEC Working Papers WP2001, ESSEC Research Center, ESSEC Business School, revised 2020.
    15. Chang, Ching-Ter, 2002. "On the posynomial fractional programming problems," European Journal of Operational Research, Elsevier, vol. 143(1), pages 42-52, November.
    16. Erfan Mehmanchi & Andrés Gómez & Oleg A. Prokopyev, 2021. "Solving a class of feature selection problems via fractional 0–1 programming," Annals of Operations Research, Springer, vol. 303(1), pages 265-295, August.
    17. Li, Yifu & Qi, Xiangtong, 2022. "A geometric branch-and-bound algorithm for the service bundle design problem," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1044-1056.
    18. Chang, Ching-Ter, 2006. "Formulating the mixed integer fractional posynomial programming," European Journal of Operational Research, Elsevier, vol. 173(2), pages 370-386, September.
    19. Buchheim, Christoph & Crama, Yves & Rodríguez-Heck, Elisabeth, 2019. "Berge-acyclic multilinear 0–1 optimization problems," European Journal of Operational Research, Elsevier, vol. 273(1), pages 102-107.
    20. Flores, Alvaro & Berbeglia, Gerardo & Van Hentenryck, Pascal, 2019. "Assortment optimization under the Sequential Multinomial Logit Model," European Journal of Operational Research, Elsevier, vol. 273(3), pages 1052-1064.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:69:y:2017:i:1:d:10.1007_s10898-016-0487-4. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.