Using linear programming to assess spatial access | Hacker News Reader

Using linear programming to assess spatial access

andrewpwheeler.com

70 pointsapwheele12 comments

PSA: Scipy has been offering a MILP and regular LP solvers for a few versions now. Very simple to use, was a delight to find out I didn’t need extra packages for a problem at work

Anyone has any idea why solvers in this space didn't get the same boom and open source availability like the machine learning stuff got in the recent years?

Good question, my thoughts: 1) to apply an LP or MILP to a practical problem that a business cares about requires a rare mix: one or a small number of people to have domain knowledge, knowledge about LPs/MILPs, and a good fit to the problem at hand. 2) the types of problem where LPs/MILPs reduce business expense is (currently) different from the spaces where ML has found success. This could change, but LPs have been applied extensively to strategic/logistics/planning applications, which aren't as approachable as applications of chatGPT, xgboost, etc. 3) LPs - since they are convex and provide global solutions - don't naturally support a kaggle-type competition that pits individuals and teams against each other. 4) there exist good open source solvers and very nice APIs (scipy, cvxpy, cvxopt, etc for example) but also high-cost and high-performance commercial solvers that businesses do pay for (Gurobi, CPLEX, etc).

To add to the above: The high-performance commercial solvers typically offer a free (as in beer) licence for academics (students and researchers), so this subgroup has a smaller incentive to develop a competing solver.

Similarly, researches who do spend their time implementing solver algorithms and running tedious computational experiements (the work that the software vendors put in) have historically had difficulties getting academic credit for their work, because the journals favored theoretical work.

That being said, with HiGHS and SCIP, we have two open-source solvers developed in an academic setting, with a lot their graduates joining commercial software vendors. So it's not like these are two completely separate worlds.

Sadly though, the Open source solvers seem to perform pretty badly compared to commercial solvers.

https://plato.asu.edu/bench.html

True, especially on difficult problems. Open-source can be good enough for many practical applications, though.

In my opinion, the gap in performance is less important, but the commercial offerings are typically more robust/reliable.

There is better open source availability than 20 years ago, I think, let say JUMP in Julia.

But I would say the culprit as to why mathematical optimization is not hyped and not as open sourced is the fact that to the layman, mathematical optimization is less impressive than say Midjourney or ChatGpt. The solution of a bus route optimization might be impressive to a public transport planner, but it requires domain knowledge.

Also, problems that are solved with mathematical optimization are often big organization problems. Sure you can model, as in this blog post, access to opiod treatment center, but to see the "product", you would have to implement the solution of the LP, aka building the treatment centers, which is unlikely to happen unless you work for the government. With generative ML, you can see something coming out of your code that is not only x1= 1, x2=3, etc.

For someone who might not be familiar, JuMP is not a solver. It is a algebraic modeling language in the same vein as AMPL or Pyomo. You will still need a solver (and JuMP provides a lot of out of the box connections) like Gurobi, CPLEX or open-source ones like HiGHs.

For my public transit planning course, I tried to use gurobi to optimize the schedule of a given fictional city involving a single inner city loop with 8 branches or so. The problem ended up being an MILP with tens or hundreds of thousands of variables, and gurobi couldn’t give me optimal solutions after days of trying - only approximations, with poor bounds.

I know my approach may have been naive, but so was the problem. I think in real life people tend to use some sort of stochastic search to get good solutions, perhaps genetic algorithms or simulated annealing. Which won’t give u provably optimal solutions, but you’ll more quickly get good solutions.

Gurobi is my go to method for optimization, but I often don’t get solutions.

There's an interesting tool called LocalSolver that uses local search methods by default for everything but if it detects a "decidable" class of problem it can also use fancier algorithms capable of returning a global optima, likely running both in parallel.

Sadly I haven't had a chance to try it.

I wasn't around for too much of the 1980s, but I think there was a qualitatively similar hype cycle starting in the late 1970s.

MINOS, CPLEX, XpressMP, OSL, KORBX, GAMS, AMPL, and many other optimisation packages came out of that period. Those packages were not free software or open-source software, but they were available to researchers at universities in the First World. (It seems unfair to expect software from 1978 to be free software or open-source software as we understand it today given that the FSF dates to 1985 and the term "open-source" to the late 1990s. Also bear in mind that personal computing was in its own initial boom in the 1980s.)

Papadimitrou and Steiglitz's book (published 1982; I have the 1998 Dover edition) has an exercise (Chapter 15, exercise 19) in which you are to read a short 1979 New York Times article about the ellipsoid algorithm and "[d]etermine, where possible, whether each statement is (a) true, (b) false, (c) misleading, [or] (d) equivalent to a well-known conjecture, the solution of which was probably not known to [the article's author]."

There's a longer article written by the same author 20 days earlier, too, and that one has more unfounded speculation about applications of LP: https://www.nytimes.com/1979/11/07/archives/a-soviet-discove...

Karmarkar's 1984 interior-point method begat similar excitement, leading to a few thousand papers through the late 1990s, and a trickle still today, on interior-point algorithms of varying correctness, generality and efficiency.

The technology that came out of that hype cycle is phenomenally capable and usable, and it's subsequently been improved even further.

With my limited insight, I think a lot of big whale industry topics like Supply Chain relied a lot on OR (solvers techniques) and sharing that knowlege would indermine their dominance. That kept it locked heavily.

Reply on news.ycombinator.com