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.
Constraints - there are in total 24 constraints, namely: 1) The flow starts at the source. 2 constraints for both 8x8 matrices. 2) The flow ends at the sink. 2 constraints for both 8x8 matrices. 3) There are 12 constraints for flow conservation, 8 each for both matrices. 4) There are 2 constraints to respect the capacity constraint, 1 for each matrix. 5) There are 6 constraints to avoid duplication
All the variables are required to be binary.
Objective - There are certain variables from those 8x8 matrices whose sum is required to be minimized.
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. 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).
I'd appreciate if someone could point me in the right direction. Following is the code which is written in 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')
See: 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
That's why you should use either:
pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMINGpywraplp.Solver.BOP_INTEGER_PROGRAMMINGpywraplp.Solver.SAT_INTEGER_PROGRAMMINGinstead of pywraplp.Solver.GLOP_LINEAR_PROGRAMMING.