## Resource Allocation Example

Assume we have to assign resources of $m$ classes to $n$ kinds of jobs. This resource allocation is encoded in $X \in \mathbb{R}^{n \times m}$, with $X_{i,j}$ denoting the amount of resource $j$ allocated to job $i$. Given the utility matrix $W \in \mathbb{R}^{n \times m}$, we want to solve the optimization problem

\begin{equation}
\begin{array}{ll}
\text{maximize} \quad &\mathrm{tr} \left( \min \left( X W^T, S\right) \right)\\
\text{subject to} \quad &X^\mathrm{min} \leq X \leq X^\mathrm{max} \\
&X^T \mathbb{1} \leq r,
\end{array}
\end{equation}

with variable $X \in \mathbb{R}^{n \times m}$. The utility for some job $i$ cannot be increased beyond the saturation value $S_{ii}$, with $S \in \mathbb{S}_+^{n}$ being diagonal. The minimum and maximum amounts of resources to be allocated are denoted by $X^\mathrm{min} \geq 0$ and $X^\mathrm{max} \geq X^\mathrm{min}$, respectively, while $r$ is the vector of available resources. The problem is feasible if $\left(X^\mathrm{min}\right)^T \mathbb{1} \leq r$ and $X^\mathrm{min} \leq X^\mathrm{max}$.

Let's define the corresponding CVXPY problem.


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

# define dimensions
n, m = 30, 10

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

# define parameters
W = cp.Parameter((n, m), name='W')
S = cp.Parameter((n, n), diag=True, name='S')
X_min = cp.Parameter((n, m), name='X_min')
X_max = cp.Parameter((n, m), name='X_max')
r = cp.Parameter(m, name='r')

# define objective
objective = cp.Maximize(cp.trace(cp.minimum(X@W.T, S)))

# define constraints
constraints = [X_min <= X, X<= X_max, 
               X.T@np.ones(n) <= r]

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

Assign parameter values and solve the problem.


```python
np.random.seed(0)

W.value = np.ones((n, m)) + 0.1*np.random.rand(n, m)
S.value = 100*np.eye(n)
X_min.value = np.random.rand(n, m)
X_max.value = 10 + np.random.rand(n, m)
r.value = np.matmul(X_min.value.T, np.ones(n)) + 10*np.random.rand(m)

val = problem.solve()
```

Generating C source for the problem is as easy as:


```python
from cvxpygen import cpg

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

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


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

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

# assign parameter values
np.random.seed(0)
prob.param_dict['S'].value = 100*np.eye(n)
prob.param_dict['W'].value = 0.8*np.ones((n, m)) + 0.2*np.random.rand(n, m)
prob.param_dict['X_min'].value = np.zeros((n, m))
prob.param_dict['X_max'].value = np.ones((n, m))
prob.param_dict['r'].value = np.matmul(prob.param_dict['X_min'].value.T, np.ones(n)) + np.random.rand(m)

# 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.resource import create_animation
from IPython.display import Image
    
create_animation(prob, 'resource_animation')

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

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