线性规划 - Google ortools - 不正确的决策变量最终值
Linear Programming - Google ortools - incorrect decision variable final values
我正在尝试解决线性规划问题。以下是问题的规格：
我有一个已转换为线性规划问题的网络流问题。因此，必须强制执行所有流量约束，例如容量、流量守恒等。我的objective是为了最小化成本。
决策变量 - 我通过定义一个字典并在这 128 个位置的每个位置添加决策变量来构建两个 8x8 矩阵。
约束——总共有24个约束，即：
1）流量从源头开始。两个 8x8 矩阵的 2 个约束。
2）流程在汇点结束。两个 8x8 矩阵的 2 个约束。
3) 流量守恒有 12 个约束条件，两个矩阵各有 8 个约束条件。
4) 有 2 个约束来遵守容量约束，每个矩阵 1 个。
5) 有6条约束可以避免重复
所有变量都必须是二进制的。
Objective - 那些8x8矩阵中有一些变量的总和需要最小化。
同样，所有变量都必须是二进制的。
我已经能够在 Google ORTOOLS 中编写解决方案并且解决方案收敛并显示最小值。但是，当我查看变量时，有些变量具有非二进制值。另外，解决方案是错误的（我在 excel 中有一个现有的解决方案 运行，它是正确的并且不同）。
如果有人能指出正确的方向，我将不胜感激。下面是写在Python36.
中的代码
from ortools.linear_solver import pywraplp
import numpy as np
def configure_constraints(cfg, solver, variable_list):
print(cfg)
dest_convs = cfg['dest_convs']
msize = cfg['lookback_win'] + 1 + 1
rem_capacity = cfg['rem_caps']
# Constraint 1 - Flow starts at the source
for i in range(dest_convs):
# print([(i, 0, c) for c in range(1, msize)])
solver.Add(solver.Sum([variable_list[(i,0,c)] for c in range(1, msize)]) == 1)
# Constraint 2 - Flow ends at the sink
for i in range(dest_convs):
# print([(i, r, msize - 1) for r in range(1, msize)])
solver.Add(solver.Sum([variable_list[(i,r,msize - 1)] for r in range(1, msize)]) == 1)
# Constraint 3 - Flow Conservation
for i in range(dest_convs):
for r in range(msize - 1):
if r+1 == msize - 1:
continue
solver.Add(solver.Sum([variable_list[(i,rind, r+1)] for rind in range(r + 1)]) - solver.Sum([variable_list[(i,r+1, cind + 1)] for cind in range(r+1, msize - 1)]) == 0)
#
# # Constraint 4 - Capacity Constraint
for i in range(dest_convs):
solver.Add(solver.Sum([variable_list[(i, r, c)] for r in range(1, msize-1) for c in range(r+1, msize - 1)]) <= rem_capacity[i] - 1)
#
# # Constraint 5 - 1-vehicle, 1-conveyor
dest_conv_list = []
for i in range(dest_convs):
dest_conv_list.append([])
for r in range(1, msize - 1):
dest_conv_list[i].append(sum([variable_list[(i,r,c)] for c in range(r+1, msize)]))
for items in zip(*dest_conv_list):
solver.Add(solver.Sum(items) == 1)
def configure_objective(solver, variable_list, cost_vars):
# Objective
solver.Minimize(solver.Sum([variable_list[items] for items in zip(*np.where(cost_vars))]))
def solve(solver):
result_status = solver.Solve()
return result_status
def configure_variables(cfg, solver):
# identify variables for the objective function
# print(cfg)
nvehs = cfg['vehicles']
dest_convs = cfg['dest_convs']
color_vec = cfg['color_vec']
cur_cars = cfg['cur_cars']
msize = cfg['lookback_win'] + 1 + 1
# objective_mat = np.zeros((msize, msize), dtype="int32")
mat = [[[0] * msize for i in range(msize)] for j in range(dest_convs)]
# source to vehicles
for i in range(dest_convs):
for j in range(nvehs):
# print(color_vec[j], cur_cars[i])
if color_vec[j] != cur_cars[i]:
mat[i][0][j+1] = 1
for h in range(dest_convs):
for i in range(0, nvehs):
for j in range(i+1, nvehs):
# print(i+1,j+1)
# print(color_vec[i+1], color_vec[j])
if color_vec[i] != color_vec[j]:
mat[h][i+1][j + 1] = 1
cost_vars = np.array(mat).reshape(dest_convs, msize, msize)
print(np.array(mat).reshape(dest_convs,msize,msize))
dvars = {}
for i in range(dest_convs):
for j in range(msize):
for k in range(msize):
dvars[i, j, k] = solver.BoolVar('x[%i,%i, %i]' % (i, j, k))
return dvars, cost_vars
def main(cfg, what):
solver = pywraplp.Solver('SolveSimpleSystem', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
dvars_list, cost_vars = configure_variables(cfg, solver)
configure_constraints(cfg, solver, dvars_list)
configure_objective(solver, dvars_list, cost_vars)
result_status = solve(solver)
print('Number of Variables:', solver.NumVariables())
print('Number of Constraints:', solver.NumConstraints())
# print('Constraints:', solver.)
if result_status == solver.OPTIMAL:
print('Solution Found.')
# The problem has an optimal solution.
print(('Problem solved in %f milliseconds' % solver.wall_time()))
# The objective value of the solution.
print(('Optimal objective value = %f' % solver.Objective().Value()))
var_sum = 0
for variable in dvars_list:
print(('%s = %f' % (dvars_list[variable].name(), dvars_list[variable].solution_value())))
var_sum += dvars_list[variable].solution_value()
print(('Variable sum = %f' % var_sum))
# The value of each variable in the solution.
elif result_status == solver.INFEASIBLE:
print('No solution found.')
elif result_status == solver.POSSIBLE_OVERFLOW:
print('Some inputs are too large and may cause an integer overflow.')
if __name__ == '__main__':
cfg = {'vehicles': 6,
'dest_convs': 2,
'cur_cars':['B', 'R'],
'rem_caps': [3,3],
'lookback_win':6,
'color_vec': ['W', 'W', 'B', 'B', 'R', 'B'],
}
main(cfg, 'cost')
参见：https://groups.google.com/forum/#!msg/or-tools-discuss/p5qVzZWIeIg/g77egaD-AAAJ
Glop is a pure LP. It will only solve the relaxation of the mip problem. So it is normal that the error checker tells you that the solution is not integral.
You can change GLOP_LINEAR_PROGRAMMING to BOP_INTEGER_PROGRAMMING if you program is purely boolean.
Or you can stay with CBC
这就是为什么你应该使用：
pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMINGpywraplp.Solver.BOP_INTEGER_PROGRAMMINGpywraplp.Solver.SAT_INTEGER_PROGRAMMING
而不是 pywraplp.Solver.GLOP_LINEAR_PROGRAMMING。
我正在尝试解决线性规划问题。以下是问题的规格：
我有一个已转换为线性规划问题的网络流问题。因此，必须强制执行所有流量约束，例如容量、流量守恒等。我的objective是为了最小化成本。
决策变量 - 我通过定义一个字典并在这 128 个位置的每个位置添加决策变量来构建两个 8x8 矩阵。
约束——总共有24个约束，即： 1）流量从源头开始。两个 8x8 矩阵的 2 个约束。 2）流程在汇点结束。两个 8x8 矩阵的 2 个约束。 3) 流量守恒有 12 个约束条件，两个矩阵各有 8 个约束条件。 4) 有 2 个约束来遵守容量约束，每个矩阵 1 个。 5) 有6条约束可以避免重复
所有变量都必须是二进制的。
Objective - 那些8x8矩阵中有一些变量的总和需要最小化。
同样，所有变量都必须是二进制的。
我已经能够在 Google ORTOOLS 中编写解决方案并且解决方案收敛并显示最小值。但是，当我查看变量时，有些变量具有非二进制值。另外，解决方案是错误的（我在 excel 中有一个现有的解决方案 运行，它是正确的并且不同）。
如果有人能指出正确的方向，我将不胜感激。下面是写在Python36.
中的代码 from ortools.linear_solver import pywraplp
import numpy as np
def configure_constraints(cfg, solver, variable_list):
print(cfg)
dest_convs = cfg['dest_convs']
msize = cfg['lookback_win'] + 1 + 1
rem_capacity = cfg['rem_caps']
# Constraint 1 - Flow starts at the source
for i in range(dest_convs):
# print([(i, 0, c) for c in range(1, msize)])
solver.Add(solver.Sum([variable_list[(i,0,c)] for c in range(1, msize)]) == 1)
# Constraint 2 - Flow ends at the sink
for i in range(dest_convs):
# print([(i, r, msize - 1) for r in range(1, msize)])
solver.Add(solver.Sum([variable_list[(i,r,msize - 1)] for r in range(1, msize)]) == 1)
# Constraint 3 - Flow Conservation
for i in range(dest_convs):
for r in range(msize - 1):
if r+1 == msize - 1:
continue
solver.Add(solver.Sum([variable_list[(i,rind, r+1)] for rind in range(r + 1)]) - solver.Sum([variable_list[(i,r+1, cind + 1)] for cind in range(r+1, msize - 1)]) == 0)
#
# # Constraint 4 - Capacity Constraint
for i in range(dest_convs):
solver.Add(solver.Sum([variable_list[(i, r, c)] for r in range(1, msize-1) for c in range(r+1, msize - 1)]) <= rem_capacity[i] - 1)
#
# # Constraint 5 - 1-vehicle, 1-conveyor
dest_conv_list = []
for i in range(dest_convs):
dest_conv_list.append([])
for r in range(1, msize - 1):
dest_conv_list[i].append(sum([variable_list[(i,r,c)] for c in range(r+1, msize)]))
for items in zip(*dest_conv_list):
solver.Add(solver.Sum(items) == 1)
def configure_objective(solver, variable_list, cost_vars):
# Objective
solver.Minimize(solver.Sum([variable_list[items] for items in zip(*np.where(cost_vars))]))
def solve(solver):
result_status = solver.Solve()
return result_status
def configure_variables(cfg, solver):
# identify variables for the objective function
# print(cfg)
nvehs = cfg['vehicles']
dest_convs = cfg['dest_convs']
color_vec = cfg['color_vec']
cur_cars = cfg['cur_cars']
msize = cfg['lookback_win'] + 1 + 1
# objective_mat = np.zeros((msize, msize), dtype="int32")
mat = [[[0] * msize for i in range(msize)] for j in range(dest_convs)]
# source to vehicles
for i in range(dest_convs):
for j in range(nvehs):
# print(color_vec[j], cur_cars[i])
if color_vec[j] != cur_cars[i]:
mat[i][0][j+1] = 1
for h in range(dest_convs):
for i in range(0, nvehs):
for j in range(i+1, nvehs):
# print(i+1,j+1)
# print(color_vec[i+1], color_vec[j])
if color_vec[i] != color_vec[j]:
mat[h][i+1][j + 1] = 1
cost_vars = np.array(mat).reshape(dest_convs, msize, msize)
print(np.array(mat).reshape(dest_convs,msize,msize))
dvars = {}
for i in range(dest_convs):
for j in range(msize):
for k in range(msize):
dvars[i, j, k] = solver.BoolVar('x[%i,%i, %i]' % (i, j, k))
return dvars, cost_vars
def main(cfg, what):
solver = pywraplp.Solver('SolveSimpleSystem', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
dvars_list, cost_vars = configure_variables(cfg, solver)
configure_constraints(cfg, solver, dvars_list)
configure_objective(solver, dvars_list, cost_vars)
result_status = solve(solver)
print('Number of Variables:', solver.NumVariables())
print('Number of Constraints:', solver.NumConstraints())
# print('Constraints:', solver.)
if result_status == solver.OPTIMAL:
print('Solution Found.')
# The problem has an optimal solution.
print(('Problem solved in %f milliseconds' % solver.wall_time()))
# The objective value of the solution.
print(('Optimal objective value = %f' % solver.Objective().Value()))
var_sum = 0
for variable in dvars_list:
print(('%s = %f' % (dvars_list[variable].name(), dvars_list[variable].solution_value())))
var_sum += dvars_list[variable].solution_value()
print(('Variable sum = %f' % var_sum))
# The value of each variable in the solution.
elif result_status == solver.INFEASIBLE:
print('No solution found.')
elif result_status == solver.POSSIBLE_OVERFLOW:
print('Some inputs are too large and may cause an integer overflow.')
if __name__ == '__main__':
cfg = {'vehicles': 6,
'dest_convs': 2,
'cur_cars':['B', 'R'],
'rem_caps': [3,3],
'lookback_win':6,
'color_vec': ['W', 'W', 'B', 'B', 'R', 'B'],
}
main(cfg, 'cost')
参见：https://groups.google.com/forum/#!msg/or-tools-discuss/p5qVzZWIeIg/g77egaD-AAAJ
Glop is a pure LP. It will only solve the relaxation of the mip problem. So it is normal that the error checker tells you that the solution is not integral.
You can change GLOP_LINEAR_PROGRAMMING to BOP_INTEGER_PROGRAMMING if you program is purely boolean. Or you can stay with CBC
这就是为什么你应该使用：
pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMINGpywraplp.Solver.BOP_INTEGER_PROGRAMMINGpywraplp.Solver.SAT_INTEGER_PROGRAMMING
而不是 pywraplp.Solver.GLOP_LINEAR_PROGRAMMING。