発見的プログラミングと数学的プログラミングの両方を使ってNP困難な問題を解くことは可能ですか？

Question

私は、遺伝的アルゴリズムと、並列機械スケジューリング問題の混合整数プログラミングモデルを持っています。しかし、数学的モデルは問題を解決するのに時間がかかりすぎるとは考えにくい遺伝的アルゴリズムは時間がかかりませんが、最適解は示されません。だから私は、遺伝的アルゴリズムから解を取って数学プログラミングの出発点にすることが不可能かどうか不思議です。実際に可能ですか？

Answer 1

従来のブランチとバインドMIPソルバーを使用すると、ヒューリスティックなソリューションを提供する場合（たとえば、対応するコールバックによって）、ソルバーを一定量まで助けることができます。 1つだけでなく、ソリューションプールにさらに多くの情報を提供できます。

1. 問題は、ほとんどの場合、MIPソルバーが最適性を証明しようとしていることです。たとえ最適な解が見つかったとしても、数時間と数日を使って最適解を見つけることができます。だから、客観的な値に対してより大きなギャップを設定することができます。これは、最適性のために受け入れられます。通常、それは多くの助けになります。
2. 通常、スケジューリングの問題は非常に対称的であり、通常、単純なホルムラチンではかなり悪い結果を出します。あなたのスケジューリング問題の科学文献を探してみてください。スタック交換に関する数学フォーラムにあるかもしれません。
3. これらの問題が簡単に定式化された場合、LP緩和はしばしば非常に緊密ではない。多くの場合、少なくとも受け入れ可能なものを実行するには、いくつかのエキストラカットが必要です。これは二元性のギャップにも意味があります。

したがって、客観的価値のために最初に大きな許容差をつけてみてください。次に、対応する発見的なコールバックによって、いくつかの良い（そしてさまざまな解決策）MIP-Solverに渡そうとします。依然として受け入れられない場合は、問題の文献を探してみてください。しかし、私は、MathOverflow-Forumはそれらのモデルトピックに適していると考えています（そして、このトピックよりも熟練した意見があります）。