IDEAS home Printed from https://ideas.repec.org/p/mns/wpaper/wp201213.html
   My bibliography  Save this paper

Continuous Piecewise Linear δ-Approximations for MINLP Problems. II. Bivariate and Multivariate Functions

Author

Listed:
  • Steffen Rebennack

    (Division of Economics and Business, Colorado School of Mines)

  • Josef Kallrath

    (Department of Astronomy, University of Florida)

Abstract

Following up on Rebennack and Kallrath (2012), in this paper, for functions depending on two variables, using refinement heuristics, we automatically construct triangulations subject to the condition that the continuous, piecewise linear approximation, under- or overestimation never deviates more than a given δ-tolerance from the original function over a given domain. This tolerance is proven by solving subproblems over each triangle to global optimality. The continuous, piecewise linear approximators, under- and overestimators involve shift variables at the vertices of the triangles leading to a small number of triangles while still ensuring continuity over the full domain. On a set of test functions, we demonstrate the numerical behavior of our approach. For functions depending on more than two variables we provide appropriate transformations and substitutions which allow to use one- or two-dimensional δ-approximators. We address the problem of error propagation when using these dimensionality reduction routines. The automatic refinement triangulation provides an alternative to separation or transformation techniques applied to bivariate functions followed by one-dimensional piecewise linear approximation. We discuss and analyze the tradeoff between one-dimensional and two-dimensional approaches. To demonstrate the methodology we apply it to a cutting stock problem in which we compute minimal area rectangles hosting a given number of circles; we prove optimality for one literature problem which so far had been solved only with finite gap.

Suggested Citation

  • Steffen Rebennack & Josef Kallrath, 2012. "Continuous Piecewise Linear δ-Approximations for MINLP Problems. II. Bivariate and Multivariate Functions," Working Papers 2012-13, Colorado School of Mines, Division of Economics and Business.
  • Handle: RePEc:mns:wpaper:wp201213
    as

    Download full text from publisher

    File URL: http://econbus-papers.mines.edu/working-papers/wp201213.pdf
    File Function: First version, 2012
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. R. Misener & C. A. Floudas, 2010. "Piecewise-Linear Approximations of Multidimensional Functions," Journal of Optimization Theory and Applications, Springer, vol. 145(1), pages 120-147, April.
    2. Josef Kallrath, 2005. "Solving Planning and Design Problems in the Process Industry Using Mixed Integer and Global Optimization," Annals of Operations Research, Springer, vol. 140(1), pages 339-373, November.
    3. Timpe, Christian H. & Kallrath, Josef, 2000. "Optimal planning in large multi-site production networks," European Journal of Operational Research, Elsevier, vol. 126(2), pages 422-435, October.
    4. Steffen Rebennack & Josef Kallrath, 2012. "Continuous Piecewise Linear δ-Approximations for MINLP Problems. I. Minimal Breakpoint Systems for Univariate Functions," Working Papers 2012-12, Colorado School of Mines, Division of Economics and Business.
    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. Josef Kallrath & Steffen Rebennack, 2014. "Cutting ellipses from area-minimizing rectangles," Journal of Global Optimization, Springer, vol. 59(2), pages 405-437, July.
    2. Steffen Rebennack & Josef Kallrath, 2012. "Continuous Piecewise Linear δ-Approximations for MINLP Problems. I. Minimal Breakpoint Systems for Univariate Functions," Working Papers 2012-12, Colorado School of Mines, Division of Economics and Business.

    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. Steffen Rebennack & Josef Kallrath, 2015. "Continuous Piecewise Linear Delta-Approximations for Bivariate and Multivariate Functions," Journal of Optimization Theory and Applications, Springer, vol. 167(1), pages 102-117, October.
    2. Becker, Tristan & Lier, Stefan & Werners, Brigitte, 2019. "Value of modular production concepts in future chemical industry production networks," European Journal of Operational Research, Elsevier, vol. 276(3), pages 957-970.
    3. Codas, Andrés & Camponogara, Eduardo, 2012. "Mixed-integer linear optimization for optimal lift-gas allocation with well-separator routing," European Journal of Operational Research, Elsevier, vol. 217(1), pages 222-231.
    4. Josef Kallrath & Steffen Rebennack, 2014. "Cutting ellipses from area-minimizing rectangles," Journal of Global Optimization, Springer, vol. 59(2), pages 405-437, July.
    5. Wang, X. & Li, D. & O'brien, C. & Li, Y., 2010. "A production planning model to reduce risk and improve operations management," International Journal of Production Economics, Elsevier, vol. 124(2), pages 463-474, April.
    6. Tsai, Kune-muh & Wang, Shan-chi, 2009. "Multi-site available-to-promise modeling for assemble-to-order manufacturing: An illustration on TFT-LCD manufacturing," International Journal of Production Economics, Elsevier, vol. 117(1), pages 174-184, January.
    7. Azaron, A. & Brown, K.N. & Tarim, S.A. & Modarres, M., 2008. "A multi-objective stochastic programming approach for supply chain design considering risk," International Journal of Production Economics, Elsevier, vol. 116(1), pages 129-138, November.
    8. Shiva Moslemi & Mohammad Hossein Zavvar Sabegh & Abolfazl Mirzazadeh & Yucel Ozturkoglu & Eric Maass, 2017. "A multi-objective model for multi-production and multi-echelon closed-loop pharmaceutical supply chain considering quality concepts: NSGAII approach," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 8(2), pages 1717-1733, November.
    9. Timo Berthold & Jakob Witzig, 2021. "Conflict Analysis for MINLP," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 421-435, May.
    10. Andjelka Kelic & Zachary A. Collier & Christopher Brown & Walter E. Beyeler & Alexander V. Outkin & Vanessa N. Vargas & Mark A. Ehlen & Christopher Judson & Ali Zaidi & Billy Leung & Igor Linkov, 2013. "Decision framework for evaluating the macroeconomic risks and policy impacts of cyber attacks," Environment Systems and Decisions, Springer, vol. 33(4), pages 544-560, December.
    11. Rakiz, Asma & Absi, Nabil & Fenies, Pierre, 2023. "Comparing approaches for a multi-level planning problem in a mining industry," International Journal of Production Economics, Elsevier, vol. 265(C).
    12. Michelle L. Blom & Christina N. Burt & Adrian R. Pearce & Peter J. Stuckey, 2014. "A Decomposition-Based Heuristic for Collaborative Scheduling in a Network of Open-Pit Mines," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 658-676, November.
    13. Kazda, Kody & Li, Xiang, 2024. "A linear programming approach to difference-of-convex piecewise linear approximation," European Journal of Operational Research, Elsevier, vol. 312(2), pages 493-511.
    14. Yin-Yann Chen & Hsiao-Yao Fan, 2013. "The Multi-Site Order Fulfillment-Planning Model: A Global Corporation Case Study," Journal of Social and Development Sciences, AMH International, vol. 4(5), pages 236-241.
    15. Sun, X.T. & Chung, S.H. & Chan, Felix T.S. & Wang, Zheng, 2018. "The impact of liner shipping unreliability on the production–distribution scheduling of a decentralized manufacturing system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 242-269.
    16. Peter Kirst & Oliver Stein & Paul Steuermann, 2015. "Deterministic upper bounds for spatial branch-and-bound methods in global minimization with nonconvex constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(2), pages 591-616, July.
    17. Dwi Iryaning Handayani & Ilyas Masudin & Ahmad Rusdiansyah & Judi Suharsono, 2021. "Production-Distribution Model Considering Traceability and Carbon Emission: A Case Study of the Indonesian Canned Fish Food Industry," Logistics, MDPI, vol. 5(3), pages 1-21, September.
    18. J. Behnamian & S. M. T. Fatemi Ghomi, 2016. "A survey of multi-factory scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(1), pages 231-249, February.
    19. Cheng Guo & Merve Bodur & Dionne M. Aleman & David R. Urbach, 2021. "Logic-Based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1551-1569, October.
    20. Jans, R.F. & Degraeve, Z., 2005. "Modeling Industrial Lot Sizing Problems: A Review," ERIM Report Series Research in Management ERS-2005-049-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.

    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:mns:wpaper:wp201213. 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: Jared Carbone (email available below). General contact details of provider: https://edirc.repec.org/data/decsmus.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.