线性规划两组约束 CPLEX Python API

Question

我正在尝试使用IBM的CPLEX Python API解决线性规划问题。它涉及两组相等约束。当我们使用两组约束中的任何一组时，下面的代码工作正常，但是当使用两组约束时，无法找到解决方案。

约束条件包括： 第一个约束：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

如果以以下方式将两组约束组合成一个矩阵，则它有效，尽管最好找到一个不必组合

的解决方案

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()

Answer 2

当您尝试创建第二组约束时，您对行使用了错误的索引：

# 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")