組合せ最適化とは¶
最適化の分類
PyQの「数理的アプローチによる問題解決」では、最適化問題を以下の3つに分類して説明します。
線形最適化：前パートで扱いました。目的関数と制約条件が線形の問題です。
混合整数最適化：線形最適化と比較して、変数の種類として連続変数と整数変数が使えます。
一般的な最適化：制限のない「いわゆる最適化」です。研究者の間では、非線形最適化というキーワードで、一般的な最適化が扱われるので、ここでは非線形最適化とも呼びます。
包含関係だけ抜き出すと、下図のようになります。
組合せ最適化（Combinatorial Optimization）は、分類中の混合整数最適化に含まれますが、ほぼ同じものと考えてください。組合せ最適化では、線形最適化では扱えなかった問題が扱えるようになります。
参考：組合せ最適化
組合せ最適化のやり方¶
組合せ最適化では、線形最適化で使えなかった、0-1変数と整数変数が使えます。 違いは、これだけです。
組合せ最適化のQ&A¶
組合せ最適化は、使われていますか？
組合せ最適化は、社会で広くニーズがあります。日本では、使われている分野もありますが、広く使われているとは言い難いです。
無料で使えますか？
モデラーもソルバーも特に制限なく無料で使えます。ただし、規模の大きい問題は解けません。一般的に、有料のソルバーの方が高性能です。
大きなサイズも解けますか？
組合せ最適化は、変数が数十の小さい問題でさえ、1日実行しても結果が出ないことがあります。変数が数十万でも解けることもあります。実行してみないと、何とも言えません。同じぐらいのサイズであってもモデル化の違いで計算時間が全く異なることが、よくあります。
