SCOP（Solver forCOnstraint Programing：スコープ）は， 大規模な制約最適化問題を高速に解くためのソルバーである．
ここで，制約最適化(constraint optimization)とは， 数理最適化を補完する最適化理論の体系であり， 組合せ最適化問題に特化した求解原理-メタヒューリスティクス(metaheuristics)-を用いるため， 数理最適化ソルバーでは求解が困難な大規模な問題に対しても，効率的に良好な解を探索することができる．
SCOPのトライアルバージョンは， http://logopt.com/scop2/ からダウンロードもしくはgithub https://github.com/mikiokubo/scoptrial からクローンできる． また，テクニカルドキュメントは， https://scmopt.github.io/manual/14scop.html にある．
重み付き制約充足問題
ここでは，SCOPで対象とする重み付き制約充足問題について解説する．
一般に制約充足問題(constraint satisfaction problem)は，以下の3つの要素から構成される．
変数(variable): 分からないもの，最適化によって決めるもの． 制約充足問題では，変数は，与えられた集合（以下で述べる「領域」）から1つの要素を選択することによって決められる．
領域(domain): 変数ごとに決められた変数の取り得る値の集合
制約(constraint): 幾つかの変数が同時にとることのできる値に制限を付加するための条件． SCOPでは線形制約（線形式の等式，不等式），2次制約（一般の2次式の等式，不等式）， 相異制約（集合に含まれる変数がすべて異なることを表す制約）が定義できる．
制約充足問題は，制約をできるだけ満たすように， 変数に領域の中の1つの値を割り当てることを目的とした問題である．
SCOPでは，重み付き制約充足問題(weighted constraint satisfaction problem) を対象とする．
ここで「制約の重み」とは，制約の重要度を表す数値であり， SCOPでは正数値もしくは無限大を表す文字列 "inf"を入力する． "inf"を入力した場合には，制約は絶対制約(hard constraint)とよばれ， その逸脱量は優先して最小化される． 重みに正数値を入力した場合には，制約は考慮制約(soft constraint)とよばれ， 制約を逸脱した量に重みを乗じたものの和の合計を最小化する．
すべての変数に領域内の値を割り当てたものを解(solution)とよぶ． SCOPでは，単に制約を満たす解を求めるだけでなく， 制約からの逸脱量の重み付き和（ペナルティ）を最小にする解を探索する．
SCOPが有効なケース
SCOPは組合せ最適化問題に特化したソルバーである． ここでは，数理最適化や量子計算（無制約2次最適化）より制約最適化が有効になる例を示す．
数理最適化（無制約2次最適化）で組合せ最適化問題を定式化するには， $\{ 0,1 \}$ （もしくは $\{ -1,1 \}$） の領域をもつ変数を用いる必要がある． 一方，SCOPが採用している制約最適化では，任意の集合をとることができる． この差によってSCOPの方が有効になる場合がある．
以下では，最近コンサルティングをした案件を例として解説する．
$5000$人の従業員に$4000$のシフトを割り当てるスケジューリング問題を考える． この問題を数理（無制約2次）最適化で定式化すると， 従業員 $i$ にシフト$s$を割り当てる $2000$万個の変数 $x_{is}$ が必要になる． さらに$30$日分のシフトを作成しようとすると，既存のソルバーでは計算不能になる．
SCOPでは，従業員 $i$ に対して，シフトを領域とした $5000$個の変数 $X_i$ を準備する． $30$日分のシフトを考慮する際には，従業員 $i$ の日 $d$ に対するシフトを領域とした $15$万個の変数$X_{id}$ を用いれば良い． このように，問題に対して適切に「領域」を定義することによって，定式化したときの問題のサイズをコンパクトにすることができる．
また，この種のシフト最適化の実際問題に対しては，日にまたがるシフトに対する制約が付加されることが多い． たとえば，4日の連続勤務の後には，必ず2日連続で休暇を入れるというのが典型的な制約である． このような制約を数理最適化の制約領域が極度に退化した状態になり，本来なら多項式時間で計算可能な線形最適化でさえ膨大な時間がかかる．
SCOPはメタヒューリスティクスに基づくソルバーであるので，制約領域の構造に左右されることなく，現実的な時間で，現実的な解を算出することができるのである．
from scop import *
例題：仕事の割当1
あなたは，土木事務所の親方だ．いま，3人の作業員 A,B,C を3つの仕事 $0,1,2$ に割り当てる必要がある． すべての仕事には1人の作業員を割り当てる必要があるが， 作業員と仕事には相性があり，割り当てにかかる費用（単位は万円）は，以下のようになっているものとする．
| 仕事 | 0 | 1 | 2 |
| 作業員 | |||
| A | 15 | 20 | 30 |
| B | 7 | 15 | 12 |
| C | 25 | 10 | 13 |
総費用を最小にするように作業員に仕事を割り振るには，どのようにしたら良いだろうか？
この問題をSCOPを使って解いてみよう．
まず，モデルのインスタンスmodelを生成し，作業員 $A,B,C$ に割り振られた仕事を表す変数 $X_A, X_B, X_C$ （プログラムでは A,B,C）を定義する．
数理最適化においては変数は数字で表さなければならないが， 制約最適化では，変数のとれる値の集合で定義する．
これを 領域 (domain)とよぶ． 作業員は仕事 $0,1,2$ のいずれかの仕事をすることができるので，各変数の領域は[0,1,2]となる．
変数の追加は，モデルインスタンスmodelのaddVariableメソッドを用いる．
model = Model()
A = model.addVariable(name="A", domain=[0,1,2])
B = model.addVariable(name="B", domain=[0,1,2])
C = model.addVariable(name="C", domain=[0,1,2])
数理最適化でモデリングをすると $9=(3 \times 3)$ 個の0-1変数が必要になるが， SCOPだと3個の変数で表現できる．
すべての仕事に1人の作業員を割り当てることを表すには， 相異制約を使う．
- 相異制約 (Alldiff): リストに含まれる変数（すべて同じ領域をもつと仮定する）がすべて異なる値をとることを表す．
Alldiffクラスのインスタンスalldiffを生成し， それをmodelに追加する．
SCOPにおける制約は， すべて逸脱したときのペナルティをweight引数で定義する．weight引数に無限大を表すinfを入れると，絶対制約（ハードな制約）を定義できる．
alldiff = Alldiff("All Diff",[A,B,C],weight="inf")
model.addConstraint(alldiff)
これも数理最適化でモデリングすると，仕事ごとに定義する必要があるので 3本の制約が必要であるが， SCOPだと相異制約1本で表現できる．
SCOPには目的関数という概念がない．すべて制約で表現し， 制約の逸脱ペナルティの合計を最小化する． 割り当て費用は線形制約で記述する．
線形制約は線形不等式（もしくは等式）であり，式として記述する際には，値変数の概念を用いる． 値変数とは変数が領域の値をとったときに $1$ になる仮想の変数であり， 実際のプログラム内では使わない． 作業員 $A$ に割り当てられた仕事を表す変数 $X_A$ に対して，値変数 $x_{Aj} (j=0,1,2)$ が定義される． $x_{Aj}$ は， 作業員 $A$ が仕事 $j$ に割り当てられたときに $1$，それ以外のとき $0$ を表す変数である．
これを使うと割り当て費用を表す線形制約は，
$$ 15 x_{A0} + 20 x_{A1} + 30 x_{A2} + 7 x_{B0} + 15 x_{B1} + 12 x_{B2} + 25 x_{C0} + 10 x_{C1} + 13 x_{C2} \leq 0 $$と書ける． この制約の逸脱ペナルティweightを $1$ に設定すると，制約の逸脱を許す考慮制約（ソフトな制約）となり，逸脱量が割り当て費用になる．
線形制約クラスLinearの右辺定数rhsを $0$，制約の方向を<=と設定してインスタンスlinearを生成する．
左辺の各項は，addTermsメソッドを用いて追加する．引数は順に，係数のリスト，変数のリスト，値のリストである．
linear = Linear(name="Objective Function",weight=1,rhs=0,direction="<=")
linear.addTerms([15,20,30],[A,A,A],[0,1,2])
linear.addTerms([7,15,12],[B,B,B],[0,1,2])
linear.addTerms([25,10,13],[C,C,C],[0,1,2])
model.addConstraint(linear)
SCOPのインスタンスはprint関数で表示できる． ここでは上で作成したモデルインスタンスmodelを表示しておく．
modelのoptimizeメソッドで最適化を実行する．返値は解を表す辞書と逸脱した制約を表す辞書である．
print(model)
sol, violated = model.optimize()
print("solution=", sol)
print("violated constraint=", violated)
プログラム全体を以下に示す．
model = Model()
# 変数の宣言
A = model.addVariable(name="A", domain=[0, 1, 2])
B = model.addVariable(name="B", domain=[0, 1, 2])
C = model.addVariable(name="C", domain=[0, 1, 2])
# 相異制約
alldiff = Alldiff("All Diff", [A, B, C], weight="inf")
model.addConstraint(alldiff)
# 目的関数
linear = Linear(name="Objective Function", weight=1, rhs=0, direction="<=")
linear.addTerms([15, 20, 30], [A, A, A], [0, 1, 2])
linear.addTerms([7, 15, 12], [B, B, B], [0, 1, 2])
linear.addTerms([25, 10, 13], [C, C, C], [0, 1, 2])
model.addConstraint(linear)
print(model)
# 返値は解を表す辞書と逸脱を表す辞書
sol, violated = model.optimize()
print("solution=", sol)
print("violated constraint=", violated)
例題：仕事の割当2
あなたは土木事務所の親方だ．今度は，5人の作業員 $A,B,C,D,E$ を3つの仕事 $0,1,2$ に割り当てる必要がある． ただし，各仕事にかかる作業員の最低人数が与えられており，それぞれ $1,2,2$人必要であり， 割り当ての際の費用（単位は万円）は，以下のようになっているものとする．
| 仕事 | 0 | 1 | 2 |
| 作業員 | |||
| A | 15 | 20 | 30 |
| B | 7 | 15 | 12 |
| C | 25 | 10 | 13 |
| D | 15 | 18 | 3 |
| E | 5 | 12 | 17 |
さて，誰にどの仕事を割り振れば費用が最小になるだろうか？
例題1では変数をA,B,Cと別々に定義したが，ここではより一般的な記述法を示す．
パラメータは例題1と同じようにリストと辞書で準備する．
- $W$: 作業員の集合． その要素を $i$ とする．
- $J$: 仕事の集合． その要素を $j$ とする．
- $c_{ij}$: 作業員 $i$ が仕事 $j$ に割り当てられたときの費用
- $LB_j$: 仕事 $j$ に必要な人数
model=Model()
workers=["A","B","C","D","E"]
Jobs =[0,1,2]
Cost={ ("A",0):15, ("A",1):20, ("A",2):30,
("B",0): 7, ("B",1):15, ("B",2):12,
("C",0):25, ("C",1):10, ("C",2):13,
("D",0):15, ("D",1):18, ("D",2): 3,
("E",0): 5, ("E",1):12, ("E",2):17
}
LB={0: 1,
1: 2,
2: 2
}
変数は辞書xに保管する．
- $X_{i}$: 作業員 $i$ に割り振られた仕事を表す変数． 領域は仕事の集合 $J$ であり，そのうち1つの「値」を選択する．
x={}
for i in workers:
x[i]=model.addVariable(name=i,domain=Jobs)
$x_{ij}$ は， $X_i$ が $j$ に割り当てられたときに $1$，それ以外のとき $0$ を表す変数（値変数）であり，これを使うと人数の下限制約と割り当て費用は，以下の 線形制約として記述できる．
- 人数下限を表す線形制約（重み $\infty$） $$ \sum_{i \in W} x_{ij} \geq LB_j \ \ \ \forall j \in J $$
- 割り当て費用を表す線形制約（重み $1$） $$ \sum_{i \in W, j \in J} c_{ij} x_{ij} \leq 0 $$
LBC={}
for j in Jobs:
LBC[j]=Linear(f"LB{j}","inf",LB[j],">=")
for i in workers:
LBC[j].addTerms(1,x[i],j)
model.addConstraint(LBC[j])
obj=Linear("obj")
for i in workers:
for j in [0,1,2]:
obj.addTerms(Cost[i,j],x[i],j)
model.addConstraint(obj)
modelのパラメータParamsで制限時間TimeLimitを1（秒）に設定して最適化する．
プログラム全体を以下に示す．
model = Model()
workers = ["A", "B", "C", "D", "E"]
Jobs = [0, 1, 2]
Cost = {
("A", 0): 15,
("A", 1): 20,
("A", 2): 30,
("B", 0): 7,
("B", 1): 15,
("B", 2): 12,
("C", 0): 25,
("C", 1): 10,
("C", 2): 13,
("D", 0): 15,
("D", 1): 18,
("D", 2): 3,
("E", 0): 5,
("E", 1): 12,
("E", 2): 17,
}
LB = {0: 1, 1: 2, 2: 2}
x = {}
for i in workers:
x[i] = model.addVariable(name=i, domain=Jobs)
LBC = {}
for j in Jobs:
LBC[j] = Linear(f"LB{j}", "inf", LB[j], ">=")
for i in workers:
LBC[j].addTerms(1, x[i], j)
model.addConstraint(LBC[j])
obj = Linear("obj")
for i in workers:
for j in [0, 1, 2]:
obj.addTerms(Cost[i, j], x[i], j)
model.addConstraint(obj)
model.Params.TimeLimit = 1
sol, violated = model.optimize()
print("solution")
for x in sol:
print(x, sol[x])
print("violated constraint(s)")
for v in violated:
print(v, violated[v])
例題：仕事の割当3
上の例題と同じ状況で，仕事を割り振ろうとしたところ，作業員 $A$ と $C$ は仲が悪く， 一緒に仕事をさせると喧嘩を始めることが判明した． 作業員 $A$ と $C$ を同じ仕事に割り振らないようにするには，どうしたら良いだろうか？
この問題は，追加された作業員 $A$ と $C$ を同じ仕事に割り当てることを禁止する制約を記述するだけで解決できる． ここでは，2次制約（重みは $100$）として記述する．
$$ x_{A0} x_{C0} + x_{A1} x_{C1} + x_{A2} x_{C2} = 0 $$作業員AとCが同じ仕事に割り当てられると左辺は $1$になり，制約を逸脱する．
線形制約クラスと同様に2次制約クラスQuadraticからインスタンスconfを生成する．
左辺の項を追加するには，addTermsメソッドを用いる． 引数は，最初の変数の係数，変数，値の次に2番目の変数の係数，変数，値を入れる．
conf=Quadratic("conflict",100,0,"=")
for j in Jobs:
conf.addTerms(1,x["A"],j,x["C"],j)
model.addConstraint(conf)
数理最適化ソルバーは非凸の2次を含む制約や目的関数が苦手であるが，SCOPは通常の制約と同じように解くことができる．
model = Model()
workers = ["A", "B", "C", "D", "E"]
Jobs = [0, 1, 2]
Cost = {
("A", 0): 15,
("A", 1): 20,
("A", 2): 30,
("B", 0): 7,
("B", 1): 15,
("B", 2): 12,
("C", 0): 25,
("C", 1): 10,
("C", 2): 13,
("D", 0): 15,
("D", 1): 18,
("D", 2): 3,
("E", 0): 5,
("E", 1): 12,
("E", 2): 17,
}
LB = {0: 1, 1: 2, 2: 2}
x = {}
for i in workers:
x[i] = model.addVariable(i, Jobs)
LBC = {}
for j in Jobs:
LBC[j] = Linear(f"LB{j}", "inf", LB[j], ">=")
for i in workers:
LBC[j].addTerms(1, x[i], j)
model.addConstraint(LBC[j])
obj = Linear("obj", 1, 0, "<=")
for i in workers:
for j in Jobs:
obj.addTerms(Cost[i, j], x[i], j)
model.addConstraint(obj)
conf = Quadratic("conflict", 100, 0, "=")
for j in Jobs:
conf.addTerms(1, x["A"], j, x["C"], j)
model.addConstraint(conf)
model.Params.TimeLimit = 1
sol, violated = model.optimize()
print("solution")
for x in sol:
print(x, sol[x])
print("violated constraint(s)")
for v in violated:
print(v, violated[v])
例題：魔方陣
魔方陣とは， $n \times n$ のマス目に $1$ から $n^2$ までの数字を1つずつ入れて，どの横行，縦列，対角線のマス目の数字の和も同じになるようにしたものである.
$n=3$ の問題を以下の手順で問題を解く．
各マス目 $(i,j), i=0,1,2, j=0,1,2$ に対して変数 $x[i,j]$ を準備して，その領域を $1$ から $9$ までの数とする．
各マス目には異なる数字を入れる必要があるので，すべての変数のリストを入れた相異制約 (Alldiff) を追加する． この制約は絶対制約とする．
さらに，各行（$i=0,1,2$)と各列($j=0,1,2$)に対して，その和がちょうど $15 = (1+2+\cdots+9)/3$ になるという制約を追加する． これらの制約は考慮制約とし，逸脱の重みは $1$ とする．
最適化を行い，解を表示する．
行の集合を $I$， その要素を $i$ とする．
列の集合を $J$，その要素を $j$ とする．
$X_{ij}$: マス目 $i,j$ に割り当てられた数字を表す変数； 領域は $[1,2,3,4,5,6,7,8,9]$ であり，そのうち1つの「値」を選択する．
$x_{ijk}$: $X_{ij}$ が $k$ に割り当てられたときに $1$，それ以外のとき $0$ を表す変数（値変数）
相異制約（重み $\infty$）； すべてのマス目の数字が異なることを表す．
$$ \mathrm{Alldiff} ~( X_{ij}, \ \ \ \forall i \in I, \forall j \in J ) $$線形制約（重み $1$）；行ごとの和が $15$ であることを表す． $$ \sum_{j \in J} \sum_{k} k x_{ijk} = 15 \ \ \ \forall i \in I $$
線形制約（重み $1$）；列ごとの和が $15$ であることを表す． $$ \sum_{i \in I} \sum_{k} k x_{ijk} = 15 \ \ \ \forall j \in J $$
線形制約（重み $1$）；対角線ごとの和が $15$ であることを表す． $$ \sum_{j \in J} \sum_{k} k x_{jjk} = 15 $$
$$ \sum_{j \in J} \sum_{k} k x_{j,2-j,k} = 15 $$以下に一般の $n$ でも解けるプログラムを示す． ただしトライアル版だと $n=3$ までしか解くことができない．
n = 3
nn = n * n
model = Model()
x = {}
dom = [i + 1 for i in range(nn)]
sum_ = sum(dom) // n
for i in range(n):
for j in range(n):
x[i, j] = model.addVariable(name=f"x[{i},{j}]", domain=dom)
alldiff = Alldiff(f"AD", [x[i, j] for i in range(n) for j in range(n)], weight="inf")
model.addConstraint(alldiff)
col_constr = {}
for j in range(n):
col_constr[j] = Linear(f"col_constraint{j}", weight=1, rhs=sum_, direction="=")
for i in range(n):
for k in range(1, nn + 1):
col_constr[j].addTerms(k, x[i, j], k)
model.addConstraint(col_constr[j])
row_constr = {}
for i in range(n):
row_constr[i] = Linear(f"row_constraint{i}", weight=1, rhs=sum_, direction="=")
for j in range(n):
for k in range(1, nn + 1):
row_constr[i].addTerms(k, x[i, j], k)
model.addConstraint(row_constr[i])
diagonal_constr = {}
diagonal_constr[0] = Linear(
f"diagonal_constraint{0}", weight=1, rhs=sum_, direction="="
)
for j in range(n):
for k in range(1, nn + 1):
diagonal_constr[0].addTerms(k, x[j, j], k)
model.addConstraint(diagonal_constr[0])
diagonal_constr[1] = Linear(
f"diagonal_constraint{1}", weight=1, rhs=sum_, direction="="
)
for j in range(n):
for k in range(1, nn + 1):
diagonal_constr[1].addTerms(k, x[j, n - 1 - j], k)
model.addConstraint(diagonal_constr[1])
model.Params.TimeLimit = 100
model.Params.RandomSeed = 1
sol, violated = model.optimize()
print("逸脱制約=", violated)
import numpy as np
solution = np.zeros((n, n), int)
for i in range(n):
for j in range(n):
solution[i, j] = int(x[i, j].value)
print(solution)
問題 多制約ナップサック
あなたは，ぬいぐるみ専門の泥棒だ． ある晩，あなたは高級ぬいぐるみ店にこっそり忍び込んで，盗む物を選んでいる． 狙いはもちろん，マニアの間で高額で取り引きされているクマさん人形だ． クマさん人形は，現在 $4$体販売されていて， それらの値段と重さと容積は，以下のリストで与えられている．
v=[16,19,23,28] #価値
a=[[2,3,4,5],[3000,3500,5100,7200]] #重さと容積
あなたは，転売価格の合計が最大になるようにクマさん人形を選んで逃げようと思っているが， あなたが逃走用に愛用しているナップサックはとても古く， $7$kgより重い荷物を入れると，底がぬけてしまうし，$10000 {cm}^3$（$10$$\ell$）を超えた荷物を入れると破けてしまう．
さて，どのクマさん人形をもって逃げれば良いだろうか？
問題 巡回セールスマン
あなたは休暇を利用してヨーロッパめぐりをしようと考えている． 現在スイスのチューリッヒに宿を構えているあなたの目的は， スペインのマドリッドで闘牛を見ること， イギリスのロンドンでビックベンを見物すること， イタリアのローマでコロシアムを見ること， ドイツのベルリンで本場のビールを飲むことである．
あなたはレンタルヘリコプターを借りてまわることにしたが， 移動距離に比例した高額なレンタル料を支払わなければならない． したがって， あなたはチューリッヒ (T) を出発した後， なるべく短い距離で他の $4$つの都市 マドリッド(M)，ロンドン(L)，ローマ(R)，ベルリン(B) を経由し， 再びチューリッヒに帰って来ようと考えた． 都市の間の移動距離を測ってみたところ，以下のようになっていることがわかった．
cities=["T","L","M","R","B"]
d=[[0,476,774,434,408],
[476,0,784,894,569],
[774,784,0,852,1154],
[434,894,852,0,569],
[408,569,1154,569,0]]
さて，どのような順序で旅行すれば，移動距離が最小になるだろうか?
問題 ビンパッキング
あなたは，大企業の箱詰め担当部長だ．あなたの仕事は，色々な大きさのものを，決められた大きさの箱に「上手に」詰めることである． この際，使う箱の数をなるべく少なくすることが，あなたの目標だ． （なぜって，あなたの会社が利用している宅配業者では，運賃は箱の数に比例して決められるから．） 1つの箱に詰められる荷物の上限は $7$ kgと決まっており，荷物の重さはのリストは [6,5,4,3,1,2] である． しかも，あなたの会社で扱っている荷物は，どれも重たいものばかりなので，容積は気にする必要はない （すなわち箱の容量は十分と仮定する）． さて，どのように詰めて運んだら良いだろうか？
問題 車の投入順決定
コンベア上に一直線に並んだ車の生産ラインを考える． このラインは，幾つかの作業場から構成され，それぞれの作業場では異なる作業が行われる． いま，4種類の車を同じ生産ラインで製造しており，それぞれをモデル $A,B,C,D$ とする． 本日の製造目標は，それぞれ $30,30,20,40$台である．
最初の作業場では，サンルーフの取り付けを行っており，これはモデル $B,C$ だけに必要な作業である． 次の作業場では，カーナビの取り付けが行われており，これはモデル $A,C$ だけに必要な作業である． それぞれの作業場は長さをもち， サンルーフ取り付けは車 $5$台分，カーナビ取り付けは車 $3$台分の長さをもつ． また，作業場には作業員が割り当てられており，サンルーフ取り付けは $3$人，カーナビ取り付けは $2$人の 作業員が配置されており，作業場の長さを超えない範囲で別々に作業を行う．
作業場の範囲で作業が可能な車の投入順序を求めよ．
（ヒント： 投入順序をうまく決めないと，作業場の範囲内で作業を完了することができない． たとえば，$C,A,A,B,C$ の順で投入すると， サンルーフ取り付けでは，3人の作業員がそれぞれモデル $C,B,C$ に対する作業を行うので 間に合うが，カーナビ取り付けでは， 2人の作業員では $C,A,A$ の3台の車の作業を終えることができない）
これは，作業場の容量制約とよばれ，サンルーフ取り付けの作業場では， すべての連続する $5$台の車の中に，モデル $B,C$ が高々 $3$つ， カーナビ取り付けの作業場では， すべての連続する $3$台の車の中に，モデル $A,C$ が高々 $2$つ入っているという制約を課すことに相当する
問題 段取り費用付き生産計画
１つの生産ラインでa,bの２種類の製品を生産している．各期に生産できる製品は1つであり，生産はバッチで行われるため生産量は決まっている（辞書S）． 5期の需要量（辞書D）を満たすように，生産計画（どの期にどの製品を生産するか）を作りたいのだが，製品の切り替えには段取り費用（辞書F）がかかる． ただし，生産しないことを表すダミーの製品０があるものと仮定し，直前の期では何も生産していなかったものと仮定する． 生産すると生産量だけ在庫が増え，毎期需要分だけ在庫が減少する． 初期在庫（辞書I0）を与えたとき，各期の在庫量が上限（辞書UB）以下，下限（辞書LB)以上でなければいけないとしたとき，段取り費用の合計を最小にする生産計画をたてよ．
S={"0":0,"a":30,"b":50} #S[P,T]：単位生産量
UB={"0":0,"a":50,"b":50} #UB[p,t]：在庫量の上限
LB={"0":0,"a":10,"b":10} #LB[p]：在庫量の下限
I0={"0":0,"a":10,"b":30} #I0[p]:初期在庫
#D[p,t]：需要量
D={("0",1):0,("0",2):0,("0",3):0,("0",4):0,("0",5):0,
("a",1):10,("a",2):10,("a",3):30,("a",4):10,("a",5):10,
("b",1):20,("b",2):10,("b",3):20,("b",4):10,("b",5):10}
#F[p,q]: 製品p,q間の段取り費用
F={("0","a"):10,("0","b"):10,
("a","0"):10,("a","b"):30,
("b","0"):10,("b","a"):10}