IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v219y2012i1p86-95.html
   My bibliography  Save this article

Fitting piecewise linear continuous functions

Author

Listed:
  • Toriello, Alejandro
  • Vielma, Juan Pablo

Abstract

We consider the problem of fitting a continuous piecewise linear function to a finite set of data points, modeled as a mathematical program with convex objective. We review some fitting problems that can be modeled as convex programs, and then introduce mixed-binary generalizations that allow variability in the regions defining the best-fit function’s domain. We also study the additional constraints required to impose convexity on the best-fit function.

Suggested Citation

  • Toriello, Alejandro & Vielma, Juan Pablo, 2012. "Fitting piecewise linear continuous functions," European Journal of Operational Research, Elsevier, vol. 219(1), pages 86-95.
    • Handle: RePEc:eee:ejores:v:219:y:2012:i:1:p:86-95
    DOI: 10.1016/j.ejor.2011.12.030
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711011246
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2011.12.030?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. Kumar Abhishek & Sven Leyffer & Jeff Linderoth, 2010. "FilMINT: An Outer Approximation-Based Solver for Convex Mixed-Integer Nonlinear Programs," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 555-567, November.
    2. Novoa, Clara & Storer, Robert, 2009. "An approximate dynamic programming approach for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 196(2), pages 509-515, July.
    3. Papadaki, Katerina P. & Powell, Warren B., 2002. "Exploiting structure in adaptive dynamic programming algorithms for a stochastic batch service problem," European Journal of Operational Research, Elsevier, vol. 142(1), pages 108-127, October.
    4. Bot, Radu Ioan & Lorenz, Nicole, 2011. "Optimization problems in statistical learning: Duality and optimality conditions," European Journal of Operational Research, Elsevier, vol. 213(2), pages 395-404, September.
    5. Ruppert,David & Wand,M. P. & Carroll,R. J., 2003. "Semiparametric Regression," Cambridge Books, Cambridge University Press, number 9780521785167, September.
    6. Lau, Kin-nam & Leung, Pui-lam & Tse, Ka-kit, 1999. "A mathematical programming approach to clusterwise regression model and its extensions," European Journal of Operational Research, Elsevier, vol. 116(3), pages 640-652, August.
    7. Strikholm, Birgit, 2006. "Determining the number of breaks in a piecewise linear regression model," SSE/EFI Working Paper Series in Economics and Finance 648, Stockholm School of Economics.
    8. Juan Pablo Vielma & Shabbir Ahmed & George Nemhauser, 2010. "Mixed-Integer Models for Nonseparable Piecewise-Linear Optimization: Unifying Framework and Extensions," Operations Research, INFORMS, vol. 58(2), pages 303-315, April.
    9. Dimitris Bertsimas & Romy Shioda, 2007. "Classification and Regression via Integer Optimization," Operations Research, INFORMS, vol. 55(2), pages 252-271, April.
    10. Ruppert,David & Wand,M. P. & Carroll,R. J., 2003. "Semiparametric Regression," Cambridge Books, Cambridge University Press, number 9780521780506, September.
    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. Lingxun Kong & Christos T. Maravelias, 2020. "On the Derivation of Continuous Piecewise Linear Approximating Functions," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 531-546, July.
    2. Ruobing Shen & Bo Tang & Leo Liberti & Claudia D’Ambrosio & Stéphane Canu, 2021. "Learning discontinuous piecewise affine fitting functions using mixed integer programming over lattice," Journal of Global Optimization, Springer, vol. 81(1), pages 85-108, September.
    3. Jon Lee & Daphne Skipper & Emily Speakman & Luze Xu, 2023. "Gaining or Losing Perspective for Piecewise-Linear Under-Estimators of Convex Univariate Functions," Journal of Optimization Theory and Applications, Springer, vol. 196(1), pages 1-35, January.
    4. Ploussard, Quentin, 2024. "Piecewise linear approximation with minimum number of linear segments and minimum error: A fast approach to tighten and warm start the hierarchical mixed integer formulation," European Journal of Operational Research, Elsevier, vol. 315(1), pages 50-62.
    5. Noam Goldberg & Youngdae Kim & Sven Leyffer & Thomas Veselka, 2014. "Adaptively refined dynamic program for linear spline regression," Computational Optimization and Applications, Springer, vol. 58(3), pages 523-541, July.
    6. Wang, Yongqiao & Wang, Shouyang & Dang, Chuangyin & Ge, Wenxiu, 2014. "Nonparametric quantile frontier estimation under shape restriction," European Journal of Operational Research, Elsevier, vol. 232(3), pages 671-678.
    7. 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.
    8. Huang, Zhiliang & Wang, Huaixing & Gan, Zhouwang & Yang, Tongguang & Yuan, Cong & Lei, Bing & Chen, Jie & Wu, Shengben, 2024. "An mechanical/thermal analytical model for prismatic lithium-ion cells with silicon‑carbon electrodes in charge/discharge cycles," Applied Energy, Elsevier, vol. 365(C).
    9. Noam Goldberg & Steffen Rebennack & Youngdae Kim & Vitaliy Krasko & Sven Leyffer, 2021. "MINLP formulations for continuous piecewise linear function fitting," Computational Optimization and Applications, Springer, vol. 79(1), pages 223-233, May.
    10. David Lucas dos Santos Abreu & Erlon Cristian Finardi, 2022. "Continuous Piecewise Linear Approximation of Plant-Based Hydro Production Function for Generation Scheduling Problems," Energies, MDPI, vol. 15(5), pages 1-23, February.
    11. Jan Szczegielniak & Krzysztof J Latawiec & Jacek Łuniewski & Rafał Stanisławski & Katarzyna Bogacz & Marcin Krajczy & Marek Rydel, 2018. "A study on nonlinear estimation of submaximal effort tolerance based on the generalized MET concept and the 6MWT in pulmonary rehabilitation," PLOS ONE, Public Library of Science, vol. 13(2), pages 1-18, February.
    12. Huaiyu Zhu & Yun Pan & Kwang-Ting Cheng & Ruohong Huan, 2018. "A lightweight piecewise linear synthesis method for standard 12-lead ECG signals based on adaptive region segmentation," PLOS ONE, Public Library of Science, vol. 13(10), pages 1-22, October.
    13. Fodstad, Marte & Crespo del Granado, Pedro & Hellemo, Lars & Knudsen, Brage Rugstad & Pisciella, Paolo & Silvast, Antti & Bordin, Chiara & Schmidt, Sarah & Straus, Julian, 2022. "Next frontiers in energy system modelling: A review on challenges and the state of the art," Renewable and Sustainable Energy Reviews, Elsevier, vol. 160(C).
    14. Aakil M. Caunhye & Douglas Alem, 2023. "Practicable robust stochastic optimization under divergence measures with an application to equitable humanitarian response planning," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 45(3), pages 759-806, September.
    15. John Alasdair Warwicker & Steffen Rebennack, 2022. "A Comparison of Two Mixed-Integer Linear Programs for Piecewise Linear Function Fitting," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1042-1047, March.
    16. Juan Pablo Vielma, 2018. "Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139," Management Science, INFORMS, vol. 64(10), pages 4721-4734, October.
    17. Zheng, Xiao-Xue & Chang, Ching-Ter, 2021. "Topology design of remote patient monitoring system concerning qualitative and quantitative issues," Omega, Elsevier, vol. 98(C).
    18. Cody Allen & Mauricio Oliveira, 2022. "A Minimal Cardinality Solution to Fitting Sawtooth Piecewise-Linear Functions," Journal of Optimization Theory and Applications, Springer, vol. 192(3), pages 930-959, March.
    19. Wu, Yaqing & Maravelias, Christos T., 2024. "Piecewise linear trees as surrogate models for system design and planning under high-frequency temporal variability," European Journal of Operational Research, Elsevier, vol. 315(2), pages 541-552.
    20. Steffen Rebennack & Vitaliy Krasko, 2020. "Piecewise Linear Function Fitting via Mixed-Integer Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 507-530, April.
    21. Emilio Carrizosa & Vanesa Guerrero & Dolores Romero Morales, 2023. "On mathematical optimization for clustering categories in contingency tables," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 17(2), pages 407-429, June.
    22. Gambella, Claudio & Ghaddar, Bissan & Naoum-Sawaya, Joe, 2021. "Optimization problems for machine learning: A survey," European Journal of Operational Research, Elsevier, vol. 290(3), pages 807-828.

    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. Lingxun Kong & Christos T. Maravelias, 2020. "On the Derivation of Continuous Piecewise Linear Approximating Functions," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 531-546, July.
    2. Gambella, Claudio & Ghaddar, Bissan & Naoum-Sawaya, Joe, 2021. "Optimization problems for machine learning: A survey," European Journal of Operational Research, Elsevier, vol. 290(3), pages 807-828.
    3. Otto-Sobotka, Fabian & Salvati, Nicola & Ranalli, Maria Giovanna & Kneib, Thomas, 2019. "Adaptive semiparametric M-quantile regression," Econometrics and Statistics, Elsevier, vol. 11(C), pages 116-129.
    4. Mestekemper, Thomas & Windmann, Michael & Kauermann, Göran, 2010. "Functional hourly forecasting of water temperature," International Journal of Forecasting, Elsevier, vol. 26(4), pages 684-699, October.
    5. Naschold, Felix, 2012. "“The Poor Stay Poor”: Household Asset Poverty Traps in Rural Semi-Arid India," World Development, Elsevier, vol. 40(10), pages 2033-2043.
    6. Arthur Charpentier & Emmanuel Flachaire & Antoine Ly, 2017. "Econom\'etrie et Machine Learning," Papers 1708.06992, arXiv.org, revised Mar 2018.
    7. Hyunju Son & Youyi Fong, 2021. "Fast grid search and bootstrap‐based inference for continuous two‐phase polynomial regression models," Environmetrics, John Wiley & Sons, Ltd., vol. 32(3), May.
    8. Welham, S.J. & Thompson, R., 2009. "A note on bimodality in the log-likelihood function for penalized spline mixed models," Computational Statistics & Data Analysis, Elsevier, vol. 53(4), pages 920-931, February.
    9. Dlugosz, Stephan & Mammen, Enno & Wilke, Ralf A., 2017. "Generalized partially linear regression with misclassified data and an application to labour market transitions," Computational Statistics & Data Analysis, Elsevier, vol. 110(C), pages 145-159.
    10. Longhi, Christian & Musolesi, Antonio & Baumont, Catherine, 2014. "Modeling structural change in the European metropolitan areas during the process of economic integration," Economic Modelling, Elsevier, vol. 37(C), pages 395-407.
    11. Kuhlenkasper, Torben & Kauermann, Göran, 2010. "Female wage profiles: An additive mixed model approach to employment breaks due to childcare," HWWI Research Papers 2-18, Hamburg Institute of International Economics (HWWI).
    12. Strasak, Alexander M. & Umlauf, Nikolaus & Pfeiffer, Ruth M. & Lang, Stefan, 2011. "Comparing penalized splines and fractional polynomials for flexible modelling of the effects of continuous predictor variables," Computational Statistics & Data Analysis, Elsevier, vol. 55(4), pages 1540-1551, April.
    13. Christian Schluter & Jackline Wahba, 2012. "Abstract: Illegal Migration, Wages, and Remittances: Semi-Parametric Estimation of Illegality Effects," Norface Discussion Paper Series 2012037, Norface Research Programme on Migration, Department of Economics, University College London.
    14. Zi Ye & Giles Hooker & Stephen P. Ellner, 2021. "Generalized Single Index Models and Jensen Effects on Reproduction and Survival," Journal of Agricultural, Biological and Environmental Statistics, Springer;The International Biometric Society;American Statistical Association, vol. 26(3), pages 492-512, September.
    15. Esra Kürüm & Danh V. Nguyen & Qi Qian & Sudipto Banerjee & Connie M. Rhee & Damla Şentürk, 2024. "Spatiotemporal multilevel joint modeling of longitudinal and survival outcomes in end-stage kidney disease," Lifetime Data Analysis: An International Journal Devoted to Statistical Methods and Applications for Time-to-Event Data, Springer, vol. 30(4), pages 827-852, October.
    16. Ferraccioli, Federico & Sangalli, Laura M. & Finos, Livio, 2022. "Some first inferential tools for spatial regression with differential regularization," Journal of Multivariate Analysis, Elsevier, vol. 189(C).
    17. Carlo Fezzi & Ian Bateman, 2015. "The Impact of Climate Change on Agriculture: Nonlinear Effects and Aggregation Bias in Ricardian Models of Farmland Values," Journal of the Association of Environmental and Resource Economists, University of Chicago Press, vol. 2(1), pages 57-92.
    18. Blöchl, Andreas, 2014. "Trend Estimation with Penalized Splines as Mixed Models for Series with Structural Breaks," Discussion Papers in Economics 18446, University of Munich, Department of Economics.
    19. Akdeniz Duran, Esra & Härdle, Wolfgang Karl & Osipenko, Maria, 2012. "Difference based ridge and Liu type estimators in semiparametric regression models," Journal of Multivariate Analysis, Elsevier, vol. 105(1), pages 164-175.
    20. Jullion, Astrid & Lambert, Philippe, 2007. "Robust specification of the roughness penalty prior distribution in spatially adaptive Bayesian P-splines models," Computational Statistics & Data Analysis, Elsevier, vol. 51(5), pages 2542-2558, February.

    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:eee:ejores:v:219:y:2012:i:1:p:86-95. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.