A Discussion
Eugene Freuder
I asked Helmut Simonis if he could identify some specific NP-complete problems for which an increase in the “n” that can be handled in reasonable time at reasonable cost would provide a large practical commercial benefit, and how much of an increase would be required. He provided a thoughtful and illuminating answer.
For the heck of it I asked ChatGPT a similar question.
The chatbot took the question literally and provided what may or may not be a good answer. The human expert observed that I was asking the wrong question. 🙂
Below I provide Helmut’s response and a link to an extended conversation with the chatbot.
What do you think? About the question? About the responses? Please join the discussion!
Remember to reply to the Group, not just to me individually.
Helmut:
I don't think that being able to provide the "exact, optimal" solution for some larger problem instances would make a big difference. For most problems, we are able to solve large problem instances to a reasonable quality in a reasonable amount of time.
The big gains, in my opinion, typically come from another direction: In many cases, the large overall problem is decomposed into a set of interdependent sub-problems, to allow solving of the problem at all. The operations of an airline, for example, will be decomposed into route planning, deciding which connections to over, plane rotations (which specific planes will perform which flights), and crew rotations (which crew will cover which flights as part of a 4 week plan), and then the operational replanning on the day, as flights are delayed, crew is sick, or planes develop problems. Splitting the problem in this way creates more manageable subproblems, which one can solve with different technologies, and different teams. The problem is that the sub-problems are interdependent, the best choice for overing a route may have a huge negative impact on the number of crew required to cover this route, the best monthly plan for crew may be so tight that any delay or other change requires a complete replan, etc. There has been a lot of work on solving the integrated problem instead, showing the potential benefits, but this has a number of issues, some technical, but even more organizational. The teams for dealing with the sub problems may have been working on their problem for many years, and do not want to lose some of their optimization benefits to other groups. The sub problems might be solved with different technologies, and it is not clear which method would work best for the combined problem. The combined problem may need to be resolved frequently as the situation changes, dramatically increasing the computational demand to keep the solution current over time.
Another example for this challenge is the IHTC 2024 competition for integrated hospital management that you mentioned a few weeks back. Here the classical decomposition leads to a sequence of sub-problems, where each problem builds on the solution of the previous steps. The problem is that these subproblems require different techniques, due to their formulation. The initial patient admission/room assignment problem would probably be best solved by Benders Decomposition, with the room assignment providing cuts to guide the initial admission assignment. But the later stages of nurse allocation are formulated with soft constraints only, a local search looks like the most promising solution method. What method should we use for the integrated problem? But it is clear that an integrated approach would provide better overall results, it does not work if you admit a lot of patients at some point, if your nursing staff is not able to deal with the care demands of these patients. The better overall solution would be to limit admission, even if that means that some patients are delayed in their treatment.
Of course there are problems where teams are competing to solve the next size instance. You may recall the rectangle packing problem from a fews years back, where you have a sequence of synthetic problems of increasing sizes, each size adding one more square to be packed. Being able to find and prove optimality gets so much more difficult from n to n+1, that increasing the best known results from 25 to 26 makes a publishable paper. But even here we do have more manageable approximation methods. Laying out an integrated circuit with billions of transistors will not be solved by an exact method for some time to come :-)
Another thought:
There is an important distinction to make with regards to combinatorial problems. In nearly all cases, the well-known "pure" problems (like job-shop, TSP) are the most simple problem formulation that maintains the theoretical complexity, but it doesn't mean that any real problem only has those constraints. Academics like to work on these pure problems, as they are easy to understand, to explain, and make comparison between results much easier.
But, to be really useful, the solution may have to incorporate many company/setting specific additional constraints, especially when humans are affected by the solution. This can be breaks, or working time limits, personal preferences, etc.
Also, the raw input data may only be known with a certain accuracy, and solving the problem for one specific choice of data values may not produce a solution that is as good under changes of data.
In the end, these models are abstractions, and most likely were created in the olden days as the most complex version of the problem that could be solved by existing software/hardware. At some point you have to step back and see if just solving larger instances of the same problem formulation is still meaningful, or if a more complex abstraction of the problem should be chosen.
ChatGPT:
https://chatgpt.com/share/68cdbf5a-488c-8010-af3a-dfda9dcf666e
(Read from the top. And here is general info on shared links if you need it: https://help.openai.com/en/articles/7925741-chatgpt-shared-links-faq.)
Join the discussion, here on the Google Group. Remember to reply to the Group, not just to me individually.
mark.wallace
By retiming a small number of flights, the software allowed the schedule to be covered by fewer aircraft.