6 ms·

Software engineers interested in ML/algorithms should learn about linear programming. It's surprising how many problems can be formulated as linear optimizatio

by ford 3y ago

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)

tylerhou 3y ago
ILP is NP-complete.
- eru 3y ago
  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.
  - imtringued 3y ago
    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.
    - 7thaccount 3y ago
      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.
      - keithalewis 3y ago
        Wassily Leontief and his Nobel Prize would like to have a chat with your colleague.
        7thaccount 3y ago
        Can you be more specific?
    - eru 3y ago
      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.)
  - tylerhou 3y ago
    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.
    - eru 3y ago
      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 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.)
- adgjlsfhk1 3y ago
  it's not. it's np-hard. the easiest proof is that the best known algorithm is greater than O(2^N)
  - tylerhou 3y ago
    0/1 ILP is NP-hard and the trivial algorithm takes O(2^N), and it's also in NP.
    - adgjlsfhk1 3y ago
      right, but tfa was about the general case where the fancy new algorithm is log(n)^n
- BlindEyeHalo 3y ago
  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.
mp05 3y ago
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.
- maxFlow 3y ago
  CS already is the super-degree.
  - fuzztester 3y ago
    How so?
    - axus 3y ago
      It qualifies you for an opinion on any subject.
      - shermantanktop 3y ago
        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.
        Al-Khwarizmi 3y ago
        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.
        shermantanktop 3y ago
PartiallyTyped 3y ago
One of my favourite courses in grad school was approximation algorithms and it involved reductions to LP. Lots of fun, can recommend.
- WJW 3y ago
  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.
  - tylerhou 3y ago
    https://people.seas.harvard.edu/~cs224/fall14/lec.html https://people.seas.harvard.edu/~cs224/fall14/lec.html In particular, seems like lectures 9-11 have LP content.
    - WJW 3y ago
      Thanks!
  - PartiallyTyped 3y ago
    We used the book "the design of approximation algorithms" https://www.designofapproxalgs.com/book.pdf https://www.designofapproxalgs.com/book.pdf
isaacfung 3y ago
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.
nojs 3y ago
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.

by ford 3y ago

tylerhou 3y ago

ILP is NP-complete.

eru 3y ago
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.
- imtringued 3y ago
  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.
  - 7thaccount 3y ago
    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.
    - keithalewis 3y ago
      Wassily Leontief and his Nobel Prize would like to have a chat with your colleague.
      - 7thaccount 3y ago
        Can you be more specific?
  - eru 3y ago
    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.)
- tylerhou 3y ago
  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.
  - eru 3y ago
    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 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.)
adgjlsfhk1 3y ago
it's not. it's np-hard. the easiest proof is that the best known algorithm is greater than O(2^N)
- tylerhou 3y ago
  0/1 ILP is NP-hard and the trivial algorithm takes O(2^N), and it's also in NP.
  - adgjlsfhk1 3y ago
    right, but tfa was about the general case where the fancy new algorithm is log(n)^n
BlindEyeHalo 3y ago
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.

mp05 3y ago

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.

maxFlow 3y ago
CS already is the super-degree.
- fuzztester 3y ago
  How so?
  - axus 3y ago
    It qualifies you for an opinion on any subject.
    - shermantanktop 3y ago
      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.
      - Al-Khwarizmi 3y ago
        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.
        shermantanktop 3y ago

PartiallyTyped 3y ago

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

WJW 3y ago
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.
- tylerhou 3y ago
  https://people.seas.harvard.edu/~cs224/fall14/lec.html https://people.seas.harvard.edu/~cs224/fall14/lec.html In particular, seems like lectures 9-11 have LP content.
  - WJW 3y ago
    Thanks!
- PartiallyTyped 3y ago
  We used the book "the design of approximation algorithms" https://www.designofapproxalgs.com/book.pdf https://www.designofapproxalgs.com/book.pdf

isaacfung 3y ago

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.

nojs 3y ago

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.