問題タブ [constraint-programming]

編集: このパズルは「アインシュタインのなぞなぞ」としても知られています

The Who owns the Zebra (ここでオンライン バージョンを試すことができます) は古典的なパズル セットの例であり、Stack Overflow のほとんどの人はペンと紙で解決できるに違いありません。しかし、プログラマティック ソリューションはどのようなものになるでしょうか。

以下の手がかりに基づいて...

• 家が5軒あります。
• 各家には独自の色があります。
• 家の所有者はすべて異なる国籍です。
• 彼らはすべて異なるペットを飼っています。
• 彼らはすべて異なる飲み物を飲みます。
• 彼らは皆違うタバコを吸っている。
• そのイギリス人男性は赤い家に住んでいます。
• スウェーデン人は犬を飼っています。
• デーンはお茶を飲みます。
• 緑の家は白い家の左側にあります。
• 彼らは温室でコーヒーを飲みます。
• ポール・モールを吸う男は鳥を飼っている.
• 黄色い家では、彼らはダンヒルを吸っています。
• 真ん中の家では牛乳を飲みます。
• ノルウェー人は最初の家に住んでいます。
• ブレンドを吸っている男性は、猫がいる家の隣の家に住んでいます。
• 馬を飼っている隣の家ではダンヒルを吸っている。
• ブルーマスターを吸う男はビールを飲む。
• ドイツ人はプリンスを吸う。
• そのノルウェー人は青い家の隣に住んでいます。
• 彼らはブレンドを吸う家の隣の家で水を飲みます。

...ゼブラの所有者は誰ですか?

制約プログラミングを始めるためのヒント、チュートリアル、本、その他のリソースを探しています。

私は仕事の影響の問題を解決する必要があり、この問題を解決するためにできれば効率的なアルゴリズムを見つけたいと思います。

いくつかの種類のタスクを実行できるワーカーがいるとしましょう。また、毎週実行する必要のあるタスクのプールもあります。各タスクには時間がかかります。各タスクは誰かが行う必要があります。各労働者は週にNからP時間の間働かなければなりません。

問題のこの最初の部分は、制約プログラミングアルゴリズムの良い候補のようです。

しかし、ここに複雑さがあります。労働者はさまざまなタスクを実行できるため、好み（または希望）もある可能性があります。すべての人のすべての希望を満たしたい場合、問題の解決策はありません（制約が多すぎます）。

したがって、この問題を解決するためのアルゴリズムが必要です。完璧なホイールがすでに存在する場合、私はホイールを再発明したくありません。

アルゴリズムは公平でなければならないので（この単語を定義できる場合）、たとえば、「人ごとに少なくとも1つの願いを満たそうとする」などの制約を追加できるはずです。この問題が、ここで説明されている制約階層メソッドによって解決できるかどうかはわかりません：制約階層。実際、このカテゴリのアルゴリズムの有効な制約によって「公平性」と希望を表現できるかどうかはわかりません。

アドバイスをくれる制約プログラミングの専門家はいますか？効率的なCPアルゴリズムを使用する代わりに、いくつかのヒューリスティックを使用して新しいホイールを開発する必要がありますか？

ありがとう ！

Java Constraints Libraryを使用してCSPロジックの問題を解決する必要があります。今のところ、問題のいくつかの制約を表すことができました。それらのほとんどは、「等しい」および「等しくない」バイナリ制約に基づいています。私の疑問は、追加ベースの制約を表現する方法ですか? 例：

• variable1 は DomainA に属します
• variable2 は DomainB に属します
• variable3 は DomainA に属します
• variable4 は DomainB に属します

制約は次のとおりです。

• variable1 と variable2 の合計は、variable3 と variable4 の合計より大きくなります。

観察: これらの変数はお金を表しているため、追加できます。

私はインタラクティブなジョブ スケジューリング アプリケーションに取り組んでいます。対応する容量/可用性プロファイルを持つ一連のリソース、これらのリソースで実行される一連のジョブ、およびジョブ シーケンスとジョブの最早/最遅開始/終了時間を決定する一連の制約が与えられた場合、ユーザーが手動で移動できるようにしたい周りの仕事。基本的には、ユーザーがジョブ ネットワークのノードを「つかみ」、制約に違反することなく前後にドラッグできるようにしたいと考えています。

このイメージは、単純な構成例を示しています。最後の三角形のジョブは、すべてのジョブの最終終了時刻を示し、ジョブ間の接続線はジョブに順序を課し、灰色/緑色のバーはリソースの可用性と負荷を示します。

任意のジョブをドラッグして、スケジュールを圧縮できます。能力プロファイルが異なるため、ジョブの長さが変わることに注意してください。

ちょっと機能するアドホックアルゴリズムを実装しました。ただし、失敗していくつかの制約に違反する場合がまだあります。ただし、ジョブ ショップ スケジューリングは、一般的な NP 困難な問題に対する最適な (または適切な) ソリューションを見つけるための多くのアルゴリズムとヒューリスティックを備えた十分に研究された分野であるため、より簡単なサブセットにはソリューションが存在するはずだと考えています。制約プログラミングのトピックや物理ベースのソリューション (静的ジョイントを介して接続された剛体) を調べましたが、これまでのところ適切なものが見つかりませんでした。ポインター/ヒント/ヒント/検索キーワードはありますか?

私はJavaでアプリケーションに取り組んでおり、その機能の一部として複雑な論理ルールの推論を行う必要があります。結果として得られるコードは非常に単純で保守しやすいものになると信じているため、Java の代わりに Prolog やその他の論理/制約プログラミング言語で論理演繹をコーディングしたいと考えています。

Prolog に埋め込まれた Java の実装を探してみたところ、多数の実装が見つかりましたが、それぞれのドキュメントはほとんどありませんでした。私の（控えめな）選択基準は次のとおりです。

• Java に組み込むことができる必要があります (たとえば、外部プログラムのネイティブ インストールを必要とする代わりに、私の Java パッケージにバンドルすることができます)。
• Java から使用するシンプルなインターフェース (推論の開始、結果の検査、およびルールの追加用)
• それを使用する方法に関する少なくともいくつかの例が付属しています
• 必ずしも Prolog である必要はありませんが、上記の基準を持つ他のロジック/制約プログラミング言語も私のニーズに合っています。

どのような選択肢があり、その利点と欠点は何ですか?

Constraint-Logic Programmingを読んでいると、SQL プログラミングとの明らかな関係に気付かずにはいられません。SQL は実際の「制約ロジック プログラミング」の例ですか?

かなり複雑な状況を解決するために Microsoft Solver Foundation 2 を使用しようとしていますが、可能な限りモデルを縮小しても UnsupportedModelException が発生します。
誰かが私が間違っていることを知っていますか?
以下は、問題のある動作を再現するために必要な最小限の例です。

私の実際のモデルには、完成したら、a + b a <= someValue の形式でいくつかの制約を含める必要があることを考慮してください。そのため、最終的に実行したいことがサポートされていない場合は、事前にお知らせください。その場合は、使用できる.NETフレンドリーなインターフェイスを備えた他のソルバーの提案もいただければ幸いです（よく知られている商用パッケージのみでお願いします）。

前もって感謝します

購入したい商品のリストがあります。アイテムは、さまざまなショップとさまざまな価格で提供されています。ショップには個別の配送料がかかります。最小限の合計価格ですべてのアイテムを購入するための最適なショッピング戦略（およびそれをサポートするJavaライブラリ）を探しています。

例：

• Item1はShop1で$100、Shop2で$111で提供されます。
• Item2はShop1で$90、Shop2で$85で提供されます。
• Shop1の配送料1：注文総額が150ドル未満の場合は10ドル。それ以外の場合は$0
• Shop2の配送料：注文合計が$50未満の場合は$5。それ以外の場合は$0

• Shop1でItem1とItem2を購入した場合、合計費用は$ 100 + $ 90 + $ 0 =$190になります。
• Shop2でItem1とItem2を購入した場合、合計費用は$ 111 + $ 85 + $ 0 =$196です。
• Shop1でItem1を購入し、Shop2でItem2を購入した場合、合計コストは$ 100 + $ 10 + $ 85 + $ 0=195になります。

Shop1でItem1とItem2を注文すると、最低価格が表示されます：$ 190

これまでに試したこと

その前に別の質問をしたところ、制約プログラミングの分野にたどり着きました。クリームとチョコを見てみましたが、問題を解決するためのモデルの作り方がわかりませんでした。

私のアイデアは、これらの制約を定義することでした。

• 各価格「pxy」はドメイン（0、c）で定義されます。ここで、cはこのショップの商品の価格です。
• 1行の1つの価格のみがゼロ以外である必要があります
• 1つのショップで1つ以上の商品を購入し、価格の合計が制限を下回っている場合は、合計費用に送料を追加します。
• ショップの総費用は、ショップ内のすべてのアイテムの価格の合計です。
• 総費用は、すべてのショップの合計の合計です

目的は「総コスト」です。これを最小限に抑えたい。

クリームでは、条件付き送料の「ifthen」制約を表現できませんでした。

チョコにはこれらの制約がありますが、5つのアイテムと10のショップでさえ、プログラムは解決策を見つけることなく10分間実行されていました。

質問

この問題を制約プログラミングソルバーで解決できるようにするには、制約をどのように表現すればよいですか？