Curious. Interesting. BUT: In some very important, practical ways, the whole question, issue, etc. of
P vs NP
amounts to a lot less than meets the eye.
In the history, much of the start was from (with TeX markup)
Michael R.\ Garey and
David S.\ Johnson,
{\it Computers and Intractability:\ \
A Guide to the Theory of NP-Completeness,\/}
ISBN 0-7167-1045-5,
W.\ H.\ Freeman,
San Francisco,
1979.\ \
So, AT&T needed to grow their
networks, and there were in principle some astronomically large number of combinations of equipment deployments that differed in cost. Somehow Bell Labs got involved, and the book was one result.
Early in the book is a cartoon that summarized the situation: Bell Labs admitted that they couldn't find the best, least cost, optimal design but neither could a long line of other researchers.
So, the strong suggestion was that there was a serious problem that no one knew how to solve.
About then I was at FedEx and working on how to schedule the fleet. I'd written some software that was easy to use to produce schedules, and one evening a VP and I used the software to produce a schedule for the whole envisioned fleet. The BoD was pleased, doubts were set aside, and crucial equity funding was enabled. It's fair to say that my software saved the company.
Then I continued to investigate the problem of fleet scheduling. I visited Cornell, MIT, Brown, Johns Hopkins. At Brown, I had lunch with two mathematicians. One of these two was famous, asked what I was doing, and hearing about fleet scheduling responded
"The traveling salesman problem"
and dismissed my efforts as hopeless.
I was surprised: I didn't find the problem as hopeless and, indeed, had already done well enough to save the company.
I learned more and more and eventually quite a lot. In a certain, narrow, curious, interesting sense, the mathematician at Brown was correct. In all overwhelmingly important practical respects -- we're talking $ millions a year at the time and later maybe 10s of $ millions a year -- he was badly wrong.
To be simple and clear, what was hopeless was getting optimal schedules that saved all the money possible, down, literally, to the last tiny fraction of the last penny of operating cost, in worst cases. Saving the $ millions or 10s of $ millions, essentially always in practice, down to maybe the last $1000 or so, entirely doable with reasonable effort.
So, in my university visits and various investigations, the founder, COB, CEO of FedEx wrote a memo appointing me head of a project I had proposed to apply 0-1 integer linear programming set covering to the problem of fleet scheduling.
How to do that:
(1) Generate a lot, likely all reasonable, single airplane tours from the Memphis hub and back. Keep only tours that don't violate lots of really obscure, often non-linear, ..., constraints. For each such tour, do the cost arithmetic to find the expected cost.
(2) Set up a 0-1 integer linear programming problem with one row for each city to be served and one column and one variable for each tour. The costs are just the tour costs. The right side is just a column of 1s. The constraints are all equalities.
(3) Tweak the simplex algorithm to get a feasible, nearly optimal solution. Can use some simple bounding math to confirm that are optimal or nearly so.
Smile from the $ millions a year saved. In practice, can work fine nearly always.
The question of
P vs NP?
Get to ignore it.
The research questions in computational complexity remain curious, interesting, challenging, and likely important. But for the immediate, practical problems of combinatorial optimization in practice, where we care a lot about the $ millions saved and hardly care at all about the possibility of $1000 not saved, we don't have to wait on the research and, instead, often or usually can do well now.
P vs NP
amounts to a lot less than meets the eye.
In the history, much of the start was from (with TeX markup)
Michael R.\ Garey and David S.\ Johnson, {\it Computers and Intractability:\ \ A Guide to the Theory of NP-Completeness,\/} ISBN 0-7167-1045-5, W.\ H.\ Freeman, San Francisco, 1979.\ \
So, AT&T needed to grow their networks, and there were in principle some astronomically large number of combinations of equipment deployments that differed in cost. Somehow Bell Labs got involved, and the book was one result.
Early in the book is a cartoon that summarized the situation: Bell Labs admitted that they couldn't find the best, least cost, optimal design but neither could a long line of other researchers.
So, the strong suggestion was that there was a serious problem that no one knew how to solve.
About then I was at FedEx and working on how to schedule the fleet. I'd written some software that was easy to use to produce schedules, and one evening a VP and I used the software to produce a schedule for the whole envisioned fleet. The BoD was pleased, doubts were set aside, and crucial equity funding was enabled. It's fair to say that my software saved the company.
Then I continued to investigate the problem of fleet scheduling. I visited Cornell, MIT, Brown, Johns Hopkins. At Brown, I had lunch with two mathematicians. One of these two was famous, asked what I was doing, and hearing about fleet scheduling responded
"The traveling salesman problem"
and dismissed my efforts as hopeless.
I was surprised: I didn't find the problem as hopeless and, indeed, had already done well enough to save the company.
I learned more and more and eventually quite a lot. In a certain, narrow, curious, interesting sense, the mathematician at Brown was correct. In all overwhelmingly important practical respects -- we're talking $ millions a year at the time and later maybe 10s of $ millions a year -- he was badly wrong.
To be simple and clear, what was hopeless was getting optimal schedules that saved all the money possible, down, literally, to the last tiny fraction of the last penny of operating cost, in worst cases. Saving the $ millions or 10s of $ millions, essentially always in practice, down to maybe the last $1000 or so, entirely doable with reasonable effort.
So, in my university visits and various investigations, the founder, COB, CEO of FedEx wrote a memo appointing me head of a project I had proposed to apply 0-1 integer linear programming set covering to the problem of fleet scheduling.
How to do that:
(1) Generate a lot, likely all reasonable, single airplane tours from the Memphis hub and back. Keep only tours that don't violate lots of really obscure, often non-linear, ..., constraints. For each such tour, do the cost arithmetic to find the expected cost.
(2) Set up a 0-1 integer linear programming problem with one row for each city to be served and one column and one variable for each tour. The costs are just the tour costs. The right side is just a column of 1s. The constraints are all equalities.
(3) Tweak the simplex algorithm to get a feasible, nearly optimal solution. Can use some simple bounding math to confirm that are optimal or nearly so.
Smile from the $ millions a year saved. In practice, can work fine nearly always.
The question of
P vs NP?
Get to ignore it.
The research questions in computational complexity remain curious, interesting, challenging, and likely important. But for the immediate, practical problems of combinatorial optimization in practice, where we care a lot about the $ millions saved and hardly care at all about the possibility of $1000 not saved, we don't have to wait on the research and, instead, often or usually can do well now.