Originally posted by: Andy_Bu

Hi everyone,

we have just expanded an unconstrained binary quadratic problem (dense coefficient matrix), that is very efficiently solved with cplex when linearisation is turned off, with a series of continuous variables -.5<phi_i<.5 that describe some fine details of the model. First of all, the inclusion of these variables increases the runtime significantly. Is is possible to let cplex emphasize the binary variables (that describe big changes in the model), spending less time on the fine details? 

Moreover, we have currently modelled the function 1-cos(2*pi*phi_i) by it's second order Taylor expansion. While this gives quite decent qualitative results, it is not very precise. Is it possible to go to higher orders in the Taylor expansion by introducing some auxiliary variables and constraints, without sacrificing too much performance? E.g. the runtime for piecewise approximations seems to be really bad.

Thanks!

Originally posted by: EdKlotz

First of all, is the original quadratic objective convex or nonconvex?   That will affect the answer to the other parts of your question.    Also, how do the continuous phi variables relate to the binary variables in the quadratic objective?

Maybe you should just post a couple of the models in question up to this thread.

Originally posted by: Andy_Bu

Hi EdKlotz, the objective is convex and remains so even with the inclusion of the phi_i (for the case when I approximate the cosine by a second order taylor series). The phi variables have a nonzero coupling between each other, as well as to all the binary variables within the Q matrix. But they are all restricted to the range -0.5<phi_i<0.5. Attached is a .mps file for a small problem of 51 binary variables and 51 continuous variables, where 1-cos(2*pi*phi) has been approximated by the second order Taylor series.

Originally posted by: Andy_Bu

Here is attached the model with the piecewise implementation of the phi_i's (for 30 binaries). The piecewise function consists of 11 points and has a very bad performance.

Originally posted by: EdKlotz

I had a look at the model.   Regarding your question

>>>>

First of all, the inclusion of these variables increases the runtime significantly. Is is possible to let cplex emphasize the binary variables (that describe big changes in the model), spending less time on the fine details? 

>>>>>

If you know enough regarding the quadratic objective coefficients involving the all binary terms that you could use them to create a priority order for branching, that could help.   Another way to "emphasize" the binaries would be to first optimize over the model with only binary terms in the objective, then use that as a MIP start for the problem that include products of binaries and continuous variables.   However, on the model you sent, I tried it and found that it didn't help (or hurt) performance.

Regarding your question about using more than 2 terms in the Taylor series expansion, going to 3 terms involves values of phi^4, right?   I don't see any change of variables that will enable you to model this in a way CPLEX can use other than the piecewise linear formulation you mentioned.   That being said, if your function is convex over the domains of your phi variables, maybe there's some second order cone formulation that would work.    There certainly are some convex functions that are definitely not quadratic that can be formulated using SOCP in some rather counterintuitive ways; see section 2 of the Alizadeh/Goldfarb paper (availalble at http://bicmr.pku.edu.cn/~wenzw/courses/Alizadeh-Goldfarb-socp.pdf among other places).   Beyond that, the second order expansion basically uses a parabolic type function, so maybe you could instead fit some other parabola to your curve that actually provides a more precise representation.

I haven't really thought much modeling this type of expression before, so maybe someone else will have something to add.

Originally posted by: Andy_Bu

Thanks a lot! I also tested priorities by now, but no change in performance unfortunately. The 4-th order term would be x^4 and I would probably need to go to 6-th order to get good enough precision. While the trig. function is not convex itself, it can be bounded from below and above by parabolas (see the pdf). Not sure how much that helps though. I need to have a look at the paper you send! I still think that there should be some efficient solution, but how to get there...

Originally posted by: EdKlotz

Looking at the attached PDF, the trig function is convex for most of the domain of phi, so maybe you can break the problem up into optimizing 3 subproblems, namely the convex part in the middle and the concave parts near the boundaries of the domains, perhaps using piecewise linear functions.

Originally posted by: Andy_Bu

Hmm, I can separate the piecewise functions into three parts, the central one being convex and the two others being concave. Would that be useful? Another question arises how to implement which of the three functions is applied. One would have to say, if phi is in that variable region, apply piecewise function 1, otherwise apply pw function 2 and so on. That would be not so easy to implement I guess.

Originally posted by: EdKlotz

Yes, you could use pwl for all 3 parts, but I was proposing that you use some sort of parabolic approximation (which could be second order Taylors series, but could also be the "best fit" parabolic approximation) for the central. convex region.    So  you solve that region with a quadratic approximation, then solve the left and right regions using pwl approximations, then take the solution from the 3 solves that gives you the best region.   So do 3 separate solves, possibly in parallel.   It sounds like you are instead proposing to add a disjunctive constraint that sets an expression to be one of 3 possible expressions (2 pwl, one quadratic), then do a single optimization.   You could try that as well, but I think solving the 3 problems separately is more promising (and probably easier to try out).