[SCIP] Adding cuts to polynomial constraints

[Gregor Hendel]

Hi Bjarne,

Am 07.04.19 um 21:16 schrieb Bjarne Grimstad:
> Hello,
>
> Thank you for working on the open-source solver SCIP.
We appreciate that.
>
> I am developing some new cuts for polynomial constraints that I would 
> like to test using the SCIP solver. My needs are as follows:
>
>   * For each node in the B&B tree, and for each polynomial constraint,
>     I would like to generate and add cuts (to the relaxation of the
>     polynomial).
>   * Obviously, it is important that the cuts are added before interval
>     propagation is performed.
>   * The cuts shall be discarded after the node has been processed
>     (i.e., they shall not be inherited by children nodes).
>
> I would really appreciate some pointers to relevant tutorials/docs or 
> source files that I can modify to achieve this.
I have *the* link for you

https://scip.zib.de/doc/html/

It has all the information you are asking for.

...

Now, seriously. I know that SCIP's API can be overwhelming at first, and 
probably you have read the documentation up to a certain point already, 
but could not find the relevant answers. Please always indicate such 
effort on your side in your question. What you want to implement is a 
separator. Since you are not mentioning any programming language 
preferences, I conjecture you prefer C. Please have a look at

https://scip.zib.de/doc/html/SEPA.php

which explains how to implement a user separator.

There is an example https://scip.zib.de/doc/html/GMI_MAIN.php 
implementing a user separator, which you may use as a starting point for 
your implementation.

Polynomial constraints are handled

  * by the linear constraint handler if the degree is 1
    (https://scip.zib.de/doc/html/cons__linear_8h.php)
  * by the quadratic constraint handler if the degree is 2
    (https://scip.zib.de/doc/html/cons__quadratic_8h.php)
  * as nonlinear constraints if the degree is higher
    (https://scip.zib.de/doc/html/cons__nonlinear_8h.php)

You can use the API of those constraint handlers from within your user 
separator to derive the desired inequalities.

Let us know how far you can get with the provided starting points.


Best regards
Gregor

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20190408/97cd5305/attachment.html>