frontpage.
newsnewestaskshowjobs

Made with ♥ by @iamnishanth

Open Source @Github

Open in hackernews

Last fifty years of integer linear programming: Recent practical advances

https://inria.hal.science/hal-04776866v1
139•teleforce•13h ago

Comments

djoldman•6h ago
I've heard Gurobi is fairly expensive. Anyone willing to share pricing details?
Chio•5h ago
I 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://www.scipopt.org/

nrclark•4h ago
How do those stack up against lp_solve (https://lpsolve.sourceforge.net/5.5/index.htm)?
sirwhinesalot•1h ago
Waaaaay faster.
antman•3h ago
Ortools by google had good benchmarks
wombatpm•16m ago
You 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.

RainyDayTmrw•4h ago
What 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•4h ago
I don't know why people think it's such a deeply shrouded secret - it's ~10k a seat for a core-limited license.
edot•3h ago
It’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•3h ago
Gurobi does have a cloud service where you pay by the hour. A full non-academic license is pricy.
quanto•2h ago
The 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•1h ago
It'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.
perching_aix•5h ago
title could use [pdf] [2024]
gcr•5h ago
the link does not point to a pdf, it points to an abstract
omgmajk•5h ago
But downloads a pdf.
perching_aix•4h ago
Unless 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•2h ago
[pdf] implies that the link directly downloads a pdf.
perching_aix•1h ago
Then I am hereby indeed officially moderately annoyed & wondering.
wslh•5h ago
You can just add the reference to the paper: https://inria.hal.science/hal-04776866v1/document
CyberDildonics•2h ago
Integer linear programming doesn't sound very complex.
arnsholt•2h ago
You can encode travelling salesman as an ILP problem, so it’s a pretty tricky problem.
luiwammus•2h ago
This 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•21m ago
The point is the implied np-completeness of integer programming.
thrance•2h ago
It's harder than linear programming though.
lambdaone•2h ago
It's substantially harder than linear programming: it's equivalent to SAT, whereas linear programming is merely polynomial-time (and in practice weakly polynomial-time with current algorithms).
firesteelrain•1h ago
I normally use Simplex method which is fast and not polynomial in the worst case though
tgv•2h ago
You have to find the integers that fulfill a certain condition best. That's fundamentally different from real numbers. It looks exactly like other numerical problems, but there's no general solution for it, only (very good) heuristics for specific classes.
CamperBob2•1h ago
Or very real.
FabHK•2h ago
I 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•2h ago
I 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•1h ago
Could 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•1h 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)?

lukebuehler•48m ago
scale and speed. for example, most quant trading firms run huge optimizations as often as possible. open-source solver often cannot even solve the problems (OOM exceptions, etc)
cpgxiii•40m ago
> the best solvers are just a large ensemble of heuristics for very specific sub-problems

The big commercial solvers have the resources (and the clients interested in helping) to have invested a lot of time in tuning everything in their solves to real-world problems. Heuristics are part of that; recognizing simpler sub-problems or approximations that can be fed back into the full problem is also part.

I think a big part is that the OSS solvers are somewhat hamstrung by the combination of several issues: (1) the barrier to entry in SoTA optimizer development is very high, meaning that there are very few researchers/developers capable of usefully contributing both the mathematical and programming needed in the first place, (2) if you are capable of (1), the career paths that make lots money lead you away from OSS contribution, and (3) the nature of OSS projects means that "customers" are unlikely to contribute back to kind of examples, performance data, and/or profiling that is really needed to improve the solvers.

There are some exceptions to (2), although being outside of traditional commercial solver development doesn't guarantee being OSS (e.g. SNOPT, developed at Stanford, is still commercially licensed). A lot of academic solver work happens in the context of particular applications (e.g. Clarabel) and so tends to be more narrowly focused on particular problem classes. A lot of other fields have gotten past this bottleneck by having a large tech company acquire an existing commercial project (e.g. Mujoco) or fund an OSS project as a means of undercutting competitors. There are narrow examples of this for solvers (e.g. Ceres) but I suspect the investment to develop an entire general-purpose solver stack from scratch has been considered prohibitive.

christina97•29m ago
It’s mostly that they work closely with clients in a very hands on way to implement problem-specific speedups. And they’ve been doing this for 10-20 years. In the MILP world this means good heuristics (to find good starting points for branch & bound, and to effectively prune the B&B tree), as well as custom cuts (to cut off fractional solutions in a way that effectively improves the objective and solution integrality).

It’s common that when researchers in Operations Research pick a problem, they can often beat Gurobi and other solvers pretty easily by writing their own cuts & heuristics. The solver companies just do this consistently (by hiring teams of PhDs and researchers) and have a battery of client problems to track improvements and watch for regressions.

beret4breakfast•1h ago
It 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•1h ago
SAT 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!

Acorn in the f'n WWDC 2025 Keynote

https://shapeof.com/archives/2025/6/acorn_fn_wwdc_2025_keynote.html
1•zdw•2m ago•0 comments

The Steps of Life

https://publicdomainreview.org/collection/the-steps-of-life/
1•kawera•5m ago•0 comments

Computer Noises [video]

https://www.youtube.com/watch?v=tIOR7kRevPU
1•marvinborner•7m ago•0 comments

Prompty: An asset class and format for LLM prompts

https://github.com/microsoft/prompty
1•saikatsg•12m ago•0 comments

GitHub's CEO says startups can only get so far with vibe coding

https://www.msn.com/en-us/money/technology/github-s-ceo-says-startups-can-only-get-so-far-with-vibe-coding/ar-AA1GER5q
1•kmdupree•13m ago•0 comments

DocumentDB Extension for VS Code

https://github.com/microsoft/vscode-documentdb
1•saikatsg•15m ago•0 comments

AI Concepts Every Developer Should Know

https://substackcdn.com/image/fetch/f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2Fbca8fe62-8673-4ef9-a0e7-0489f56de848_1280x1546.jpeg
1•metadat•16m ago•1 comments

Vibe Tennis

https://vibe.tennis/
1•rmason•17m ago•0 comments

Atomic Bomb Considered as Hungarian High School Science Fair Project

https://slatestarcodex.com/2017/05/26/the-atomic-bomb-considered-as-hungarian-high-school-science-fair-project/
1•srean•18m ago•0 comments

Dodgy High Voltage Experiments – 787 Volts from a $2 Board [video]

https://www.youtube.com/watch?v=2UUn6yFibcM
1•iamflimflam1•20m ago•0 comments

Do Clouds Mostly Form Above the Lakes?

https://old.reddit.com/r/Physics/comments/1lbdgng/do_clouds_mostly_form_above_the_lakes/
1•dargscisyhp•20m ago•0 comments

Anne Wojcicki is taking back control of 23andMe

https://www.theverge.com/news/687123/23andme-anne-wojcicki-acquisition
3•bookofjoe•23m ago•0 comments

Implement CI/CD monitoring using OpenTelemetry

https://signoz.io/blog/cicd-observability-with-opentelemetry/
1•ankit01-oss•23m ago•0 comments

Atmospheric chemistry enhances climate mitigation potential of tree restoration

https://www.nature.com/articles/s43247-025-02343-9
2•PaulHoule•26m ago•0 comments

Neanderthals Spread Across Asia with Surprising Speed–and Now We Know How

https://gizmodo.com/neanderthals-spread-across-asia-with-surprising-speed-and-now-we-know-how-2000613781
1•rntn•27m ago•0 comments

Writers, Abandon Literary Prizes

https://www.persuasion.community/p/writers-abandon-literary-prizes
1•Michelangelo11•28m ago•0 comments

Ask HN: Career Advice for Younger Folk

1•radialstub•29m ago•0 comments

Oxcaml

https://blog.janestreet.com/introducing-oxcaml/
3•bvaldivielso•31m ago•1 comments

Show HN: US Protest Map

https://protestmap.info
2•throwaway-cusc•33m ago•1 comments

Why I joined DOGE

https://www.npr.org/2025/06/13/1254121714/doge-staffer-sahil-lavingia-musk-va-fired
1•rmason•35m ago•0 comments

Parallel Self-Hosted Code Generation in the Zig Compiler

https://ziglang.org/devlog/2025/#2025-06-14
4•kristoff_it•35m ago•0 comments

The Most Important Memory Is Still the One Inside Your Head

https://carlhendrick.substack.com/p/the-most-important-memory-is-still
2•transpute•36m ago•0 comments

What Old Money Looks Like in America, and Who Pays for It

https://www.newyorker.com/culture/photo-booth/what-old-money-looks-like-in-america-and-who-pays-for-it
2•rbanffy•37m ago•0 comments

Collatz's Ant – alternative representation of Collatz dynamics

https://gbragafibra.github.io/2025/05/19/collatz_ant4.html
1•Fibra•39m ago•0 comments

The Death of the Summer Job

https://financialpost.com/fp-work/canadian-students-face-jobless-summer
1•like_any_other•48m ago•1 comments

Select() FD Crash Solved

https://github.com/Exafunction/codeium/pull/207
1•RAPIDEN•48m ago•1 comments

Novo Nordisk's Canadian Mistake

https://www.science.org/content/blog-post/novo-nordisk-s-canadian-mistake
2•mxhold•49m ago•0 comments

How to a DSL for typesafe and maintainable regex, and even more

https://github.com/Stream29/RegexDsl/blob/master/BuildDslStory.md
2•Stream•53m ago•0 comments

I built a site to explore the most popular Japanese anime by year

https://hot-anime.techartlife.com/
1•techartlife•55m ago•1 comments

Sleep Is for Backpropagation (2017)

https://dimitarsimeonov.com/2017/12/22/sleep-is-for-backpropagation
2•ijidak•58m ago•1 comments