すべての制約を満たすすべてのソリューションを見つけるという線形の問題があります。たとえば、私の変数は = [0.323, 0.123, 1.32, 6.3...] です。たとえば、フィットネス (最大化/最小化) 関数で並べ替えられた上位 100 のソリューションを取得することは可能ですか?

or-tools ルーティングの背後にある制約プログラミングをよりよく理解するために、デポと 2 つのルートを許可するように構成された他の 4 つのノードのおもちゃの例を作成しました。

これは、車両がデポから に移動し、0次に1ピッキング2またはのいずれかを選択してデポに移動し、デポに戻るという考え方です。車両は緑または赤のパスを選択します。私の実際の問題はより複雑で、複数の車両がありますが、同様の制約があります。340

この例では、コストのユークリッド距離関数を作成しました。

そして、次数を制約する l0 距離関数:

次に、モデルを作成し、これを解決しようとします。

したがって[1]、 とは、最初のソリューションが機能[4]することを可能にする選言であり、緑または赤のパスのいずれかを選択する必要があることを示す選言です。ALL_UNPERFORMED[2, 3]

これらの選言により、ソルバーは解決策を見つけますが、それを追加して2 after3と1beforeにアクセスする必要がある場合4、ソルバーはアクセスしない2か3、まったくアクセスしません。これはなぜですか？の分離ペナルティを0 -> 1 -> 2/3 -> 4 -> 0回避して、より最適なルートをソルバーが見つけられないのはなぜですか?int(1e10)[2,3]

編集：

それらを削除してに追加することにより、順序制約をソフトに制約しますDistance.__call__。

許可されていない注文にペナルティを課すには、ルートが発生し0 -> 2 -> 1 -> 4 -> 0ます。では、 and を明示的に有効にしている場合でも、 or-tools が1andを交換しないのはなぜだろうか。2use_swap_activeuse_relocate_neighborssearch_parameters.local_search_operators

注:失敗した理由は次のとおりです。

結論: 検索空間は小さく、より良い解はuse_relocate_neighbors返された解の近傍にありますが、or-tools はそれを見つけられません。なんで？

すべてのコード:

私はGoogle のor-toolsAWS EC2 インスタンスを正常に使用していますが、最近 AWS Lambda 関数に含めることを検討していますが、実行できません。

関数debug.py

以下は、すべてが正しく設定されていれば成功するはずのpywrapcpfromをインポートする基本的な関数です。ortools

モジュールのインポートの失敗

zip アーカイブを作成する前に、 Amazon の指示に従ってすべての依存関係をプロジェクトにコピーするpackage.shスクリプトを作成しました。デプロイされたコードを実行すると、次のようになります。

の内容package.sh

ortoolsフォルダーをortools-4.4.3842-py2.7-linux-x86_64.eggプロジェクト ルートに直接コピーすると、それが見つかりortoolsますが、インポートpywrapcpに失敗します。これは、ネイティブ ライブラリの読み込みの失敗に関連している可能性がありますが、ログに詳細が表示されないため、わかりません。

何か案は？

私は Python プログラミングと開発全般に比較的慣れていないので、Google or-tools をうまくインストールできたことに驚きました。それは、このコマンドまででした: $ make third_party. コマンドが認識されません:

toolsファイルがあるサブディレクトリに移動するmake.exeと、コマンドは認識されますが、エラーが発生します。

これで、GLPK と SCIP を依存関係に追加するなど、途中のすべてのステップ (CMake と Java JDK のインストールなど) を完了しましPATHた。 Googleの指示に明確に記載されていないにもかかわらず、インストールしました。

SVN は or-tools リポジトリの と連携することになっていることは知っていMakefileますが、それを認識していないようです。別のオプションよりも TortoiseSVN を選択することで問題が発生する可能性がありますか? 私は何を間違っていますか？

また、Microsoft Visual Studios 2015 の [ツール] メニューにターミナルがありません。VS2015 の開発者コマンド プロンプトを使用するように求められていますか?

以下のコードを使用して、routingModel に時間制限を設定しています。

しかし、検索が完了した後にステータスを取得する方法がわからないので、それがキャンセルされたのが制限時間だったのか、それとも他の理由で解決策が見つからなかったのかを確認できます。助けてください

RoutingModel クラスにはこの静的プロパティがありますが、インスタンスからそれらを読み取る方法がわかりません:

次のコードの問題は次のとおりです。

配達する場所が 10 か所しかなく、場所 0 に 1 つのデポが設定されている場合でも、この例では、車両 1,2,3,4 は場所 10,11,12,13 にデポがあるようです。それらの場所は存在しません。私が持っている10個は、0から9までの番号が付けられています。

一方、ビジネス ロジックは問題ないようです。

デポを出るコストとデポに戻るコスト (値 10) を分離したので、期待される結果 104 が得られました。デポを含まない都市間の移動は 4 回しかありません。

これは Google またはツールのバグですか?

Google or-tools のサンプルの 1 つは、n-queens 問題のソルバーです。 下部には、対称性を破る制約を制約ソルバーに追加することで実装を改善できることが示されています。

インターネットを見回すと、対称性が n-queens 問題の制約を破っていることがわかりましたが、それらを制約に変換して、それらを実装する Python コードにする方法を一生理解できません。

編集：これは悪い質問でした。更新しましょう...

私は何を試しましたか？

上記の最初のリンクからのセットアップは次のとおりです。

単純な制約をうまく実装できることはわかっています。ソリューションの最初の行の最初の列に常にクイーンがあることを確認したい場合は、次のように実装できます。

変数は最初の列のqueens[0]クイーンの位置を表し、この制約は、最初の列の最初の行にクイーンがある場合にのみ満たされます。もちろん、これは私がやりたいことではありませんが、ソリューションにコーナーセルが含まれていない可能性があるためです。

n-queens 問題の対称性の破れの制約を以下に示します。それらは、2 番目の段落のリンクから直接取得されます。

これらの制約がどのように機能するかを理解しています。この関数を n-queens ボードの各セルに適用して、状態を同等の状態に変換できるという考え方です。これらの状態の 1 つが、その状態の正規表現になります。これは、重複した評価を排除することによって、将来の処理を削減する方法として使用されます。

事後的にこれを実装するだけなら、上記で説明したことを正確に実行し、考えられる対称性を破る関数をそれぞれ使用して状態を変換し、ある種の状態ハッシュ (たとえば、各列で選択された行の文字列) を計算します。提案されたソリューションごとに最も低いものを選択します。以前に見たものについては、将来の処理をスキップします。

私の問題は、これらの変換を google or-tools 制約プログラミング ソルバーの制約に変換する方法がわからないことです。

d1(r[i] = j) => r[j] = i主対角線についての最も単純な反射を見てみましょう。私が知っているのは、変換をすべてのセルに適用し、現在の状態と比較して、セルが拡張されないようにする必要があるということです。ここで変換のためにどのような式が機能するかを理解するのにPythonについて十分に理解していません。また、この特定のソルバーの現在の状態と変換を比較する制約を作成する方法がわかりません。