線形制約の矛盾判定アルゴリズム

最適化アルゴリズムを実装する際など、さまざまな場面で遭遇する、線形な制約式
\begin{align*}Ax\ge b\hspace{20pt} A \;:\; m\times n\text{ matrix}\end{align*}
を満たすベクトル x が存在するかどうかを判定する問題について考えてみます。

行列 A を正方行列として、連立一次方程式 Ax=b が一意解をもつか、という問題設定ならば行列 A がフルランクであるかどうかが問題になりますが、今考えている問題設定では A のランクは関係ありません(つまり行列がランク落ちしていても解が存在することもあるし、フルランクでも解が存在しないこともあります)。

実践的な方法として、線形計画法のソルバーが利用可能であるならば、
\begin{align*}\text{maximize}\hspace{10pt} \sum_i\; x_i\end{align*}
\begin{align*}\text{subject to}\hspace{10pt} Ax\ge b\end{align*}
という問題を解いてみて “Model is infeasible” な例外が出なければOKとする方法が簡単でしょう。

ここではもう一歩踏み込んで「システマティックに矛盾を検出するアルゴリズム」について考えてみます。

“線形制約の矛盾判定アルゴリズム”の続きを読む

firefox/google chrome でメイリオをアンチエイリアシング

windows xp で firefox を使っていると、さまざまなサイトでフォントがカクカクとして汚いページを見かけます。この原因はウェブページのフォントがメイリオ系に指定されていることが原因です。メイリオ系のフォントは Vista 以降に標準搭載されるようになったので、xp ではインストールが必要です(ただし windows update でインストールされるので入っている人も多いはず)。

最近はメイリオを標準フォントにしているウェブサイトも多いので(このサイトもそうです)汚いフォントはストレスになります。Internet Explorer な人々(IE7以降)はメイリオをインストールするだけできれいに表示されるらしいですが、firefox/chrome などの「非M$」なブラウザではインストールしただけではアンチエイリアシングがかからないため、設定が必要です。といっても設定は非常に簡単で

「画面のプロパティ(デスクトップの何もないところで右クリック→プロパティ)」 → デザインのタブ → 効果 → 「次の方法でスクリーンフォントの縁を滑らかにする」にチェック → Clear Type を選択

とするだけです。

また、google chrome には「強制メイリオちゃん」という拡張機能があって、これをいれると何でもかんでもメイリオフォントにしてくれます。