Cheat Sheet

Cheat Sheet#

総和#

決定変数の総和#

import jijmodeling as jm

N = jm.Placeholder('N')
x = jm.BinaryVar('x',shape=(N,))
i = jm.Element('i', belong_to=(0, N))
jm.sum(i,x[i])

\[\displaystyle \sum_{i = 0}^{N - 1} x_{i}\]

係数付き決定変数の総和#

import jijmodeling as jm

N = jm.Placeholder('N')
a = jm.Placeholder('a', ndim=1)
x = jm.BinaryVar('x', shape=(N,))
i = jm.Element('i', belong_to=(0, N))
jm.sum(i,a[i] * x[i])

\[\displaystyle \sum_{i = 0}^{N - 1} a_{i} \cdot x_{i}\]

添字集合に沿った決定変数の総和#

import jijmodeling as jm

N = jm.Placeholder('N')
C = jm.Placeholder('C', ndim=1)
x = jm.BinaryVar('x', shape=(N,))
i = jm.Element('i', belong_to=C)
jm.sum(i,x[i])

\[\displaystyle \sum_{i \in C} x_{i}\]

辺集合に沿った決定変数の総和#

import jijmodeling as jm

V = jm.Placeholder('V')
E = jm.Placeholder('E', ndim=2)
x = jm.BinaryVar('x', shape=(V,))
e = jm.Element('e', belong_to=E)
jm.sum(e, x[e[0]]*x[e[1]])

\[\displaystyle \sum_{e \in E} x_{e_{0}} \cdot x_{e_{1}}\]

条件付きの総和#

import jijmodeling as jm

N = jm.Placeholder('N')
J = jm.Placeholder('J', ndim=2)
x = jm.BinaryVar('x', shape=(N,))
i = jm.Element('i', belong_to=(0, N))
j = jm.Element('j', belong_to=(0, N))
jm.sum([i,(j,i>j)],J[i,j] * x[i] * x[i])

\[\begin{split}\displaystyle \sum_{i = 0}^{N - 1} \sum_{\substack{j = 0\\i > j}}^{N - 1} J_{i, j} \cdot x_{i} \cdot x_{i}\end{split}\]

行列の対角要素を除く総和#

import jijmodeling as jm

N = jm.Placeholder('N')
J = jm.Placeholder('J', ndim=2)
i = jm.Element('i', belong_to=(0, N))
j = jm.Element('j', belong_to=(0, N))
jm.sum([i,(j,i!=j)],J[i,j])

\[\begin{split}\displaystyle \sum_{i = 0}^{N - 1} \sum_{\substack{j = 0\\i \neq j}}^{N - 1} J_{i, j}\end{split}\]

別のインデックスに依存した総和#

import jijmodeling as jm

N = jm.Placeholder('N')
x = jm.BinaryVar('x', shape=(N,))
a = jm.Placeholder('a', ndim=1)
i = jm.Element('i', belong_to=(0,N))
j = jm.Element('j', belong_to=a[i]) 
jm.sum(i, jm.sum(j, x[j]))

\[\displaystyle \sum_{i = 0}^{N - 1} \sum_{j = 0}^{a_{i} - 1} x_{j}\]

制約条件#

One-hot制約#

import jijmodeling as jm

N = jm.Placeholder('N')
x = jm.BinaryVar('x',shape=(N,))
i = jm.Element('i', belong_to=(0, N))
jm.Constraint('onehot_constraint' , jm.sum(i,x[i]) == 1)

\[\begin{split}\begin{array}{cccc} & \text{onehot\_constraint} & \displaystyle \sum_{i = 0}^{N - 1} x_{i} = 1 & \\ \end{array}\end{split}\]

K-hot制約#

import jijmodeling as jm

K = jm.Placeholder('K')
N = jm.Placeholder('N')
x = jm.BinaryVar('x',shape=(N,))
i = jm.Element('i', belong_to=(0, N))
jm.Constraint('k-hot_constraint' , jm.sum(i,x[i]) == K)

\[\begin{split}\begin{array}{cccc} & \text{k-hot\_constraint} & \displaystyle \sum_{i = 0}^{N - 1} x_{i} = K & \\ \end{array}\end{split}\]

2次元バイナリ変数の各列に対するK-hot制約#

import jijmodeling as jm

K = jm.Placeholder('K', ndim=1)
N = jm.Placeholder('N')
x = jm.BinaryVar('x', shape=(N,N))
i = jm.Element('i', belong_to=(0, N))
j = jm.Element('j', belong_to=(0, N))
jm.Constraint('k-hot_constraint' , jm.sum(i,x[i,j]) == K[j], forall=j)

\[\begin{split}\begin{array}{cccc} & \text{k-hot\_constraint} & \displaystyle \sum_{i = 0}^{N - 1} x_{i, j} = K_{j} & \forall j \in \left\{0,\ldots,N - 1\right\} \\ \end{array}\end{split}\]

各集合に対するK-hot制約#

K = jm.Placeholder('K', ndim=1)
C = jm.Placeholder('C', ndim=2)
N = jm.Placeholder('N') # for binary index
M = jm.Placeholder('M') # for set index

x = jm.BinaryVar('x', shape=(N,))
a = jm.Element('a', belong_to=(0, M))
a.set_latex(r'\alpha')
i = jm.Element('i', belong_to=C[a])

jm.Constraint('k-hot_constraint' , jm.sum(i,x[i]) == K[a], forall=a)

\[\begin{split}\begin{array}{cccc} & \text{k-hot\_constraint} & \displaystyle \sum_{i \in C_{\alpha}} x_{i} = K_{\alpha} & \forall \alpha \in \left\{0,\ldots,M - 1\right\} \\ \end{array}\end{split}\]

ナップサック制約 (線形不等式制約)#

import jijmodeling as jm

w = jm.Placeholder('w', ndim=1)
W = jm.Placeholder('W')
N = jm.Placeholder('N')
x = jm.BinaryVar('x', shape=(N,))
i = jm.Element('i', belong_to=(0, N))
jm.Constraint('weight', jm.sum(i,w[i] * x[i])<=W)

\[\begin{split}\begin{array}{cccc} & \text{weight} & \displaystyle \sum_{i = 0}^{N - 1} w_{i} \cdot x_{i} \leq W & \\ \end{array}\end{split}\]

Big-M不等式制約#

import jijmodeling as jm

c = jm.Placeholder('c', ndim=2)
N = c.len_at(0, latex='N')
M = jm.Placeholder('M')

x = jm.BinaryVar('x', shape=(N,N))
e = jm.Placeholder('e', ndim=1)
l = jm.Placeholder('l', ndim=1)
t = jm.IntegerVar('t',shape=(N,),lower_bound=e,upper_bound=l)
i = jm.Element('i', belong_to=(0,N))
j = jm.Element('j',belong_to=(0,N))
    
jm.Constraint('Big-M',t[i] + c[i,j] - M * (1 - x[i,j]) <= t[j],forall=[(i),(j,j!=i)])

\[\begin{split}\begin{array}{cccc} & \text{Big-M} & \displaystyle t_{i} + c_{i, j} - M \cdot \left(- x_{i, j} + 1\right) \leq t_{j} & \forall i \in \left\{0,\ldots,N - 1\right\} \forall j \in \left\{j \in \left\{0,\ldots,N - 1\right\} \mid j \neq i \right\} \\ \end{array}\end{split}\]