Decentralization (SASPy)¶
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]: import saspy
In [3]: config_file = os.path.abspath('../tests/examples/saspy_config.py')
In [4]: sas_conn = saspy.SASsession(cfgfile=config_file)
Using SAS Config named: sshsas
SAS Connection established. Subprocess id is 158
In [5]: import sasoptpy
In [6]: from examples.client_side.decentralization import test
In [7]: test(sas_conn)
NOTE: Initialized model decentralization.
NOTE: Converting model decentralization to OPTMODEL.
NOTE: Submitting OPTMODEL code to SAS instance.
NOTE: Writing HTML5(SASPY_INTERNAL) Body file: STDOUT
NOTE: Problem generation will use 4 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 4 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.7285714 75.98% 0
0 1 3 8.1000000 30.9500000 73.83% 0
0 1 3 8.1000000 30.5142857 73.46% 0
0 1 3 8.1000000 28.5000000 71.58% 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 33 cuts with 177 cut coefficients at the root.
NOTE: Optimal.
NOTE: Objective = 14.9.
NOTE: The data set WORK.PROB_SUMMARY has 20 observations and 3 variables.
NOTE: The data set WORK.SOL_SUMMARY has 18 observations and 3 variables.
NOTE: The data set WORK.SOLUTION has 105 observations and 6 variables.
NOTE: The data set WORK.DUAL has 278 observations and 4 variables.
NOTE: PROCEDURE OPTMODEL used (Total process time):
real time 0.20 seconds
cpu time 0.23 seconds
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: Converting model decentralization to OPTMODEL.
NOTE: Submitting OPTMODEL code to SAS instance.
NOTE: Writing HTML5(SASPY_INTERNAL) Body file: STDOUT
NOTE: Problem generation will use 4 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 4 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 data set WORK.PROB_SUMMARY has 20 observations and 3 variables.
NOTE: The data set WORK.SOL_SUMMARY has 18 observations and 3 variables.
NOTE: The data set WORK.SOLUTION has 105 observations and 6 variables.
NOTE: The data set WORK.DUAL has 68 observations and 4 variables.
NOTE: PROCEDURE OPTMODEL used (Total process time):
real time 0.11 seconds
cpu time 0.10 seconds
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 65.1
assign (A, Bristol) 1
(A, Brighton) 0
(A, London) 0
(B, Bristol) 0
(B, Brighton) 1
(B, London) 0
(C, Bristol) 0
(C, Brighton) 1
(C, London) 0
(D, Bristol) 1
(D, Brighton) 0
(D, London) 0
(E, Bristol) 0
(E, Brighton) 1
(E, London) 0
dtype: int64
Out[7]: 14.9