IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v52y2004i6p942-953.html
   My bibliography  Save this article

Cutting Planes for Low-Rank-Like Concave Minimization Problems

Author

Listed:
  • Marcus Porembski

    (Department of Mathematics, University of Marburg, 35032 Marburg, Germany)

Abstract

Concavity cuts play an important role in several algorithms for concave minimization, such as pure cutting plane algorithms, conical algorithms, and branch-and-bound algorithms. For concave quadratic minimization problems Konno et al. (1998) have demonstrated that the lower the rank of the problem, i.e., the smaller the number of nonlinear variables, the deeper the concavity cuts usually turn out to be. In this paper we examine the case where the number of nonlinear variables of a concave minimization problem is large, but most of the objective value of a good solution is determined by a small number of variables only. We will discuss ways to exploit such a situation to derive deep cutting planes. To this end we apply concepts usually applied for efficiently solving low-rank concave minimization problems.

Suggested Citation

  • Marcus Porembski, 2004. "Cutting Planes for Low-Rank-Like Concave Minimization Problems," Operations Research, INFORMS, vol. 52(6), pages 942-953, December.
    • Handle: RePEc:inm:oropre:v:52:y:2004:i:6:p:942-953
    DOI: 10.1287/opre.1040.0151
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1040.0151
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1040.0151?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, 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. 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.
    3. J. B. Rosen, 1983. "Global Minimization of a Linearly Constrained Concave Function by Partition of Feasible Domain," Mathematics of Operations Research, INFORMS, vol. 8(2), pages 215-230, May.
    4. 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.
    5. H. P. Benson, 1999. "Generalized γ-Valid Cut Procedure for Concave Minimization," Journal of Optimization Theory and Applications, Springer, vol. 102(2), pages 289-298, August.
    Full references (including those not matched with items 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. Marcus Porembski, 2008. "On the hierarchy of γ‐valid cuts in global optimization," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(1), pages 1-15, February.
    2. Amanda O. C. Ayres & Betania S. C. Campello & Washington A. Oliveira & Carla T. L. S. Ghidini, 2021. "A Bi-Integrated Model for coupling lot-sizing and cutting-stock problems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(4), pages 1047-1076, December.
    3. 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.
    4. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    5. Arbib, Claudio & Marinelli, Fabrizio, 2005. "Integrating process optimization and inventory planning in cutting-stock with skiving option: An optimization model and its application," European Journal of Operational Research, Elsevier, vol. 163(3), pages 617-630, June.
    6. K. Moshirvaziri, 1998. "Construction of Test Problems for Concave Minimization Under Linear and Nonlinear Constraints," Journal of Optimization Theory and Applications, Springer, vol. 98(1), pages 83-108, July.
    7. Anselmo Ramalho Pitombeira-Neto & Bruno de Athayde Prata, 2020. "A matheuristic algorithm for the one-dimensional cutting stock and scheduling problem with heterogeneous orders," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(1), pages 178-192, April.
    8. Kennedy A. G. Araújo & Tibérius O. Bonates & Bruno A. Prata & Anselmo R. Pitombeira-Neto, 2021. "Heterogeneous prestressed precast beams multiperiod production planning problem: modeling and solution methods," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(3), pages 660-693, October.
    9. Darinka Dentcheva & Eli Wolfhagen, 2016. "Two-Stage Optimization Problems with Multivariate Stochastic Order Constraints," Mathematics of Operations Research, INFORMS, vol. 41(1), pages 1-22, February.
    10. Oliveira, Washington A. & Fiorotto, Diego J. & Song, Xiang & Jones, Dylan F., 2021. "An extended goal programming model for the multiobjective integrated lot-sizing and cutting stock problem," European Journal of Operational Research, Elsevier, vol. 295(3), pages 996-1007.
    11. Tao Wu & Kerem Akartunal? & Raf Jans & Zhe Liang, 2017. "Progressive Selection Method for the Coupled Lot-Sizing and Cutting-Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 523-543, August.
    12. 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.
    13. Gramani, Maria Cristina N. & Franca, Paulo M., 2006. "The combined cutting stock and lot-sizing problem in industrial processes," European Journal of Operational Research, Elsevier, vol. 174(1), pages 509-521, October.
    14. Song, X. & Chu, C.B. & Nie, Y.Y. & Bennell, J.A., 2006. "An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1870-1889, December.
    15. 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.
    16. Bennell, Julia A. & Soon Lee, Lai & Potts, Chris N., 2013. "A genetic algorithm for two-dimensional bin packing with due dates," International Journal of Production Economics, Elsevier, vol. 145(2), pages 547-560.
    17. Gramani, Maria Cristina N. & França, Paulo M. & Arenales, Marcos N., 2011. "An Exact Approach to the Relaxed Combined Production Planning Model," Insper Working Papers wpe_178, Insper Working Paper, Insper Instituto de Ensino e Pesquisa.
    18. Sônia Poltroniere & Kelly Poldi & Franklina Toledo & Marcos Arenales, 2008. "A coupling cutting stock-lot sizing problem in the paper industry," Annals of Operations Research, Springer, vol. 157(1), pages 91-104, January.
    19. Duan Li & Xiaoling Sun & Ken McKinnon, 2005. "An Exact Solution Method for Reliability Optimization in Complex Systems," Annals of Operations Research, Springer, vol. 133(1), pages 129-148, January.
    20. 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.

    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:oropre:v:52:y:2004:i:6:p:942-953. 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.