Mixed Integer SDP with MOSEK Solver under YALMIP

[Mark L. Stone]

If a mixed integer SDP is provided to YALMIP with MOSEK (version 7) specified as the solver, is YALMIP passing the problem to MOSEK as a mixed integer SDP to be solved entirely by MOSEK's own algorithm, or is YALMIP using a mixed integer algorithm framework in which only continuous SDPs are passed to MOSEK?  If the latter, is there an option, or plans for an option, for the former?

Thanks.

[Erling D. Andersen]

There is no native support for mixed-integer SDP in MOSEK. Since we have no test problems then the incentive to add has been very small. MOSEK can do mixed-integer LP and SOCP. 

[Mark L. Stone]

Thanks Erling.  I guess I allowed myself to be led astray by the CVX User's Guide, which for MOSEK at http://web.cvxr.com/cvx/doc/solver.html#supported-solvers has Y's for SOCP, SDP, and Integer, but doesn't state Integer not applying to SDP.  And per http://web.cvxr.com/cvx/doc/intro.html#mixed-integer-problems , seems to strongly suggest that CVX can process and pass on to MOSEK for (attempted) solution any mixed integer disciplined convex program.  So now I'm wondering what CVX does with mixed integer semidefinite programs which are not convertible into second order cone programs (I think such creatures exist).

[Erling D. Andersen]

You would have to ask the CVX forum. Most likely the documentation should be revised.

[Mark L. Stone]

Thanks Erling.  So I have what is still a question for Yohan, which is what YALMIP does.  Thanks.

[Johan Löfberg]

YALMIP solves MISDP using the internal bnb solver (with, e.g., mosek as lower bound solver). Alternatively, it can use the internal cutting-plane solver (with any MILP solver used for solving local MILPs)

[Erling D. Andersen]

If you want to support in MOSEK, then providing some test problems would extremely beneficial.

[Mark L. Stone]

Erling,

This is more of a hypothetical question for me, as I have not (YET) encountered any mixed integer SDPs of my own, but can envision doing so. If you want a mixed integer SDP, take an SDP and impose some integer constraints.  I can think of one application area which I'm not involved in (as of now), but not sure if the math works out correctly for a continuous variable SDP (as a zero duality gap dual) to be converted into an integer SDP and have the solution be "correct" in the real world.

[Erling D. Andersen]

The following is merely some general comments than directly related to the original question.

A company like of ours has a ton of good projects. I am currently tuning our presolve for instance that will benefit a tons of users.

Therefore, if something is merely of theoretical/academic interest, then it will move down on the TODO list. 

It is easy for us to do mixed integer SDP code but if we have no real world problems to tune it for it is likely to be uninteresting/worthless exercise.

Developers like us HATE randomly constructed problems because experience says they tell us nothing about the problems users want to solve.

They can either be too easy or too hard.

To summarize if somebody wants a commercial company like MOSEK to support a problem type then providing some interesting instances to work

on will make it much more likely that company does something about it. I am aware there is a chicken and egg issue here.

[Mark L. Stone]

Erling,

I appreciate your comments.  I think my original question was more along the lines of inquiring about the details of a chicken, mistakenly thinking it already existed, but given that it does not, I don't have the egg, but thinking about the possibility of an egg, and perhaps would think a little harder if I knew there were a chicken. Nevertheless, I'll let you know if I find an egg, and if I do, it's likely to be of the highly non-trivial variety.

[Mark L. Stone]

Yes, the CVX documentation needs to be revised.  See http://ask.cvxr.com/question/1906/mixed-integer-sdps-which-are-not-mixed-integer-socps/ .