／var／logmarcus chiu

Combined Capacity and Flow Assignment Problem

Created on

In Capacity Assignment Problem and Flow Assignment Problem we have learned how to find capacities or flows if one of them is known and we want to dimension the other.

Combined Capacity and Flow Assignment Problem determine the optimal capacities of each link and the optimal assignment of flow on each link, when given the traffic demand between every pair of nodes

Problem

input:

  • network topology
  • traffic matrix R, where each entry Rpq is the traffic demand from node p to q
  • an upper limit Tmaxon the network-wide mean delay
  • a cost function di(Ci) for each link, similarly to the capacity assignment problem
    where di and di0 are constants

    List indent undo

Objective

find both:

  • link capacities C = (C1, C2, …, Cl)
  • flow assignment f = (f1, f2, …, fl)

such that the total cost

is minimized

Constraints

  • The flow f is a multi-commodity flow satisfying R, as in the flow assignment problem. Again, this can be expressed by a system of linear inequalities, but now the capacities are also variables, so we may put it in the form

    Af + BC ≤ b

    with an appropriate choice of the matrices A, B and the vector b. For simplicity, we assume that it includes the obvious constraints f ≤ C, C ≥ 0 and f ≥ 0

  • The network-wide mean delay cannot exceed Tmax. Using our earlier derived formula for T this can be expressed as

    List indent undo

    where γ = Σp,q[Rpq]. The notation T(f,C) emphasizes that now both f and C are variables to be optimized

LP Problem Formulation

LP Problem

  • objective function:
    minimize

    List indent undo

  • linear constraints:

    List indent undo

Solution

Even though the task looks complicated, there is a relatively simple iterative procedure to find at least a local optimum. This makes use of the fact that for the capacity assignment problem we already have an explicit formula for the optimal assignment (in case of linear cost function). If the capacities are assigned according to that formula, then the resulting cost will depend on the flow variables only, as it is already optimized with respect for the capacities:

Now we can try to optimize D(f) with respect to f, which can be done by a heuristic iterative algorithm, as sketched below:

  1. find an initial feasible flow f(0) (can be done by solving the multi-commodity flow problem via linear programming)

  2. compute link weights according to

    List indent undo

    where j is the iteration index

    solve the minimum cost multi-commodity flow problem (via linear programming) using the wi(j)values as link costs. The solution is the next iteration f(j+1)

  3. if D(f(j+1)) ≥ D(f(j)), then STOP, f(j) is a local optimum. Otherwise set j := j + 1 and repeat from Step 2

  4. once the algorithm has found a (locally) optimum flow, the corresponding capacities can be directly computed from the optimal capacity assignment solution:

    List indent undo