…州…‖…捌州捌m…州…榊州…ll111榊l…8−1m……棚州……………州…l刷刷州l日脚l…m州……州川棚川附M州…州……州…州Il

数理計画ヅプ恥初体験
柳浦 随意
州州州…州………811…………州…l………捌‖捌川棚‖…附州州………………川棚‖川川川棚州‖…‖川…‖l…………‖川棚川＝川…l

るんだということはご理解いただけると思います．な−一

亙教授：「今年は科研費が結構あるやろ。うちにも数理計画ソフトが且つあると便利でいいんじやないかと思うんやけど，柳滑君ちょっと調べておむ、てくれな
いかなぁ」

おッモデル記述言語をすでに利用なさっている方にはとくに目新む／い情報はないと思いますがご了承くださl′、・・ ‥ 竿∴ニニ…：−‡‥芋茎三聾者て「ははヤ」というわけでフ急遽数理計画ソフトをいろいろ使ってみることをこなりましたn この事のソフトは初体験だったのでサが，使ってみてまず感じたのが，J￣ぉぉっ，何と手軽里」ということでサ。これはひとえにモデル記述貰語なるもののおか各ザなのですがワニれを使うとヲ集合や数式を用いた入力が可能になるため，わざわざ行列の形に係数をならべ直すなどの必要がなくフ人間が理解じ牽サV鳩然な形で問題を記述することができます血 よって9数理計画ソフトを手軽に使えるようにモデル記述言語に対応した数理計画ソフトとしてはっ 例えばフ SOPT（AMPL），CPmEX（AMPm），
Ⅹ野鼠ESS血M㌘（MP−MODEm），NWOPT（S‡MPm取乱‡NDOブG瓦Nのなどがあります（括弧内はモデル記述言語名）。また，表計算ソフトExce‖こは独自のソルバ山が付いています」胤0屯やC償柑Pなどはヲ制約充足問
題を基本とするソフトですがヲ数理計画法の導入が予定されているようです。これらには論理的な制約を簡単に記述できるような様々な表現法が用意されています。ニ菅デル記述言語の詳しい解説は∋もちろんソフトなるわけです。

線形計画問題（阻P）に限らず，整数計画問題や非線形計画問題が市販の数理計画ソフトで比較的大きなサイズまで解けるようになってきて折まず＼もちろん，整数ヲおよび非線形計画問題の場合は効率的に解けるケ山スが限られてくるので注意が必要ですが。「解きたい数理計画問題が手元にあるのだがフどうも数理計画法と糾うのは難んそうで使う気が＜．…」とかフ「数理計画問題を解いてくれるソフトがあることは知っているのだが∋どうも教科書に書いてあるような行列の形に定式化するのもめんどくさそうだし…」などと思ってむ、る方々がヲこの記事を読んで∋ F−これなら使ってみを購入すればセットで付いてきますが，例えばヲ以前のの鼠学会誌に‰IND①とG‡Nのの解説削が，またヲ問題のモデル化を含め，さらに詳しい解説書として虹パ刊などがありますのでご参照ください。また，毎年春と秋に行われるの既学会の研究発表会場では，ⅩPRESS炒M㌘やN甘Jの炉甘などのデモがありますれソフトを販売している会社の連絡先は例えば最近のの毘学会誌の広告などに載っています。とりあえずちょっと試してみてから購入を検討したいとむ、う方のために，サンプル版を有効期限付きで貸してくれる会社もあります。
少々青いですが，F7］にいろいろなソフトの紹介がありますのでッこちらもご参照下さい。また，をデル記述ようか」空糾う気になって下されノば幸いです以￣下ではラモデル記述言語を利用むノた入力方法の一例と簡単な計算例を紹介じます。数理計画ソフトを初めて使ってみた程度の筆者が解説記事を書くのは少々妙な感じでサが，少なくとも仁初心者でもすぐに使え言語に対応しているかどうかは確認していませんがフタダ のソフトも数多くあります．久保先生の記事
臣6］や松井先生のホームページ1などをご覧ください．
上述したような語デル記述言語は，それぞれに特色がありぅまたヲ文法も多少異なりますが，以下に述べる

やぎうら むつのり 京都大学工学研究科

ような基本的な記述能力は大抵どれにでも備わってい〒6の6凹の鼠京都聯左京区吉田本町
・・●∴
9堵（28）、、‥・ ・・、：こ・、・LごJ∵− ご‥・し・・
オペレ、一一一一ションズ0© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

リサー】チ

ます．以下では，SOPT＋AMPL（AMPLについては例

ampl：S11bject to b11dget：

えば【1］参照）を用いた入力例を紹介します・

ampl：2．0＊Ⅹ1＋2．5＊Ⅹ2＋3．0＊Ⅹ3＋0．5＊Ⅹ4
ampl：＜＝2000；

3．ナップサック問題

ampl：SOlve；

前回の特集「ユーザのための数理計画入門」の冒頭

Optimalsolutionfoundの茨木先生の記事【3】で紹介されたナップサック問題の（obj＝1．8983e＋03，time＝0．01sec）

入力を考えてみましょう．問題は，予算2000円でコー

ampl：display utility；

ヒー，紅茶，日本茶，ジュースをそれぞれ∬1，∬2，￡3，∬4utility＝1898．3単位（g，mlなど）購入して，満足度を最大にするとい

ampl：display xl，Ⅹ2，Ⅹ3，Ⅹ4；

うもので，データは，

Ⅹ1＝500，Ⅹ2＝300，Ⅹ3＝＝83．3，Ⅹ4＝0
はじめの4行は変数の定義，および各変数の上下限制
コーヒー 紅茶 日本茶 ジュース￡1∬2∬3

噂好係数cj‥2・02・3 2・5

値段αj＝2・02・53・0

約を与えます．次の2行はutilityと名づけた目的関∬4数の最大化が目標であることを指定します．目的関数0・3

や制約式1本の定義はセミコロン「；」で区切られる

0・5

ので，この例のように間に改行が入ってもかまいませ最大必要量‥ 500g 300g 300g lOOOml

ん．最後は予算制約です．solveという命令によりソルバーが稼動し，最適解が求まります．d土splayとい問題は満足度： 2．0二rl＋2．お2＋2．5∬3＋0．3∬4→最大
制約条件：2．0∬1＋2．5ごr2＋3．0∬3＋0．5∬4≦2000

う命令により，最適値や最適解など様々な情報を見ることができます．この例では，求まった最適解は0≦諾1≦500，0≦∬2≦300∬1＝500（コーヒー）

0≦∬3≦300，0≦∬4≦1000∬2＝300（紅茶）ヱ3＝幻・3（日本茶）と与えられます（通常は整数制約が入るが簡単のため￡4＝0 （ジュー ス），省略）・これをAMPLで記述するわけですが，以下では実際に入力する部分をタイプライターフォントで書

最適値は1898・3となっており，得られた解が【31で求くことにします．それ以外はコンピュータの出力です．

めたものと一致していることが確認できます。C言語

まず，AMPLを立ち上げるために，コンピュータのコのprintf文と同様の表記も受け付けますので，出力をマンド入力プロンプトで，都合の良いフォーマットで行うこともできます．このように，対話的なインターフェイスが用意されている

prompt％ampl

ので，問題や解法のパラメータを変化させながら満足と入力します．すると，解が得られるまで対話的に作業を進めることが可能です．

ampl：通常，問題を手で入力するのは大変なので，何らかというAMPLのプロンプトが出て入力待ち状態になのプログラムを用いて問題を記述したファイルを生ります・ここで問題を1行1行入力していって，最後成し，それをソルバーに読ませるなどの方法をとりまにsolveと入力すればソルバーが勝手に答えを出しす・これを行うには，以下のようなファイルを，例えばてくれます．

knapsack．modと名前をつけて保存しておきます．

ampl：Vaヱ・Ⅹ1＞＝0，くニ500；＃ナップサック問題（ファイル名：knapBaCk．mod））

ampl：Var X2＞＝0，＜＝300；♯変数定義と上下限制約

ampl：Va工・Ⅹ3＞ニ0，＜＝300；

Var Xl＞＝ 0，＜＝ 500；＃ コーヒー

ampl：Var X4＞＝0，＜＝1000；

Var X2＞＝0，く＝ 300；＃紅茶

ampl：maXimize11tility：

Var X3＞＝0，＜＝ 300；＃ 日本茶

ampl：2．0＊Ⅹ1＋2．3＊Ⅹ2＋2，5＊Ⅹ3＋0．3＊Ⅹ4；

Var X4＞＝0，＜＝1000；＃ ジュース

1998年2月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（29）95

且の問題例は，

辟 困的関数（満足度硯七ま1立もyの最大化）
m乱Ⅹ温血宜器eⅧ亀弧瓦亀y：田的関数：2飢1＋触2＋2野21

二2，0＊Ⅹユ 十 2，3ヰⅩ2 サ 2ハ5涙Ⅹ3 サ 03＊x4言＋5y22＋3封31＋2馳2→最小辞制約条件（予算制約》

制約条件：2封且且＋3野21＋且邸31≦4

凱㈲錘灯随翫汗翫喝酢一缶：

2凱2【卜2野22＋2封32≦3

フ．0＊JK二き十 2ト5＊xフ 小 3．0＊Ⅹ3 十 0．5準X4＜＝ 2000；

凱1司w凱2＝ニ乱（1）一、馳皿＋駅ほ＝凋

、・；・、

慰31十封32＝且1aミ工1Pi二鼠nclude knapsack・mOd二翫1≧のブ飢2≧0

amp鼠：翳0乱ve；

即2鼠≧：の，即22≧￠
野3ま≧の，馳2≧0とすればよいわけでサ。なお，止の例のように，「＃」（必ず半角）から改行までの間にはコメントを書くこと表せます。各仕事の総量を且として，変数眺ゴは仕事とができます．

壱を作業者jに割当てる割合を意味します（通常は整数制約が入るが簡単のため省略）．目的関数は総コス

感② 闇般化割当問題

ト9制約条件のはじめの2つは作業者且と2の負荷許容量に対する制約ヲ次の3つは各仕事がすべて割当て

ナップサック問題の例で簡単なルールはご理解いた

られなければならなW、ことヲ最後は割当てる畳は負にだけたと思います小 じかし，上の例ではフ表現がなじなってはならないことを表しますe

みやすむ、ということの他にはあまりモデル記述言語説明の都合上∵記号を使ってもう少し一般的に書くのメジットが見えませんけ ここではっもう少し複雑なと，仕事数を孤，作業者数をmブ仕事壱を作業者ゴに割一般化割当閻魔懐考えてみましょう。この問題は，ナッ当てたときのコストを軋わ負荷をγ五j，作業者jの負荷プサック問題に似ているのでサがヲ少し拡張した問題許容量をになって附潰す。問題を園且の例で説明します∴仕事βJとして9′花m掛的関数 監∑ば盲動→馴、
五＝1ゴニ1

作業者

耶．

宜ニ＝1

γ㍑ 芝野五j＝且，壱＝1，…ラ孤・∵塩1

尊重宕引野山遵・

制約条鰍 監γ盲動≦5J，j＝且，…，m

J＝・乱∴、 −；・、−‥・、・

ト山川一．Ⅴ／．と書けます＼止の例題をÅM肝且で書くと，例えば，
廊パラメータ定義

代4︑ノpa訂誠m；pay弧m； 辞仕事数と作業者数
炉ar弧姐‡i…冨鼠♪鼠…m）；＃各割当のコスト
par弧甘‡￡…弘♪軋D。m）；＃各割当の必要負荷pa訂弧S‡鼠−，m｝；

図且：一般化割当問題の一例

邸各作業者の許容負荷

僻変数定義と下限・・・∴ −・こ・．

を作業者に割当てる際ヲ仕事且単位につき枝上の数字

詣 冒的関数分のコスト（賃金など）を要しヲまたフ負荷（労働時間な

1Ⅵ土nimJZ巳（：0S†：ど）が作業者にかかるものとしますDこの時，各作業者

y、．．、・．、・・、‥・‥・；．．・・・ミIl、ゝ1ミ∴ jご‥・の負荷が許容量を超えないようにした上でヲ総コスト

器負荷許容量制約が愚かとなる仕事の配分を求めるという問題です」図

ト∴ ●∴ ・、ニ ーここ、∵ ここぐ・、、 −・、・・1い閑（30）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレ、叫ションズ0リサーチ

sun（iinl‥n）r［i，j］＊y【i，j］＜＝S［j］；

れだけ大変か（ちょっと大袈裟かも）を簡単に説明した＃割当て制約

いと思います．線形計画問題は一般的にはⅣ

subject to assign（iinl■・n）：

田的関数：∑cJ∬j→最小sum（jinl‥m）y［i，j］＝1；

ゴ＝1data；♯以下は問題例のデータ．Ⅳ

制約条件：∑木拘≦むゎ壱＝1，…，怖 （2）param n：＝3；para皿m：＝2；

j＝1

param d：1 2：＝
1 2

4252Ⅳ

∑ヰ拘＝む壱，壱＝〟1十1，…，〟J＝1∬j≧0，メ＝1，…，Ⅳ

3 3 2；

param r：1 2：＝と書けますが，モデル記述言語を用いない場合は，通1 22

常，この形に問題を記述した上で，叫，あ五，およびcJ22のゼロでないもの（非ゼロ要素）を指定された順序で3 1 2；添字とともに入力していきます．一般化割当問題の場

3合，変数yiゴには2つの添字がついているので，param S：＝1 4

肌J←＝鞘（た＝＝m（五−1）＋ブ）

2 3；のような対応づけを行い，問題が（2）の形になるようのようになります．前半で問題の一般的な定義を行に添字の変換を行う必要があります．これは，別に難い，後半で具体的なデータを入力しています．コメン

しいことではないのですが，良く考えながら慎重に作トを含む最初の5行で問題を定めるパラメータを定業を進めないと，思わぬバグの原因になりがちな作業

義し，次の2行で変数を定義します．そして，これらです・上の一般化割当問題を（2）の形に書き直すと，の文字を使って目的関数と制約式の定義を行います．

目的関数：2こrl＋4ェ2一卜2こr3

AMPLの中では1‥nというのは，集合（1，2，…，m）
を意味し，Su皿（iinl‥n）は∑芸1や∑呵1，…，几）と同じ意味になります・また，Subject to resource（j＋5二r4＋3∬5＋2こr6→最小
制約条件：2二だ1＋3こr3一卜1三方5≦4
2こr2＋2こr4−ト2二r6≦3inl．．m）：は，各j＝1，2，…，mに対してこの制約が定義されることを意味します．パラメー

ヱ1＋∬2＝］L

タdとrの入ヱ3＋∬4＝］L

力部分では，第1行目と第1列目は行と列の番号になっ￡5＋諾6＝皿ています．例えば，d［1，1］＝2，d［1，2］＝4，d［2，1］＝2，￡1≧0，∬2≧0d［2，2］＝5…などという情報がまとめて書いてあるわ∬3≧0，∬4≧0けです．パラメータsの第1列目も同様です．

ご5≧0，諾6≧0

データ入力の部分が，図1の枝に付いている数値をそのまま順序良く並べただけの，直感的にわかりやすとなりますから，い形でコンパクトに入力されており，（1）の表記をそ

Ⅳ＝6，．肘1＝2，且す＝5のまま書き下すよりも少々賢い入力法になっているこ

Cl＝2， C2＝4， C3＝2とがお分かりいただけると思います．また，このようC4＝5， C5＝3， C6＝2な書き方をしておくと，前半と後半を別々のファイル

α11＝2，α13＝3，α15＝1に分けておき，新たな例題を入力する際には後半のデ

α22＝2，α24＝2，α26＝2ータ部分のみを生成して入力を行うことができるの

α31＝1，α32＝1で，便利です・さらに，このような入力方法をとると，

α43＝1，α44＝1

書かれている数字の意味がすぐに分かるので，修正やα55＝1，α56＝1

デバッグが容易であるというメリットもあります．

あ1＝4， あ2＝3， あ3＝1

さて，次に，モデル記述言語がない場合の入力がど
1998年2 月号

あ4＝1， ら5＝1

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（31）97

という情報を入力するわけです。例えばッF4j（p．30）のブ射血1∇ツトに従うと，この入力は以下のようにな衷且：山般化割当問題に対する計算例ります。（この本には，線形計画問題に対するシンプレのサイズックス法を畏まじめとサる様々なアルゴリズムの解説があり，その中で紹介されたプ田グラムの入ったフⅢツ
ピ匝ディスクも安価で販売されているのでそういうイズ

計算時間（秒）且000

500（〕 1005

10（】003．31

5 二三Jlく：し）510i〕00 ：之005

20000

10．00

10 100CP

10000 1010

20000

7．02

鼠0 200（〕20000 2010

40000

17．44

2ひ20000

且000

孔020

40000

16．58

意味では手軽に利用できるのでサが，モデル記述言語

20 2000

4000〔） 2020

80000

41．00

3（〕 鼠000

30000 1030

60（〕0026 58とは対応じておらずヲÅカは少針酎劉になり潰すま

30

6000C♭

た，著者閃く「分かりやサさを重視して教育用に開発
じた＿巨プ田グラムなので，大きむ、サイズの問題を解く

200む

2030

1200006且．86

80000

35車79

40 1000

40000 1040

40 2000

80000 ：204（〕160000

84．77

5の乱00050000

1000（〕047中275ぴ

2000

且050

且00000 2050

20（〕000110．74のには適きないようです」

m通Åu

2分程度で解けています。計算時間は，通乳変数の数よりもむしろ非ゼロ要素数に依存します。また，線形計画問題の場合はこのように大規模な問題が効率的に解けるのですが，整数性の制約や非線形の式が加5り血6mV且︵MハUnU用心

3・ミ1、11望62

5

いC O

32L∴主2

ワ見こぅ き：」4

プニ手こ：‡

255］邑

模な問題になりますが，普通のワークステーションで1

且5且︵M44遜l n︶

二こ33

肘わ43乱！▲

且且2

止血321ー⊥

365

実際の入力ファイルはこの数字の列が且列に並ぶのでハU

mWりノ︼

爪U

すが，場所の都合止，4列に分けて書む、てありまサ＼フnU¶且ォーマットを一応簡単に説明じておきますとヲー行目

は変数の数と制約の数フ2行田以降「の00」までが）「壱，来期」ラ次の「針削1藍でが∋「五ヲあ五」フ次の「の0」まで

わるとパルつもこのように効率よく問題が解けるわけではありませんので，ご注意ください㌧1いずれにしてもヲこのような大規模な問題を効率よく解いてくれるソフトが意外と手軽に使えることは大変心強いことと思うのですがヲいかがでしょうか。

・、 ・．∴こ・・−、 ・、
ここでは，問題に整数制約や非線形関数が加わるとが，各行の制約タイプ（解雇番田の制約が不等式（≦）のきの入力方法や，規則的なデータや疎なデータの入力場合は「底，］L」と書きヲ等式ならば記述不要）フ次の「の方法についてふれておきます。

勘二藍でがヲ「ゴ，Cゴ」ヲ最後に各変数の上下限制約を書きます（今回は不要なので「の揖＿jのみを入力）。これ

まずフ変数に整数制約を加える場合は，変数の定義のところでフらの数字の並びを見てもピンと来ずっ・山田では意味が分からな附止溌㍉このような形式に従って入力を行う
ことが少々やっかレヽな作業であることが分かると思いますVar〕〔ユ∴三mteger ＞＝ C，＜∴＝ 500；′・、

い− ∴、・・こさこ一 ノー￣ こ．このように書きまず．またフ目的関数がヲr††Jl

馬￠ 皿般化割当問題す≡封ずる計算例、．・∴ニー・い、．−▲ニト
壱＝1J＝i

それではフ入力じた問題が市販のソフトでどの程度の時間で解けるかを見てみたいと思います。使用した計算機はSumU且も訂a鼠Mo鮎且且70E，利用したソフトはサイテック社のSのP甘でサ。一般化割当問題をSOPTのように望次の場合吼
・い ＝・・∴こ・ニ㌧rL・㌔・・ご ・さ ミ」一、・∴ ご・こ・∴、・・ − ・ −∴にプしカしたときの計算時間を表且に示しまず．表中，GÅ㌘は一般化割当問題（gemer誠zedassigmmem也prob】のように入力できまサ．このように，ヰタ Ⅶク ＊，／声 ＊＊亙em）を意味じます。作業者数50，仕事数20ののの場（四則演算とべき乗）が利用できる上abs（〉，eXp（）タ合はぅ線形計画問題の変数の数は且の万フ制約を記述

乱og（）などの組込み関数も用意されていますので，さサるα壱プの非ゼロ要素数は2の捌こもなりヲかなり大塊らに複雑な関数も入力できます．ただしラ整数制約や盟留（32）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレー州ションズロ

リサーチ

05＼﹂

3っていただけたでしょうか？モデルを記述する具体例を説明するため，かなり数式を使ってしまいましたが，70

さて，数理計画ソフトは「手軽に使えそうだ！」と思

0

次に，データ入力についてですが，0うになってきたことは，大変喜ばしいことと思います．

0合がありますので，注意が必要です・

0も，数理計画法が現実の問題にどんどん利用されるよ′し非線形関数については，ソルバーが対応していない場

そのせいで「何だ，やっぱり数式がいっぱい出てきて難しいじやないか」ということにならなければいいののように0が多い行列を入力するときには，
paramn；Parama（1・・n，1‥n）；ですが．

参考文献

data；

【1］R．Fburer，D・M・GayandB・W・Kernighan，AMPL

pa工■am n：＝3；

A〟ode払クエαmタ祝叩eわγ〟α兢eγ柁α加cαgP和タrαm−

para皿a defa111t O ‥ニ

ming，boyd＆fraserpublishingcompagy，1993・

1 1 3【2】羽鳥， 制約論理プログラミングによるフイルム・

2 3 5

紙の裁断計画， 生産スケジューリングシンポジウ

3 3 7；

ム，卯講演論文集（1997）157−160■のように，デフォルト値を0と定めた上で，0以外の要素について「行番号，列番号，要素の値」の順に入力することができます，このような入力方法は，大規模で0011O0O0ヽj1′し疎な行列のデータを入力する際に便利です．また，【3］茨木， 数理計画：問題解決への広き門， オペレー
ションズ・リサーチ，41（1996）313−319・【4］茨木，福島，FORTRAN77最適化プログラミン
グ，岩波書店，1991．
【5］N・Konishi，Y・Nakagawa，H・Nishida and N・

Sakai，A MIP−Based Approach to the Cutting

StockProblemforRollandLongStripMaterials
With Minimum Production Amount Constraint，のように，対角要素のみが1であるような行列を定義する場合には，Proc．A血αれCeβ盲mアγ0血c如れ〟αれ叩emeすIf勒β一ねmβ（1996）603−608・［6】久保， タダより安い数理計画入門， オペレーショpaヱ■am n；param a（iinl‥n，jinl‥n）：＝

ンズ・リサーチ，41（1996）337−342．
【7］J・J・Mor6andS・J・Wright，qPtimizationS（埴wareifi＝j thenlelse O；

α祝窟de，SIAM，1993．のように，規則を書くだけでコンパクトに入力できます．これら以外にも便利な入力方法は多数用意されていますが，詳しくは【1，11】などを参照下さい・［8］西田，山軋今井，熊本，清家，神谷，中村， 列生
成法による鋳型設置場所割当問題の解乳 日本

OR学会秋季研究発表会アブストラクト集（1996）
112−113．

7。 むすび【9】新村， 数理計画法のパッケージ，中間言語，ライ数理計画ソフトの簡単な紹介，およびモデル記述言語を用いた手軽な利用法を紹介いたしました．
最近では，企業においてスケジューリング問題など

ブラリー， オペレーションズ・リサーチ，38（1993）
124−130．

【10】高田，寺野， 作業者のスキルとローテーションをを解く際に，ここで紹介したような数理計画ソフトを考慮したスケジューリングシステム， 生産スケ利用したという報告が見受けられるようになってきま

ジューリングシンポジウム，97講演論文集（1997）

した【2，5，8，10】．スケジューリング問題の場合は，31−36．

どうしても組合せ的な制約があるために，線形計画で［11】H・P・ウイリアムス著（前田監訳，小林訳），数理はなく，混合整数計画問題や制約充足問題として定式計画モデルの作成法，産業図書，1995．

化することのほうが多いようですが．いずれにして1998年2 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（33）99