# Speedup or Caching for a Multi-Iteration MIP problem

I'm solving an MIP: \begin{align}\mathrm{arg\,min}&\quad\sum\limits_{i}{x_i}\\\text{s.t.}&\quad A\,x\geq1,\end{align} where both the matrix $$A$$ and vector $$x$$ are boolean valued, and $$A$$ is symmetric (adjacency matrix). I am then solving this problem repeatedly for different values of $$A$$, but with the same dimension.

My question: How can I make this process faster? I solve the same MIP around 6 times on average, with different values of $$A$$ (generated using solution $$x$$ from previous iteration and a threshold value).

1. Is there a way to cache the results? I'm not sure what I could cache apart from storing the calculated values in a dictionary $$A: x$$ mapping, but there are $$2^{(\dim{A})^2}$$ variants for the dictionary key, so I don't think it's useful.

2. Can we parallelise the computation somehow? I am currently using CVXPY open source Python library, which doesn't support parallel computation, and I don't know how to split the problem into smaller chunks.

• Do you know all the instances of $A$ prior to solving any of the MIPs? Do you need the solution of an MIP to determine the $A$ for the next MIP? If the former, obviously you can parallelize at the "per MIP problem" level, although if only parallel cores in a single processor, rather than parallel processors, there might be limited speedup due to memory bus contention among the cores. – Mark L. Stone Dec 15 '19 at 16:09
• @MarkL.Stone Unfortunately I use the solution of the MIP to calculate the new $A$. In rough terms, I am searching for a solution $x$ with a pre-defined number of non-zero elements. If the number is higher, I re-generate $A$ with higher adjacency threshold, and if lower, with lower threshold, and then re-run the MIP. – Vidak Dec 15 '19 at 16:23