I'm looking for ways to improve the computation time in my optimization
My problem is in the form
$$ \min p^T \cdot q + |c| \\ \text{lower bound} \leq q \leq \text{upper bound} \\ \text{lower bound} \leq c \leq \text{upper bound} \\ Aq + Bc = d \\ Rq \leq \text{bound} $$
Where $p, d$ are vectors and $A, B, R$ are sparse matrices and $q, c$ are variables.
The matrices $A,B.R$ are very large and very sparse and have a repeating pattern. So I was curious if there could be some improvement. The problem is a on hourly basis, which means that the pattern will repeat for every hour.
Basically in $q$ the first $17$ variables corresponds to the first hour, variables $18-35$ corresponds to the second hour, variables $36-53$ corresponds to the third hour and so on.
In $A$ the block corresponding to first hour looks like this
$$ \begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{pmatrix} \begin{pmatrix} q_1 \\ q_2 \\ q_3 \\ q_5 \\ \vdots \\ q_{17} \\ \end{pmatrix} $$
The rest of $A$ is just the same block shifted to the "right and down" so that it "hits" $q_{18} - q_{35}$, $q_{36} - q_{53}$ and so on
$$ \begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ & & & & & & & & & & & & & & & & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ & & & & & & & & & & & & & & & & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ & & & & & & & & & & & & & & & & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ & & & & & & & & & & & & & & & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0\\ & & & & & & & & & & & & & & & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ & & & & & & & & & & & & & & & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{pmatrix} \begin{pmatrix} q_1 \\ q_2 \\ q_3 \\ q_5 \\ \vdots \\ q_{35} \\ \end{pmatrix} $$
Matrix $B$ has the same behaviour with hour block "hitting" the first $8$ variables in $c$, second hour block hitting variables $9-17$, third hour hitting variables $18-26$ and so on. Where the block looks like
$$ \begin{pmatrix} -1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & \\ 1 & 0 & -1 & -1 & 0 & 1 & 0 & 0 & \\ 0 & 0 & 1 & 0 & -1 & -1 & 0 & 0 & \\ 0 & 0 & 0 & 0 & 1 & 0 & -1 & -1 & \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & \\ \end{pmatrix} \begin{pmatrix} c_1 \\ c_2 \\ c_3 \\ c_5 \\ \vdots \\ c_{8} \\ \end{pmatrix} $$
The rest of $B$ is just the same block shifted to the "right and down" so that it "hits" $c_{9} - q_{17}$, $c_{18} - c_{26}$ and so on, just like in $A$
Now in matrix $R$ its taken into account what happend previous hour. So at hour $2$ we're looking at what happend at hour $1$. At hour $3$ we are looking at what happend at hour $2$ and $1$. Thus, at hour $i$ we are considering what happend at hour $1$ through $i-1$. This does not apply to all variables in $q$. It only applies to $4$ variables for each hour, i.e $q_{3 + 17k}, q_{6 + 17k}, q_{11 + 17k}, q_{15 + 17k}$.
This means that $Rq$ looks like
$$ \begin{pmatrix} -q_3 \\ -q_6 \\ -q_{11} \\ -q_{15} \\ q_3 \\ q_6 \\ q_{11} \\ q_{15} \\ -q_3 - q_{20}\\ -q_6 - q_{23} \\ -q_{11} - q_{28} \\ -q_{15} - q_{32} \\ q_3 + q_{20}\\ q_6 + q_{23} \\ q_{11} + q_{28} \\ q_{15} + q_{32} \\ \vdots \\ - \sum_{k=0}^{N} q_{3+17k} \\ - \sum_{k=0}^{N} q_{6+17k} \\ - \sum_{k=0}^{N} q_{11+17k} \\ - \sum_{k=0}^{N} q_{15+17k} \\ \sum_{k=0}^{N} q_{3+17k} \\ \sum_{k=0}^{N} q_{6+17k} \\ \sum_{k=0}^{N} q_{11+17k} \\ \sum_{k=0}^{N} q_{15+17k} \end{pmatrix} $$
All matrices $A, B, R$ contain a lot of zeros and are large. My thinking is that there perhaps is a better way to formulate this, how the problem is formulated mathematically or how its implemented in code. All matrices are implemented as spare matrices with the function spmatrix in cvxopt.
problem = op(sum(prod_price) + 1e-6*sum(abs(c)), [q >= q_lower_bound, q <= q_upper_bound, -1*c <= -1*c_lower_bound, c <= c_upper_bound, A * q + B * c == d, R * q <= bound])
Current setup A is a $26058 \times 73831$ matrix
B is a $26058 \times 34744$ matrix
R is a $34744\times 73831$ matrix
and it takes about 30 minutes to solve
Edit I'm not looking for a high accuracy in the solution. Accuracy at $10^{-1}$ is enough. Currently trying to go through the different options that can be set to solver to see if computation time can be decreased with less accuracy.