カーマーカーのアルゴリズム
以下の線形計画問題を考える。
maximize x 1 + x 2 {\displaystyle x_{1}+x_{2}}
subject to 2 p x 1 + x 2 ≤ p 2 + 1 , p = 0.0 , 0.1 , 0.2 , ... , 0.9 , 1.0. {\displaystyle 2px_{1}+x_{2}\leq p^{2}+1,\quad p=0.0,0.1,0.2,\ldots ,0.9,1.0.}
上記には、2つの変数 x 1 , x 2 {\displaystyle x_{1},x_{2}} と、11の束縛変数 p {\displaystyle p} がある。本節の例解図には、アルゴリズムを繰り返し実行するごとに赤い円が点描されることと、青い直線は束縛境界であることが示されている。