Decentralization¶
Reference¶
SAS/OR example: http://go.documentation.sas.com/?docsetId=ormpex&docsetTarget=ormpex_ex10_toc.htm&docsetVersion=15.1&locale=en
SAS/OR code for example: http://support.sas.com/documentation/onlinedoc/or/ex_code/151/mpex10.html
Model¶
import sasoptpy as so
import pandas as pd
def test(cas_conn):
m = so.Model(name='decentralization', session=cas_conn)
DEPTS = ['A', 'B', 'C', 'D', 'E']
CITIES = ['Bristol', 'Brighton', 'London']
benefit_data = pd.DataFrame([
['Bristol', 10, 15, 10, 20, 5],
['Brighton', 10, 20, 15, 15, 15]],
columns=['city'] + DEPTS).set_index('city')
comm_data = pd.DataFrame([
['A', 'B', 0.0],
['A', 'C', 1.0],
['A', 'D', 1.5],
['A', 'E', 0.0],
['B', 'C', 1.4],
['B', 'D', 1.2],
['B', 'E', 0.0],
['C', 'D', 0.0],
['C', 'E', 2.0],
['D', 'E', 0.7]], columns=['i', 'j', 'comm']).set_index(['i', 'j'])
cost_data = pd.DataFrame([
['Bristol', 'Bristol', 5],
['Bristol', 'Brighton', 14],
['Bristol', 'London', 13],
['Brighton', 'Brighton', 5],
['Brighton', 'London', 9],
['London', 'London', 10]], columns=['i', 'j', 'cost']).set_index(
['i', 'j'])
max_num_depts = 3
benefit = {}
for city in CITIES:
for dept in DEPTS:
try:
benefit[dept, city] = benefit_data.loc[city, dept]
except:
benefit[dept, city] = 0
comm = {}
for row in comm_data.iterrows():
(i, j) = row[0]
comm[i, j] = row[1]['comm']
comm[j, i] = comm[i, j]
cost = {}
for row in cost_data.iterrows():
(i, j) = row[0]
cost[i, j] = row[1]['cost']
cost[j, i] = cost[i, j]
assign = m.add_variables(DEPTS, CITIES, vartype=so.BIN, name='assign')
IJKL = [(i, j, k, l)
for i in DEPTS for j in CITIES for k in DEPTS for l in CITIES
if i < k]
product = m.add_variables(IJKL, vartype=so.BIN, name='product')
totalBenefit = so.expr_sum(benefit[i, j] * assign[i, j]
for i in DEPTS for j in CITIES)
totalCost = so.expr_sum(comm[i, k] * cost[j, l] * product[i, j, k, l]
for (i, j, k, l) in IJKL)
m.set_objective(totalBenefit-totalCost, name='netBenefit', sense=so.MAX)
m.add_constraints((so.expr_sum(assign[dept, city] for city in CITIES)
== 1 for dept in DEPTS), name='assign_dept')
m.add_constraints((so.expr_sum(assign[dept, city] for dept in DEPTS)
<= max_num_depts for city in CITIES), name='cardinality')
product_def1 = m.add_constraints((assign[i, j] + assign[k, l] - 1
<= product[i, j, k, l]
for (i, j, k, l) in IJKL),
name='pd1')
product_def2 = m.add_constraints((product[i, j, k, l] <= assign[i, j]
for (i, j, k, l) in IJKL),
name='pd2')
product_def3 = m.add_constraints((product[i, j, k, l] <= assign[k, l]
for (i, j, k, l) in IJKL),
name='pd3')
m.solve()
print(m.get_problem_summary())
m.drop_constraints(product_def1)
m.drop_constraints(product_def2)
m.drop_constraints(product_def3)
m.add_constraints((
so.expr_sum(product[i, j, k, l]
for j in CITIES if (i, j, k, l) in IJKL) == assign[k, l]
for i in DEPTS for k in DEPTS for l in CITIES if i < k),
name='pd4')
m.add_constraints((
so.expr_sum(product[i, j, k, l]
for l in CITIES if (i, j, k, l) in IJKL) == assign[i, j]
for k in DEPTS for i in DEPTS for j in CITIES if i < k),
name='pd5')
m.solve()
print(m.get_problem_summary())
totalBenefit.set_name('totalBenefit')
totalCost.set_name('totalCost')
print(so.get_solution_table(totalBenefit, totalCost))
print(so.get_solution_table(assign).unstack(level=-1))
return m.get_objective_value()
Output¶
In [1]: import os
In [2]: hostname = os.getenv('CASHOST')
In [3]: port = os.getenv('CASPORT')
In [4]: from swat import CAS
In [5]: cas_conn = CAS(hostname, port)
In [6]: import sasoptpy
In [7]: from examples.client_side.decentralization import test
In [8]: test(cas_conn)
NOTE: Initialized model decentralization.
NOTE: Added action set 'optimization'.
NOTE: Converting model decentralization to OPTMODEL.
NOTE: Submitting OPTMODEL code to CAS server.
NOTE: Problem generation will use 8 threads.
NOTE: The problem has 105 variables (0 free, 0 fixed).
NOTE: The problem has 105 binary and 0 integer variables.
NOTE: The problem has 278 linear constraints (183 LE, 5 EQ, 90 GE, 0 range).
NOTE: The problem has 660 linear constraint coefficients.
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).
NOTE: The OPTMODEL presolver is disabled for linear problems.
NOTE: The initial MILP heuristics are applied.
NOTE: The MILP presolver value AUTOMATIC is applied.
NOTE: The MILP presolver removed 0 variables and 120 constraints.
NOTE: The MILP presolver removed 120 constraint coefficients.
NOTE: The MILP presolver added 120 constraint coefficients.
NOTE: The MILP presolver modified 0 constraint coefficients.
NOTE: The presolved problem has 105 variables, 158 constraints, and 540 constraint coefficients.
NOTE: The MILP solver is called.
NOTE: The parallel Branch and Cut algorithm is used.
NOTE: The Branch and Cut algorithm is using up to 8 threads.
Node Active Sols BestInteger BestBound Gap Time
0 1 2 -14.9000000 135.0000000 111.04% 0
0 1 2 -14.9000000 67.5000000 122.07% 0
0 1 2 -14.9000000 55.0000000 127.09% 0
0 1 3 8.1000000 55.0000000 85.27% 0
0 1 3 8.1000000 48.0000000 83.12% 0
0 1 3 8.1000000 44.8375000 81.93% 0
0 1 3 8.1000000 42.0000000 80.71% 0
0 1 3 8.1000000 39.0666667 79.27% 0
0 1 3 8.1000000 34.7500000 76.69% 0
0 1 3 8.1000000 33.3692308 75.73% 0
0 1 3 8.1000000 32.6500000 75.19% 0
0 1 3 8.1000000 31.9066667 74.61% 0
0 1 3 8.1000000 30.7000000 73.62% 0
0 1 3 8.1000000 30.1600000 73.14% 0
0 1 3 8.1000000 29.8800000 72.89% 0
0 1 3 8.1000000 29.8000000 72.82% 0
0 1 3 8.1000000 29.4722222 72.52% 0
0 1 3 8.1000000 28.9117647 71.98% 0
0 1 3 8.1000000 28.6716667 71.75% 0
0 1 3 8.1000000 28.5000000 71.58% 0
0 1 4 14.9000000 14.9000000 0.00% 0
NOTE: The MILP solver added 34 cuts with 185 cut coefficients at the root.
NOTE: Optimal.
NOTE: Objective = 14.9.
NOTE: The output table 'SOLUTION' in caslib 'CASUSER(casuser)' has 105 rows and 6 columns.
NOTE: The output table 'DUAL' in caslib 'CASUSER(casuser)' has 278 rows and 4 columns.
NOTE: The CAS table 'solutionSummary' in caslib 'CASUSER(casuser)' has 18 rows and 4 columns.
NOTE: The CAS table 'problemSummary' in caslib 'CASUSER(casuser)' has 20 rows and 4 columns.
Selected Rows from Table PROBLEMSUMMARY
Value
Label
Objective Sense Maximization
Objective Function netBenefit
Objective Type Linear
Number of Variables 105
Bounded Above 0
Bounded Below 0
Bounded Below and Above 105
Free 0
Fixed 0
Binary 105
Integer 0
Number of Constraints 278
Linear LE (<=) 183
Linear EQ (=) 5
Linear GE (>=) 90
Linear Range 0
Constraint Coefficients 660
NOTE: Added action set 'optimization'.
NOTE: Converting model decentralization to OPTMODEL.
NOTE: Submitting OPTMODEL code to CAS server.
NOTE: Problem generation will use 8 threads.
NOTE: The problem has 105 variables (0 free, 0 fixed).
NOTE: The problem has 105 binary and 0 integer variables.
NOTE: The problem has 68 linear constraints (3 LE, 65 EQ, 0 GE, 0 range).
NOTE: The problem has 270 linear constraint coefficients.
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).
NOTE: The OPTMODEL presolver is disabled for linear problems.
NOTE: The initial MILP heuristics are applied.
NOTE: The MILP presolver value AUTOMATIC is applied.
NOTE: The MILP presolver removed 0 variables and 0 constraints.
NOTE: The MILP presolver removed 0 constraint coefficients.
NOTE: The MILP presolver modified 0 constraint coefficients.
NOTE: The presolved problem has 105 variables, 68 constraints, and 270 constraint coefficients.
NOTE: The MILP solver is called.
NOTE: The parallel Branch and Cut algorithm is used.
NOTE: The Branch and Cut algorithm is using up to 8 threads.
Node Active Sols BestInteger BestBound Gap Time
0 1 2 -28.1000000 135.0000000 120.81% 0
0 1 2 -28.1000000 30.0000000 193.67% 0
0 1 3 -16.3000000 30.0000000 154.33% 0
0 1 3 -16.3000000 30.0000000 154.33% 0
NOTE: The MILP solver added 4 cuts with 24 cut coefficients at the root.
2 0 4 14.9000000 14.9000000 0.00% 0
NOTE: Optimal.
NOTE: Objective = 14.9.
NOTE: The output table 'SOLUTION' in caslib 'CASUSER(casuser)' has 105 rows and 6 columns.
NOTE: The output table 'DUAL' in caslib 'CASUSER(casuser)' has 68 rows and 4 columns.
NOTE: The CAS table 'solutionSummary' in caslib 'CASUSER(casuser)' has 18 rows and 4 columns.
NOTE: The CAS table 'problemSummary' in caslib 'CASUSER(casuser)' has 20 rows and 4 columns.
Selected Rows from Table PROBLEMSUMMARY
Value
Label
Objective Sense Maximization
Objective Function netBenefit
Objective Type Linear
Number of Variables 105
Bounded Above 0
Bounded Below 0
Bounded Below and Above 105
Free 0
Fixed 0
Binary 105
Integer 0
Number of Constraints 68
Linear LE (<=) 3
Linear EQ (=) 65
Linear GE (>=) 0
Linear Range 0
Constraint Coefficients 270
totalBenefit totalCost
- 80.0 65.1
assign (A, Bristol) 1.0
(A, Brighton) 0.0
(A, London) 0.0
(B, Bristol) 0.0
(B, Brighton) 1.0
(B, London) 0.0
(C, Bristol) 0.0
(C, Brighton) 1.0
(C, London) -0.0
(D, Bristol) 1.0
(D, Brighton) 0.0
(D, London) 0.0
(E, Bristol) 0.0
(E, Brighton) 1.0
(E, London) 0.0
dtype: float64
Out[8]: 14.9