Bilinear constraints and Gurobi?

[Enrique Fernández]

I'm trying to solve a program in which one of the constraints is of the form:

xA1 == xA0 + cA1 * (tf - t0)

where xA1, xA0 and cA1 are (2,1) vars, tf is a 1x1 var and t0 is a constant.

I believe this is a non-convex constraint.

The other constraints I have are pretty simple, most linear and some convex quadratic.

I've tried using ipopt and snopt and the solutions I get so far are very good (in fact I think they are optimal, although I no longer know if I am to expect optimal solutions..). The solvers are also very fast in this very small problem (ipopt and snopt take about 0.02 sec each), so things look pretty good yet.

However, since I am going to scale this model and add many more variables with similar constraints (although in general very sparse), I was wondering if, given that my model is not that non-linear, I could use a more specialized solver.

Gurobi seems to support quadratically constrained programs. However, when I try to use Gurobi, YALMIP says that Gurobi is not compatible with this problem.

It seems like Gurobi only takes certain types of quadratic constraints: http://www.gurobi.com/documentation/6.5/refman/py_model_addqconstr.html

My constraint is not one of those types, so that would explain why YALMIP says Gurobi it's not compatible. However the same page also says: 

"If you add a constraint that isn't in one of these forms (and Gurobi presolve is unable to transform the constraint into one of these forms), you'll get an error when you try to solve the model. Constraints where the quadratic terms only involve binary variables will always be transformed into one of these forms."

My constraints only involve binary variables. Therefore, should I expect that Gurobi supports this type of constraint?

If not, does anyone know if there are solvers well suited for this type of problem without having to use a full general purpose non-linear solver?

Yalmip is awesome. It really makes it easy to prototype.

Thank you!

[Johan Löfberg]

I don't know how well gurobi works when it comes to linearization of binary quadratics. Why don't you simply try

Otherwise, it is trivial to do it manually, or you can use the function binmodel in YALMIP

x*y where x and y are binary can be modelled as z where the binary z satisfies z<=x,z<=y,z>=x+y-1. Products x*y where x binary and y general can also be converted to linear expressions

[Johan Löfberg]

Missed that you already test with gurobi. YALMIP does not know that Gurobi transforms these models and hence rejects.

If you simply use binmodel, YALMIP will do what gurobi now does internally

I will add logic in YALMIP to support this

[Enrique Fernández]

Hi Johan,

Thank you for your help.

Unfortunately, my variables are all continuous.

My quadratic constraints are of the form:

x = c*t

where x, c and t are continuous variables. c and t are bounded by constants though (c_min <= c <= c_max; t_min <= t <= t_max).

Since all my variables are continuous, I guess there are no tricks I can use such as the binmodel one, right?

Is there any specific type of solver specially well suited for this type of constraints?

Ipopt and snopt are working very well in the (very) simple examples I have hand coded, but since my problem is not all that non-linear apart from these constraints and some other convex quadratic constraints, I was wondering if I could do better than general purpose non-linear solvers.

Finally, is there any recommended resource to read about what general purpose non-linear solvers work better for what type of problems?

I keep reading about ipopt, snopt, BARON, knitro and others, and it's hard to know if one of them is considered the state of the art or if the best one of those depends on the type of problem.

Thanks a lot for your help!

[Johan Löfberg]

The you have a nonlinear nonconvex problem for which Gurobi isn't applicable

You can go with a local approach (ipopt, fmincon,snopt,...) or a global aproach (YALMIPs bmibnb, baron, scip). For large-scale, you will have to accept a local approach.

[Enrique Fernández]

I see.

So far snopt/ipopt seem to be working very well, so fingers crossed.

Thanks a lot!

YALMIP is really amazing and makes our lives so much easier. It only took me a couple of hours to prototype something that would have taken me a really long time otherwise, and I get to test it with many solvers with no extra effort at all.

Enrique