<div dir="ltr"><div><div>Hi Ahmed<br><br>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.<br></div><div><br>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.<br><br></div><div>In what follows I assume the quadratic constraint is of the form f(x) <= 0. I'll use <,> for the dot product.<br><br></div><div>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:<br></div><div>f(y) + < gradient f(y) , x - y > <=  f(x) for all x and y<br><br></div><div>In particular, for our constraint it holds<br>f(y) + < gradient f(y) , x - y > <=  0 for all  y and all *feasible* x  (since for feasible x, f(x) <= 0)<br></div><div>So if you want to cut off x_0 because it doesn't satisfy the constraint, then  <br>f(x_0) + < gradient f(x_0) , x - x_0 > <=  0<br></div><div>is a valid inequality. It indeed separates the point, since f(x_0) should be > 0, otherwise it would satisfy the constraint.<br><br>In the non-convex case, things are a bit more complicated since you can't always find a separating hyperplane.<br>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.<br><br>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.<br></div><div>I'll now explain what a McCormick linearization is.<br></div><div>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<br></div><div>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.<br><br></div><div>Best,<br></div><div>Felipe <br></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Mar 6, 2016 at 6:19 PM, Ahmed Ibrahim <span dir="ltr"><<a href="mailto:Ahmed.Ibrahim@umanitoba.ca" target="_blank">Ahmed.Ibrahim@umanitoba.ca</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">



<div bgcolor="#FFFFFF">
<div style="direction:ltr;font-family:Tahoma;color:#000000;font-size:10pt"><br>
<div style="font-family:Times New Roman;color:#000000;font-size:16px">
<hr>
<div style="direction:ltr"><font face="Tahoma" color="#000000" size="2"><b>From:</b> Ahmed Ibrahim<br>
<b>Sent:</b> Sunday, March 06, 2016 11:03 AM<br>
<b>To:</b> Gerald Gamrath<br>
<b>Subject:</b> RE: [SCIP] Constraint cutting planes in constraint handlers<br>
</font><br>
</div>
<div></div>
<div>
<div style="direction:ltr;font-family:Tahoma;color:#000000;font-size:10pt">Hi Gerald,
<div><br>
</div>
<div>Thanks for this response. Actually it fixed a misunderstanding I had. May I also ask, whether the same applies for quadratic constraint separators?</div>
<div><br>
</div>
<div>Regards,</div>
<div>Ahmed<br>
<div style="font-family:Times New Roman;color:#000000;font-size:16px">
<hr>
<div style="direction:ltr"><font face="Tahoma" color="#000000" size="2"><b>From:</b> Gerald Gamrath [<a href="mailto:gamrath@zib.de" target="_blank">gamrath@zib.de</a>]<br>
<b>Sent:</b> Tuesday, March 01, 2016 9:36 AM<br>
<b>To:</b> Ahmed Ibrahim; <a href="mailto:scip@zib.de" target="_blank">scip@zib.de</a><br>
<b>Subject:</b> Re: [SCIP] Constraint cutting planes in constraint handlers<br>
</font><br>
</div><div><div class="h5">
<div></div>
<div>
<div>Dear Ahmed,<br>
<br>
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.<br>
<br>
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.<br>
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.<br>
<br>
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.<br>
<br>
Best,<br>
Gerald<br>
<br>
On 29.02.2016 20:51, Ahmed Ibrahim wrote:<br>
</div>
<blockquote type="cite">
<div style="direction:ltr;font-family:Tahoma;color:#000000;font-size:10pt">Hi all,
<div>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? </div>
<div><br>
</div>
<div>Regards,</div>
<div>Ahmed</div>
</div>
<br>
<fieldset></fieldset> <br>
<pre>_______________________________________________
Scip mailing list
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a>
<a href="http://listserv.zib.de/mailman/listinfo/scip" target="_blank">http://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
<br>
</div>
</div></div></div>
</div>
</div>
</div>
</div>
</div>
</div>

<br>_______________________________________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de">Scip@zib.de</a><br>
<a href="http://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">http://listserv.zib.de/mailman/listinfo/scip</a><br>
<br></blockquote></div><br></div>