7 ms·
Last fifty years of integer linear programming: Recent practical advances (2024)
- djoldman 1y agoI've heard Gurobi is fairly expensive. Anyone willing to share pricing details?
- Chio 1y agoI can't share pricing details since they are confidential but if you just want to play with MIP you don't need to buy one of the big three (XPRESS, Gurobi, CPLEX) which are all very expensive but usually available for free for students. There are at least two good open source / free for non-commercial use MIP solvers available: https://highs.dev/ https://highs.dev/ https://www.scipopt.org/ https://www.scipopt.org/
- nrclark 1y agoHow do those stack up against lp_solve (https://lpsolve.sourceforge.net/5.5/index.htm https://lpsolve.sourceforge.net/5.5/index.htm)?
- sirwhinesalot 1y agoWaaaaay faster.
- 7thaccount 1y agoI've used both. They are waaaaaaaaaay faster, waaaay more reliable, and actually have support. You're not going to want to run your product that is responsible for millions off of something without really solid support.
- loehnsberg 1y agoCheck out the Mittelmann benchmarks: https://plato.asu.edu/bench.html https://plato.asu.edu/bench.html
- antman 1y agoOrtools by google had good benchmarks
- wombatpm 1y agoYou can get a temporary free license for Gurobi. You are limited to a 1000 node problem size, but you can learn how to use the tool and set up your problem. If you have a problem that needs Gurobi, it’s worth paying for it. Talk with their sales team. They are happy to help you get started. They know once you know how to use it, and how it can solve problems you will be inclined to use it in the future.
- aleph_minus_one 1y ago> If you have a problem that needs Gurobi, it’s worth paying for it. Thit statement is baed on the assumption that it is a "big money" problem. On the other hand, I know lots of problems interesting to nerds for which Gurobi would help (but nerds don't have the money).
- zozbot234 1y agoIf you have a "nerdy" problem you can probably get someone to write it up as a research paper and then it would easily fall under the academic license. To some extent, if you're buying a commercial license you're just paying for secrecy.
- aleph_minus_one 1y agoThis is not true: to get an academic license of Gurobi, you have to be a member of a degree-granting academic institution (otherwise every person could easily (illegally) get one): > https://www.gurobi.com/academia/academic-program-and-licenses/ https://www.gurobi.com/academia/academic-program-and-license... "You must be a faculty member, student, or staff of a recognized degree-granting academic institution. [...] To activate your license, you must connect from a recognized academic network."
- zozbot234 1y agoIf you can't even get a random member of any degree-granting institution (could just be random research staff, a student or adjunct faculty) to take some interest in your optimization problem as a subject for publishable research, does it even qualify as a "nerdy" problem?
- steine65 1y agoTheir price list wasn't that confidential last I spoke with the sales team. It depends on the license type. Last I heard, it's around $15k/year for a standard subscription license. You can probably trial it for free, or be a student and have longer free access.
- ge0ffrey 1y agoOther open source solvers: - Timefold Solver (not MIP, focussed on vehicle routing, job scheduling, shift rostering, etc): http://solver.timefold.ai http://solver.timefold.ai - Several solvers at COIN-OR: https://www.coin-or.org/ https://www.coin-or.org/ - Choco
- RainyDayTmrw 1y agoWhat I've heard - and obviously I can't confirm this - is that their only pricing tier is "call us" - at which point they try to figure out how much money you're making and ask for a slice of it.
- almostgotcaught 1y agoI don't know why people think it's such a deeply shrouded secret - it's ~10k a seat for a core-limited license.
- 0cf8612b2e1e 1y agoHeh, given all of the whispering, I was imagining something 10x the price. I am a nobody and have at least one license to a different product that is some $13k annual.
- edot 1y agoIt’s much cheaper than making suboptimal decisions slowly. Free solvers are fine for small problems (GLPK, for example), but lots of business problems are pretty much impossible to solve in the timeframe required unless you fork over cash for a premium solver (Gurobi being the best).
- cschmidt 1y agoGurobi does have a cloud service where you pay by the hour. A full non-academic license is pricy.
- quanto 1y agoThe last time I checked about a decade ago, a full license with multiple users and on a server was around 100k USD. I don't recall exact number of seats or server count restrictions. I want to add that, for many in the industry, it is well worth the price.
- __alexs 1y agoIt's not cheap but actually quite reasonable and the quality is very good vs free solvers. If you are building a product that needs MILP it's worth it.
- aleph_minus_one 1y ago> If you are building a product that needs MILP it's worth it. Rather: if you are building a product that will for sure make a lot of money, and needs MILP, it's worth it. A lot of product concepts that nerds create are very innovate, but are often some private side projects.
- __alexs 1y agoThe on demand pricing is pretty reasonable.
- aleph_minus_one 1y ago> The on demand pricing is pretty reasonable. Test case for your claim: someone privately intensively develops some open-source product that uses Gurobi as optimization backend. I guess on-demand will become very expensive.
- __alexs 1y agoIt would be best to develop against open models and plug Gurobi in separately in this situation I expect. If you are working on a problem that NEEDS Gurobi's level of quality, someone will pay you to build it (and probably keep it closed source.)
- aleph_minus_one 1y ago> It would be best to develop against open models and plug Gurobi in separately in this situation I expect. That is basically what I did in the end. > If you are working on a problem that NEEDS Gurobi's level of quality, someone will pay you to build it Here I vehemently disagree: there exist quite a lot of problems that would insanely profit from a great MILP solver: - Only a small subset of these problems have a (huge) commercial potential (i.e. are suitable for making some customer money). - Even if there exists an insane commercial potential, building great applications/models, and being able to convince someone with huge pockets (or even get access to them) are completely unrelated skills.
- 7thaccount 1y agoThe best MIP solvers (CPLEX, GUROBI, FICO) are all extremely expensive unless you're an academic. The free ones are fine for smaller problems. Some like Mosek are quite affordable and a good middle ground. To most organizations, the cost is reasonable for what they're getting.
- jwr 1y agoI wish somebody in this thread would quantify "extremely expensive". So many messages and we still have no idea how much they cost.
- aleph_minus_one 1y agoEstimate something in the ballpark of 10.000-15.000 USD per seat for a core-limited license (see also https://news.ycombinator.com/item?id=44277010 https://news.ycombinator.com/item?id=44277010), and quite much more money for a network license. Data point: https://www.solver.com/gurobi-solver-engine-lpmip-software https://www.solver.com/gurobi-solver-engine-lpmip-software A plugin for some software that contains a Gurobi license specific to this product costs 10.500 USD.
- jcd000 1y agoFor us it was more than 10x the price of CPLEX.
- perching_aix 1y agotitle could use [pdf] [2024]
- gcr 1y agothe link does not point to a pdf, it points to an abstract
- omgmajk 1y agoBut downloads a pdf.
- omgmajk 1y agoSince I can't edit the original comment, this seems to be untrue now but when I originally clicked the link from here it 100% did download the pdf directly, I tested it twice.
- perching_aix 1y agoUnless the OP meant to post specifically the abstract, which I very much doubt, the content submitted is the PDF linked. That said, if that's how the [pdf] tag is meant to be used on this forum, I could understand. Would just also leave me moderately annoyed & wondering why the tag isn't automated then, since that'd be automatable.
- gammarator 1y ago[pdf] implies that the link directly downloads a pdf.
- perching_aix 1y agoThen I am hereby indeed officially moderately annoyed & wondering.
- layer8 1y ago
- CyberDildonics 1y agoInteger linear programming doesn't sound very complex.
- arnsholt 1y agoYou can encode travelling salesman as an ILP problem, so it’s a pretty tricky problem.
- luiwammus 1y agoThis is actually a pretty poor example because we can solve huge TSP instances to optimality in practice (see the concorde solver). There exist many more tricky Combinatorial problems such as packing or covering problems that are typically much harder to solve to optimality.
- robotpepi 1y agoThe point is the implied np-completeness of integer programming.
- nullc 1y agoThe np-completeness of it is often not very relevant for practical concerns, as the parent post was mentioning. There are many applications with an underlying technically np-complete problem for which optimal solutions are easily found for almost all instances you will encounter. Because they are np-complete it's possible to construct instances which aren't efficiently solvable, but that doesn't mean you'll ever even encounter one in practice. Then even beyond that there are plenty of cases where an efficient approximation with bounded error exists, and that bounded error might be arbitrarily small. To give an easily understood example, consider a knapsack problem where the items are never larger than 1% of the knapsack size. There exists a trivial O(N log N) approximation algorithm: sort by value per size, include in that order until no more fit. This yields an optimal solution when the last selected item exactly fills the sack, and otherwise it yields an approximate solution which is suboptimal by no more than the unfilled space, which is no more than 1% due to the size constraint. And 1% is the worse case approximation error, normally less space will be unused and the lowest value per space will be a fraction of the highest value per space, so the actual average approximation error in a real application may be, say, 0.01%. If some other application constraint meant the item sizes would always add up to the sack size then the simple algorithm always gives an optimal solution. Of course, you can do better than the simple algorithm with some search but even the dumbest algorithm gives very good approximations and is sometimes optimal... and yet the general knapsack (even just the decision form) is a problem which is np-complete. This insight can be quite surprising to anyone who assumes np-complete == unsolvable. Complexity theory is awesome but it can also lead us astray.
- FabHK 1y agoI remember implementing some version of Gomory cutting hyperplanes back in the 1990s in Maple (for learning, not for production.) Looks like the field has progressed... > if we needed two months of running time to solve an LP in the early 1990s, we would need less than one second today. Recently, Bixby compared the machine-independent performance of two MILP solvers, CPLEX and Gurobi, between 1990 and 2020 and reported speed-ups of almost 4×10^6.
- dcminter 1y agoI vaguely recall building a resource allocation tool using IBM's "ILOG" mixed integer linear programming library and we realised that if we'd built the tool about 20 years earlier it would have still been running for the same problems we were now solving within 5 minutes. As I recall it the raw computer power had increased by a factor of around a thousand and the algorithms had improved by about the same, giving us a factor of a million improvement. Worth pondering when trying to predict the future! The "resources" in question were diamonds by the way...
- aquafox 1y agoCould someone maybe give a high-level explanation into why commercial ILP solvers (e.g. Gurobi) are that much better than free/open-source ones? Is it because ILP is inherently that difficult to solve (I know it's NP-hard), that the best solvers are just a large ensemble of heuristics for very specific sub-problems and thus no general "good" strategy has made it's way into the public domain?
- zozbot234 1y ago> solvers are just a large ensemble of heuristics for very specific sub-problems Isn't that statement trivially applicable to anything NP-Hard (which ILP is, since it's equivalent to SAT)?
- fooker 1y agoNo, good algorithms for NP hard problems can be more than just heuristics. Modern SAT solvers are a good example of this. CDCL is elegant.
- sirwhinesalot 1y agoA SAT solver without any preprocessing won't be competitive with SoTA SAT solver. CDCL is core to the problem, but it is not sufficient. You even have SAT solvers like CryptoMiniSAT that try to detect clauses that encode xor gates so they can use Gaussian Elimination. This is also true of ILP solvers. Simplex + Branch & Cut is elegant. But that's not how you get to the top.
- graycat 1y agoNP-hard is really hard, but it is hard for (a) polynomial running time, (b) for exact solutions, (c) on worst case problems. One might suspect that fast enough on specific problems for approximate solutions that still make/save a lot of money might also be welcome. Ah, perhaps not! E.g., in NYC, two guys had a marketing resource allocation problem, tried simulated annealing, and ran for days before giving up. They sent me the problem statement via email, and in one week I had the software written and in the next week used the IBM OSL (Optimization Subroutine Library) and some Lagrangian relaxation. In 500 primal-dual iterations with 600,000 variables 40,000 constraints found a feasible solution within 0.025% of optimality. So, I'd solved their problem (for practical purposes, the 0.025% has to count as a solving) for free. They were so embarrassed they wanted nothing to do with me. We never got to where I set a price for my work. The problem those two guys had was likely that, if they worked with me, then I would understand their customers and, then, beat the guys and take their customers. There in NYC, that happened a second time. If a guy is in, say, the auto business, and needs a lawyer, the guy might want the best lawyer but will not fear that the lawyer will enter the auto business as a powerful competitor. Similarly for a good medical doctor. For an optimization guy saving, say, 5% of the operating costs of a big business, say, $billion in revenue a year, all the management suite will be afraid of the guy getting too much power and work to get him out -- Goal Subordination 101 or just fighting to retain position in the tribe. After having some grand successes in applied math where other people had the problem but then being afraid that I would be too powerful, I formulated: If some technical, computing, math, etc. idea you have is so valuable, then start your own business exploiting that idea -- of course, need a suitable business for the idea to be powerful.
- beret4breakfast 1y agoIt feels like there’s a significant lack of “ML/AI” based approaches applied to these kinds of problems. I’ve seen a lot of example of RL/GNN papers that do attempt to solve smaller problems but it always feels like the best option is to just pay for a gurobi license and have at it. I’ve been doing some scheduling optimisation recently (close to job shop scheduling) and while there’s some examples of using RL they just don’t seem to cut it. I’ve resorted to evolutionary algorithms to get reasonable solutions to some big problems. Maybe it’s just always more efficient to using OR type approaches when you can formulate the problem well.
- zozbot234 1y agoSAT is a standard GOFAI problem and you can of course use any programming language in the ML family to write a SAT solver. Thus I'd say that "ML/AI" approaches are, if anything, quite applicable!
- 7thaccount 1y agoIt depends on the problem. The security contained unit commitment problem (how you figure out which power plants to turn on when) is an unbelievably complex problem that MILP solvers like Gurobi can find globally optimal solutions (within the bounds of the MIP gap) quickly. Sure you could create a genetic algorithm, but there is no guarantee it will give you an answer that isn't stuck in a local minima. That is assuming you can make it run fast. Neural networks are also going to be sub optimal.
- tormeh 1y agoCan anyone share how this is used in practice? Somehow I imagine implementing numerical optimization often fails due to the usual problems with data-driven approaches (trust, bad data, etc.) and ultimately someone important just decides how things are going to be done based on stomach feel.
- jakewins 1y agoWe use solvers throughout the stack at work: solvers to schedule home batteries and EVs in peoples homes optimally, solvers to schedule hundreds of thousands of those homes optimally as portfolios, solvers to trade that portfolio optimally. The EU electricity spot price is set each day in a single giant solver run, look up Euphemia for some write ups of how that works. Most any field where there is a clear goal to optimise and real money on the line will be riddled with solvers
- ies7 1y agoFMCG company here. We use these in practice of: 1. Salesman & delivery travel plan 2. Machine, Human and material resource scheduling for production 3. Inventory level for warehouse distribution center. This one isn't fully automatic because demand forecasting is hard
- shoo 1y agohave a read through the case studies: gurobi case studies: https://www.gurobi.com/case_studies/ https://www.gurobi.com/case_studies/ some cplex case studies: https://www.ibm.com/products/ilog-cplex-optimization-studio/resources https://www.ibm.com/products/ilog-cplex-optimization-studio/... hexaly (formerly localsolver) case studies: https://www.hexaly.com/customers https://www.hexaly.com/customers
- pradn 1y ago"... between 1988 and 2004, hardware got 1600 times faster, and LP solvers got 3300 times faster, allowing for a cumulative speed-up factor higher than 5 × 106, and that was already 20 years ago!" "The authors observed a speedup of 1000 between [the commercial MILP solvers of] 2001 and 2020 (50 due to algorithms, 20 due to faster computers)." I wonder if we can collect these speedup factors across computing subfields, decomposed by the contribution of algorithmic improvements, and faster computers. In compilers, there's "Proebsting's Law": compiler advances double computing power every 18 years.
- deleted 1y ago[deleted]
- Sankoaung 1y agoReply