整数計画法での定式化

<--目次へ

基本的な定式化を紹介します。

(2021.12.24 追記)

論理演算

バイナリ変数の場合には次の定式化が可能です。

	制約条件	バイナリ変数yに値を設定	または
not	1-x	x+y == 1
and (2変数)	x1+x2 == 2	x1+x2-1 <= y x1+x2 >= 2*y	x1+x2-1 <= y x1 >= y x2 >= y
and (3変数)	x1+x2+x3 == 3	x1+x2+x3-2 <= y x1+x2+x3 >= 3*y	x1+x2+x3-2 <= y x1 >= y x2 >= y x3 >= y
and (配列)	sum{i in 1..n}x[i]==n	sum{i in 1..n}x[i]-n+1 <= y sum{i in 1..n}x[i] >=n*y	sum{i in 1..n}x[i]-n+1 <= y {i in 1..n}: x[i] >=y
or (2変数)	x1+x2 >= 1	x1+x2 >= y x1+x2 <= 2*y	x1+x2 >= y x1 <= y x2 <= y
or (3変数)	x1+x2+x3 >= 1	x1+x2+x3 >= y x1+x2+x3 <= 3*y	x1+x2+x3 >= y x1 <= y x2 <= y x3 <= y
or (配列)	sum{i in 1..n}x[i]>=1	sum{i in 1..n}x[i] >= y sum{i in 1..n}x[i] <= n*y	sum{i in 1..n}x[i] >= y {i in 1..n}: x[i] <= y

目的関数でyの最小化や最大化をする時には、andやorの2式は一方だけを使うことで可能です。

例えばor(3変数)のときは
s.t. x1+x2+x3 <= 3*y;
minimize y;
片方の制約式で目的を達成できます。

N以上・N未満の数

zがN以上の時にyが1になります

gte.mod

var z integer, >=0;
var y binary;
s.t. geN1: z-(N-1)<=M*y;
s.t. geN2: z>=N*y;

Mはz-(N-1)が取りうる最大の数あるいはそれ以上の任意の整数を与えます。
yを(1-y)に入れ替えると、否定の意味になりますので、N未満を検出できるようになります。

1以上の数の使用例が「生産現場で役に立つかもしれない最適化手法1【GLPK】」のpallet04.modにありますので参考に。

最大値・最小値

最大値をyに(最大値の最小化)

maximize.mod

var y;
s.t. max_x: max{i in 1..n}: x[i]<=y;
minimize max_y: y;

最小値をyに(最小値の最大化)

minimize.mod

var y;
s.t. max_x: max{i in 1..n}: x[i]>=y;
maximize min_y: y;

絶対値

xが-LからUの間(L,Uは正)にある場合には絶対値(y)が求められます。

abs1.mod

var x, >=-L, <=U;
var y, >=0;
var z binary;
s.t. abs1: x<=y;
s.t. abs2: x>=-y;
s.t. abs3: y<=-x+2*U*z;
s.t. abs4: y<=x+2*L*(1-z);

目的関数で絶対値の最小化をする場合には次のような簡単なプログラムでできます。

abs2.mod

var x;
var y ,>=0;
s.t. abs1: x<=y;
s.t. abs2: x>=-y;
minimize abs: y;

商と余り

xをNで割った時の値y

div1.mod

var x integer, >=0;
var y integer, >=0;
s.t. div1: y >= x*N;
s.t. div2: y <= x*N+N-1;

余りzはx-y*Nでも求められますが、次のようにすると商と余りを同時に求めることができます。

div2.mod

var x integer, >=0;
var y integer, >=0;
var z integer, >=0, <=N-1;
s.t. div1: y == x*N+z;

Nで割り切れるか

(2021.12.24 追記)

div3.mod

var quotient integer, >=0; # 商　上限も設定する方が良い
var divisible binary; # Nで割り切れると1、余りがあると0になるバイナリ変数

s.t. div_1: x >= quotient*N;
s.t. div_2: x <= quotient*N+(N-1)*(1-divisible);

上式では、xがNで割り切れるときには、divisibleが1か0に、割り切れないときには0になります。
maximizeなどを使って目的関数にdivisibleを入れると割り切れるか判断することが可能です。
「生産現場で役に立つかもしれない最適化手法1【GLPK】」の pallet04_ext に使用例があります。

参考資料

整数計画法による定式化入門