離散最適化とその応用

第1回 離散凸関数はどのような性質を満たすべきか：離散最適化の視点から
塩浦 昭義…l……………‖州‖………‖‖‖‖‖‖‖‖‖‖……lll‖‖‖川Il…………l……l…‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖刷川……‖‖＝＝‖‖‖＝‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖＝州…………‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖州…lll‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝州

集合5⊆R乃は，任意の∬，y∈5およびα∈［0，1］に1．はじめに対してα∬＋（1−α）〝∈Sを満たすとき．に凸集合と呼ば与えられた解集合の中で，与えられた関数を最小れる．同様に，関数／：R乃→RU（＋∞）は，任意の（または最大）にするものを求める問題を，最適化問∬，y∈dom′…（z∈R乃げ（z）＜＋㌫）およびα∈［0，1］に題もしくは数理計画問題と呼ぶ（最適化および数理計

対して不等式画について詳′（α∬＋（1−α）y）≦α／（エ）＋（1一α）′（y）

適化の分野は，扱う問題の解集合Sおよび関数／のを満たすときに凸関数と呼ばれる．なお，／が連続の構造によって，実数変数に関する最適化である連続最場合には，凸性は次の中点凸性と等価である：

適化（または非線形最適化）と，整数変数に関する最適化である離散最適化（または組合せ最適化，整数計画）の大きく二つに分類することができる．連続最適／（（エ十y）／2）≦（／（∬）＋／（y））／2（J，y∈dom／）．
任意の集合S⊆R乃に対し，その標示関数∂5：R乃→（0，＋∞）を化の分野では，与えられた解集合や関数が「凸性」と呼ばれる性質をもっていると問題が効率的に解ける，0 （∬∈5），∂5（ホ（＋∞（その他）ということが良く知られている．一方，離散最適化のにより定義する．すると，集合Sの凸性とその標示分野では，解きやすい問題に現れる「良い構造」を凸関数の凸性が等価であり，また，凸集合は凸関数の樽性の視点から捉えようという試みが近年盛んに行われ殊ケースと見なせることがわかる．このような凸集合ており，様々な離散凸性の概念が提案されてきた．本と申開数の関係を踏まえて，本稿では，関数に対する稿では，これまでに提案された幾つかの離散凸性につ00性が定義されたとき，集合に対する00性を，そいて解言見し，どのような性質をもつ関数が離散凸関数の標示関数に対する00性により定義し，集ノ合に対すとして相応しいのか，離散最適化の視点から考察する．

る00性を関数に対する00性の特殊ケースとして見

なお，離散凸関数は，離散最適化の分野だけでなく，なすことにする．

数理経済学や工学の分野などにおいても有用な概念で凸関数に対する基本的かつ重要な演算として，和とあり，不可分剖財を含む経済均衡の問題や行列を用いたたみ・込みがある．二つの関数んム：R乃→RUたシステム解析など，様々な応用が知られている．離（＋∞）が与えられたとき，和はg（∬）＝ム（∬）＋ム（∬）（∬

散凸関数の応用について興味をお持ちの方は文献［10，∈Rりにより，たたみ込みは11］を参鱒されたい．

ぁ（∬）＝inf仏（れ）十月（∬2）l∬1＋∬2＝J）（∬∈Rりにより，それぞれ与えられる．凸関数のクラスは，こ2．凸性の定義とその性質れらの演算に関して閉じていることに注意されたい．

本節では，連続最適化の分野において重要な概念である，凸集合および凸関数の定義およびその性質について説明する．凸性について詳しくは文献［3］を参照されたい．
しおうら あきよし

凸関数は様々な良い性質をもつが，連続最適化の観点から特に重要なのは以下の二つの定理であろう．
次の定理は，凸関数の大域的な最小性は局所的な最小性により保証されることを述べている（図1参照）．

定理1（局所最小性＝大域的最小性）．／：R〃→RU

東北大学大学院情報科学研究科（十∞）は凸関数，∬∈dom／とする．このとき，エの〒980−8579仙台市青葉区荒巻字音葉09

ある近傍N（∬）⊆R〃に対して／（∬）≦′（〟）（y∈N（∬））

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

オペレーションズ・リサーチ（1）

こ㌧三千タ′∫
大域郎点適

大域郎虐適
局所最適

図2 分離定理．凸関数が凹関数の上にあるとき，その間図1局所最小性と大域的最小性に挟まれる線形関数が存在するが成・り立つことと，／（J）≦′（y）（〝∈Rりが成り立つ
ことは等佃である．

□

この性質より，現在の点の近傍を調べ，近傍内で関数値のより小さい点に（適切なやり方で）移動する，ということを繰り返し行うと，最終的に凸関数／の● 最小解が得られることがわかる．すなわち，降下法によって凸関数の最小化ができる．このことは，凸性を

図3 一変数関数に対する離散凸性．黒い点が関数／を，折れ線が関数／を，それぞれ表すもつ問題の「解きやすさ」の一端を表している．
関数g：R乃→RU（−∞）は，一夕が凸関数のときに散開数に対する凸性（離散凸性）をいかに定義すべき凹関数と呼ばれる．次の定理は，凸関数と凹関数を線か考えていく．

まず，一変数の離散関数／：Z→RU（十∞）に対す形関数によって分離できることを示している（図2参月別．

る凸性を考える．この場合，グラフの各点（∬，／（J））

定理2（分離定理）．凸関数′：R乃→RU（＋∞）と凹関数g：R刀→RU卜∞）に対し，（適当な仮定のもとで）／（J）≧g（∬）（∀∬∈Rりが成り立つならば，（∬∈Z）を線分で結んでいくことにより得られる区分線形関数f：R→RU（＋∞）に注目し（図3参照），この関数／が凸であるような離散関数／を離散凸と定義するのが自然であろう．

／（∬）≧〆ご＋α≧g（∬）（∀∬∈Rりを満たす♪∈R〃とα∈Rが存在する．

口分離定理から，連続最適化の理論において重要な役
また，分離定理の系として，次の性質が得られる：

系3．二つの凸関数差：R乃→RU（＋∞）（才＝1，2）に対して（適当な仮定のもとで）min仏（∬）十ム（∬））∫∈RJl＝min（jl（x）＋i＞Tx）＋min（J；（x）−DTx）．r∈R′lエ∈RJl

定義するのが良いだろうか？一つの候補として，一変数の離散凸関数ム：Z→RU（十∞）（才＝1，2，…，乃）割を果たす双対定理を導くことができる．

●

では，一般の離散関数についてはどのように凸性をを満たす♪∈R乃が存在する．

Ji によって′（J）＝∑ム（ェf）（∬∈Zりと表せる関数，すなl■＝1

わち分離凸関数が挙げられる．分離凸関数は確かに様々な良い性質を満たす．しかし，分離凸関数はとても特殊な関数であり，例えば分離凸性の集合版，すなわち，その標示関数が分離凸関数となるような集合は超直方体

系3は，式（2）を満たす♪∈R乃を求めることにより，凸関数の和ム＋ムの最小化を，それぞれの凸関数の最小化と†、う，より簡単な問題に帰着することができる，ということを述べている．

3．離散凸関数の満たすべき性質
以下では，整数格子点Z〃上で定義された関数のこ（∬∈Z乃lの≦れ≦れ（ブ＝1，2，…，乃））に限定される．したがって，分離凸関数は離散凸関数のクラスとしては小さすぎるので，分離凸関数を含む，より広い離散関数のクラスを考える必要がある．
上記で考えた一変数関数に対する離散凸性は，普通の凸関数に拡張できる，という性質により定義された．
一般の場合についても，「離散凸関数ならば普通の凸とを，実数空間R乃上で定義された関数と区別するた関数へ拡張可能であってほしい」と考えるのが自然でめに，特に離散関数と呼ぶことにする．本節では，離あろう．以下では，「凸関数へ拡張可能」という言葉

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

（47）丁31ト／」／
図4 離散関数の凸閉包．黒い点が関数′を，折れ線が関数7を，それぞれ表すを厳密に定義をする．

離散関数／：Z乃→RU（＋∞）に対し，その凸閉包

図5 整数ベクトル∬∈Z乃の近傍Nz（∬）

7：R乃→RU（＋∞）を∬2f（x）＝SuP（bTx＋如Ty＋α≦f（y）（y∈Zn））（∬∈Rりにより定義する（図4参月別．直感的には，凸閉包743

口 ロ ．．・・℃

は条件7（〟）≦′（y）（y∈Zりを満たす「最大」の凸関0●■一数である．離散関数／の凸閉包ア：R乃→RU（＋∞）
が7（J）＝／（∬）（∬∈Z乃）を満たすとき，′を凸拡張可●一一′0■一一 ′一一0，0） 口

能である，と呼ぶことにする．離散凸関数が満たすべき性質として，最初に次の性質を挙げる：

2623

図6 凸拡張可能だがP2を満たさない離散関数の例．点線は直線∬1−3こr2＝−2∬1＋3∬2せ表す

Pl［凸拡張可能性］「離散凸関数」ならば凸拡張可能．
max（Jl−3∬2，−2∬1＋3J2）

一変数関数の場合は，性質Plを満たす関数が離散凸関数として適一切であることがわかった．これに倣い，／（動，J2）＝（∬1≧0，∬2≧0）＋∞

一般の場合についても凸拡張可能関数が離散凸関数と（その他）は凸拡張可能である（図6参照）．ここでベクトル（0，して適切かどうか，考えてみたい．
定理1では「局所最小＝大域的最小」という凸関数の性質について述べたが，これは凸性をもつ連続最適化問題の解きやすさにつながる性質なので，離散凸関数でも同様の性質が成り立ってほしい．整数ベクトル0）は局所最小であるが大域的最小ではない．
したがって，一般の場一合には，凸拡張可能性だけでは離散凸性を定義するには不十分なことがわかった．

4．Milterの離散凸関数

ぞ∈Z乃の局所最小性を定義するために，その近傍
Nz（J）⊆Z〃を次のように定める（図5参照）：

本節では，Miller［6］の提案した離散凸性を紹介する．離散凸性を定義するためのアイディアとして，凸Nz（∬）＝（y∈Z〃川〝−J帖≦1）．

性を定義する不等式（1）の離散版を考える．整数ベクトP2［局所最小＝大域的最小］

ル∬，〝∈Z乃およぴα∈［0，1］が与えられたとき，Z＝′（∬）≦／（〟）（y∈Nz（∬））⇔／（∬）≦′（y）（y∈Z乃）

普通の凸関数の場合と同様に，離散凸関数が上記の性質P2を満たすならば，離散凸関数に対しても降下法により，簡単に最小解を求めることができる．

αr＋（1−α）yは一般に整数ベクトルとは限らない．
Mi11er［6］はベクトルzの代わりに近傍
HC（z）＝（z′∈Z柁ILzJ≦z；≦「zコ（∀わ）（図7参照）を用いた不等式

さて，離散凸関数の候補に挙げられている凸拡張可min（f（z′）lz，∈HC（z））≦d（x）＋（1−α）f（y）

能関数であるが，性質P2を満たすとは限らないことを考え，任意のエ，y∈dom／およぴα∈【0，1］に対しが次の例からわかる．

てこの不等式を満たす離散関数／：Z〝→RU（＋∞）を

例4（凸拡張可能だがP2を満たさない例）．関数

離散凸関数と定めた．

Mi11erの離散凸関数は性質P2を満たすことが知られている［6］．一方，Millerの離散凸関数は凸拡張
丁32（48）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

□rzl
才Z●
図9 整数ベクトル集合の局所凸拡張．斜線の領域が局所H （z）

凸拡張を表す．左の集合は整凸であるが，右の集合

図7 集合HC（z）の定義．黒丸で表されるベクトルzには整凸ではない

対して，HC（z）に含まれる点は白丸で表されるえる．このとき，局所凸拡張／の∬における値f（J）はて石（∬）により定められる．例えば一変数？

離散関数の場合，局所凸拡張／は図3のように区分線形関数により与えられる．その定義により，局所凸●

拡張は常にf（〝）＝／（y）（y∈Z乃）を満たすこと■に注意されたい．なお，整数ベクトル集合の局所凸拡張は図9に示されるような集合となる．

離散関数の局所凸拡張は必ずしも凸関数とは限らな

図8 Millerの離散凸性を満たすが凸拡張可能でない集合の例．黒丸が集合内の点を表す．点（1，1，1）が含まい．Favati−Tardella［1］は，局所凸拡張jが凸関数れていないことに注意されたいとなるような離散関数′を整凸関数と定めた．その定義により，整凸関数は凸拡張可能であり，かつMi11erの離散凸性を満たすことが示せる．したがっ可能であるとは限らない．て，離散凸関数として満たすべき性質PlおよびP2

例5（Millerの離散凸関数でPlを満たさない例）．
S＝（∬∈Z3lェ1＋∬2＋∬3≦2，∬f≧0（∀f））

を，整凸関数は満たす．このように，整凸関数は凸拡∪（（1，2，0），（0，1，2），（2，0，1））

張可能関数やMillerの離散凸関数に比べるとより良により与えられた集合S⊆Z3（図8参照）に対し，そい性質をもつ関数であるが，以下に述べるように，離の標示関数8sはMillerの離散凸関数である．しかし，散凸関数としてはまだ不十分な概念である．
一つの例として，（0，1）一ベクトル集合（0，1）乃の上で（（1，2，0）＋（0，1，2）＋（2，0，1））／3定義された離散関数（以下，（0，1）一離散関数）につい＝（1，1，1）孝S●により∂ざはPlを満たさない．

□

したがって，Mi．11erの離散凸関数も，離散凸関数としては不十分な概念である．

5．Favat卜Tardeて考える．組合せ最適化問題のほとんどは，（0，1）一離散関数の最小化問題として定式化できる．任意の（0，1）−離散関数の局所凸拡張は必ず凸関数になるので，aの離散凸関数

本節では，Favati−Tardella［1］の提案した整凸関数という概念を紹介する．整凸関数は凸拡張可能性とMillerの離散凸性の両方を満たす概念である．

（0，1ト離散関数全体は整凸関数のクラスに含まれる．
しかし，（0，1）一離散関数の中にはNP困難な組合せ最適化問題に対応する関数も存在するが，そのような関数は離散凸関数として相応しいとはいえない．

また，整凸関数はMillerの離散凸関数の特殊ケー整凸関数を定義するために，まず離散関数／：Z乃→スなので，「局所最小＝大域的最小」という性質P2RU（＋∞）の局所凸拡張ア：R乃→RU（＋∞）を定義を満たす．しかし，近傍Nz（∬）（∬∈Z刀）は3乃個のベする．任意の実ベクトル∬∈R刀に対し，′を近傍クトルを含むので，局所最小性のチェッHC（∬）の上へ制限して得られる離散関数ムをを要する．これでは，離散最適化の観点から見て，

ム（z）＝ （／（z）（z∈HC（J）），

「良い」性質とは必ずしもいえない．この点を踏まえ，＋∞（その他）

離散凸関数の満たすべき性質としてP2より強い性質により定め，その凸閉包（ム）：R乃→RU（＋∞）を考
2002年11月号

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

（49）丁33

P2′［局所最小＝大域的最小（多項式時間版）］

ある近傍命z（∬）⊆Nz（J）が存在して，レ○／（∬）≦／（y）（y∈丙z（∬））←＝⇒／（∬）≦／（y）（y∈Z乃），○局所最小性のチェックが多項式時間で可能．
Jl∧

例えば，分離凸関数／（∬）＝∑力（∬f）の場合，
i＝1丙z（∬）＝（∬±ズ∫け＝1，2，…，乃）という近傍を選ぶことにより，性質P2′が成り立つ

図10 Lq凸集合

ことが分かる．ここでズf∈（0，1）乃（ブ＝1，2，…，乃）は第オ成分に関する単位ベクトルを表す．

′（∬）＋／（y）≧′（（J−α1）＞y）＋／（∬＜（y＋α1））を満たす離散関数／：Z乃→RU（＋∞）はLq凸関数と次に，定理2で述べた分離定理の離散版を考える．
P3［離散分離定理］呼ばれる．ここで1∈Z乃はすべての成分が1である「離散凸関数」／：Z乃→RU（＋∞）と「離散凹関ベクトルである．Lq凸関数は，劣モジ云ラ不等式数」g：Z乃→RUト∞）に対し，／（∬）≧g（∬）（∬∈（J，y∈dom／）を満たす整凸関数として特徴づけられる．また，ピZ乃）が成り立つならば，／（∬）≧〆∬十α≧g（∬）（∬∈Zりを満たす♪∈R乃とα∈Rが存在する．

凸関数は次の離散中点凸性を用いても特徴づけできる：

凸関数に対する分離定理の場合と同様に，離散分離定／（闇）＋′（牌）≦′（か′（y）

理は離散最適化において理論とアルゴリズム構築の両面で非常に有用な性質である．分離凸関数については，（エ，〟∈dom／）．

性質P3が成り立つことが比較的簡単に示せる．一方，ここで，任意のペグトルZ∈R刀に対し整数ベクトル整凸関数に対してはP3は必ずしも成り立たない．

「zl，Ld∈Z〃は（「zl）f＝「Z］，（Lz」）ど＝Lz山こより，それぞれ与えられる．Lh凸集合の例を図10に示す．
上記の特徴づけより，Lり凸関数は整凸関数であることがわかる．したがって，離散凸関数として満たす

例6（整凸関数でP3を満たさない例）．
／（Jl，J2）＝maX（0，∬1＋∬2−1）（（礼∬2）∈Z2），g（∬1，J2）＝min（Jl，J2）（（れ，∬2）∈Z2）
により与えられる関数／とgはそれぞれ整凸およびべき性質PlおよびP2を満たすが，さらに性質P2′整凹であるが，′（J）≧〆∬十α≧g（∬）を満たす♪∈R2，およびP3も満たすことが知られている．

α∈Rは存在しない．max（0，1／2＋1／2−1）＜min（1／2，1／2）となることに注意されたい．

定理7．Lh凸関数／：R乃→RU（十∞）および∬∈
ロ

L凸関数とM凸関数は室田［7，8］により提案されに帰着できるので，局所最小性を多項式時間で調べると等価な概念である，Lh凸関奴（藤垂一室田［2］）およことができる．

れらの概念に関してより詳しくは文献［9−11］を参照されたい．

口

上記の局所最小性判定は劣モジュラ集合関数の最小化た概念である．本節では，L凸関数およびM凸関数
びMq凸関数（室日ヨ一塩浦［12］）について考える．こ●dom′に対し，以￣Fが成り立つ：／（∬）≦′（J±d）（∀d∈（0，1）り←⇒′（∬）≦′（y）（∀〝∈Zり．

6．L凸関数とM凸関数

定理8．ピ凸関数′：Z乃→RU（＋∞）とLh凹関数
g：Z〃→RU（−∞）に対し，（適当な仮定のもとで）／（∬）≧g（J）（∬∈写りが成り立つならば，式（3）を満た

6．1Lh凸関数

すカ∈R〝とα∈Rが存在する．さらに，／とタの関任意のベクトル∬，y∈Z乃に対し，ベクトル∬＜y，数値が整数の場合には，式（3）を満たすカ∈Z刀とα∈Z∬＞〟∈Z乃をそれぞれ（∬＜y）∫＝min（∬f，机），（J＞y）．＝
max（∬ ，机）（才＝1，2，…，乃）により定義する（図10参照）．任意の∬，〟∈Z乃および非負整数αに対して

丁34（50）●／（∬）十／（y）≧／（∬＞y）十／（ェ＜〝）が存在する．

ロ

リ凸関数は和の演算に関しては閉じていることが示せるが，たたみ込みに関しては閉じていない．二つ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

のLh凸関数のたたみ込みにより表現できる関数は艮す．さらには，性質P2′およびP3も成り立つこと凸関数と呼ばれている．Lち凸関数は，U凸関数全体がわかっている．

を含む関数のクラスであり，また整凸関数のクラスに含まれることが知られている．したがって，Lち凸関数に対して性質PlおよびP2が成り立ち，さらに性定理9．岬凸関数／：Z乃→RU（＋∞）および∬∈dom／に対し，以下が成り立つ：／（∬）≦／（∬−ズf＋ぉ）（∀オ，ノ），／（∬）≦′（∬±ズf）（∀わ

質P2′も成り立つ．しかし，性質P3については成り立たない例が存在する．

口

上記の局所最小性を判定するには乃2＋乃＋1個のベク

6．2 Mh凸関数

トルを調べればよいことに注意されたい．

M凸関数は次の交換公理により定義される（図11

定理10．M凸関数／‥Z乃rRU（＋∞）とM凹関数♂：Z刀→RU（−∞）に対し，（適当な仮定のもとで）参照）：／（ェ）≧g（∬）（∬∈Z乃）ゲ成り立つならば，式（3）を満た∀∬，〝∈dom′，∀オ∈（ゐIJ力＞如）：す少∈R乃とα∈Rが存在する．さらに，／とgの関（i）／（∬）十′（〟）≧／（∬−ズf＋ん）＋／（〟＋ズ〜−お）（ヨノ∈（々l∬烏＜y烏）），もしくは●←＝⇒／（∬）≦／（y）（∀〝∈Zり．

数値が整数の場合には，式（3）を満たすカ∈Z乃とα∈Zが存在する．

（ii）／（∬）＋／（y）≧′（∬−ズf）＋／（y十ズf）．

ロ

M凸関数はたたみ込みの演算に関しては閉じていM凸集合の例を図11に示す．

ることが示せるが，和に関しては閉じていない．二つM凸関数は整凸関数であることが知られている．のM凸関数の和により表現できる関数はM隻凸関数

したがって，M凸関数は性質PlおよびP2を満たと呼ばれている．M呈凸関数は，その定義より明らかにM凸関数全体を含む関数のクラスであり，また整凸関数のクラスに含まれることが知られている．したがって，M隻凸関数に対して性質PlおよびP2が成り立ち，さらに性質P2′も成り立つ．しかし，性質P3については成り立たない例が存在する．

7．おわりに本稿で扱った，様々な離散凸性の関係を図12にまとめた．ピ凸関数とM凸関数の共通部分，および図11Mq凸集合

u凸関数とM皇凸関数の共通部分がそれぞれ分離凸●

図12 様々な離散凸性の関係
2002年11月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（51）735関数のクラスに一致していることに注意されたい．
本稿では，最後に，本稿を書く機会を与えて下さった毛利裕昭氏，およびこの原稿に対する有用なコメントを下さった田村明久氏，徳山豪氏，森口聡子氏に感謝したい．

Millerの離散凸関数→整凸関数→M凸／Lh凸関数
参考文献の順に離散凸関数の概念を紹介してきた．しかし，これは実際の研究の流れとは異なっており，M凸関数
およびLq凸関数の概念はMillerの離散凸関数や整凸関数の概念とは独立に提案されたことを断っておく．

M凸関数およびU凸関数の概念が提案されるまでの

1inearintegerprogramming ，RiceYra QPemtiva，53，3−
44（1990）．

［2］Fujishige，S．and Murota，K．： Notes on L−／M−
COnVeXfunctionsandtheseparationtheorems

歴史的な流れを簡単にまとめると，，Math．

P和好和椚∽わ曙，88，129−146（2000）．
［3］福島雅夫： 非線形最適化の基礎 ，朝倉書店（2001）．

マトロイド → 付値マトロイド
J［1］Favati，P．and

5‑

ポリマトロイド → M凸（M勾凸）関数［4］福島雅夫： 数理計画入門 ，朝倉書店（1996）．

［5］茨木俊秀，福島雅夫： 最適化の手法 ，共立出版（1993）．

劣モジュラ集合関数 → L凸（Lh凸）関数［6］Miller，B・L・： On minimizing nonseparable func−tionsdefinedontheintegerswithaninventoryappli−のようになる．離散凸関数の歴史について詳しくは文献［10］を参照されたい．

Cation，SL4MJAMl．Math．，21，166−185（1971）．

［7］Murota，K．： Convexity and Steinitz s exchange

これまでの議論から，Lb凸関数とげ凸関数は離散凸関数として満たすべき性質Pl，P2′，およびP3を満たすことが分かった．このことからLh凸性やM凸性をもつ離散最適化問題は「解きやすい」ということがわかり，実際に効率的なアルゴリズムが提案されproperty ，Adv．Math．，124，272−311（1996），［8］Murota，K：

Discrete convex analysis

P，℃g用∽研ブタ材，83，313−371（1998）．
［9］室田一雄： 離散凸解析 ，藤垂悟（編），離散構造とアルゴリズムⅤ，近代科学社（1998），51−100．ている［10，11］．しかし，性質Pl，P2′，および［10］室田一維： 離散凸解析，：，共立出版（2001）．

P3を満たす離散関数はピ凸関数やMり凸関数以外に［11］Murotaも存在することが分かっている．Lり凸関数やMh凸関数全体を含み，かつ性質Pl，P2′，およびP3を満たす離散関数のクラスを明確にすることが今後の課題の一つである．

，Math．

published．
［12］Murota，K．andShioura，A．：
Ongeneralizedpolymatroid

M−COnVeXfunction，Math．（砂erRes．，24，95−

105（1999）．

［13］田村明久，村松正和： 最適化法 ，共立出版（2002）．

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

オペレーションズ・リサーチ