この問題は課題で発生しましたが、現在はクローズされているため、質問しても問題ありません。
問題 (この質問自体ではありません。これは単なる背景情報です) は、独自のイメージを借りて、次のように視覚的に説明できます。
私はそれを最適に解決することにしました。それはおそらく（決定バリアントの場合）NP完全問題です（確かにNPにあり、正確なカバーのようなにおいがしますが、一般的な正確なカバーの問題をそれに還元できることを証明していません）が、それで問題ありません。必ずしも最悪の場合ではなく、実際に高速である必要があるだけです。この質問の文脈では、カットを提供しない限り、近似アルゴリズムには興味がありません。
明らかな ILP モデルがあります。すべての可能な正方形を生成し (存在するグリッドのセルのみをカバーする場合、正方形は可能です)、x_i使用するかどうかを示すすべての正方形にバイナリ変数を導入し、次に
minimize sum x_i
subject to:
1) x_i is an integer
2) 0 ≤ x_i ≤ 1
3) for every cell c
(sum[j | c ϵ square_j] x_j) = 1
制約 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 回カバーする必要があるという制約によって、それは総面積で示されていることがすでに保証されています。より多くの自由を許可するだけです。
また、平方数 (すべての平方の面積は平方です) と平方数の差を使って何かをしようとしましたが、それも有用なものにはなりませんでした。