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. 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.
    2. 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.
    3. James E. Falk & Richard M. Soland, 1969. "An Algorithm for Separable Nonconvex Programming Problems," Management Science, INFORMS, vol. 15(9), pages 550-569, May.
    4. 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.
    5. Richard M. Soland, 1974. "Optimal Facility Location with Concave Costs," Operations Research, INFORMS, vol. 22(2), pages 373-382, April.
    6. 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.
    7. 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.
    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. 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. 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.
    4. 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.
    5. 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.

    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. 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.
    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. 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.
    5. 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.
    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. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    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. Torki, Abdolhamid & Yajima, Yatsutoshi & Enkawa, Takao, 1996. "A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 94(2), pages 384-391, October.
    17. 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.
    18. Walter Briec & Laurent Cavaignac & Kristiaan Kerstens, 2020. "Input Efficiency Measures: A Generalized, Encompassing Formulation," Operations Research, INFORMS, vol. 68(6), pages 1836-1849, November.
    19. 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.
    20. H.A. Le Thi & T. Pham Dinh & L.D. Muu, 2003. "Simplicially-Constrained DC Optimization over Efficient and Weakly Efficient Sets," Journal of Optimization Theory and Applications, Springer, vol. 117(3), pages 503-531, 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.