IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v37y1990i4p515-525.html
   My bibliography  Save this article

An algorithm for concave integer minimization over a polyhedron

Author

Listed:
  • Harold P. Benson
  • S. Selcuk Erenguc

Abstract

We present an algorithm for solving the problem of globally minimizing a concave function over the integers contained in a compact polyhedron. The objective function of this problem need not be separable or even analytically defined. To our knowledge, the algorithm is the first ever proposed for this problem. Among the major advantages of the algorithm are that no nonlinear computations or optimizations are required, and that it allows one to exploit the polyhedral nature of X. We discuss these and other advantages and disadvantages of the algorithm, and we present some preliminary computational experience using our computer code for the algorithm. This computational experience seems to indicate that the algorithm is quite practical for solving many concave integer minimization problems over compact polyhedra.

Suggested Citation

  • Harold P. Benson & S. Selcuk Erenguc, 1990. "An algorithm for concave integer minimization over a polyhedron," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(4), pages 515-525, August.
    • Handle: RePEc:wly:navres:v:37:y:1990:i:4:p:515-525
    DOI: 10.1002/1520-6750(199008)37:43.0.CO;2-X
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(199008)37:43.0.CO;2-X
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(199008)37:43.0.CO;2-X?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. James E. Falk & Karla R. Hoffman, 1976. "A Successive Underestimation Method for Concave Minimization Problems," Mathematics of Operations Research, INFORMS, vol. 1(3), pages 251-259, August.
    2. H. Tuy & T. V. Thieu & Ng. Q. Thai, 1985. "A Conical Algorithm for Globally Minimizing a Concave Function Over a Closed Convex Set," Mathematics of Operations Research, INFORMS, vol. 10(3), pages 498-514, August.
    3. S. Selcuk Erenguc & Harold P. Benson, 1986. "The interactive fixed charge linear programming problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 33(2), pages 157-177, May.
    4. Harold P. Benson, 1985. "A finite algorithm for concave minimization over a polyhedron," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 32(1), pages 165-177, February.
    5. James E. Falk & Richard M. Soland, 1969. "An Algorithm for Separable Nonconvex Programming Problems," Management Science, INFORMS, vol. 15(9), pages 550-569, May.
    6. Richard M. Soland, 1974. "Optimal Facility Location with Concave Costs," Operations Research, INFORMS, vol. 22(2), pages 373-382, April.
    7. Claude Dennis Pegden & Clifford C. Petersen, 1979. "An algorithm (GIPC2) for solving integer programming problems with separable nonlinear objective functions," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 26(4), pages 595-609, December.
    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. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2021. "A General Purpose Exact Solution Method for Mixed Integer Concave Minimization Problems," IIMA Working Papers WP 2021-03-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    2. Kurt M. Bretthauer & A. Victor Cabot & M. A. Venkataramanan, 1994. "An algorithm and new penalties for concave integer minimization over a polyhedron," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(3), pages 435-454, April.
    3. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2023. "A general purpose exact solution method for mixed integer concave minimization problems," European Journal of Operational Research, Elsevier, vol. 309(3), pages 977-992.
    4. Kurt M. Bretthauer, 1994. "A penalty for concave minimization derived from the tuy cutting plane," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(3), pages 455-463, April.
    5. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2021. "A General Purpose Exact Solution Method for Mixed Integer Concave Minimization Problems (revised as on 12/08/2021)," IIMA Working Papers WP 2021-03-01, Indian Institute of Management Ahmedabad, Research and Publication Department.

    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. Harold P. Benson, 1996. "Deterministic algorithms for constrained concave minimization: A unified critical survey," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(6), pages 765-795, September.
    2. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2023. "A general purpose exact solution method for mixed integer concave minimization problems," European Journal of Operational Research, Elsevier, vol. 309(3), pages 977-992.
    3. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2021. "A General Purpose Exact Solution Method for Mixed Integer Concave Minimization Problems," IIMA Working Papers WP 2021-03-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    4. Reiner Horst, 1990. "Deterministic methods in constrained global optimization: Some recent advances and new fields of application," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(4), pages 433-471, August.
    5. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2021. "A General Purpose Exact Solution Method for Mixed Integer Concave Minimization Problems (revised as on 12/08/2021)," IIMA Working Papers WP 2021-03-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    6. Harold P. Benson, 2004. "Concave envelopes of monomial functions over rectangles," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(4), pages 467-476, June.
    7. Kurt M. Bretthauer & A. Victor Cabot & M. A. Venkataramanan, 1994. "An algorithm and new penalties for concave integer minimization over a polyhedron," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(3), pages 435-454, April.
    8. Wooseung Jang & J. George Shanthikumar, 2002. "Stochastic allocation of inspection capacity to competitive processes," Naval Research Logistics (NRL), John Wiley & Sons, vol. 49(1), pages 78-94, February.
    9. Takahito Kuno, 2022. "A revision of the rectangular algorithm for a class of DC optimization problems," Journal of Global Optimization, Springer, vol. 83(2), pages 187-200, June.
    10. Vedat Verter & M. Cemal Dincer, 1995. "Facility location and capacity acquisition: An integrated approach," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(8), pages 1141-1160, December.
    11. M. Vanhoucke, 2002. "Optimal Due Date Assignment In Project Scheduling," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 02/159, Ghent University, Faculty of Economics and Business Administration.
    12. Nonas, Sigrid Lise & Thorstenson, Anders, 2000. "A combined cutting-stock and lot-sizing problem," European Journal of Operational Research, Elsevier, vol. 120(2), pages 327-342, January.
    13. S. Selcuk Erenguc, 1988. "Multiproduct dynamic lot‐sizing model with coordinated replenishments," Naval Research Logistics (NRL), John Wiley & Sons, vol. 35(1), pages 1-22, February.
    14. Benson, Harold P., 2006. "Fractional programming with convex quadratic forms and functions," European Journal of Operational Research, Elsevier, vol. 173(2), pages 351-369, September.
    15. Vanhoucke, Mario & Demeulemeester, Erik & Herroelen, Willy, 2003. "Progress payments in project scheduling problems," European Journal of Operational Research, Elsevier, vol. 148(3), pages 604-620, August.
    16. Yong Xia & Longfei Wang & Meijia Yang, 2019. "A fast algorithm for globally solving Tikhonov regularized total least squares problem," Journal of Global Optimization, Springer, vol. 73(2), pages 311-330, February.
    17. Jungho Park & Hadi El-Amine & Nevin Mutlu, 2021. "An Exact Algorithm for Large-Scale Continuous Nonlinear Resource Allocation Problems with Minimax Regret Objectives," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1213-1228, July.
    18. Ankhili, Z. & Mansouri, A., 2009. "An exact penalty on bilevel programs with linear vector optimization lower level," European Journal of Operational Research, Elsevier, vol. 197(1), pages 36-41, August.
    19. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    20. Frank Karsten & Marco Slikker & Peter Borm, 2017. "Cost allocation rules for elastic single‐attribute situations," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(4), pages 271-286, June.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:37:y:1990:i:4:p:515-525. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.