問題タブ [integer-programming]

Gurobi 6.0 で大きな MIP を解決しています。私のアドバイザーは、問題に 12 時間の制限時間を設定したいと考えています。TimeLimit パラメーターを設定すると、割り当てられた時間が経過するとソルバーが強制終了されることがわかりましたが、その時点で最適な実行可能なソリューションを取得する方法がわかりません。目的の値と最適性のギャップだけです。実行可能な最善の解決策を得る方法はありますか?

整数計画問題を解くために、matlab GA ツールボックスを使用しました。この問題には、いくつかのバイナリ変数があります。バイナリ変数などの非線形制約を使用しx*(1-x) = 0ましたが、matlab はこれらの変数に対して実数を出力します。

もう 1 つの問題は、最終的な解決策が実行可能でないことです。このコード行を使用しました：

しかし、matlab は実行可能なソリューションをまだ生成していません。

友人は、等式制約の代わりに不等式制約を使用することを提案しましたが、それは失敗しました。

それから、2 つの問題があります。1）バイナリ変数についてmatlabを言い、2）実行可能なソリューションを生成します。

問題に matlab GA を使用するにはどうすればよいですか?

数学的最適化モデルを解こうとしています。モデルでセット、たとえばiを定義したいのですが、それを 0 から 15 にしたいのですが、可能ですか? または、1 から 16 まで定義する必要がありますか? Web サイトで入手できる GAMS (General Algebraic Modeling System) のデモ版を使用しています。

ありがとう

PS: 十分な評判がある人は、GAMS タグを作成してください。

私は（混合）整数プログラミングに比較的慣れておらず、制約の定式化に行き詰まりました。

私の単純化したモデルでは、上限として値 321 を持つ正の実数である 1 つのパラメーターと 2 つの変数があります。表現したいロジックは次のとおりです。

これを線形イン（等式）を使用して実際に記述することは可能ですか?

役立つ場合: 実装には、Python、Pyomo、および最新の gurobi ソルバーを使用しています。

ご協力いただきありがとうございます！

バイナリ整数プログラミングの問題があり、 で解決したいと考えていbintprogます。

解決策bintprogは私に与えられましたが、 1と2（3に接続されている）の両方が選択されている場合、平均4に到達x={3}できる解決策が必要です。x={1,2}望んでいた結果を得るにはどうすればよいですか?

編集: ノード 3 は、それに接続されている少なくとも 2 つのノードがアクティブな場合にのみ有効にできるスイッチのように機能します。これが発生すると、最後のノードに到達できます。たとえば、1,2 がアクティブな場合、4 に到達できます。1,4 がアクティブな場合も同じことが言え、2 に到達できます。3は明らかに解決策ではありません。

私は整数プログラミングに比較的慣れていないため、(再び) 制約の定式化に行き詰まりました。

私の簡略化されたモデルでは、下限 LB がゼロ未満で上限 UB がゼロより大きい (連続) 変数があります。ここで、変数が取った値に応じて、変数値を他の変数に割り当てたいと思います。

私が表現したいロジックは次のとおりです。

線形 (不) 等式を使用してこれをどのように説明できますか?

取り込みが少し遅いと思います..

前もって感謝します！

** 編集: モデリングには、Python、Pyomo、および最新の Gurobi ソルバーを使用しています。

*** 編集: バイナリ変数を使用して、次のように定式化しました。（二次であることは知っていますが、これは後で線形化できます）：

しかし、Variable2 が > 0 の場合、Variable3 が 0 であることを確認する必要があります。

何か案は？

MIP ソルバーが分岐する変数を選択しようとしているノードを考えると、選択する変数の小さなサブセットを提案したいと思いますが、ソルバーのヒューリスティックとの関係を断ち切ります。これにより、整数計画問題を解くのに必要な時間を大幅に短縮できると信じるに足る十分な理由があります。私は Gurobi (Python API) を好みますが、必要に応じて別のソルバー (SCIP、CPLEX) に切り替えたいと考えています。

問題：

1. どのGurobi コールバック コードが、ソルバーが分岐しようとしていることを教えてくれるかわかりませんでした。 CPLEX についてはBranchCallback、詳細な例を見つけました。対応する SCIP ドキュメントは次のとおりです: How to add branching rules .

2. ソルバーに提案したい変数のサブセットは、ノードでの緩和の解が与えられると、オンザフライで計算されます。つまり、分岐の優先順位は、緩和された問題の解に応じて、ノードごとに変化します。コールバックで分岐優先度をリセットすることが許可され、期待どおりに機能するかどうかは不明です。Gurobi のドキュメントにBranchPriorityは記載がなく、問題 1 が解決されない限り、自分で「リバース エンジニアリング」することはできません。

3. 必要に応じて、変数のサブセットを提案するだけでなく、独自の完全な分岐ルールを作成して、関係を自分で断ち切ることもできます。ただし、これは 5 年前の Gurobi では不可能であり、ドキュメントはCallback状況が同じであることを示唆しています。コードを変更して SCIP や CPLEX を使用するよりも、独自の分岐ルールを実装するほうが簡単に思えるので、その Google グループの投稿で言及されている「コールバックによるカスタム部分カット」を試してみます。残念ながら、これを行う方法は私には明確ではありません。それが助けになる場合：すべての係数は整数であり、すべての変数はバイナリ変数です。

かなり一般的な MIP を解決しようとしています。ここに問題の特徴があります。

1. マルチ製品、マルチサイト (サイトは同時に生産、需要、および在庫保管場所として機能します)。毎週の時間バケット
2. 製品 (単位: ケース) は、各サイトで毎週限られた数のシフト/バッチを使用して、個別のバッチ サイズでのみ作成できます。
3. どのサイトでも需要を満たすために、サイト間の輸送が許可されています
4. さらに、各場所で週末の最低在庫レベルを満たす必要があります。

ソルバー (gurobi) からの現在の解は、ベスト バウンドから 15% を超える MIP ギャップに達することはありません。

この問題のバッチ サイズが固定されていない場合 (シフト中に任意の数量を生成できる場合)、問題は単純です。しかし、そうでない場合、誰かがこの種の MIP を解決するための単純なヒューリスティック手法を提案できますか?