Kidney Exchange¶
Reference¶
SAS blog: https://blogs.sas.com/content/operations/2015/02/06/the-kidney-exchange-problem/
Model¶
import sasoptpy as so
import random
def test(cas_conn, **kwargs):
# Data generation
n = 80
p = 0.02
random.seed(1)
ARCS = {}
for i in range(0, n):
for j in range(0, n):
if random.random() < p:
ARCS[i, j] = random.random()
max_length = 10
# Model
model = so.Model("kidney_exchange", session=cas_conn)
# Sets
NODES = set().union(*ARCS.keys())
MATCHINGS = range(1, int(len(NODES)/2)+1)
# Variables
UseNode = model.add_variables(NODES, MATCHINGS, vartype=so.BIN,
name="usenode")
UseArc = model.add_variables(ARCS, MATCHINGS, vartype=so.BIN,
name="usearc")
Slack = model.add_variables(NODES, vartype=so.BIN, name="slack")
print('Setting objective...')
# Objective
model.set_objective(so.expr_sum((ARCS[i, j] * UseArc[i, j, m]
for [i, j] in ARCS for m in MATCHINGS)),
name="total_weight", sense=so.MAX)
print('Adding constraints...')
# Constraints
Node_Packing = model.add_constraints((UseNode.sum(i, '*') + Slack[i] == 1
for i in NODES), name="node_packing")
Donate = model.add_constraints((UseArc.sum(i, '*', m) == UseNode[i, m]
for i in NODES
for m in MATCHINGS), name="donate")
Receive = model.add_constraints((UseArc.sum('*', j, m) == UseNode[j, m]
for j in NODES
for m in MATCHINGS), name="receive")
Cardinality = model.add_constraints((UseArc.sum('*', '*', m) <= max_length
for m in MATCHINGS),
name="cardinality")
# Solve
model.solve(options={'with': 'milp', 'maxtime': 300}, **kwargs)
# Define decomposition blocks
for i in NODES:
for m in MATCHINGS:
Donate[i, m].set_block(m-1)
Receive[i, m].set_block(m-1)
for m in MATCHINGS:
Cardinality[m].set_block(m-1)
model.solve(options={
'with': 'milp', 'maxtime': 300, 'presolver': 'basic',
'decomp': {'method': 'user'}}, **kwargs)
return model.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.sas_kidney_exchange import test
In [8]: test(cas_conn)
NOTE: Initialized model kidney_exchange.
Setting objective...
Adding constraints...
NOTE: Added action set 'optimization'.
NOTE: Converting model kidney_exchange to OPTMODEL.
NOTE: Submitting OPTMODEL code to CAS server.
NOTE: Problem generation will use 8 threads.
NOTE: The problem has 8133 variables (0 free, 0 fixed).
NOTE: The problem has 8133 binary and 0 integer variables.
NOTE: The problem has 5967 linear constraints (38 LE, 5929 EQ, 0 GE, 0 range).
NOTE: The problem has 24245 linear constraint coefficients.
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).
NOTE: The remaining solution time after problem generation and solver initialization is 299.81 seconds.
NOTE: The initial MILP heuristics are applied.
NOTE: The MILP presolver value AUTOMATIC is applied.
NOTE: The MILP presolver removed 6193 variables and 5357 constraints.
NOTE: The MILP presolver removed 17478 constraint coefficients.
NOTE: The MILP presolver modified 0 constraint coefficients.
NOTE: The presolved problem has 1940 variables, 610 constraints, and 6767 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 4 12.0775275 2279.8770216 99.47% 0
0 1 4 12.0775275 18.3085704 34.03% 1
NOTE: The MILP solver's symmetry detection found 140 orbits. The largest orbit contains 37 variables.
0 1 4 12.0775275 18.3085704 34.03% 1
0 1 4 12.0775275 18.3085704 34.03% 1
0 1 4 12.0775275 18.3085704 34.03% 1
0 1 4 12.0775275 18.3085704 34.03% 1
NOTE: The MILP solver added 4 cuts with 196 cut coefficients at the root.
11 8 5 17.1113590 18.1252274 5.59% 1
28 6 6 17.1113590 18.0210902 5.05% 2
30 5 7 17.1113590 18.0210902 5.05% 2
40 6 8 17.1113590 18.0210902 5.05% 2
66 0 8 17.1113590 17.1113590 0.00% 2
NOTE: Optimal.
NOTE: Objective = 17.111358985.
NOTE: The output table 'SOLUTION' in caslib 'CASUSER(casuser)' has 8133 rows and 6 columns.
NOTE: The output table 'DUAL' in caslib 'CASUSER(casuser)' has 5967 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.
NOTE: Added action set 'optimization'.
NOTE: Converting model kidney_exchange to DataFrame.
NOTE: Cloud Analytic Services made the uploaded file available as table BLOCKSTABLE in caslib CASUSER(casuser).
NOTE: The table BLOCKSTABLE has been created in caslib CASUSER(casuser) from binary data uploaded to Cloud Analytic Services.
NOTE: Uploading the problem DataFrame to the server.
NOTE: Cloud Analytic Services made the uploaded file available as table TMP7IU3_X2F in caslib CASUSER(casuser).
NOTE: The table TMP7IU3_X2F has been created in caslib CASUSER(casuser) from binary data uploaded to Cloud Analytic Services.
NOTE: The problem kidney_exchange has 8133 variables (8133 binary, 0 integer, 0 free, 0 fixed).
NOTE: The problem has 5967 constraints (38 LE, 5929 EQ, 0 GE, 0 range).
NOTE: The problem has 24245 constraint coefficients.
NOTE: The initial MILP heuristics are applied.
NOTE: The MILP presolver value BASIC is applied.
NOTE: The MILP presolver removed 2685 variables and 1925 constraints.
NOTE: The MILP presolver removed 8005 constraint coefficients.
NOTE: The MILP presolver modified 0 constraint coefficients.
NOTE: The presolved problem has 5448 variables, 4042 constraints, and 16240 constraint coefficients.
NOTE: The MILP solver is called.
NOTE: The Decomposition algorithm is used.
NOTE: The Decomposition algorithm is executing in the distributed computing environment in single-machine mode.
NOTE: The DECOMP method value USER is applied.
NOTE: All blocks are identical and the master model is set partitioning.
NOTE: The Decomposition algorithm is using an aggregate formulation and Ryan-Foster branching.
NOTE: The number of block threads has been reduced to 1 threads.
NOTE: The problem has a decomposable structure with 38 blocks. The largest block covers 2.598% of the constraints in the problem.
NOTE: The decomposition subproblems cover 5396 (99.05%) variables and 3990 (98.71%) constraints.
NOTE: The deterministic parallel mode is enabled.
NOTE: The Decomposition algorithm is using up to 8 threads.
Iter Best Master Best LP IP CPU Real
Bound Objective Integer Gap Gap Time Time
. 283.4155 10.5814 10.5814 96.27% 96.27% 1 1
1 259.0121 10.5814 10.5814 95.91% 95.91% 1 1
2 230.6758 10.5814 10.5814 95.41% 95.41% 1 1
3 204.2627 10.5814 10.5814 94.82% 94.82% 2 2
4 192.9770 14.7394 14.7394 92.36% 92.36% 2 2
6 162.6582 15.6274 15.6274 90.39% 90.39% 6 6
7 140.2584 15.6274 15.6274 88.86% 88.86% 6 6
8 109.9454 15.6274 15.6274 85.79% 85.79% 6 7
9 65.4530 16.1007 15.6274 75.40% 76.12% 7 7
10 65.4530 16.1007 17.1114 75.40% 73.86% 7 8
11 51.8662 17.1114 17.1114 67.01% 67.01% 7 8
14 25.6849 17.1114 17.1114 33.38% 33.38% 8 9
15 17.1114 17.1114 17.1114 0.00% 0.00% 8 9
Node Active Sols Best Best Gap CPU Real
Integer Bound Time Time
0 1 9 17.1114 17.1114 0.00% 8 9
NOTE: The Decomposition algorithm used 8 threads.
NOTE: The Decomposition algorithm time is 9.86 seconds.
NOTE: Optimal.
NOTE: Objective = 17.111358985.
Out[8]: 17.11135898487