基本的な定式化を紹介します。
(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 に使用例があります。