3 ms·

People really need to come up with better names. "Linear Programming" or "Integer Linear Programming" mean absolutely nothing. Also anything dealing with findi

People really need to come up with better names. "Linear Programming" or "Integer Linear Programming" mean absolutely nothing. Also anything dealing with finding the minimum distance distances can be short circuited by keeping the shortest distance and not taking paths that exceed that. This is how approximate nearest neighbor works and can still speed up the full solution. Figuring out full paths that have short average distances first can also get to shorter distances sooner. You can also cluster points knowing you probably don't want to jump from one cluster to another multiple times.

ford 3y ago
This made me wonder why it's called programming (since clearly it's not the sense of the word programming most HN'ers are used to). https://en.wikipedia.org/wiki/Mathematical_optimization#History https://en.wikipedia.org/wiki/Mathematical_optimization#Hist...
- dang 3y ago
  From that link: Programming in this context does not refer to computer programming, but comes from the use of program by the United States military to refer to proposed training and logistics schedules, which were the problems Dantzig studied at that time Is that also true of 'dynamic programming'?
  - mturmon 3y ago
    If you don’t know, you are in for a treat. Here is Bellman’s own description of how he came up with the term “dynamic programming “ — I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, ‘Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities (Autobiography, p. 159). See: https://pubsonline.informs.org/doi/pdf/10.1287/opre.50.1.48.17791 https://pubsonline.informs.org/doi/pdf/10.1287/opre.50.1.48.... People up-thread have been getting cranky about the use of “programming “ in this sense. Now of course, “programming“ for optimization has been well-entrenched since the 1970s at least. But perhaps Bellman’s story does give some cover to those who feel the word “programming“ has been wrongly appropriated?
    - dang 3y ago
      Oh gosh—I was vastly out of the loop: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=%22We%20had%20a%20very%20interesting%20gentleman%20in%20Washington%22&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... Thanks! That's a classic for sure.
      - mturmon 3y ago
        Not least, for the delightful characterization of that versatile word, "dynamic"!
cmrx64 3y ago
take "programming" to mean "scheduling" and the ancient crusty term acquires some meaning.
kevindamm 3y ago
absolutely nothing? you mean other than the relationship with linear systems and linear algebra?
deleted 3y ago
[deleted]
eru 3y ago
Linear programming solvers use lots of heuristics (not entirely unlike the ones you sketched) internally. The important thing to keep in mind is that their heuristic only speed up the amount of time spent finding the optimal solution. But you still get a prove at the end, that they actually found the optimal solution. (Or if you stop earlier, you get a provable upper bound estimate of how far you are away at worst from the optimal solution.) Heuristics like the ones you sketched don't (easily) give you those estimates.
muldvarp 3y ago
> Also anything dealing with finding the minimum distance distances can be short circuited by keeping the shortest distance and not taking paths that exceed that. That's the "bound" part of "branch-and-bound", so MILP-solvers already do this. > You can also cluster points knowing you probably don't want to jump from one cluster to another multiple times. You can incorporate heuristics into the branch-and-bound algorithm, but the goal of MILP-solvers is generally to produce an optimal solution (or at least a solution that is _provably_ within x% of optimality). If you don't care about optimality and just want a solution that's good enough, I would implement the Christofides–Serdyukov algorithm.

ford 3y ago

This made me wonder why it's called programming (since clearly it's not the sense of the word programming most HN'ers are used to). https://en.wikipedia.org/wiki/Mathematical_optimization#History https://en.wikipedia.org/wiki/Mathematical_optimization#Hist...

dang 3y ago
From that link: Programming in this context does not refer to computer programming, but comes from the use of program by the United States military to refer to proposed training and logistics schedules, which were the problems Dantzig studied at that time Is that also true of 'dynamic programming'?
- mturmon 3y ago
  If you don’t know, you are in for a treat. Here is Bellman’s own description of how he came up with the term “dynamic programming “ — I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, ‘Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities (Autobiography, p. 159). See: https://pubsonline.informs.org/doi/pdf/10.1287/opre.50.1.48.17791 https://pubsonline.informs.org/doi/pdf/10.1287/opre.50.1.48.... People up-thread have been getting cranky about the use of “programming “ in this sense. Now of course, “programming“ for optimization has been well-entrenched since the 1970s at least. But perhaps Bellman’s story does give some cover to those who feel the word “programming“ has been wrongly appropriated?
  - dang 3y ago
    Oh gosh—I was vastly out of the loop: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=%22We%20had%20a%20very%20interesting%20gentleman%20in%20Washington%22&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... Thanks! That's a classic for sure.
    - mturmon 3y ago
      Not least, for the delightful characterization of that versatile word, "dynamic"!

cmrx64 3y ago

take "programming" to mean "scheduling" and the ancient crusty term acquires some meaning.

kevindamm 3y ago

absolutely nothing? you mean other than the relationship with linear systems and linear algebra?

deleted 3y ago

[deleted]

eru 3y ago

Linear programming solvers use lots of heuristics (not entirely unlike the ones you sketched) internally. The important thing to keep in mind is that their heuristic only speed up the amount of time spent finding the optimal solution. But you still get a prove at the end, that they actually found the optimal solution. (Or if you stop earlier, you get a provable upper bound estimate of how far you are away at worst from the optimal solution.) Heuristics like the ones you sketched don't (easily) give you those estimates.

muldvarp 3y ago

> Also anything dealing with finding the minimum distance distances can be short circuited by keeping the shortest distance and not taking paths that exceed that. That's the "bound" part of "branch-and-bound", so MILP-solvers already do this. > You can also cluster points knowing you probably don't want to jump from one cluster to another multiple times. You can incorporate heuristics into the branch-and-bound algorithm, but the goal of MILP-solvers is generally to produce an optimal solution (or at least a solution that is _provably_ within x% of optimality). If you don't care about optimality and just want a solution that's good enough, I would implement the Christofides–Serdyukov algorithm.