Cheat Sheet

import jijmodeling as jm

総和

決定変数の総和

Plain API

problem = jm.Problem("BasicSum")
N = problem.Natural("N")
x = problem.BinaryVar("x", shape=(N,))
problem += x.sum()

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{BasicSum}\\\displaystyle \min &\displaystyle \sum _{\vec{\imath }}{{{\left(x\right)}}_{\vec{\imath }}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("BasicSum")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    x = problem.BinaryVar(shape=(N,))
    problem += x.sum()

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{BasicSum}\\\displaystyle \min &\displaystyle \sum _{\vec{\imath }}{{{\left(x\right)}}_{\vec{\imath }}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

係数付き決定変数の総和

Plain API

problem = jm.Problem("WeightedSum")
a = problem.Float("a", ndim=1)
N = problem.DependentVar("N", a.len_at(0))
x = problem.BinaryVar("x", shape=(N,))
problem += jm.sum(a * x)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{WeightedSum}\\\displaystyle \min &\displaystyle \sum _{\vec{\imath }}{{{\left(a\cdot x\right)}}_{\vec{\imath }}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}a&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}N&=\mathop{\mathtt{len\_{}at}}\left(a,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("WeightedSum")
def problem(problem: jm.DecoratedProblem):
    a = problem.Float(ndim=1)
    N = problem.DependentVar(a.len_at(0))
    x = problem.BinaryVar(shape=(N,))
    problem += (a * x).sum()

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{WeightedSum}\\\displaystyle \min &\displaystyle \sum _{\vec{\imath }}{{{\left(a\cdot x\right)}}_{\vec{\imath }}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}a&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}N&=\mathop{\mathtt{len\_{}at}}\left(a,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

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

Plain API

problem = jm.Problem("SumAlongSet")
N = problem.Natural("N")
x = problem.BinaryVar("x", shape=(N,))
C = problem.Natural("C", ndim=1)
problem += jm.sum(jm.map(lambda i: x[i], C))

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{SumAlongSet}\\\displaystyle \min &\displaystyle \sum _{i\in C}{{x}_{i}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}C&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("SumAlongSet")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    x = problem.BinaryVar(shape=(N,))
    C = problem.Natural(ndim=1)
    problem += jm.sum(x[i] for i in C)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{SumAlongSet}\\\displaystyle \min &\displaystyle \sum _{i\in C}{{x}_{i}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}C&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

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

Plain API

problem = jm.Problem("SumAlongEdgeSet")
V = problem.Natural("V")
E = problem.Graph("E")
x = problem.BinaryVar("x", shape=(V,))
problem += jm.map(lambda i, j: x[i] * x[j], E).sum()

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{SumAlongEdgeSet}\\\displaystyle \min &\displaystyle \sum _{\left\langle i,j\right\rangle \in E}{{x}_{i}\cdot {x}_{j}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[V;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}E&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{N}\times \mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\times \mathbb{N}\\V&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("SumAlongEdgeSet")
def problem(problem: jm.DecoratedProblem):
    V = problem.Natural()
    E = problem.Graph()
    x = problem.BinaryVar(shape=(V,))
    problem += jm.sum(x[i] * x[j] for (i, j) in E)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{SumAlongEdgeSet}\\\displaystyle \min &\displaystyle \sum _{\left\langle i,j\right\rangle \in E}{{x}_{i}\cdot {x}_{j}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[V;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}E&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{N}\times \mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\times \mathbb{N}\\V&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

条件付きの総和

Plain API

problem = jm.Problem("ConditionalSum")
N = problem.Natural("N")
J = problem.Float("J", shape=(N, N))
x = problem.BinaryVar("x", shape=(N,))
problem += jm.map(
    lambda i: jm.filter(lambda j: i > j, N).map(lambda j: J[i, j] * x[i] * x[j]).sum(),
    N
).sum()

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{ConditionalSum}\\\displaystyle \min &\displaystyle \sum _{i=0}^{N-1}{\sum _{\substack{j=0\\i>j}}^{N-1}{{J}_{i,j}\cdot {x}_{i}\cdot {x}_{j}}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}J&\in \mathop{\mathrm{Array}}\left[N\times N;\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("ConditionalSum")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    J = problem.Float(shape=(N, N))
    x = problem.BinaryVar(shape=(N,))
    problem += jm.sum(J[i, j] * x[i] * x[j] for i in N for j in N if i > j)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{ConditionalSum}\\\displaystyle \min &\displaystyle \sum _{i=0}^{N-1}{\sum _{\substack{j=0\\i>j}}^{N-1}{{J}_{i,j}\cdot {x}_{i}\cdot {x}_{j}}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}J&\in \mathop{\mathrm{Array}}\left[N\times N;\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

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

Plain API

problem = jm.Problem("NonDiagonalSum")
N = problem.Natural("N")
J = problem.Float("J", shape=(N, N))
problem += jm.map(
    lambda i: jm.filter(lambda j: i != j, N).map(lambda j: J[i, j]).sum(),
    N
).sum()

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{NonDiagonalSum}\\\displaystyle \min &\displaystyle \sum _{i=0}^{N-1}{\sum _{\substack{j=0\\i\neq j}}^{N-1}{{J}_{i,j}}}\\&\\\text{where}&\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}J&\in \mathop{\mathrm{Array}}\left[N\times N;\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("NonDiagonalSum")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    J = problem.Float(shape=(N, N)) 
    problem += jm.sum(J[i, j] for i in N for j in N if i != j)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{NonDiagonalSum}\\\displaystyle \min &\displaystyle \sum _{i=0}^{N-1}{\sum _{\substack{j=0\\i\neq j}}^{N-1}{{J}_{i,j}}}\\&\\\text{where}&\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}J&\in \mathop{\mathrm{Array}}\left[N\times N;\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

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

Plain API

problem = jm.Problem("DependentSum")
N = problem.Natural("N")
x = problem.BinaryVar("x", shape=(N,))
a = problem.Natural("a", ndim=1)
M = problem.DependentVar("M", a.len_at(0))
problem += jm.sum(jm.flat_map(lambda i: a[i].map(lambda j: x[j]), M))

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{DependentSum}\\\displaystyle \min &\displaystyle \sum _{i=0}^{M-1}{\sum _{j=0}^{{a}_{i}-1}{{x}_{j}}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}a&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}M&=\mathop{\mathtt{len\_{}at}}\left(a,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("DependentSum")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    x = problem.BinaryVar(shape=(N,))
    a = problem.Natural(ndim=1)
    M = problem.DependentVar(a.len_at(0))
    problem += jm.sum(x[j] for i in M for j in a[i])

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{DependentSum}\\\displaystyle \min &\displaystyle \sum _{i=0}^{M-1}{\sum _{j\in {a}_{i}}{{x}_{j}}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}a&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}M&=\mathop{\mathtt{len\_{}at}}\left(a,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

制約条件

One-hot 制約

Plain API

problem = jm.Problem("OneHot")
N = problem.Natural("N")
x = problem.BinaryVar("x", shape=(N,))
problem += problem.Constraint("onehot", x.sum() == 1)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{OneHot}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{onehot}&\quad \displaystyle \sum _{\vec{\imath }}{{{\left(x\right)}}_{\vec{\imath }}}=1\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("OneHot")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    x = problem.BinaryVar(shape=(N,))
    problem += problem.Constraint("onehot", x.sum() == 1)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{OneHot}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{onehot}&\quad \displaystyle \sum _{\vec{\imath }}{{{\left(x\right)}}_{\vec{\imath }}}=1\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

K-hot 制約

Plain API

problem = jm.Problem("KHot")
N = problem.Natural("N")
K = problem.Natural("K")
x = problem.BinaryVar("x", shape=(N,))
problem += problem.Constraint("k_hot", x.sum() == K)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{KHot}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{k\_{}hot}&\quad \displaystyle \sum _{\vec{\imath }}{{{\left(x\right)}}_{\vec{\imath }}}=K\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}K&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("KHot")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    K = problem.Natural()
    x = problem.BinaryVar(shape=(N,))
    problem += problem.Constraint("k_hot", x.sum() == K)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{KHot}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{k\_{}hot}&\quad \displaystyle \sum _{\vec{\imath }}{{{\left(x\right)}}_{\vec{\imath }}}=K\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}K&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

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

Plain API

problem = jm.Problem("2D K-Hot")
K = problem.Natural("K", ndim=1)
N = problem.DependentVar("N", K.len_at(0))
M = problem.Natural("M")
x = problem.BinaryVar("x", shape=(N, M))
problem += problem.Constraint("2d k-hot", x.sum(axis=1) == K)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{2D K-Hot}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{2d k-hot}&\quad \displaystyle x.\mathop{\mathtt{sum}}\left(\mathtt{axis}=\left[1\right]\right)=K\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N\times M;\left\{0, 1\right\}\right]&\quad &2\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}K&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\\M&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}N&=\mathop{\mathtt{len\_{}at}}\left(K,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("2D K-Hot")
def problem(problem: jm.DecoratedProblem):
    K = problem.Natural(ndim=1)
    N = problem.DependentVar(K.len_at(0))
    M = problem.Natural()
    x = problem.BinaryVar(shape=(N, M))
    problem += problem.Constraint("2d k-hot", x.sum(axis=1) == K)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{2D K-Hot}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{2d k-hot}&\quad \displaystyle x.\mathop{\mathtt{sum}}\left(\mathtt{axis}=\left[1\right]\right)=K\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N\times M;\left\{0, 1\right\}\right]&\quad &2\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}K&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\\M&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}N&=\mathop{\mathtt{len\_{}at}}\left(K,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

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

Plain API

problem = jm.Problem("KHotOverSet")
N = problem.Natural("N")
C = problem.Natural("C", jagged=True, ndim=2)
M = problem.DependentVar("M", C.len_at(0))
K = problem.Natural("K", shape=(M,))
x = problem.BinaryVar("x", shape=(N,))
problem += problem.Constraint(
    "k-hot_constraint", lambda a: C[a].map(lambda i: x[i]).sum() == K[a], domain=M
)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{KHotOverSet}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{k-hot\_{}constraint}&\quad \displaystyle \sum _{i\in {C}_{a}}{{x}_{i}}={K}_{a}\quad \forall a\;\text{s.t.}\;a\in \left\{0,\ldots ,M-1\right\}\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}C&\in \mathop{\mathrm{JaggedArray}}\left[(-)\times (-);\mathbb{N}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{N}\\K&\in \mathop{\mathrm{Array}}\left[M;\mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}M&=\mathop{\mathtt{len\_{}at}}\left(C,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("KHotOverSet")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    C = problem.Natural(jagged=True, ndim=2)
    M = problem.DependentVar(C.len_at(0))
    K = problem.Natural(shape=(M,))
    x = problem.BinaryVar(shape=(N,))
    problem += problem.Constraint(
        "k-hot_constraint", (jm.sum(x[i] for i in C[a]) == K[a] for a in M),
    )

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{KHotOverSet}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{k-hot\_{}constraint}&\quad \displaystyle \sum _{i\in {C}_{a}}{{x}_{i}}={K}_{a}\quad \forall a\;\text{s.t.}\;a\in \left\{0,\ldots ,M-1\right\}\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}C&\in \mathop{\mathrm{JaggedArray}}\left[(-)\times (-);\mathbb{N}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{N}\\K&\in \mathop{\mathrm{Array}}\left[M;\mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}M&=\mathop{\mathtt{len\_{}at}}\left(C,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

線形不等式制約

Plain API

problem = jm.Problem("LinearInequality")
w = problem.Float("w", ndim=1)
N = problem.DependentVar("N", w.len_at(0))
W = problem.Float("W")
x = problem.BinaryVar("x", shape=(N,))
problem += problem.Constraint("weight", (w * x).sum() <= W)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{LinearInequality}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{weight}&\quad \displaystyle \sum _{\vec{\imath }}{{{\left(w\cdot x\right)}}_{\vec{\imath }}}\leq W\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\w&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}N&=\mathop{\mathtt{len\_{}at}}\left(w,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("LinearInequality")
def problem(problem: jm.DecoratedProblem):
    w = problem.Float(ndim=1)
    N = problem.DependentVar(w.len_at(0))
    W = problem.Float()
    x = problem.BinaryVar(shape=(N,))
    problem += problem.Constraint("weight", (w * x).sum() <= W)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{LinearInequality}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{weight}&\quad \displaystyle \sum _{\vec{\imath }}{{{\left(w\cdot x\right)}}_{\vec{\imath }}}\leq W\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\w&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}N&=\mathop{\mathtt{len\_{}at}}\left(w,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

SOS1 不等式制約

Plain API

problem = jm.Problem("SOS-1")
N = problem.Natural("N")
M = problem.Float("M", shape=(N,))
a = problem.ContinuousVar("a", shape=N, lower_bound=0, upper_bound=M)
x = problem.BinaryVar("x", shape=N)
problem += problem.Constraint("SOS1", x.sum() <= 1)
problem += problem.Constraint("Big-M", a <= M * x)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{SOS-1}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{Big-M}&\quad \displaystyle a\leq M\cdot x\\\text{SOS1}&\quad \displaystyle \sum _{\vec{\imath }}{{{\left(x\right)}}_{\vec{\imath }}}\leq 1\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}a&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]\;\left(0\leq a\leq M\right)&\quad &1\text{-dim continuous variable}\\x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}M&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("SOS-1")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    M = problem.Float(shape=(N,))
    a = problem.ContinuousVar(shape=N, lower_bound=0, upper_bound=M)
    x = problem.BinaryVar(shape=N)
    problem += problem.Constraint("SOS1", x.sum() <= 1)
    problem += problem.Constraint("Big-M", a <= M * x)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{SOS-1}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{Big-M}&\quad \displaystyle a\leq M\cdot x\\\text{SOS1}&\quad \displaystyle \sum _{\vec{\imath }}{{{\left(x\right)}}_{\vec{\imath }}}\leq 1\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}a&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]\;\left(0\leq a\leq M\right)&\quad &1\text{-dim continuous variable}\\x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}M&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Big-M 不等式制約

Plain API

problem = jm.Problem("BigM")
N = problem.Natural("N")
c = problem.Float("c", shape=(N, N))
M = problem.Float("M")
x = problem.BinaryVar("x", shape=(N, N))
e = problem.Float("e", shape=(N,))
l = problem.Float("l", shape=(N,))
t = problem.IntegerVar("t", shape=(N,), lower_bound=e, upper_bound=l)
non_diagonals = jm.product(N, N).filter(lambda i, j: i != j)
problem += problem.Constraint(
    "Big-M",
    lambda i, j: t[i] + c[i, j] - M * (1 - x[i, j]) <= t[j],
    domain=non_diagonals,
)

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{BigM}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{Big-M}&\quad \displaystyle {t}_{i}+{c}_{i,j}-M\cdot \left(1-{x}_{i,j}\right)\leq {t}_{j}\quad \forall \left(i,j\right)\;\text{s.t.}\;i\in \left\{0,\ldots ,N-1\right\},j\in \left\{0,\ldots ,N-1\right\},i\neq j\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}t&\in \mathop{\mathrm{Array}}\left[N;\mathbb{Z}\right]\;\left(e\leq t\leq l\right)&\quad &1\text{-dim integer variable}\\x&\in \mathop{\mathrm{Array}}\left[N\times N;\left\{0, 1\right\}\right]&\quad &2\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}c&\in \mathop{\mathrm{Array}}\left[N\times N;\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\e&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\l&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\M&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Decorator API

@jm.Problem.define("BigM")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    c = problem.Float(shape=(N, N))
    M = problem.Float()
    x = problem.BinaryVar(shape=(N, N))
    e = problem.Float(shape=(N,))
    l = problem.Float(shape=(N,))
    t = problem.IntegerVar(shape=(N,), lower_bound=e, upper_bound=l)
    problem += problem.Constraint(
        "Big-M",
        (
            t[i] + c[i, j] - M * (1 - x[i, j]) <= t[j]
            for i in N
            for j in N
            if i != j
        ),
    )

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{BigM}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{Big-M}&\quad \displaystyle {t}_{i}+{c}_{i,j}-M\cdot \left(1-{x}_{i,j}\right)\leq {t}_{j}\quad \forall \left(i,j\right)\;\text{s.t.}\;i\in \left\{0,\ldots ,N-1\right\},j\in \left\{0,\ldots ,N-1\right\},i\neq j\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}t&\in \mathop{\mathrm{Array}}\left[N;\mathbb{Z}\right]\;\left(e\leq t\leq l\right)&\quad &1\text{-dim integer variable}\\x&\in \mathop{\mathrm{Array}}\left[N\times N;\left\{0, 1\right\}\right]&\quad &2\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}c&\in \mathop{\mathrm{Array}}\left[N\times N;\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\e&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\l&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\M&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]