8

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.

Vidak
  • 183
  • 5
  • 1
    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

1 Answers1

6

If you can switch the solver to either CPLEX or Gurobi, you can have parallel threads during the MIP solutions.

I'm not familiar with Gurobi, but with CPLEX, you could try passing a previous solution in as a hot start, and let CPLEX try to repair it. Depending on how you do your updates to A, you might use the previous solution, or you might stockpile solutions and choose the one that satisfies the most constraints (breaking ties via the objective function). Whether that would be faster than just turning CPLEX loose without a hot start is an empirical question.

prubin
  • 39,078
  • 3
  • 37
  • 104