Оптимизация с PuLP: не могу работать с постоянной матрицей. В чем проблема? - PullRequest
Новая
       40

Оптимизация с PuLP: не могу работать с постоянной матрицей. В чем проблема?

0 голосов
/ 08 октября 2019

Я пытаюсь реализовать модель оптимизации с использованием инфраструктуры PuLP в Python. Псевдокод проблемы: Алгоритм псевдокода

И проблема оптимизации: IP - проблема

Первое, с чем я борюсь, этоинициализация C с использованием k-средних кластеров. Поскольку M является целочисленной матрицей, я не понимаю, зачем использовать k-средства для инициализации C, а не F, поэтому я решил сначала инициализировать F и переключить оптимизации.

Моя проблема: если я поставлюФактически оптимизированная матрица C (соответственно F) для модели оптимизации всегда имеет некоторые проблемы с умножением целочисленных (или плавающих) значений и значений NoneType. Я попробовал так много формулировок, которые нашел, было много разных формулировок этих моделей оптимизации PuLP. Теперь у меня есть 2 метода, 1 для оптимизации матрицы F и другой для оптимизации матрицы C. 

def optimize_matrix_F(self, M, C, k, a):
    prob = LpProblem("optimize_F")

    # Matrix M has length of m x n
    n = len(M)
    m = len(M[0])
    I = range(n)
    J = range(m)
    T = range(k) # k is the number of columns in C/rows in F

    # Adding the variables
    B = {(i, j, t): LpVariable(cat=LpBinary, name="B_{0}_{1}_{2}".format(i, j, t))
         for i in I for j in J for t in T}
    F = {(t, j): LpVariable(cat=LpInteger, lowBound=0, upBound=n, name="F_{0}_{1}".format(t, j))
         for t in T for j in J}
    R = {(i, j): LpVariable(cat=LpInteger, lowBound=0, upBound=n, name="R_{0}_{1}".format(i, j))
         for i in I for j in J}
    A = {(i, j): LpVariable(cat=LpBinary, name="A_{0}_{1}".format(i, j))
         for i in I for j in J}
    Y = {(i, j): LpVariable(cat=LpInteger, lowBound=0, upBound=n, name="Y_{0}_{1}".format(i, j))
         for i in I for j in J}

    # Adding the constraints

    for i in I:
        for j in J:
            for t in T:
                prob += LpConstraint(e=(C[i][t] * F[t][j]), sense=LpConstraintLE, rhs=R[i][j])

    for i in I:
        for j in J:
            for t in T:
                prob += LpConstraint(e=(C[i][t] * F[t][j] + (1 - B[i][j][t])), sense=LpConstraintGE, rhs=R[i][j])

    for i in I:
        for j in J:
            for t in T:
                prob += LpConstraint(e=lpSum(B[i][j][t]), sense=LpConstraintEQ, rhs=1)

    for i in I:
        for j in J:
            prob += LpConstraint(e=n*A[i][j], sense=LpConstraintGE, rhs=R[i][j])

    for i in I:
        for j in J:
            prob += LpConstraint(e=A[i][j], sense=LpConstraintLE, rhs=R[i][j])

    for i in I:
        for j in J:
            prob += LpConstraint(e=(M[i][j]*A[i][j] - R[i][j]), sense=LpConstraintLE, rhs=Y[i][j])

    for i in I:
        for j in J:
            prob += LpConstraint(e=((-M[i][j]) * A[i][j] + R[i][j]), sense=LpConstraintLE, rhs=Y[i][j])


    # The objective function
    obj = (lpSum((a*A[i][j] - Y[i][j]) for i in I for j in J))
    prob += obj

    prob.sense = LpMaximize
    prob.setObjective(obj)
    prob.solve()

    # Converting the dict objects to np arrays
    F_res = np.array([[F[t][j].varValue for j in J] for t in T])
    R_res = np.array([[R[i][j].varValue for j in J] for i in I])
    A_res = np.array([[A[i][j].varValue for j in J] for i in I])

    return F_res, R_res, A_res

def optimize_matrix_C(self, M, F, k, a):

    prob = LpProblem("optimize_C")
    # Matrix M has length of m x n
    n = len(M)
    m = len(M[0])
    I = range(n)
    J = range(m)
    T = range(k) # k is the number of columns in C/rows in F

    # Adding the variables
    B = {(i, j, t): LpVariable(cat=LpBinary, name="B_{0}_{1}_{2}".format(i, j, t))
         for i in I for j in J for t in T}
    C = {(i, t): LpVariable(cat=LpBinary, name="C_{0}_{1}".format(i, t))
         for i in I for t in T}
    R = {(i, j): LpVariable(cat=LpInteger, lowBound=0, upBound=n, name="R_{0}_{1}".format(i, j))
         for i in I for j in J}
    A = {(i, j): LpVariable(cat=LpBinary, name="A_{0}_{1}".format(i, j))
         for i in I for j in J}
    Y = {(i, j): LpVariable(cat=LpInteger, lowBound=0, upBound=n, name="Y_{0}_{1}".format(i, j))
         for i in I for j in J}

    # Adding the constraints
    for i in I:
        for j in J:
            for t in T:
                prob += LpConstraint(e=(C[i][t] * F[t][j]), sense=LpConstraintLE, rhs=R[i][j])

    for i in I:
        for j in J:
            for t in T:
                prob += LpConstraint(e=(C[i][t] * F[t][j] + (1 - B[i][j][t])), sense=LpConstraintGE, rhs=R[i][j])

    for i in I:
        for j in J:
            for t in T:
                prob += LpConstraint(e=lpSum(B[i][j][t]), sense=LpConstraintEQ, rhs=1)

    for i in I:
        for j in J:
            prob += LpConstraint(e=n * A[i][j], sense=LpConstraintGE, rhs=R[i][j])

    for i in I:
        for j in J:
            prob += LpConstraint(e=A[i][j], sense=LpConstraintLE, rhs=R[i][j])

    for i in I:
        for j in J:
            prob += LpConstraint(e=(M[i][j] * A[i][j] - R[i][j]), sense=LpConstraintLE, rhs=Y[i][j])

    for i in I:
        for j in J:
            prob += LpConstraint(e=((-M[i][j]) * A[i][j] + R[i][j]), sense=LpConstraintLE, rhs=Y[i][j])

    # The objective function
    obj = (lpSum((a * A[i][j] - Y[i][j]) for i in I for j in J))
    prob += obj

    prob.sense = LpMaximize
    prob.setObjective(obj)
    prob.solve()

    # Converting the dict objects to np arrays
    C_res = np.array([[C[i][t].varValue for t in T] for i in I])
    R_res = np.array([[R[i][j].varValue for j in J] for i in I])
    A_res = np.array([[A[i][j].varValue for j in J] for i in I])

    return C_res, R_res, A_res

Итак, в данный момент я получаю KeyError: 0 в строке: 

prob += LpConstraint(e=(C[i][t] * F[t][j]), sense=LpConstraintLE, rhs=R[i][j])

Не могли бы вы помочь мне, что я делаю не так, или что делать, чтобы я мог каким-то образом получить результат этих функций? Нужно ли как-то инициализировать неизвестную матрицу / матрицы?

Спасибо!

PS: Я получил этот тип форматирования с этой страницы: https://medium.com/opex-analytics/optimization-modeling-in-python-pulp-gurobi-and-cplex-83a62129807a

...