Hacker News Reader

Comment by JZL003 | Hacker News Reader

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?

View on HN

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.

Reply on news.ycombinator.com