## Network Flow Example

We have a network of $m$ directed edges that support $n$ flows, each of which goes over a fixed path in the graph.  We denote the flow values as $f \in \mathbb{R}_+^n$.  The resulting traffic on the $m$ edges is given by $R f$, where $R \in \{0,1\}^{m \times n}$ is the routing matrix, with $R_{ij}=1$ if flow $j$ goes over edge $i$, and 0 otherwise.

The edges have capacity $c \in \mathbb{R}_+^m$, so we have $Rf \leq c$. The objective is to maximize the total utility, which is $U(f) = \sum_i U_i(f_i)$, with

\begin{equation}
U_i(f_i) = \begin{cases}
-\infty \quad &\text{if} \quad f_i < f^\mathrm{min}_i \\
w_i f_i \quad &\text{if} \quad f^\mathrm{min}_i \leq f_i \leq f_i^\mathrm{max} \\
w_i f_i^\mathrm{max} \quad &\text{otherwise},
\end{cases}
\end{equation}


where the first case is the implicit version of the constraint $f^\mathrm{min} \leq f$. Except for the case of degenerate networks, the third condition will never hold at optimality. Intuitively, when $f_i > f_i^\mathrm{max}$, reducing $f_i$ at not cost, to free capacity for other flows that run through the edges of flow $i$, improves the objective function. We encode this information in the constraint $f \leq f^\mathrm{max}$ and rewrite $U$ in vector form to arrive at the optimization problem

\begin{equation}
\begin{array}{ll}
\text{maximize} \quad &w^T f \\
\text{subject to} \quad &R f \leq c \\
&f^\mathrm{min} \leq f \leq f^\mathrm{max},
\end{array}
\end{equation}

with variable $f \in \mathbb{R}_+^n$ and parameters $w\geq 0$, $c \geq 0$, $R$, and $0 \leq f^\mathrm{min} \leq f^\mathrm{max}$.

Let's define the corresponding CVXPY problem.


```python
import cvxpy as cp
import numpy as np

# define dimensions
n, m = 4, 5

# define variable
f = cp.Variable(n, name='f')

# define parameters
R = cp.Parameter((m, n), name='R')
c = cp.Parameter(m, nonneg=True, name='c')
w = cp.Parameter(n, nonneg=True, name='w')
f_min = cp.Parameter(n, nonneg=True, name='f_min')
f_max = cp.Parameter(n, nonneg=True, name='f_max')

# define objective
objective = cp.Maximize(w@f)

# define constraints
constraints = [R@f <= c, f_min <= f, f <= f_max]

# define problem
problem = cp.Problem(objective, constraints)
```

Assign parameter values and solve the problem.


```python
import numpy as np

np.random.seed(0)
R.value = np.round(np.random.rand(m, n))
c.value = n*(0.1+0.1*np.random.rand(m))
w.value = 0.1+np.random.rand(n)
f_min.value = np.zeros(n)
f_max.value = np.ones(n)

val = problem.solve()
```

Generating C source for the problem is as easy as:


```python
from cvxpygen import cpg

cpg.generate_code(problem, code_dir='network_code')
```

Now, you can use a python wrapper around the generated code as a custom CVXPY solve method.


```python
from network_code.cpg_solver import cpg_solve
import numpy as np
import pickle
import time

# load the serialized problem formulation
with open('network_code/problem.pickle', 'rb') as f:
    prob = pickle.load(f)

# assign parameter values
np.random.seed(0)
prob.param_dict['R'].value = np.round(np.random.rand(m, n))
prob.param_dict['c'].value = n*(0.1+0.1*np.random.rand(m))
prob.param_dict['w'].value = np.random.rand(n)
prob.param_dict['f_min'].value = np.zeros(n)
prob.param_dict['f_max'].value = np.ones(n)

# solve problem conventionally
t0 = time.time()
# CVXPY chooses eps_abs=eps_rel=1e-5, max_iter=10000, polish=True by default,
# however, we choose the OSQP default values here, as they are used for code generation as well
val = prob.solve()
t1 = time.time()
print('\nCVXPY\nSolve time: %.3f ms' % (1000 * (t1 - t0)))
print('Objective function value: %.6f\n' % val)

# solve problem with C code via python wrapper
prob.register_solve('CPG', cpg_solve)
t0 = time.time()
val = prob.solve(method='CPG')
t1 = time.time()
print('\nCVXPYgen\nSolve time: %.3f ms' % (1000 * (t1 - t0)))
print('Objective function value: %.6f\n' % val)
```


```python
from visualization.network import create_animation
from IPython.display import Image
    
create_animation(prob, 'network_animation')

with open('network_animation.gif', 'rb') as f:
    display(Image(f.read()))
```

e99a6fe7ac7b287e497e78099c5727d9ccfaf571
ipynb
Jupyter Notebook
examples/network.ipynb
cvxgrp/cvxpygen
5aaacdb894354288e2f12a16ca738248c69181c4
Apache-2.0
2022-02-25T03:30:06.000Z
2022-03-30T16:24:40.000Z
examples/network.ipynb
cvxgrp/cvxpygen
5aaacdb894354288e2f12a16ca738248c69181c4
Apache-2.0
examples/network.ipynb
cvxgrp/cvxpygen
5aaacdb894354288e2f12a16ca738248c69181c4
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES