IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v145y2010i1d10.1007_s10957-009-9626-0.html
   My bibliography  Save this article

Piecewise-Linear Approximations of Multidimensional Functions

Author

Listed:
  • R. Misener

    (Princeton University)

  • C. A. Floudas

    (Princeton University)

Abstract

We develop explicit, piecewise-linear formulations of functions f(x):ℝ n ↦ℝ, n≤3, that are defined on an orthogonal grid of vertex points. If mixed-integer linear optimization problems (MILPs) involving multidimensional piecewise-linear functions can be easily and efficiently solved to global optimality, then non-analytic functions can be used as an objective or constraint function for large optimization problems. Linear interpolation between fixed gridpoints can also be used to approximate generic, nonlinear functions, allowing us to approximately solve problems using mixed-integer linear optimization methods. Toward this end, we develop two different explicit formulations of piecewise-linear functions and discuss the consequences of integrating the formulations into an optimization problem.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:joptap:v:145:y:2010:i:1:d:10.1007_s10957-009-9626-0
    DOI: 10.1007/s10957-009-9626-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-009-9626-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-009-9626-0?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. J. J. H. Forrest & J. P. H. Hirst & J. A. Tomlin, 1974. "Practical Solution of Large Mixed Integer Programming Problems with Umpire," Management Science, INFORMS, vol. 20(5), pages 736-773, January.
    2. Faiz A. Al-Khayyal & James E. Falk, 1983. "Jointly Constrained Biconvex Programming," Mathematics of Operations Research, INFORMS, vol. 8(2), pages 273-286, May.
    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. 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.
    2. Emmanuel Ogbe & Ali Almansoori & Michael Fowler & Ali Elkamel, 2023. "Optimizing Renewable Injection in Integrated Natural Gas Pipeline Networks Using a Multi-Period Programming Approach," Energies, MDPI, vol. 16(6), pages 1-24, March.
    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. Pantelis Broukos & Antonios Fragkogios & Nilay Shah, 2022. "A Linearized Mathematical Formulation for Combined Centralized and Distributed Waste Water Treatment Network Design," SN Operations Research Forum, Springer, vol. 3(3), pages 1-29, September.
    5. Xie, Shiwei & Hu, Zhijian & Wang, Jueying, 2020. "Two-stage robust optimization for expansion planning of active distribution systems coupled with urban transportation networks," Applied Energy, Elsevier, vol. 261(C).
    6. 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.
    7. 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.
    8. 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.
    9. Miten Mistry & Dimitrios Letsios & Gerhard Krennrich & Robert M. Lee & Ruth Misener, 2021. "Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1103-1119, July.
    10. Schäffer, Linn Emelie & Helseth, Arild & Korpås, Magnus, 2022. "A stochastic dynamic programming model for hydropower scheduling with state-dependent maximum discharge constraints," Renewable Energy, Elsevier, vol. 194(C), pages 571-581.
    11. 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. İhsan Yanıkoğlu & Erinç Albey & Serkan Okçuoğlu, 2022. "Robust Parameter Design and Optimization for Quality Engineering," SN Operations Research Forum, Springer, vol. 3(1), pages 1-36, March.
    2. Eli Towle & James Luedtke, 2018. "New solution approaches for the maximum-reliability stochastic network interdiction problem," Computational Management Science, Springer, vol. 15(3), pages 455-477, October.
    3. N. V. Thoai, 2000. "Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints," Journal of Optimization Theory and Applications, Springer, vol. 107(2), pages 331-354, November.
    4. Radu Baltean-Lugojan & Ruth Misener, 2018. "Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness," Journal of Global Optimization, Springer, vol. 71(4), pages 655-690, August.
    5. Evrim Dalkiran & Hanif Sherali, 2013. "Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality," Journal of Global Optimization, Springer, vol. 57(4), pages 1147-1172, December.
    6. M. M. Faruque Hasan, 2018. "An edge-concave underestimator for the global optimization of twice-differentiable nonconvex problems," Journal of Global Optimization, Springer, vol. 71(4), pages 735-752, August.
    7. Gabriele Eichfelder & Peter Kirst & Laura Meng & Oliver Stein, 2021. "A general branch-and-bound framework for continuous global multiobjective optimization," Journal of Global Optimization, Springer, vol. 80(1), pages 195-227, May.
    8. Sonia Cafieri & Jon Lee & Leo Liberti, 2010. "On convex relaxations of quadrilinear terms," Journal of Global Optimization, Springer, vol. 47(4), pages 661-685, August.
    9. Keith Zorn & Nikolaos Sahinidis, 2014. "Global optimization of general nonconvex problems with intermediate polynomial substructures," Journal of Global Optimization, Springer, vol. 59(2), pages 673-693, July.
    10. Tsao, Yu-Chung & Lu, Jye-Chyi & An, Na & Al-Khayyal, Faiz & Lu, Richard W. & Han, Guanghua, 2014. "Retailer shelf-space management with trade allowance: A Stackelberg game between retailer and manufacturers," International Journal of Production Economics, Elsevier, vol. 148(C), pages 133-144.
    11. Al-Khayyal, Faiz & Hwang, Seung-June, 2007. "Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk, Part I: Applications and model," European Journal of Operational Research, Elsevier, vol. 176(1), pages 106-130, January.
    12. Siqian Shen & Murat Kurt & Jue Wang, 2015. "Chance-Constrained Programming Models and Approximations for General Stochastic Bottleneck Spanning Tree Problems," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 301-316, May.
    13. Marcia Fampa & Jon Lee, 2021. "Convexification of bilinear forms through non-symmetric lifting," Journal of Global Optimization, Springer, vol. 80(2), pages 287-305, June.
    14. Derpich, Ivan & Vera, Jorge R., 2006. "Improving the efficiency of the Branch and Bound algorithm for integer programming based on "flatness" information," European Journal of Operational Research, Elsevier, vol. 174(1), pages 92-101, October.
    15. Manuel Ruiz & Olivier Briant & Jean-Maurice Clochard & Bernard Penz, 2013. "Large-scale standard pooling problems with constrained pools and fixed demands," Journal of Global Optimization, Springer, vol. 56(3), pages 939-956, July.
    16. 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.
    17. Jochen Gorski & Frank Pfeuffer & Kathrin Klamroth, 2007. "Biconvex sets and optimization with biconvex functions: a survey and extensions," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 66(3), pages 373-407, December.
    18. J Irion & J-C Lu & F A Al-Khayyal & Y-C Tsao, 2011. "A hierarchical decomposition approach to retail shelf space management and assortment decisions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(10), pages 1861-1870, October.
    19. Marco Locatelli, 2016. "Polyhedral subdivisions and functional forms for the convex envelopes of bilinear, fractional and other bivariate functions over general polytopes," Journal of Global Optimization, Springer, vol. 66(4), pages 629-668, December.
    20. Irion, Jens & Lu, Jye-Chyi & Al-Khayyal, Faiz & Tsao, Yu-Chung, 2012. "A piecewise linearization framework for retail shelf space management models," European Journal of Operational Research, Elsevier, vol. 222(1), pages 122-136.

    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:spr:joptap:v:145:y:2010:i:1:d:10.1007_s10957-009-9626-0. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.