特許

J-GLOBAL ID：200903089077377928

組合せ問題処理装置

発明者： 丸山 文宏 ,  箕田 依子 ,  澤田 秀穂 ,  滝沢 ユカ ,  吉田 裕之
出願人/特許権者： 富士通株式会社
代理人 (1件)： 大菅 義之 (外1名)
公報種別：公開公報
出願番号（国際出願番号）：特願平3-297496
公開番号（公開出願番号）：特開平5-028126
出願日： 1991年11月13日
公開日（公表日）： 1993年02月05日
要約：

【要約】 (修正有)【目的】 変数が離散的な値をとる組合せ制約充足および最適化問題を、処理の途中に得られた失敗情報を最大限に利用して効率的に解決する手段を提供する。【構成】 計算機100内に、外部から指示される制約である不等式系(不等式や等式)101と相反する制約違反不等式を生成する初期制約違反不等式生成部102と、制約充足を調べる変数の値を現在の値から他の値に変更する変数値変更部104、および、値が未定の変数の値を選択する変数値選択部105と、変数値変更部104および変数値選択部105の処理ですべての値が制約を満たさない場合に、制約違反不等式またはこれから生成された制約違反条件のなかに現れる変数を数値化することにより、簡略化した不等式の論理積の新しい制約違反条件を生成する制約違反条件生成部106を有し、そこで生成した制約違反条件を蓄積する制約違反条件格納部103で構成する。

請求項（抜粋）：

不等式や等式で与えられた制約を満たすように、各変数の離散的な値を決定する組合せ制約充足問題、あるいは、不等式や等式で与えられた制約を満たし、かつ、与えられた評価関数の値を最小あるいは最大にするように各変数の離散的な値を計算機により決定する組合せ最適化問題を解く組合せ問題処理装置であって、前記計算機内に、外部から指示される制約である不等式系(不等式や等式)と相反する制約違反不等式を生成する初期制約違反不等式生成部を含む、ことを特徴とする組合せ問題処理装置。

IPC (2件)：

G06F 15/20 ,  G06F 15/36