3 ms·

For what it's worth, my experience thus far has been quite different: - I agree that operations research has a brand problem, but the problem is that nobody re

For what it's worth, my experience thus far has been quite different: - I agree that operations research has a brand problem, but the problem is that nobody recognizes the name. Every week I have this conversation: "What do you do?" "I'm a PhD student in operations research at MIT." [blank look] "Have you heard of OR? I wouldn't blame you; most people haven't." "No, what is it?" "It's something of a mix between computer science, applied math, and statistics, and in particular we do a lot of optimization work." "Wow, that's really useful!" So no, we don't have the brand of computer science, but I get a uniformly positive reception when I describe what I do. From technical people there's a fair amount of "Oh! I have this optimization problem in my work, do you think..." - People graduating from MIT operations research seem to have 100% success in finding good jobs, both in academia and industry. I think we'll be surprised to learn that finding good jobs is tough. Yes, we all benefit tremendously from the name MIT, no doubt. Nonetheless, if everyone graduating from my program has an excellent offer lined up by the time they cross the stage...that doesn't suggest a congested market with few opportunities. - Yes, integer programming is Hard in the technical sense. However, with overwhelmingly high probability, the problem you actually care about is not hard at all. Write down the first formulation that comes to mind, throw it at Gurobi or CPLEX, go for a coffee, and when you come back you'll have an answer with tiny optimality gap, perhaps certifiably optimal. Integer programming in particular is one of the great academic success stories; the combined speedup of hardware and algorithms in the last ~30 years has made IP solvers ~10e9 faster. ___ You write as someone who has personal experience and knows what they're talking about, so perhaps I should update my priors. But suffice to say I think OR and its practitioners are in a fantastic spot right now.

graycat 10y ago
MIT? Yup, D. Bertsekas! And his student S. Shreve! And, of course, T. Magnanti! Right: Magnanti gave a Goldman lecture at Johns Hopkins on design of internet networks. Sure, it was network design at Bell Labs that got Garey and Johnson at Bell Labs to write that first, important book on NP-completeness. At about the time of Magnanti's lecture, I was also looking into the same problem, especially for the core of the Internet with multi-protocol label switching, border gateway protocol, etc. I couldn't get any VCs interested in funding me (since then I learned more about what VCs want -- not a problem posed in a lecture by the Dean of Science at MIT and attacked by a Ph.D. in optimization). So, soon I heard of a venture funded startup doing network design and sent them a resume. They flew me down. The CEO met me at the door; I hadn't looked up his name; that was a fatal social flub; and he refused his interview slot with me. But, some of his venture funders were there, very concerned, nicer to me, liked that I'd been the first Director of Operations Research at FedEx and with my work on scheduling the fleet had saved the company -- literally. The CEO of that startup had been an IBM executive, and I'd been at the IBM Watson lab. Mostly the team I was on worked in AI, but I worked also in some mathematical statistics and some optimization. My optimization work knocked off an old problem in the Kuhn-Tucker conditions and solved a problem stated but not solved in the famous Arrow, Hurwicz, Uzawa paper in mathematical economics. My statistic paper was quite different. It was that CEO's error: Since I was also from IBM, apparently he expected me to have a good IBM style executive handshake. Sorry 'bout that. His company was in deep trouble; no doubt that is why his VCs were right there. Solving integer linear programming problems was just crucial for his business, essentially as in Magnanti's lecture. Their head applied mathematician had just left to return to his university slot. Again, the CEO was in deep, smelly, sticky stuff. I met with their team. What they really cared about were software object oriented inheritance hierarchies. Gads. Next to irrelevant for solving the integer programming problems, but okay by me -- I'd be glad to write in C++ and their hierarchy if they wanted. Then we got to optimization: I said that my most recent work was on a commercial problem in marketing resource allocation where I found a feasible solution to a 0-1 integer linear programming problem with 40,000 constraints and 600,000 variables in 905 seconds on a 90 MHz PC. From the primal-dual bounding, my feasible solution was within 0.025% of optimality. That work should be a good initial qualification! Alas, they had heard that 0-1 integer linear programming was in NP-complete, thus believed that only small, trivial problems could be attacked (a serious mistake that is far too common), and concluded that I was lying! Gads. Well, they told me about their approach -- enumeration. They confessed that it was running too long, for days. Gads. In a back room they had a high end PC and a copy of C-PLEX, but they were not touching it. I didn't get an offer, and soon the startup went out of business. Sorry, guys. Looks like Darwin was on he case. That experience was a good example of the cultural, social, or professional problem: The CEO was in a business that desperately depended on getting good results from integer linear programming. But the CEO was a traditional, blue suit, white shirt, polished shoes, strong handshake, no nonsense, tough, results-oriented manager, focused on the bottom line, ... who however didn't know the first thing about optimization or how to hire a team that did and didn't recognize a good optimization guy when one walked in the door. And I didn't come in with enough professional status, say, like that of a lawyer advising on an IPO or some such, for him to swallow his pride in knowing everything and take me seriously. Actually, that problem of 40,000 constraints, etc. was another example: I'd found some guys who had some customers high in banking and had talked the customers into letting these guys attack problems in optimization, or anything else they could get paid to work on. Well, the bank had a resource allocation optimization problem. Well the head guy was a salesman type, but he had a technical guy he liked. The technical guy knew next to nothing about optimization but had heard about simulated annealing. And, maybe to his credit, he did formulate the banking problem as the 0-1 integer linear programming (ILP) problem I mentioned. So, I met those two guys over coffee, and they sent me e-mail with the 0-1 ILP formulation. I looked at the formulation, derived some non-linear duality for essentially Lagrangian relaxation, considered several approaches, knew that since the primal problem was a minimization, the dual problem was a maximization of a concave function that could be approximated with supporting hyper planes. The dual problem was in 16 dimensions, that is, there were 16 Lagrange multipliers. In this case, given values of the Lagrange multipliers, the primal problem was just trivial to solve exactly, just with a page or so of simple code for some simple arithmetic. So, all that was left was to maximize the concave dual problem in 16 variables. So, I wrote them back that I thought I saw a path. So, I wrote the code and for the linear programming part for the concave maximization called the IBM Optimization Subroutine Library (OSL), went through 500 primal-dual iterations, and found the feasible solution within 0.025% of optimality. So, after two weeks, I sent them e-mail on my success. They went silent. There had been hints: The technical guy had been trying simulated annealing, running for days, and stopping when he gave up, of course, maybe without being feasible and certainly with no indication of how close he was to optimality. He didn't like me and was pinging on his CEO buddy to keep me away from the work. So, from my distant view of the political situation through a glass darkly, my work, 905 seconds and 0.025%, just totally pissed off and humiliated the technical guy, let the CEO know that he'd picked an incompetent for his lead technical guy, didn't want to admit his need for me, and just gave up. So, again, as lawyers have learned: A working professional technical specialist should report only to a person with such qualifications and never to a generalist line manager. That is, the CEO guy needed a professional that he could respect for his professionalism, and he was not yet ready to do that with me. Really, in real business, darned few generalist middle managers want to have to manage someone doing important technical work the manager does not understand. It's almost like, if he had a heart attack, he'd rather go to a nurse than a high end cardiologist. The key is, the cardiologist has a lot of professional status. There was another case similar to the banking thingy: Some guys were selling to some companies with a big sales force and wanted to use optimization to get better sales results. They had a problem formulation that was a good start. So, they hired me, and soon I found that the 0-1 ILP really was a case of min cost network flows. I typed up the math using TeX and sent them a nice paper. So, I reviewed W. Cunningham's paper on strongly feasible basic solutions and started writing code. Again the CEO guy had a jealous technical guy who knew next to nothing about optimization and talked the CEO guy out letting me finish the code. I got fired. And, there are other examples. I gave up -- tough to sell optimization in business. The business guys would rather do without optimization, even if it puts them out of business. That is, the CEO guys want to do it their way or the way of some not very good technical guy they have a personal relationship with or not at all. Net, the people I knew just didn't much care for optimization. They didn't want it. Maybe now some people do want some optimization. Maybe. Yup, I can believe that Bixby's latest software is terrific. Last I heard, he was working with Ellis Johnson and George Nemhauser and/or some of their students at Georgia Tech. Of course, Johnson helped get the OSL going and did some good things with it at American Airlines. Gee, maybe I'll send another 1000 resumes on applied optimization, stochastic processes, statistics! Maybe.

graycat 10y ago

MIT? Yup, D. Bertsekas! And his student S. Shreve! And, of course, T. Magnanti! Right: Magnanti gave a Goldman lecture at Johns Hopkins on design of internet networks. Sure, it was network design at Bell Labs that got Garey and Johnson at Bell Labs to write that first, important book on NP-completeness. At about the time of Magnanti's lecture, I was also looking into the same problem, especially for the core of the Internet with multi-protocol label switching, border gateway protocol, etc. I couldn't get any VCs interested in funding me (since then I learned more about what VCs want -- not a problem posed in a lecture by the Dean of Science at MIT and attacked by a Ph.D. in optimization). So, soon I heard of a venture funded startup doing network design and sent them a resume. They flew me down. The CEO met me at the door; I hadn't looked up his name; that was a fatal social flub; and he refused his interview slot with me. But, some of his venture funders were there, very concerned, nicer to me, liked that I'd been the first Director of Operations Research at FedEx and with my work on scheduling the fleet had saved the company -- literally. The CEO of that startup had been an IBM executive, and I'd been at the IBM Watson lab. Mostly the team I was on worked in AI, but I worked also in some mathematical statistics and some optimization. My optimization work knocked off an old problem in the Kuhn-Tucker conditions and solved a problem stated but not solved in the famous Arrow, Hurwicz, Uzawa paper in mathematical economics. My statistic paper was quite different. It was that CEO's error: Since I was also from IBM, apparently he expected me to have a good IBM style executive handshake. Sorry 'bout that. His company was in deep trouble; no doubt that is why his VCs were right there. Solving integer linear programming problems was just crucial for his business, essentially as in Magnanti's lecture. Their head applied mathematician had just left to return to his university slot. Again, the CEO was in deep, smelly, sticky stuff. I met with their team. What they really cared about were software object oriented inheritance hierarchies. Gads. Next to irrelevant for solving the integer programming problems, but okay by me -- I'd be glad to write in C++ and their hierarchy if they wanted. Then we got to optimization: I said that my most recent work was on a commercial problem in marketing resource allocation where I found a feasible solution to a 0-1 integer linear programming problem with 40,000 constraints and 600,000 variables in 905 seconds on a 90 MHz PC. From the primal-dual bounding, my feasible solution was within 0.025% of optimality. That work should be a good initial qualification! Alas, they had heard that 0-1 integer linear programming was in NP-complete, thus believed that only small, trivial problems could be attacked (a serious mistake that is far too common), and concluded that I was lying! Gads. Well, they told me about their approach -- enumeration. They confessed that it was running too long, for days. Gads. In a back room they had a high end PC and a copy of C-PLEX, but they were not touching it. I didn't get an offer, and soon the startup went out of business. Sorry, guys. Looks like Darwin was on he case. That experience was a good example of the cultural, social, or professional problem: The CEO was in a business that desperately depended on getting good results from integer linear programming. But the CEO was a traditional, blue suit, white shirt, polished shoes, strong handshake, no nonsense, tough, results-oriented manager, focused on the bottom line, ... who however didn't know the first thing about optimization or how to hire a team that did and didn't recognize a good optimization guy when one walked in the door. And I didn't come in with enough professional status, say, like that of a lawyer advising on an IPO or some such, for him to swallow his pride in knowing everything and take me seriously. Actually, that problem of 40,000 constraints, etc. was another example: I'd found some guys who had some customers high in banking and had talked the customers into letting these guys attack problems in optimization, or anything else they could get paid to work on. Well, the bank had a resource allocation optimization problem. Well the head guy was a salesman type, but he had a technical guy he liked. The technical guy knew next to nothing about optimization but had heard about simulated annealing. And, maybe to his credit, he did formulate the banking problem as the 0-1 integer linear programming (ILP) problem I mentioned. So, I met those two guys over coffee, and they sent me e-mail with the 0-1 ILP formulation. I looked at the formulation, derived some non-linear duality for essentially Lagrangian relaxation, considered several approaches, knew that since the primal problem was a minimization, the dual problem was a maximization of a concave function that could be approximated with supporting hyper planes. The dual problem was in 16 dimensions, that is, there were 16 Lagrange multipliers. In this case, given values of the Lagrange multipliers, the primal problem was just trivial to solve exactly, just with a page or so of simple code for some simple arithmetic. So, all that was left was to maximize the concave dual problem in 16 variables. So, I wrote them back that I thought I saw a path. So, I wrote the code and for the linear programming part for the concave maximization called the IBM Optimization Subroutine Library (OSL), went through 500 primal-dual iterations, and found the feasible solution within 0.025% of optimality. So, after two weeks, I sent them e-mail on my success. They went silent. There had been hints: The technical guy had been trying simulated annealing, running for days, and stopping when he gave up, of course, maybe without being feasible and certainly with no indication of how close he was to optimality. He didn't like me and was pinging on his CEO buddy to keep me away from the work. So, from my distant view of the political situation through a glass darkly, my work, 905 seconds and 0.025%, just totally pissed off and humiliated the technical guy, let the CEO know that he'd picked an incompetent for his lead technical guy, didn't want to admit his need for me, and just gave up. So, again, as lawyers have learned: A working professional technical specialist should report only to a person with such qualifications and never to a generalist line manager. That is, the CEO guy needed a professional that he could respect for his professionalism, and he was not yet ready to do that with me. Really, in real business, darned few generalist middle managers want to have to manage someone doing important technical work the manager does not understand. It's almost like, if he had a heart attack, he'd rather go to a nurse than a high end cardiologist. The key is, the cardiologist has a lot of professional status. There was another case similar to the banking thingy: Some guys were selling to some companies with a big sales force and wanted to use optimization to get better sales results. They had a problem formulation that was a good start. So, they hired me, and soon I found that the 0-1 ILP really was a case of min cost network flows. I typed up the math using TeX and sent them a nice paper. So, I reviewed W. Cunningham's paper on strongly feasible basic solutions and started writing code. Again the CEO guy had a jealous technical guy who knew next to nothing about optimization and talked the CEO guy out letting me finish the code. I got fired. And, there are other examples. I gave up -- tough to sell optimization in business. The business guys would rather do without optimization, even if it puts them out of business. That is, the CEO guys want to do it their way or the way of some not very good technical guy they have a personal relationship with or not at all. Net, the people I knew just didn't much care for optimization. They didn't want it. Maybe now some people do want some optimization. Maybe. Yup, I can believe that Bixby's latest software is terrific. Last I heard, he was working with Ellis Johnson and George Nemhauser and/or some of their students at Georgia Tech. Of course, Johnson helped get the OSL going and did some good things with it at American Airlines. Gee, maybe I'll send another 1000 resumes on applied optimization, stochastic processes, statistics! Maybe.