how to solve the max-min routing question?

Hi folks,

I encountered an issue when I tried to solve the problem: we have `U` city pairs, and we know precisely the possible slot that can place a router. If we just want to use $N_need$ routers, then we wonder what is the worst case of delay (the routing algorithm chooses the shortest path).

As the problem explains, it might be described as a max-min problem, and the formulation can be described as:

$\begin{align}
& \underset{S}{\mathop{\max }}\,\sum\limits_{u=1}^{U}{\min {{d}_{u}}} \\
& =\underset{S}{\mathop{\max }}\,\sum\limits_{u=1}^{U}{\min \sum\limits_{i=1}^{N}{\sum\limits_{j=1}^{N}{{{c}_{ij}}r_{ij}^{u}}}} \\
& =\underset{S}{\mathop{\max }}\,(\min \sum\limits_{u=1}^{U}{\sum\limits_{i=1}^{N}{\sum\limits_{j=1}^{N}{{{c}_{ij}}r_{ij}^{u}}}}) \\
\end{align}$

Then, I follow the solution proposed https://mathoverflow.net/questions/223869/max-min-optimization-problem , and introduce a slack variable as the lower_bound of the shortest path, but it seems that the model is infeasible or unbounded. Specifically, I found that there are many loops, but that's weird because the result should be the shortest path! I'm so stuck to the question, could you please help me solve this issue? Many many thanks!

The main part of my code is here:

m = gp.Model('max_min_delay')

s = m.addVars(N1, vtype=GRB.BINARY, name='s')

m.update()

r = m.addVars(U, E, vtype=GRB.BINARY, name='r')

m.update()

x_lb = m.addVars(U, vtype=GRB.CONTINUOUS, name='x_lb')

m.update()

x = m.addVar(vtype=GRB.CONTINUOUS, name='x')

m.update()

m.addConstr(sum(s[i] for i in range(N1)) == N_need)

for node in range(N1):

    for u in range(U):

        m.addConstrs(r[u, e] <= s[node] for e in in_d[node])

        m.addConstrs(r[u, e] <= s[node] for e in out_d[node])

m.addConstrs(gp.quicksum(edge[e][2] * r[u, e] for e in range(E)) >= x_lb[u] for u in range(U))

m.addConstr(x == gp.quicksum(x_lb[u] for u in range(U)))

for u in range(U):

    src, dst = OD[u][0], OD[u][1]

    src_in_edge, src_out_edge = in_d[src], out_d[src]

    dst_in_edge, dst_out_edge = in_d[dst], out_d[dst]

    m.addConstr(gp.quicksum(r[u, e] for e in src_in_edge) == 0)

    m.addConstr(gp.quicksum(r[u, e] for e in src_out_edge) == 1)

    m.addConstr(gp.quicksum(r[u, e] for e in dst_in_edge) == 1)

    m.addConstr(gp.quicksum(r[u, e] for e in dst_out_edge) == 0)

    for node in range(N):

        if node != src and node != dst:

            in_edge, out_edge = in_d[node], out_d[node]

            m.addConstr(gp.quicksum(r[u, e] for e in in_edge) == gp.quicksum(r[u, e] for e in out_edge))

m.setObjective(x, GRB.MAXIMIZE)

m.write('max_min_delay.lp')

m.optimize()

Sincerely,

Yikun

how to solve the max-min routing question?

Comments

Didn't find what you were looking for?