整数計画問題を解くための数値計算ライブラリ
整数計画問題とは?
変数が整数であるという制約条件を付けた線形計画問題を 一般的に整数計画問題(IP=Integer Programming)と呼んでいます。この中で一部の変数のみが整数の問題を混合整数計画問題と分けて呼ぶ場合もあります。 整数計画問題はオペレーションズリサーチなどで 広く利用されますが、変数の数が多くなると計算量が膨大になります。
例えば左の問題(3X1 + 2X2が一番小さくなるようにする)を考えた場合、下の図の斜線部分が解の「可能領域」となり、×を中に含む○で示されている点が整数座標になります。 「斜線」は実際にはコンター図を表していますので、この図からこの問題の解は(1,1)であることがわかります。 この問題では一意な解が求まりましたが、解が存在しない場合や一意に求まらない場合もあり得ます。
nAGが提供する整数計画問題ルーチンについて
nAG数値計算ライブラリが提供する整数計画問題ルーチンでは分枝限定法(branch and bound method)を用いて、 すべての変数もしくは一部の変数が整数もしくは0または1の問題を解くことが可能です。 本ソルバールーチンでは最適解もしくは最初に見つかった解を求めることが可能です。
またnAGでは整数計画問題に利用されている MPSX形式のデータを読み込むためルーチンもあわせて提供されます。 これによりMPSX形式で記述した整数計画問題の利用が容易に行えます。
nAG数値計算ライブラリはC/C++, Java, VB, VBA(Excel), MATLAB®(Toolboxとして)など様々な環境から利用可能ですので、研究者の方やシステム開発会社様にぴったりの商品です。 nAGライブラリについての詳細はこちらをご参照下さい。
リファレンス
Ahuja R K, Magnanti T L and Orlin J B (1993) Network Flows: Theory, Algorithms, and
Applications Prentice Hall.
Beale E M (1977) Integer Programming The State of the Art in Numerical Analysis (ed D A H
Jacobs) Academic Press.
Dantzig G B (1963) Linear Programming and Extensions Princeton University Press.
Mitra G (1973) Investigation of branch and bound strategies for the solution of mixed integer linear
programs Math. Programming 4 155-170.
Williams H P (1990) Model Building in Mathematical Programming (3rd Edition) Wiley.
unattributed (1971) Program Number 5734 XM4 MPSX - Mathematical programming system IBM
Trade Corporation, New York.
整数計画問題に関する主な関数(サブルーチン)詳細
開発環境 | 関数名 | 機能 |
C | nag_ip_bb | 0-1整数計画問題,混合整数計画問題,全整数計画問題 |
Fortran | H02BBF | |
.NET | h02bb | |
C | nag_transport | 輸送計画問題 |
Fortran | H03ABF | |
C | nag_ip_mps_read | mpsx形式データの読み込み |
Fortran | H02BUF |