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
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
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
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
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 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.