線形計画法の問題を段階的に解決し、新しい制約を追加して、双対シンプレックスで最適化を解決したいと考えています。これはソルバーの内部で行われますが、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
- generate new nodes without branching on integer variables
- with a different new constraint for each node