Google スプレッドシートアドオン-Linear Optimization

Google Sheets の Add-onとして線形最適化問題が解けるものが提供されているようなので,触ってみた.

Linear Optimization - Google スプレッドシートアドオン

サービス->Google Optimization

アドオンをインストールしてシートを開き,メニューから,「Add-ons」->「Linear Optimization」->「Set up optimization sheet」を選択することで,線形最適化問題を入力できる状態になる.上に示したウェブページ「Linear Optimization - Google スプレッドシートアドオン」の「A simple example」に例題が載っているのでそのとおりにすればよい.

まずは変数を定義する.シートの右に「Describe data」という窓があるので,「Variables」を選んで,変数名(Variable name),タイプ(Type,連続変数か整数変数か),下界(Lower bound),上界(Upper bound),目的関数における係数(Objective coefficient)を入力してAddボタンを押す.すると,D列のセルD1から下に,設定した内容が表示される.これを変数の数だけ繰り返せばよい.新しく変数を追加すると,右側の空いている列に追加で表示される.窓から入力するのが面倒であれば,空いている列のVariable NameからObjective Coefficientまでのセルに直に値を入力しても動くようだ(仕様は知らないが,やってみたら動いた.)

「A simple example」の例題を入力してみた.まず,変数xとyを定義する.次に, x+2y<=14を加えるとする.これに制約式名 Swordsとつける. 「Describe data」窓で「Constraints」を選択し,「Constraint name」で「New constraint」を選択すると,「New constraint name」という欄が出ている. ここには,制約式の名前Swordsを入れればよい.そして,「Upper bound」には,14を入力する.この制約式には下側の値は設定されていないので,デフォルトの値-Infinityとしておく.これで,「Add」ボタンをクリックすると,スプレッドシートのセルに値と文字列が入力される.

この時点では,線形式x+2yはまだ設定されていない.制約式Swordsは,-Infinity <= (空っぽの線形式) <= 14という状態である.なので,Swordsに線形式x+2yを設定する.そのためには「Constraint name」でSwordを選ぶ.そうすると,「Variable name」の下で変数を選択できる状態になる。そこで,変数名xを選択し,その変数に設定したい係数1を「Variable coefficient」に入力し「Add」ボタンをおす.すると,スプレッドシート内のxに対応する列の,Swordに対応する行に,1が表示される.次に,「Variable name」で変数yを選び,「Variable coefficient」に2を入力し,「Add」ボタンを押す.すると,スプレッドシート内のyに対応する列の,Swordに対応する行に,2が表示される.これで,x+2y<=14が定義された. 同様の方法で,例題の残り二つの制約式PlowsharesとPensも定義できる.

制約式の定義は,上のようにシート右側に出ている「Describe data」から入力するのが間違いがない.制約式を定義するもう一つの方法として,シートのセル内に直接書き込む方法がある.ひとつ制約式を定義したとする(例えばSword).そしたら,そのセル,具体的にはA8セルのSwordからG8セルまでを横にコピーして,制約式がかかれた部分の最後の行の下(「Constraint Name」と書かれたセルから下のセルを辿ったときの最初の空白セル)に貼付ける.そして,その行のセルの内容を書き換えればよい.そうすれば新しい制約式が定義できている.

変数と制約式を追加したら,メニューから「Add-ons」->「Linear Optimization」->「Solve」 を選ぶ.最適解が得られれば,変数が書かれた青い部分のSolution Valueのところに解が入る.実行不能だったりUnboundedだったりすると,それを知らせるポップアップが出る.

さて,整数変数が含まれている問題も解けるらしい.整数変数が含まれているときにはSCIPで解くようだ.ということで,この例題の変数xを整数として指定してみる.その前に,制約式Swordでの変数xの係数を1.5に変えておく.というのも,1のままだと最適解がxもyも整数になっているから,xを整数にしてSolveしても何も変わらないから.係数を1.5に変えて再度Solveを選択して解くと,解は,(x,y)=(1.867,5.6)と小数になる.さて,変数xのTypeを指定しているセルD2の値をCONTINUOUSからINTEGERに変更する.これで変数xは整数変数になった.そして,Add-ons->Linear Optimization->Solveを再度実行する.これで得られる解は(x,y)=(5,3.25)となる.確かに変数xは整数になっている.

「Add-ons」->「Linear Optimization」のところに,Add varaibles...というのとAdd constraints...というのがあるのだが,何に使うのか今のところ分からない.

変数と制約式は,別途テキストファイルに用意したデータをコピペして定義することもできる.スプレッドシートのなかの変数を定義する部分をタブ区切りのテキストデータとして用意すればよい.具体的には

x[タブ区切り]y
CONTINUOUS[タブ区切り]CONTINUOUS
-Infinity[タブ区切り]-Infinity
Infinity[タブ区切り]Infinity
2[タブ区切り]4

というテキストファイルを用意して,コピーする.それを,「Variable Name」の右のセル(D1)に貼付ける.そうすると,変数が定義できる.

制約式も同じ要領でコピペで定義できる.このとき,不等号は空欄にしておくのがこつだ.

Constraint Name[タブ区切り]Constraint Lower Bound
Sword[タブ区切り]-Infinity[タブ区切り][タブ区切り]1.5[タブ区切り]2[タブ区切り][タブ区切り]14
Plowshares[タブ区切り]0[タブ区切り][タブ区切り]3 -1[タブ区切り][タブ区切り]Infinity
Pens -Infinity[タブ区切り][タブ区切り]1 -1[タブ区切り][タブ区切り]2

要は,スプレッドシート内のだいだいの部分を忠実に書けばよい.その際,セルの区切りはタブにすればよい.そして,不等号は空欄にしておく.このテキストをセルA7に貼付ければ,制約式が定義できる.このとき,変数が定義されている列とずれないように注意する.

HPには,次のような文があるので,あくまで小さな問題を解くためのしくみなのかもしれない.

The API has a timeout of five minutes, rather than the add-on's two minutes, so it's better-suited for larger optimization problems.

Google Optimizationというページがあるのだけど,記述はあっさりしているし,このLinear Optimizationのアドオンも研究のツールとしてがんがん使う類いのものかどうかはいまのことろわからない.しかし,SCIPがGoogleスプレッドシートから呼べるというのは使いでがある気がする.問題は,上記の「5分」という制限かもしれない.整数計画を解くのに5分の制限があるとしたら,短すぎる.