この問題を表すモデルを探していますが、それはnp完全であると思われます

Question

（NDAの問題を回避するために、この質問の詳細を変更しました。文字通り撮影すれば、この理論的な会社を運営するより良い方法があることを知っています。）

倉庫のグループがあり、それぞれが会社が製造している合計1000製品のうち、200種類の製品を保管および配布できます。各倉庫には200個の製品が在庫されており、注文が割り当てられ、手元の在庫から埋めるようになります。

課題は、各倉庫が自給自足である必要があることです。倉庫に割り当てられる任意の数の製品（通常は5〜10）の注文があります。その後、倉庫は注文に必要な製品を梱包し、それらを一緒に出荷します。倉庫で利用できないアイテムの場合、注文を出荷する前に、アイテムを倉庫に個別に配信する必要があります。

したがって、問題は、最高の注文数を注文して個々のアイテムを待つことなく梱包できるように、最適な倉庫/製品構成を決定することにあります。

たとえば（それぞれ手紙で表される製品を使用し、5つの製品ラインを在庫できる倉庫）：

Warehouse 1: [A, B, C, D, E]
Warehouse 2: [A, D, F, G, H]

Order: [A, C, D] -> Warehouse 1
Order: [A, D, H] -> Warehouse 2
Order: [A, B, E, F] -> Warehouse 1 (+1 separately ordered)
Order: [A, D, E, F] -> Warehouse 2 (+1 separately ordered)

目標は、履歴データを使用して、将来的に個別に注文された製品の数を最小限に抑えることです。倉庫が特定の方法でセットアップされると、ソフトウェアはどの倉庫が最小限のオーバーヘッドで注文を処理できるかを判断するだけです。

これはすぐに私を機械学習スタイルの問題として襲います。また、特定のよく知られているNP不完全な問題の組み合わせのように思えますが、それらのどれも適切に適合していないようです。

このタイプの問題を表すモデルはありますか？

Answer 1

正しく理解していれば、問題を分離する必要があります。

• 各倉庫が何をすべきかを予測します
• 注文に最適な倉庫を入手してください

最初の問題については、私はあなたに Netflix賞 ：これはほぼ同じ問題であり、素晴らしい解決策が提案されています。 （私のデータマイニングハンドブックは自宅にあり、Googleへの正確なキーワードを覚えていません。ごめんなさい。

2番目の場合、これはPrologの問題です。

• アイテムを個別に注文するためのコストを設定します
• IDKのためにコストを設定し、顧客に近接してください
• すでに所有している製品を0に設定する
• 製品を取得するためにルールを作成します：あなたがそれを持っていない場合はそれを購入してください、あなたがするならばそれを取得します
• すべての製品を取得するためのルールを作成します：foreach製品、上記のルール
• このルールのコストを取得します
• Prologに解決策を取得するように優しく依頼してください。十分でない場合は、もっと尋ねてください。

Prologを使用したくない場合は、いくつかの制約ライブラリがあります。ただGoogle "Constraint Library <insert your programming language here>"

Answer 2

問題の最初の部分（アイテムは一緒に頻繁に順序付けられる）は、共起問題として知られていることがあり、データマイニングの文献の大部分です。 （私の回想は、問題はNPにあるが、非常に良い近似アルゴリズムがあるということです）。

あなたが満足している共起データを取得したら、あなたはまだ倉庫へのアイテムの割り当てを残しています。セットカバーの問題に少し似ていますが、まったく同じではありません。この問題はNPハードです。