問題タブ [integer-programming]

n 個の整数変数と m 個の制約を使用した ILP (整数線形計画法) 最適化と、正準問題を解決するための分枝限定木を実装する場合、

1. ツリーが全整数最適解に到達するために必要なレベル (ツリーの高さ) はいくつですか?
2. アルゴリズムが全整数最適解に到達するために必要な枝の数は?

線形計画法 (LP) の問題の凸包をどのように定式化して積分することができますか? これを実行するための一般的な手法はありますか?

与えられた n と mに対して、エントリが 0 または 1の n × m 部分巡回行列すべてを反復処理します。同じ合計を与える列のサブセットが 2 つ存在しないような行列があるかどうかを調べたいと思います。ここで列を追加するときは、要素ごとに行います。私の現在のコードはortools による制約プログラミングを使用しています。しかし、それは私が望むほど速くはありません。n = 7 および m = 12 の場合は 3 分以上かかり、n = 10、m = 18 の場合は、考慮すべき異なる行列が 2^18 = 262144 しかないにもかかわらず終了しません。これが私のコードです。

n = 10、m = 18 を解くことができるように、この問題を十分速く解くことができますか?

与えられた n と mに対して、エントリが 0 または 1の n × m の部分巡回行列すべてを反復処理します。同じ合計を持つ列のサブセットが 2 つ存在しないような行列があるかどうかを調べたいと思います。ここで列を追加するときは、要素ごとに行います。私の現在のコードはortools による制約プログラミングを使用しています。これが私のコードです。

この行values = [-1,0,1]では、解に任意の数のゼロを使用できます。代わりに、ソリューションで許可されるゼロの正確な数を指定するにはどうすればよいですか?

いくつかの制約に従って、s = c1*x1 + c2*x2 + c3*x3 + c4*x4 のような式を最大化するアルゴリズムを使用する必要があるボードをフラッシュしています。

たとえば、x+y <= 2, 3x+y >= 4 を条件として p = x+y を最大化します。最適解: p = 2; x = 1、y = 1

どこかで使用できる無料のコードはありますか?

ありがとうございました

みんな。私は自分の研究のためにいくつかの式を定式化します。この問題を解決できるツールはありますか。GLPK や MATLAB ツールボックスなどのツールをいくつか調査しましたが、数式は非線形のようです。インターネットでいくつかの情報を見つけました。これは、0-1 整数計画法と呼ばれる整数計画法の特殊なケースです。

私の疑問は、次の式のようにバイナリ変数を指数に入れることはできますか? また、この問題を解決するときに「product(pi)」を使用して利用できますか? いくつかの例を調査しましたが、この 2 つの使用法は見つかりませんでした。

変数は Xc,n,m,s,i です。また、Lc,n、Tmax、Tm、Pm,s,i、Dc,n,k、Bm はすべて既知の数です。

この問題について誰か提案してもらえますか? 読んでくれてありがとう！

写真を更新し、数式に AMPL 言語を使用してみます。

指数関数から変数 X を削除するための論理制約を使用した変更:

変数 h が既に正の整数値に関連付けられているとします。値が h より小さい完全平方の数を 1 から数えるためのコードを記述します。(完全な二乗は、別の整数 (この場合はそれぞれ 3*3 、 4*4 、 5*5 、 6*6) の二乗に等しい 9 、 16 、 25 、 36 のような整数です)。変数 q に計算します。たとえば、h が 19 の場合、h より小さい完全な正方形 ( 1 で始まる) が 1 、 4 、 9 、 16 であるため、q に 4 を割り当てます。

これは私がこれまでに持っているもので、何が間違っているのかわかりません。

q = 0

平方根 = int(h ** 0.5)

sqrt != h の場合:

h += 1

for i in range(1, sqrt):

q += 1

これは、 SCIP を使用した MIP の LP 緩和に関する以前の質問のフォローアップです。

MIP (CPLEX 形式) を SoPlex に渡すだけで MIP の LP 緩和ソリューションを計算できますが、SoPlex にかかる計算時間は、SCIP 自体を使用して MIP を最適化するよりも長いことがわかります (より小さな入力のテスト)。 ）。SCIP は MIP を解決する前に SoPlex を内部的に使用するため、これはどのように可能ですか? さらに、私の LP 緩和の結果は、実際には整数解を与えており、MIP と同じ目的値です。LPリラクゼーションを間違えていますか？それとも、私の問題/定式化の特性ですか？

私は、ソルバーによって出力された合計計算時間を参照しています (自分で計算したものではありません)。