Python PuLP では、線形計画法の制約を弾性部分問題に変えることができます。
http://www.coin-or.org/PuLP/pulp.html?highlight=lpsum#elastic-constraints
部分問題を解くと、目標値からの距離が最適化されます。
もちろん、ターゲット値はこのサブ問題に対する最適なソリューションですが、弾性化の全体的なポイントは、このソリューションが実行不可能である可能性があると考えていることです。
サブ問題を全体の問題にどのように組み込むことができますか? 制約を追加する方法で問題に追加しようとしましたが、これにより型エラーがスローされました。目的関数に入れてみましたが、これもうまくいきませんでした。
上記のドキュメントまたはここでホストされている例には何も見つかりません。
https://code.google.com/p/pulp-or/wiki/OptimisationWithPuLP?tm=6
これが私が定式化した副問題です:
capacity = LpConstraint(e=lpSum([ x[m][n] * len(n.items) for n in N ]),
sense=-1, rhs=30, name=str(random.random()))
stretch_proportion = 30/50
elasticCapacity = capacity.makeElasticSubProblem(penalty=50,
proportionFreeBoundList=[1,stretch_proportion])
LP目標に組み込む必要があると私が考える最も近いものは次のとおりです。
def sub(m):
capacity = LpConstraint(e=lpSum([ x[m][n] * len(n.items) for n in N ]),
sense=-1, rhs=30, name=str(random.random()))
stretch_proportion = 30/50
elasticCapacity = capacity.makeElasticSubProblem(penalty=50,
proportionFreeBoundList=[1,stretch_proportion])
elasticCapacity.solve()
return elasticCapacity.isViolated()
...
prob += lpSum( [ x[m][n] * reduce(op.add, map(D2, [i.l for i in n.items], [j.l for j in n.items]))\
for n in N for m in M ] ) + 50 * sub(m)