Hacker News Reader

Comment by cjalmeida | Hacker News Reader

It's not particularly new, but recently I've been involved a lot with solving large combinatorial optimization problems

https://en.m.wikipedia.org/wiki/Combinatorial_optimization

Algos to solve those both exact methods and heuristics are super useful in real world applications, and very underappreciated by the HN crowd IMO.

View on HN

Yes! Me too, there's a whole world out there and it's codified in bullet-proof programs like CPLEX or gurobi. Sadly they are expensive and it's not obvious if a given problem's size and complexity will tailor itself to some of their heuristics.

Have you been doing it by hand or using a big program?

Answer Set Programming is an incredibly powerful tool to declaratively solve combinatorial problems. Clingo is one of the best open source implementations in my opinion: https://github.com/potassco/clingo

  - Based on conflict driven nogood learning, it has incredible performance (including good multithreading)
  - It has different optimization and enumeration modes
  - It has strong built-in heuristics, but also allows manual heuristics
  - It allows incremental solving
  - It has a nice API to integrate other solving paradigms (like difference logic and constraint programming, for which implementations already exist)
  - There is a huge ecosystem around it

And much more, go check it out!

At $DayJob, we deal with OR problems for large companies and typically, when possible, we leverage Gurobi to solve Mixed Integer Linear Programming (MIP) formulations. However it's not unusual for the problems to be huge to the point even Gurobi can't solve them in a reasonable time. And of course, there's the case where the problem can't be formulated (or approximated) as a linear program at all.

So, in a couple projects I was involved we had to resort to manually constructed heuristics such as Simulated Annealing (SA) and Large Neighborhood Search (LNS).

A very cool large scale approach we resorted in some problems (eg. airline scheduling) was Column Generation[1]. Not only it solved in minutes what took hours in the MIP implementation, unlike SA and LNS it's and exact method that provide valid bounds to global optimality.

[1]: https://en.wikipedia.org/wiki/Column_generation

I like the Column Generation idea. Not a big fan of SA and LNS as you often can't really tell the relative quality of the solutions. I've often pushed for a different, simpler model form when the larger model isn't solvable in the usual ways. Running out of memory in CPLEX or Gurobi is a sign you need to reformulate more than anything else. Of course, that requires having people capable of formulating and evaluating math programming formulations. Turns out there aren't so many of those. Surprised me at first, but I guess I shouldn't be surprised. The real trick in optimization is coming up with the right formulation.

> Algos to solve those both exact methods and heuristics are super useful in real world applications, and very underappreciated by the HN crowd IMO.

If you are in the HN crowd, the 'opposite' direction is useful:

Know that effective generic solvers exist for these problems (but don't worry about how they do it), and re-formulate many of the trickier problems you encounter in the languages of these solvers, instead of eg writing your own bespoke algorithm to assign tents at the company picnic.

> Algos to solve those both exact methods and heuristics are super useful in real world applications, and very underappreciated by the HN crowd IMO.

There just aren't many situations where they're useful. Time scheduling, logistics, operations, there are only a handful of places where these problems are so important that they need to be solved optimally or nearly optimally.

IMO, the main benefit of those exact algos are the they provide optimality bounds, allowing you to make informed decision to continue or stop and provide a non-optimal solution. This is valuable in many practical situations.

>Time scheduling, logistics, operations...

Add marketing (pricing, assortment, ...) and finance (portfolio, captial budgeting, ...) to those.

And those are huge domains, moving trillions of USD globally each year. Many companies (think most of the Global 2000) benefit from a couple % improvement on their operations that lead to many $$ in savings.

Even just arranging UI elements around a page could be done with these solvers, instead of coding up heuristics to satisfy your constraints by hand.

I don't think this is true. It's just that there aren't many optimization practitioners and the OR community has done a terrible job promoting itself. The value in scheduling and logistics is well established. So optimizers tend to congregate. But optimization could be applied to lots of other domains successfully. ML is just minimizing a loss function. I see simulation and post-hoc analyses being applied in numerous situations where optimization would be more efficient and produce a guaranteed optimal result. RL on simple, static problems is really an MDP but I've seen organizations fail to realize this. Etc.

How often do these come up? I studied some OR stuff in grad school when I was evaluating solvers and brushed up against the OR tools community for some research ideas and from what I could tell the businesses that really needed it already use these tools and the other businesses just don't have enough business dependent on optimization to be worthwhile.

Are there some interesting examples of real world applications of this stuff? Is it like planning problems or supply chain optimization etc.?

I've used SAT solvers recreationally to try solve some mathematical combinatoricsish-like problems but interesting more down-to-earth applications have eluded me. I would love to dig deeper into this stuff.

I used a MILP solver to optimize my ship loadouts in Highfleet. It's rugged-looking, but works great. https://hfopt.jodavaho.io

Gurobi (maker of a MIP solver) has a bunch of industry case studies as marketing materials on their website:

https://www.gurobi.com/case_studies/

however, it's mixed-integer programming rather than SAT solvers/constraint programming, but similar in spirit.

Learning optimal decision trees and related ML models using SAT, MILP, and other mathematical optimization methods.

Some recent literature reviews:

https://link.springer.com/article/10.1007/s11750-021-00594-1

https://www.ijcai.org/proceedings/2021/608

What makes you think they’re underappreciated? I too have been spending a lot of time in this space recently and agree it’s one of the more fertile “maths meets reality” spaces :)

Any advice on how to get to work on this for a living?

I think it depends a lot on the domain you are in. A example of some domains with lots of discrete opt problems: transport, scheduling, logistics. And then read stuff by Stephen Boyd :)

I managed to smuggle applications of those solvers into a few jobs.

Eg at Goldman Sachs I used mixed integer linear programming to reshuffle the assignments of particular departments' computing needs to specific data centres. Before I got my hands at this, people used to just do it manually and hadn't even realized this was something were you could optimize systematically and squeeze some efficiency out of.

If you have an eye for it, you can find similar opportunities in many areas of many companies. Assignment / scheduling is actually extremely common, if you can recognise it. It's also relatively easy to show an improvement that you can measure in dollars, which always goes over well with the business folks.

Reply on news.ycombinator.com