動的計画とPuLPで実際問題を解決？

最適化の勉強会のビデオで某IT企業の人が動的計画で実際問題を解決できるとおっしゃっていた。競技プログラミングならまだしも、実際問題に適用して、なんでも解けるというのは無謀だ。

この会社は色々なプロジェクトで失敗していると聞いている。競技プログラミング程度の腕前で実際問題を解決できると宣伝している会社は避けるべきだ。

別のビデオで、ジョブショップスケジューリングをPuLPで解決というのがあった。結局、オモチャ問題を解いているだけなのだが、どうやら友人の書いたブログを参考に、勉強して解いてみたということらしい。友人は、定式化とプログラミングのお手本を示しているだけなのだが、解けるとは言っていない。このビデオでは、実際問題どころか、最小のベンチマーク問題さえ解けない。

Gurobiなら最大完了時刻が小さいベンチマーク問題なら、ある程度の解が出る。ただし、離接定式化という弱い下界の定式化を使う必要があるので、最適解を出すのは難しい。