IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i7p1038-d778494.html
   My bibliography  Save this article

Predicting the Execution Time of the Primal and Dual Simplex Algorithms Using Artificial Neural Networks

Author

Listed:
  • Sophia Voulgaropoulou

    (Department of Applied Informatics, School of Information Sciences, University of Macedonia, GR-54636 Thessaloniki, Greece
    These authors contributed equally to this work.)

  • Nikolaos Samaras

    (Department of Applied Informatics, School of Information Sciences, University of Macedonia, GR-54636 Thessaloniki, Greece
    These authors contributed equally to this work.)

  • Nikolaos Ploskas

    (Department of Electrical & Computer Engineering, Faculty of Engineering, University of Western Macedonia, GR-50100 Kozani, Greece
    These authors contributed equally to this work.)

Abstract

Selection of the most efficient algorithm for a given set of linear programming problems has been a significant and, at the same time, challenging process for linear programming solvers. The most widely used linear programming algorithms are the primal simplex algorithm, the dual simplex algorithm, and the interior point method. Interested in algorithm selection processes in modern mathematical solvers, we had previously worked on using artificial neural networks to formulate and propose a regression model for the prediction of the execution time of the interior point method on a set of benchmark linear programming problems. Extending our previous work, we are now examining a prediction model using artificial neural networks for the performance of CPLEX’s primal and dual simplex algorithms. Our study shows that, for the examined set of benchmark linear programming problems, a regression model that can accurately predict the execution time of these algorithms could not be formed. Therefore, we are proceeding further with our analysis, treating the problem as a classification one. Instead of attempting to predict exact values for the execution time of primal and dual simplex algorithms, our models estimate classes, expressed as time ranges, under which the execution time of each algorithm is expected to fall. Experimental results show a good performance of the classification models for both primal and dual methods, with the relevant accuracy score reaching 0.83 and 0.84 , respectively.

Suggested Citation

  • Sophia Voulgaropoulou & Nikolaos Samaras & Nikolaos Ploskas, 2022. "Predicting the Execution Time of the Primal and Dual Simplex Algorithms Using Artificial Neural Networks," Mathematics, MDPI, vol. 10(7), pages 1-21, March.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:7:p:1038-:d:778494
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/7/1038/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/7/1038/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Hyndman, Rob J. & Koehler, Anne B., 2006. "Another look at measures of forecast accuracy," International Journal of Forecasting, Elsevier, vol. 22(4), pages 679-688.
    2. William J. Carolan & James E. Hill & Jeffery L. Kennington & Sandra Niemi & Stephen J. Wichmann, 1990. "An Empirical Evaluation of the KORBX® Algorithms for Military Airlift Applications," Operations Research, INFORMS, vol. 38(2), pages 240-248, April.
    3. Mustafa Baz & Brady Hunsaker & Oleg Prokopyev, 2011. "How much do we “pay” for using default parameters?," Computational Optimization and Applications, Springer, vol. 48(1), pages 91-108, January.
    4. Sophia Voulgaropoulou & Nikolaos Samaras & Angelo Sifaleras, 2019. "Computational complexity of the exterior point simplex algorithm," Operational Research, Springer, vol. 19(2), pages 297-316, June.
    5. Nikolaos Ploskas & Nikolaos Samaras, 2017. "Correction to: Linear Programming Using MATLAB®," Springer Optimization and Its Applications, in: Linear Programming Using MATLAB®, pages E1-E3, Springer.
    6. Maros, Istvan & Haroon Khaliq, Mohammad, 2002. "Advances in design and implementation of optimization software," European Journal of Operational Research, Elsevier, vol. 140(2), pages 322-337, July.
    7. Jianfeng Liu & Nikolaos Ploskas & Nikolaos V. Sahinidis, 2019. "Tuning BARON using derivative-free optimization algorithms," Journal of Global Optimization, Springer, vol. 74(4), pages 611-637, August.
    8. David H. Wolpert & William G. Macready, 1995. "No Free Lunch Theorems for Search," Working Papers 95-02-010, Santa Fe Institute.
    9. Castle Jennifer L. & Doornik Jurgen A & Hendry David F., 2011. "Evaluating Automatic Model Selection," Journal of Time Series Econometrics, De Gruyter, vol. 3(1), pages 1-33, February.
    10. Osman Y. Özaltın & Brady Hunsaker & Andrew J. Schaefer, 2011. "Predicting the Solution Time of Branch-and-Bound Algorithms for Mixed-Integer Programs," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 392-403, August.
    11. Nikolaos Ploskas & Nikolaos Samaras, 2017. "Linear Programming Using MATLAB®," Springer Optimization and Its Applications, Springer, number 978-3-319-65919-0, June.
    12. Alwosheel, Ahmad & van Cranenburgh, Sander & Chorus, Caspar G., 2018. "Is your dataset big enough? Sample size requirements when using artificial neural networks for discrete choice analysis," Journal of choice modelling, Elsevier, vol. 28(C), pages 167-182.
    Full references (including those not matched with items on IDEAS)

    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. Jae Hyoung Lee & Nithirat Sisarat & Liguo Jiao, 2021. "Multi-objective convex polynomial optimization and semidefinite programming relaxations," Journal of Global Optimization, Springer, vol. 80(1), pages 117-138, May.
    2. Marianna E.-Nagy & Anita Varga, 2023. "A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 31(3), pages 691-711, September.
    3. Mohand Bentobache & Mohamed Telli & Abdelkader Mokhtari, 2022. "New LP-based local and global algorithms for continuous and mixed-integer nonconvex quadratic programming," Journal of Global Optimization, Springer, vol. 82(4), pages 659-689, April.
    4. Marianna E.-Nagy & Anita Varga, 2023. "A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 31(3), pages 691-711, September.
    5. Péter Tar & Bálint Stágel & István Maros, 2017. "Parallel search paths for the simplex algorithm," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(4), pages 967-984, December.
    6. repec:prg:jnlcfu:v:2022:y:2022:i:1:id:572 is not listed on IDEAS
    7. Chang, Andrew C. & Hanson, Tyler J., 2016. "The accuracy of forecasts prepared for the Federal Open Market Committee," Journal of Economics and Business, Elsevier, vol. 83(C), pages 23-43.
    8. Haoying Wang & Guohui Wu, 2022. "Modeling discrete choices with large fine-scale spatial data: opportunities and challenges," Journal of Geographical Systems, Springer, vol. 24(3), pages 325-351, July.
    9. Driver, Ciaran & Trapani, Lorenzo & Urga, Giovanni, 2013. "On the use of cross-sectional measures of forecast uncertainty," International Journal of Forecasting, Elsevier, vol. 29(3), pages 367-377.
    10. Ling Tang & Chengyuan Zhang & Tingfei Li & Ling Li, 2021. "A novel BEMD-based method for forecasting tourist volume with search engine data," Tourism Economics, , vol. 27(5), pages 1015-1038, August.
    11. Hewamalage, Hansika & Bergmeir, Christoph & Bandara, Kasun, 2021. "Recurrent Neural Networks for Time Series Forecasting: Current status and future directions," International Journal of Forecasting, Elsevier, vol. 37(1), pages 388-427.
    12. Michael Vössing & Niklas Kühl & Matteo Lind & Gerhard Satzger, 2022. "Designing Transparency for Effective Human-AI Collaboration," Information Systems Frontiers, Springer, vol. 24(3), pages 877-895, June.
    13. Frank, Johannes, 2023. "Forecasting realized volatility in turbulent times using temporal fusion transformers," FAU Discussion Papers in Economics 03/2023, Friedrich-Alexander University Erlangen-Nuremberg, Institute for Economics.
    14. Kourentzes, Nikolaos & Petropoulos, Fotios & Trapero, Juan R., 2014. "Improving forecasting by estimating time series structural components across multiple frequencies," International Journal of Forecasting, Elsevier, vol. 30(2), pages 291-302.
    15. Jeon, Yunho & Seong, Sihyeon, 2022. "Robust recurrent network model for intermittent time-series forecasting," International Journal of Forecasting, Elsevier, vol. 38(4), pages 1415-1425.
    16. Snyder, Ralph D. & Ord, J. Keith & Koehler, Anne B. & McLaren, Keith R. & Beaumont, Adrian N., 2017. "Forecasting compositional time series: A state space approach," International Journal of Forecasting, Elsevier, vol. 33(2), pages 502-512.
    17. Paulo Júlio & Pedro M. Esperança, 2012. "Evaluating the forecast quality of GDP components: An application to G7," GEE Papers 0047, Gabinete de Estratégia e Estudos, Ministério da Economia, revised Apr 2012.
    18. José Berenguel & L. Casado & I. García & Eligius Hendrix, 2013. "On estimating workload in interval branch-and-bound global optimization algorithms," Journal of Global Optimization, Springer, vol. 56(3), pages 821-844, July.
    19. Rivera, Nilza & Guzmán, Juan Ignacio & Jara, José Joaquín & Lagos, Gustavo, 2021. "Evaluation of econometric models of secondary refined copper supply," Resources Policy, Elsevier, vol. 73(C).
    20. Cameron Roach & Rob Hyndman & Souhaib Ben Taieb, 2021. "Non‐linear mixed‐effects models for time series forecasting of smart meter demand," Journal of Forecasting, John Wiley & Sons, Ltd., vol. 40(6), pages 1118-1130, September.
    21. Massimo Guidolin & Manuela Pedio, 2019. "Forecasting and Trading Monetary Policy Effects on the Riskless Yield Curve with Regime Switching Nelson†Siegel Models," Working Papers 639, IGIER (Innocenzo Gasparini Institute for Economic Research), Bocconi University.

    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:gam:jmathe:v:10:y:2022:i:7:p:1038-:d:778494. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.