# Help speeding up mixed integer SDP solve

**URL:** <https://discourse.julialang.org/t/help-speeding-up-mixed-integer-sdp-solve/23889>\
**Category:** Optimization (Mathematical)\
**Created:** [May 5, 2019, 11:30pm UTC](https://discourse.julialang.org/t/help-speeding-up-mixed-integer-sdp-solve/23889 "2019-05-05T23:30:08Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [May 5, 2019, 11:30pm UTC](https://discourse.julialang.org/t/help-speeding-up-mixed-integer-sdp-solve/23889/1 "2019-05-05T23:30:08Z")

</div>

I have a big mixed-integer SDP that I’d like to solve. Essentially my difficulty is it takes too long to solve-- using Pajarito, it doesn’t even finish the first MILP solve in 12 hours with access to 216 cores and 6 TB of ram.

I’ve been using Pajarito with CPLEX as the mixed-integer solver and Mosek as the continuous solver. Pajarito reports my problem has

```julia
Problem dimensions:
       variables | 33857
     constraints | 131341
   nonzeros in A | 315513

Cones summary:
Cone | Count | Min dim. | Max dim.
   Pos. semidef. | 4 | 4^2 | 4^2

Variable types:
      continuous | 32833
          binary | 1024

```

I’ve set CPLEX as

```julia
mip_solver = CplexSolver(
    CPX_PARAM_SCRIND=1, # AKA verbose = false
    CPX_PARAM_EPINT=1e-8,
    CPX_PARAM_EPRHS=1e-7,
    CPX_PARAM_EPGAP=1e-5,
    CPX_PARAM_THREADS=215,
    CPX_PARAM_PARALLELMODE=-1
)

```

and the Pajarito solver as

```julia
PajaritoSolver(cont_solver = MosekSolver(LOG=1), mip_solver = mip_solver,
       mip_solver_drives = false, use_mip_starts = true,
       solve_relax = false, log_level = 3)

```

choosing some of the parameters by trying with a smaller instance of the problem and seeing what seemed to speed it up.

The form of the problem is

\min \langle \pi(v), c \rangle

where v is a vector defined by v\_i = \operatorname{tr}(A\_i X) with the A\_i fixed PSD matrices, X is a PSD variable, \pi is a permutation matrix, and c is a fixed vector (actually, just c=(1,2,3,...,n)). (Actually, the problem is a sum of several such terms, only related by an affine constraint, \sum\_k X\_k = I, where X\_k is the PSD variable from the kth such term).

Now, a priori this is a quadratic problem since the binary variables in \pi are multiplied by the matrix elements of X. I am not against trying solving the quadratic problem (or relaxing the permutations to bistochastic matrices), but it is of the form x^T Q x for non-PSD Q, so I don’t think it’s a convex problem in that formulation. I was fortunate to receive some help in [this issue](https://github.com/lanl-ansi/Alpine.jl/issues/114) to reformulate it from a non-convex quadratic problem to a mixed-integer SDP by introducing auxiliary variables y corresponding to the product of entries of \pi and entries of X, along with four affine constraints on each element of y (well, 8 for me, since my variables X are complex so I deal with the real and imaginary parts separately).

One helpful observation is that for a given choice of X, the optimal \pi is just the permutation that sorts v into decreasing order, since c is already in increasing order. However, I could not use this information directly in a convex way (e.g. the sorted dot product is an atom in Convex.jl, but it is convex, and introducing the right minus signs to sort one vector in increasing order and the other in decreasing order results in a concave objective function). I can and do, however, introduce constraints on \pi to require it to sort v in decreasing order, which does seem to speed up a smaller instance of the problem (2 seconds to 1.2 seconds on my laptop).

So with all that context, my question is: can anyone advise me about how to try to speed up solving this problem? In Pajarito, I can’t even get past the first iteration, which (I believe) means solving the resulting MILP that you get when you remove all the SDP constraints, with CPLEX. Maybe there are some more CPLEX parameters I should try? Or I should try different Pajarito parameters? Is it just too big? I don’t really have a good idea of how big or small this problem is considered to be.

One issue is that I think CPLEX may not be using all the parallelism it could be. The average CPU load starts very high, but decreasing over the course of the computation. After 8-9 hours, it seemed like it was only using a few cores at most, though maybe 300 gb of ram. I tried setting `CPX_PARAM_PARALLELMODE=-1` for “opportunistic” parallelism which CPLEX said might be faster, but it did not seem better.

I really appreciate any help or advice.

---

<div class="post-metadata">

**Author:** ![Vahid\_Ansari](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vahid_ansari/32/35136_2.png) [@Vahid\_Ansari](https://discourse.julialang.org/u/Vahid_Ansari)\
**Post date:** [April 15, 2022, 5:17pm UTC](https://discourse.julialang.org/t/help-speeding-up-mixed-integer-sdp-solve/23889/2 "2022-04-15T17:17:17Z")

</div>

Hello  
I have faced same problem  
did you find any solution for that?

---

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [April 15, 2022, 5:33pm UTC](https://discourse.julialang.org/t/help-speeding-up-mixed-integer-sdp-solve/23889/3 "2022-04-15T17:33:26Z")

</div>

No, I didn’t. I tried many reformulations of my problem but did not have much success in solving bigger instances of my problem. I have some code here from that project: [https://github.com/ericphanson/GuessworkQuantumSideInfo.jl](https://github.com/ericphanson/GuessworkQuantumSideInfo.jl).

---

<div class="post-metadata">

**Author:** ![Vahid\_Ansari](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vahid_ansari/32/35136_2.png) [@Vahid\_Ansari](https://discourse.julialang.org/u/Vahid_Ansari)\
**Post date:** [April 16, 2022, 5:26am UTC](https://discourse.julialang.org/t/help-speeding-up-mixed-integer-sdp-solve/23889/4 "2022-04-16T05:26:30Z")

</div>

thanks for your answer