最適化一口話

仕事として数理最適化を実践している立場から、その中身や可能性について概説しております。

「習うより慣れろ」で始める数理最適化:「集合被覆」の例題

車両 1~5 と、部品工場A ~ F との対応を示している表があります。 どんな状況が想定されるでしょうか? f:id:optimizationTanabe:20161109170927p:plain

ここはあるメーカーの本社組み立て工場。 操業には部品工場(A~F)からの部品を仕入れて来る必要があって、 この表は仕入れをしている 5台の車のそれぞれが、 今日、仕入れ先のどこを回ることになっているかを示しています。なぜこの表が必要になったかというと、 急ぎで今日中に各部品工場すべてに届けたいものが生じたのです。仕入れのついでに持っていってもらうことにしようと思いますがどの車に頼めば、すべての部品工場を網羅できる(カバーできるか)か決めたい、とします。 すべての部品工場を網羅している車はないので、複数の車に頼む必要がありますが、できるならば最小限の車に頼むことで済ませたいのです。

この問題は「集合被覆問題」というなかなか使いでのある数理最適化の例題になるので Excel を入口にして、数理最適化という道を辿ってみます。 まず、どの車に頼むかどうかの選択をセルに入力すると、部品工場がカバーできるかがわかる、という表を作りましょう。以下はイメージです。

f:id:optimizationTanabe:20161109171012p:plain

さて、これを例えば Excel で作るにはどうすればよいかです。方法は一つではないですが、○×のままだとしんどい。文字を数字に置き換えて、Excel の数式が使えるようにする案が定番として浮上します。慣れている方ならば、元の表と連動させて、次のような表を新たに作ることは造作もないことかと思います。 具体的には、黄色のセルに、各車両に実際頼むかどうかを 0-1 で入れ、IF 関数を使って、○を 1 で、空白セルを 0 で置き換え(オレンジの部分)、緑のセルには SUMPRODUCT を使って、各工場がカバーされたら 1 以上の値が入るようにしておきます(下図)。

f:id:optimizationTanabe:20161109171100p:plain

黄色のセルを変化させると、緑のセルの値が瞬時に変化するはずです。 ま、実際この程度ならばこの表を見ながら試行錯誤するので十分ですが、せっかくですから数理最適化で「逆算」してみましょう。逆算とはすなわち数理最適化に、緑のセルの値がすべて1以上の値になるような、黄色のセルを設定させるわけです。

f:id:optimizationTanabe:20161109171150p:plain

ここからは数理最適化ソフトが必要になります。それぞれ固有のやり方を覚える必要がありますが、黄色のセルを「変数」と定義して、緑のセルに定義されている数式を制約、黄色のセルの和を目的関数として教えます。 数理最適化ソルバーが導いた答は次です。

f:id:optimizationTanabe:20161109171240p:plain

車1と車4に頼めば無駄なく回ることができることがわかります。一台ではカバーしけれなかったので、これは最適解になっています。Excel 技を使って、元の○×の表に結果を書き込んでみましょう。

f:id:optimizationTanabe:20161109171312p:plain

「数式臭さ」が抜けて、普通に人に見せてわかる、イメージした通りの表になっています。途中は○とか×を 1 と 0 に置き換えて途中の計算をわざわざ数字にしていました。これを理屈っぽく言うと「数理モデル化を行った」ということになりますが、これはつまるところ、Excel の数式を使うためで「便利」だからにすぎません。数理最適化でも同じ事情です。数理最適化でむやみやたらと数式に頼った記述は避けるべきと私は思っています。黄色のセルにはあくまで 0 か 1 しか入れることができず、0.4 とかいう値は入れられません(頼む、頼まないの二択なのに、意味が変になりますよね)。こういう変数を離散変数( 0-1 変数 ) と呼び、字義通り 0 とか 1 という意味ではなく、モデルの作り手により '○' とか'×' という意味を付与されています。

前回は「生産量」、という量そのものを変数にしましたが、実際の意思決定の場面では、このように「やる/やらない」とか、「どれを選ぶ」とかを決めることも多く、そこから現れる、離散変数を含む数理最適化問題は数理最適化の一大研究分野となっています。

今回は、「急ぎで各部品工場すべてに届けたい」という、突発的なニーズに対応しましたが、次は同じ表から出発して定常的なニーズに対応したモデルにしてみましょう。

「習うより慣れろ」で始める数理最適化:「生産計画」の例題 (2)

前回は Excel による集計表をベースに数理最適化のモデルを記述して、

f:id:optimizationTanabe:20161003092234p:plain

という表を得るところまで進みました。 丸で囲った「生産量」のところの数字が数理最適化の答です。 タイトル通り、面倒な解説は抜きで、どんどん数字を変えて数理最適化の応答を見てみましょう。 製品 A,B に対して同じ利益というのも面白くないので、適当に A は B の 2 倍の利益という設定にしてみます。

f:id:optimizationTanabe:20161003011121p:plain

利益は 80 とぴったりですが、 製品 A,B の生産量はなんだか微妙な数の答が出てきました。 在庫残りも絶妙(?)に調整されている風な値です。 製品Aの生産量、どうにも半端な 34.7 を 30 に切り捨ててみましょう。

f:id:optimizationTanabe:20161003011153p:plain

利益は減るところからみて、たぶん先ほどのは最適解だろうとは思うのですが、試みに製品Aの生産量を30のまま、残り原料在庫で製品Bを作れるだけ作ることにするとどうでしょう。 原料 q に着目すると (320-8×30)/4 = 20 だけ作れます。書き込んでみましょう。

f:id:optimizationTanabe:20161003011350p:plain

おっと、数理最適化の出した「最適解」と同じ利益 80 の解がもう一つ作れてしまいました! 実はこの場合、製品 A,B が原料 q を使う比率(8:4=2:1)と利益の比率(2:1)が一致しているので、一旦利益 80 の答を得てしまえば、原料 q を使い切るように比率を保ったままA,B の生産量を操作すれば、「最適解」が量産できてしまいます。 製品 A だけ作って原料 q を使い切る答もありそうです。320 / 8 = 40 作ればよいわけです。入れて確かめてみましょう。

f:id:optimizationTanabe:20161003011501p:plain

これでも利益 80 が得られます。 一般に数理最適化ソルバーが「最適解」だと言って答を返してきたからといって同等に良い答が他に存在しない訳ではないことにどうかご注意ください。言えているのはこれ以上良い答が存在しないことのみで、同等の答がこうして沢山あるのは実務的な数理最適化モデルを試行錯誤しているときには決して珍しいことではありません。

このような場合には「最適」の定義を見直してみましょう。上で示した3通りの答の原料の残り方を見てみます。最初に数理最適化が出した答 (製品A,製品B) = (34.7,10.7)だと

f:id:optimizationTanabe:20161003011559p:plain

(製品A,製品B) = (30,20)だと

f:id:optimizationTanabe:20161003011612p:plain

(製品A,製品B) = (40,0)だと

f:id:optimizationTanabe:20161003011624p:plain

実現されている利益は同じ 80 でも、こうして残り在庫を見ると決して等価な答とは言えません。「最適」の尺度が「利益」だけ、と単細胞なのでその実現方法は沢山あり、その結果として多くの「最適解」が出現してきてしまったのだとも言えます。そもそも残せばよい原料の在庫は数理最適化が「全自動」で決めるべきものではありません。今後の需要予測に基いて人間が行うものであり、数理最適化は人間のポリシーに従って実現値を導く役回り(意思決定の補佐)を振られるのが一般的です。試しに利益を固定して、原料r の在庫残りが 25 になるようにしてみましょう。実験は数理モデルを若干改修すればよいので実に手軽(数式表現が気になる方へ: 利益を 80 に固定し、原料rの在庫残りと 25 の差の絶対値を目的関数にします)。

f:id:optimizationTanabe:20161003092317p:plain

丁度合わせてきました。では、在庫残り 30 ではどうか?

f:id:optimizationTanabe:20161003092335p:plain

これでもぴったり合わせて来ます。 こうしてモデルが出す便宜上の「最適解」を見ながら、人間が対話的に条件を設定して結果を絞り込むのが数理最適化の実践的な使い方です。あれ、と思ったら人間が結果を打ち込むこともできる。これはまさに Excel の使いどころではないでしょうか。

次回はこの表の構造は同じまま数を拡張して別の問題にしてみましょう。            

「習うより慣れろ」表計算で始める数理最適化:「生産計画」の例題 (1)

「数理最適化は表に始まり表に終わる」というのは私が勝手に作った言葉ですが、 我々が普通に Excel などを使って作る集計表を数理最適化にかけると、集計結果が意図した感じになるよう都合良く数字を書き込んでくれたりします。ここから始まるちょっとしたシリーズでは表計算から最短コースで数理最適化の本質(の端っこ)に迫ってみます。

製品を2つ作れるとして、それぞれは 3つの原料を決まった量だけ使います。各製品を単位あたり作ったときの利益と原料の在庫の表が次のように与えられています。製品は A,B 、原料は p,q,r としています。

f:id:optimizationTanabe:20160923093532p:plain

製品 A を 1 単位作ると原料 p,q,r をそれぞれ 4,8,1 消費して、利益が 1 出ます(表を横に見る)。 製品 B も 1 単位生産で利益 1 を得ますが、所要する原料は微妙に異なっています。原料在庫も表に加えておきました。

さて、この表をちょっと拡張して製品の生産によって消費される原料の量や利益の欄を加えます。Excel の数式や関数を使って、オレンジのセルに値が入力されたら緑のセルに数字が出るようにしてみましょう。

f:id:optimizationTanabe:20160923093554p:plain

足し算と掛け算でもよいですし、"SUMPRODUCT" なら、なお簡単。 「生産量」を示すオレンジのセルについては絶対参照をうまく使うと簡単ですね。。 とかいうのはこの Web 上に溢れる Excel 関連の情報源を辿って頂くとしましょう。

できました。次は A,B の生産量の欄に 5,6 と適当に入れた場合の表の値です。 在庫はまだ余裕で利益は 11。

f:id:optimizationTanabe:20160923093626p:plain

「生産量」のセルをあれこれ触ると利益とか在庫残りがリアルタイムに変化します。 A の生産量を 7 にすると。。

f:id:optimizationTanabe:20160923093702p:plain

利益がちょっと増えましたね。もっと増やすにはどうしましょう。 原料在庫が許す限り生産すればよいのです。 まだ余裕ありそうですので、思い切って 30 ずつ作ると、

f:id:optimizationTanabe:20160923093748p:plain

あれあれ在庫をショートしてしまいました。これでは使えません。もうすこし減らして良いところを探りましょう。。

数理最適化を実感する上でこんなに良いツールはない、と良く思います。 これはただの Excel 演習で全然数理最適化じゃないだろうって? 確かに。でも我々が数理最適化にやらせているのはこの「生産量」セルの値についての試行錯誤の肩代りであり、Excel をはじめとする表計算は数理最適化ソルバーの操作を実演し、実感する格好のツールなのです。

さてここからは数理最適化ソフトが必要で、各ソフト固有のやり方を覚える必要がありますが、 数理最適化ソルバーに、何をすべきかという「ゲームのルール」(数理モデル)を教えるのは、このExcel 上で SUMPRODUCT とか使って数式を定義する操作とやっていることは本質的に変わりません。数理最適化ソルバーに、変数は「生産量」のセルの値であるということ、「生産量」セルの値を使って在庫残りは 0 以上でなくてはならないという制約を定義し、利益を最大化したいのだ、と教え込むことができたとしましょう。解かせてみます。 数理最適化ソルバーの答が返したのは 製品A,B をそれぞれ 28,40 作る利益 52 の計画でした。

f:id:optimizationTanabe:20160923093818p:plain

ご存知の方も多いと思いますが、じつはこの例、 数理最適化の教科書の「導入」の定番なのです(ふと思い立って私の周りにある本、和洋とりまぜて 11冊を調べてみたら、じつに 8 冊がこの例題に類するものを導入に使っていました)。 ただ A,B = 28,40 という、一つの結果から得られる情報には限りがありますから、 教科書の書かれた頃よりもおそらくは恵まれた計算機環境を手にしている、というアドバンテージを活かし、数字をいろいろ替えて試しながら数理最適化というやつのお手並みを体感してみましょう。 ぱっと見わかるのは q,r の在庫を使い切る答になっているということ(表で使い切られた原料は色付けしています)。原料がすべて余っているならば製品にしてしまえばよいわけで、これは確かに妥当な動作である感じがします。では原料 r の在庫を 105 に増やしてみましょう。

f:id:optimizationTanabe:20160923093855p:plain

増やした r をまた使い切って 1 利益が増えました。 では思い切って r の在庫を 120 にしてみます。

f:id:optimizationTanabe:20160923093941p:plain

あんまり素直に利益は増えません。r を使い切ることができてません。 原料 p,q の在庫が使い切られているところを見ると、今度は p,q が頭打ちになっているのだなとわかります。 原料 q の在庫を増やしてみましょう。

f:id:optimizationTanabe:20160923094010p:plain

無事 q の在庫を使い切って利益を増やす答になっています。 こうやって試していると、(求めたかったはず)の生産量の値より、 どの在庫を使い切っているかというところから結果を理解する方が容易なことがわかります。 実は、数理最適化の教える知見の一つに、

  丁度満たされている制約(使い切っている在庫)によって答が決まる。

という事実があります。特に数理最適化が求めようとしている量の一次の式(定数倍の和)によって問題が表現されている線形計画法の場合、どの製品の在庫が使い切られているか、という情報は答の情報と等価である、とすら言えてしまいます。もちろんどの製品の在庫が使い切られているかを知るために目的関数を参照しているのですが、出てくる結果を陽に支配するのは制約式の方で、だから目的関数のウエイトをいじっても結果が付いてこない・・といったことが起きます。

教科書だと、次のような感じのグラフが出てきて

f:id:optimizationTanabe:20160923094052p:plain

結果を「解析的に」(要するに筆算)で求め、 どうして最適と言えるのか説明したり、一般的な解き方を解説したり、さらには「双対変数」とかいうじつに不可思議な量の説明に入ってしまうのですが、じつは、こういう知識はツールとして実務的に数理最適化ソルバーを使い出す上では不要。 Excel 上に問題を表現した段階で、数理最適化を始める準備(数理モデル化)はもうできています。 「習うより慣れろ」でどんどん動かすことで、知見を得てゆきましょう。そうする中で教科書を読んだだけではわからない事実も見えてきます。

次回はこの生産計画のモデルをもうすこし触って、数理最適化の性質に迫ってみます。

数理最適化に意思決定ができるのか?

倉庫には容量以上の在庫は入らない。 納期を守るには先立って一定のリソースを割く必要があるし、 休暇は所定の数だけ必ず取ってもらわねばならない。 数理最適化はそんなビジネスの「ロジック」を取り出して記述し、 その枠内で良さげな答を探しださせる手法です。 しかしビジネスが「ロジック」だけで動いているかというと、さにあらず。 実務家はロジックの枠に「意志」とか「予測」とか「期待」を流し込んでゆくのが普通です。 時に彼らは問題の枠組みや制約を踏み外して、使える答をひねりだしてしまうことだってあります。

私も以前は好んで使っていたこういう宣伝文句

「(数理)最適化で意思決定!」

お聞きになったことありますでしょうか。 私の経験で言うといまいちで「意思決定」というワードがお客様の胸に響いたということはなかったように思っています。 数理最適化は自動化という言葉で括られる所作、 例えばエネルギーコストを最小化すべく動力プラントのボイラーの運転を決めたり、 レコメンドしたりといったいわば「マイクロ意思決定」は十分できているのですが、 新しい営業所を開いたり大規模な設備を増設したりといった人間が担当している重要な意思決定であるほど、ロジック以外の部分を無視することはできないので、数理最適化任せにできないという感覚をお持ちの方が多いということだと思います。

では、「ロジック」の権化である数理最適化は何もできないかというとそうでもなく、得意なその路線で頑張ればよい。

「もしこの設備を導入したとして最適に運転したとすると..」
「すべての人の休暇希望を叶えて、できるだけ残業を減らすには..」
「コストはさておいて生産性を最大にしてみると..」

数理最適化は恣意性が入らない、 誰もが認める「ロジック」を冷徹に突き詰めた答を出すことで、意思決定者の検討材料を増やすことができます。 シミュレーションとしての利用と言えるでしょうか。「最適にする」という一言でくどくどデータを与える必要がないのがメリット。

そんなわけで先のフレーズを言い直すと

「数理最適化で意思決定の脇を固めましょう!」

となるでしょうか。意思決定の裏方仕事ならちゃんとできることはわかってほしいなと願っています。

コンピュータの得意な部分をどうやって人間の仕事に組み込むのかという文脈で、 「アドバンスド将棋」に関する論考を見つけました。人によってコンピュータに任せようとする部分は様々なのも面白い。こういった考察はまだ初まったばかりなのだと感じました。人工知能に支配される暗黒の未来といったホラーな話よりもぐっと夢があって、わくわくする話であります。

「最適化」のち「数理計画法」再び「最適化」

「最適化」という言葉を Web で探すと

スマホ最適化、ディスク最適化、画像最適化・・

といった感じのものがひっかかってきます。 「今よりも良い状態」を実現する手段といったニュアンスですね。 じつは学術的な数理最適化の分野の「最適」はもっと杓子定規に定義されているのをご存知でしょうか。研究論文とかでは、制約を満たすだけの答は「実行可能解」という格下の名前で呼ばれ、今得られているよりも目的関数値を良くする実行可能解が存在しないことを「証明」できて初めて最適解に昇格するのです(だからでしょうか、最適解は x* とか星を付けて「偉さ」を示すのが慣例)。 ですので、厳密解法という、いつかは最適解を出力することを謳っているアルゴリズムではそれよりも良い実行可能解が存在しない証明にかなりの労力をかけます。 その意義はここに示した通りですが、難しい問題だと答は見つかってるのに延々と「証明」を続けてメモリを使いつくしてしまったりする。それではあまりに悲しいし、とにかく制約を満たす方法だけ知りたい場合もあります。

そんな融通の効かないこと言ってないでそこそこ良い解を速く出そうよ

という発想が「近似解法」という、厳密解法に対置される一つの解法の流れを進化させてゆきました。 じつはこちらの方が「最適化」という言葉の一般の意味に近いとも言えます。

実務に数理最適化を応用しようとする中、我々がお客さまと話す中で気づいたのは

「最適」は一つに定まらない

という悟りです。世の中には各人が自分の好きに解釈できる程度に曖昧なので、 なんとなく意思の疎通が取れたような気になってしまう言葉がありますが、 実は「最適化」はその代表格。「最適化しよう!」という点では仲良くしてたのに何を優先するかの各論に入ると途端に対立して話がまとまらなかったりする担当者の方々が居たり。 まあまあ、まずは今より良くしましょうよ、という感じでスパイラルに話を進めるのが我々の数理最適化の実務における常套的プロセスになっております。

一時期のことですが私、「最適化」という言葉の曖昧さが嫌で「数理計画法」という言葉を好んで使っていた時期があります。この時期に私が書いた資料のタイトルが、

 「最適化読本」-数理計画法って何なのさ-

となんだかわけがわからなくなっているのはそんなわけです。 「数理計画法」なら数理的なルールをモデルで抽象化して表現して何らかの答を見出す手法をあまねく指す言葉ですから、曖昧さがない。 ただ、なんだかとっつきにくいし、一回聞いただけでは頭に入りにくい。

近似解法を使ってシフトスケジュールなんかを求めているのは、 じつは学術的な最適化ではなく、「スマホやディスクの最適化」に近いんだから、 名実共に我々は一般の意味の「最適化」をやっていると言ってもよいのではないかな、と今は考えています。

空白セルの圧迫と「ルール」の力

「一筆書き」のように、 答を見せられれば正しいかどうかはすぐにわかるけれど、 「白紙」の状態からそれを見つけるのはかなり難しい、 というタイプの問題は世の中には数多くあります。 数学的な話で有名なのは大きな数の素因数分解ですが、 ここまで抽象的な例を引っ張り出さなくても、選択式の試験よりも記述式の方が難しい、とか 日常的な感覚として了解できるところかなと思います。

じつはこの手の「一筆書き」的問題にアプローチできるという点が数理最適化という手法の特徴の一つと言えます。 次はマス目タイプのスケジューリング問題のデモンストレーションで、20人の一か月分のスケジュールですが、 水色のセルに(準日勤、日勤、準夜勤、当直、深夜勤、休日)のいずれかを入れる、 というのがここでの課題になります。 入力は、各日に各勤務を担当している人の合計人数(タテ計)と各人の休日数(ヨコ計)で 黄色い表の部分です。

f:id:optimizationTanabe:20160824121716p:plain

しかしこうしてみると水色の空白セルから受ける「圧迫感」はかなりのものです。 マス目タイプのスケジューリング問題は制約の数(表のタテヨコの和)よりも変数の数(表のタテヨコの積)が圧倒的に大きくなるのでやむを得ないことではありますが。実務家の方々が、毎月この空白セルを手動で埋めていると考えるとその労苦が偲ばれます。そんなところに数理最適化が現れてこんな答を書き込んでゆきました・・。

f:id:optimizationTanabe:20160824121756p:plain

ときにつっこみどころ満載ではありますが一応制約を満たす答ではあります。一つの結果があるとこれがいわゆる 'ice break' になって思考を前に進めることはできます。

こんなことを計算機がやるなんて、なんかちょっと不思議?

そうですね。 このシフト表を与えられて集計結果を出すのは計算機がごくあたりまえに行うことですが、 逆に集計結果しかない状況でシフト表を計算機に求めさせようとするのが数理最適化なのです。

データが潤沢に得られる「ビッグデータ時代」になって、 計算機ができることの質が格段に向上したのは確かなのですが、 だからと言ってデータが不足している場合に何もできないわけではありません。 データの不足は「ルール」で補うのです。上のケースでは、集計結果を合わせることと、 勤務種別に関する幾つかのルール(実は最初の二行に対応する人、1番さんと2番さんには日勤優先、としています)、 そして努力目標(休日の日数はできるだけ揃える)を与えるだけでかなりもっともらしい勤務表を導くことができています。

もちろん、「ルール」一辺倒で事足りるわけではないのは、大量データの解析を背景とした昨今の機械学習の応用の目覚ましい発展が教えるところであります。一般に「ルール」は各論的な話や明文化できないものに弱い。 ルールの目が粗すぎると結果が絞り切れてなかったり、 逆に細かすぎても前回議論したような実行不可能性が引き起こされて結果が出なくなってしまうこともあります。 そんなときには「ルール」に拘りすぎずに過去の勤務表の「データ」を使うのが最善の手です。 シフトの例で言えば、もし過去の勤務表がデータ化されているのなら、将棋のプログラムで使われているように 何等かの評価値(結果が前例のように尤もらしいか)を作成して、シフト生成の目的関数に利用する、といったことができます。数理最適化の立場としては「データ」あるいは「モデル」一辺倒ではなく、手に入る限りの「データ」と「モデル」両者から、うまく情報を引き出して要領良く適切な結果を得ることが現在の我々に求められていると言えるでしょう。

「実行不可能」との戦い

「メンバーは5人、勤務は日勤と夜勤の二種類しかありません」 今、小さな病院の担当の方に勤務シフト作りについて伺っています。 「毎日日勤は2人、夜勤は1人は必要です。夜勤空けは休み。それとは別に各人週に1日は休みを入れ、夜勤の担当回数は週あたり1日から2日です」 ここまではごく普通。 「新人の E さんは、ベテランのAさん、あるいはBさんとペアで夜勤に入れるようにしてください」良くある話ではあります。 「ベテラン二人は夜勤1日との約束になってます」了解。 モデルのタイプはまさにマス目埋め の典型で、要求を書き下すことに何の難しさもありません。 まずは、この5名(A,B,C,D,Eさん)一週間分の勤務シフト表を作ってみることにしました。

さて、「実行不可能」との戦いの始まりです。 なぜなら、この設定だとすべての制約を満足する勤務シフト表は作れないからです。

昔の数理最適化ソルバーの場合

古典的な数理最適化ソルバー(厳密解法)にこの条件を入力してみましょう。結果は

「実行不可能(エラー xx番)」

制約条件を満たす解が存在しないので、解析できない、という意味です。 制約を満たす中で最適な答を探すアルゴリズムにとって、 確かに想定外なのはわかるのですが、理由くらい教えてほしい。

「すいません、条件が厳しすぎて結果が出ないんですが」
「え?なぜですか」
「それが私にもわからないんです、でも数学的に答がないことはわかりました!」
「...」

前回に言ったような特殊ケースでなければ、これを喜んでくれるお客さんは居ません。

制約充足問題への変形

こんなとき古くから伝わる智恵として、制約を「努力目標」として記述し、 違反を零にできないまでも最小化する、という形(制約充足問題)に問題を変形する、という手があります。 制約充足問題をやはり古典的な分枝限定法による厳密解法で解いてみましょう。 今度は無事結果が出ました! 違反の最小値は 1、結果は以下です。夜勤明けを「-」で区別して表示しています。

f:id:optimizationTanabe:20160819032401p:plain

「一箇所違反が出てしまうようですが、結果出ました」
「でも、新人の E さんが一人で夜勤をやってしまってますけど..」
「だって、一箇所は違反が出てしまうのは数学的に仕方ないんです!」
「...」

「数学的」事実をタテに妙に強気に出てはなりません。 ここで「最適解は実は沢山あるかも」と気をまわしていたら、 次のような答え方になったかもしれません。

「Eさんの制約違反の重みを大きく設定すれば、違反しない解が出るかもしれません。
  大丈夫です。制約すべてに重みを設定できるようにすれば、お好みの解が自由自在です!」
「...」

がんばっているのはわかるのですが、制約はざっと 9 種類。 お客さんは結果が欲しいのであって、 こんな重みの調整に苦労するくらいならば自分でシフト表、作りますよね。

複数の答を出す(メタヒューリスティクスの適用)

今我々が持っている手段の中で最も訴求力がありそうなのは、 同じ目的関数の答を複数個出すこと。 アルゴリズムを古典的解法からメタヒューリスティクスに切り換えると実現できます。 例えば次のような感じの答が沢山得られます。

月曜に誰も夜勤をやらない解:

f:id:optimizationTanabe:20160819032501p:plain

ベテランの B さんやむなく週2回で夜勤をする解:

f:id:optimizationTanabe:20160819032524p:plain

何回か実行して出てきた解を分類すると、最初に出た「新人が単独勤務」解、 「どこかの日の夜勤担当なし」解、「ベテラン週2回」解、 が出るようです(私としては、いつか Web 検索のように、 これら候補解が違反量でランキングされて複数出すようにすればもっと数理最適化は馴染みのあるものになると思っています)。 どんな方向性の解が良いかはお客さんに選んでもらいましょう。 若干のお手数をかけますが、「完成品」の答を選ぶのは9個の重みを設定するよりも良い手段ではあります。 ここまでわかれば、あの deep-learning も及ばない人間知性の働きであるところの 「帰納的推論能力」のおかげでこの問題が解けない理由に気付くことができるでしょう。すなわち、 いずれかの日で(Aさん - Eさん)あるいは(Bさん - Eさん)の組みあわせで夜勤をしてしまうと、 残りの6日の夜勤を3人で担当せねばならない。 その 3人のうち一人は Aさんか Bさんなので、 合計して担当できる夜勤の回数は5回。要するに一日分足りないわけです。 Eさんが2回夜勤をするケースも考えられますが、これも C さん D さんが2人で5回の夜勤をしなければならないので無理、というわけでした。

ごく単純な制約でも組みあわせると相互作用して引き起こされる上、解消の方向性が一意ではない。 数理最適化を実務的に応用しようとする場合、 そのエネルギーの少なからざる部分がこの「実行不可能」との戦いに費される理由になっています。