サブロウ丸

Sabrou-mal サブロウ丸

主にプログラミングと数学

【Python】PuLP; 多段階最適化

まだ PuLPのdocumentに載っていない(執筆時)関数ですが sequentialSolveという多段階最適化を行う関数が実装されています

import pulp
from pulp import LpVariable

# 問題の宣言
problem = pulp.LpProblem()

# 変数の宣言(連続変数, 上限2)
x = LpVariable('x', upBound=2, cat='Continuous')
y = LpVariable('y', upBound=2, cat='Continuous')
z = LpVariable('z', upBound=2, cat='Continuous')

# 制約の追加
problem.addConstraint(x + y + z >= 3)

# 多段階最適化(obj1→obj2)
# つまり出てきた解x*はobj1をf1, obj2をf2とすると
# f1(x*) ≤ f1(x) (for all x in feasible solution)
# f2(x*) ≤ f2(x) (for all x in feasible solution such that f1(x) = f1(x*))
# を満たしている
obj1 = x + y
obj2 = y + z
problem.sequentialSolve(objectives=[obj1, obj2])

# 最適解を表示
for v in [x, y, z]:
    print(f'{v.name}={v.value()}')

> x=2.0
> y=-1.0
> z=2.0



documentに載っていないのは, まだ開発中だからのようです.
心配な方は下記の関数を参考に自分で処理を書くとよいでしょう.

中身の処理は単純で, まず第一目的関数で問題を解き目的関数値O1を取得したら, 次は, その目的関数をO1以下とする制約を追加して, 第二目的関数で問題を解きます. その後はこれの繰り返しです. なのでobjectivesの長さ(=目的関数の個数)の回数だけ問題の生成とソルバによる求解が行われます.

ソースコードは: https://github.com/coin-or/pulp/blob/68c70ec33a03e0fadeab50d69b0da106edaa345f/pulp/pulp.py から

    def sequentialSolve(self, objectives, absoluteTols = None,
                        relativeTols = None, solver = None, debug = False):
        """
        Solve the given Lp problem with several objective functions.

        This function sequentially changes the objective of the problem
        and then adds the objective function as a constraint

        :param objectives: the list of objectives to be used to solve the problem
        :param absoluteTols: the list of absolute tolerances to be applied to
           the constraints should be +ve for a minimise objective
        :param relativeTols: the list of relative tolerances applied to the constraints
        :param solver: the specific solver to be used, defaults to the default solver.

        """
        #TODO Add a penalty variable to make problems elastic
        #TODO add the ability to accept different status values i.e. infeasible etc

        if not(solver): solver = self.solver
        if not(solver): solver = LpSolverDefault
        if not(absoluteTols):
            absoluteTols = [0] * len(objectives)
        if not(relativeTols):
            relativeTols  = [1] * len(objectives)
        #time it
        self.solutionTime = -clock()
        statuses = []
        for i,(obj,absol,rel) in enumerate(zip(objectives,
                                               absoluteTols, relativeTols)):
            self.setObjective(obj)
            status = solver.actualSolve(self)
            statuses.append(status)
            if debug: self.writeLP("%sSequence.lp"%i)
            if self.sense == LpMinimize:
                self += obj <= value(obj)*rel + absol,"%s_Sequence_Objective"%i
            elif self.sense == LpMaximize:
                self += obj >= value(obj)*rel + absol,"%s_Sequence_Objective"%i
        self.solutionTime += clock()
        self.solver = solver
        return statuses