図面 (/)

技術 組合せ問題処理装置

出願人 富士通株式会社
発明者 丸山文宏箕田依子澤田秀穂滝沢ユカ
出願日 1993年8月25日 (26年10ヶ月経過) 出願番号 1993-209811
公開日 1995年3月10日 (25年3ヶ月経過) 公開番号 1995-064967
状態 特許登録済
技術分野 複合演算 特別なプログラム実行装置 特殊なプログラム実行装置 知識ベースシステム 学習型計算機 特定用途計算機
主要キーワード 各不等式 くい切り 初期制約 ナップザック 切り出しパターン 基本遅延 線形不等式 ナップザック問題
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(1995年3月10日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (13)

目的

変数離散的な値をとる組合せ制約問題あるいは組合せ最適化問題解く組合せ問題処理装置に関し、変数値のなかの一部の値を優先的に使用すること、および、一つの解が求まったときに、その解以外の別解を求めることを可能とする。

構成

制約条件を表す不等式系101と相反する制約違反不等式を生成する初期制約違反不等式生成部102と、制約充足を調べる変数の値を制約違反条件を成立させないように変更する変数値変更部104と、値が未定の変数について制約違反条件を成立させないように選択する変数値選択部105と、変数値変更部104および変数値選択部105で変数値が決定できなかった場合に、該変数値を制約違反条件に代入して数値化し、新たな制約違反条件を生成する制約違反条件生成部106と、初期制約違反不等式生成部102および制約違反条件生成部106で生成した制約違反条件を格納する制約違反条件格納部103で構成する。

概要

背景

計算機応用分野や広がる一方であるが、組合せ制約充足問題または組合せ最適化問題を計算機によって高速解くことは、計算機の応用分野における一つの重要な課題になっている。組合せ制約充足問題あるいは組合せ最適化問題とは次のような問題である。

今、n個の変数x1,x2,… ,xn について、不等式
fk ( x1,x2,… ,xn )≦bk (k=0,1, …,m)
が与えられており、変数xi の取り得る値は、飛び飛びのcij (i=1,2,…,n ;j=1,2,3,…) であるとする。このとき、上の不等式をすべて満たすように各変数の値を決定(選択)する問題が組合せ制約充足問題である。言い換えると、
fk ( c1,s(1), c2,s(2), …, cn,s(n)) ≦bk (k=0,1, …,m)
を満たす写像s:{1,2,…, n}→{1,2,3,…}を求める問題が組合せ制約充足問題である。

例えば、論理設計において、回路中の各コンポーネントに対応する変数x1,x2,… ,xn を設け、
b0 をゲート数の上限値、
bk (k=0,1, …,m) をk番目パス(パスk)に沿った遅延時間の上限値、
a0i=1(i=1,2,…,n) 、
パスk(k=1,2,…,m) がi番目のコンポーネントを通っていればaki=1、それ以外はaki=0、
d0(xi ) はi番目のコンポーネントのゲート数、
dk ( xi ) (k=1,2,…,m) はパスkに沿った遅延時間に対するi番目のコンポーネントによる寄与(パスkがi番目のコンポーネントを通っていなければ0)として、次の不等式系

概要

変数が離散的な値をとる組合せ制約問題あるいは組合せ最適化問題を解く組合せ問題処理装置に関し、変数値のなかの一部の値を優先的に使用すること、および、一つの解が求まったときに、その解以外の別解を求めることを可能とする。

制約条件を表す不等式系101と相反する制約違反不等式を生成する初期制約違反不等式生成部102と、制約充足を調べる変数の値を制約違反条件を成立させないように変更する変数値変更部104と、値が未定の変数について制約違反条件を成立させないように選択する変数値選択部105と、変数値変更部104および変数値選択部105で変数値が決定できなかった場合に、該変数値を制約違反条件に代入して数値化し、新たな制約違反条件を生成する制約違反条件生成部106と、初期制約違反不等式生成部102および制約違反条件生成部106で生成した制約違反条件を格納する制約違反条件格納部103で構成する。

目的

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

不等式等式で与えられた制約を満たすように、各変数離散的な値を決定する組合せ制約充足問題、あるいは、不等式や等式で与えられた制約を満たし、かつ、与えられた評価関数の値を最小あるいは最大にするように各変数の離散的な値を計算機により決定する組合せ最適化問題解く組合せ問題処理装置であって、前記計算機内に、外部から指示される制約である不等式系(不等式や等式)と相反する制約違反不等式を生成する初期制約違反不等式生成部と、前記計算機内に、制約充足を調べる変数の値を現在の値から他の値に、全ての制約違反条件を成立させないように変更する変数値変更部、および、値が未定の変数について、その値を全ての制約違反条件を成立させないように選択する変数選択部と、前記計算機内に、前記変数値変更部および前記変数値選択部の処理においてすべての値が制約を満たさない(すなわち、制約違反条件のなかで成立するものがある)場合に、制約違反不等式または制約違反不等式から生成された制約違反条件のなかに現れる変数を数値化することにより、簡略化した不等式の論理積として得られる新しい制約違反条件を生成する制約違反条件生成部と、前記計算機内あるいは計算機の外部に、前記初期制約違反不等式生成部および前記制約違反条件生成部で生成した制約違反不等式および制約違反条件を蓄積する制約違反条件格納部とを有し、各変数の値のIDを表す属性値を設け、該属性値に関する制約条件を追加して組合せ問題を処理することを特徴とする組合せ問題処理装置。

請求項2

不等式や等式で与えられた制約を満たすように、各変数の離散的な値を決定する組合せ制約充足問題、あるいは、不等式や等式で与えられた制約を満たし、かつ、与えられた評価関数の値を最小あるいは最大にするように各変数の離散的な値を計算機により決定する組合せ最適化問題を解く組合せ問題処理装置であって、前記計算機内に、外部から指示される制約である不等式系(不等式や等式)に対応する制約充足不等式を生成する初期制約充足不等式生成部と、前記計算機内に、制約充足を調べる変数の値を現在の値から他の値に、全ての制約充足条件を成立させるように変更する変数値変更部、および、値が未定の変数について、その値を全ての制約充足条件を成立させるように選択する変数選択部と、前記計算機内に、前記変数値変更部および前記変数値選択部の処理においてすべての値が制約を満たさない(すなわち、制約充足条件のなかで成立しないものがある)場合に、制約充足不等式または制約充足不等式から生成された制約充足条件のなかに現れる変数を数値化することにより、簡略化した不等式の論理積として得られる新しい制約充足条件を生成する制約充足条件生成部と、前記計算機内あるいは計算機の外部に、前記初期制約充足不等式生成部および前記制約充足条件生成部で生成した制約充足不等式および制約充足条件を蓄積する制約充足条件格納部とを有し、各変数の値のIDを表す属性値を設け、該属性値に関する制約条件を追加して組合せ問題を処理することを特徴とする組合せ問題処理装置。

請求項3

請求項1および請求項2に記載の組合せ問題処理装置であって、変数値として優先的に使用したい変数値の集合が存在する場合に、該変数値のIDを表す属性値に関して該集合を表す不等式を生成し、不等式系に追加して組合せ問題を解くことを特徴とする組合せ問題処理装置。

請求項4

請求項1および請求項2に記載の組合せ問題処理装置であって、一つの解が求まった際、該解とは異なる別解を求める場合に、該変数値のIDを表す属性値に関して該解を否定する制約条件を生成し、不等式系に追加して組合せ問題を解くことを特徴とする組合せ問題処理装置。

請求項5

請求項3に記載の組合せ問題処理装置であって、変数xi (i番目の変数)の変数値に対して、優先的に使用したい順にIDとして整数(0,1,2,・・・)を割り当て、IDを示す属性値d0 (xi )に対して、優先的に使用する変数値の集合を限定する不等式d0 (xi )≦c(cは限定使用する変数値数−1)を制約条件として不等式系に加えることを特徴とする組合せ問題処理装置。

請求項6

請求項5に記載の組合せ問題処理装置であって、先に優先的に使用する変数値の集合として不等式d0 (xi )≦c(cは限定使用する変数値数−1)によって限定した変数値の集合のなかからは解が求まらなかった場合に、cの値を大きくした制約条件を不等式系に加えることにより使用する変数値の集合の制限を緩和して、再度組合せ問題を解くことを特徴とする組合せ問題処理装置。

請求項7

請求項4に記載の組合せ問題処理装置であって、求まった解についての変数xi の値のIDをσi としたとき、該IDを否定する属性値に関する制約条件として、d0 (xi )≠σi のすべての変数iについての論理和を不等式系に加えて再度組合せ問題を解き、新たな解を求めることを特徴とする組合せ問題処理装置。

技術分野

0001

本発明は、計算機により、変数離散的な値を取る組合せ制約充足または組合せ最適化問題解く組合せ問題処理装置に関する。

背景技術

0002

計算機の応用分野や広がる一方であるが、組合せ制約充足問題または組合せ最適化問題を計算機によって高速に解くことは、計算機の応用分野における一つの重要な課題になっている。組合せ制約充足問題あるいは組合せ最適化問題とは次のような問題である。

0003

今、n個の変数x1,x2,… ,xn について、不等式
fk ( x1,x2,… ,xn )≦bk (k=0,1, …,m)
が与えられており、変数xi の取り得る値は、飛び飛びのcij (i=1,2,…,n ;j=1,2,3,…) であるとする。このとき、上の不等式をすべて満たすように各変数の値を決定(選択)する問題が組合せ制約充足問題である。言い換えると、
fk ( c1,s(1), c2,s(2), …, cn,s(n)) ≦bk (k=0,1, …,m)
を満たす写像s:{1,2,…, n}→{1,2,3,…}を求める問題が組合せ制約充足問題である。

0004

例えば、論理設計において、回路中の各コンポーネントに対応する変数x1,x2,… ,xn を設け、
b0 をゲート数の上限値、
bk (k=0,1, …,m) をk番目パス(パスk)に沿った遅延時間の上限値、
a0i=1(i=1,2,…,n) 、
パスk(k=1,2,…,m) がi番目のコンポーネントを通っていればaki=1、それ以外はaki=0、
d0(xi ) はi番目のコンポーネントのゲート数、
dk ( xi ) (k=1,2,…,m) はパスkに沿った遅延時間に対するi番目のコンポーネントによる寄与(パスkがi番目のコンポーネントを通っていなければ0)として、次の不等式系

0005

0006

を考える。そうすると、この不等式系は、回路規模およびスピードに関する制約表現したものになっている。各変数xi は飛び飛びのcij (i=1,2,…,n ; j=1,2,3, …) をとるから、すなわち、各コンポーネントの実現方法は飛び飛びであるから、組合せ制約充足問題となる。

0007

一方、組合せ最適化問題は、
fk ( x1,x2,… ,xn )≦bk (k=0,1, …,m)
を満たし、かつ、評価関数
f0 ( x1,x2,… ,xn )
を最小にする問題である。

0008

例えば、紙ロールからいろいろな型紙を裁断する際や、大きな材木からいくつかの形状の切り出す際に、無駄を最小にする問題(「カッティングストック問題」と呼ばれている)において、各材木(紙ロール)に対応する変数x1,x2,… ,xn を設け、bk (k=1,2, …,m) をk番目の棚(型紙)の必要最小数、dk ( xi ) (k=1,2, …,m) をi番目の材木(紙ロール)から切り出されるk番目の棚(型紙)の数とすると、制約は次の不等式系で表現され、

0009

0010

問題は次の評価関数を最小にすることになる。

0011

0012

ただし、d0(xi ) はi番目の材木(型紙)から出る無駄(使われない面積)である。各変数xi は飛び飛びのcij (i=1,2,…,n ; j=1,2,3, …) をとるから(すなわち、切り出し方は飛び飛び)、組合せ最適化問題となる。

0013

以上は、不等式、評価関数とも線形の場合であったが、一般には線形とは限らない。論理設計の例では、厳密に言うと、一つのコンポーネントのあるパスに沿った遅延時間は、その接続先のコンポーネントの実現方法に依存する。すなわち、コンポーネントCのパスkに取った遅延時間は、
(Cの基本遅延時間)
+(Cの負荷容量依存係数)×[(Cから接続先までの配線の容量)
+Σ{(コンポーネント内配線の容量)+(入力容量の総和)}]
で計算される(ただし、和はパスkに沿ってCの先に接続しているコンポーネントについて取る)。したがって、不等式には異なる変数の積の項が現れ、非線形となる。

0014

このような組合せ制約充足問題は潜在的な解空間が組み合わせ的に大きくなり、変数が連続値をとる場合の問題に比べて一層難しい問題であると認識されており、単純な探索方式は適用できない。

0015

ところが、見かけ上の解空間のなかで求める解が存在しない部分を識別できるケースがあり、このような構造を有効に利用することにより、効率的に解を求めることが可能になる場合がある。

0016

従来の技術としては、組合せ制約充足問題を計算機によって解く方式として、(a)整数計画法、(b)分岐限定法、(c)線形計画法、(d)ATMS等がある。
(a) 整数計画法
飛び飛びの値をとる変数を扱うために、整数値を取る変数を導入する。特に、0または1を取る変数を導入する。ところが、この処理により変数の数が増えるという問題がある。すなわち、前述した記法に従えば、n個の変数x1,x2,… ,xn を扱う代わりに、cij (i=1,2,…,n ; j=1,2,3, …) をすべて変数にする必要がある。この結果、整数計画法の計算時間は、変数の数について指数的に増加する傾向にあり、変数の増加により計算時間が大幅に延びてしまうという問題がある。
(b) 分岐限定法
変数の値を決定(選択)する際、一部の範囲に限定して制約を満たしているかどうかをチェック評価関数値を求める。チェックや評価関数計算ができない(あるいは、それまでに求まっている評価関数値を下回る可能性が残っている)なら、さらに範囲を限定する。ある範囲に限定した場合の評価関数値がそれまでに求まっている評価関数値を下回る可能性がないなら、その範囲は捨てる。ところが、この方法では、ある範囲に限定して制約を満たしているかどうかチェックし、評価関数値を求めた過程の情報がそれ以降に利用されないため、不適当変数値を繰り返し選択する可能性があるという問題を有する。
(c) 線形計画法
変数が連続値を取りうるとして最適解を求め、それに近い離散値を解とする。ところが、このように近似した場合、得られた解が制約を満たすという保証も最適であるという保証もなくなる。これがこの手法の問題点である。
(d) ATMS(assumption based truth maintenance system)
制約を満たさなかった変数値の組合せを格納しておき、それを含むような組合せは捨てる。ところが、変数値の組合せの数が膨大となるため、扱える問題の規模が限られるという問題がある。なお、このATMSに関する参考文献としては、以下のものがある。

0017

J. de Kleer: An Assumption-based Truth Maintenance System, ArtificialIntelligence 28 (1986).

発明が解決しようとする課題

0018

本発明に先立ち、本発明者等は、変数が離散的な値をとる組合せ制約充足問題を対象として、処理の途中時点までに得られた失敗情報をそれ以降の処理で最大限に利用することにより、効率的に組合せ制約充足問題を解決する技術手段を提供している(特願平3−297496号)。

0019

この先の発明では、計算機により、不等式で与えられた制約を満たすように、各変数の離散的な値を決定する組合せ制約充足問題を解くために、次の処理部等を備えている。
初期制約違反不等式生成部:外部から指示される制約である不等式系(不等式や等式)と相反する制約違反不等式を生成する。
変数値変更部:制約充足を調べる変数の値を現在の値から他の値に変更する。
変数値選択部:値が未定の変数について、その値を選択する。
制約違反条件生成部:上記変数値変更部および上記変数値選択部の処理においてすべての値が制約を満たさない(すなわち、制約違反条件のなかで成立するものがある)場合に、制約違反不等式または制約違反不等式から生成された制約違反条件のなかに現れる変数を数値化することにより、簡略化した不等式の論理積として得られる新しい制約違反条件を生成する。
制約違反条件格納部:上記制約違反条件生成部で生成した制約違反条件を蓄積する。

0020

そして、変数の値を変更/選択する際には、既に上記制約違反条件格納部に格納されている制約違反条件をどれも成立させないように行なうように構成されている。

0021

この先の発明では、変数値変更/選択処理において、ある変数の変数値の変更/選択に失敗する(すなわち、すべての変数値について、それぞれ少なくとも一つの制約違反条件が成立する)と、各変数値について成立している制約違反条件をそれぞれ一つ選び、各々の条件中の当該変数にその変数値を代入して簡略化し、これらすべての論理積を作り、制約違反条件としてに格納する。この制約違反条件には、もはや当該変数は含まれない。

0022

この制約違反条件は現在成立しているから、これに含まれる変数に対応する現在の変数値の組合せを禁止する条件となるが、禁止する組合せは現在の組合せに限定されず、この制約違反条件を満たす組合せはこれ以降すべて禁止される。

0023

制約違反条件が生成されると、該制約違反条件が成立しないように、それに現れる変数の値を変更する。変数変更に失敗すると、再び制約違反条件を生成し、変更に成功すると、値が未定の変数が残っているか否かを調べ、あれば、該変数値を選択する。値が未定の変数が残っていないならば、解が求まっていることになる。

0024

第4図は、本発明の作用説明図である。実線試行済みの経路点線は未試行の経路を表している。×で示す箇所で制約違反が検出されると、制約違反条件
fk ( x1,x2,a3,… ,an )>bk (ただし、a3,… ,an は定数
が生成される。この制約違反条件を満たす組合せは、第4図に△で示すように、これ以降はすべて禁止されることになり、処理の無駄を省くことができる。

0025

一方、先の発明は、制約違反条件を蓄積して制約違反条件をどれも成立させないように変数の値の変更/選択をする代わりに、制約違反条件と反対の意味を持つ制約充足条件を蓄積し、この制約充足条件を満たすように変数の値の変更/選択をしても技術的に全く同等の処理ができる。

0026

制約充足条件を用いる場合には、次のような処理部で構成することができる。
’初期制約充足不等式生成部:外部から指定された不等式系(不等式や等式)から制約充足を示す不等式を生成する。
’変数値変更部:制約充足を調べる変数の値を現在の値から他の値に変更する。
’変数値選択部:値が未定の変数についてその値を選択する。
’制約充足条件生成部:上記変数値変更部および上記変数値選択部の処理においてすべての値が制約を満たさない(すなわち、制約充足条件のなかで成立しないものがある)場合に、制約充足条件中に現れる当該変数を数値化することにより簡略化した不等式の論理和として得られる制約充足条件を生成する。
’制約充足条件格納部:上記の制約充足条件生成部が生成した制約充足条件を蓄積する。

0027

また、与えられた不等式の系(制約)お満たし、かつ、与えられた評価関数の値を最小または最大にするように各変数の離散的な値を決定する組合せ最適化問題に対しては、評価関数に対応する不等式(「可変不等式」と呼ぶ)を設け、与えられた不等式の系に可変不等式を付加した組合せ充足問題を、上記方式によって解き、可変不等式の制約値を、
(得られた評価関数値)─ε <ここでεは十分小さな正数
更新し、上記組合せ制約充足方式を繰り返し適用することにより、求める解を得るようにすることが可能である。

0028

組合せ最適化問題の具体例として、先の発明を適用した例を説明する。問題としては、『数理計画(刀根薫著)』に挙げられているナップザック問題取り上げる。この問題は以下のようなものである。
〔問題〕
『遠足に持っていくナップザックに入れていく候補の品物が4種類ある。容量の制限を満たして期待される価値の総和を最大にしたい。

0029

番目の品物(以下ではAgent(0)) の大きさは6で、期待される価値は1である。選択肢(alternative) は、入れていく(Agent(0)=1)、入れていかない(Agent(0)=2)の二つである(他の品物でも同じ)。

0030

1番目の品物の大きさに対応する変数を(0,1) 、期待される価値に対応する変数を(0,2) と書く(他の品物でも同様)。2番目の品物(Agent(1)であり) の大きさは8で、期待される価値は3、3番目の品物(Agent(2)であり) の大きさは5で、期待される価値は7、4番目の品物(Agent(3)であり) の大きさは2で、期待される価値は3である。

0031

入れていかないときのその品物の大きさと期待される価値は0と考える』この問題において、容量制限を14とする。
制約条件と評価関数〕
制約条件は、
(0,1) +(1,1) +(2,1) +(3,1) ≦constraint(0)
ただし、constraint(0) はナップザックの容量制限。

0032

制約違反不等式は、
(0,1) +(1,1) +(2,1) +(3,1) >constraint(0)
となる。

0033

また、価値の評価関数は(0,2) +(1,2) +(2,2) +(3,2) であり、これを最大にしたい。評価関数も次の可変不等式として扱う。すなわち、
(0,2) +(1,2) +(2,2) +(3,2) ≧constraint(1)
である。以上の2式が制約違反条件格納部に格納される。ここで、constraint(0) =14,初期の価値の下限値constraint(1) = 0として制約充足処理を実行する。
〔実行例〕
0+(1,1)+(2,1)+(3,1)>constraint(0) has been generated. (a)
1+(1,2)+(2,2)+(3,2)<constraint(1) has been generated. (b)
1+(2,2)+(3,2)<constraint(1) & 8+(2,1)+(3,1)>constraint(0)
has been generated. (c)
4+(2,2)+(3,2)<constraint(1) has been generated. (d)
8+(3,2)<constraint(1) & 13+(3,1)>constraint(0) has been generated.(e)
11+(3,2)<constraint(1) has been generated. (f)
11<constraint(1) & 15>constraint(0) has been generated. (g)
Design completed !
The alternative of each agend is:
Agent(0)=1, Agent(1)=2, Agent(2)=1, Agent(3)=1
解説〕以下、上記実行例について解説する。
(A)まず、すべての品物を入れていくとする。

0034

Agent(0)=1, Agent(1)=1, Agent(2)=1, Agent(3)=1
この大きさの総和は21であるから、14の容量制限をオーバーする。
(B)Agent(0)についての変数値変更を試みるが、変数値変更に失敗して、菓子を入れていく場合の大きさ6を代入した不等式と、菓子を入れていかない場合の大きさ0を代入した不等式の論理積を取り、制約違反条件(a)を生成する。

0035

このとき、Agent(0)=x (不定), Agent(1)=1,Agent(2)=1,Agent(3)=1 .
(C)Agent(1)についての変数値変更に成功する。
Agent(0)=x (不定), Agent(1)=2,Agent(2)=1,Agent(3)=1 .
(D)Agent(0)についての変数値選択に成功する。容量の解は11になる。

0036

Agent(0)=1, Agent(1)=2,Agent(2)=1,Agent(3)=1.
(E)constraint(1) を12に更新して再評価すると、変数値変更に失敗して、可変不等式に対応する制約違反不等式に1 と0 を代入した条件の論理積により制約違反条件(b) を生成する。

0037

Agent(0)=x (不定), Agent(1)=2,Agent(2)=1,Agent(3)=1 .
(F)Agent(1)についての変数値変更にも失敗して、制約違反条件(b) に0 を代入した条件と制約違反条件(a) に8 を代入した条件の論理積により制約違反条件(c) を生成する。

0038

Agent(0)=x (不定), Agent(1)=x ( 不定),Agent(2)=1,Agent(3)=1 .
(G)Agent(2)についての変数値変更に成功する。
Agent(0)=x (不定), Agent(1)=x ( 不定),Agent(2)=2,Agent(3)=1 .
(H)Agent(1)についての変数値変更に失敗して、制約違反条件(b) に3 と0 を代入した条件の論理積により制約違反条件(d) を生成する。
(I)Agent(2)についての変数値変更に失敗して、制約違反条件(c) に5 と7 を代入した条件と制約違反条件(d) に0 を代入した条件の論理積により制約違反条件(e) を生成する。

0039

Agent(0)=x (不定), Agent(1)=x ( 不定),Agent(2)=x( 不定),Agent(3)=1 .
(J)Agent(3)についての変数値変更に成功する。
Agent(0)=x (不定), Agent(1)=x ( 不定),Agent(2)=x( 不定),Agent(3)=2 .
(K)Agent(2)についての変数値変更に失敗して、制約違反条件(d) に7 と0 を代入した条件の論理積により制約違反条件(f) を生成する。
(L)Agent(3)についての変数値変更に失敗して、制約違反条件(e) に2 と3 を代入した条件と制約違反条件(f) に0 を代入した条件の論理積により制約違反条件(g) を生成する。
◎ 解(11)が一つ得られ、それ以上の解がみつからなかったため、解(11)が最適解と分かる。

0040

Agent(0)=1, Agent(1)=2,Agent(2)=1,Agent(3)=1 .
以上の例から分かるように、先の発明によれば、生成された制約違反条件は、これらに含まれる変数に対応する現在の変数値の組合せを禁止する条件となるが、禁止する組合せは現在の組合せに限定されず、この制約違反条件を満たす組合せはこれ以降すべて禁止されることになり、解空間を狭めることが可能になる。

0041

例えば、制約違反条件(または制約充足条件)の係数がすべて1の線形不等式なら、和が現在の変数値の和以上(さらには、制約値から既に数値化された部分の和を差し引いた値以上(これは現在の変数値の和を上回ることはない))となるすべての組合せが禁止されることになり、無駄な探索が省略できる。これによって、制約充足問題解法時間の短縮が可能になる。

0042

この他、先の発明では、初めからすべての変数値が既知でないような場合であって、新しい変数値を後で追加するような場合に、当該変数の値がこれ以上ないことを示すフラグまたは当該変数の値がこれ以上あることを示すフラグを付加し、実際に当該変数の新しい変数値を使用する際には、このフラグが付いている制約違反条件または制約充足条件を無効にし、新しい変数値に対応できるようにする方法を開示している。

0043

また、先の発明では、不等式の関数の値が単調増加あるいは単調減少するような問題において、変数値の組合せが成立しない場合に、不等式の左辺偏微分係数を利用して新たな制約違反条件あるいは制約充足条件を生成し、これを使って問題を解く方法を開示している。

0044

また、先の発明では、複数のプロセサを使用し、各プロセサに、変数値、もしくは、制約違反条件または制約充足条件等を分割して持たせることにより、並列的に問題を解く方法を開示している。

0045

ところで、組合せ制約問題を解く場合には、各変数に対して、変数値変換部および変数値選択部が値を設定し、その値によって制約違反条件が成立するか否か、また制約充足条件が成立するか否かを判断して処理を進めていくが、このとき、先の発明では、変数値として取りえる値をすべて変数に設定して判断することが基本となっている。ところが、変数値のなかには、変数値として好ましい変数値と好ましくない変数値が存在する場合がある。先の発明の方式では、好ましくない変数値も好ましい変数値と同様に設定されて判断され、条件を満たせば解となる可能性があるという問題があった。

0046

また、先の発明では、一つの解が見つかった時点で処理が終了し、他の解を見つけることができないという問題があった。本発明は、先の発明をさらに発展させ、変数の値のうちの一部の値を可能なかぎ使いたいというユーザの要請(ユーザの好み)や、得られた解以外の別解を求めたいという要請(制約では表現できなかった解の好ましさ)に答えることのできる組合せ制約問題処理装置を提供することを目的とする。

課題を解決するための手段

0047

第1図は、本発明の第一の原理構成図である。第一の原理構成は、制約違反条件を生成する解法についての原理構成である。

0048

本発明は、CPUおよびメモリ等からなる計算機上に構築し、外部より与えられる制約を表現する不等式系についての組合せ制約充足問題あるいは組合せ制約最適化問題を解くことを前提とする。

0049

第1図において、まず、計算機100内に設けられる初期制約違反不等式生成部102は、外部より与えられた不等式系101の各不等式からそれに相反する不等式、すなわち、制約違反の十分条件となる初期制約違反条件を生成する。例えば、左辺≦右辺の不等式に対して左辺>右辺、左辺≧右辺の不等式に対して左辺<右辺が制約違反不等式である。

0050

また、計算機100に接続された二次記憶装置内に設けられる制約違反条件格納部103は、初期制約違反不等式生成部102が生成した制約違反不等式や、制約充足処理中に生成される制約違反条件を蓄積する。制約違反条件格納部103は、計算機100外の二次記憶装置内に設けることもできるが、また、計算機100内のメモリ中に設けることも可能である。

0051

一方、これも計算機100内に設けられた変数値変更部104は、変数値の値を現在の値から他の値に変更する。この変更処理は、制約違反条件格納部103に格納されている制約違反条件をどれも成立させないように行なう。値が未定の変数を含む制約違反条件は不成立とみなす

0052

また、計算機100内に設けられた変数選択部105は、値が未定の変数についてその値を選択する。このとき、制約違反条件格納部103に格納されている制約違反条件をどれも成立させないように選択する。値が未定の変数を含む制約違反条件は不成立とみなす。

0053

さらに、計算機100内に設けられた制約違反条件生成部106は、変数変更部104または変数選択部105の処理で変数値の変更/選択が不可能であった場合に、新しい制約違反条件を生成する。生成した新しい制約違反条件は、制約違反条件格納部103に格納する。

0054

この結果、制約違反条件格納部103には、処理開始直後には初期制約違反不等式生成部102が設定した初期制約違反不等式のみを格納し、その後、制約違反条件生成部106が生成した制約違反条件を順次格納する。

0055

第2図は、第1図の原理構成図のなかの不等式系101を詳細構成の説明図である。制約条件定式化部201は、解くべき問題の制約条件を不等式または不等式の論理和で表現し、初期の不等式系を生成する。作成した初期の不等式系は第1図の不等式系101に対応し、ここに蓄えたうえで、初期制約違反不等式生成部102に送ることになる。

0056

一方、これも不等式系101に接続されているID不等式追加部202は、組合せ制約問題を解く場合に、変数の値のうちの一部の値を可能な限り使いたいという場合に稼働する。ID不等式追加部202は、変数の値についてのIDを表す特別の属性値に関する不等式を不等式系101に追加する。すなわち、例えば、各変数値に対して好ましいことをを表す特別の属性値(小さい値)を割り当て、好ましい変数値の該属性値(小さい値)と好ましくない変数値の該属性値(大きい値)を区別できるようにする。そして、好ましい変数値をまず使用できるように該属性値に関する不等式系を(ある値よりも小さい該属性値を使用する制約条件)作成し、これを不等式系101に追加する。

0057

さらに、これも不等式系101に接続されている現在解禁止不等式追加部203は、ある解が求まったときに、その解以外の別解が欲しい場合に稼働し、現在の解を禁止する不等式を生成し、不等式系101に追加する。

0058

第3図は、本発明の第二の原理構成図である。制約充足条件を生成する解法についての原理構成図を示している。まず、計算機300内に設けられる初期制約充足不等式生成部302は、外部より与えられた不等式系301から、制約充足条件を示す不等式を生成する。

0059

また、計算機300に接続された二次記憶装置内に設けられる制約充足条件格納部303は、初期制約充足不等式生成部302が生成した制約充足不等式や、制約充足処理中に生成される制約充足条件を蓄積する。制約充足条件格納部303は、計算機300外の二次記憶装置内に設けることもできるが、また、計算機300内のメモリ中に設けることも可能である。

0060

一方、これも計算機300内に設けられた変数値変更部304は、変数値の値を現在の値から他の値に変更する。この変更処理は、制約充足条件格納部303に格納されている制約充足条件をすべて満たすように行なう。値が未定の変数を含む制約充足条件は成立しているとみなす。

0061

また、計算機300内に設けられた変数選択部305は、値が未定の変数についてその値を選択する。このとき、制約充足条件格納部203に格納されている制約充足条件をすべて成立させるように選択する。値が未定の変数を含む制約充足条件は成立しているとみなす。

0062

さらに、計算機300内に設けられた制約充足条件生成部306は、変数変更部304または変数選択部305の処理で変数値の変更/選択が不可能であった場合に、新しい制約充足条件を生成する。生成した新しい制約充足条件は、制約充足条件格納部303に格納する。

0063

この結果、制約充足条件格納部303には、処理開始直後には初期制約充足不等式生成部302が設定した初期制約充足不等式のみを格納し、その後、制約充足条件生成部306が生成した制約充足条件を順次格納する。

0064

第二の原理構成も、第一の原理構成と同様に、不等式系301の部分は第2図のような構成になっている。すなわち、初期の制約条件を不等式系301に入力する制約条件定式化部201と、好ましい変数値を表す特別の属性値に関する不等式を不等式系301に追加するID不等式追加部202と、得られた解とは別な解を求めるために、現在得られた解を禁止する不等式を不等式系301に追加する現在解禁止不等式追加部203からなる。

0065

以上の原理構成の動作を次に説明する。まず、第1図の制約違反条件を生成して問題を解く方式の原理構成の動作を説明する。

0066

最初に、制約条件定式化部201(図2)を稼働し、ユーザが解きたい組合せ問題についての不等式系101を計算機100に入力する。このとき、変数値として使用したい変数値の集合がある場合には、ID不等式追加部202(図2)を起動し、各変数値についてそのIDで示す特別の属性値に値を設定し、該属性値に関する不等式を計算機100に入力する。この属性値に関する不等式を不等式系101に加えることにより、ある範囲の値(ID)の該属性値をもつ変数値を優先的に使用することが可能になる。優先的に使用する変数値では解が求まれない場合には、上記の制約条件を解除し、その他の変数値も含めた解を求めることになる。

0067

計算機100は、不等式系101の入力を受けて、初期制約違反不等式生成部102を起動し、入力された不等式系101と相反する不等式を生成し、初期制約違反不等式として制約違反条件格納部103に格納する。このとき、不等式系101に大小関係を示す純粋な不等式だけではなく等式が含まれる場合、与えられた制約である等式を等価な二つの不等式に変更することにより、等式を含む制約に対しても、その充足を行なわせることが可能である。先に不等式系101に付加した好ましい変数値を優先的に使用するための特別の属性値に関する不等式も、他の初期制約条件と同様に初期制約違反不等式生成部102で初期制約違反不等式として制約違反条件格納部103に格納されるので、以下、他の制約違反条件と同様に処理されることになる。

0068

初期制約違反不等式が制約違反条件格納部103に格納されると、次に、変数値変更部104と変数値選択部105が起動される。変数値変更部104は、制約違反条件格納部103に格納されている制約違反条件をどれも成立させないように変更する。また、変数値が未定の変数が存在する場合には、変数値選択部105が該変数値を選択する。この場合も、制約違反条件格納部103に格納されている制約違反条件をどれも成立させないように選択する。

0069

この変数値変更/選択処理において、ある変数の変数値の変更/選択に失敗する(すなわち、すべての変数値について、それぞれ少なくとも一つの制約違反条件が成立する)と、制約違反条件生成部106が起動される。制約違反条件生成部106は、各変数値について成立している制約違反条件をそれぞれ一つ選び、各々の条件中の当該変数にその変数値を代入して簡略化し、これらすべての論理積を作り、制約違反条件として制約違反条件格納部103に格納する。この制約違反条件には、もはや当該変数は含まれない。

0070

この制約違反条件は現在成立しているから、これに含まれる変数に対応する現在の変数値の組合せを禁止する条件となるが、禁止する組合せは現在の組合せに限定されず、この制約違反条件を満たす組合せはこれ以降すべて禁止される。

0071

制約違反条件が生成されると、再び変数値変更部104が起動され、該制約違反条件が成立しないように、それに現れる変数の値を変更する。変数変更に失敗すると、再び制約違反条件生成部106が制約違反条件を生成し、制約違反条件格納部103に格納する。一方、変更に成功すると、値が未定の変数が残っているか否かを調べ、あれば、変数値選択部105が該変数値を選択する。値が未定の変数が残っていないならば、解が求まっていることになる。

0072

ここで、一つの解が求まったわけだが、計算機100はこれをユーザに提示する。ユーザがこの解を受け入れずに他の解を求める場合には、現在解禁止不等式追加部203を起動する。そして、不等式系101に新たな不等式として、今求まった解を否定する不等式を入力する。この不等式を、先の解を得るときに入力した初期の不等式系に加えて初期制約違反不等式生成部202に入力して制約違反不等式を生成し、再び、変数値変更部104、変数値選択部105、制約違反条件生成部106を稼働して先の解を求めたときと同様に問題を解く。すなわち、先の解を求めた際の制約違反条件に加えて、先の解を禁止する制約違反条件を加えた問題を解き、別解を求める処理を行なう。

0073

次に、第3図の制約充足条件を生成する原理構成についての動作を説明する。最初に、制約条件定式化部201(図2)を稼働し、ユーザが解きたい組合せ問題についての不等式系301を計算機300に入力する。このとき、変数値として使用したい変数値の集合がある場合には、ID不等式追加部202(図2)を起動し、各変数値についてそのIDで示す特別の属性値に値を設定し、該属性値に関する不等式を計算機300に入力する。この属性値に関する不等式を不等式系301に加えることにより、ある範囲の値(ID)の該属性値をもつ変数値を優先的に使用することが可能になる。優先的に使用する変数値では解が求まれない場合には、上記の制約条件を解除し、その他の変数値も含めた解を求めることになる。

0074

計算機300は、不等式系301の入力を受けて、初期制約充足不等式生成部302を起動し、通常は、該不等式をそのまま初期制約充足不等式として制約充足条件格納部303に格納する。このとき、不等式系301に大小関係を示す純粋な不等式だけではなく等式が含まれる場合、与えられた制約である等式を等価な二つの不等式に変更してから制約充足条件格納部303に格納する。先に不等式系301に付加した好ましい変数値を優先的に使用するための特別の属性値に関する不等式も、他の初期制約条件と同様に初期制約違反不等式生成部302で初期制約違反不等式として制約違反条件格納部303に格納されるので、以下、他の制約違反条件と同様に処理されることになる。

0075

初期制約充足不等式が制約充足条件格納部303に格納されると、次に、変数値変更部304と変数値選択部305が起動される。変数値変更部304は、制約充足条件格納部303に格納されている制約充足条件をすべて満たすように変更する。また、変数値が未定の変数が存在する場合には、変数値選択部305が該変数値を選択する。この場合も、制約充足条件格納部303に格納されている制約充足条件をすべて満たすように選択する。

0076

この変数値変更/選択処理において、ある変数の変数値の変更/選択に失敗する(すなわち、すべての変数値について、それぞれ少なくとも一つの制約充足条件が不成立になる)と、制約充足条件生成部306が起動される。制約充足条件生成部306は、各変数値について成立していない制約充足条件をそれぞれ一つ選び、各々の条件中の当該変数にその変数値を代入して簡略化し、これらすべての論理和を作り、制約充足条件として制約充足条件格納部303に格納する。この制約充足条件には、もはや当該変数は含まれない。

0077

この制約充足条件は現在成立していないから、これに含まれる変数に対応する現在の変数値の組合せを禁止する条件となるが、禁止する組合せは現在の組合せに限定されず、この制約充足条件を満たさない組合せはこれ以降すべて禁止される。

0078

制約充足条件が生成されると、再び変数値変更部304が起動され、該制約充足条件が成立するように、それに現れる変数の値を変更する。変数変更に失敗すると、再び制約充足条件生成部306が制約充足条件を生成し、制約充足条件格納部303に格納する。一方、変更に成功すると、値が未定の変数が残っているか否かを調べ、あれば、変数値選択部305が該変数値を選択する。値が未定の変数が残っていないならば、解が求まっていることになる。

0079

ここで、一つの解が求まったわけだが、計算機300はこれをユーザに提示する。ユーザがこの解を受け入れずに他の解を求める場合には、現在解禁止不等式追加部203を起動する。そして、不等式系301に新たな不等式として、今求まった解を否定する不等式を入力する。この不等式を、先の解を得るときに入力した初期の不等式系に加えて初期制約違反不等式生成部302に入力して制約違反不等式を生成し、再び、変数値変更部304、変数値選択部305、制約違反条件生成部306を稼働して先の解を求めたときと同様に問題を解く。すなわち、先の解を求めた際の制約違反条件に加えて、先の解を禁止する制約違反条件を加えた問題を解き、別解を求める処理を行なう。

0080

一方、第1図、第2図の原理構成において、組合せ制約最適化問題、すなわち、不等式系で与えられた制約を満たし、かつ、与えられた評価関数の値を最小にするように各変数の離散的な値を決定する問題を解く場合には次のように行なう。

0081

評価関数に対応する不等式(以下、これを可変不等式という)を設け、与えられた不等式系に可変不等式を付加した組合せ制約充足問題を第1図または第2図に示す原理構成によって解く。そして、可変不等式の制約値を、
(得られた評価関数値)−ε 〈ここではεは十分小さな正数〉
に更新し、組合せ制約充足問題を解く方式を繰り返し適用することにより、最適値を得る。このとき、変数を含まないさいやく違反条件または制約充足条件が生成されたら処理を停止する。直前に得られた解が最適解である。以前(制約値が現在の値になる前)に生成した制約違反条件または制約充足条件を参照しながら制約充足を行なう。したがって、制約値を更新する前に制約充足に失敗した際の情報によって、無駄な探索を省くことができるのである。

0082

また、評価関数値を最大にするような組合せ制約最適化問題の場合も同様に、評価関数に対応する不等式を可変不等式として付加して組合せ制約充足問題を解くが、このとき、
(得られた評価関数値)+ε 〈ここではεは十分小さな正数〉
に更新し、組合せ制約充足問題を解く方式を繰り返し適用することにより、最適値を得る。

0083

以下、図面を参照しながら本発明の好適実施例につき説明する。第4図は、汎用コンピュータ等の計算機システムで実現される本発明の好適実施例のシステム構成図である。本実施例のシステムは、前述の第一の原理構成を実現するものであり、制約違反条件を生成しながら組合せ制約問題を解く。

0084

計算機400は、CPU401およびI/Oインタフェース402、主記憶403からなる。CPU401は、主記憶403に格納されているソフトウエアに従った処理を実行し、I/Oインタフェース403は、CPU401の命令に従って入出力装置404や外部記憶装置405と計算機400間のやりとりを行なう。

0085

本発明のシステムは主に主記憶403内に格納されるソフトウエアとして実現される。まず、制御部410は、組合せ問題解法の全体の制御を行なう。そして、この制御部410の要求により、制約充足処理部420が組合せ制約充足問題を解く処理を実行する。また、変数値変更部430および変数値選択部440は、制約充足処理部420の要求により変数値を変更/選択する処理を実行する。

0086

また、外部記憶装置405には、生成した制約違反条件を格納する制約違反条件格納部450を設ける。なお、制約違反条件格納部450は、処理の高速性が要求される場合には計算機400内の主記憶403内に設けることが可能である。

0087

まず、本システムを起動すると、制御部410は、ユーザに対して組合せ問題を表現する不等式系を入力するように要求する。ユーザは、これを受けて入出力装置404から不等式系を入力する。このとき、各変数について変数値として好ましい値と好ましくない値がある場合には、好ましい変数値を優先的に使うための特別の属性値についての不等式系も入力する。例えば、各変数の値にIDとして0から始まる整数を割り当て、属性値d0 (x)を変数xの値のIDを表す属性値とし、該属性値d0 (x)に関する制約を追加する。変数xi の値のうち特定の10個を優先的に使いたい場合には、その10個の変数値に0〜9のIDを割り当て、d0 (xi )≦c(ただし、制約値cの初期値は9とする)という制約を追加する。

0088

入力された不等式系は初期制約違反不等式に変換して制約違反条件格納部450に格納される。この後、制御部410は制約充足処理部420を起動し、制約充足処理を実行する。制約充足処理後、解をI/Oインタフェース402を介して入出力装置404に出力する。

0089

変数xi の10個の値では解が構成できない場合には、制約値cの値を大きくして、他の値を使えるようにし、再び制約充足処理部420により制約充足処理を実行する。

0090

次に、制約となる不等式の係数がすべて1の線形不等式の場合についてデータ構造の例を示す。
番号付け
変数番号 :0,1,…,n-agent −1
変数値番号(変数i ):1,2,…,alt i
属性値番号 :0,1,2,3,…
ここで、n-agent は変数の数。alt i については後述する。
◎制約違反不等式テーブル(int dnj DNJ AGENT
DNJ、AGENTは、それぞれ、初期制約違反不等式の数の上限、変数の数の上限を示す。ここで、制約違反条件をNJと呼ぶので、初期制約違反不等式をデフォルトNJ(dnj)と名付けている。

0091

dnj i j は、初期制約違反不等式iが参照する変数jの属性値番号である。論理設計の例では、属性値番号1はゲート数、2以上はコンポーネント内のパスの遅延時間に対応する。該当なし(不等式に当該変数が現れない)は0とする。また、変数値としての好ましさを属性値で表す場合には、属性値番号0を対応する変数のIDとする。
◎制約値テーブル(int constr DNJ )
constr i (0≦i≦n-path) は初期制約違反不等式iに対応する制約値。ここで、n-pathは不等式の総数から1を引いた数。論理設計の例では遅延制約を付加するパスの数になる。
◎データ・テーブル(float des AGENTALTATR
ALT,ATRは、それぞれ、変数値の数の上限、属性値の数の上限を示す。des i j k は、変数iのj+1番目の変数値の属性値番号k+1の値。

0092

属性値番号0には、該変数値のIDを格納する。
◎変数値テーブル(int alt AGENT)
alt i ( 0≦i≦n-agent −1)は、変数iの変数値の総数。
◎inテーブル(int in AGENT )
in i は変数iのinの変数値。0なら、すべての変数値がout であることを示す。ただし、現在、変数の取っている値をinであるといい、変数の値が未定の場合にはすべての変数値がout であるという。
◎out 変数スタック(int out AGENT )
inテーブルのエントリが0となっている(つまりすべての変数値がout である) 変数の番号を格納するスタックである。
◎conjunct
conjunctは制約違反条件の論理積を構成する項であり、次の構造を持つ。

0093

ID=000007HE=035 WI=042 LX=0390 LY=0300
メンバdnj は起源である初期制約違反不等式の番号を示す。メンバtable は変数の情報を示す。table i が0なら、変数iはもともと該当なし(起源である初期制約違反不等式に現れない)か、数値化されてもはや変数ではない。メンバvalue は数値化された部分の合計値を格納する。メンバnextは次のconjunct(もしあれば)へのポインタを格納する。次のconjunctがなければNULLである。
◎制約違反条件テーブル(struct cnj *nj NJ )
NJは制約違反条件の数(初期制約違反不等式は除く)の上限を示す。

0094

第5図は、本発明の好適実施例に係る制約充足システムの処理の流れを示している。この処理は第4図の制御部410のソフトウエアに対応する。まず、入出力装置404から、制約充足問題を解くための初期値をユーザに設定させる(S510)。すなわち、変数の数(n-agent)、不等式の総数から1を引いた数(n-path) を設定し、制約違反不等式テーブル(dnj) を完成する。

0095

次に、データ入力(S550)では、変数値テーブル(alt) およびデータ・テーブル(des) を完成させる。すなわち、変数値の総数とデータ(具体的には、各変数の各変数値の各属性値)を設定する。ここで属性値番号0の属性値としては、各変数値の好ましさを示すために各変数値のIDを格納する。例えば、好ましい変数値に対して小さい値のIDを設定し、好ましくない変数値に対しては大きい値のIDを設定するようにする。また、inテーブルのエントリをすべて1にする。

0096

この後、制約条件をユーザに入力させる(S530)。インタラクティブに各不等式の制約値を入力させ、その結果を制約値テーブル(constr)に書き込む。この制約条件の入力において、好ましい変数値を優先的に使用するようにするための属性値番号0の属性値に関する制限も入力させるようにする。例えば、属性値番号0の属性値(ID)がある値以下というような制約条件を入力すれば、該値以下の属性値(ID)をもつ変数値を以下の実行処理で使うことになる。

0097

以上が組合せ制約充足問題を解く場合にまず行なう初期処理であり、この後、制約充足処理を実行する(S540)。これについては、後述する(第6図)。この処理において、制約充足に成功すれば、結果(inテーブルのエントリ) と各不等式に対応する属性値(論理設計の例では、ゲート数やパス全体の遅延時間)を出力し、制約充足に失敗すれば、最終的な制約違反条件(そのすてのconjunctの左辺が数値になっているもの)を出力する。

0098

この結果を受けて、ユーザに処理を続行するか否かを問う(S550)。続行しない場合(N)には全処理を終了する。また、続行する場合(Y)には、NJ(制約違反条件)のクリアが必要か否かをユーザに判断させる(S560)。必要ない場合(N)には、制約条件入力処理S530に戻る。一方、クリアが必要な場合(Y)にはS540(実行)中に蓄積された制約違反条件をすべてクリアし(S570)、制約条件入力処理S530に戻る。

0099

このとき、制約充足に成功した場合に結果がユーザに提示されるが、ユーザがこの結果を不満足感じて他の解をさらに求めたい場合がある。このような場合には、S530の制約条件入力において、今求まった解を否定する制約条件を入力させるようにする。

0100

すなわち、今求まった解は各変数xi がとる変数値の集合であるから、該変数の変数値の集合を否定する制約条件を作成する。今、解が求まった変数xi のIDをσi とし、各変数値が特別の属性値d0 (xi )=σi をもつとする。この特別の属性値は、先に優先的に使用したい変数値につけた属性値d0 (xi )と同じものである。そこで、今求まった解を否定するための制約条件として、d0(xi )がσi でないすべてのiのORを取る。すなわち、
∨d0 (xi )≠σi (すべてのiについての論理和)
を求め、制約条件として不等式系101に加え、S540以降の処理を再度実行する。

0101

第6図は、第5図S540に示した制約充足処理の処理フローチャートである。まず、成立している制約違反条件があるか否かを判定する(S600)。成立している制約違反条件がある場合(Y)、変数値を変更する処理を実行する(S601)。すなわち、現在注目している制約違反条件のconjunct(制約違反条件の論理積を構成する項)のうち、含む変数の数が最小(正)のものを一つ選び、そこに現れる変数(すなわち、対応するフィールドの値が非)のうち現在の属性値が最も大きいものを選び(iとする)、in i のエントリを他の変数値に変更する。ただし、制約違反条件によって禁止されているものは選ばない。したがって、データ入力S520において、好ましい変数値の属性値番号0に小さい属性値を設定し、制約条件入力S530において、該変数値についてある値よりも小さい該属性値を使用する制約条件を入力した場合には、その条件で禁止されている大きい該属性値の変数値は選ばれない。変数値を変更する際、並行して制約違反条件の合成を進めていき、変更が失敗すると(すなわち、すべての変数値が禁止される場合)、合成してきた制約違反条件を出力する。

0102

上記の変数選択方法は、現在の寄与がもっとも大きいものを選ぶ方法であるが、変数の選択順を固定しておくこともできる。変数値の変更処理において変数値がすべて禁止であったか否かを次に判定する(S602)。すべて禁止であった場合(Y)には、変数値変更処理(S601)で合成した制約違反条件(NJ)の左辺が数値か否かを判定する(S603)。数値でない場合(N)には、合成した制約違反条件を制約違反条件テーブルに登録し、このコピーを作る(以後の処理のため)(S604)。その後、S601の変数値変更処理に戻り、同様の処理を繰り返す。S603においてNJの左辺が数値の場合(Y)、制約充足処理は失敗したことを示すので、合成された制約違反条件(NJ)を出力して(S605)処理を終了する。

0103

S600において成立している制約違反条件がない場合(N)、および、変数値変更処理S601においてすべての変数値変更が禁止であった場合(S602のN)、inテーブルのエントリに0があるか否かを判定する(S606)。すなわち、未定の変数値があるか(0がある)否か(すべて1)を判定する。未定の変数値がない場合(N)、制約充足なのでNULLを返して処理を終了する(S607)。

0104

一方、inテーブルのエントリに0がある場合(Y)には、変数値を選択する処理を実行する(S608)。すなわち、inテーブルのエントリが0である変数(out 変数スタックのトップ) を選び、一つの変数値をinに設定する。ただし、制約違反条件によって禁止されている変数値はinにしない。変数値変更と同様、並行して制約違反条件の合成を進めていく。変数値選択処理後S602に戻り、処理を繰り返す。

0105

制約違反条件の合成では、各変数値について成立している制約違反条件をそれぞれ一つ選び、各々の条件中の当該変数にその変数値の属性値を代入して簡略化する。例えば、
x1 +x2 +10>13
という制約違反条件(NJ)のx2 にその値c21の属性値(例えば2)を代入して、
x1 +12>13
とする。また、これらの論理積を作った後も簡略化する。例えば、
x1 +12>13∧x1 +11>13 (c22の属性値(例えば1)を代入したもの)から、
x1 +11>13
と簡略化する。

0106

第7図は、第6図の変数値変更処理S601(S602を含む)の詳細な処理内容を示している。まず、変数値変更処理では、現在の寄与が最も大きい変数を選ぶ(S701)。なお、変数の選択順を固定にしておいてもよい。変数の選択順が固定の場合には、あらがじめ決められた順番で変数を選択する。

0107

次に、現在注目している制約違反条件に対して選択した変数に対応するフィールドに、その変数の現在の変数値の該当する属性値を書き込む(S702)。インプリメンテーション上は、変数をiとすると、現在注目している制約違反条件についてのtable i が0でない各conjunctについて、table i に0を代入してvalue を変数iの現在の変数値の該当する属性値だけ増やす。

0108

次に、NJの簡略化を行なう(S703)。簡略化は、第6図で説明した
x1 +12>13∧x1 +11>13から
x1 +11>13への処理である。
簡略化処理(S703)の後、試していない変数値があるか否かを判定する(S704)。ない場合には(N)、変数値変更に失敗したものとして呼び出し元へ制御を移す。このときNJを返す(S705)。一方、試していない変数値がある場合(Y)には、変数値設定処理を行なう(S706)。すなわち、試していない変数値を一つ選んで設定する。そして、蓄積されている制約違反条件が成立するか否かをチェックする(S707)。

0109

制約違反条件を満たさない場合(N)は、変数値変更成功であり、NULLを呼び出し元に返す(S708)。一方、制約違反条件を満たす場合(Y)は、その制約違反条件に該当する属性値を書き込んだものと、その時点までに合成した制約違反条件との論理積を作る(S709)。そして、S703のNJ簡略化処理に戻り、以下の処理を繰り返す。

0110

第6図のNJストア(S604)では、変数値変更または変数値選択の結果返された制約違反条件(NJ)を、制約違反条件テーブルに登録し、そのコピーを作ることになる。そのコピーには、直後の変数値変更において、第7図に示す属性値書き込み(S702)の処理により属性値が書き込まれることになる。

0111

以上の処理では、制約違反条件を扱っているが、これとは逆に、制約充足条件の成立/不成立を扱うことにより、同様に処理目的を達成することが可能である。

0112

第8図は、第4図の好適実施例において組合せ制約最適化問題を解く最適化システムの処理フローチャートである。なお、ここでは説明を簡単にするために、データがすべて整数の場合の処理を取り上げる。したがって、評価関数に対応する可変不等式の制約を、得られた評価関数値より小さい(大きい)最大(最小)の整数とすればよいことになる。データがすべて整数でなくても同様に処理することが可能である。

0113

まず、初期設定を行なう(S801)。すなわち、変数の数(n-agent) 、不等式の総数から1引いた数(n-path) を設定し、制約違反不等式テーブル(dnj) を完成する。

0114

次に、データ入力では、変数値テーブル(alt) およびデータ・テーブル(des)を完成する(S802)。すなわち、変数値の総数とデータ(具体的には、各変数の各変数値の属性値)を設定する。ここで属性値番号0の属性値としては、各変数値の好ましさを示すために各変数値のIDを格納する。例えば、好ましい変数値に対して小さい値のIDを設定し、好ましくない変数値に対しては大きい値のIDを設定するようにする。また、inテーブルのエントリをすべて1にする。

0115

次に、評価関数を選択する処理を行なう(S803)。すなわち、0からn-pathまでの制約条件のうちどれを最適化の評価関数にするかを選択し、その(制約値としての)初期値を入力し、制約値テーブル(constr) に書き込む。

0116

そして、組合せ制約の各不等式をインタラクティブに入力する(S804)。すなわち、各不等式(評価関数を除く)の制約値を入力し、その結果を制約値テーブル(constr) に書き込む。このとき、好ましい変数値を優先的に使用するための属性値番号0についての不等式も作成し入力する。

0117

以上の処理の後、制約充足処理を実行する(S805)。実行では、配列in-save(int in-save AGENT) を0に初期化し、制約充足アルゴリズムを実行する。制約充足に成功すると、結果(inテーブルのエントリ) を配列in-save にコピー(上書き)し、評価関数の値を計算し、その値より小さい(大きい)最大(最小)の整数を新しい制約値として制約値テーブル(constr) に書き込み、失敗するまで制約充足処理を繰り返す。最終的に制約充足に失敗すると、結果(配列in-save のエントリ) および各不等式に対応する属性値(論理設計の例では、ゲート数やパス全体のディレイ)を出力する。1回も制約充足に成功しなかった場合は、結果の代わりに、(評価関数の初期制約値に対する)実行可能解がないことを示す最終的な制約違反条件(そのすべてのconjunctの左辺が数値になっているもの) を出力する。

0118

以上の制約充足処理が終了し、制約充足処理の結果が得られると、以上の処理を繰り返すか否かをユーザに問い合わせる(S806)。続行しない場合(N)には処理を終了する。一方、続行する場合(Y)には、制約違反条件(NJ)をクリアする必要があるか否かをユーザに問い合わせる(S807)。そして、必要がある場合(Y)にはNJのクリアを行ない(S808)、必要がない場合(N)にはそのまま、S803の評価関数選択処理に戻り、以下の処理を繰り返す。

0119

このとき、制約充足に成功した場合に結果がユーザに提示されるが、ユーザがこの結果を不満足と感じて他の解をさらに求めたい場合がある。このような場合には、S804の制約条件入力において、今求まった解を否定する制約条件を入力させるようにする。

0120

すなわち、今求まった解は各変数xi がとる変数値の集合であるから、該変数の変数値の集合を否定する制約条件を作成する。今、解が求まった変数xi のIDをσi とし、各変数値が特別の属性値d0 (xi )=σi をもつとする。この特別の属性値は、先に優先的に使用したい変数値につけた属性値d0 (xi )と同じものである。そこで、今求まった解を否定するための制約条件として、d0(xi )がσi でないすべてのiのORを取る。すなわち、
∨d0 (xi )≠σi (すべてのiについての論理和)
を求め、制約条件として不等式系101に加え、S805以降の処理を再度実行する。

0121

次に、切断問題を例題として、本発明の、変数値のうちで優先的に使用する場合の方法と、別解を求める場合の方法を説明する。第9図は、切断問題の説明図である。

0122

問題は次のようなものである。『同図に示すような大きさ2500×1220の板が200 枚あり、これらから6種類の棚を図に示した要求枚数切りだす際(要求枚数より多く切りだして構わない)、使えない無駄な面積を最小にする切り方を選択する。板は50枚ずつ4ロットにし、1つのロットでは皆同じ切り方をするものとする』。

0123

切り方の例を第10図に示す。斜線を施した部分が使えない無駄な部分である。切断機は、同時に切ることができる刃の組を水平方向に1組、垂直方向に2組持っている。切り方は、まず、水平方向に切り、細長い板にする。次に、細長い板を垂直方向に2組の刃のうちどちらかで切って棚を得る。板は多くの切り方が考えられるが、切り方に制限が加えられ、切り方の総数が抑えられている。例えば72通り、あるいは92通りの切り方が考えられる。

0124

この問題では、200 枚の板を4 つのロットに分け、各ロット50枚の板の切り方は同じである。すなわち、72通りあるいは92通りの切り方のなかから4 通りの切り方を選ぶ問題になる。ロットに対応する4つの変数を設け、各棚の枚数が決められた第 9図中に示した各枚数以上になることに対応する6つの不等式と、無駄に対応する評価関数を立てる。すなわち、

0125

0126

ここで、xi は各ロットの切り方に対応する変数。
dk はk番目の棚の枚数に対応する属性値。
bk はk番目の棚の必要枚数。

0127

d7 はそのロットから出る無駄の合計に対応する属性値。
である。これらの不等式および評価関数から制約違反条件を生成し、問題を解くことになる。図11はは制約違反条件の一例である。

0128

ところで、この問題では、例えば72通りあるいは92通りの切り方が考えられているが、それらの切り方のなかでも水平方向および垂直方向の刃位置の設定方法等により、切り出しやすい切り方と切り出しにくい切り方があると考えられる。すなわち、使いたい切り方のパターンと出来るだけ使いたくないパターンがある。

0129

このような場合、本発明の方法により、作成した制約条件に、使いたい変数と使いたくない変数のIDを表す属性値に関する不等式を追加して解く方法が利用できる。すなわち、使いたい切り方のパターンから順に0,1,2,・・・というように整数のID番号をふっておき、該IDを表す属性値をd0 として、次の不等式を制約条件に加える。

0130

d0 (xi ) ≦ c
そして、10通りの切り出しパターンを優先的に使用したい場合には、c=9として問題を解く。この不等式を加えることにより、使いたい特定の10通りの切り方がまず使われることになる。

0131

10通りの切り出しパターンによって問題が解ければこれでこの問題の解法は終了するが、解けない場合には、例えば次に好ましい10通りの切り方パターンを加え、c=19として問題を解く。これにより、先の10通りの最も好ましい切り方パターンに次に好ましい10通りのパターンを加えた20通りの切り出しパターンにより問題を解くことになる。このように、解が得られない場合に順次切りだし方のパターンの制約を緩めながら解法を繰り返すことにより、必要枚数が取れ、さらに無駄が最小限で、出来るかぎり切りだしやすい切り方のパターンが求まる。

0132

このように、組合せ問題に出てくる変数に対して、変数のIDを表す属性値d0 (xi )を導入することにより、優先的に使用したい変数値の集合を設定することが可能になる。

0133

一方、従来の方法で組合せ問題を解くと、一応解が求まる。しかし、その解以外の別解が欲しい場合がある。例えば、上記の棚の切りだし問題において、切り方のパターンのIDが2,7,15,19の4通りのパターンで切りだせばよいという解が一応出たとする。しかし、これ以外の解も欲しいとする。

0134

このような場合には、今までの制約条件に、ID番号が2,7,15,19の切り方パターンの組を使用しないで解くための制約条件を追加する。すなわち、解として求まった上記の切り方パターンのIDを示す属性値d0 (xi )をσiとしたとき、d0 (xi )がσi に等しくないという式について、すべてのi、ここでは4通りのロットについてORを取り制約条件を得る。すなわち、d0 (xi )≠2∨d0 (xi )≠7∨d0 (xi )≠15∨d0 (xi )≠19という制約条件を追加して、再び問題を解いてやることにより、これ以外の解が求まることになる。

0135

このように、組合せ問題に出てくる変数に対して、変数のIDを表す属性値d0 (xi )を導入することにより、一旦求まった解以外の別解を求めることが可能になる。

発明の効果

0136

以上のように、本発明によれば、変数のIDを表す属性値d0 (xi )を導入し、該属性値d0 (xi )についてd0 (xi )≦c(cは使用する変数値のIDの上限)という制約条件を加えて問題を解くことにより、優先的に使いたい一部の変数値の集合から解を得ることが可能になる。また、同様に変数のIDを表す属性値d0 (xi )を導入し、該属性値d0 (xi )について、一旦求まった解のIDを除外するような制約条件を付加して再び問題を解くことにより、別解を求めることが可能になる。

図面の簡単な説明

0137

図1本発明の原理構成図(その1)、
図2不等式系の詳細原理構成図、
図3本発明の原理構成図(その2)、
図4一実施例のシステム構成図(原理構成図(その1)の場合)、
図5制約充足システムの処理フローチャート、
図6制約充足処理説明図、
図7変数値変更処理説明図、
図8最適化システムの処理フローチャート、
図9切断問題に適用した場合の説明図(その1)、
図10切断問題に適用した場合の説明図(その2:切り方の一例)、
図11切断問題に適用した場合の説明図(その3:制約違反条件の一例)、
図12関連発明の作用説明図。

--

0138

100,300計算機
101,301不等式系
102初期制約違反不等式生成部
103制約違反条件格納部
104,304変数値変更部
105,305 変数値選択部
106 制約違反条件生成部
302 初期制約充足不等式生成部
303制約充足条件格納部
106 制約充足条件生成部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ