ブランドのルール

数学的最適化において、ブランド則（ブランドアルゴリズム、ブランド反サイクリング則、ブランドピボット則とも呼ばれる）は、線形最適化のためのシンプレックス法のアルゴリズム的改良である。

ブランド則を用いると、シンプレックスアルゴリズムは循環なしで実行可能な線形最適化問題を解くことができる。^{[1] [2] [3]}

元の単体アルゴリズムは、任意の基本実行可能解から開始し、最小化ターゲットを減少させて最適解を見つけるために基底を変更します。通常、ターゲットは各ステップで実際に減少するため、制限された数のステップの後に最適解が見つかります。ただし、元の単体アルゴリズムが永久に循環する退化した線形計画の例があります。基本実行可能解(実行可能多面体の角) で行き詰まり、最小化ターゲットを減少させることなく、基底を循環的に変更します。

このようなサイクルは、基底に入る列と基底から出る列を選択するための Bland の規則によって回避されます。

ブランド則は、現在コーネル大学のオペレーションズリサーチの名誉教授であるロバート・G・ブランドが、ベルギーのオペレーションズリサーチおよび計量経済学センターの研究員であったときに考案されました。^[1]

シンプレックス法の反復中に Bland の規則を使用して、最初にテーブル内のどの列 (入力変数) を、次にどの行 (出力変数) をピボットするかを決定します。目的関数を最小化する問題であると仮定すると、アルゴリズムは次のように大まかに定義されます。

1. 負の（削減された）コストを持つ、最も小さい番号（つまり、最も左）の非基本列を選択します。
2. 次に、行の中から、（変換された）右側とピボット テーブル内の係数（係数が 0 より大きい）の比率が最も低い行を選択します。最小比率が複数の行で共有されている場合は、基本となる列番号が最も小さい行（変数）を選択します。

Bland の選択規則により、単体アルゴリズムが循環することはなく、制限された時間内に終了することが保証されることが正式に証明されます。

ブランドのピボットルールは理論的には重要ですが、実用的な観点から見ると非常に非効率的で、収束に長い時間がかかります。実際には他のピボットルールが使用され、サイクリングはほとんど発生しません。^{[4] : 72–76}

有向マトロイドの抽象的な設定では、Blandの規則はいくつかの例で循環する。Blandの規則が循環を回避する有向マトロイドの限定されたクラスは、ジャック・エドモンズによって「Bland有向マトロイド」と呼ばれている。別のピボット規則であるクリスクロスアルゴリズムは、すべての有向マトロイド線形計画法で循環を回避する。^[5]

• ブランド、ロバート G. ( 1977年5 月)。「シンプレックス法のための新しい有限ピボット規則」。オペレーションズリサーチの数学。2 (2): 103–107。doi :10.1287/moor.2.2.103。JSTOR 3689647。MR  0459599  。
• George B. Dantzigと Mukund N. Thapa。2003 年。『線形計画法 2: 理論と拡張』。Springer-Verlag。
• Katta G. Murty、「線形計画法」、Wiley、1983年。
• Evar D. Nering とAlbert W. Tucker、 1993 年、「Linear Programs and Related Problems 」、Academic Press。
• M. Padberg、「線形最適化と拡張」、第 2 版、Springer-Verlag、1999 年。
• Christos H. Papadimitriouおよび Kenneth Steiglitz、「Combinatorial Optimization: Algorithms and Complexity」、新しい序文を付けて修正再出版、Dover。(コンピュータ サイエンス)
• Alexander Schrijver 著『線形計画法と整数計画法の理論』 John Wiley & Sons、1998 年、ISBN 0-471-98232-6 (数学) 
• Michael J. Todd (2002年2 月)。 「線形計画法のさまざまな側面」。数学プログラミング。91 (3): 417–436。doi :10.1007/s101070100261。S2CID  6464735。(国際数理計画シンポジウムからの招待調査。)