Линейное программирование двух наборов ограничений CPLEX Python API

Question

Я пытаюсь решить задачу линейного программирования, используя API CPLEX Python от IBM. Он включает в себя два набора ограничений равенства. Приведенный ниже код прекрасно работает, когда мы используем один из двух наборов ограничений, но не может найти решение, когда используются оба набора ограничений.

Ограничения: Первое ограничение: Wx' = c', где W = [[20,0,0],[0,20,30]], x = [a,b,c], c=[20,30] Второе ограничение: Vx' = e', где V = [[1,1,0],[0,0,1]], x = [a,b,c], c=[1,1]

Функция цели: minimize a + c

Одно решение, которое удовлетворяет обоим наборам ограничений: a=1, b=0, c=1.

Ошибка в введении двух наборов ограничений в Cplex Python. Мой код ниже. Чтобы убедиться, что код работает с любым набором ограничений, закомментируйте наборы ограничений.

import cplex
from cplex.exceptions import CplexError
import sys



def populatebynonzero(prob):


    my_obj      = [1.0, 0.0, 1.0]
    my_ub       = [1.0] * len(my_obj)
    my_lb       = [0.0] * len(my_obj)
    my_colnames = ["a", "b", "c"]

    prob.objective.set_sense(prob.objective.sense.minimize)
    prob.variables.add(obj = my_obj, ub = my_ub, lb = my_lb ,names = my_colnames)

    # first set of equality constraints: Wx' = c', where W = [[20,0,0],[0,20,30]], x = [a,b,c], c=[20,30]
    my_rhs      = [20.0, 30.0]
    my_rownames = ["c1", "c2"]
    my_sense    = "E" * len(my_rownames)
    rows = [0,1,1] 
    cols = [0,1,2]
    vals = [20.0,20.0,30.0]
    prob.linear_constraints.add(rhs = my_rhs, senses = my_sense,names = my_rownames)
    prob.linear_constraints.set_coefficients(zip(rows, cols, vals))     

    # second set of equality constraints: Vx' = e', where V = [[1,1,0],[0,0,1]], x = [a,b,c], c=[1,1]

    my_rhs      = [1.0, 1.0]
    my_rownames = ["e1", "e2"]
    my_sense    = "E" * len(my_rownames)
    rows = [0,0,1] 
    cols = [0,1,2]
    vals = [1.0,1.0,1.0]
    prob.linear_constraints.add(rhs = my_rhs, senses = my_sense,names = my_rownames)
    prob.linear_constraints.set_coefficients(zip(rows, cols, vals))



def lpex1():
    try:
        my_prob = cplex.Cplex()
        handle = populatebynonzero(my_prob)
        my_prob.solve()
    except CplexError, exc:
        print exc
        return

    numrows = my_prob.linear_constraints.get_num()
    numcols = my_prob.variables.get_num()

    print
    # solution.get_status() returns an integer code
    print "Solution status = " , my_prob.solution.get_status(), ":",
    # the following line prints the corresponding string
    print my_prob.solution.status[my_prob.solution.get_status()]
    print "Solution value  = ", my_prob.solution.get_objective_value()
    slack = my_prob.solution.get_linear_slacks()
    pi    = my_prob.solution.get_dual_values()
    x     = my_prob.solution.get_values()
    dj    = my_prob.solution.get_reduced_costs()
    for i in range(numrows):
        print "Row %d:  Slack = %10f  Pi = %10f" % (i, slack[i], pi[i])
    for j in range(numcols):
        print "Column %d:  Value = %10f Reduced cost = %10f" % (j, x[j], dj[j])

    my_prob.write("lpex1.lp")




    print x, "SOLUTIONS"

lpex1()

Answer 1

Когда вы пытаетесь создать второй набор ограничений, вы используете неправильные индексы для строк:

# second set of equality constraints: Vx' = e', where V = [[1,1,0],[0,0,1]], x = [a,b,c], c=[1,1]

my_rhs      = [1.0, 1.0]
my_rownames = ["e1", "e2"]
my_sense    = "E" * len(my_rownames)
rows = [0,0,1]  # <- HERE
cols = [0,1,2]
vals = [1.0,1.0,1.0]

То есть вы используете индексы строк 0 и 1, которые были созданы для первого набора ограничений. Вместо этого вы должны сделать что-то вроде следующего:

# second set of equality constraints: Vx' = e', where V = [[1,1,0],[0,0,1]], x = [a,b,c], c=[1,1]

my_rhs      = [1.0, 1.0]
my_rownames = ["e1", "e2"]
my_sense    = "E" * len(my_rownames)
cols = [0,1,2]
vals = [1.0,1.0,1.0]
rowindices = list(prob.linear_constraints.add(rhs = my_rhs, senses = my_sense,names = my_rownames))
assert len(rowindices) == 2
rows = [rowindices[0], rowindices[0], rowindices[1]]
prob.linear_constraints.set_coefficients(zip(rowindices, cols, vals))

Выше мы получаем новые индексы строк из вызова prob.linear_constriants.add . С этим изменением скрипт работает нормально.

Кроме того, неплохо было бы выписать проблему в формате LP, чтобы убедиться, что она выглядит правильно, например:

prob.write("model.lp")

Answer 2

Это работает, если два набора ограничений объединяются в одну матрицу следующим образом, хотя было бы хорошо найти решение, которое не должно объединять

import cplex
from cplex.exceptions import CplexError
import sys



def populatebynonzero(prob):


    my_obj      = [1.0, 0.0, 1.0]
    my_ub       = [1.0] * len(my_obj)
    my_lb       = [0.0] * len(my_obj)
    my_colnames = ["a", "b", "c"]

    prob.objective.set_sense(prob.objective.sense.minimize)
    prob.variables.add(obj = my_obj, ub = my_ub, lb = my_lb ,names = my_colnames)

    #combined constraints
    my_rhs      = [20.0, 30.0, 1.0, 1.0]
    my_rownames = ["c1", "c2", "e1", "e2"]
    my_sense    = "E" * len(my_rownames)
    rows = [0,1,1,2,2,3] 
    cols = [0,1,2,0,1,2]
    vals = [20.0,20.0,30.0,1,1,1]
    prob.linear_constraints.add(rhs = my_rhs, senses = my_sense,names = my_rownames)
    prob.linear_constraints.set_coefficients(zip(rows, cols, vals))     


    """

    # first set of equality constraints: Wx' = c', where W = [[20,0,0],[0,20,30]], x = [a,b,c], c=[20,30]
    my_rhs      = [20.0, 30.0]
    my_rownames = ["c1", "c2"]
    my_sense    = "E" * len(my_rownames)
    rows = [0,1,1] 
    cols = [0,1,2]
    vals = [20.0,20.0,30.0]
    prob.linear_constraints.add(rhs = my_rhs, senses = my_sense,names = my_rownames)
    prob.linear_constraints.set_coefficients(zip(rows, cols, vals))     

    # second set of equality constraints: Vx' = e', where V = [[1,1,0],[0,0,1]], x = [a,b,c], c=[1,1]

    my_rhs      = [1.0, 1.0]
    my_rownames = ["e1", "e2"]
    my_sense    = "E" * len(my_rownames)
    rows = [0,0,1] 
    cols = [0,1,2]
    vals = [1.0,1.0,1.0]
    prob.linear_constraints.add(rhs = my_rhs, senses = my_sense,names = my_rownames)
    prob.linear_constraints.set_coefficients(zip(rows, cols, vals))
    """


def lpex1():
    try:
        my_prob = cplex.Cplex()
        handle = populatebynonzero(my_prob)
        my_prob.solve()
    except CplexError, exc:
        print exc
        return

    numrows = my_prob.linear_constraints.get_num()
    numcols = my_prob.variables.get_num()

    print
    # solution.get_status() returns an integer code
    print "Solution status = " , my_prob.solution.get_status(), ":",
    # the following line prints the corresponding string
    print my_prob.solution.status[my_prob.solution.get_status()]
    print "Solution value  = ", my_prob.solution.get_objective_value()
    slack = my_prob.solution.get_linear_slacks()
    pi    = my_prob.solution.get_dual_values()
    x     = my_prob.solution.get_values()
    dj    = my_prob.solution.get_reduced_costs()
    for i in range(numrows):
        print "Row %d:  Slack = %10f  Pi = %10f" % (i, slack[i], pi[i])
    for j in range(numcols):
        print "Column %d:  Value = %10f Reduced cost = %10f" % (j, x[j], dj[j])

    my_prob.write("lpex1.lp")




    print x, "SOLUTIONS"

lpex1()