Cassowary (Incremental Simplex)を雑に理解した

UI とかの業界で使われているアルゴリズムを雑に調べた

参考文献

オリジナルの論文が一番わかりやすい（というかそれ以外の資料があまりみつからない）

• 総本山のWebサイト: https://constraints.cs.washington.edu/cassowary/
• 論文
  • 最近のヤツ: https://constraints.cs.washington.edu/solvers/cassowary-tochi.pdf

必要となる前提知識

• シンプレックス法

シンプレックス法はもとより、二段階シンプレックス法に関しても理解していないと Cassowary を理解するのは難しい。あと、双対シンプレックス法に関しても多少の知識が必要。私もつい先日勉強した: 「シンプレックス法を雑に理解した -Qiita」

1. 解きたい問題

Cassowary で解きたい課題は線形計画問題なんだけど、標準形の線形計画問題を少し変形したものを対象とする。

まずはおさらい。標準形の線形計画問題:

• 全変数に 非負制約
• 目的関数を 最小化 することがミッション
• 制約は全て 等式制約

で、Cassowary で解きたい課題は上記標準形を少し変形したもの:

• 要件1: 非負制約がつかない変数が存在しうる
• 要件2: 満たさなくてもよい制約が存在する
  • 制約間に重要度の差がある
• 要件3: インクリメンタルに解ける
  • 制約を追加・除去・微修正した際に問題を効率よく解く

ユースケースは、WebブラウザやGUIアプリケーションにおけるレイアウト問題

2. 非制約変数の扱い

「要件1: 非負制約がつかない変数が存在」と第一章で記載した。それについて。

標準的なシンプレックス法でも非負制約がつかない変数(非制約変数)を扱えた。具体的には非制約変数 x に対して非負変数 u, v を持ち出して、x = u - v として、解きたい課題から x を除去して代わりに u, v を導入するという方法だ。しかし、もっとよい方法があるらしく、Cassowary ではそっちの方法を使う。

全部で N 個の変数があって、K 個の非制約変数があって、M 個の等式制約があるとしよう。イメージとしてはK 個の非制約変数の存在は ラッキー なのだ。なぜなら非制約変数は制約がない分あとから自由に決められるから。例えば以下のように非制約変数が制約変数で以下のように規定されていたとする:

$$x_u = 100 - 2X + 3Y$$

非制約変数 x_u は X, Y の値が決まったら上の式に代入した値を使えばよい。非負条件がないのでマイナスになっても構わない。このように考えると、 K 個の非制約変数が存在する最適化問題を以下のようなイメージでとらえ直すことが出来る:

• K 個の自由度の高い変数
  • M 本の等式制約のうち、K 本の等式制約は非制約変数の値を与えるために充てられるので事実上制約でなくなる
• より解きやすい標準形に帰着
  • M - K 本の等式制約
  • N - K 個の非負変数

3. 制約とその表現

「要件2: 満たさなくてもよい制約が存在する」と第一章で記載した。それについて。

解きたい問題には、満たさなくてもよいができるだけ満たしてほしいというクラスの制約がある（これを制約と呼ぶのか、ヒントと呼ぶのか、プリファレンスと呼ぶのか、という議論はあっていいように思う）。Cassowary では以下のように制約をカテゴライズする:

• Required: 必ず満たさねばならない制約
• Strong: Edit制約に使われる強めの制約
  • Edit 制約: 値をユーザが指定するタイプの制約
    • 例: Window 幅を 800px にしたい
    • 例: 月曜日の残業時間は 0 時間にしたい
• Weak: Stay制約に使われる弱めの制約
  • Stay 制約: 特に理由がなければ現在の値のままでいてほしい
    • 例: Window 幅が小さくなっても画像の幅は現在の100 px のままにしてほしい
    • 例: 月曜日は残業しなくても、総残業時間は 30時間に保ちたい

上記では、Required, Strong, Weak の三種類でカテゴライズしたが、理論上はもっとたくさんあってもよい。実際、Cassowary の実装では、Strong と Weak の間に、Medium という強さのカテゴリを用意している。

制約充足の優先度

Cassowary の精神では、強いカテゴリの制約の充足が 弱いカテゴリの制約の充足に完全に優先される。例えば、Strong の制約が充足されるまで、Weak 以下の強さの制約は参照すらされない。同じ強さの制約が複数ある場合は、それらは対等に扱われる（後述のように重みを付けて重要度に傾斜をつけることも可）。

制約の充足ぐあいを値で測る

制約を満たしてもよいし、満たさなくても許容されるのであれば、制約の充足具合を単に OK, NG の二値で測るのは不十分である。そこで制約の充足具合を数値で表すという発想が出てくる。前述のように、Edit制約やStay制約は「x の値をできるだけαにしろ」という形をとる。そこで、α からのズレ（絶対値）を制約違反ペナルティとして定義する（正確には error function というらしい）ことで、制約の充足度を数値化できる。同じ強さの制約におけるペナルティの総和を最小にするような値付けが、制約を最も充足するとみなすのである（同じ強さの制約でも重みづけをすることで重要度を表現することも可能）。

最適性
まとめると最適解が満たすべき条件とは以下のようなものだ

• Required な制約 をすべて満たしており、
• Strong な制約における制約違反ペナルティの重み付き総和が最小となるものの中で、
• Weak な制約における制約違反ペナルティの重み付き総和が最小となる値付け

なるほど。と思う一方、あれ？目的関数の最小化ってお題はどこにいったの？線形計画って目的関数の最小化がミッションじゃなかったんだっけ？という疑問がわく。それは次の章で。

4. 問題の再定義

前章の最後でも問題提起したが、Cassowary での課題感は 普通の線形計画問題と 結構異なる。

普通の線形計画では、N個の変数に値して、M (<= N) 個の制約があるので、制約をすべて満たしてなお、N 個の変数の値付けには任意性がある。その任意性の中で目的関数を最小とするような値付けを探すというメンタルモデルであった。

一方、Cassowary では、N個の変数に対して課された制約をすべて満たすことが難しい（ことが多い）。そこで、制約違反ペナルティをできるだけ小さくするような値付けを探す、というのが基本的なメンタルモデルになる。このように目的関数に制約違反ペナルティを組み込む、というのがCassowary での大きな特徴となっている。

5. インクリメンタルと向き合う

「要件3: インクリメンタルに解ける」と第一章で記載した。それについて。

「Window 幅を広げたいのでマウスで Window の端をつかんで 800px になるように D&D する」のように、似てるけど少し違う最適化問題を解かなくてはいけなくなる。このようにインクリメンタルに解く必要があるのだが、主なユースケースは以下の3つ:

• 1. Edit/Stay 制約の変更
  • 例: Window をずらしてディスプレイの真ん中に置く
• 2. 制約の追加
  • 例: 新しいWindowを配置したいので、既存のWindowの右端は 座標500 にする
  • 初期実行可能基底解を求めるのにも使う(シンプレックス法の最初の一歩)
• 3. 制約の除去
  • 例: 略

最適解が得られている状態（＝適切な基底変数を選択し辞書が得られている状態）で上記のように問題設定に変更があった時に、可能な限り計算量が少なく（≒ピボッティングの回数を少なく）新しい問題の最適解が得られている状態に持っていく方法を見つけよう、というのが趣旨である。

特に重要なのは 1. の制約の変更である

Stay & Edit 制約の変更に伴う最適解の見つけ方
結論から言うと、以下の順序でやると上手くいく

• stay 制約変更に対応する
  • 何もしなくてよい (対応するエラー変数が非基底の場合)
  • 辞書における定数部を 0 にする(対応するエラー変数が基底の場合)
• edit 制約変更に対応する
  • エラー変数（のペア）にオフセットを付ける（両エラー変数が非基底の場合）
    • 必要があれば再度ピボッティングを行う(双対シンプレックス法）
  • 基底側のエラー変数に押し付ける（エラー変数の片方が非基底の場合）

ハイライトは edit変数の修正にともなう双対シンプレックス法の適用。edit 変数値を変更しようとすると、辞書の定数部が負になりえて、「実行不能だけどオプティマル」な辞書が出来上がってしまう。これを「実行可能でオプティマル」にするために双対シンプレックス法で使うようなピボッティングが使えて、数回のピボッティングで最適解にたどり着ける。それ以外の場合はそもそもピボッティング不要で最適解にたどり着く。

制約追加
基本的には二段階シンプレックス法の第一段階と同一なのだが、もう少しだけ効率よくやる方法がある

追加制約は等式制約としてよい（不等式制約の場合はスラック変数を導入して等式制約に変換）し、既知の非制約変数や 基底変数を含まないとしてよい（あれば代入して消しちゃえばよいだけ）。制約に登場する変数に非制約変数が含まれている場合は、非制約タブローに組み込んでしまえばよいだけ。そうではない場合、制約タブローに新たに制約が加わることになり、実行可能基底解を探すために人工変数を導入して二段階シンプレックス法の一段目のロジックを回す必要があるのだが、一目見て実行可能基底解があるかチェックしてからでも遅くない。具体的には、制約の定数部と符号が逆の係数を持つ非既知な変数があるかをチェックするということ。もしあればラッキーで、実行可能基底解を得られたことになる。ないなら仕方ないので二段階シンプレックス法を解く。

興味深い結果は、Requiredでない制約を追加する際には人工変数の導入が不要（実行可能基底解導出のために第一段シンプレックス法を利用する必要がない）という点。簡単に証明できる。

制約削除
制約に紐づくマーカー（スラック変数やエラー変数があればそれが使えるしなければ人工的にくっつける）を用意し、その影響を明確化して削除する。

要はマーカー変数を基底変数に選んで辞書をつくれば、その行以外に消去したい制約の影響が伝播していないことがわかるので、その行のみを消去すればよいということになる

感想

そんなに難しいわけではないんだけど、シンプレックス法を完全に理解していないとつらい部分があった。