2020-04-29

Model Building in Mathematical Programming: Chapter 1, Chapter 2

Optimization Night で H. Paul Williams, Model Building in Mathematical Programming, 5th Edition, Wiley, 2013. の輪読会をしているので、そのメモです。

Chapter 1

1.1 The concept of a model

ここでは「モデル」という言葉のコンセプトについて議論。数理最適化もしくはオペレーションズ・リサーチの文脈では抽象的な数理モデルを指すことが多い。機械学習や物理学の文脈でも「モデル」という言葉がでてきて、それぞれなんとなくイメージしている抽象度が違いそうなので、コミュニケーションの際には注意が必要そう。京都大学のページにもあるとおり、数理最適化は

問題のポイントを整理して数学モデルを作成する．
モデルの特性を考慮した適切な方法（アルゴリズム）を用いて解を求める．
得られた解をもとに現実の問題の解決策を実施する．

というステップを踏むことになるので、「モデル」のコンセプトを理解して「アルゴリズム」と区別するのはとても大事。

あまり本筋とは関係ないですが、本書ではオペレーションズ・リサーチのことを operations research ではなく operational research と書いてあります。 Wikipedia によると、 operational research はイギリス英語らしい。

Chapter 2

2.1 Algorithms and packages

既存のパッケージ（Gurobiなどのソルバー）は長年の研究の成果を泥臭く実装していて、素人に手を出せるようなものではないので、むやみにアルゴリズムを実装したりせず、既存のパッケージを利用しましょう。昔 cbc (Coin-or branch and cut) という数理最適化ソルバーのコードを読み解こうとしたのを思い出しました。

既存のパッケージの多くは、以下のような典型的な制約を簡単に記述する機能が備わっていて、そういった機能を使うと効率的に計算してくれることがあるので、できるだけ使ったほうが良さそうです。（最近のパッケージでは自動的に判定して効率的な計算をしてくれるものもあるようです。）

Simple bounding constraints:
- $L \leq x \leq U$
Ranged constraints:
- $\sum a_j x_j \leq b1, \sum a_j x_j \geq b2$
Generalized upper bounding constraints:
- $x_1 + x_2 + \cdots + x_n \leq M$

あとは適切な初期解を与えるのも計算時間の短縮に効果的。また、Sensitivity Analysis (感度分析) についてもふれていて、少し議論ができて楽しかったです。

2.2 Practical considerations

既存のパッケージには、計算結果（途中結果を含む）を保存する機能がついていることが多いので、それを活用しましょう。数値を少しだけ変えた問題を解く際に初期値として使うこともできるし、計算リソース等の関係で、途中で計算をやめて再開したいケースもある。コメントもあったけど、このあたりは機械学習周りと感覚が似ている。（というか機械学習がそもそも数理最適化問題の一種なので当然といえば当然かも）

2.4 Constraint programming

ここでは CP (Constraint programming) と IP (Integer Programming)との関係についても触れています。個人的に CP に興味があるけど全く触ったことがなかったし、イメージもよくわからなかったので、とても助かった。 CPとIPは、もともと別の文脈で発展していて、コミュニティも別だったりするけど、同じ問題を解けたり解けなかったりするので面白い。CPの方が少ない実行可能解を見つけるのは得意だが、巡回セールスマン問題のような大量の実行可能解から最適なものを見つけるのは苦手なんだそうです。また、CPでは、以下のようなglobalな制約を記述できるので、見通しが良くなりそう。(IPとして記述できるけど、変数が増えたり定式化が複雑になったりして大変そう)

${\rm all\_different}(x_1, x_2, \dots, x_n)$
- $x _ i$ がすべて違う値
$\neq$
- 普遍と左辺が異なる値
${\rm card_m}(x_1, x_2,\dots,x_n|v)$
- cardinality. ちょうど $m$ 個の値が $v$
${\rm cumulative}((t_1, t_2,\dots,t_n), (D_1, D_2,\dots,D_n), (C_1,C_2,\dots,C_n), C)$
- 時刻 $t_i$ にスタートして $D_i$ の時間と $C_i$ のリソースを消費するジョブが $n$ 個あった時に、利用リソースが常に $C$ を超えない
${\rm circuit}(x_1,x_2,\dots,x_n)$
- $(x_1,x_2,\dots,x_n)$ が順列になっている
${\rm element}(j, (x_1, x_2,\dots,x_n), z)$
- $z$ が $(x_1, x_2,\dots,x_n)$ の $j$ 番目の要素と等しい
$(x_1, x_2,\dots,x_n) >_{lex} (y_1, y_2,\dots,y_n)$
- 集合同士の大小関係 (ある $r \leq n$ があって、 $x _ 1 = y _ 1,\dots,x _ {r-1} = y _ {r-1},x _ r>y _ r$ の場合に true)

TODO

12.1 Food manufacture 1 を解く
2.1 に出てくる REDUCE, PRESOLVE, ANALYSE がそれぞれ何を指しているのか確認する

2019-11-10

イベント盛り上げるのに良いな、と思ったサービス: Kahoot, Sli.do, SwapCard

アメリカの技術イベントに参加して、そこで使われていていいなと思ったサービスをまとめておこうと思います。

Kahoot

kahoot.com

Kahoot は、簡単にいうとクイズを簡単につくれるサービスです。スマフォを使ってリアルタイムに出題 > 回答 > 採点（早いほどポイントが高い） > ランキングができて、けっこう盛り上がります。

単なるクイズプラットフォームではなく、教育にゲーミフィケーションを持ち込むことを目的としていて、学校の授業や企業のオンボーディング用に用いられているようです。教育者観点での使用感はこちらの記事(PDF)にまとまっていますが、学校の授業で盛り上がらないはずはないし、教育的な効果も期待できるし、とても良いサービスな気がします。

ただ、企業のオンボーディングでつかうイメージが正直わかない。大企業だと違うのかな...。リアルタイム性が売りだと思うので、一定以上の人数が同時に入社研修うけたりしないと意味がなさそう。全体会議の最後にコンプライアンステスト、みたいなのは意味がありそう。

Sli.do

sli.do

Sli.doはこれまでも何回か利用経験があるのですが、聴衆から質問を集めるサービスです。LTとか、時間が決まっていて質問しづらい、会場が広すぎてマイクを持っていくのに時間がかかる、リモート参加の方にも同じ質問機会を与えたい、質問内容を運営側がある程度フィルタリングしたいなど、色々状況で有用なサービスだと思います。

Swapcard

www.swapcard.com

最近のイベントでは、専用のイベントアプリがあって、それを使ってセッションのリザベーションやリマインド、開催会場の確認ができるようになっていることが多いです。Swapcard はイベント & ネットワーキング用のサービスで、開催するイベントの情報の表示や参加者の一覧ができて、イベントアプリを0から作る必要がなくなります。使い勝手は個人的には「まぁ普通」と言ったところでしたが、周りの評判はとても高かったです。常々感じていたのが、イベント毎にアプリインストールするの面倒くさいし、微妙に使い勝手も違うし、ものによっては質も悪いし、なんとかならないかな、ということだったので、こういったサービスを使って、一本化してもらいたいなぁと思いました。

セッションが複数あるような、ある程度大きいイベントでないと意味がない気がするので、直近で自分が利用する機会はなさそうですが。

2019-10-22

TensorFlow UserGroup で話す時用のMarpのスライドテーマを作った

これまでは Google Slides を使うことが多かったのですが、毎回そんなに複雑なことをするわけでもないので、Markdown でお手軽にスライドを作成できるように、 Marpのテーマを作りました。

github.com

↓みたいな感じの Markdown を書くと

# Your Name

- a
- b
- c

![your logo](assets/logo.png)

↓みたいなスライドに変換されます。

f:id:ohtaman:20191022214522p:plain — 生成されたスライド

これでスライド作成がはかどります。

Marp とは

Marpはyhattさんが開発している、 Markdown記法からスライドを生成するアプリ・ライブラリのことです。もともとはPDFに出力して使うことを想定されていたようですが、現在はHTML出力も可能になっています。CSSを記述することで独自のテーマを適用することもできます。

Markdown記法からスライドを生成する方法は、Marp以外にも色々あって、たとえばreveal.jsが有名だと思います。あと、Qiitaに書くような内容に限るのであれば、Qiitaのスライドモードを使うのが手っ取り早いと思います。そんな中で、Marpは日本初ながら

余計なことをしないので、独自テーマが使いやすい
Visual Studio Code の拡張機能が使いやすい
Qiita のようにサービスの制約を受けない / 完全にローカルでプレビューを見ながら執筆できる
開発も活発に進んでいる（ように見える）

という点で、とても良い立ち位置にいると思います。

スライドを Markdown で記述するメリット

エンジニアであれば誰でも Markdown は記述できる点、専用の（高価な）ソフトが不要な点、テキストなのでバージョン管理が楽である点などいろいろありますが、個人的には、できることが限られているので、（結果的に）調整に時間が取られないというのが一番のメリットだと思います。

スライドをMarkdown で記述するデメリット

一方で、デメリットもあります。例えば、共同編集には弱い点。共同編集は、Google Docs や Office 365 であれば標準で備えている機能で、複数人で1つのスライドを作り上げていくような場合だと重宝するというか、なくてはならない機能だと思います。Markdownで記述する場合は、Markdownを共同編集できるような環境を別途作らなければいけないというデメリットがあります。共同編集という意味だと、会社ではエンジニアと営業が協力して1つのスライドを完成させるようなケースも多いと思いますが、正直営業さんに Markdown を強要する勇気は僕にはありません。

また、Markdown でできる範囲は限られているので、その範囲からはずれたことをやろうとすると、とても時間がかかってしまうというのもデメリットかもしれません。（ただ、これは必要以上に作り込まなくなるというメリットと裏表でもありますが...）

ちなみに、Markdown だけの機能だと、ダイアグラムのようなものを記述することはできないのですが、Marpでは、一度HTMLに変換してから必要に応じてPDFに変換しているため、mermaid.js のような、JavaScriptのライブラリを使ってダイアグラムを記述することができます。

執筆環境について一言

Markdown から HTML/PDF への変換方法には、marp-cli というコマンドを利用する方法、Marpをライブラリとしてnodeから呼び出す方法、対応しているエディタの拡張機能を利用する方法などがあります。

普段 Visual Studio Code（vscode）を利用しているのですが、Marp拡張 marp-vscode を入れると、プレビューを確認しながら書きすすめることができるのでとても便利です。

プレビューが自動更新される
Markdownそのものではなく、適用しているテーマのcssを更新してもプレビューが更新されるので、独自テーマの作成がとてもはかどりました。
テーマとしてリモートのcssも指定できる
これは marp-cli だとできないように見えますが、今回のようにテーマを公開したい場合にはとても重宝される機能だと思います。