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, January.
    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, January.
    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. 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.
    2. 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.
    3. Zanin, Luca & Marra, Giampiero, 2012. "Assessing the functional relationship between CO2 emissions and economic development using an additive mixed model approach," Economic Modelling, Elsevier, vol. 29(4), pages 1328-1337.
    4. Ni, Xiao & Zhang, Hao Helen & Zhang, Daowen, 2009. "Automatic model selection for partially linear models," Journal of Multivariate Analysis, Elsevier, vol. 100(9), pages 2100-2111, October.
    5. Proietti, Tommaso, 2010. "Trend Estimation," MPRA Paper 21607, University Library of Munich, Germany.
    6. 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.
    7. Javier Parada Gómez Urquiza & Alejandro López-Feldman, 2013. "Poverty dynamics in rural Mexico: What does the future hold?," Ensayos Revista de Economia, Universidad Autonoma de Nuevo Leon, Facultad de Economia, vol. 0(2), pages 55-74, November.
    8. Bethany Everett & David Rehkopf & Richard Rogers, 2013. "The Nonlinear Relationship Between Education and Mortality: An Examination of Cohort, Race/Ethnic, and Gender Differences," Population Research and Policy Review, Springer;Southern Demographic Association (SDA), vol. 32(6), pages 893-917, December.
    9. Tatiyana V. Apanasovich & David Ruppert & Joanne R. Lupton & Natasa Popovic & Nancy D. Turner & Robert S. Chapkin & Raymond J. Carroll, 2008. "Aberrant Crypt Foci and Semiparametric Modeling of Correlated Binary Data," Biometrics, The International Biometric Society, vol. 64(2), pages 490-500, June.
    10. Eduardo L. Montoya & Wendy Meiring, 2016. "An F-type test for detecting departure from monotonicity in a functional linear model," Journal of Nonparametric Statistics, Taylor & Francis Journals, vol. 28(2), pages 322-337, June.
    11. Yu, Jun, 2012. "A semiparametric stochastic volatility model," Journal of Econometrics, Elsevier, vol. 167(2), pages 473-482.
    12. Timothy K.M. Beatty & Erling Røed Larsen, 2005. "Using Engel curves to estimate bias in the Canadian CPI as a cost of living index," Canadian Journal of Economics/Revue canadienne d'économique, John Wiley & Sons, vol. 38(2), pages 482-499, May.
    13. 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.
    14. 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.
    15. Arthur Charpentier & Emmanuel Flachaire & Antoine Ly, 2017. "Econom\'etrie et Machine Learning," Papers 1708.06992, arXiv.org, revised Mar 2018.
    16. Jaroslaw Harezlak & Louise M. Ryan & Jay N. Giedd & Nicholas Lange, 2005. "Individual and Population Penalized Regression Splines for Accelerated Longitudinal Designs," Biometrics, The International Biometric Society, vol. 61(4), pages 1037-1048, December.
    17. 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.
    18. 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.
    19. Wei Huang & Oliver Linton & Zheng Zhang, 2022. "A Unified Framework for Specification Tests of Continuous Treatment Effect Models," Journal of Business & Economic Statistics, Taylor & Francis Journals, vol. 40(4), pages 1817-1830, October.
    20. Michael Wegener & Göran Kauermann, 2017. "Forecasting in nonlinear univariate time series using penalized splines," Statistical Papers, Springer, vol. 58(3), pages 557-576, 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: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.