4 ms·

WOW! There is still some interest in optimization? I'm shocked! The message long was "Operations Research is dead." Gee, I got started in OR (operations res

WOW! There is still some interest in optimization? I'm shocked! The message long was "Operations Research is dead." Gee, I got started in OR (operations research) at FedEx, covered a lot from some of the best people in grad school, taught it as a prof in B-school, and applied it to US national security and some commercial problems. Good to see the interest in some of the flight operations work for Lufthansa -- I was considering (no great progress) some of those problems at FedEx! One commercial problem was allocating marketing resources for some banks. I was given the formulation, 0-1 integer linear programming with 600,000 variables and 40,000 constraints. I derived some non-linear duality theory, used the IBM OSL (Optimization Subroutine Library), and in 500 iterations found a feasible solution with the objective function guaranteed to be within 0.025% of optimality! Another commercial problem was some more marketing optimization. It was also 0-1 integer linear programming, but surprisingly it was just a problem in least cost network flows. That is also linear programming, but there the simplex algorithm takes on a special form where a basis is a spanning tree of arcs in the network. A simplex pivot is to add an arc to the tree, thus, yielding a circuit, and running flow around the circuit in the direction that saves money and removing from the circuit, thus, making a tree again, one of the first arcs where the flow goes to zero. There is a cute variation of the algorithm due to W. Cunningham (one of my profs) based on his strongly feasible basis, that avoids cycling. A super nice point about the simplex problem on least cost network flows is if all the arc capacities are whole numbers and if start with an integer basic feasible solution, then the simplex algorithm will automatically maintain an integer basic feasible solution and terminate with an integer solution. It is good to suspect that a lot of integer linear programming problems are actually just such network flow problems or nearly so. Once I used that stuff to say, for NASA, how to assign signals to satellite channels to minimize some signal interference -- it was an example of the bottleneck assignment problem which should be solvable very quickly by some post optimality tweaking with the network simplex algorithm. I enjoyed using the IBM OSL, but IBM withdrew it from marketing in about 2003, maybe in favor of marketing C-PLEX. But it appears that at about 2004 IBM donated the source of the OSL (with lots of pieces, network flow, stochastic programming, etc.) to Riverware which might distribute the open source. I got started with the OSL when I was in an AI group at IBM's Watson lab where the OSL was written. The Watson lab long had some high expertise in optimization -- Gomory (cutting planes, Gilmore-Gomory column generation, etc.) was head of the lab; there was Phil Wolfe (the Wolfe dual, etc.), Ellis Johnson (group theory and integer programming), etc. So, in particular, if still want to do some OR and optimization, get some quite well written software, and save some money, then might look into getting all the IBM OSL code open source.

tgflynn 7y ago
> The message long was "Operations Research is dead." Could you elaborate on why that was perceived to be the case ? It seems like the number of applications is very large and I suspect the technology is under-exploited outside of very large organizations.
- graycat 7y ago
  Of course optimization went back at least to Newton and his work to find the shape of a frictionless wire that would let a bead slide down in least time. That problem was a seed for the field of calculus of variations and later deterministic optimal control. But the optimization of operations research was different, e.g., less central use of calculus: Some of the surprising history is in a book review at https://www.jstor.org/stable/2975180?seq=1#page_scan_tab_contents https://www.jstor.org/stable/2975180?seq=1#page_scan_tab_con... And that is not really the beginnings of such things since there was the Kantorovich work on the cutting stock problem. In that book review will see that linear programming (LP) had a launch as a big splash. Broadly it appeared that LP was so close to so many important practical problems -- military, commercial, maybe more -- that it was bound to become a big thing for a long time. And, can check, IIRC several Nobel prizes in Economics were given for LP and more topics in optimization applied to economics. And there are connections with two sided optimization, i.e., the theory of two person games (e.g., paper, scissors, rock) since the basic saddle point result, IIRC first proved by von Neumann, follows easily from the duality part of basic theory of LP. So, again LP looked good. Can't leave out the Hugh Everett work: He had a company around DC working on military problems -- best allocation of resources. Everett's theorem is a cute version of Lagrange multipliers and supposedly the foundation of his Lambda Corporation. Yes, that Everett, physics student of J. Wheeler where Everett worked up the many worlds interpretation of quantum mechanics. Operations research had a more general big push during WWII, e.g., with some of the work of F. Dyson. So, by the 1950s, it looked like operations research (OR) and its tools of optimization, especially LP, were to be big things. Problems: (1) Real Problems. What real problems were to be solved? Too commonly the problems were not really linear or were linear but linear integer (which led to the question of P versus NP). (2) Data. Too often it was a struggle to get the needed real data. (3) Software. The IBM OSL I mentioned was good software, and so are C-PLEX, Gurobi, and more, but in the 1950s the software situation was grim. (4) Computing. The 1950s computers, e.g., the IBM 709, were clumsy to use, slow, and expensive. Then (1)-(4) too easily resulted in projects with not so good fits with reality, over budget, and later than promised. Reputation fell. Another problem, no surprise, was that the real business problem commonly evolved faster than the optimization software could keep up. But for selected and sufficiently valuable applications, e.g., running an oil refinery, by 1970 LP could be a big money maker. There were claims that companies that mixed animal feed did well with LP in, say, the 1970s or so. In the 1980s the situation on LP software and computing was good enough to permit some better -- project time and budget -- results on real problems. By the 1980s, B-school accreditation called for a course in LP. So, a lot of B-school students got a good introduction to LP. But there was very little down to essentially no instruction to turn out well skilled professionals in OR or LP. The college profs concentrated on publishing papers, e.g., about P versus NP, and were discouraged from working on real, non-academic problems from outside academics, i.e., were not like MDs in medical teaching/research hospitals who were also clinical and professional. So, the OR/LP workers who were available still needed some years of hands on experience to become competent professionals for important practical applications. The standard attitude in the C-suites was a special case of C-suite attitudes more generally -- don't spend money on chancy, risky stuff. Instead, if there is to be a development project, then time, budget, good ROI, etc. needed to be reliable. So, in the C-suites, LP and OR got reputations as "dead fields", flops. Or maybe no middle manager ever got fired declining to pursue an OR/LP project. Neither the C-suite nor a middle manager wanted to have their career at risk from an OR/LP project they didn't understand. The problem of P versus NP also hurt: Or, the dream was that in business we should need only to formulate an optimization problem, type that into some software to get the problem ready for some solver software, and then have the solver produce an optimal solution quickly and reliably. Well, with the P versus NP issue, we saw that at least for now such a solver was asking for too much. [My experience was that it was usually necessary and effective to take the problems one by one and exploit special structure.] Giving up that way was mostly a mistake: If the real business problem is a $100 million project, an optimal solution might save $15 million, the problem is a case of NP-complete so that saving all the $15 million to the last penny, guaranteed, in reasonable time, is also in this particular case (not necessarily the worst case of the P versus NP issue) not reasonable but saving $14 million is reasonable, then still commonly people regarded the challenge of P versus NP and showing that anything about optimization for the real problem was unreasonable and would also believe that the challenge of P versus NP meant that the $14 million was also beyond hope. People just gave up. But in broad terms from 100,000 feet up, the original observation that business needs optimization was correct then and still, now. For such problems, a lot of what has long been known in LP and optimization more generally is uniquely powerful, relevant stuff. So, there's money to be saved. The main question is, do C-suites want to fund the relevant projects? My guess is that the C-suites and middle managers have not changed much and, no, rarely want to fund the relevant projects.

tgflynn 7y ago

> The message long was "Operations Research is dead." Could you elaborate on why that was perceived to be the case ? It seems like the number of applications is very large and I suspect the technology is under-exploited outside of very large organizations.

graycat 7y ago
Of course optimization went back at least to Newton and his work to find the shape of a frictionless wire that would let a bead slide down in least time. That problem was a seed for the field of calculus of variations and later deterministic optimal control. But the optimization of operations research was different, e.g., less central use of calculus: Some of the surprising history is in a book review at https://www.jstor.org/stable/2975180?seq=1#page_scan_tab_contents https://www.jstor.org/stable/2975180?seq=1#page_scan_tab_con... And that is not really the beginnings of such things since there was the Kantorovich work on the cutting stock problem. In that book review will see that linear programming (LP) had a launch as a big splash. Broadly it appeared that LP was so close to so many important practical problems -- military, commercial, maybe more -- that it was bound to become a big thing for a long time. And, can check, IIRC several Nobel prizes in Economics were given for LP and more topics in optimization applied to economics. And there are connections with two sided optimization, i.e., the theory of two person games (e.g., paper, scissors, rock) since the basic saddle point result, IIRC first proved by von Neumann, follows easily from the duality part of basic theory of LP. So, again LP looked good. Can't leave out the Hugh Everett work: He had a company around DC working on military problems -- best allocation of resources. Everett's theorem is a cute version of Lagrange multipliers and supposedly the foundation of his Lambda Corporation. Yes, that Everett, physics student of J. Wheeler where Everett worked up the many worlds interpretation of quantum mechanics. Operations research had a more general big push during WWII, e.g., with some of the work of F. Dyson. So, by the 1950s, it looked like operations research (OR) and its tools of optimization, especially LP, were to be big things. Problems: (1) Real Problems. What real problems were to be solved? Too commonly the problems were not really linear or were linear but linear integer (which led to the question of P versus NP). (2) Data. Too often it was a struggle to get the needed real data. (3) Software. The IBM OSL I mentioned was good software, and so are C-PLEX, Gurobi, and more, but in the 1950s the software situation was grim. (4) Computing. The 1950s computers, e.g., the IBM 709, were clumsy to use, slow, and expensive. Then (1)-(4) too easily resulted in projects with not so good fits with reality, over budget, and later than promised. Reputation fell. Another problem, no surprise, was that the real business problem commonly evolved faster than the optimization software could keep up. But for selected and sufficiently valuable applications, e.g., running an oil refinery, by 1970 LP could be a big money maker. There were claims that companies that mixed animal feed did well with LP in, say, the 1970s or so. In the 1980s the situation on LP software and computing was good enough to permit some better -- project time and budget -- results on real problems. By the 1980s, B-school accreditation called for a course in LP. So, a lot of B-school students got a good introduction to LP. But there was very little down to essentially no instruction to turn out well skilled professionals in OR or LP. The college profs concentrated on publishing papers, e.g., about P versus NP, and were discouraged from working on real, non-academic problems from outside academics, i.e., were not like MDs in medical teaching/research hospitals who were also clinical and professional. So, the OR/LP workers who were available still needed some years of hands on experience to become competent professionals for important practical applications. The standard attitude in the C-suites was a special case of C-suite attitudes more generally -- don't spend money on chancy, risky stuff. Instead, if there is to be a development project, then time, budget, good ROI, etc. needed to be reliable. So, in the C-suites, LP and OR got reputations as "dead fields", flops. Or maybe no middle manager ever got fired declining to pursue an OR/LP project. Neither the C-suite nor a middle manager wanted to have their career at risk from an OR/LP project they didn't understand. The problem of P versus NP also hurt: Or, the dream was that in business we should need only to formulate an optimization problem, type that into some software to get the problem ready for some solver software, and then have the solver produce an optimal solution quickly and reliably. Well, with the P versus NP issue, we saw that at least for now such a solver was asking for too much. [My experience was that it was usually necessary and effective to take the problems one by one and exploit special structure.] Giving up that way was mostly a mistake: If the real business problem is a $100 million project, an optimal solution might save $15 million, the problem is a case of NP-complete so that saving all the $15 million to the last penny, guaranteed, in reasonable time, is also in this particular case (not necessarily the worst case of the P versus NP issue) not reasonable but saving $14 million is reasonable, then still commonly people regarded the challenge of P versus NP and showing that anything about optimization for the real problem was unreasonable and would also believe that the challenge of P versus NP meant that the $14 million was also beyond hope. People just gave up. But in broad terms from 100,000 feet up, the original observation that business needs optimization was correct then and still, now. For such problems, a lot of what has long been known in LP and optimization more generally is uniquely powerful, relevant stuff. So, there's money to be saved. The main question is, do C-suites want to fund the relevant projects? My guess is that the C-suites and middle managers have not changed much and, no, rarely want to fund the relevant projects.