HUMPS (Ver. 1.10a)

  1. 概要
  2. 既知の不具合
  3. 使用条件
  4. インストール
  5. 実行例
  6. データファイル
  7. 実行結果のファイル
  8. 制限事項
  9. 補足
  10. 更新履歴
  11. 謝辞
  12. 参考文献

概要

HUMPSは，（混合整数）線形計画問題を解くパッケージで，主な機能は以下の通りです。

既知の不具合

使用条件

インストール

  1. まず使用する環境に応じた実行形式ファイルを入手して下さい。

    上にあげた環境以外についての対応は現時点で予定しておりませんが，強いご希望があれば作者までご連絡下さい。ちなみに，当方が使用している開発環境は，Windows95/98/NT が Microsoft Visual Studio 6.0， Solaris 2.5.1 (Sparc) は Sun Workshop (version 3)， Solaris 2.5.1 (x86) は GNU gcc (version 2.7.2.3)です。

  2. 使用環境が Windows95/98/NT であればそのまま動作するはずです。 UNIX 環境の場合，ファイルに実行許可を与える必要があると思います。 なお，ファイル名はご自分の好みで変えていただいて結構です。

実行例

  1. HUMPS に与える入力データをあらかじめ作成しておく必要があります。 現時点で，データファイルを作成するツールはありません。 データファイルの形式等は後程説明します。 ここでは，サンプルデータ(sample.mps)をダウンロードしてみて下さい。

  2. HUMPS はすべての実行環境において，非GUI (graphical user interface) です。 Windows 95/98/NTの場合，コマンドプロンプトからファイル名を指定して下さい。 なお，カレントディレクトリに，zzで始まる複数の補助ファイルが自動的に 作成されます。 （具体的には，zzvar.dat, zzwork.dat, zzsearch.dat，zzvalue.dat の4つのファイル。） もし，同じ名前のユーザーファイルがあると上書きされてしまいますので， 注意して下さい。また，プログラム実行中にこれらのファイルを消さないように注意して下さい。 プログラム終了後は消去しても結構です。 （但し，データファイルを変更せず，再度同じ問題を解きたい場合には， これらの作業ファイルを残しておけば， データファイル読み込み時間分だけ処理時間を短縮できます。）

  3. 以下に，実行の様子を示します。 
    >humps
HUMPS Ver. 1.10 (C) Copyright 1998 Katsumi Morikawa.
You need information? (yes = 1, no = 0) :1
New MPS data? (yes = 1, no = 0) :1
MPS data file name : sample.mps
Rows Section Start.
Columns Section Start.
RHS Section Start.
Ranges Section Start.
Bounds Section Start.
 Data echo back
 Number of rows     :     4
 Number of columns  :     3
 Number of elements :    12
 Density (%)        :100.000
We are writing information.
Finished...
Output file name:sample.res
Save final solution? (yes = 1, no = 0) :0
Use saved solution? (yes = 1, no = 0) :0
 iteration:     1, current ita stack:       3
 iteration:     2, current ita stack:       3
Become Feasible.
 iteration:     3, current ita stack:       7
 iteration:     4, current ita stack:      11
Optimal Solution.
>
  4. 【実行の様子の説明】
    実行形式ファイル名を与えると，まず付加的な情報を画面に表示するかどうかを聞いてきます。 no (=0) を指定すると，実行中の状況が表示されないため， 多少処理速度は低下しますが，yes (=1)を指定することをお勧めします （ただし，混合整数計画問題を解く場合は，no (=0) とした方がよい）。 次に，新しいデータファイルであるか否かを聞いてきます。 通常はyes (=1) になると思います。データファイル名を入力すると， プログラムはデータ解析を行い，データにエラーがなければ，補助ファイルにデータの 内容を一部加工しつつ書き出します。
    Output file name: に対しては，結果を書き出すファイル名を指定します。 次の Save final solution? に対しては，通常の利用では no (=0) を選んで下さい。 次の Use saved solution? についても同様です。 もし，再度，類似した問題を解くのであれば，最終解を保存しておいた方が有利です（特に大規模な問題の場合）。 もし Save final solution? に対して保存する (yes = 1) を選んだ場合，ファイル名が要求されます。 ここで保存したファイルは，次回以降の実行で，「Use saved solution?」に対して yes (=1) を選ぶことで 入力できます。
    以上の諸準備がすむと，humps が処理を開始し，最後に最適解を得たか， あるいは実行不可能であったり，非有界であった場合に停止し，結果を先に指定した ファイルに書き出して終了します。

データファイル

以下のファイルは 制約行数４（目的関数含む），決定変数３の 簡単な問題の入力データをあらわしています。 いわゆるＭＰＳ形式とは若干異なり，ＥＣＬ形式を基にしています。 すでにＭＰＳ形式をご存知の方にはほぼ違和感なくご利用いただける と思います。 「ＭＰＳとは何か？聞いたこともない。」という方は，たとえば本文末の参考文献 を参照下さい。あるいは，ＭＰＳ形式についてホームページで公開されている 文書もありますので，それらを参考にしていただくことも良策です。 
RO                              
N OBJECT                        
E ROW01                         
L ROW02                         
G ROW03                         
CO                              
  X01     OBJECT          -25.0
  X01     ROW01             2.0
  X01     ROW02             6.0
  X01     ROW03             7.0
  X02     OBJECT          -50.0
  X02     ROW01            10.0
  X02     ROW02             5.0
  X02     ROW03            10.0
  X03     OBJECT          -34.0
  X03     ROW01             4.0
  X03     ROW02             8.0
  X03     ROW03             8.0
RH                             
          ROW01           425.0
          ROW02           400.0
          ROW03           550.0
RA                             
          ROW03            50.0
BO                             
LO        X01              10.0
UP        X01              25.0
LO        X03              -1.0
UP        X03              10.0
EA
このデータに対応した問題を数式で表したものを用意しています(PDF形式です）。

以下では，ＭＰＳ形式に対してある程度の知識のある読者を想定して説明します。

まず大きな前提条件として，HUMPS は目的関数の最小化を目的としており， 目的関数の行の名前は「OBJECT 」に固定してあります。 また，データセット名も与える設定にはなっておりません。 ROWS，COLUMNS，RHS，RANGES，BOUNDSなどのインジケータは， それぞれ以下のように２文字だけを利用するようになっています。 

    RO :    ROWS    インジケータ
    CO :    COLUMNS インジケータ
    RH :    RHS     インジケータ
    RA :    RANGES  インジケータ
    BO :    BOUNDS  インジケータ
    EA :    データの終了
    NA :    当該行データを無視
    M  :    マーカーレコードインジケータ
COLUMNS の行以降についてＭＰＳ形式では， １つのデータ行で（Ａ，Ｂ，データ１，Ｃ，データ２）のような５項形式のデータ入力が認められていますが， 本システムでは，１つの行で１つの値しか認めない形式となっています。 よって，先の例では２行を利用して（Ａ，Ｂ，データ１）と（Ａ，Ｃ，データ２）のような形でデータを与える必要があります。 （なお，先の例でカッコやカンマは説明の便宜上用いたものであり，実際には上の例から明らかなようにこれらの区切り記号は使用しません。）

制約行と決定変数の名前は８文字（固定値）であり，８文字より短い名前の場合にも空白を補って， 必ず８文字として下さい。なお，大文字・小文字は区別されます。 また，行列の値は実数値で与えて下さい（たとえ整数値しか出てこない問題でも， 必ず .0 を補って実数表現にして下さい）。

行の最初の２文字分はインジケータ，もしくは制約行列の タイプ用で，次の８文字分は制約行名もしくは決定変数名用， 次の８文字分も制約行名もしくは決定変数名用，その後に 値を書きます。値については特に指定文字幅はありません。

混合整数計画問題の場合， たとえば，上述の問題で決定変数 X02 が整数変数の場合，データは以下のように記述して下さい。 

RO                              
N OBJECT                        
E ROW01                         
L ROW02                         
G ROW03                         
CO                              
  X01     OBJECT          -25.0
  X01     ROW01             2.0
  X01     ROW02             6.0
  X01     ROW03             7.0
M         'INTORG'
  X02     OBJECT          -50.0
  X02     ROW01            10.0
  X02     ROW02             5.0
  X02     ROW03            10.0
M         'INTEND'
  X03     OBJECT          -34.0
  X03     ROW01             4.0
  X03     ROW02             8.0
  X03     ROW03             8.0
RH                             
          ROW01           425.0
          ROW02           400.0
          ROW03           550.0
RA                             
          ROW03            50.0
BO                             
LO        X01              10.0
UP        X01              25.0
LO        X03              -1.0
UP        X03              10.0
EA
すなわち，COLUMNS セクションで 'INTORG' と 'INTEND' で囲まれた範囲の 決定変数が整数変数として取り扱われます。 なお，整数変数の取る値は０，１，２という０以上の整数に限定しています。

実行結果のファイル

実行結果はＭＰＳを模倣しておりますので，ＭＰＳを利用された方であればそのままご理解いただけると思います。以下では初めての方を想定して，最小限度の説明をいたします。

以下の結果は先のサンプルデータに対応しております。最初のあたりに 「Optimal solution.」と表示されていることより，最適解が得られたことがわかります。 最適解の目的関数値は NUMBER 0 にある OBJECT の行の ACTIVITY の個所に示されている -2640 です。 この値を与えた決定変数の値が，SECTION 2 - COLUMNS の NUMBER 4 から 6 の 個所で与えられており，X01 は 25，X02 は 33.5，X03 は 10.0 となっています。 それぞれの決定変数に与えられた目的関数の係数は INPUT COST の部分に，また 決定変数の上下限値は LOWER LIMIT と UPPER LIMIT に表示されています。 なお，原則としてゼロの値はピリオド(.)で示されます（たとえば，X02の下限値の個所）。 

*** Generated by HUMPS Ver. 1.10 (C) 1998 Katsumi Morikawa. ***

 Optimal solution.

  SECTION 1 - ROWS

 NUMBER  ...ROW..  AT  ...ACTIVITY...  SLACK ACTIVITY  ..LOWER LIMIT.  ..UPPER LIMIT.  .DUAL ACTIVITY
      0  OBJECT    BS     -2640.00000      2640.00000            NONE            NONE          .     
      1  ROW01     EQ       425.00000          .            425.00000       425.00000          .     
      2  ROW02     BS       397.50000         2.50000            NONE       400.00000          .     
      3  ROW03     BS       590.00000       -40.00000       550.00000       600.00000          .     

  SECTION 2 - COLUMNS

 NUMBER  .COLUMN.  AT  ...ACTIVITY...  ..INPUT COST..  ..LOWER LIMIT.  ..UPPER LIMIT.  .REDUCED COST.
      4  X01       UL        25.00000       -25.00000        10.00000        25.00000       -15.00000
      5  X02       BS        33.50000       -50.00000          .                 NONE          .     
      6  X03       UL        10.00000       -34.00000        -1.00000        10.00000       -14.00000

入力問題が混合整数計画問題であった場合，最初に，整数制約を緩和した問題の 最適解が示された後に，実行可能な解１，実行可能な解２，...と，出力されます。実行可能な解は， 現在よりも目的関数値の小さいものが発見されるたびに出力され，最後に，もうこれ以上よい解が ないとわかった時点で，最後に出力された解が最適解であるというメッセージが出ます。 先に挙げた問題の場合，次のように出力されます。 

*** Generated by HUMPS Ver. 1.10 (C) 1998 Katsumi Morikawa. ***

 LP Relaxed Optimal solution.

  SECTION 1 - ROWS

 NUMBER  ...ROW..  AT  ...ACTIVITY...  SLACK ACTIVITY  ..LOWER LIMIT.  ..UPPER LIMIT.  .DUAL ACTIVITY
      0  OBJECT    BS     -2640.00000      2640.00000            NONE            NONE          .     
      1  ROW01     EQ       425.00000          .            425.00000       425.00000          .     
      2  ROW02     BS       397.50000         2.50000            NONE       400.00000          .     
      3  ROW03     BS       590.00000       -40.00000       550.00000       600.00000          .     

  SECTION 2 - COLUMNS

 NUMBER  .COLUMN.  AT  ...ACTIVITY...  ..INPUT COST..  ..LOWER LIMIT.  ..UPPER LIMIT.  .REDUCED COST.
      4  X01       UL        25.00000       -25.00000        10.00000        25.00000       -15.00000
      5I X02       BS        33.50000       -50.00000          .                 NONE          .     
      6  X03       UL        10.00000       -34.00000        -1.00000        10.00000       -14.00000

 Feasible solution for mixed-integer problem.

  SECTION 1 - ROWS

 NUMBER  ...ROW..  AT  ...ACTIVITY...  SLACK ACTIVITY  ..LOWER LIMIT.  ..UPPER LIMIT.  .DUAL ACTIVITY
      0  OBJECT    BS     -2622.50000      2622.50000            NONE            NONE          .     
      1  ROW01     EQ       425.00000          .            425.00000       425.00000          .     
      2  ROW02     BS       390.00000        10.00000            NONE       400.00000          .     
      3  ROW03     BS       585.00000       -35.00000       550.00000       600.00000          .     

  SECTION 2 - COLUMNS

 NUMBER  .COLUMN.  AT  ...ACTIVITY...  ..INPUT COST..  ..LOWER LIMIT.  ..UPPER LIMIT.  .REDUCED COST.
      4  X01       UL        25.00000       -25.00000        10.00000        25.00000        -8.00000
      5I X02       LL        34.00000       -50.00000        34.00000            NONE        35.00000
      6  X03       BS         8.75000       -34.00000        -1.00000        10.00000          .     

 *** The final solution is optimal. ***
整数変数と実数変数の識別は，SECTION 2 で番号(NUMBER)の直後にある記号 'I' で識別します（Iがあれば，整数変数）。上の例では，X02が整数変数であることがわかります。 最後の行に，*** The final solution is optimal. ***と出力されていることより， 最適解の目的関数値は -2622.5 であることがわかります。
なお，整数変数に対しては，逐次，上下限制約を追加して問題を解くため，整数変数に対する 上下限値は，もともと与えたものとは異なった値が出力されるため，注意して下さい。 （上の例では，整数変数 X02 はゼロ以上の値が取れるという設定ですが，最適解のところを見ると， 下限が34と設定されています。）

制限事項

補足

更新履歴

謝辞

参考文献

  1. 反町洋一編：線形計画法の実際（講座・数理計画法３），産業図書，1992.
  2. W. オーチャード・ヘイズ著，高橋磐郎ら監修：コンピュータによる線形計画法，培風館，1973．
  3. HITACプログラムプロダクト VOS2/VOS3，数理計画システム MPSII/MPSII-RMO，文法/操作
Apr. 20, 2001
mkatsumi@hiroshima-u.ac.jp