問題タブ [integer-programming]

私のバイナリプログラミングの問題は次のとおりです。

対象:

これは、プロセス タスクの割り当ての問題です。私の場合、バイナリ/整数プログラミングの問題を解決するためのオーバーヘッドは、非常に小さくする必要があります (< 1 ミリ秒)。これを CBC ソルバー / lpsolve で実行すると、2 ミリ秒から 7 ミリ秒の時間がレポートされます。SCIP/Gurobi を持っていません。これをミリ秒未満で解決する方法はありますか? これを 1 ミリ秒未満で解決できると期待するのは理にかなっているように思えますか?

（私はCBCでprintfを無効にしました。しかし、他にスタックしているシステム操作があるかどうかはわかりません....それが書き込んでいるログファイル）

目的関数に 2 つの乗算変数があり、モデルを 2 次にする最適化問題があります。

現在、モデルを解析するために zimpl を使用し、それを解決するために glpk を使用しています。二次計画法をサポートしていないため、これを MILP に変換する必要があります。

. 最初の変数は範囲 [0, 1] の実数で、2 番目の変数は範囲 0 から inf の実数です。これは問題なく整数である可能性があります。

目的関数の重要な部分は次のようになります。

制約にも同様の問題がありましたが、簡単に解決できました。

この種の問題を目的関数でどのように解決できますか?

この問題は課題で発生しましたが、現在はクローズされているため、質問しても問題ありません。

問題 (この質問自体ではありません。これは単なる背景情報です) は、独自のイメージを借りて、次のように視覚的に説明できます。

私はそれを最適に解決することにしました。それはおそらく（決定バリアントの場合）NP完全問題です（確かにNPにあり、正確なカバーのようなにおいがしますが、一般的な正確なカバーの問題をそれに還元できることを証明していません）が、それで問題ありません。必ずしも最悪の場合ではなく、実際に高速である必要があるだけです。この質問の文脈では、カットを提供しない限り、近似アルゴリズムには興味がありません。

明らかな ILP モデルがあります。すべての可能な正方形を生成し (存在するグリッドのセルのみをカバーする場合、正方形は可能です)、x_i使用するかどうかを示すすべての正方形にバイナリ変数を導入し、次に

制約 3 は、すべてのセルが 1 回だけカバーされることを示しています。制約 1 と 2 は、x_i を 2 進数にします。最小解は、元の問題に対する最適解を与えます。

これの線形緩和 (つまり、制約 1 を無視する) は半分まともですが、次のようなことを行います (これは、左上隅が欠落している 6x6 グリッドです)。

ここでは、13 個の正方形がサイズの「半分」(客観的な値 6.5 を与える) が選択されています (そのため、それらを簡単に見つけることができます)。

• 4x4 の 1
• 3x3 の 3
• 2x2 の 6
• 1x1 の 3

このインスタンスの最適解は、次のように 8 の目的値を持ちます。

直線的な緩和はまあまあですが、私は完全に満足しているわけではありません。ギャップは 10% を超えることもあり、整数フェーズが非常に遅くなることがあります。

それが実際の質問の出番です。分数解を改善するために、カットとして (遅延して) 追加できる追加の制約はありますか?

たとえば、正方形を選択する代わりに、「左上隅」と「右下隅」を選択するとどうなるでしょうか。これらを一致させて、重なり合わない正方形を形成しますすべてのセルをカバーしますか? 次に、すべての「バックスラッシュのような対角線」には、左上隅と右下隅の数が一致する必要があります。しかし、それは役に立ちません。なぜなら、正方形を選択した場合、その条件はとにかく常に真であり、分数の解でも同じだからです。

また、重複についていくつかの推論を試みました。たとえば、2 つの正方形が明らかに重複している場合、それらの合計は 1 より大きくてはならず、重複領域に完全に含まれるすべての正方形を追加することで改善できます。しかし、その制約は、すべてのセルが 1 回だけカバーされるという制約よりも強力ではありません。

総面積について推論しようとしましたが (カバーされる総面積はセルの数と等しくなければなりません)、すべてのセルを 1 回カバーする必要があるという制約によって、それは総面積で示されていることがすでに保証されています。より多くの自由を許可するだけです。

また、平方数 (すべての平方の面積は平方です) と平方数の差を使って何かをしようとしましたが、それも有用なものにはなりませんでした。

それに応じてC、A、b、lb、ubを構築したオクターブでGLPKを使用して線形計画法の問題を解決しました。私の問題は最小化問題でした。したがって、ctype私は値を使用Lしvartype、値は でしたC。

今、私は整数計画問題を解決したいと考えています。vartypetoを変更しIて他の引数をそのままにしておくと、積分結果が得られますか? どんな助けでも本当に感謝します。

次の目的関数を使用して、混合整数線形計画法を解きたいと考えています。

J = 最大化 (f1(x) + f2(x)) 制約条件: cost(x) <= しきい値

ここで、x は選択された変数のセット、f1 と f2 は 2 つのスコアリング関数、cost はコスト関数です。

f2 は、選択した変数間の類似性に基づく関数です。この機能をパルプで定式化する方法がわかりません。

これは、関数 f2 が2つの成分間の類似性であり、すでに選択された変数にsimilarity[i][j]ある場合は目的関数に追加したいjが、その方法がわからない私の最小限の作業例です。

このコードは、基本的に静的コストのみを考慮します (costs 変数にエンコードされています)。similarity変数である類似性コストを動的に追加するにはどうすればよいですか?

すべてのエントリが 0 または 1 である、固定の m 行 n 列の行列 M を考えます。問題は、すべてのエントリが -1、0、または 1 であり、Mv = 0 であるゼロでないベクトル v が存在するかどうかです。たとえば、

この例では、そのようなベクトル v はありません。

この例では、ベクトル (0,0,0,1) により M_2v = 0 が得られます。

私は現在、すべての異なるベクトル v を試して、この問題を解決しています。

ただし、問題を整数計画問題または制約計画問題として表現することは可能ですか?その場合、より効率的な SCIP などの既存のソフトウェア パッケージを代わりに使用できます。

すべてのエントリが 0 または 1 である、m 行 n 列の行列 M を考えます。特定の M に対して、問題は、すべてのエントリが -1、0、または 1 であり、Mv = 0 である非ゼロのベクトル v が存在するかどうかです。例えば、

この例では、そのようなベクトル v はありません。

この例では、ベクトル (0,0,0,1) により M_2v = 0 が得られます。

m と n が与えられた場合、Mv = 0 のようなゼロ以外の v がないように、そのような M が存在するかどうかを調べたいと思います。

上記m = 3のようにn = 4、答えが「はい」の場合。

私は現在、非常に高価なすべての異なる M と v を試して、この問題を解決しています。

ただし、問題を整数計画問題または制約計画問題として表現して、より効率的な SCIP などの既存のソフトウェア パッケージを代わりに使用することはできますか。

線形計画法の問題を段階的に解決し、新しい制約を追加して、双対シンプレックスで最適化を解決したいと考えています。これはソルバーの内部で行われますが、GLPK、Clp、または LPsolve の API でそれを行う方法が見つかりません。

長方形のパッキング制約を使用して NP 完全問題を解決しています。線形緩和を伴うカスタム分枝限定アルゴリズムを使用します。混合整数計画法は論外です。あまりにも多くの変数 (n^2) を追加し、より厳密ではなく、一般に不適切な分岐決定を行います。ブール変数ではなく、追加された制約に分岐することで問題を解決します。

私は現在、LP の限られたサブセットのみを処理する手書きのソルバーを持っており、緩和を強化したいと考えています。真の (オープンな) LP ソルバーを使用したいと考えています。たとえば、GLPKは遅延制約を許可しますが、分岐を許可しないようで、各問題に異なる制約を追加し、以前の基底因数分解を破棄せずに解決します。

これらのソルバーで適切に行うにはどうすればよいでしょうか?

ありがとう

編集 - 背景:

I solve a problem with hard runtime limits, which includes rectangle packing constraints. For any pair of rectangles, there are four disjunctive constraints i.e. R1 above/below/right/left of R2.
Modeling it with boolean variables (with big-M), is too slow (bad branching choices + slower relaxation even with custom branching + lots of redundancy between feasible solutions): I need to branch directly on the disjunctive constraints, which works well, but I now need to use a general-purpose LP solver rather than my custom flow solver.

i.e. in the callback I want to

1. generate new nodes without branching on integer variables
2. with a different new constraint for each node