[Scip] binary quadratic problems (BQP) problems in SCIP

[Stefan Vigerske]

Hi,

this kind of problem is not necessarily "simple". :-)
There are a number of parameters in SCIP you could play with.

By default, SCIP linearizes the objective by introducing new variables, 
likely around n many if your x is of dimension n. That is, each term 
x_i(\sum_j Q_{i,j}x_j) is replaced by a new variable w_i and linear 
constraints are added to enforce w_i = x_i(\sum_j Q_{i,j}x_j) for x_i 
\in {0,1}.
You can turn this off by setting
constraints/quadratic/replacebinaryprod = 0, sometimes that works 
better, sometimes not.
You can also let it introduce a new variable for each x_i*x_j with 
nonzero Q_{i,j} by setting constraints/quadratic/replacebinaryprod = 1.
As higher the value of this parameter (default is infinity), as fewer 
auxiliary variables are used.

Additionally, you can tell SCIP to use and-constraint to represent the 
condition w_{i,j} = x_i * x_j by setting
constraints/quadratic/empathy4and = 2. I haven't seen instances where 
this helps, but maybe you are more lucky (if you have a product of > 2 
variables, and-constraints should be better).

Further, try constraints/quadratic/binreforminitial = TRUE. That makes 
all constraints added by the above linearizations initial, while by 
default half of them are not in the initial LP but only separated when 
needed. Having them all in the LP should increase the chance for finding 
good solutions, but also slows down LP solving.

If Q is block-separable and you have chosen 
constraints/quadratic/replacebinaryprod = 0, then also try 
constraints/quadratic/disaggregate = TRUE. The latter leads to split up 
your big quadratic constraint into a number of smaller ones, one for 
each block.

Finally, there are emphasis settings in SCIP you can play around, e.g., 
setting heuristics aggressively, if you feel that finding a good 
solution takes too long, or setting separation aggressively, if you hope 
that more cutting planes can help.

That's all I can think of at the moment.

Best,
Stefan


On 01/18/2013 01:08 AM, James Gunning wrote:
> Dear all,
>           I'm a newcomer to the list, with an interest in solving binary
> quadratic problem
> of form
>   min(x^T.Q.x)
>    with some simple linear constraint on x (Q not pos definite in general).
> Inputting these problem in via the standard cplex lp format with []
> notation for the
> quadratic pieces, I get the right answer from SCIP, but I'm sure its
> capable of much faster
> performance given the right tricks.
> If anyone has experience, usage guidance or suggestions for simple
> problem of this form in SCIP,
> I'd be grateful to hear them.
>
> Best wishes to all,
>          James.
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>