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, December.
    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. 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.
    5. repec:prg:jnlcfu:v:2022:y:2022:i:1:id:572 is not listed on IDEAS
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. Alysha M De Livera, 2010. "Automatic forecasting with a modified exponential smoothing state space framework," Monash Econometrics and Business Statistics Working Papers 10/10, Monash University, Department of Econometrics and Business Statistics.
    14. Nikitopoulos, Christina Sklibosios & Thomas, Alice Carole & Wang, Jianxin, 2023. "The economic impact of daily volatility persistence on energy markets," Journal of Commodity Markets, Elsevier, vol. 30(C).
    15. I. Yu. Zolotova & V. V. Dvorkin, 2017. "Short-term forecasting of prices for the Russian wholesale electricity market based on neural networks," Studies on Russian Economic Development, Springer, vol. 28(6), pages 608-615, November.
    16. Döpke, Jörg & Fritsche, Ulrich & Müller, Karsten, 2019. "Has macroeconomic forecasting changed after the Great Recession? Panel-based evidence on forecast accuracy and forecaster behavior from Germany," Journal of Macroeconomics, Elsevier, vol. 62(C).
    17. Ester Vasta & Tommaso Scimone & Giovanni Nobile & Otto Eberhardt & Daniele Dugo & Massimiliano Maurizio De Benedetti & Luigi Lanuzza & Giuseppe Scarcella & Luca Patanè & Paolo Arena & Mario Cacciato, 2023. "Models for Battery Health Assessment: A Comparative Evaluation," Energies, MDPI, vol. 16(2), pages 1-34, January.
    18. Thiyanga S. Talagala & Feng Li & Yanfei Kang, 2019. "Feature-based Forecast-Model Performance Prediction," Monash Econometrics and Business Statistics Working Papers 21/19, Monash University, Department of Econometrics and Business Statistics.
    19. Martin Guth, 2022. "Predicting Default Probabilities for Stress Tests: A Comparison of Models," Papers 2202.03110, arXiv.org.
    20. Santamaría-Bonfil, G. & Reyes-Ballesteros, A. & Gershenson, C., 2016. "Wind speed forecasting for wind farms: A method based on support vector regression," Renewable Energy, Elsevier, vol. 85(C), pages 790-809.
    21. Jui-Sheng Chou & Dinh-Nhat Truong & Chih-Fong Tsai, 2021. "Solving Regression Problems with Intelligent Machine Learner for Engineering Informatics," Mathematics, MDPI, vol. 9(6), pages 1-25, March.

    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.