[SCIP] FW: Constraint cutting planes in constraint handlers

[Felipe Serrano]

Hi Ahmed

Standard  SCIP solves LP relaxations, so quadratic constraints are not
added to the LP. Basically, they try to build a linear cut separating, say,
the current LP solution from the region defined by the quadratic constraint.

I'll try to briefly explain how to obtain cuts for a quadratic constraint.
However these are the basic mechanisms and it is not always what SCIP does.
So if you have a more particular doubt, please ask.

In what follows I assume the quadratic constraint is of the form f(x) <= 0.
I'll use <,> for the dot product.

Roughly speaking, if a quadratic constraint is convex (f(x)<= 0, with f
convex), then the cut is obtained from the following inequality that holds
for all convex function:
f(y) + < gradient f(y) , x - y > <=  f(x) for all x and y

In particular, for our constraint it holds
f(y) + < gradient f(y) , x - y > <=  0 for all  y and all *feasible* x
(since for feasible x, f(x) <= 0)
So if you want to cut off x_0 because it doesn't satisfy the constraint,
then
f(x_0) + < gradient f(x_0) , x - x_0 > <=  0
is a valid inequality. It indeed separates the point, since f(x_0) should
be > 0, otherwise it would satisfy the constraint.

In the non-convex case, things are a bit more complicated since you can't
always find a separating hyperplane.
Anyway, the general idea is to build a convex underestimator of the
function and hope that a "gradient cut" (as the one above) separates the
point.

One can usually build linear underestimators by applying McCormick
linearizations for bilinear terms (ie, x*y) and secants for concave terms
(ie, -x^2). It is *very* important that your variables are bounded,
otherwise there might not exist a covex underestimator.
I'll now explain what a McCormick linearization is.
Say x is in [lx, ux] and y is in [ly, uy], then you know that (x-lx) (y -
ly) >= 0 for all feasible points. Expanding and leaving xy at the left side
you get: xy >= x ly + y lx - lx ly
This is one of the 2 possible  McCormick underestimators you can build. So,
if you find a point that violates x*y + x <= 0, you would hope that x ly +
y lx - lx ly + x <= 0 would separate it.

Best,
Felipe

On Sun, Mar 6, 2016 at 6:19 PM, Ahmed Ibrahim <Ahmed.Ibrahim at umanitoba.ca>
wrote:

>
> ------------------------------
> *From:* Ahmed Ibrahim
> *Sent:* Sunday, March 06, 2016 11:03 AM
> *To:* Gerald Gamrath
> *Subject:* RE: [SCIP] Constraint cutting planes in constraint handlers
>
> Hi Gerald,
>
> Thanks for this response. Actually it fixed a misunderstanding I had. May
> I also ask, whether the same applies for quadratic constraint separators?
>
> Regards,
> Ahmed
> ------------------------------
> *From:* Gerald Gamrath [gamrath at zib.de]
> *Sent:* Tuesday, March 01, 2016 9:36 AM
> *To:* Ahmed Ibrahim; scip at zib.de
> *Subject:* Re: [SCIP] Constraint cutting planes in constraint handlers
>
> Dear Ahmed,
>
> the logic or, setppc, and varbound constraint handlers have separation
> routines, but these only generates the linear rows representing the
> specific constraints. They do not create 'real' cutting planes.
>
> Remember that a constraint is not directly present in the LP, but it will
> normally create one or more rows to add the constraint (or a relaxation of
> it) to the LP. For linear constraints or their specializations (e.g., logic
> or, setppc, and varbound), the constraint can be represented by one linear
> row.
> If constraints have their 'initial' flag set to TRUE when created (which
> is the default), the initial relaxation will be added to the LP when
> building the LP data structure at the root node. Linear constraints and
> specializations are then fully represented in the LP and no separation is
> needed later, anymore.
>
> On the other hand, if 'initial' is set to FALSE or 'removable' to TRUE,
> the row corresponding to a constraint may not be in the LP. The separation
> procedure then checks whether the row would by violated by the current LP
> solution and adds it, if needed. This is similar to the concept of lazy
> constraints used in, e.g., CPLEX.
>
> Best,
> Gerald
>
> On 29.02.2016 20:51, Ahmed Ibrahim wrote:
>
> Hi all,
> I was wondering if any one knows where can I find an explanation of how
> cutting planes for logic or setppc and varbound constraint handlers are
> obtained?
>
> Regards,
> Ahmed
>
>
> _______________________________________________
> Scip mailing listScip at zib.dehttp://listserv.zib.de/mailman/listinfo/scip
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20160306/774e8ce3/attachment.html>