(2021.1.7) program1b.modelを修正しています。
はじめに
多数の数値の中から、合計値になる組み合わせを探す方法を考えてみました。
ここではGLPKを使っています。
###1. 合計に完全に一致する数値の組み合わせを探す
set ValueID; # 通し番号
param value{ValueID}; # 数値
param target_total; # 目標とする合計
var assign{ValueID} binary; # 選ばれた時に1、選ばれない時は0
s.t. constrain_total: sum{i in ValueID}assign[i]*value[i]==target_total;
solve;
# 出力
printf "合計 %f\n", target_total;
printf "内訳\n";
printf{i in ValueID: assign[i]==1} "%d %f\n", i, value[i];
data;
param target_total :=21258; # 合計
# 通し番号 値
param : ValueID : value :=
1 1679
2 681
3 75510
4 160
5 3416
6 2405
7 85230
8 7916
9 7030
10 9586
11 7420
12 6935
13 3830
14 5532
15 50306
16 8093
17 2394
18 6390
19 2017
20 1750
;
プログラム部分とデータ部分を分けてあり、データ部分だけの書き換えだけで動くようにしています。慣れないうちはプログラム部分の後にデータ部分を追加したファイルを作成して実行してみてください。
データ部分に、目標とする合計と20個の数値(行の前に1から20までの通し番号)が書いてあります。その部分は表計算ソフトからコピペをしています。数値の区切りは空白、タブ、コンマ、改行などが使え、並び順があっていれば形式は問いません。しかしデータの最後のセミコロンは必ず必要ですので、気をつけてください。
結果が出力されずに「PROBLEM HAS NO INTEGER FEASIBLE SOLUTION」が表示される場合には、合計が一致する組み合わせが見つからないということです。
出力は数値が小数を含んでも良いように、フォーマットで%fを指定しています。小数点以下も出力されますので、整数限定されるのであれば%dに書き換えてみてください。C言語のフォーマット指定と同じです。
小数を含む値の場合には、厳密は一致しないことがあるので、
s.t. constrain_totalの行を
s.t. total_upper_limit: sum{i in ValueID}assign[i]*value[i]<=target_total+0.001;
s.t. total_lower_limit: sum{i in ValueID}assign[i]*value[i]>=target_total-0.001;
のように許容範囲を設定する方が良いように思います。
整数計画問題では、通常1つしか答えを求めることができません。上の例では実は二種類の組み合わせがあります。
複数の組み合わせを探す
set ValueID; # 通し番号
param value{ValueID}; # 数値
param target_total; # 目標とする合計
param n_results integer; # 求める組み合わせの数
set Result := 1..n_results;
param power2{i in ValueID} integer := 2**(i-1); # 2のべき乗
var sig{Result} integer; # 組み合わせを特徴づけるユニークな値
var assign{Result, ValueID} binary; # 選ばれた時に1、選ばれない時は0
s.t. constrain_total{j in Result}: sum{i in ValueID}assign[j, i]*value[i]==target_total;
s.t. calc_sig{j in Result}: sum{i in ValueID}assign[j, i]*power2[i]==sig[j];
s.t. sig_order{i in 1..n_results-1}: sig[i+1]>=sig[i]+1;
minimize sig_upper_limit: sig[n_results];
solve;
# 出力
printf "合計 %f\n", target_total;
for{j in Result}{
printf "内訳\n";
printf{i in ValueID: assign[j, i]==1} "%d\t%f\n", i, value[i];
}
param n_results := 2; # 求める組み合わせの数
param target_total :=21258; # 合計
# 以下上記data1aと同じ
(2021.1.7) 7行目にintegerを追加しました。realだと同じ組み合わせが複数でてくることがあるようです。
n_resultsを増やしていきそれ以上の組み合わせがなくなると、「PROBLEM HAS NO INTEGER FEASIBLE SOLUTION」と表示されます。
それぞれの組み合わせ結果が異なることを保証するために、入力値に対して2のべき乗の値を与え、採用された値に対する2のべき乗の値を合計したsigを計算しています。sigは異なる組み合わせだと必ず違う値になります。
sig[1]とsig[2]が一致しないようにしたいので、sig[2]>=sig[1]+1という条件を使っています。
minimize行は必ずしも必要はないのですが、これがあると収束が速くなります。
もっとエレガントな方法があるかも知れません。良いアイデアがありましたらコメントをお願いします。
###2. 合計に一番近い数値の組み合わせを探す
set ValueID; # 通し番号
param value{ValueID}; # 数値
param target_total; # 目標とする合計
var assign{ValueID} binary; # 選ばれた時に1、選ばれない時は0
var total >=0.0; # 実際の合計
var difference >=0.0; # 目標とする合計と実際の合計の差の絶対値
s.t. calculate_total: sum{i in ValueID}assign[i]*value[i]==total; # 実際の合計
s.t. constrain_lower: total-target_total>=-difference;
s.t. constrain_upper: total-target_total<=difference;
minimize difference1: difference; # 目標とする合計と実際の合計の差の絶対値を最小に
solve;
# 出力
printf "目標合計 %f\n", target_total;
printf "実際の合計 %f 差 %f\n", total, total-target_total;
printf "内訳\n";
printf{i in ValueID: assign[i]==1} "%d %f\n", i, value[i];
data;
param target_total :=21249;
param : ValueID : value :=
以下data1aと同じ
合計値が一致する組み合わせがない場合には、一番近い組み合わせを表示します。
s.t.行とminimize行で差の絶対値が最小になる組み合わせを求めています。
このあたりの方法は、目次にある「整数計画法での定式化」を参考にしてください。