I am trying to solve a linear programming problem.
(我正在尝试解决线性编程问题。)
Following are specs of the problem: (以下是问题的规格：)
I have a network flow problem that's been converted to a linear programming problem.
(我遇到了网络流量问题，该问题已转换为线性编程问题。)
So, all the flow constraints, such as capacity, flow conservation etc., will have to be enforced. (因此，必须强制执行所有流量约束，例如容量，流量守恒等。)
My objective is to minimize cost. (我的目标是最小化成本。)
Decision Variables - I have built two 8x8 matrices by defining a dictionary and adding decision variable at each of those 128 locations.
(决策变量-通过定义字典并在这128个位置的每个位置添加决策变量，我建立了两个8x8矩阵。)
Constraints - there are in total 24 constraints, namely: 1) The flow starts at the source.
(约束-共有24个约束，即：1）流程从源头开始。)
2 constraints for both 8x8 matrices. (两种8x8矩阵都有2个约束。)
2) The flow ends at the sink. (2）流程在水槽处结束。)
2 constraints for both 8x8 matrices. (两种8x8矩阵都有2个约束。)
3) There are 12 constraints for flow conservation, 8 each for both matrices. (3）守恒有12个约束，两个矩阵各有8个。)
4) There are 2 constraints to respect the capacity constraint, 1 for each matrix. (4）有2个约束要遵守容量约束，每个矩阵要约束1个约束。)
5) There are 6 constraints to avoid duplication (5）有6个约束可以避免重复)
All the variables are required to be binary.
(所有变量都必须为二进制。)
Objective - There are certain variables from those 8x8 matrices whose sum is required to be minimized.
(目标-这些8x8矩阵中的某些变量需要将其总和最小化。)
Again, all the variables have to be binary.
(同样，所有变量都必须是二进制的。)
I have been able to code the solution in Google ORTOOLS and solution converges and shows minimum value.
(我已经能够在Google ORTOOLS中编码解决方案，并且解决方案收敛并显示出最小值。)
But, when I look at the variables, there are variables that have non-binary values. (但是，当我查看变量时，有些变量具有非二进制值。)
Also, the solution is wrong (I have an existing solution running in excel which is correct and is different). (另外，解决方案是错误的（我有一个在excel中运行的现有解决方案，该解决方案正确且有所不同）。)
I'd appreciate if someone could point me in the right direction.
(如果有人能指出我正确的方向，我将不胜感激。)
Following is the code which is written in Python 36. (以下是用Python 36编写的代码。)
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')
ask by Ahsan translate from so 
