ECMP-MILP.py

# -*- coding: utf-8 -*-
"""INET traffic engineering MIP.ipynb

Automatically generated by Colab.

Original file is located at
    https://colab.research.google.com/drive/13PhdLN7ya2PQml99gGycTV5sjk2O00-8
"""

# Libraries
from gurobipy import Model, GRB, quicksum

# Input 1 (slide 23)
# V = ['s1', 's2',
#     'v',  'd'
#     ]
# E = [
#     ('s1', 's2'),  ('s1', 'v'),
#     ('s2', 'v'), ('s2','d'),
#     ('v', 'd'),
#     ]
# E.extend([(b, a) for (a, b) in E if (b, a) not in E])

# c = {edge: 1 for edge in E}  # Edge capacities
# B_s_d = {
#     ('s1', 'd'): 1.5,
#     ('s2', 'd'): 1.5,
# }



# Input 2 (slide 53)
V = ['s', 'z',
    'w', 'x',  'a', 'b',  'y', 'c', 'd'
    ]
E = [
    ('s', 'z'), ('s', 'x'), ('s', 'y'),
    ('z', 'w'),
    ('w', 'x'), ('w', 'b'), ('w', 'a'),  ('w', 'c'),  ('w', 'y'),
    ('x', 'a'), ('y', 'c'),
    ('a', 'b'), ('b', 'c'),
    ('a', 'd'), ('b', 'd'),   ('c', 'd')
    ]
E.extend([(b, a) for (a, b) in E if (b, a) not in E])

c = {edge: 1 for edge in E}  # Edge capacities
B_s_d = {
    # ('s', 'd'): 3,
    ('s', 'w'): 3,
    ('w', 'd'): 3,
    ('y', 'b'): 2,
    ('x', 'b'): 2
}

SD = list(B_s_d.keys())
D = list(set(d for _, d in SD))

# Create a new model and variables
model = Model("graph_optimization")
#model.setParam('OutputFlag', False)

w = model.addVars(E, vtype=GRB.INTEGER, name="w_u_v", lb=1)
dist_u_d = model.addVars(V, D, vtype=GRB.INTEGER, name="dist_u_d", lb=0)
a_u_v_d = model.addVars(E, D, vtype=GRB.BINARY, name="a_u_v_d")
f_u_v_s_d = model.addVars(E, SD, name="f_u_v_s_d", lb=0)
C = model.addVar(name="C")

M = 5*len(E)

#Constraints

#Ensuring weights are the same on both direction
for u, v in E:
  model.addConstr(w[u,v]==w[v,u])


#Distance constraints
for u, v in E:
    for d in D:
        model.addConstr(dist_u_d[u, d] <= dist_u_d[v, d] + w[u, v])

for u, v in E:
    for d in D:
        model.addConstr(dist_u_d[u, d] >= dist_u_d[v, d] + w[u, v] - M * (1 - a_u_v_d[u, v, d]))

for u, v in E:
    for d in D:
        model.addConstr((1 - a_u_v_d[u, v, d]) <= (dist_u_d[v, d] + w[u, v] - dist_u_d[u, d]))

# Flow capacity constraints
model.addConstrs(
    (f_u_v_s_d[u, v, s, d] <= a_u_v_d[u, v, d] * B_s_d[s, d]
    for s, d in SD for u, v in E ),
    name="flow_capacity_constraint"
)


# Flow conservation constraints
for s, d in SD:
    demand = B_s_d[s, d]
    for v in V:
        b_v = 0
        if v == s:
            b_v = -demand
        elif v == d:
            b_v = demand
        model.addConstr(
            quicksum(f_u_v_s_d[u, v, s, d] for u in V if (u,v) in E) -  # Inflow to v
            quicksum(f_u_v_s_d[v, w, s, d] for w in V if (v,w) in E) == b_v,
            name=f"flow_conservation_{s}_{d}_{v}"
        )

#f^s,d(v,u) <= f^s,d(v,w) + M * (1 - a_d(v,w)) for all (u,v), (v,w) in E, (s,d) in SD
model.addConstrs((f_u_v_s_d[v1, u, s, d] <= f_u_v_s_d[v2, w, s, d] + M * (1 - a_u_v_d[v2, w, d]) for (v1, u) in E for (v2, w) in E for (s, d) in SD if v1 == v2), "flow_capacity")

#Congestion constraints
model.addConstrs(
    (f_u_v_s_d[u, v, s, d]  <= c[u, v] + C
     for u, v in E for s, d in SD),
    name="capacity_constraint"
)

print()

#Setting Objective and minimizng

# Set the objective to minimize C
model.setObjective(C, GRB.MINIMIZE)

# Optimize the model
model.optimize()

# Retrieve and print the optimized solution
if model.status == GRB.OPTIMAL:
    for u, v in E:
        weight = w[u,v].X
        print(f"  Weight for ({u},{v}): {weight}")
        # for s,d in SD:
        #   flow = f_u_v_s_d[u,v,s,d].X
        #   print(f"  flow for ({s},{d},{u},{v}): {flow}")
    print(f"\nOptimal objective value C: {C.X}")
else:
    print("No optimal solution found.")