defprint_sub_sol_benders(model, demand_nominal, demand_var, x, g, pi, theta, v, w, h): d_sol = {} if(model.status != 2): print('The problem is infeasible or unbounded!') print('Status: {}'.format(model.status)) else: print('Obj(sub) : {}'.format(model.ObjVal), end='\t| ') for key in g.keys(): # print('demand: {}, perturbation = {}'.format(demand_nominal[key], g[key].x)) d_sol[key] = demand_nominal[key] + demand_var[key] * g[key].x return d_sol
""" build initial master problem """ """ Create variables """ master = Model('master problem') x_master = {} z = {} y = {} eta = master.addVar(lb=0, vtype=GRB.INTEGER, name='eta')
for i in range(facility_num): y[i] = master.addVar(vtype=GRB.BINARY, name='y_%s' % (i)) z[i] = master.addVar(lb=0, vtype=GRB.INTEGER, name='z_%s' % (i))
""" Set objective """ obj = LinExpr() for i in range(facility_num): obj.addTerms(fixed_cost[i], y[i]) obj.addTerms(unit_capacity_cost[i], z[i]) obj.addTerms(1, eta)
master.setObjective(obj, GRB.MINIMIZE)
""" Add Constraints """ # cons 1 for i in range(facility_num): master.addConstr(z[i] <= max_capacity * y[i])
""" Add initial value Constraints """ # create new constraints
''' create the subproblem ''' subProblem = Model('sub problem') x = {} # transportation decision variables in subproblem # d = {} # true demand g = {} # uncertainty part: var part pi = {} # dual variable theta = {} # dual variable v = {} # aux var w = {} # aux var h = {} # aux var big_M = 10000 for i in range(facility_num): pi[i] = subProblem.addVar(lb=-GRB.INFINITY, ub=0, vtype=GRB.INTEGER, name='pi_%s' % i) v[i] = subProblem.addVar(vtype=GRB.BINARY, name='v_%s' % i) for j in range(customer_num): w[j] = subProblem.addVar(vtype=GRB.BINARY, name='w_%s' % j) g[j] = subProblem.addVar(lb=0, ub=1, vtype=GRB.CONTINUOUS, name='g_%s' % j) theta[j] = subProblem.addVar(lb=-GRB.INFINITY, ub = 0, vtype=GRB.INTEGER, name='theta_%s' % j) # d[j] = subProblem.addVar(lb = 0, ub = GRB.INFINITY, vtype = GRB.CONTINUOUS, name = 'd_%s'%j) for i in range(facility_num): for j in range(customer_num): h[i, j] = subProblem.addVar(vtype=GRB.BINARY, name='h_%s_%s' % (i, j)) x[i, j] = subProblem.addVar(lb=0, ub = GRB.INFINITY, vtype=GRB.CONTINUOUS, name='x_%s_%s' % (i, j))
""" set objective """ sub_obj = LinExpr() for i in range(facility_num): for j in range(customer_num): sub_obj.addTerms(trans_cost[i][j], x[i, j]) subProblem.setObjective(sub_obj, GRB.MAXIMIZE)
""" add constraints to subproblem """ # cons 1 for i in range(facility_num): expr = LinExpr() for j in range(customer_num): expr.addTerms(1, x[i, j]) subProblem.addConstr(expr <= z_sol[i], name='sub_capacity_1_z_%s' % i)
# cons 2 for j in range(facility_num): expr = LinExpr() for i in range(customer_num): expr.addTerms(1, x[i, j]) subProblem.addConstr(expr >= demand_nominal[j] + demand_var[j] * g[j])
# cons 3 for i in range(facility_num): for j in range(customer_num): subProblem.addConstr(pi[i] - theta[j] <= trans_cost[i][j])
""" demand constraints """ # for j in range(customer_num): # subProblem.addConstr(d[j] == demand_nominal[j] + g[j] * demand_var[j])
# close the flag master.setParam('Outputflag', 0) subProblem.setParam('Outputflag', 0) """ Main loop of CCG algorithm """ while (UB - LB > eps and iter_cnt <= max_iter): iter_cnt += 1 # print('\n\n --- iter : {} --- \n'.format(iter_cnt)) print('\n iter : {} '.format(iter_cnt), end='\t | ')
# if subproblem is frasible and bound, create variables xk+1 and add the new constraints if (subProblem.status == 2and subProblem.ObjVal 1000000000): """ Benders Optimality Cut""" # create new cuts """ eta >= sum {theta * d} - sum {pi * z} """ ...... ......
# solve the resulted master problem # master.optimize() print('Obj(master): {}'.format(master.ObjVal), end='\t | ') """ Update the LB """ LB = master.ObjVal print('LB (iter {}): {}'.format(iter_cnt, LB), end='\t | ')
""" Update the subproblem """ # first, get z_sol from updated master problem for key in z.keys(): z_sol[key] = z[key].x
# change the coefficient of subproblem for i in range(facility_num):
constr_name_1 = 'sub_capacity_1_z_' + str(i) constr_name_2 = 'sub_capacity_2_z_' + str(i) subProblem.remove(subProblem.getConstrByName(constr_name_1)) subProblem.remove(subProblem.getConstrByName(constr_name_2)) # add new constraints # cons 1
Rahmaniani, R., Ahmed, S., Crainic, T.G., Gendreau, M., Rei, W., 2020. The Benders Dual Decomposition Method. Operations Research 68, 878–895. https://doi.org/10.1287/opre.2019.1892
Zeng, B., Zhao, L., 2013. Solving two-stage robust optimization problems using a column-and-constraint generation method. Operations Research Letters 41, 457–461. https://doi.org/10.1016/j.orl.2013.05.003
