Hacker News Reader

Comment by ford | Hacker News Reader

Software engineers interested in ML/algorithms should learn about linear programming.

It's surprising how many problems can be formulated as linear optimization.

For example, in college I was talking to my Industrial Engineer friend about the average minimum number of swaps required to place billiards balls in an acceptable starting position in the rack (triangle). We both happened to write programs that used monte-carlo sampling to solve it - but my solution did BFS on the state space of a graph, and his used linear programming (which was _probably_ more efficient)

View on HN

A lot of polynomial time algorithms for combinatorial optimization problems can be interpreted as primal dual algorithms for the corresponding LPs, e.g. mst, matching(bipartite or general graph), network flow, matroid intersection, submodular flow. The extreme point solutions of some LPs also have interesting properties that you can exploit to design approximation algorithms for NP-complete problems. For example, you can prove that there is always a variable with value at least half in an extreme point solution of the steiner forest problem, so you can just iteratively round a variable and resolve the LP to get a 2-approximation. When I was in grad school that was the only 2-approximation algorithm for this problem. Another interesting thing is that you can solve LPs with exponentially many constraints as long as you have a polynomial time separation oracle.

One of my favourite courses in grad school was approximation algorithms and it involved reductions to LP. Lots of fun, can recommend.

Do you have a link to some materials to help get me started? I did an optimization/ILP MOOC once and that was indeed a lot of fun.

https://people.seas.harvard.edu/~cs224/fall14/lec.html

In particular, seems like lectures 9-11 have LP content.

Thanks!

We used the book "the design of approximation algorithms"

https://www.designofapproxalgs.com/book.pdf

I foresee a future where industrial engineering and CS are combined into some super-degree. There is currently a surprising amount of overlap in the OR side of things, but I'm shocked by how few IE grads can program their way out of a box. It's a shame, really.

CS already is the super-degree.

How so?

It qualifies you for an opinion on any subject.

A CS degree also qualifies you for on-the-job training in writing code, that odious task that your professors find trivial but somehow are also terrible at it.

We just don't have time. Incentives are elsewhere. Any time devoted to writing good code for a paper is time we cannot use to work on the next paper, (shudder) grant application, or a plethora of other things that we are either forced or incentivized to do.

I miss coding from when I was in a more junior stage of my career and could afford time for it, and I think my fellow professors mostly feel the same, I don't think many would dismiss it as trivial or odious.

I’m inferring “odious” from the priority that is applied to it. Maybe “irrelevant” is better?

But when those junior engineers hit my company, they can do homework problems and that’s about it. “CS fundamentals” aren’t useful when you can’t quit vi or debug a regex. They get to be useful 2-3 years later, after the engineer has shaken off being a student.

Operations Research is basically Industrial Engineering + Mathematical Optimization + programming familiarity. It's super useful.

I mean, it helped win WW2, so I think its utility is already demonstrated. :)

Thanks for the comment. I was thinking more about linear programming and related techniques that mostly came about after the war with Dantzig and when computers could be utilized (I know Kantorovich independently also developed the technique before the war). I went ahead and skimmed some articles on OR in WW2. Cool stuff. Thanks for expanding my knowledge.

> but I'm shocked by how few IE grads can program their way out of a box. It's a shame, really.

These days, you could replace the "IE" in your sentence by any of many, many disciplines and still be correct.

As much as mathematicians will hate to hear this, CS is a new and more tangible/practical way to do maths and should therefore hold a spot in a general education as central as maths has in the last few centuries.

I view mathematics (as in, proving theorems) as one of the professions that's most likely to succumb to automation. We like to think there's some mystical human intuition involved, but that's just us putting things the brain isn't all that good at on a high pedestal.

When I traded betting markets I was able to formulate a lot of multi-market arbitrage problems as ILP. The integer part turned out to be quite important as I recall, since you can generally only trade in whole cents.

ILP is NP-complete.

Yes? We do manage to solve ILP problems in practice quite nicely.

In fact, most NP problems that you come across in practice are relatively tractable for most practical instances.

Eg for the knapsack problem you have to actually work very hard to get a hard instance in the first place.

That's not correct.

First of all, you can't solve a neoclassical economy using LP, because equilibrium constraints can only be represented as complementarity constraints. You would have to give up on some aspects, like dynamic prices.

The linear complementarity problem in itself is NP hard. So you're screwed from the get go, because your problems are now LPCC problems. Good luck finding an LPCC solver. I can confirm that an open source QPCC solver exists though, which should be even slower.

Next is the fact that if you wanted to build a neoclassical economy model, only global optimization will do.

This means that you need to simulate every time step in one large LPCC model, instead of using a finite horizon. Due to the perfect information assumption, you must know about the state of every person on the planet. You're going to need millions of variables due to simple combinatorial explosion.

It's kind of startling how these assumptions, which are supposed to make analytical solutions tractable by the way, also make non-analytical solutions literal hell.

And before you say that prices can be determined iteratively, as I mentioned, you would run into the problem that future prices are unknown to you, so how are you going to plug them into the second time step? The very thing you want to calculate depends on it's future value.

Economics is a weird science, where experienced reality works much better than the theory.

Computational economics is a relatively new field where intelligent agents are used with lots of runs instead of general optimization solvers I believe. Pretty nifty. One of my colleagues publishes a good bit on it.

Wassily Leontief and his Nobel Prize would like to have a chat with your colleague.

Can you be more specific?

Huh? Are you replying to the wrong comment? I never made any claims about 'solving a neoclassical economy'.

I'm not quite sure who cares about solving a neoclassical economic model like that?

As you indirectly suggest, neoclassical assumption of the type you suggested are not computationally tractable. So the kind of computations real economic agents actually do are likely to be different. (Whether that flavour of neoclassical economics is still useful after taking this caveat into account, is a different question.)

In any case: yes, not all NP-hard or NP-complete problems are easy to solve in practice. Even worse, many problems widely believed to be neither NP-hard nor NP-complete, like factoring integers or computing discrete logarithms, are also hard for many practical instances. (And they have to be, if cryptography is supposed to work.)

It was a response to

> It's surprising how many problems can be formulated as linear optimization.

i.e., all problems in NP (which is most problems you're likely to encounter on a day-to-day basis) can be solved with ILP, and many of them can be solved or well-approximated quickly.

You are technically correct.

To interpret the observation a bit more meaningfully:

It's surprising how many problems can be formulated as continuous (!) linear optimisation.

And it is surprising how many problems can be formulated somewhat naturally as mixed-integer linear optimisation. And 'many of them can be solved or well-approximated quickly', exactly as you say.

---

I seem to remember that continuous linear optimisation is to P what integer linear optimisation is to NP. In the sense that there's some natural reduction of many problems in P to continuous linear optimisation.

(I don't remember if that's just an informal observation, or whether there's some formal way to reduce problems in P in eg linear time to linear optimisation? https://en.wikipedia.org/wiki/P-complete#P-complete_problems mentions Linear Optimisation as being P-complete, but I haven't vetted all the fine-print, eg about what specific reduction they are using.)

it's not. it's np-hard. the easiest proof is that the best known algorithm is greater than O(2^N)

0/1 ILP is NP-hard and the trivial algorithm takes O(2^N), and it's also in NP.

right, but tfa was about the general case where the fancy new algorithm is log(n)^n

Just because it is NP-hard in the worst-case doesn't mean it is not practical. As can be seen in the many theorems under which conditions the regular polynomial-time LP algorithm provides an integer solution.

Reply on news.ycombinator.com