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

Tightening big Ms in integer programming formulations for support vector machines with ramp loss

Author

Listed:
  • Baldomero-Naranjo, Marta
  • Martínez-Merino, Luisa I.
  • Rodríguez-Chía, Antonio M.

Abstract

This paper considers various models of support vector machines with ramp loss, these being an efficient and robust tool in supervised classification for the detection of outliers. The exact solution approaches for the resulting optimization problem are of high demand for large datasets. Hence, the goal of this paper is to develop algorithms that provide efficient methodologies to exactly solve these optimization problems. These approaches are based on three strategies for obtaining tightened values of the big M parameters included in the formulation of the problem. Two of them require solving a sequence of continuous problems, while the third uses the Lagrangian relaxation to tighten the bounds. The proposed resolution methods are valid for the ℓ1-norm and ℓ2-norm ramp loss formulations. They were tested and compared with existing solution methods in simulated and real-life datasets, showing the efficiency of the developed methodology.

Suggested Citation

  • Baldomero-Naranjo, Marta & Martínez-Merino, Luisa I. & Rodríguez-Chía, Antonio M., 2020. "Tightening big Ms in integer programming formulations for support vector machines with ramp loss," European Journal of Operational Research, Elsevier, vol. 286(1), pages 84-100.
    • Handle: RePEc:eee:ejores:v:286:y:2020:i:1:p:84-100
    DOI: 10.1016/j.ejor.2020.03.023
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172030237X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.03.023?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. F. Plastria & E. Carrizosa, 2001. "Gauge Distances and Median Hyperplanes," Journal of Optimization Theory and Applications, Springer, vol. 110(1), pages 173-182, July.
    2. Valeriy Gavrishchaka & Supriya Banerjee, 2006. "Support Vector Machine as an Efficient Framework for Stock Market Volatility Forecasting," Computational Management Science, Springer, vol. 3(2), pages 147-160, April.
    3. Pietro Belotti & Pierre Bonami & Matteo Fischetti & Andrea Lodi & Michele Monaci & Amaya Nogales-Gómez & Domenico Salvagnin, 2016. "On handling indicator constraints in mixed integer programming," Computational Optimization and Applications, Springer, vol. 65(3), pages 545-566, December.
    4. Maldonado, Sebastián & Pérez, Juan & Bravo, Cristián, 2017. "Cost-based feature selection for Support Vector Machines: An application in credit scoring," European Journal of Operational Research, Elsevier, vol. 261(2), pages 656-665.
    5. J. Paul Brooks, 2011. "Support Vector Machines with the Ramp Loss and the Hard Margin Loss," Operations Research, INFORMS, vol. 59(2), pages 467-479, April.
    6. Wang, Haifeng & Zheng, Bichen & Yoon, Sang Won & Ko, Hoo Sang, 2018. "A support vector machine-based ensemble algorithm for breast cancer diagnosis," European Journal of Operational Research, Elsevier, vol. 267(2), pages 687-699.
    7. Víctor Blanco & Alberto Japón & Justo Puerto, 2020. "Optimal arrangements of hyperplanes for SVM-based multiclass classification," 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. 14(1), pages 175-199, March.
    8. O. L. Mangasarian, 1965. "Linear and Nonlinear Separation of Patterns by Linear Programming," Operations Research, INFORMS, vol. 13(3), pages 444-452, June.
    9. Pedro Duarte Silva, A., 2017. "Optimization approaches to Supervised Classification," European Journal of Operational Research, Elsevier, vol. 261(2), pages 772-788.
    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. Fajemisin, Adejuyigbe O. & Maragno, Donato & den Hertog, Dick, 2024. "Optimization with constraint learning: A framework and survey," European Journal of Operational Research, Elsevier, vol. 314(1), pages 1-14.
    2. Astorino, Annabella & Avolio, Matteo & Fuduli, Antonio, 2022. "A maximum-margin multisphere approach for binary Multiple Instance Learning," European Journal of Operational Research, Elsevier, vol. 299(2), pages 642-652.

    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. Astorino, Annabella & Avolio, Matteo & Fuduli, Antonio, 2022. "A maximum-margin multisphere approach for binary Multiple Instance Learning," European Journal of Operational Research, Elsevier, vol. 299(2), pages 642-652.
    2. Carrizosa, Emilio & Ramírez-Ayerbe, Jasone & Romero Morales, Dolores, 2024. "Mathematical optimization modelling for group counterfactual explanations," European Journal of Operational Research, Elsevier, vol. 319(2), pages 399-412.
    3. Blanquero, R. & Carrizosa, E. & Jiménez-Cordero, A. & Martín-Barragán, B., 2019. "Functional-bandwidth kernel for Support Vector Machine with Functional Data: An alternating optimization algorithm," European Journal of Operational Research, Elsevier, vol. 275(1), pages 195-207.
    4. Blanquero, Rafael & Carrizosa, Emilio & Molero-Río, Cristina & Romero Morales, Dolores, 2020. "Sparsity in optimal randomized classification trees," European Journal of Operational Research, Elsevier, vol. 284(1), pages 255-272.
    5. Sandra Benítez-Peña & Rafael Blanquero & Emilio Carrizosa & Pepa Ramírez-Cobo, 2019. "On support vector machines under a multiple-cost scenario," 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. 13(3), pages 663-682, September.
    6. Pedro Duarte Silva, A., 2017. "Optimization approaches to Supervised Classification," European Journal of Operational Research, Elsevier, vol. 261(2), pages 772-788.
    7. Z. R. Gabidullina, 2013. "A Linear Separability Criterion for Sets of Euclidean Space," Journal of Optimization Theory and Applications, Springer, vol. 158(1), pages 145-171, July.
    8. Wanpracha Art Chaovalitwongse, 2008. "Novel quadratic programming approach for time series clustering with biomedical application," Journal of Combinatorial Optimization, Springer, vol. 15(3), pages 225-241, April.
    9. Emilio Carrizosa & Belen Martin-Barragan, 2011. "Maximizing upgrading and downgrading margins for ordinal regression," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 74(3), pages 381-407, December.
    10. Marcin Fałdziński & Piotr Fiszeder & Witold Orzeszko, 2020. "Forecasting Volatility of Energy Commodities: Comparison of GARCH Models with Support Vector Regression," Energies, MDPI, vol. 14(1), pages 1-18, December.
    11. Yu, Lean & Wang, Shouyang & Lai, Kin Keung, 2009. "An intelligent-agent-based fuzzy group decision making model for financial multicriteria decision support: The case of credit scoring," European Journal of Operational Research, Elsevier, vol. 195(3), pages 942-959, June.
    12. De Caigny, Arno & Coussement, Kristof & De Bock, Koen W., 2018. "A new hybrid classification algorithm for customer churn prediction based on logistic regression and decision trees," European Journal of Operational Research, Elsevier, vol. 269(2), pages 760-772.
    13. Abdur Rasool & Chayut Bunterngchit & Luo Tiejian & Md. Ruhul Islam & Qiang Qu & Qingshan Jiang, 2022. "Improved Machine Learning-Based Predictive Models for Breast Cancer Diagnosis," IJERPH, MDPI, vol. 19(6), pages 1-19, March.
    14. Jian Luo & Shu-Cherng Fang & Zhibin Deng & Xiaoling Guo, 2016. "Soft Quadratic Surface Support Vector Machine for Binary Classification," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(06), pages 1-22, December.
    15. Nieddu, Luciano & Patrizi, Giacomo, 2000. "Formal methods in pattern recognition: A review," European Journal of Operational Research, Elsevier, vol. 120(3), pages 459-495, February.
    16. Lee, In Gyu & Yoon, Sang Won & Won, Daehan, 2022. "A Mixed Integer Linear Programming Support Vector Machine for Cost-Effective Group Feature Selection: Branch-Cut-and-Price Approach," European Journal of Operational Research, Elsevier, vol. 299(3), pages 1055-1068.
    17. Gao, Zheming & Fang, Shu-Cherng & Luo, Jian & Medhin, Negash, 2021. "A kernel-free double well potential support vector machine with applications," European Journal of Operational Research, Elsevier, vol. 290(1), pages 248-262.
    18. Xiang, Mengyuan & Rossi, Roberto & Martin-Barragan, Belen & Tarim, S. Armagan, 2023. "A mathematical programming-based solution method for the nonstationary inventory problem under correlated demand," European Journal of Operational Research, Elsevier, vol. 304(2), pages 515-524.
    19. Joanna Błajda & Edyta Barnaś & Anna Kucab, 2022. "Application of Personalized Education in the Mobile Medical App for Breast Self-Examination," IJERPH, MDPI, vol. 19(8), pages 1-21, April.
    20. Immanuel M. Bomze & Bo Peng, 2023. "Conic formulation of QPCCs applied to truly sparse QPs," Computational Optimization and Applications, Springer, vol. 84(3), pages 703-735, April.

    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:286:y:2020:i:1:p:84-100. 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.