3 ms·
> IMHO what made hard problems difficult to solve is actually the 'intneral structure' of the problems. 20 years ago I wrote a master’s thesis in computer visi
by bjornsing 2y ago
> IMHO what made hard problems difficult to solve is actually the 'intneral structure' of the problems.
20 years ago I wrote a master’s thesis in computer vision. The stereo matching algorithm I developed could be expressed as a big integer linear program. But after pondering it for some time I realized it could also be expressed as a dynamic programming problem, with tiny integer linear programs as subproblems. Reduced the runtime by like a factor of 1000x, or more.
- raverbashing 2y agoNot that uncommon. I feel most of those big search problems could be solved much easier and quicker with some form of annealing/tree search/dynamic or greedy algorithms with results very close to the theoretical linear optimum But of course those won't get you a thesis ;)
- bjornsing 2y ago> with results very close to the theoretical linear optimum In this case I could prove it was the globally optimal solution. But this was only possible of course due to the internal structure of the problem: it was in effect a simpler problem hiding within a linear integer program. Standard solvers couldn’t find this structure, but it was possible to do by hand.
- hustwindmaple1 2y agoReformulation is a good strategy for many hard problems. It might also be possible to add problem-specific cuts/heurstics to the solver so that it can solve it fast.
- djsavvy 2y agoWow, this sounds interesting! Do you have a link to that thesis?
- bjornsing 2y agoUnfortunately not. It’s on paper and in Swedish only.