HackerPapers

arXiv:2206.09787math.OC

Progress in Mathematical Programming Solvers from 2001 to 2020

Thorsten Koch, Timo Berthold, Jaap Pedersen, Charlie Vanaret

Abstract

This study investigates the progress made in LP and MILP solver performance during the last two decades by comparing the solver software from the beginning of the millennium with the codes available today. On average, we found out that for solving LP/MILP, computer hardware got about 20 times faster, and the algorithms improved by a factor of about nine for LP and around 50 for MILP, which gives a total speed-up of about 180 and 1,000 times, respectively. However, these numbers have a very high variance and they considerably underestimate the progress made on the algorithmic side: many problem instances can nowadays be solved within seconds, which the old codes are not able to solve within any reasonable time.

arXiv comments
Journal reference
EURO Journal on Computational Optimization, Volume 10 (2022)
DOI
doi:10.1016/j.ejco.2022.100031
Subjects
math.OCOptimization and Control

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Jul 2022 to Aug 2024.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Encyclopedia of Optimization 1 comment

    • The paper I have mentioned can be found here https://arxiv.org/pdf/2206.09787 There are so many things that have only been invented in the last couple of years like RINS, MCF cuts, conflict analysis, symmetry detection, dynamic search,... (see e.g. Tobias Achterberg's line of…

      mattalexView on HNParent context

  2. The importance of exponentially more computing power 1 comment

    • > we examine the contribution of more computing power to better outcomes No, they pick a set of problems where computational methods are known to have a beneficial impact and the plot every progress in that field against increased amounts of computing. Since amount of computing…

      freemintView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.