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

[James Gunning]

Hi Stefan,
            thanks for such a prompt list of suggestions. They give me some 
things to try.
A few remarks below...

Stefan Vigerske wrote:
> Hi,
>
> this kind of problem is not necessarily "simple". :-)
I'm very much aware of that, probably very NP-hard. I meant "simple to state" :-)
> 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.
Ok - nice to know what "default" does. I have vague memories of this in some 
Glover papers....
> 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.
I'd already tried this trick, converting to a BLP and feeding to the coin-or cbc 
code. It's pretty good, & I had some
very generous help from John Forrest, but my instinct was one may be able to do 
better,
e.g. with other linearizations, hence my interest in trying it in SCIP.
>
> 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.
OK, thanks for these ideas.
> 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.
If only this were true of my problem....  :-)
>
> 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.
I appreciate your thoughts very much. Thanks for taking the time to make these 
suggestions.

Best wishes,
         James.

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: James_Gunning.vcf
Type: text/x-vcard
Size: 223 bytes
Desc: not available
Url : http://listserv.zib.de/mailman/private/scip/attachments/20130118/d3f8ad7b/James_Gunning.vcf