JP7841586B2 - 情報処理装置、制御方法及びプログラム - Google Patents

Description

本開示は、最適化問題に関する処理を行う情報処理装置、制御方法及び記憶媒体の技術分野に関する。

従来から、最適化問題における解を算出するシステムが知られている。例えば、特許文献１には、業者と顧客との双方の希望取引条件が同時に満足するように、組み合わせ候補を複数作成する電子取引仲介システムが開示されている。また、特許文献２には、取引対象となる物資の売手と買手とがそれぞれ希望する取引量及び取引価格などの取引条件が合致するように組み合わせを決定（マッチング）した後、一部の取引条件を変更して再マッチングを行うことが可能な最適化システムが開示されている。

国際公開ＷＯ２００２／０２７５７５ 国際公開ＷＯ２０２１／００１９７７

最適化問題の解を最適化により得る場合、定式化された制約条件を満たす解が得られる。一方、制約条件が厳密に守られない解であってもユーザが許容できる場合が存在する。

本開示の目的の一つは、上述した課題を鑑み、制約条件の緩和を考慮した情報を好適に提示することが可能な情報処理装置、制御方法及び記憶媒体を提供することである。

情報処理装置の一の態様は、
目的関数値を最小化又は最大化する解を求める最適化問題の条件に関する条件情報と、前記最適化問題の制約条件の緩和に関する制約緩和情報と、に基づき、前記最適化問題の複数の解を、前記緩和の度合いに応じて設定される複数の罰則値ごとに決定する解決定手段と、
前記罰則値と、当該罰則値に応じた前記緩和を行った場合に得られる前記解の目的関数値との関係を示す関係情報を、表示装置に表示する表示制御手段と、
を有する情報処理装置である。

制御方法の一の態様は、
コンピュータが、
目的関数値を最小化又は最大化する解を求める最適化問題の条件に関する条件情報と、前記最適化問題の制約条件の緩和に関する制約緩和情報と、に基づき、前記最適化問題の複数の解を、前記緩和の度合いに応じて設定される複数の罰則値ごとに決定し、
前記罰則値と、当該罰則値に応じた前記緩和を行った場合に得られる前記解の目的関数値との関係を示す関係情報を、表示装置に表示する、
制御方法である。

プログラムの一の態様は、
目的関数値を最小化又は最大化する解を求める最適化問題の条件に関する条件情報と、前記最適化問題の制約条件の緩和に関する制約緩和情報と、に基づき、前記最適化問題の複数の解を、前記緩和の度合いに応じて設定される複数の罰則値ごとに決定し、
前記罰則値と、当該罰則値に応じた前記緩和を行った場合に得られる前記解の目的関数値との関係を示す関係情報を、表示装置に表示する処理をコンピュータに実行させるプログラムである。

制約条件の緩和を考慮した情報を好適に提示することができる。

第１実施形態における最適化システムの構成を示す。 情報処理装置のハードウェア構成を示す。 最適化処理に関するプロセッサの機能ブロックの一例である。 第１実施形態における最適化処理の概要を示すフローチャートの一例である。 制約緩和指定画面の第１表示例である。 （Ａ）制約緩和指定画面の第２表示例である。（Ｂ）制約緩和指定画面の第３表示例である。 変数ｘと、制約条件（ａ）に対する罰則値との関係を示すグラフである。 罰則値・目的関数値関係画面の表示例を示す。 制約緩和状況比較画面の表示例を示す。 第２実施形態における最適化システムの構成を示す。 第３実施形態における情報処理装置の機能ブロック図である。 第３実施形態における情報処理装置の処理手順を示すフローチャートの一例である。

以下、図面を参照しながら、情報処理装置、制御方法及び記憶媒体の実施形態について説明する。

＜第１実施形態＞
（１）システム構成
図１は、第１実施形態に係る最適化システム１００の構成を示す。最適化システム１００は、主に、情報処理装置１と、入力装置２と、表示装置３と、記憶装置４とを備える。

情報処理装置１は、指定された最適化問題における最適化に関する処理である最適化処理を行う。最適化処理には、最適化問題の制約条件の緩和に関する指定を受け付ける処理、及び、制約条件の緩和の度合いに応じた最適化問題の解に関する情報を表示する処理などが含まれている。なお、最適化問題は、例えば、取引対象となる物資の売手と買手の組み合わせ（及び当該物資の輸送スケジュール）を決定する問題であってもよく、従業員の勤務シフトを決定する問題であってもよく、その他の任意の組み合わせ最適化問題であってもよい。上述の取引対象となる物資は、ＬＮＧなどの燃料、鉄鋼、機械、エレクトロニクス、繊維、化学製品、医療関連商品、食品、その他の任意の物であってもよい。

また、情報処理装置１は、通信網を介し、又は、無線若しくは有線による直接通信により、入力装置２と、表示装置３と、記憶装置４とデータ通信を行う。

入力装置２は、ユーザの入力を受け付けるインターフェースであり、例えば、タッチパネル、ボタン、音声入力装置などが該当する。入力装置２は、ユーザの入力に基づき生成した入力情報「Ｓ１」を情報処理装置１へ供給する。この場合、例えば、情報処理装置１は、入力装置２から供給される入力情報Ｓ１に基づき、記憶装置４に記憶する各種情報を生成したり、最適化処理に関してユーザが指定する条件等を特定したりする。

表示装置３は、例えば、ディスプレイ、プロジェクタ等であり、情報処理装置１から供給される表示情報「Ｓ２」に基づき、所定の表示を行う。

記憶装置４は、最適化処理に必要な各種情報を記憶するメモリである。例えば、記憶装置４は、情報処理装置１が解くべき最適化問題の条件を示す条件情報を記憶している。条件情報は、緩和される前の制約条件に関する情報を含んでいる。例えば、取引対象となる物資の売手と買手の組み合わせを決定する問題が情報処理装置１が解くべき最適化問題として設定されている場合には、条件情報は、取引対象の物資の売手の情報（受渡場所、受渡期間、取引量、及び価格等に関する各売手の希望条件を含む）、取引対象の物資の買手の情報（受渡場所、受渡期間、取引量、及び価格等に関する各買手の希望条件を含む）などを含む。

なお、記憶装置４は、情報処理装置１に接続又は内蔵されたハードディスクなどの外部記憶装置であってもよく、フラッシュメモリなどの記憶媒体であってもよい。また、記憶装置４は、情報処理装置１とデータ通信を行うサーバ装置であってもよい。この場合、記憶装置４は、複数のサーバ装置から構成されてもよい。

なお、図１に示す最適化システム１００の構成は一例であり、当該構成に種々の変更が行われてもよい。例えば、入力装置２及び表示装置３は、一体となって構成されてもよい。この場合、入力装置２及び表示装置３は、情報処理装置１と一体となるタブレット型端末として構成されてもよい。また、情報処理装置１は、複数の装置から構成されてもよい。この場合、情報処理装置１を構成する複数の装置は、予め割り当てられた処理を実行するために必要な情報の授受を、これらの複数の装置間において行う。

（２）情報処理装置のハードウェア構成
図２は、情報処理装置１のハードウェア構成を示す。情報処理装置１は、ハードウェアとして、プロセッサ１１と、メモリ１２と、インターフェース１３とを含む。プロセッサ１１、メモリ１２及びインターフェース１３は、データバス１９を介して接続されている。

プロセッサ１１は、メモリ１２に記憶されているプログラムを実行することにより、所定の処理を実行する。プロセッサ１１は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＴＰＵ（Ｔｅｎｓｏｒ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）などのプロセッサである。プロセッサ１１は、複数のプロセッサから構成されてもよい。プロセッサ１１は、コンピュータの一例である。

メモリ１２は、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）などの各種の揮発性メモリ及び不揮発性メモリにより構成される。また、メモリ１２には、情報処理装置１が各種の処理を実行するためのプログラムが記憶される。また、メモリ１２は、作業メモリとして使用され、記憶装置４から取得した情報等を一時的に記憶する。なお、メモリ１２は、記憶装置４として機能してもよい。同様に、記憶装置４は、情報処理装置１のメモリ１２として機能してもよい。なお、情報処理装置１が実行するプログラムは、メモリ１２以外の記憶媒体に記憶されてもよい。

インターフェース１３は、情報処理装置１と他の装置とを電気的に接続するためのインターフェースである。これらのインターフェースは、他の装置とデータの送受信を無線により行うためのネットワークアダプタなどのワイアレスインターフェースであってもよく、他の装置とケーブル等により接続するためのハードウェアインターフェースであってもよい。

なお、情報処理装置１のハードウェア構成は、図２に示す構成に限定されない。例えば、情報処理装置１は、入力装置２又は表示装置３の少なくとも一方を含んでもよい。また、情報処理装置１は、スピーカなどの音出力装置と接続又は内蔵してもよい。

（３）最適化処理の概要
図３は、最適化処理に関するプロセッサ１１の機能ブロックの一例である。プロセッサ１１は、機能的には、解決定部１５と、ＵＩ（Ｕｓｅｒ Ｉｎｔｅｒｆａｃｅ）制御部１６とを有する。また、なお、図３では、データの授受が行われるブロック同士を実線により結んでいるが、データの授受が行われるブロックの組み合わせは図３に限定されない。後述する他の機能ブロックの図においても同様である。

解決定部１５は、最適化問題の解を決定する。この場合、解決定部１５は、記憶装置４に記憶された最適化問題の条件情報及びＵＩ制御部１６の制約緩和指定部１６１から供給される情報に基づき、最適化問題の解を決定する。この場合、後述するように、制約緩和指定部１６１から供給される情報には、緩和が許容される制約条件の種類、緩和が許容される範囲、及び緩和された場合の罰則の重みを指定する情報が含まれている。よって、解決定部１５は、ユーザにより指定された範囲内において制約条件の緩和を許容し、その緩和度合いに応じた複数個の最適化の解を算出する。解決定部１５は、制約条件の緩和度合いに応じて算出した解を示すデータ（「解データ」とも呼ぶ。）を、ＵＩ制御部１６へ供給する。

なお、解決定部１５は、任意の最適化方法（最適化ソルバー）に基づき、最適化問題の解を決定してもよい。例えば、解決定部１５は、取引対象となる物資の売手と買手の組み合わせを決定する問題を解く場合、この問題を１つの組み合わせ最適化問題とみなして整数計画問題に定式化する。そして、解決定部１５は、定式化した整数計画問題を、一般的なアプリケーションプログラム（例えば、ＩＢＭ ＩＬＯＧ ＣＰＬＥＸ、Ｇｕｒｏｂｉ Ｏｐｔｉｍｉｚｅｒ、ＳＣＩＰ）と同等の処理を行うことで解を求める。なお、整数計画問題に定式化して売手、買手、使用する船舶、及び当該船舶の航行期間を決定する方法については、例えば、特許文献２などに開示されている。

ＵＩ制御部１６は、ユーザ入力の受け付け及びユーザに閲覧させる情報の表示に関する制御を行う。この場合、ＵＩ制御部１６は、入力装置２から供給される入力情報Ｓ１に基づき、制約条件の緩和に関するユーザの指定を受け付けたり、解決定部１５が生成する解データに基づき生成した表示情報Ｓ２を表示装置３に供給することで表示装置３の表示制御を行ったりする。

また、ＵＩ制御部１６は、機能的には、制約緩和指定部１６１と、第１表示制御部１６２と、第２表示制御部１６３とを含んでいる。

制約緩和指定部１６１は、制約条件の緩和に関するユーザの指定を受け付ける。本実施形態では、制約緩和指定部１６１は、緩和が許容される制約条件の種類、許容される緩和の範囲（「緩和範囲」とも呼ぶ。）、及び制約条件が緩和された場合の罰則の重み（「罰則重み」とも呼ぶ。）を指定するユーザ入力を受け付ける。ここで、「罰則重み」は、制約条件を緩和した場合の罰則（ペナルティ）の度合いを指し、制約条件の緩和度合いを総合的に表す指標値である罰則値の算出に用いられる係数である。そして、制約緩和指定部１６１は、ユーザ入力に基づき指定された、制約条件の緩和に関する情報（「制約緩和情報」とも呼ぶ。）を、解決定部１５に供給する。その後、解決定部１５は、記憶装置４に記憶された条件情報及び制約緩和指定部１６１が生成した制約緩和情報に基づき、罰則値に応じた最適化を複数回実行し、罰則値に応じた複数の解を決定する。罰則値の決定方法等については後述する。

第１表示制御部１６２は、罰則値に応じた解を示す解データを解決定部１５から取得し、当該解データに基づき、罰則値と、最適化において最大化又は最小化すべき目的関数の値（「目的関数値」とも呼ぶ。）との関係を示す情報を表示装置３に表示させる。以後では、罰則値と目的関数値との関係を示す情報（関係情報）を表示する画面を「罰則値・目的関数値関係画面」とも呼ぶ。罰則値・目的関数値関係画面の表示例については後述する。

第２表示制御部１６３は、罰則値・目的関数値関係画面において罰則値と目的関数値との組の任意の２組がユーザ入力に基づき指定された場合に、指定された２組に対応する解における制約条件の緩和状況を比較する情報を表示装置３に表示させる。以後では、指定された２組に対応する解における制約条件の緩和状況を比較表示する画面を「制約緩和状況比較画面」とも呼ぶ。制約緩和状況比較画面の表示例については後述する。

なお、図３において説明した解決定部１５、制約緩和指定部１６１、第１表示制御部１６２、及び第２表示制御部１６３の各構成要素は、例えば、プロセッサ１１がプログラムを実行することによって実現できる。また、必要なプログラムを任意の不揮発性記憶媒体に記録しておき、必要に応じてインストールすることで、各構成要素を実現するようにしてもよい。なお、これらの各構成要素の少なくとも一部は、プログラムによるソフトウェアで実現することに限ることなく、ハードウェア、ファームウェア、及びソフトウェアのうちのいずれかの組み合わせ等により実現してもよい。また、これらの各構成要素の少なくとも一部は、例えばＦＰＧＡ（Ｆｉｅｌｄ－Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）又はマイクロコントローラ等の、ユーザがプログラミング可能な集積回路を用いて実現してもよい。この場合、この集積回路を用いて、上記の各構成要素から構成されるプログラムを実現してもよい。また、各構成要素の少なくとも一部は、ＡＳＳＰ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｓｔａｎｄａｒｄ Ｐｒｏｄｕｃｅ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）又は量子プロセッサ（量子コンピュータ制御チップ）により構成されてもよい。このように、各構成要素は、種々のハードウェアにより実現されてもよい。以上のことは、後述する他の実施の形態においても同様である。さらに、これらの各構成要素は，例えば，クラウドコンピューティング技術などを用いて、複数のコンピュータの協働によって実現されてもよい。

図４は、第１実施形態における最適化処理の概要を示すフローチャートの一例である。

まず、情報処理装置１は、最適化の対象となる最適化問題に関する条件情報を記憶装置４等から取得する（ステップＳ１１）。次に、情報処理装置１は、緩和する制約の種類、緩和範囲、及び罰則重みを指定する入力を受け付ける（ステップＳ１２）。

そして、情報処理装置１は、ステップＳ１２で受け付けた入力により生成された制約緩和情報に基づき、制約緩和の度合いである罰則値を変えて最適化を複数回実行する（ステップＳ１３）。この場合、情報処理装置１は、例えば、予め定めた複数の罰則値の夫々を対象とする最適化を行うことで、当該複数の罰則値の夫々に対する最適化の解を生成する。

次に、情報処理装置１は、ステップＳ１３で生成した解データに基づき、罰則値と目的関数値との関係を可視化した罰則値・目的関数値関係画面を表示装置３に表示させる（ステップＳ１４）。そして、情報処理装置１は、罰則値・目的関数値関係画面に表示した罰則値と目的関数値との組から任意の２組が指定されたか否か判定する（ステップＳ１５）。そして、情報処理装置１は、任意の２組が指定されたと判定した場合（ステップＳ１５；Ｙｅｓ）、指定された２組に対応する解の制約条件の緩和状況を比較した制約緩和状況比較画面を表示装置３に表示させる（ステップＳ１６）。

一方、情報処理装置１は、任意の２組が指定されていないと判定した場合（ステップＳ１５；Ｎｏ）、罰則値・目的関数値関係画面に表示した罰則値と目的関数値との組から任意の１組が指定されたか否か判定する（ステップＳ１７）。そして、情報処理装置１は、任意の１組が指定されたと判定した場合（ステップＳ１７；Ｙｅｓ）、指定された組に対応する解と、当該解における制約条件の緩和状況とを表示装置３に表示させる（ステップＳ１８）。一方、情報処理装置１は、罰則値・目的関数値関係画面に表示した罰則値と目的関数値との組がいずれも指定されていないと判定した場合（ステップＳ１７；Ｎｏ）、フローチャートの処理を終了する。

ここで、制約条件の緩和の効果について補足説明する。例えば、取引における意思決定者が本システムを用いる場合、意思決定の途中で意思決定者が罰則値・目的関数値関係画面及び制約緩和状況比較画面等を参照して制約条件を緩和した場合の状況を把握することで、取引相手に影響を与えるための交渉等の材料を得ることができる。他の例では、制約条件の緩和を行わずに単一の最適化を行う場合と比較して目的関数値の向上に繋げることができる。さらに別の例では、解決定部１５による最適化において許容解が見つからない（実行不能）場合において、制約条件の緩和を選択肢に含めることで許容解が得られるようになる。

（４）制約緩和情報の生成
次に、制約緩和指定部１６１が実行する制約緩和情報の生成方法の具体例について説明する。

図５は、制約緩和を指定する入力画面（「制約緩和指定画面」とも呼ぶ。）の第１表示例である。第１表示例は、緩和する候補となる制約条件が期間などの連続的な範囲により指定される場合の表示例を示す。

制約緩和指定部１６１は、制約緩和指定画面を表示するための表示情報Ｓ２を条件情報に基づき生成し、生成した表示情報Ｓ２を表示装置３にインターフェース１３を介して送信することで、表示装置３に制約緩和指定画面を表示させる。なお、例えば、記憶装置４に記憶される条件情報には、制約条件の種類ごとに、制約名と、罰則重みの初期値と、緩和前の制約内容（制約の範囲）を示す初期範囲と、を関連付けた情報が含まれており、制約緩和指定部１６１は、この条件情報を参照することで、制約緩和指定画面の表示情報Ｓ２を生成する。

第１表示例に係る制約緩和指定画面は、「制約名」、「罰則重み」、「緩和範囲」の各項目に対応する表示フィールドを含んでいる。項目「制約名」は、条件を緩和する候補となる制約条件（言い換えると、緩和可能な制約条件）の名前を示す。ここでは、「取引先Ａの受渡期間」及び「取引先Ｂの受渡期間」が項目「制約名」の表示フィールドに列挙されている。

項目「罰則重み」は、項目「制約名」の表示フィールドに表示された制約名の制約条件に対して設定する罰則重みを示し、項目「罰則重み」の表示フィールドには、重み指定欄３１、３２が設けられている。重み指定欄３１、３２は、入力装置２によりユーザが任意の罰則重みの数値を指定可能な入力欄である。なお、重み指定欄３１、３２には罰則重みの初期値が予め表示されていてもよい。

項目「緩和範囲」は、項目「制約名」の表示フィールドに表示された制約名の制約条件に対して許容する制約条件の緩和状況を示し、項目「緩和範囲」の表示フィールドには、グラフ４１、４２が表示されている。グラフ４１、４２は、夫々、条件情報が示す制約条件の初期範囲を示している。さらにグラフ４２は、初期範囲に加えて、ユーザ入力により指定された制約条件の緩和範囲を示している。例えば、制約緩和指定部１６１は、初期範囲の右端又は左端を許容可能な日付に対応する位置までドラッグアンドドロップする操作を検知すること等により、緩和範囲の指定を受け付ける。例えば、グラフ４２の場合、制約緩和指定部１６１は、初期範囲の右端を５月２１日の位置までドラッグアンドドロップする操作を検知したことにより、初期範囲の終点（４月２７日）を始点とし５月２１日を終点とする緩和範囲を設定している。

図６（Ａ）は、制約緩和指定画面の第２表示例である。第２表示例は、緩和する候補となる制約条件が離散的な数値により指定される場合の表示例である。

第２表示例では、項目「制約名」の表示フィールドに「取引先Ａの約定回数の下限」が表示されている。そして、項目「罰則重み」の表示フィールドには、制約条件「取引先Ａの約定回数の下限」に対して設定する罰則重みの入力欄である重み指定欄３３が設けられている。さらに、項目「緩和範囲」の表示フィールドには、上述の制約条件に対する緩和範囲を指定するための入力欄である緩和範囲指定欄４３が設けられている。

緩和範囲指定欄４３は、一例としてプルダウンメニュー形式の入力欄となっており、取引先Ａの約定回数の下限として設定可能な値（離散値）を夫々選択可能に表示している。また、制約条件「取引先Ａの約定回数の下限」の初期値は「３」となっており、当該初期値よりも緩い制約となる値「０」、「１」、「２」の各メニューが緩和範囲指定欄４３において強調表示されている。例えば、緩和範囲指定欄４３において「１」が選択された場合、取引先Ａの約定回数が１回及び２回となる場合が新たに許容されることとなり、取引先Ａの約定回数が１回及び２回となる範囲が緩和範囲に相当する。

図６（Ｂ）は、制約緩和指定画面の第３表示例である。第３表示例は、緩和する候補となる制約条件が除外可能か否かが指定される場合の表示例である。

第３表示例では、項目「制約名」の表示フィールドに「スタッフＸは夜勤連続可」、「スタッフＹは夜勤連続可」が列挙されている。そして、項目「罰則重み」の表示フィールドには、これらの制約条件に対して設定する罰則重みの入力欄である重み指定欄３４、３５が設けられている。さらに、項目「緩和可否」の表示フィールドには、上述の各制約条件に対する緩和（ここでは除外）の可否を指定するための入力欄であるチェックボックス４４、４５が夫々設けられている。図６（Ｂ）の例では、チェックボックス４４にチェックが入っていることから、制約条件「スタッフＸは夜勤連続可」は緩和により除外することが可能である旨が指定されている。

このように、制約緩和指定部１６１は、緩和を許容する制約条件の候補として種々の制約条件を表示し、緩和を許容する制約条件としてユーザが指定した制約条件に関する罰則重み及び緩和範囲の指定を受け付けることができる。

（５）罰則重みに基づく罰則値の算出
次に、罰則重みに基づく罰則値の算出方法について、具体例を用いて補足説明する。

ここでは、最適化問題において解として求めるべき変数を「ｘ」（連続値）、「ｙ」（整数値）、「ｚ」（０又は１の２値）とし、以下の制約条件（ａ）～（ｃ）が条件情報に含まれているものとする。
（ａ）４≦ｘ≦１０
（ｂ）３≦ｙ≦５
（ｃ）ｚ＝０

また、目的関数は、以下のように、ｘ、ｙ、ｚの総和（ｘ＋ｙ＋ｚ）に設定され、目的関数値が最大化又は最小化（ここでは最大化とする）されるように最適化の解（ｘ、ｙ、ｚ）の決定が行われるものとする。
ｍａｘ（ｘ＋ｙ＋ｚ）

そして、制約緩和指定画面でのユーザ入力に基づき、制約条件（ａ）～（ｃ）は、以下の条件（ａ１）～（ｃ１）に夫々緩和されたものとする。
（ａ１）１≦ｘ≦１３
（ｂ１）２≦ｙ≦７
（ｃ１）ｚ＝０又は１

また、制約緩和指定画面でのユーザ入力に基づき、制約条件（ａ）～（ｃ）に対する罰則重み「ｐａ」、「ｐｂ」、「ｐｃ」が夫々設定されたものとする。
ｐａ＝４
ｐｂ＝２
ｐｃ＝１０

この場合、罰則重みｐａ～ｐｃは、罰則値の決定に用いられる係数であり、例えば、求めた解が元の制約条件（ａ）～（ｃ）から外れた度合い（外れ度合い）に乗じられる。そして、制約条件ごとの罰則重みと外れ度合いの乗算値の合計値が罰則値として算出される。

図７は、変数ｘと、制約条件（ａ）に対する罰則値との関係を示すグラフである。図７に示すように、制約条件（ａ）に対する罰則値は、制約条件（ａ）が満たされる限り０となる。一方、制約条件（ａ）を満たさず、かつ、条件（ａ１）を満たす範囲（即ち緩和範囲）にある場合には、制約条件（ａ）から離れるほど（即ち外れ度合いが大きくなるほど）罰則重みｐａに応じて罰則値が大きくなる。

例えば、解が（ｘ、ｙ、ｚ）＝（８、４、０）の場合、罰則値が０となる。一方、解が（ｘ、ｙ、ｚ）＝（１３、２、１）の場合、罰則値は、
（１３－１０）・ｐａ＋（３－２）・ｐｂ＋（１－０）・ｐｃ＝２４
となる。なお、（ｘ、ｙ、ｚ）＝（１５、５、０）は、制約条件（ａ）及びその緩和後の条件（ａ１）のいずれも満たされない（即ち初期範囲及び緩和範囲のいずれにも属しない）ため、解の候補から除外される。

（６）罰則値・目的関数値関係画面
次に、第１表示制御部１６２が表示する罰則値・目的関数値関係画面について具体的に説明する。図８は、罰則値・目的関数値関係画面の表示例を示す。第１表示制御部１６２は、罰則値・目的関数値関係画面を表示するための表示情報Ｓ２を表示装置３にインターフェース１３を介して送信することで、罰則値・目的関数値関係画面を表示装置３に表示させる。

ここで、第１表示制御部１６２は、罰則値・目的関数値関係画面上に、罰則値毎の目的関数値を示す複数のレコードを有するテーブルである罰則値－目的関数値テーブル５１と、罰則値と目的関数値との関係を示すグラフである罰則値－目的関数値グラフ５２と、個別表示ボタン５４と、比較表示ボタン５５と、を表示している。

この例では、解決定部１５は、制約緩和指定部１６１が生成した制約緩和情報及び条件情報に基づき、「０」、「１０」、「２０」、「２５」、「３０」を夫々罰則値とした場合に目的関数値が最大となる解を夫々算出する。そして、第１表示制御部１６２は、罰則値「０」、「１０」、「２０」、「２５」、「３０」と、これらの罰則値の夫々に対応する解の目的関数値（１００、１０５、１１０、１１５、１２０）と、を対応付けた罰則値－目的関数値テーブル５１を表示する。同様に、解決定部１５は、罰則値「０」、「１０」、「２０」、「２５」、「３０」と、これらの解に対応する目的関数値との関係を示す罰則値－目的関数値グラフ５２を表示する。なお、罰則値－目的関数値グラフ５２には、罰則値－目的関数値テーブル５１の各レコードに対応する対応点５３ａ～５３ｅが明示されている。罰則値と目的関数値とは、一方が好ましくない値に変化するほど他方が好ましい値に変化するというトレードオフの関係となっている。

この表示によれば、第１表示制御部１６２は、目的関数値と罰則値との関係を好適に可視化し、目的関数値と罰則値との関係をユーザに的確に把握させることができる。

また、罰則値－目的関数値テーブル５１の各レコードは、ユーザ入力に基づき選択可能となっている。そして、第１表示制御部１６２は、罰則値－目的関数値テーブル５１のいずれか１つのレコードが選択された状態で個別表示ボタン５４が選択されたことを検知した場合、図４のステップＳ１８に従い、選択されたレコードに対応する罰則値での解と制約緩和状況とを表示する画面を、表示装置３に表示させる。一方、第１表示制御部１６２は、罰則値－目的関数値テーブル５１の任意の２つ（３つ以上であってもよい）のレコードが選択された状態で比較表示ボタン５５が選択されたことを検知した場合、図４のステップＳ１６に従い、選択されたレコードに対応する制約緩和状況の比較表示に関する制約緩和状況比較画面を、表示装置３に表示させる。

（７）制約緩和状況比較画面
次に、第２表示制御部１６３が表示する制約緩和状況比較画面について具体的に説明する。図９は、制約緩和状況比較画面の表示例を示す。第２表示制御部１６３は、制約緩和状況比較画面を表示するための表示情報Ｓ２を表示装置３にインターフェース１３を介して送信することで、表示装置３に制約緩和状況比較画面を表示させる。

第２表示制御部１６３は、罰則値・目的関数値関係画面において指定された２つの解（ここでは罰則値１０に対する解と、罰則値２０に対する解）において、緩和された制約条件を特定する。そして、第２表示制御部１６３は、緩和された制約条件の各々について、２つの解に対応する罰則重み及び制約条件の緩和状況を、制約緩和状況比較画面上に、比較可能に表示する。例えば、制約条件「取引先Ｂの受渡期間」については、罰則重みが１００に設定されたことが罰則重み表示欄３６において示されており、かつ、グラフ４６において、各解での緩和状況が初期範囲と共に色分けして表示されている。ここでは、罰則値１０に対する解では、制約条件「取引先Ｂの受渡期間」の終点が５月２１日まで延長（緩和）されており、罰則値２０に対する解では、制約条件「取引先Ｂの受渡期間」の終点が６月１７日まで延長（緩和）されている。

同様に、制約条件「取引先Ａの約定回数の下限」については、罰則重みが１０に設定されたことが罰則重み表示欄３７において示されており、かつ、グラフ４７において、各解での緩和状況が初期範囲と共に色分けして表示されている。ここでは、罰則値１０に対する解では、取引先Ａの約定回数の下限が「２」まで引き下げられて（緩和されて）おり、罰則値２０に対する解では、取引先Ａの約定回数の下限が「０」まで引き下げられて（緩和されて）いる。なお、除外可能か否かが指定された制約条件（図６（Ｂ）参照）についても同様に、第２表示制御部１６３は、制約条件の除外の有無を解ごとに対応付けた情報を制約緩和状況比較画面上に表示するとよい。

＜第２実施形態＞
図１０は、第２実施形態における最適化システム１００Ａの構成を示す。図１０に示すように、最適化システム１００Ａは、主に、情報処理装置１Ａと、記憶装置４と、端末装置５とを有する。情報処理装置１Ａと端末装置５とは、ネットワーク６を介してデータ通信を行う。

情報処理装置１Ａは、第１実施形態に係る情報処理装置１と同一構成を有し、情報処理装置１と同じ最適化処理を実行する。この場合、情報処理装置１Ａは、第１実施形態において情報処理装置１が入力装置２から受信する入力情報Ｓ１を、ネットワーク６を介して端末装置５から受信する。また、情報処理装置１Ａは、第１実施形態において情報処理装置１が表示装置３に送信した表示情報Ｓ２を、ネットワーク６を介して端末装置５へ送信する。このように、第２実施形態に係る情報処理装置１Ａは、サーバ装置として機能する。

端末装置５は、入力機能、表示機能、及び通信機能を有する端末であり、第１実施形態における入力装置２及び表示装置３として機能する。端末装置５は、例えば、パーソナルコンピュータ、タブレット型端末、ＰＤＡ（Ｐｅｒｓｏｎａｌ Ｄｉｇｉｔａｌ Ａｓｓｉｓｔａｎｔ）などであってもよい。端末装置５は、受け付けたユーザ入力に基づき生成した入力情報Ｓ１を、ネットワーク６を介して情報処理装置１Ａへ送信する。また、端末装置５は、情報処理装置１Ａから表示情報Ｓ２を受信した場合に、当該表示情報Ｓ２に基づき各種画面を表示する。

第２実施形態に係る情報処理装置１Ａは、第１実施形態において情報処理装置１が実行した入力処理及び表示処理を端末装置５の使用者を対象として好適に実行することができる。

＜第３実施形態＞
図１１は、第３実施形態における情報処理装置１Ｘの機能ブロック図である。情報処理装置１Ｘは、主に、解決定手段１５Ｘと、表示制御手段１６２Ｘとを有する。情報処理装置１Ｘは、複数の装置から構成されてもよい。

解決定手段１５Ｘは、最適化問題の条件に関する条件情報と、最適化問題の制約条件の緩和に関する制約緩和情報と、に基づき、最適化問題の解を、制約条件の緩和度合いに応じて決定する。解決定手段１５Ｘは、例えば、第１実施形態又は第２実施形態における解決定部１５とすることができる。

表示制御手段１６２Ｘは、制約条件の緩和度合いと、当該緩和度合いに対する解の目的関数値との関係を示す関係情報を、表示装置に表示する。表示装置は、情報処理装置１Ｘと別体の装置（例えば、表示装置３又は端末装置５）であってもよく、情報処理装置１Ｘに内蔵されてもよい。表示制御手段１６２Ｘは、例えば、第１実施形態又は第２実施形態における第１表示制御部１６２とすることができる。

図１２は、第３実施形態において情報処理装置１Ｘが実行するフローチャートの一例である。まず、解決定手段１５Ｘは、最適化問題の条件に関する条件情報と、最適化問題の制約条件の緩和に関する制約緩和情報と、に基づき、最適化問題の解を、制約条件の緩和度合いに応じて決定する（ステップＳ２１）。表示制御手段１６２Ｘは、制約条件の緩和度合いと、当該緩和度合いに対する解の目的関数値との関係を示す関係情報を、表示装置に表示する（ステップＳ２２）。

第３実施形態に係る情報処理装置１Ｘは、制約条件の緩和度合いと目的関数値との関係を好適に可視化することができる。

その他、上記の各実施形態（変形例を含む、以下同じ）の一部又は全部は、以下の付記のようにも記載され得るが以下には限られない。

［付記１］
最適化問題の条件に関する条件情報と、前記最適化問題の制約条件の緩和に関する制約緩和情報と、に基づき、前記最適化問題の解を、前記制約条件の緩和度合いに応じて決定する解決定手段と、
前記緩和度合いと、当該緩和度合いに対する前記解の目的関数値との関係を示す関係情報を、表示装置に表示する表示制御手段と、
を有する情報処理装置。
［付記２］
前記制約緩和情報は、緩和が許容される前記制約条件の種類と、当該制約条件の緩和範囲と、当該制約条件が緩和された場合の罰則の重みと、を含み、
前記緩和度合いは、前記解において緩和された制約条件に対する前記重みに基づき決定される、付記１に記載の情報処理装置。
［付記３］
前記制約条件の種類と、当該制約条件の緩和範囲と、当該制約条件が緩和された場合の罰則の重みとに関する指定を受け付ける制約緩和指定手段をさらに有する、付記２に記載の情報処理装置。
［付記４］
前記解決定手段は、前記解において緩和された制約条件の各々に対する前記重みに基づき、前記緩和度合いを表す指標値である罰則値を算出し、
前記表示制御手段は、前記罰則値と、当該罰則値に対する前記解の前記目的関数値との関係を示す前記関係情報を、前記表示装置に表示する、付記２または３に記載の情報処理装置。
［付記５］
前記解決定手段は、前記解において緩和された制約条件の各々に対する前記重みと前記解が緩和前の前記制約条件から外れた度合いとに基づき、前記罰則値を算出する、付記４に記載の情報処理装置。
［付記６］
前記表示制御手段は、少なくとも２つの前記緩和度合いに対応する前記解において緩和された前記制約条件の緩和状況を比較する情報を、前記表示装置に表示する、付記１～５のいずれか一項に記載の情報処理装置。
［付記７］
前記表示制御手段は、前記関係情報に基づく表示画面において、前記少なくとも２つの前記緩和度合いを指定する入力を受け付ける、付記６に記載の情報処理装置。
［付記８］
前記表示制御手段は、前記関係情報として、前記関係を示すテーブル又はグラフを、前記表示装置に表示する、付記１～７のいずれか一項に記載の情報処理装置。
［付記９］
コンピュータが、
最適化問題の条件に関する条件情報と、前記最適化問題の制約条件の緩和に関する制約緩和情報と、に基づき、前記最適化問題の解を、前記制約条件の緩和度合いに応じて決定し、
前記緩和度合いと、当該緩和度合いに対する前記解の目的関数値との関係を示す関係情報を、表示装置に表示する、
制御方法。
［付記１０］
最適化問題の条件に関する条件情報と、前記最適化問題の制約条件の緩和に関する制約緩和情報と、に基づき、前記最適化問題の解を、前記制約条件の緩和度合いに応じて決定し、
前記緩和度合いと、当該緩和度合いに対する前記解の目的関数値との関係を示す関係情報を、表示装置に表示する処理をコンピュータに実行させるプログラムが格納された記憶媒体。

なお、上述した各実施形態において、プログラムは、様々なタイプの非一時的なコンピュータ可読媒体（Ｎｏｎ－ｔｒａｎｓｉｔｏｒｙ ｃｏｍｐｕｔｅｒ ｒｅａｄａｂｌｅ ｍｅｄｉｕｍ）を用いて格納され、コンピュータであるプロセッサ等に供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記憶媒体（Ｔａｎｇｉｂｌｅ ｓｔｏｒａｇｅ ｍｅｄｉｕｍ）を含む。非一時的なコンピュータ可読媒体の例は、磁気記憶媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記憶媒体（例えば光磁気ディスク）、ＣＤ－ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＣＤ－Ｒ、ＣＤ－Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ（Ｐｒｏｇｒａｍｍａｂｌｅ ＲＯＭ）、ＥＰＲＯＭ（Ｅｒａｓａｂｌｅ ＰＲＯＭ）、フラッシュＲＯＭ、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（Ｔｒａｎｓｉｔｏｒｙ ｃｏｍｐｕｔｅｒ ｒｅａｄａｂｌｅ ｍｅｄｉｕｍ）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。

以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。すなわち、本願発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。また、引用した上記の特許文献等の各開示は、本書に引用をもって繰り込むものとする。

１、１Ａ、１Ｘ 情報処理装置
２ 入力装置
３ 表示装置
４ 記憶装置
５ 端末装置
１００、１００Ａ 最適化システム

Claims (10)

1. 目的関数値を最小化又は最大化する解を求める最適化問題の条件に関する条件情報と、前記最適化問題の制約条件の緩和に関する制約緩和情報と、に基づき、前記最適化問題の複数の解を、前記緩和の度合いに応じて設定される複数の罰則値ごとに決定する解決定手段と、
   前記罰則値と、当該罰則値に応じた前記緩和を行った場合に得られる前記解の目的関数値との関係を示す関係情報を、表示装置に表示する表示制御手段と、
   を有する情報処理装置。
2. 前記制約緩和情報は、緩和が許容される前記制約条件の種類と、当該制約条件の緩和範囲と、当該制約条件が緩和された場合の罰則の重みと、を含み、
   前記罰則値は、前記解において緩和された制約条件に対する前記重みに基づき決定される、請求項１に記載の情報処理装置。
3. 前記制約条件の種類と、当該制約条件の緩和範囲と、当該制約条件が緩和された場合の罰則の重みとに関する指定を受け付ける制約緩和指定手段をさらに有する、請求項２に記載の情報処理装置。
4. 前記解決定手段は、前記解において緩和された制約条件の各々に対する前記重みに基づき、前記罰則値を算出し、
   前記表示制御手段は、前記罰則値と、当該罰則値に対する前記解の前記目的関数値との関係を示す前記関係情報を、前記表示装置に表示する、請求項２または３に記載の情報処理装置。
5. 前記解決定手段は、前記解において緩和された制約条件の各々に対する前記重みと前記解が緩和前の前記制約条件から外れた度合いとに基づき、前記罰則値を算出する、請求項４に記載の情報処理装置。
6. 前記表示制御手段は、少なくとも２つの前記罰則値に対応する前記解において緩和された前記制約条件の緩和状況を比較する情報を、前記表示装置に表示する、請求項１～５のいずれか一項に記載の情報処理装置。
7. 前記表示制御手段は、前記関係情報に基づく表示画面において、前記少なくとも２つの前記罰則値を指定する入力を受け付ける、請求項６に記載の情報処理装置。
8. 前記表示制御手段は、前記関係情報として、前記関係を示すテーブル又はグラフを、前記表示装置に表示する、請求項１～７のいずれか一項に記載の情報処理装置。
9. コンピュータが、
   目的関数値を最小化又は最大化する解を求める最適化問題の条件に関する条件情報と、前記最適化問題の制約条件の緩和に関する制約緩和情報と、に基づき、前記最適化問題の複数の解を、前記緩和の度合いに応じて設定される複数の罰則値ごとに決定し、
   前記罰則値と、当該罰則値に応じた前記緩和を行った場合に得られる前記解の目的関数値との関係を示す関係情報を、表示装置に表示する、
   制御方法。
10. 目的関数値を最小化又は最大化する解を求める最適化問題の条件に関する条件情報と、前記最適化問題の制約条件の緩和に関する制約緩和情報と、に基づき、前記最適化問題の複数の解を、前記緩和の度合いに応じて設定される複数の罰則値ごとに決定し、
    前記罰則値と、当該罰則値に応じた前記緩和を行った場合に得られる前記解の目的関数値との関係を示す関係情報を、表示装置に表示する処理をコンピュータに実行させるプログラム。