最適化 - このような問題を解決するための効率的な方法だろうどのようなコスト

Question

を最小限セットの選択のサブセット：

我々は（：製品、医療検査など）多くの可能な実体を持っています。エンティティはパッケージで提供され、アイテムA、B、Cをパッケージで購入することは、別々に購入するよりもコストがかかります（商品には価格がある場合、商品は個別に販売される場合もあります）。私たちはいくつかの項目だけに興味があります。最小限のコストで必要なものをすべて購入するために、単一の製品やパッケージの最良の組み合わせが何であるかを見つけたいと考えています（私たちは、我々のリストからではなく、彼らは私たちにゼロの価値がある）。パッケージの内容は重複する可能性があります（たとえば、項目Aは複数の異なるパッケージで提供され、独自に提供することもできます）。

最もネイティブな方法は、パワーセット（すべての可能なサブセット）を計算することですが、これではソリューションの拡張がうまくできません。

効率的または近似/ヒューリスティックな解決策は何でしょうか？

Answer 1

これは最適化モデルで実行できます。

は、我々は、入力データとして持っていると言う：

----  14 SET c items+combos 

c1, c2, c3, A , B , C 


----  14 SET i single items 

A, B, C 


----  14 PARAMETER p prices 

c1 30, c2 18, c3 18, A 10, B 12, C 15 


----  14 PARAMETER cc combo content 

      A   B   C 

c1   1   1   1 
c2   1   1 
c3   2 
A   1 
B      1 
C         1 


----  14 PARAMETER demand items needed 

A 7, B 4, C 3 

今、私たちは、単純な混合整数計画（MIP）を解くモデル：

：

結果がどのように見えます

----  36 VARIABLE buy.L items+combos to buy 

c1 3, c2 1, c3 1, A 1 


----  36 VARIABLE cost.L    =  136.000 

Iいくつかのケースでは、私たちは必要以上に購入します（割引が十分に高い場合）。購入したアイテムの価値がある場合、モデルは少し複雑になります。

高性能な商用およびオープンソースMIPソルバーの両方を簡単に利用できます。彼らは、このタイプのモデルを非常に効率的にグローバルな最適化に解決します（多くのアイテムと多くのコンボを持つ大きなデータセットの場合でも）。あなたの "powerset"アルゴリズムと比べると、私にとってはこのアプローチははるかに魅力的です。 MIPソルバは近似ではありませんが、一般に可能な全ての可能な整数解のごくわずかな部分を探索する必要があります。