リニアプログラムでバリア解消後のクロスオーバー回避の問題

Question

私は大きなLP（約5M非ゼロ）を実行しており、解決プロセスをスピードアップしたい。私はどのアルゴリズムが私の問題を最も速く解決するかをテストするために並行解決を試みましたが、私はバリアメソッドが明確な勝者であることを発見しました（ソルバー= Xpress MPですが、他のソルバーにとっても同じであると思います）。

しかし、私はそれをさらにスピードアップしたいと思います。私は、実際の障壁の解が全解時間の1％未満であることに気付きました。残りの時間はクロスオーバー（〜40％）と原点解法（新しい基準でコーナー解を見つけるために）（〜60％）に費やされます。残念ながら、デュアルクロスオーバーを行うように指示する設定はありませんでした（Cplexには1つありますが、Cplexのライセンスはありません）。したがって、私はこれがより速くなるかどうか比較することができませんでした。

私は大きなスピードアップをもたらすクロスオーバをオフにしようとしましたが、ドキュメントにはいくつかの欠点があります。これまでのところ、私が知っている欠点は次のとおりです。

• 障壁溶液は中層溶液である傾向があります。
• クロスオーバのないバリアは、基本的なソリューションを生成しません（ただし、「クロスオーバを使用するかどうかにかかわらず、完全なプライマルとデュアルソリューションが利用可能です」という記述があります）。
  • 基本情報がないと、高度な開始情報を使用して繰り返し同じまたは同様の問題を最適化することができなくなります。
  • 基礎がないと、感度分析を実行するための範囲情報を取得できません。

私の質問（複数可）である（ある）シンプル。非常に非効率なクロスオーバ・ステップ（CplexとXpress MPの両方がデフォルト設定としてクロスオーバを可能にする）を正当化するには、他に何か欠点があります。あるいは、私の問題は例外的で、他の問題ではクロスオーバ・ステップが非常に速いのですか？最後に、ミッドフェイスのソリューションを持つことで何が問題になるのですか（コーナーの最適化もユニークではないことを意味します）

源：

• http://www.cs.cornell.edu/w8/iisi/ilog/cplex101/usrcplex/solveBarrier2.html（バリアアルゴリズムの高レベルの理論）
• http://tomopt.com/docs/xpress/tomlab_xpress008.php（XpressのMPソルバ設定）

Answer 1

主な欠点：溶液は "醜い" になり、即ち解の値には0.000001と0.9999999が多く含まれています。第二に、あなたは幾分異なる二重を得るかもしれません。最後に、迅速な「ホットスタート」を行うための基礎が必要です。大型モデルを高速化するための1つの方法は、シンプレックス法を使用し、代表的なベースランから高度な基礎を使用することです。