

数理最適化に関するアルゴリズムに関して学習しています。

0-1整数2次計画に関して分岐限定法で厳密解などを解くらしいのですが、  
調べても連続変数の２次計画の問題に関する内容が多く、私の検索能力が低くて見つけられません。

0-1整数2次計画問題に関して  
<https://www.letsopt.com/entry/2019/08/18/131125>

groubiOptimizerのような有料のものではなく、  
pythonで解くフリーのライブラリーなどありますか？  
また、サンプルコードでもあればそれを理解して学習したいです。  
（Atcoderとか得意な人はすぐに書けるものなのでしょうか？）


CC BY-SA 4.0
2020-06-26T01:17:26.247
68005
2022-09-21T23:00:38.287
2020-06-26T04:00:48.280
19110
37042
question
python アルゴリズム
0-1整数2次計画問題に関する数理最適化のアルゴリズムについて


## Fixstars.Amplifyソルバ

Fixstarsが提供しているAmplifyソルバを用いて問題を解くことができます。元々はイジングモデル求解ソルバですが、バイナリ（0-1整数）変数でのモデリングも可能です。制約もつけられます。

<https://amplify.fixstars.com/ja/>

利用規約の範囲で、無償ライセンスでも問題を解くことができます。  
ただ、アニーリングによるヒューリスティックな解法なので、厳密解を得られる保証はありません。

## 変数積を解消して線形計画ソルバを実行する

[http://web.tuat.ac.jp/~miya/fujie_ORSJ.pdf](http://web.tuat.ac.jp/%7Emiya/fujie_ORSJ.pdf)
の3.4非線形関数
2を見ると１つのバイナリ変数と3つの制約を問題に足すことによってバイナリ変数の積を解消する方法が記載してあります。このテクニックを用いて問題を線形化し、線形計画ソルバを実行することでオリジナルの問題の解を求めることができます。  
こちらの方法であれば厳密解の取得が可能です。


CC BY-SA 4.0
2022-09-21T13:30:32.940
91217
2022-09-21T23:00:38.287
2022-09-21T23:00:38.287
54208
54208
68005
answer