IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v45y1999i11p1539-1551.html
   My bibliography  Save this article

The Data-Correcting Algorithm for the Minimization of Supermodular Functions

Author

Listed:
  • Boris Goldengorin

    (Department of Econometrics and Operations Research, University of Groningen, P.O. Box 800, 9700 AV Groningen, The Netherlands)

  • Gerard Sierksma

    (Department of Econometrics and Operations Research, University of Groningen, P.O. Box 800, 9700 AV Groningen, The Netherlands)

  • Gert A. Tijssen

    (Department of Econometrics and Operations Research, University of Groningen, P.O. Box 800, 9700 AV Groningen, The Netherlands)

  • Michael Tso

    (Department of Mathematics, University of Manchester, Institute of Science and Technology, UMIST, Manchester, United Kingdom)

Abstract

The Data-Correcting (DC) Algorithm is a recursive branch-and-bound type algorithm, in which the data of a given problem instance are "heuristically corrected" at each branching in such a way that the new instance will be as close as possible to polynomially solvable and the result satisfies a prescribed accuracy (the difference between optimal and current solution). In this paper the DC algorithm is applied to determining exact or approximate global minima of supermodular functions. The working of the algorithm is illustrated by an instance of the Simple Plant Location (SPL) Problem. Computational results, obtained for the Quadratic Cost Partition Problem (QCP), show that the DC algorithm outperforms a branch-and-cut algorithm, not only for sparse graphs but also for nonsparse graphs (with density more than 40%), often with speeds 100 times faster.

Suggested Citation

  • Boris Goldengorin & Gerard Sierksma & Gert A. Tijssen & Michael Tso, 1999. "The Data-Correcting Algorithm for the Minimization of Supermodular Functions," Management Science, INFORMS, vol. 45(11), pages 1539-1551, November.
    • Handle: RePEc:inm:ormnsc:v:45:y:1999:i:11:p:1539-1551
    DOI: 10.1287/mnsc.45.11.1539
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.45.11.1539
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.45.11.1539?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
    ---><---

    References listed on IDEAS

    as
    1. Chun-Wa Ko & Jon Lee & Maurice Queyranne, 1995. "An Exact Algorithm for Maximum Entropy Sampling," Operations Research, INFORMS, vol. 43(4), pages 684-691, August.
    2. Francisco Barahona & Martin Grötschel & Michael Jünger & Gerhard Reinelt, 1988. "An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design," Operations Research, INFORMS, vol. 36(3), pages 493-513, June.
    3. Beasley, J. E., 1993. "Lagrangean heuristics for location problems," European Journal of Operational Research, Elsevier, vol. 65(3), pages 383-399, March.
    4. Fisher, M.L. & Nemhauser, G.L. & Wolsey, L.A., 1978. "An analysis of approximations for maximizing submodular set functions," LIDAM Reprints CORE 341, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Jon Lee, 1998. "Constrained Maximum-Entropy Sampling," Operations Research, INFORMS, vol. 46(5), pages 655-664, October.
    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. repec:dgr:rugsom:00a54 is not listed on IDEAS
    2. Zhicheng Liu & Longkun Guo & Donglei Du & Dachuan Xu & Xiaoyan Zhang, 2022. "Maximization problems of balancing submodular relevance and supermodular diversity," Journal of Global Optimization, Springer, vol. 82(1), pages 179-194, January.
    3. Goldengorin, Boris, 2009. "Maximization of submodular functions: Theory and enumeration algorithms," European Journal of Operational Research, Elsevier, vol. 198(1), pages 102-112, October.
    4. Ghosh, Diptesh & Sierksma, Gerard & Goldengorin, Boris & AlMohammad, Bader F., 2000. "Equivalent instances of the simple plant location problem," Research Report 00A54, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    5. repec:dgr:rugsom:99a17 is not listed on IDEAS
    6. Cui, Tingting & Ouyang, Yanfeng & Shen, Zuo-Jun Max J, 2010. "Reliable Facility Location Design under the Risk of Disruptions," University of California Transportation Center, Working Papers qt5sh2c7pw, University of California Transportation Center.
    7. Goldengorin, Boris & Tijssen, Gert A. & Tso, Michael, 1999. "The maximization of submodular functions : old and new proofs for the correctness of the dichotomy algorithm," Research Report 99A17, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    8. Goldengorin, Boris, 2001. "Solving the simple plant location problem using a data correcting approach," Research Report 01A53, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    9. Tingting Cui & Yanfeng Ouyang & Zuo-Jun Max Shen, 2010. "Reliable Facility Location Design Under the Risk of Disruptions," Operations Research, INFORMS, vol. 58(4-part-1), pages 998-1011, August.
    10. Yu, Guodong & Haskell, William B. & Liu, Yang, 2017. "Resilient facility location against the risk of disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 82-105.
    11. Zsolt Sándor & Michel Wedel, 2002. "Profile Construction in Experimental Choice Designs for Mixed Logit Models," Marketing Science, INFORMS, vol. 21(4), pages 455-475, February.
    12. repec:dgr:rugsom:01a14 is not listed on IDEAS
    13. Goldengorin, Boris & Ghosh, Diptesh, 2004. "A Multilevel Search Algorithm for the Maximization of Submodular Functions," Research Report 04A20, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    14. Goldengorin, Boris & Vink, Marius de, 1999. "Solving large instances of the quadratic cost of partition problem on dense graphs by data correcting algorithms," Research Report 99A50, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    15. Barros, Lilian & Riley, Michael, 2001. "A combinatorial approach to level of repair analysis," European Journal of Operational Research, Elsevier, vol. 129(2), pages 242-251, March.
    16. Goldengorin, Boris & Ghosh, Diptesh & Sierksma, Gerard, 2001. "Branch and peg algorithms for the simple plant location problem," Research Report 01A14, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    17. repec:dgr:rugsom:99a50 is not listed on IDEAS
    18. Jing-Sheng Song & Yue Zhang, 2020. "Stock or Print? Impact of 3-D Printing on Spare Parts Logistics," Management Science, INFORMS, vol. 66(9), pages 3860-3878, September.
    19. Vincent Tulasi & Isaac Kwasi Adu & Elikem Kofi Krampa, 2016. "Location of Farmers Warehouse at Adaklu Traditional Area, Volta Region, Ghana," Journal of Optimization, Hindawi, vol. 2016, pages 1-10, July.
    20. repec:dgr:rugsom:01a53 is not listed on IDEAS
    21. repec:dgr:rugsom:04a20 is not listed on IDEAS

    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. Goldengorin, Boris, 2009. "Maximization of submodular functions: Theory and enumeration algorithms," European Journal of Operational Research, Elsevier, vol. 198(1), pages 102-112, October.
    2. repec:dgr:rugsom:99a17 is not listed on IDEAS
    3. Goldengorin, Boris & Tijssen, Gert A. & Tso, Michael, 1999. "The maximization of submodular functions : old and new proofs for the correctness of the dichotomy algorithm," Research Report 99A17, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    4. Goldengorin, Boris & Sierksma, Gerard & Tijssen, Gert A., 1998. "The data-correcting algorithm for supermodular functions, with applications to quadratic cost partition and simple plant location problems," Research Report 98A08, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    5. repec:dgr:rugsom:98a08 is not listed on IDEAS
    6. Hessa Al-Thani & Jon Lee, 2020. "An R Package for Generating Covariance Matrices for Maximum-Entropy Sampling from Precipitation Chemistry Data," SN Operations Research Forum, Springer, vol. 1(3), pages 1-21, September.
    7. Goldengorin, Boris & Ghosh, Diptesh, 2004. "A Multilevel Search Algorithm for the Maximization of Submodular Functions," Research Report 04A20, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    8. Kurt M. Anstreicher, 2020. "Efficient Solution of Maximum-Entropy Sampling Problems," Operations Research, INFORMS, vol. 68(6), pages 1826-1835, November.
    9. Kurt M. Anstreicher, 2018. "Maximum-entropy sampling and the Boolean quadric polytope," Journal of Global Optimization, Springer, vol. 72(4), pages 603-618, December.
    10. Zhongzhu Chen & Marcia Fampa & Jon Lee, 2023. "On Computing with Some Convex Relaxations for the Maximum-Entropy Sampling Problem," INFORMS Journal on Computing, INFORMS, vol. 35(2), pages 368-385, March.
    11. HOFFMAN, Alan & LEE, Jon & WILLIAMS, Joy, 2000. "New upper bounds for maximum-entropy sampling," LIDAM Discussion Papers CORE 2000012, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. repec:dgr:rugsom:04a20 is not listed on IDEAS
    13. Fuda Ma & Jin-Kao Hao, 2017. "A multiple search operator heuristic for the max-k-cut problem," Annals of Operations Research, Springer, vol. 248(1), pages 365-403, January.
    14. Dell'Amico, Mauro & Trubian, Marco, 1998. "Solution of large weighted equicut problems," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 500-521, April.
    15. Zeinal Hamadani, Ali & Abouei Ardakan, Mostafa & Rezvan, Taghi & Honarmandian, Mohammad Mehran, 2013. "Location-allocation problem for intra-transportation system in a big company by using meta-heuristic algorithm," Socio-Economic Planning Sciences, Elsevier, vol. 47(4), pages 309-317.
    16. Mohit Singh & Weijun Xie, 2020. "Approximation Algorithms for D -optimal Design," Mathematics of Operations Research, INFORMS, vol. 45(4), pages 1512-1534, November.
    17. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2018. "Multi-level facility location problems," European Journal of Operational Research, Elsevier, vol. 267(3), pages 791-805.
    18. Dam, Tien Thanh & Ta, Thuy Anh & Mai, Tien, 2022. "Submodularity and local search approaches for maximum capture problems under generalized extreme value models," European Journal of Operational Research, Elsevier, vol. 300(3), pages 953-965.
    19. Grolimund, Stephan & Ganascia, Jean-Gabriel, 1997. "Driving Tabu Search with case-based reasoning," European Journal of Operational Research, Elsevier, vol. 103(2), pages 326-338, December.
    20. Klaus Büdenbender & Tore Grünert & Hans-Jürgen Sebastian, 2000. "A Hybrid Tabu Search/Branch-and-Bound Algorithm for the Direct Flight Network Design Problem," Transportation Science, INFORMS, vol. 34(4), pages 364-380, November.
    21. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    22. Majun Shi & Zishen Yang & Wei Wang, 2023. "Greedy Guarantees for Non-submodular Function Maximization Under Independent System Constraint with Applications," Journal of Optimization Theory and Applications, Springer, vol. 196(2), pages 516-543, February.
    23. Goldengorin, Boris, 2001. "Solving the simple plant location problem using a data correcting approach," Research Report 01A53, University of Groningen, Research Institute SOM (Systems, Organisations and Management).

    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:inm:ormnsc:v:45:y:1999:i:11:p:1539-1551. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.