<--目次へ

(2021.1.7) program1b.modelを修正しています。

はじめに

多数の数値の中から、合計値になる組み合わせを探す方法を考えてみました。
ここではGLPKを使っています。

###1. 合計に完全に一致する数値の組み合わせを探す

program1a.model

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];

data1a

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つしか答えを求めることができません。上の例では実は二種類の組み合わせがあります。

複数の組み合わせを探す

program1b.model

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];
}

data1b

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. 合計に一番近い数値の組み合わせを探す

program2.model

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];

data2

data;
param target_total :=21249;
param : ValueID :  value :=
以下data1aと同じ

合計値が一致する組み合わせがない場合には、一番近い組み合わせを表示します。
s.t.行とminimize行で差の絶対値が最小になる組み合わせを求めています。
このあたりの方法は、目次にある「整数計画法での定式化」を参考にしてください。