1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
7    	/*                                                                           */
8    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
9    	/*  you may not use this file except in compliance with the License.         */
10   	/*  You may obtain a copy of the License at                                  */
11   	/*                                                                           */
12   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
13   	/*                                                                           */
14   	/*  Unless required by applicable law or agreed to in writing, software      */
15   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
16   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17   	/*  See the License for the specific language governing permissions and      */
18   	/*  limitations under the License.                                           */
19   	/*                                                                           */
20   	/*  You should have received a copy of the Apache-2.0 license                */
21   	/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
22   	/*                                                                           */
23   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24   	
25   	/**@file   sepa_rlt.c
26   	 * @ingroup DEFPLUGINS_SEPA
27   	 * @brief  separator for cuts generated by Reformulation-Linearization-Technique (RLT)
28   	 * @author Fabian Wegscheider
29   	 * @author Ksenia Bestuzheva
30   	 *
31   	 * @todo implement the possibility to add extra auxiliary variables for RLT (like in DOI 10.1080/10556788.2014.916287)
32   	 * @todo add RLT cuts for the product of equality constraints
33   	 * @todo implement dynamic addition of RLT cuts during branching (see DOI 10.1007/s10898-012-9874-7)
34   	 * @todo use SCIPvarIsBinary instead of SCIPvarGetType() == SCIP_VARTYPE_BINARY ?
35   	 * @todo parameter maxusedvars seems arbitrary (too large for small problems; too small for large problems); something more adaptive we can do? (e.g., all variables with priority >= x% of highest prio)
36   	 */
37   	
38   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39   	
40   	#include <assert.h>
41   	#include <string.h>
42   	
43   	#include "scip/sepa_rlt.h"
44   	#include "scip/cons_nonlinear.h"
45   	#include "scip/pub_lp.h"
46   	#include "scip/expr_pow.h"
47   	#include "scip/nlhdlr_bilinear.h"
48   	#include "scip/cutsel_hybrid.h"
49   	
50   	
51   	#define SEPA_NAME              "rlt"
52   	#define SEPA_DESC              "reformulation-linearization-technique separator"
53   	#define SEPA_PRIORITY                10 /**< priority for separation */
54   	#define SEPA_FREQ                     0 /**< frequency for separating cuts; zero means to separate only in the root node */
55   	#define SEPA_MAXBOUNDDIST           1.0 /**< maximal relative distance from the current node's dual bound to primal bound
56   	                                         *   compared to best node's dual bound for applying separation.*/
57   	#define SEPA_USESSUBSCIP          FALSE /**< does the separator use a secondary SCIP instance? */
58   	#define SEPA_DELAY                FALSE /**< should separation method be delayed, if other separators found cuts? */
59   	
60   	#define DEFAULT_MAXUNKNOWNTERMS       0 /**< maximum number of unknown bilinear terms a row can have to be used */
61   	#define DEFAULT_MAXUSEDVARS         100 /**< maximum number of variables that will be used to compute rlt cuts */
62   	#define DEFAULT_MAXNCUTS             -1 /**< maximum number of cuts that will be added per round */
63   	#define DEFAULT_MAXROUNDS             1 /**< maximum number of separation rounds per node (-1: unlimited) */
64   	#define DEFAULT_MAXROUNDSROOT        10 /**< maximum number of separation rounds in the root node (-1: unlimited) */
65   	#define DEFAULT_ONLYEQROWS        FALSE /**< whether only equality rows should be used for rlt cuts */
66   	#define DEFAULT_ONLYCONTROWS      FALSE /**< whether only continuous rows should be used for rlt cuts */
67   	#define DEFAULT_ONLYORIGINAL       TRUE /**< whether only original variables and rows should be used for rlt cuts */
68   	#define DEFAULT_USEINSUBSCIP      FALSE /**< whether the separator should also be used in sub-scips */
69   	#define DEFAULT_USEPROJECTION     FALSE /**< whether the separator should first check projected rows */
70   	#define DEFAULT_DETECTHIDDEN      FALSE /**< whether implicit products should be detected and separated by McCormick */
71   	#define DEFAULT_HIDDENRLT         FALSE /**< whether RLT cuts should be added for hidden products */
72   	#define DEFAULT_ADDTOPOOL          TRUE /**< whether globally valid RLT cuts are added to the global cut pool */
73   	
74   	#define DEFAULT_GOODSCORE           1.0 /**< threshold for score of cut relative to best score to be considered good,
75   	                                         *   so that less strict filtering is applied */
76   	#define DEFAULT_BADSCORE            0.5 /**< threshold for score of cut relative to best score to be discarded */
77   	#define DEFAULT_OBJPARALWEIGHT      0.0 /**< weight of objective parallelism in cut score calculation */
78   	#define DEFAULT_EFFICACYWEIGHT      1.0 /**< weight of efficacy in cut score calculation */
79   	#define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 /**< weight of directed cutoff distance in cut score calculation */
80   	#define DEFAULT_GOODMAXPARALL       0.1 /**< maximum parallelism for good cuts */
81   	#define DEFAULT_MAXPARALL           0.1 /**< maximum parallelism for non-good cuts */
82   	
83   	#define MAXVARBOUND                1e+5 /**< maximum allowed variable bound for computing an RLT-cut */
84   	
85   	/*
86   	 * Data structures
87   	 */
88   	
89   	/** data object for pairs and triples of variables */
90   	struct HashData
91   	{
92   	   SCIP_VAR*             vars[3];            /**< variables in the pair or triple, used for hash comparison */
93   	   int                   nvars;              /**< number of variables */
94   	   int                   nrows;              /**< number of rows */
95   	   int                   firstrow;           /**< beginning of the corresponding row linked list */
96   	};
97   	typedef struct HashData HASHDATA;
98   	
99   	/** data structure representing an array of variables together with number of elements and size;
100  	 *  used for storing variables that are in some sense adjacent to a given variable
101  	 */
102  	struct AdjacentVarData
103  	{
104  	   SCIP_VAR**            adjacentvars;       /**< adjacent vars */
105  	   int                   nadjacentvars;      /**< number of vars in adjacentvars */
106  	   int                   sadjacentvars;      /**< size of adjacentvars */
107  	};
108  	typedef struct AdjacentVarData ADJACENTVARDATA;
109  	
110  	/** separator data */
111  	struct SCIP_SepaData
112  	{
113  	   SCIP_CONSHDLR*        conshdlr;           /**< nonlinear constraint handler */
114  	   SCIP_Bool             iscreated;          /**< indicates whether the sepadata has been initialized yet */
115  	   SCIP_Bool             isinitialround;     /**< indicates that this is the first round and original rows are used */
116  	
117  	   /* bilinear variables */
118  	   SCIP_VAR**            varssorted;         /**< variables that occur in bilinear terms sorted by priority */
119  	   SCIP_HASHMAP*         bilinvardatamap;    /**< maps each bilinear var to ADJACENTVARDATA containing vars appearing
120  	                                                  together with it in bilinear products */
121  	   int*                  varpriorities;      /**< priorities of variables */
122  	   int                   nbilinvars;         /**< total number of variables occurring in bilinear terms */
123  	   int                   sbilinvars;         /**< size of arrays for variables occurring in bilinear terms */
124  	
125  	   /* information about bilinear terms */
126  	   int*                  eqauxexpr;          /**< position of the auxexpr that is equal to the product (-1 if none) */
127  	   int                   nbilinterms;        /**< total number of bilinear terms */
128  	
129  	   /* parameters */
130  	   int                   maxunknownterms;    /**< maximum number of unknown bilinear terms a row can have to be used (-1: unlimited) */
131  	   int                   maxusedvars;        /**< maximum number of variables that will be used to compute rlt cuts (-1: unlimited) */
132  	   int                   maxncuts;           /**< maximum number of cuts that will be added per round (-1: unlimited) */
133  	   int                   maxrounds;          /**< maximum number of separation rounds per node (-1: unlimited) */
134  	   int                   maxroundsroot;      /**< maximum number of separation rounds in the root node (-1: unlimited) */
135  	   SCIP_Bool             onlyeqrows;         /**< whether only equality rows should be used for rlt cuts */
136  	   SCIP_Bool             onlycontrows;       /**< whether only continuous rows should be used for rlt cuts */
137  	   SCIP_Bool             onlyoriginal;       /**< whether only original rows and variables should be used for rlt cuts */
138  	   SCIP_Bool             useinsubscip;       /**< whether the separator should also be used in sub-scips */
139  	   SCIP_Bool             useprojection;      /**< whether the separator should first check projected rows */
140  	   SCIP_Bool             detecthidden;       /**< whether implicit products should be detected and separated by McCormick */
141  	   SCIP_Bool             hiddenrlt;          /**< whether RLT cuts should be added for hidden products */
142  	   SCIP_Bool             addtopool;          /**< whether globally valid RLT cuts are added to the global cut pool */
143  	
144  	   /* cut selection parameters */
145  	   SCIP_Real             goodscore;          /**< threshold for score of cut relative to best score to be considered good,
146  	                                              *   so that less strict filtering is applied */
147  	   SCIP_Real             badscore;           /**< threshold for score of cut relative to best score to be discarded */
148  	   SCIP_Real             objparalweight;     /**< weight of objective parallelism in cut score calculation */
149  	   SCIP_Real             efficacyweight;     /**< weight of efficacy in cut score calculation */
150  	   SCIP_Real             dircutoffdistweight;/**< weight of directed cutoff distance in cut score calculation */
151  	   SCIP_Real             goodmaxparall;      /**< maximum parallelism for good cuts */
152  	   SCIP_Real             maxparall;          /**< maximum parallelism for non-good cuts */
153  	};
154  	
155  	/* a simplified representation of an LP row */
156  	struct RLT_SimpleRow
157  	{
158  	   const char*           name;               /**< name of the row */
159  	   SCIP_Real*            coefs;              /**< coefficients */
160  	   SCIP_VAR**            vars;               /**< variables */
161  	   SCIP_Real             rhs;                /**< right hand side */
162  	   SCIP_Real             lhs;                /**< left hand side */
163  	   SCIP_Real             cst;                /**< constant */
164  	   int                   nnonz;              /**< number of nonzeroes */
165  	   int                   size;               /**< size of the coefs and vars arrays */
166  	};
167  	typedef struct RLT_SimpleRow RLT_SIMPLEROW;
168  	
169  	/*
170  	 * Local methods
171  	 */
172  	
173  	/** returns TRUE iff both keys are equal
174  	 *
175  	 * two variable pairs/triples are equal if the variables are equal
176  	 */
177  	static
178  	SCIP_DECL_HASHKEYEQ(hashdataKeyEqConss)
179  	{  /*lint --e{715}*/
180  	   HASHDATA* hashdata1;
181  	   HASHDATA* hashdata2;
182  	   int v;
183  	
184  	   hashdata1 = (HASHDATA*)key1;
185  	   hashdata2 = (HASHDATA*)key2;
186  	
187  	   /* check data structure */
188  	   assert(hashdata1->nvars == hashdata2->nvars);
189  	   assert(hashdata1->firstrow != -1 || hashdata2->firstrow != -1);
190  	
191  	   for( v = hashdata1->nvars-1; v >= 0; --v )
192  	   {
193  	      /* tests if variables are equal */
194  	      if( hashdata1->vars[v] != hashdata2->vars[v] )
195  	         return FALSE;
196  	
197  	      assert(SCIPvarCompare(hashdata1->vars[v], hashdata2->vars[v]) == 0);
198  	   }
199  	
200  	   /* if two hashdata objects have the same variables, then either one of them doesn't have a row list yet
201  	    * (firstrow == -1) or they both point to the same row list
202  	    */
203  	   assert(hashdata1->firstrow == -1 || hashdata2->firstrow == -1 || hashdata1->firstrow == hashdata2->firstrow);
204  	
205  	   return TRUE;
206  	}
207  	
208  	/** returns the hash value of the key */
209  	static
210  	SCIP_DECL_HASHKEYVAL(hashdataKeyValConss)
211  	{  /*lint --e{715}*/
212  	   HASHDATA* hashdata;
213  	   int minidx;
214  	   int mididx;
215  	   int maxidx;
216  	   int idx[3];
217  	
218  	   hashdata = (HASHDATA*)key;
219  	   assert(hashdata != NULL);
220  	   assert(hashdata->nvars == 3 || hashdata->nvars == 2);
221  	
222  	   idx[0] = SCIPvarGetIndex(hashdata->vars[0]);
223  	   idx[1] = SCIPvarGetIndex(hashdata->vars[1]);
224  	   idx[2] = SCIPvarGetIndex(hashdata->vars[hashdata->nvars - 1]);
225  	
226  	   minidx = MIN3(idx[0], idx[1], idx[2]);
227  	   maxidx = MAX3(idx[0], idx[1], idx[2]);
228  	   if( idx[0] == maxidx )
229  	      mididx = MAX(idx[1], idx[2]);
230  	   else
231  	      mididx = MAX(idx[0], MIN(idx[1], idx[2]));
232  	
233  	   /* vars should already be sorted by index */
234  	   assert(minidx <= mididx && mididx <= maxidx);
235  	
236  	   return SCIPhashFour(hashdata->nvars, minidx, mididx, maxidx);
237  	}
238  	
239  	/** store a pair of adjacent variables */
240  	static
241  	SCIP_RETCODE addAdjacentVars(
242  	   SCIP*                 scip,               /**< SCIP data structure */
243  	   SCIP_HASHMAP*         adjvarmap,          /**< hashmap mapping variables to their ADJACENTVARDATAs */
244  	   SCIP_VAR**            vars                /**< variable pair to be stored */
245  	   )
246  	{
247  	   int v1;
248  	   int v2;
249  	   int i;
250  	   ADJACENTVARDATA* adjacentvardata;
251  	
252  	   assert(adjvarmap != NULL);
253  	
254  	   /* repeat for each variable of the new pair */
255  	   for( v1 = 0; v1 < 2; ++v1 )
256  	   {
257  	      v2 = 1 - v1;
258  	
259  	      /* look for data of the first variable */
260  	      adjacentvardata = (ADJACENTVARDATA*) SCIPhashmapGetImage(adjvarmap, (void*)(size_t) SCIPvarGetIndex(vars[v1]));
261  	
262  	      /* if the first variable has not been added to adjvarmap yet, add it here */
263  	      if( adjacentvardata == NULL )
264  	      {
265  	         SCIP_CALL( SCIPallocClearBlockMemory(scip, &adjacentvardata) );
266  	         SCIP_CALL( SCIPhashmapInsert(adjvarmap, (void*)(size_t) SCIPvarGetIndex(vars[v1]), adjacentvardata) );
267  	      }
268  	
269  	      assert(adjacentvardata != NULL);
270  	
271  	      /* look for second variable in adjacentvars of the first variable */
272  	      if( adjacentvardata->adjacentvars == NULL )
273  	      {
274  	         /* we don't know how many adjacent vars there will be - take a guess */
275  	         SCIP_CALL( SCIPallocBlockMemoryArray(scip, &adjacentvardata->adjacentvars, 4) );
276  	         adjacentvardata->adjacentvars[0] = vars[v2];
277  	         ++adjacentvardata->nadjacentvars;
278  	         adjacentvardata->sadjacentvars = 4;
279  	      }
280  	      else
281  	      {
282  	         SCIP_Bool found;
283  	         int pos2;
284  	
285  	         found = SCIPsortedvecFindPtr((void**) adjacentvardata->adjacentvars, SCIPvarComp, vars[v2],
286  	               adjacentvardata->nadjacentvars, &pos2);
287  	
288  	         /* add second var to adjacentvardata->adjacentvars, if not already added */
289  	         if( !found )
290  	         {
291  	            /* ensure size of adjacentvardata->adjacentvars */
292  	            SCIP_CALL( SCIPensureBlockMemoryArray(scip, &adjacentvardata->adjacentvars, &adjacentvardata->sadjacentvars,
293  	                  adjacentvardata->nadjacentvars + 1) );
294  	
295  	            /* insert second var at the correct position */
296  	            for( i = adjacentvardata->nadjacentvars; i > pos2; --i )
297  	            {
298  	               adjacentvardata->adjacentvars[i] = adjacentvardata->adjacentvars[i-1];
299  	            }
300  	            adjacentvardata->adjacentvars[pos2] = vars[v2];
301  	            ++adjacentvardata->nadjacentvars;
302  	         }
303  	      }
304  	
305  	      /* if this is a self-adjacent var, only need to add the connection once */
306  	      if( vars[v1] == vars[v2] )
307  	         break;
308  	   }
309  	
310  	   return SCIP_OKAY;
311  	}
312  	
313  	/** returns the array of adjacent variables for a given variable */
314  	static
315  	SCIP_VAR** getAdjacentVars(
316  	   SCIP_HASHMAP*         adjvarmap,          /**< hashmap mapping variables to their ADJACENTVARDATAs */
317  	   SCIP_VAR*             var,                /**< variable */
318  	   int*                  nadjacentvars       /**< buffer to store the number of variables in the returned array */
319  	   )
320  	{
321  	   ADJACENTVARDATA* adjacentvardata;
322  	
323  	   assert(adjvarmap != NULL);
324  	
325  	   *nadjacentvars = 0;
326  	   adjacentvardata = (ADJACENTVARDATA*) SCIPhashmapGetImage(adjvarmap, (void*)(size_t) SCIPvarGetIndex(var));
327  	
328  	   if( adjacentvardata == NULL )
329  	      return NULL;
330  	
331  	   *nadjacentvars = adjacentvardata->nadjacentvars;
332  	
333  	   return adjacentvardata->adjacentvars;
334  	}
335  	
336  	/** frees all ADJACENTVARDATAs stored in a hashmap */
337  	static
338  	void clearVarAdjacency(
339  	   SCIP*                 scip,               /**< SCIP data structure */
340  	   SCIP_HASHMAP*         adjvarmap           /**< hashmap mapping variables to their ADJACENTVARDATAs */
341  	   )
342  	{
343  	   int i;
344  	   SCIP_HASHMAPENTRY* entry;
345  	   ADJACENTVARDATA* adjacentvardata;
346  	
347  	   assert(adjvarmap != NULL);
348  	
349  	   for( i = 0; i < SCIPhashmapGetNEntries(adjvarmap); ++i )
350  	   {
351  	      entry = SCIPhashmapGetEntry(adjvarmap, i);
352  	
353  	      if( entry == NULL )
354  	         continue;
355  	
356  	      adjacentvardata = (ADJACENTVARDATA*) SCIPhashmapEntryGetImage(entry);
357  	
358  	      /* if adjacentvardata has been added to the hashmap, it can't be empty */
359  	      assert(adjacentvardata->adjacentvars != NULL);
360  	
361  	      SCIPfreeBlockMemoryArray(scip, &adjacentvardata->adjacentvars, adjacentvardata->sadjacentvars);
362  	      SCIPfreeBlockMemory(scip, &adjacentvardata);
363  	   }
364  	}
365  	
366  	/** free separator data */
367  	static
368  	SCIP_RETCODE freeSepaData(
369  	   SCIP*                 scip,               /**< SCIP data structure */
370  	   SCIP_SEPADATA*        sepadata            /**< separation data */
371  	   )
372  	{  /*lint --e{715}*/
373  	   int i;
374  	
375  	   assert(sepadata->iscreated);
376  	
377  	   if( sepadata->nbilinvars != 0 )
378  	   {
379  	      /* release bilinvars that were captured for rlt and free all related arrays */
380  	
381  	      /* if there are bilinear vars, some of them must also participate in the same product */
382  	      assert(sepadata->bilinvardatamap != NULL);
383  	
384  	      clearVarAdjacency(scip, sepadata->bilinvardatamap);
385  	
386  	      for( i = 0; i < sepadata->nbilinvars; ++i )
387  	      {
388  	         assert(sepadata->varssorted[i] != NULL);
389  	         SCIP_CALL( SCIPreleaseVar(scip, &(sepadata->varssorted[i])) );
390  	      }
391  	
392  	      SCIPhashmapFree(&sepadata->bilinvardatamap);
393  	      SCIPfreeBlockMemoryArray(scip, &sepadata->varssorted, sepadata->sbilinvars);
394  	      SCIPfreeBlockMemoryArray(scip, &sepadata->varpriorities, sepadata->sbilinvars);
395  	      sepadata->nbilinvars = 0;
396  	      sepadata->sbilinvars = 0;
397  	   }
398  	
399  	   /* free the remaining array */
400  	   if( sepadata->nbilinterms > 0 )
401  	   {
402  	      SCIPfreeBlockMemoryArray(scip, &sepadata->eqauxexpr, sepadata->nbilinterms);
403  	   }
404  	
405  	   sepadata->iscreated = FALSE;
406  	
407  	   return SCIP_OKAY;
408  	}
409  	
410  	/** creates and returns rows of original linear constraints */
411  	static
412  	SCIP_RETCODE getOriginalRows(
413  	   SCIP*                 scip,               /**< SCIP data structure */
414  	   SCIP_ROW***           rows,               /**< buffer to store the rows */
415  	   int*                  nrows               /**< buffer to store the number of linear rows */
416  	   )
417  	{
418  	   SCIP_CONS** conss;
419  	   int nconss;
420  	   int i;
421  	
422  	   assert(rows != NULL);
423  	   assert(nrows != NULL);
424  	
425  	   conss = SCIPgetConss(scip);
426  	   nconss = SCIPgetNConss(scip);
427  	   *nrows = 0;
428  	
429  	   SCIP_CALL( SCIPallocBufferArray(scip, rows, nconss) );
430  	
431  	   for( i = 0; i < nconss; ++i )
432  	   {
433  	      SCIP_ROW *row;
434  	
435  	      row = SCIPconsGetRow(scip, conss[i]);
436  	
437  	      if( row != NULL )
438  	      {
439  	         (*rows)[*nrows] = row;
440  	         ++*nrows;
441  	      }
442  	   }
443  	
444  	   return SCIP_OKAY;
445  	}
446  	
447  	/** fills an array of rows suitable for RLT cut generation */
448  	static
449  	SCIP_RETCODE storeSuitableRows(
450  	   SCIP*                 scip,               /**< SCIP data structure */
451  	   SCIP_SEPA*            sepa,               /**< separator */
452  	   SCIP_SEPADATA*        sepadata,           /**< separator data */
453  	   SCIP_ROW**            prob_rows,          /**< problem rows */
454  	   SCIP_ROW**            rows,               /**< an array to be filled with suitable rows */
455  	   int*                  nrows,              /**< buffer to store the number of suitable rows */
456  	   SCIP_HASHMAP*         row_to_pos,         /**< hashmap linking row indices to positions in rows */
457  	   SCIP_Bool             allowlocal          /**< are local rows allowed? */
458  	   )
459  	{
460  	   int new_nrows;
461  	   int r;
462  	   int j;
463  	   SCIP_Bool iseqrow;
464  	   SCIP_COL** cols;
465  	   SCIP_Bool iscontrow;
466  	
467  	   new_nrows = 0;
468  	
469  	   for( r = 0; r < *nrows; ++r )
470  	   {
471  	      iseqrow = SCIPisEQ(scip, SCIProwGetLhs(prob_rows[r]), SCIProwGetRhs(prob_rows[r]));
472  	
473  	      /* if equality rows are requested, only those can be used */
474  	      if( sepadata->onlyeqrows && !iseqrow )
475  	         continue;
476  	
477  	      /* if global cuts are requested, only globally valid rows can be used */
478  	      if( !allowlocal && SCIProwIsLocal(prob_rows[r]) )
479  	         continue;
480  	
481  	      /* if continuous rows are requested, only those can be used */
482  	      if( sepadata->onlycontrows )
483  	      {
484  	         cols = SCIProwGetCols(prob_rows[r]);
485  	         iscontrow = TRUE;
486  	
487  	         /* check row for integral variables */
488  	         for( j = 0; j < SCIProwGetNNonz(prob_rows[r]); ++j )
489  	         {
490  	            if( SCIPcolIsIntegral(cols[j]) )
491  	            {
492  	               iscontrow = FALSE;
493  	               break;
494  	            }
495  	         }
496  	
497  	         if( !iscontrow )
498  	            continue;
499  	      }
500  	
501  	      /* don't try to use rows that have been generated by the RLT separator */
502  	      if( SCIProwGetOriginSepa(prob_rows[r]) == sepa )
503  	         continue;
504  	
505  	      /* if we are here, the row has passed all checks and should be added to rows */
506  	      rows[new_nrows] = prob_rows[r];
507  	      SCIP_CALL( SCIPhashmapSetImageInt(row_to_pos, (void*)(size_t)SCIProwGetIndex(prob_rows[r]), new_nrows) ); /*lint !e571 */
508  	      ++new_nrows;
509  	   }
510  	
511  	   *nrows = new_nrows;
512  	
513  	   return SCIP_OKAY;
514  	}
515  	
516  	/** make sure that the arrays in sepadata are large enough to store information on n variables */
517  	static
518  	SCIP_RETCODE ensureVarsSize(
519  	   SCIP*                 scip,               /**< SCIP data structure */
520  	   SCIP_SEPADATA*        sepadata,           /**< separator data */
521  	   int                   n                   /**< number of variables that we need to store */
522  	   )
523  	{
524  	   int newsize;
525  	
526  	   /* check whether array is large enough */
527  	   if( n <= sepadata->sbilinvars )
528  	      return SCIP_OKAY;
529  	
530  	   /* compute new size */
531  	   newsize = SCIPcalcMemGrowSize(scip, n);
532  	   assert(n <= newsize);
533  	
534  	   /* realloc arrays */
535  	   SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &sepadata->varssorted, sepadata->sbilinvars, newsize) );
536  	   SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &sepadata->varpriorities, sepadata->sbilinvars, newsize) );
537  	
538  	   sepadata->sbilinvars = newsize;
539  	
540  	   return SCIP_OKAY;
541  	}
542  	
543  	/** saves variables x and y to separator data and stores information about their connection
544  	 *
545  	 *  variables must be captured separately
546  	 */
547  	static
548  	SCIP_RETCODE addProductVars(
549  	   SCIP*                 scip,               /**< SCIP data structure */
550  	   SCIP_SEPADATA*        sepadata,           /**< separator data */
551  	   SCIP_VAR*             x,                  /**< x variable */
552  	   SCIP_VAR*             y,                  /**< y variable */
553  	   SCIP_HASHMAP*         varmap,             /**< hashmap linking var index to position */
554  	   int                   nlocks              /**< number of locks */
555  	   )
556  	{
557  	   int xpos;
558  	   int ypos;
559  	   int xidx;
560  	   int yidx;
561  	   SCIP_VAR* vars[2];
562  	
(1) Event cond_true: Condition "sepadata->bilinvardatamap == NULL", taking true branch.
563  	   if( sepadata->bilinvardatamap == NULL )
564  	   {
565  	      int varmapsize;
566  	      int nvars;
567  	
568  	      /* the number of variables participating in bilinear products cannot exceed twice the number of bilinear terms;
569  	       * however, if we detect hidden products, the number of terms is yet unknown, so use the number of variables
570  	       */
571  	      nvars = SCIPgetNVars(scip);
(2) Event cond_true: Condition "sepadata->detecthidden", taking true branch.
572  	      varmapsize = sepadata->detecthidden ? nvars : MIN(nvars, sepadata->nbilinterms * 2);
573  	
(3) Event cond_false: Condition "(_restat_ = SCIPhashmapCreate(&sepadata->bilinvardatamap, SCIPblkmem(scip), varmapsize)) != SCIP_OKAY", taking false branch.
(4) Event if_end: End of if statement.
574  	      SCIP_CALL( SCIPhashmapCreate(&sepadata->bilinvardatamap, SCIPblkmem(scip), varmapsize) );
575  	   }
576  	
577  	   xidx = SCIPvarGetIndex(x);
578  	   yidx = SCIPvarGetIndex(y);
579  	
580  	   xpos = SCIPhashmapGetImageInt(varmap, (void*)(size_t) xidx); /*lint !e571 */
581  	
(5) Event cond_true: Condition "xpos == 2147483647", taking true branch.
582  	   if( xpos == INT_MAX )
583  	   {
584  	      /* add x to sepadata and initialise its priority */
(6) Event cond_false: Condition "(_restat_ = SCIPhashmapInsertInt(varmap, (void *)(size_t)xidx, sepadata->nbilinvars)) != SCIP_OKAY", taking false branch.
(7) Event if_end: End of if statement.
585  	      SCIP_CALL( SCIPhashmapInsertInt(varmap, (void*)(size_t) xidx, sepadata->nbilinvars) ); /*lint !e571*/
(8) Event cond_false: Condition "(_restat_ = ensureVarsSize(scip, sepadata, sepadata->nbilinvars + 1)) != SCIP_OKAY", taking false branch.
(9) Event if_end: End of if statement.
586  	      SCIP_CALL( ensureVarsSize(scip, sepadata, sepadata->nbilinvars + 1) );
(10) Event deref_parm: Directly dereferencing parameter "sepadata->varssorted".
587  	      sepadata->varssorted[sepadata->nbilinvars] = x;
588  	      sepadata->varpriorities[sepadata->nbilinvars] = 0;
589  	      xpos = sepadata->nbilinvars;
590  	      ++sepadata->nbilinvars;
591  	   }
592  	
593  	   assert(xpos >= 0 && xpos < sepadata->nbilinvars );
594  	   assert(xpos == SCIPhashmapGetImageInt(varmap, (void*)(size_t) xidx)); /*lint !e571 */
595  	
596  	   /* add locks to priority of x */
597  	   sepadata->varpriorities[xpos] += nlocks;
598  	
599  	   if( xidx != yidx )
600  	   {
601  	      ypos = SCIPhashmapGetImageInt(varmap, (void*)(size_t) yidx); /*lint !e571 */
602  	
603  	      if( ypos == INT_MAX )
604  	      {
605  	         /* add y to sepadata and initialise its priority */
606  	         SCIP_CALL( SCIPhashmapInsertInt(varmap, (void*)(size_t) yidx, sepadata->nbilinvars) ); /*lint !e571*/
607  	         SCIP_CALL( ensureVarsSize(scip, sepadata, sepadata->nbilinvars + 1) );
608  	         sepadata->varssorted[sepadata->nbilinvars] = y;
609  	         sepadata->varpriorities[sepadata->nbilinvars] = 0;
610  	         ypos = sepadata->nbilinvars;
611  	         ++sepadata->nbilinvars;
612  	      }
613  	
614  	      assert(ypos >= 0 && ypos < sepadata->nbilinvars);
615  	      assert(ypos == SCIPhashmapGetImageInt(varmap, (void*)(size_t) yidx)); /*lint !e571 */
616  	
617  	      /* add locks to priority of y */
618  	      sepadata->varpriorities[ypos] += nlocks;
619  	   }
620  	
621  	   /* remember the connection between x and y */
622  	   vars[0] = x;
623  	   vars[1] = y;
624  	   SCIP_CALL( addAdjacentVars(scip, sepadata->bilinvardatamap, vars) );
625  	
626  	   return SCIP_OKAY;
627  	}
628  	
629  	/** extract a bilinear product from two linear relations, if possible
630  	 *
631  	 * First, the two given rows are brought to the form:
632  	 * \f[
633  	 *   a_1x + b_1w + c_1y \leq/\geq d_1,\\
634  	 *   a_2x + b_2w + c_2y \leq/\geq d_2,
635  	 * \f]
636  	 * where \f$ a_1a_2 \leq 0 \f$ and the first implied relation is enabled when \f$ x = 1 \f$
637  	 * and the second when \f$ x = 0 \f$, and \f$ b_1, b_2 > 0 \f$, the product relation can be written as:
638  	 * \f[
639  	 *   \frac{b_1b_2w + (b_2(a_1 - d_1) + b_1d_2)x + b_1c_2y - b_1d_2}{b_1c_2 - c_1b_2} \leq/\geq xy.
640  	 * \f]
641  	 * The inequality sign in the product relation is similar to that in the given linear relations if
642  	 * \f$ b_1c_2 - c_1b_2 > 0 \f$ and opposite if \f$ b_1c_2 - c_1b_2 > 0 \f$.
643  	 *
644  	 * To obtain this formula, the given relations are first multiplied by scaling factors \f$ \alpha \f$
645  	 * and \f$ \beta \f$, which is necessary in order for the solution to always exist, and written as
646  	 * implications:
647  	 * \f{align}{
648  	 *   x = 1 & ~\Rightarrow~ \alpha b_1w + \alpha c_1y \leq/\geq \alpha(d_1 - a_1), \\
649  	 *   x = 0 & ~\Rightarrow~ \beta b_2w + \beta c_2y \leq/\geq \beta d_2.
650  	 * \f}
651  	 * Then a linear system is solved which ensures that the coefficients of the two implications of the product
652  	 * relation are equal to the corresponding coefficients in the linear relations.
653  	 * If the product relation is written as:
654  	 * \f[
655  	 *   Ax + Bw + Cy + D \leq/\geq xy,
656  	 * \f]
657  	 * then the system is
658  	 * \f[
659  	 *   B = \alpha b_1, ~C - 1 = \alpha c_1, ~D+A = \alpha(a_1-d_1),\\
660  	 *   B = \beta b_2, ~C = \beta c_2, ~D = -\beta d_2.
661  	 * \f]
662  	 */
663  	static
664  	SCIP_RETCODE extractProducts(
665  	   SCIP*                 scip,               /**< SCIP data structure */
666  	   SCIP_SEPADATA*        sepadata,           /**< separator data */
667  	   SCIP_VAR**            vars_xwy,           /**< 3 variables involved in the inequalities in the order x,w,y */
668  	   SCIP_Real*            coefs1,             /**< coefficients of the first inequality (always implied, i.e. has x) */
669  	   SCIP_Real*            coefs2,             /**< coefficients of the second inequality (can be unconditional) */
670  	   SCIP_Real             d1,                 /**< side of the first inequality */
671  	   SCIP_Real             d2,                 /**< side of the second inequality */
672  	   SCIP_SIDETYPE         sidetype1,          /**< side type (lhs or rls) in the first inequality */
673  	   SCIP_SIDETYPE         sidetype2,          /**< side type (lhs or rhs) in the second inequality */
674  	   SCIP_HASHMAP*         varmap,             /**< variable map */
675  	   SCIP_Bool             f                   /**< the first relation is an implication x == f */
676  	   )
677  	{
678  	   SCIP_Real mult;
679  	
680  	   /* coefficients and constant of the auxexpr */
681  	   SCIP_Real A; /* coefficient of x */
682  	   SCIP_Real B; /* coefficient of w */
683  	   SCIP_Real C; /* coefficient of y */
684  	   SCIP_Real D; /* constant */
685  	
686  	   /* variables */
687  	   SCIP_VAR* w;
688  	   SCIP_VAR* x;
689  	   SCIP_VAR* y;
690  	
691  	   /* does auxexpr overestimate the product? */
692  	   SCIP_Bool overestimate;
693  	
694  	   /* coefficients in given relations: a for x, b for w, c for y; 1 and 2 for 1st and 2nd relation, respectively */
695  	   SCIP_Real a1 = coefs1[0];
696  	   SCIP_Real b1 = coefs1[1];
697  	   SCIP_Real c1 = coefs1[2];
698  	   SCIP_Real a2 = coefs2[0];
699  	   SCIP_Real b2 = coefs2[1];
700  	   SCIP_Real c2 = coefs2[2];
701  	
702  	   x = vars_xwy[0];
703  	   w = vars_xwy[1];
704  	   y = vars_xwy[2];
705  	
706  	   /* check given linear relations and decide if to continue */
707  	
708  	   assert(SCIPvarGetType(x) == SCIP_VARTYPE_BINARY);  /* x must be binary */
709  	   assert(a1 != 0.0); /* the first relation is always conditional */
710  	   assert(b1 != 0.0 || b2 != 0.0); /* at least one w coefficient must be nonzero */
711  	
(1) Event cond_false: Condition "0", taking false branch.
(2) Event loop_end: Reached end of loop.
712  	   SCIPdebugMsg(scip, "Extracting product from two implied relations:\n");
(3) Event cond_false: Condition "0", taking false branch.
713  	   SCIPdebugMsg(scip, "Relation 1: <%s> == %u => %g<%s> + %g<%s> %s %g\n", SCIPvarGetName(x), f, b1,
714  	      SCIPvarGetName(w), c1, SCIPvarGetName(y), sidetype1 == SCIP_SIDETYPE_LEFT ? ">=" : "<=",
(4) Event loop_end: Reached end of loop.
715  	      f ? d1 - a1 : d1);
(5) Event cond_false: Condition "0", taking false branch.
716  	   SCIPdebugMsg(scip, "Relation 2: <%s> == %d => %g<%s> + %g<%s> %s %g\n", SCIPvarGetName(x), !f, b2,
717  	      SCIPvarGetName(w), c2, SCIPvarGetName(y), sidetype2 == SCIP_SIDETYPE_LEFT ? ">=" : "<=",
(6) Event loop_end: Reached end of loop.
718  	      f ? d2 : d2 - a2);
719  	
720  	   /* cannot use a global bound on x to detect a product */
(7) Event cond_true: Condition "b1 == 0.", taking true branch.
(8) Event cond_false: Condition "c1 == 0.", taking false branch.
(9) Event cond_true: Condition "b2 == 0.", taking true branch.
(10) Event cond_false: Condition "c2 == 0.", taking false branch.
721  	   if( (b1 == 0.0 && c1 == 0.0) || (b2 == 0.0 && c2 == 0.0) )
(11) Event if_end: End of if statement.
722  	      return SCIP_OKAY;
723  	
724  	   /* cannot use a global bound on y to detect a non-redundant product relation */
(12) Event cond_false: Condition "a2 == 0.", taking false branch.
725  	   if( a2 == 0.0 && b2 == 0.0 ) /* only check the 2nd relation because the 1st at least has x */
726  	   {
727  	      SCIPdebugMsg(scip, "Ignoring a global bound on y\n");
728  	      return SCIP_OKAY;
(13) Event if_end: End of if statement.
729  	   }
730  	
(14) Event cond_false: Condition "0", taking false branch.
(15) Event loop_end: Reached end of loop.
731  	   SCIPdebugMsg(scip, "binary var = <%s>, product of its coefs: %g\n", SCIPvarGetName(x), a1*a2);
732  	
733  	   /* rewrite the linear relations in a standard form:
734  	    * a1x + b1w + c1y <=/>= d1,
735  	    * a2x + b2w + c2y <=/>= d2,
736  	    * where b1 > 0, b2 > 0 and first implied relation is activated when x == 1
737  	    */
738  	
739  	   /* if needed, multiply the rows by -1 so that coefs of w are positive */
(16) Event cond_false: Condition "b1 < 0", taking false branch.
740  	   if( b1 < 0 )
741  	   {
742  	      a1 *= -1.0;
743  	      b1 *= -1.0;
744  	      c1 *= -1.0;
745  	      d1 *= -1.0;
746  	      sidetype1 = sidetype1 == SCIP_SIDETYPE_LEFT ? SCIP_SIDETYPE_RIGHT : SCIP_SIDETYPE_LEFT;
(17) Event if_end: End of if statement.
747  	   }
(18) Event cond_false: Condition "b2 < 0", taking false branch.
748  	   if( b2 < 0 )
749  	   {
750  	      a2 *= -1.0;
751  	      b2 *= -1.0;
752  	      c2 *= -1.0;
753  	      d2 *= -1.0;
754  	      sidetype2 = sidetype2 == SCIP_SIDETYPE_LEFT ? SCIP_SIDETYPE_RIGHT : SCIP_SIDETYPE_LEFT;
(19) Event if_end: End of if statement.
755  	   }
756  	
757  	   /* the linear relations imply a product only if the inequality signs are similar */
(20) Event cond_false: Condition "sidetype1 != sidetype2", taking false branch.
758  	   if( sidetype1 != sidetype2 )
(21) Event if_end: End of if statement.
759  	      return SCIP_OKAY;
760  	
761  	   /* when b1c2 = b2c1, the linear relations do not imply a product relation */
(22) Event cond_true: Condition "1. >= fabs(b2 * c1)", taking true branch.
(23) Event cond_true: Condition "1. >= fabs(c2 * b1)", taking true branch.
(24) Event cond_false: Condition "fabs((b2 * c1 - c2 * b1) / ((1. >= fabs(b2 * c1)) ? (1. >= fabs(c2 * b1)) ? 1. : fabs(c2 * b1) : ((fabs(b2 * c1) >= fabs(c2 * b1)) ? fabs(b2 * c1) : fabs(c2 * b1)))) <= scip->set->num_epsilon", taking false branch.
762  	   if( SCIPisRelEQ(scip, b2*c1, c2*b1) )
763  	   {
764  	      SCIPdebugMsg(scip, "Ignoring a pair of linear relations because b1c2 = b2c1\n");
765  	      return SCIP_OKAY;
(25) Event if_end: End of if statement.
766  	   }
767  	
(26) Event cond_true: Condition "!f", taking true branch.
768  	   if( !f )
769  	   {
770  	      /* swap the linear relations so that the relation implied by x == TRUE goes first */
771  	      SCIPswapReals(&a1, &a2);
772  	      SCIPswapReals(&b1, &b2);
773  	      SCIPswapReals(&c1, &c2);
774  	      SCIPswapReals(&d1, &d2);
775  	   }
776  	
777  	   /* all conditions satisfied, we can extract the product and write it as:
778  	    * (1/(b1c2 - c1b2))*(b1b2w + (b2(a1 - d1) + b1d2)x + b1c2y - b1d2) >=/<= xy,
779  	    * where the inequality sign in the product relation is similar to that in the given linear relations
780  	    * if b1c2 - c1b2 > 0 and opposite if b1c2 - c1b2 > 0
781  	    */
782  	
783  	   /* compute the multiplier */
784  	   mult = 1/(b1*c2 - c1*b2);
785  	
786  	   /* determine the inequality sign; only check sidetype1 because sidetype2 is equal to it */
(27) Event cond_true: Condition "sidetype1 == SCIP_SIDETYPE_LEFT", taking true branch.
(28) Event cond_true: Condition "mult > 0.", taking true branch.
787  	   overestimate = (sidetype1 == SCIP_SIDETYPE_LEFT && mult > 0.0) || (sidetype1 == SCIP_SIDETYPE_RIGHT && mult < 0.0);
788  	
(29) Event cond_false: Condition "0", taking false branch.
789  	   SCIPdebugMsg(scip, "found suitable implied rels (w,x,y): %g<%s> + %g<%s> + %g<%s> <= %g\n", a1,
(30) Event loop_end: Reached end of loop.
790  	      SCIPvarGetName(x), b1, SCIPvarGetName(w), c1, SCIPvarGetName(y), d1);
(31) Event cond_false: Condition "0", taking false branch.
791  	   SCIPdebugMsg(scip, "  and %g<%s> + %g<%s> + %g<%s> <= %g\n", a2, SCIPvarGetName(x),
(32) Event loop_end: Reached end of loop.
792  	      b2, SCIPvarGetName(w), c2, SCIPvarGetName(y), d2);
793  	
794  	   /* compute the coefficients for x, w and y and the constant in auxexpr */
795  	   A = (b2*a1 - d1*b2 + d2*b1)*mult;
796  	   B = b1*b2*mult;
797  	   C = b1*c2*mult;
798  	   D = -b1*d2*mult;
799  	
(33) Event cond_false: Condition "0", taking false branch.
800  	   SCIPdebugMsg(scip, "product: <%s><%s> %s %g<%s> + %g<%s> + %g<%s> + %g\n", SCIPvarGetName(x), SCIPvarGetName(y),
(34) Event loop_end: Reached end of loop.
801  	      overestimate ? "<=" : ">=", A, SCIPvarGetName(x), B, SCIPvarGetName(w), C, SCIPvarGetName(y), D);
802  	
(35) Event deref_parm_in_call: Function "addProductVars" dereferences "sepadata->varssorted". [details]
803  	   SCIP_CALL( addProductVars(scip, sepadata, x, y, varmap, 1) );
804  	   SCIP_CALL( SCIPinsertBilinearTermImplicitNonlinear(scip, sepadata->conshdlr, x, y, w, A, C, B, D, overestimate) );
805  	
806  	   return SCIP_OKAY;
807  	}
808  	
809  	/** convert an implied bound: `binvar` = `binval`  &rArr;  `implvar` &le;/&ge; `implbnd` into a big-M constraint */
810  	static
811  	void implBndToBigM(
812  	   SCIP*                 scip,               /**< SCIP data structure */
813  	   SCIP_VAR**            vars_xwy,           /**< variables in order x,w,y */
814  	   int                   binvarpos,          /**< position of binvar in vars_xwy */
815  	   int                   implvarpos,         /**< position of implvar in vars_xwy */
816  	   SCIP_BOUNDTYPE        bndtype,            /**< type of implied bound */
817  	   SCIP_Bool             binval,             /**< value of binvar which implies the bound */
818  	   SCIP_Real             implbnd,            /**< value of the implied bound */
819  	   SCIP_Real*            coefs,              /**< coefficients of the big-M constraint */
820  	   SCIP_Real*            side                /**< side of the big-M constraint */
821  	   )
822  	{
823  	   SCIP_VAR* implvar;
824  	   SCIP_Real globbnd;
825  	
826  	   assert(vars_xwy != NULL);
827  	   assert(coefs != NULL);
828  	   assert(side != NULL);
829  	   assert(binvarpos != implvarpos);
830  	
831  	   implvar = vars_xwy[implvarpos];
832  	   globbnd = bndtype == SCIP_BOUNDTYPE_LOWER ? SCIPvarGetLbGlobal(implvar) : SCIPvarGetUbGlobal(implvar);
833  	
834  	   /* Depending on the bound type and binval, there are four possibilities:
835  	    * binvar == 1  =>  implvar >= implbnd   <=>   (implvar^l - implbnd)binvar + implvar >= implvar^l;
836  	    * binvar == 0  =>  implvar >= implbnd   <=>   (implbnd - implvar^l)binvar + implvar >= implbnd;
837  	    * binvar == 1  =>  implvar <= implbnd   <=>   (implvar^u - implbnd)binvar + implvar <= implvar^u;
838  	    * binvar == 0  =>  implvar <= implbnd   <=>   (implbnd - implvar^u)binvar + implvar <= implbnd.
839  	    */
840  	
841  	   coefs[0] = 0.0;
842  	   coefs[1] = 0.0;
843  	   coefs[2] = 0.0;
844  	   coefs[binvarpos] = binval ? globbnd - implbnd : implbnd - globbnd;
845  	   coefs[implvarpos] = 1.0;
846  	   *side = binval ? globbnd : implbnd;
847  	
848  	   SCIPdebugMsg(scip, "Got an implied relation with binpos = %d, implpos = %d, implbnd = %g, "
849  	                   "bnd type = %s, binval = %u, glbbnd = %g\n", binvarpos, implvarpos, implbnd,
850  	                   bndtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", binval, globbnd);
851  	   SCIPdebugMsg(scip, "Constructed big-M: %g*bvar + implvar %s %g\n", coefs[binvarpos],
852  	                   bndtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", *side);
853  	}
854  	
855  	/** extract products from a relation given by coefs1, vars, side1 and sidetype1 and
856  	 *  implied bounds of the form `binvar` = `!f` &rArr; `implvar` &ge;/&le; `implbnd`
857  	 */
858  	static
859  	SCIP_RETCODE detectProductsImplbnd(
860  	   SCIP*                 scip,               /**< SCIP data structure */
861  	   SCIP_SEPADATA*        sepadata,           /**< separator data */
862  	   SCIP_Real*            coefs1,             /**< coefficients of the first linear relation */
863  	   SCIP_VAR**            vars_xwy,           /**< variables in the order x, w, y */
864  	   SCIP_Real             side1,              /**< side of the first relation */
865  	   SCIP_SIDETYPE         sidetype1,          /**< is the left or right hand side given for the first relation? */
866  	   int                   binvarpos,          /**< position of the indicator variable in the vars_xwy array */
867  	   int                   implvarpos,         /**< position of the variable that is bounded */
868  	   SCIP_HASHMAP*         varmap,             /**< variable map */
869  	   SCIP_Bool             f                   /**< the value of x that activates the first relation */
870  	   )
871  	{
872  	   SCIP_Real coefs2[3] = { 0., 0., 0. };
873  	   SCIP_Real impllb;
874  	   SCIP_Real implub;
875  	   SCIP_VAR* binvar;
876  	   SCIP_VAR* implvar;
877  	   SCIP_Real side2;
878  	   int i;
879  	   SCIP_Bool binvals[2] = {!f, f};
880  	
881  	   assert(binvarpos != implvarpos);
882  	   assert(implvarpos != 0); /* implied variable must be continuous, therefore it can't be x */
883  	
884  	   binvar = vars_xwy[binvarpos];
885  	   implvar = vars_xwy[implvarpos];
886  	
887  	   assert(SCIPvarGetType(binvar) == SCIP_VARTYPE_BINARY);
888  	   assert(SCIPvarGetType(implvar) != SCIP_VARTYPE_BINARY);
889  	
890  	   /* loop over binvals; if binvar is x (case binvarpos == 0), then we want to use only implications from
891  	    * binvar == !f (which is the option complementing the first relation, which is implied from f); if
892  	    * binvar is not x, this doesn't matter since the implbnd doesn't depend on x, therefore try both !f and f
893  	    */
894  	   for( i = 0; i < (binvarpos == 0 ? 1 : 2); ++i )
895  	   {
896  	      /* get implications binvar == binval  =>  implvar <=/>= implbnd */
897  	      SCIPvarGetImplicVarBounds(binvar, binvals[i], implvar, &impllb, &implub);
898  	
899  	      if( impllb != SCIP_INVALID ) /*lint !e777*/
900  	      {
901  	         /* write the implied bound as a big-M constraint */
902  	         implBndToBigM(scip, vars_xwy, binvarpos, implvarpos, SCIP_BOUNDTYPE_LOWER, binvals[i], impllb, coefs2, &side2);
903  	
904  	         SCIP_CALL( extractProducts(scip, sepadata, vars_xwy, coefs1, coefs2, side1, side2, sidetype1,
905  	               SCIP_SIDETYPE_LEFT, varmap, f) );
906  	      }
907  	
908  	      if( implub != SCIP_INVALID ) /*lint !e777*/
909  	      {
910  	         /* write the implied bound as a big-M constraint */
911  	         implBndToBigM(scip, vars_xwy, binvarpos, implvarpos, SCIP_BOUNDTYPE_UPPER, binvals[i], implub, coefs2, &side2);
912  	
913  	         SCIP_CALL( extractProducts(scip, sepadata, vars_xwy, coefs1, coefs2, side1, side2, sidetype1,
914  	               SCIP_SIDETYPE_RIGHT, varmap, f) );
915  	      }
916  	   }
917  	
918  	   return SCIP_OKAY;
919  	}
920  	
921  	/** extract products from a relation given by `coefs1`, `vars_xwy`, `side1` and `sidetype1` and
922  	 *  cliques containing `vars_xwy[varpos1]` and `vars_xwy[varpos2]`
923  	 */
924  	static
925  	SCIP_RETCODE detectProductsClique(
926  	   SCIP*                 scip,               /**< SCIP data structure */
927  	   SCIP_SEPADATA*        sepadata,           /**< separator data */
928  	   SCIP_Real*            coefs1,             /**< coefficients of the first linear relation */
929  	   SCIP_VAR**            vars_xwy,           /**< variables of the first relation in the order x, w, y */
930  	   SCIP_Real             side1,              /**< side of the first relation */
931  	   SCIP_SIDETYPE         sidetype1,          /**< is the left or right hand side given for the first relation? */
932  	   int                   varpos1,            /**< position of the first variable in the vars_xwy array */
933  	   int                   varpos2,            /**< position of the second variable in the vars_xwy array */
934  	   SCIP_HASHMAP*         varmap,             /**< variable map */
935  	   SCIP_Bool             f                   /**< the value of x that activates the first relation */
936  	   )
937  	{
938  	   SCIP_Real coefs2[3] = { 0., 0., 0. };
939  	   SCIP_VAR* var1;
940  	   SCIP_VAR* var2;
941  	   SCIP_Real side2;
942  	   int i;
943  	   int imax;
944  	   SCIP_Bool binvals[2] = {!f, f};
945  	
946  	   var1 = vars_xwy[varpos1];
947  	   var2 = vars_xwy[varpos2];
948  	
949  	   /* this decides whether we do one or two iterations of the loop for binvals: if var1
950  	    * or var2 is x, we only want cliques with x = !f (which is the option complementing
951  	    * the first relation, which is implied from f); otherwise this doesn't matter since
952  	    * the clique doesn't depend on x, therefore try both !f and f
953  	    */
954  	   imax = (varpos1 == 0 || varpos2 == 0) ? 1 : 2;
955  	
956  	   assert(SCIPvarGetType(var1) == SCIP_VARTYPE_BINARY);
957  	   assert(SCIPvarGetType(var2) == SCIP_VARTYPE_BINARY);
958  	
959  	   for( i = 0; i < imax; ++i )
960  	   {
961  	      /* if var1=TRUE and var2=TRUE are in a clique (binvals[i] == TRUE), the relation var1 + var2 <= 1 is implied
962  	       * if var1=FALSE and var2=TRUE are in a clique (binvals[i] == FALSE), the relation (1 - var1) + var2 <= 1 is implied
963  	       */
964  	      if( SCIPvarsHaveCommonClique(var1, binvals[i], var2, TRUE, TRUE) )
965  	      {
966  	         SCIPdebugMsg(scip, "vars %s<%s> and <%s> are in a clique\n", binvals[i] ? "" : "!", SCIPvarGetName(var1), SCIPvarGetName(var2));
967  	         coefs2[varpos1] = binvals[i] ? 1.0 : -1.0;
968  	         coefs2[varpos2] = 1.0;
969  	         side2 = binvals[i] ? 1.0 : 0.0;
970  	
971  	         SCIP_CALL( extractProducts(scip, sepadata, vars_xwy, coefs1, coefs2, side1, side2, sidetype1,
972  	               SCIP_SIDETYPE_RIGHT, varmap, f) );
973  	      }
974  	
975  	      /* if var1=TRUE and var2=FALSE are in the same clique, the relation var1 + (1-var2) <= 1 is implied
976  	       * if var1=FALSE and var2=FALSE are in the same clique, the relation (1-var1) + (1-var2) <= 1 is implied
977  	       */
978  	      if( SCIPvarsHaveCommonClique(var1, binvals[i], var2, FALSE, TRUE) )
979  	      {
980  	         SCIPdebugMsg(scip, "vars %s<%s> and !<%s> are in a clique\n", binvals[i] ? "" : "!", SCIPvarGetName(var1), SCIPvarGetName(var2));
981  	         coefs2[varpos1] = binvals[i] ? 1.0 : -1.0;
982  	         coefs2[varpos2] = -1.0;
983  	         side2 = binvals[i] ? 0.0 : -1.0;
984  	
985  	         SCIP_CALL( extractProducts(scip, sepadata, vars_xwy, coefs1, coefs2, side1, side2, sidetype1,
986  	               SCIP_SIDETYPE_RIGHT, varmap, f) );
987  	      }
988  	   }
989  	
990  	   return SCIP_OKAY;
991  	}
992  	
993  	
994  	/** extract products from a relation given by `coefs1`, `vars`, `side1` and `sidetype1` and unconditional relations
995  	 * (inequalities with 2 nonzeros) containing `vars[varpos1]` and `vars[varpos2]`
996  	 */
997  	static
998  	SCIP_RETCODE detectProductsUnconditional(
999  	   SCIP*                 scip,               /**< SCIP data structure */
1000 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
1001 	   SCIP_ROW**            rows,               /**< problem rows */
1002 	   int*                  row_list,           /**< linked list of rows corresponding to 2 or 3 var sets */
1003 	   SCIP_HASHTABLE*       hashtable,          /**< hashtable storing unconditional relations */
1004 	   SCIP_Real*            coefs1,             /**< coefficients of the first linear relation */
1005 	   SCIP_VAR**            vars_xwy,           /**< variables of the first relation in the order x, w, y */
1006 	   SCIP_Real             side1,              /**< side of the first relation */
1007 	   SCIP_SIDETYPE         sidetype1,          /**< is the left or right hand side given for the first relation? */
1008 	   int                   varpos1,            /**< position of the first unconditional variable in the vars_xwy array */
1009 	   int                   varpos2,            /**< position of the second unconditional variable in the vars_xwy array */
1010 	   SCIP_HASHMAP*         varmap,             /**< variable map */
1011 	   SCIP_Bool             f                   /**< the value of x that activates the first relation */
1012 	   )
1013 	{
1014 	   HASHDATA hashdata;
1015 	   HASHDATA* foundhashdata;
1016 	   SCIP_ROW* row2;
1017 	   int r2;
1018 	   int pos1;
1019 	   int pos2;
1020 	   SCIP_Real coefs2[3] = { 0., 0., 0. };
1021 	   SCIP_VAR* var1;
1022 	   SCIP_VAR* var2;
1023 	
1024 	   /* always unconditional, therefore x must not be one of the two variables */
1025 	   assert(varpos1 != 0);
1026 	   assert(varpos2 != 0);
1027 	
1028 	   var1 = vars_xwy[varpos1];
1029 	   var2 = vars_xwy[varpos2];
1030 	
1031 	   hashdata.nvars = 2;
1032 	   hashdata.firstrow = -1;
1033 	   if( SCIPvarGetIndex(var1) < SCIPvarGetIndex(var2) )
1034 	   {
1035 	      pos1 = 0;
1036 	      pos2 = 1;
1037 	   }
1038 	   else
1039 	   {
1040 	      pos1 = 1;
1041 	      pos2 = 0;
1042 	   }
1043 	
1044 	   hashdata.vars[pos1] = var1;
1045 	   hashdata.vars[pos2] = var2;
1046 	
1047 	   foundhashdata = (HASHDATA*)SCIPhashtableRetrieve(hashtable, &hashdata);
1048 	
1049 	   if( foundhashdata != NULL )
1050 	   {
1051 	      /* if the var pair exists, use all corresponding rows */
1052 	      r2 = foundhashdata->firstrow;
1053 	
1054 	      while( r2 != -1 )
1055 	      {
1056 	         row2 = rows[r2];
1057 	         assert(SCIProwGetNNonz(row2) == 2);
1058 	         assert(var1 == SCIPcolGetVar(SCIProwGetCols(row2)[pos1]));
1059 	         assert(var2 == SCIPcolGetVar(SCIProwGetCols(row2)[pos2]));
1060 	
1061 	         coefs2[varpos1] = SCIProwGetVals(row2)[pos1];
1062 	         coefs2[varpos2] = SCIProwGetVals(row2)[pos2];
1063 	
1064 	         SCIPdebugMsg(scip, "Unconditional:\n");
1065 	         if( !SCIPisInfinity(scip, -SCIProwGetLhs(row2)) )
1066 	         {
1067 	            SCIP_CALL( extractProducts(scip, sepadata, vars_xwy, coefs1, coefs2, side1,
1068 	                  SCIProwGetLhs(row2) - SCIProwGetConstant(row2), sidetype1, SCIP_SIDETYPE_LEFT, varmap, f) );
1069 	         }
1070 	         if( !SCIPisInfinity(scip,  SCIProwGetRhs(row2)) )
1071 	         {
1072 	            SCIP_CALL( extractProducts(scip, sepadata, vars_xwy, coefs1, coefs2, side1,
1073 	                  SCIProwGetRhs(row2) - SCIProwGetConstant(row2), sidetype1, SCIP_SIDETYPE_RIGHT, varmap, f) );
1074 	         }
1075 	
1076 	         r2 = row_list[r2];
1077 	      }
1078 	   }
1079 	
1080 	   return SCIP_OKAY;
1081 	}
1082 	
1083 	/** finds and stores implied relations (x = f &rArr; ay + bw &le; c, f can be 0 or 1) and 2-variable relations
1084 	 *
1085 	 *  Fills the following:
1086 	 *
1087 	 * - An array of variables that participate in two variable relations; for each such variable, ADJACENTVARDATA
1088 	 *   containing an array of variables that participate in two variable relations together with it; and a hashmap
1089 	 *   mapping variables to ADJACENTVARDATAs.
1090 	 *
1091 	 * - Hashtables storing hashdata objects with the two or three variables and the position of the first row in the
1092 	 *   `prob_rows` array, which in combination with the linked list (described below) will allow access to all rows that
1093 	 *   depend only on the corresponding variables.
1094 	 *
1095 	 * - Linked lists of row indices. Each list corresponds to a pair or triple of variables and contains positions of rows
1096 	 *   which depend only on those variables. All lists are stored in `row_list`, an array of length `nrows`, which is
1097 	 *   possible because each row belongs to at most one list. The array indices of `row_list` represent the positions of
1098 	 *   rows in `prob_rows`, and a value in the `row_list` array represents the next index in the list (-1 if there is no next
1099 	 *   list element). The first index of each list is stored in one of the hashdata objects as firstrow.
1100 	 */
1101 	static
1102 	SCIP_RETCODE fillRelationTables(
1103 	   SCIP*                 scip,               /**< SCIP data structure */
1104 	   SCIP_ROW**            prob_rows,          /**< linear rows of the problem */
1105 	   int                   nrows,              /**< number of rows */
1106 	   SCIP_HASHTABLE*       hashtable2,         /**< hashtable to store 2-variable relations */
1107 	   SCIP_HASHTABLE*       hashtable3,         /**< hashtable to store implied relations */
1108 	   SCIP_HASHMAP*         vars_in_2rels,      /**< connections between variables that appear in 2-variable relations */
1109 	   int*                  row_list            /**< linked lists of row positions for each 2 or 3 variable set */
1110 	   )
1111 	{
1112 	   int r;
1113 	   SCIP_COL** cols;
1114 	   HASHDATA searchhashdata;
1115 	   HASHDATA* elementhashdata;
1116 	
1117 	   assert(prob_rows != NULL);
1118 	   assert(nrows > 0);
1119 	   assert(hashtable2 != NULL);
1120 	   assert(hashtable3 != NULL);
1121 	   assert(vars_in_2rels != NULL);
1122 	   assert(row_list != NULL);
1123 	
1124 	   for( r = 0; r < nrows; ++r )
1125 	   {
1126 	      assert(prob_rows[r] != NULL);
1127 	
1128 	      cols = SCIProwGetCols(prob_rows[r]);
1129 	      assert(cols != NULL);
1130 	
1131 	      /* initialise with the "end of list" value */
1132 	      row_list[r] = -1;
1133 	
1134 	      /* look for unconditional relations with 2 variables */
1135 	      if( SCIProwGetNNonz(prob_rows[r]) == 2 )
1136 	      {
1137 	         /* if at least one of the variables is binary, this is either an implied bound
1138 	          * or a clique; these are covered separately */
1139 	         if( SCIPvarGetType(SCIPcolGetVar(cols[0])) == SCIP_VARTYPE_BINARY ||
1140 	             SCIPvarGetType(SCIPcolGetVar(cols[1])) == SCIP_VARTYPE_BINARY )
1141 	         {
1142 	            SCIPdebugMsg(scip, "ignoring relation <%s> because a var is binary\n", SCIProwGetName(prob_rows[r]));
1143 	            continue;
1144 	         }
1145 	
1146 	         /* fill in searchhashdata so that to search for the two variables in hashtable2 */
1147 	         searchhashdata.nvars = 2;
1148 	         searchhashdata.firstrow = -1;
1149 	         searchhashdata.vars[0] = SCIPcolGetVar(cols[0]);
1150 	         searchhashdata.vars[1] = SCIPcolGetVar(cols[1]);
1151 	
1152 	         /* get the element corresponding to the two variables */
1153 	         elementhashdata = (HASHDATA*)SCIPhashtableRetrieve(hashtable2, &searchhashdata);
1154 	
1155 	         if( elementhashdata != NULL )
1156 	         {
1157 	            /* if element exists, update it by adding the row */
1158 	            row_list[r] = elementhashdata->firstrow;
1159 	            elementhashdata->firstrow = r;
1160 	            ++elementhashdata->nrows;
1161 	         }
1162 	         else
1163 	         {
1164 	            /* create an element for the combination of two variables */
1165 	            SCIP_CALL( SCIPallocBuffer(scip, &elementhashdata) );
1166 	
1167 	            elementhashdata->nvars = 2;
1168 	            elementhashdata->nrows = 1;
1169 	            elementhashdata->vars[0] = searchhashdata.vars[0];
1170 	            elementhashdata->vars[1] = searchhashdata.vars[1];
1171 	            elementhashdata->firstrow = r;
1172 	
1173 	            SCIP_CALL( SCIPhashtableInsert(hashtable2, (void*)elementhashdata) );
1174 	
1175 	            /* hashdata.vars are two variables participating together in a two variable relation, therefore update
1176 	             * these variables' adjacency data
1177 	             */
1178 	            SCIP_CALL( addAdjacentVars(scip, vars_in_2rels, searchhashdata.vars) );
1179 	         }
1180 	      }
1181 	
1182 	      /* look for implied relations (three variables, at least one binary variable) */
1183 	      if( SCIProwGetNNonz(prob_rows[r]) == 3 )
1184 	      {
1185 	         /* an implied relation contains at least one binary variable */
1186 	         if( SCIPvarGetType(SCIPcolGetVar(cols[0])) != SCIP_VARTYPE_BINARY &&
1187 	             SCIPvarGetType(SCIPcolGetVar(cols[1])) != SCIP_VARTYPE_BINARY &&
1188 	             SCIPvarGetType(SCIPcolGetVar(cols[2])) != SCIP_VARTYPE_BINARY )
1189 	            continue;
1190 	
1191 	         /* fill in hashdata so that to search for the three variables in hashtable3 */
1192 	         searchhashdata.nvars = 3;
1193 	         searchhashdata.firstrow = -1;
1194 	         searchhashdata.vars[0] = SCIPcolGetVar(cols[0]);
1195 	         searchhashdata.vars[1] = SCIPcolGetVar(cols[1]);
1196 	         searchhashdata.vars[2] = SCIPcolGetVar(cols[2]);
1197 	
1198 	         /* get the element corresponding to the three variables */
1199 	         elementhashdata = (HASHDATA*)SCIPhashtableRetrieve(hashtable3, &searchhashdata);
1200 	
1201 	         if( elementhashdata != NULL )
1202 	         {
1203 	            /* if element exists, update it by adding the row */
1204 	            row_list[r] = elementhashdata->firstrow;
1205 	            elementhashdata->firstrow = r;
1206 	            ++elementhashdata->nrows;
1207 	         }
1208 	         else
1209 	         {
1210 	            /* create an element for the combination of three variables */
1211 	            SCIP_CALL( SCIPallocBuffer(scip, &elementhashdata) );
1212 	
1213 	            elementhashdata->nvars = 3;
1214 	            elementhashdata->nrows = 1;
1215 	            elementhashdata->vars[0] = searchhashdata.vars[0];
1216 	            elementhashdata->vars[1] = searchhashdata.vars[1];
1217 	            elementhashdata->vars[2] = searchhashdata.vars[2];
1218 	            elementhashdata->firstrow = r;
1219 	
1220 	            SCIP_CALL( SCIPhashtableInsert(hashtable3, (void*)elementhashdata) );
1221 	         }
1222 	      }
1223 	   }
1224 	
1225 	   return SCIP_OKAY;
1226 	}
1227 	
1228 	/** detect bilinear products encoded in linear constraints */
1229 	static
1230 	SCIP_RETCODE detectHiddenProducts(
1231 	   SCIP*                 scip,               /**< SCIP data structure */
1232 	   SCIP_SEPADATA*        sepadata,           /**< separation data */
1233 	   SCIP_HASHMAP*         varmap              /**< variable map */
1234 	   )
1235 	{
1236 	   int r1; /* first relation index */
1237 	   int r2; /* second relation index */
1238 	   int i; /* outer loop counter */
1239 	   int permwy; /* index for permuting w and y */
1240 	   int nrows;
1241 	   SCIP_ROW** prob_rows;
1242 	   SCIP_HASHTABLE* hashtable3;
1243 	   SCIP_HASHTABLE* hashtable2;
1244 	   HASHDATA* foundhashdata;
1245 	   SCIP_VAR* vars_xwy[3];
1246 	   SCIP_Real coefs1[3];
1247 	   SCIP_Real coefs2[3];
1248 	   SCIP_ROW* row1;
1249 	   SCIP_ROW* row2;
1250 	   int xpos;
1251 	   int ypos;
1252 	   int wpos;
1253 	   int f; /* value of the binary variable */
1254 	   SCIP_VAR** relatedvars;
1255 	   int nrelatedvars;
1256 	   SCIP_Bool xfixing;
1257 	   SCIP_SIDETYPE sidetype1;
1258 	   SCIP_SIDETYPE sidetype2;
1259 	   SCIP_Real side1;
1260 	   SCIP_Real side2;
1261 	   int* row_list;
1262 	   SCIP_HASHMAP* vars_in_2rels;
1263 	   int nvars;
1264 	
1265 	   /* get the (original) rows */
(1) Event cond_false: Condition "(_restat_ = getOriginalRows(scip, &prob_rows, &nrows)) != SCIP_OKAY", taking false branch.
(2) Event if_end: End of if statement.
1266 	   SCIP_CALL( getOriginalRows(scip, &prob_rows, &nrows) );
1267 	
(3) Event cond_false: Condition "nrows == 0", taking false branch.
1268 	   if( nrows == 0 )
1269 	   {
1270 	      SCIPfreeBufferArray(scip, &prob_rows);
1271 	      return SCIP_OKAY;
(4) Event if_end: End of if statement.
1272 	   }
1273 	
1274 	   /* create tables of implied and unconditional relations */
(5) Event cond_false: Condition "(_restat_ = SCIPhashtableCreate(&hashtable3, SCIPblkmem(scip), nrows, SCIPhashGetKeyStandard, hashdataKeyEqConss, hashdataKeyValConss, NULL)) != SCIP_OKAY", taking false branch.
(6) Event if_end: End of if statement.
1275 	   SCIP_CALL( SCIPhashtableCreate(&hashtable3, SCIPblkmem(scip), nrows, SCIPhashGetKeyStandard,
1276 	      hashdataKeyEqConss, hashdataKeyValConss, NULL) );
(7) Event cond_false: Condition "(_restat_ = SCIPhashtableCreate(&hashtable2, SCIPblkmem(scip), nrows, SCIPhashGetKeyStandard, hashdataKeyEqConss, hashdataKeyValConss, NULL)) != SCIP_OKAY", taking false branch.
(8) Event if_end: End of if statement.
1277 	   SCIP_CALL( SCIPhashtableCreate(&hashtable2, SCIPblkmem(scip), nrows, SCIPhashGetKeyStandard,
1278 	      hashdataKeyEqConss, hashdataKeyValConss, NULL) );
(9) Event cond_false: Condition "(row_list = BMSallocBufferMemoryArray_call(SCIPbuffer(scip), (size_t)(ptrdiff_t)nrows, 4UL /* sizeof (*row_list) */, "/sapmnt/home1/d029903/my_work/SCIPSoPlex_coverity/scip-soplex-9.0.0_rc1/scip/src/scip/sepa_rlt.c", 1279)) == NULL", taking false branch.
(10) Event cond_false: Condition "(_restat_ = (((row_list = BMSallocBufferMemoryArray_call(SCIPbuffer(scip), (size_t)(ptrdiff_t)nrows, 4UL /* sizeof (*row_list) */, "/sapmnt/home1/d029903/my_work/SCIPSoPlex_coverity/scip-soplex-9.0.0_rc1/scip/src/scip/sepa_rlt.c", 1279)) == NULL) ? SCIP_NOMEMORY : SCIP_OKAY)) != SCIP_OKAY", taking false branch.
(11) Event if_end: End of if statement.
1279 	   SCIP_CALL( SCIPallocBufferArray(scip, &row_list, nrows) );
1280 	
1281 	   /* allocate the adjacency data map for variables that appear in 2-var relations */
1282 	   nvars = SCIPgetNVars(scip);
(12) Event cond_true: Condition "nvars <= nrows * 2", taking true branch.
(13) Event cond_false: Condition "(_restat_ = SCIPhashmapCreate(&vars_in_2rels, SCIPblkmem(scip), ((nvars <= nrows * 2) ? nvars : (nrows * 2)))) != SCIP_OKAY", taking false branch.
(14) Event if_end: End of if statement.
1283 	   SCIP_CALL( SCIPhashmapCreate(&vars_in_2rels, SCIPblkmem(scip), MIN(nvars, nrows * 2)) );
1284 	
1285 	   /* fill the data structures that will be used for product detection: hashtables and linked lists allowing to access
1286 	    * two and three variable relations by the variables; and the hashmap for accessing variables participating in two
1287 	    * variable relations with each given variable */
(15) Event cond_false: Condition "(_restat_ = fillRelationTables(scip, prob_rows, nrows, hashtable2, hashtable3, vars_in_2rels, row_list)) != SCIP_OKAY", taking false branch.
(16) Event if_end: End of if statement.
1288 	   SCIP_CALL( fillRelationTables(scip, prob_rows, nrows, hashtable2, hashtable3, vars_in_2rels, row_list) );
1289 	
1290 	   /* start actually looking for products */
1291 	   /* go through all sets of three variables */
(17) Event cond_true: Condition "i < SCIPhashtableGetNEntries(hashtable3)", taking true branch.
(21) Event cond_true: Condition "i < SCIPhashtableGetNEntries(hashtable3)", taking true branch.
(25) Event cond_true: Condition "i < SCIPhashtableGetNEntries(hashtable3)", taking true branch.
1292 	   for( i = 0; i < SCIPhashtableGetNEntries(hashtable3); ++i )
1293 	   {
1294 	      foundhashdata = (HASHDATA*)SCIPhashtableGetEntry(hashtable3, i);
(18) Event cond_true: Condition "foundhashdata == NULL", taking true branch.
(22) Event cond_true: Condition "foundhashdata == NULL", taking true branch.
(26) Event cond_false: Condition "foundhashdata == NULL", taking false branch.
1295 	      if( foundhashdata == NULL )
(19) Event continue: Continuing loop.
(23) Event continue: Continuing loop.
(27) Event if_end: End of if statement.
1296 	         continue;
1297 	
(28) Event cond_false: Condition "0", taking false branch.
1298 	      SCIPdebugMsg(scip, "(<%s>, <%s>, <%s>): ", SCIPvarGetName(foundhashdata->vars[0]),
(29) Event loop_end: Reached end of loop.
1299 	         SCIPvarGetName(foundhashdata->vars[1]), SCIPvarGetName(foundhashdata->vars[2]));
1300 	
1301 	      /* An implied relation has the form: x == f  =>  l(w,y) <=/>= side (f is 0 or 1, l is a linear function). Given
1302 	       * a linear relation with three variables, any binary var can be x: we try them all here because this can
1303 	       * produce different products.
1304 	       */
(30) Event cond_true: Condition "xpos < 3", taking true branch.
(34) Event cond_true: Condition "xpos < 3", taking true branch.
(38) Event cond_true: Condition "xpos < 3", taking true branch.
1305 	      for( xpos = 0; xpos < 3; ++xpos )
1306 	      {
1307 	         /* in vars_xwy, the order of variables is always as in the name: x, w, y */
1308 	         vars_xwy[0] = foundhashdata->vars[xpos];
1309 	
1310 	         /* x must be binary */
(31) Event cond_true: Condition "(SCIP_VARTYPE)vars_xwy[0]->vartype != SCIP_VARTYPE_BINARY", taking true branch.
(35) Event cond_true: Condition "(SCIP_VARTYPE)vars_xwy[0]->vartype != SCIP_VARTYPE_BINARY", taking true branch.
(39) Event cond_false: Condition "(SCIP_VARTYPE)vars_xwy[0]->vartype != SCIP_VARTYPE_BINARY", taking false branch.
1311 	         if( SCIPvarGetType(vars_xwy[0]) != SCIP_VARTYPE_BINARY )
(32) Event continue: Continuing loop.
(36) Event continue: Continuing loop.
(40) Event if_end: End of if statement.
1312 	            continue;
1313 	
1314 	         /* the first row might be an implication from f == 0 or f == 1: try both */
(41) Event cond_true: Condition "f <= 1", taking true branch.
1315 	         for( f = 0; f <= 1; ++f )
1316 	         {
(42) Event cond_false: Condition "f == 1", taking false branch.
1317 	            xfixing = f == 1;
1318 	
1319 	            /* go through implied relations for the corresponding three variables */
(43) Event cond_true: Condition "r1 != -1", taking true branch.
(51) Event cond_true: Condition "r1 != -1", taking true branch.
1320 	            for( r1 = foundhashdata->firstrow; r1 != -1; r1 = row_list[r1] )
1321 	            {
1322 	               /* get the implied relation */
1323 	               row1 = prob_rows[r1];
1324 	
1325 	               assert(SCIProwGetNNonz(row1) == 3);
1326 	               /* the order of variables in all rows should be the same, and similar to the order in hashdata->vars,
1327 	                * therefore the x variable from vars_xwy should be similar to the column variable at xpos
1328 	                */
1329 	               assert(vars_xwy[0] == SCIPcolGetVar(SCIProwGetCols(row1)[xpos]));
1330 	
1331 	               coefs1[0] = SCIProwGetVals(row1)[xpos];
1332 	
1333 	               /* use the side for which the inequality becomes tighter when x == xfixing than when x == !xfixing */
(44) Event cond_true: Condition "!xfixing", taking true branch.
(45) Event cond_true: Condition "coefs1[0] > 0.", taking true branch.
(52) Event cond_true: Condition "!xfixing", taking true branch.
(53) Event cond_true: Condition "coefs1[0] > 0.", taking true branch.
1334 	               if( (!xfixing && coefs1[0] > 0.0) || (xfixing && coefs1[0] < 0.0) )
1335 	               {
1336 	                  sidetype1 = SCIP_SIDETYPE_LEFT;
1337 	                  side1 = SCIProwGetLhs(row1);
(46) Event if_fallthrough: Falling through to end of if statement.
(54) Event if_fallthrough: Falling through to end of if statement.
1338 	               }
1339 	               else
1340 	               {
1341 	                  sidetype1 = SCIP_SIDETYPE_RIGHT;
1342 	                  side1 = SCIProwGetRhs(row1);
(47) Event if_end: End of if statement.
(55) Event if_end: End of if statement.
1343 	               }
1344 	
(48) Event cond_true: Condition "fabs(side1) >= scip->set->num_infinity", taking true branch.
(56) Event cond_false: Condition "fabs(side1) >= scip->set->num_infinity", taking false branch.
1345 	               if( SCIPisInfinity(scip, REALABS(side1)) )
(49) Event continue: Continuing loop.
(57) Event if_end: End of if statement.
1346 	                  continue;
1347 	
1348 	               side1 -= SCIProwGetConstant(row1);
1349 	
1350 	               /* permute w and y */
(58) Event cond_true: Condition "permwy <= 2", taking true branch.
1351 	               for( permwy = 1; permwy <= 2; ++permwy )
1352 	               {
1353 	                  wpos = (xpos + permwy) % 3;
1354 	                  ypos = (xpos - permwy + 3) % 3;
1355 	                  vars_xwy[1] = foundhashdata->vars[wpos];
1356 	                  vars_xwy[2] = foundhashdata->vars[ypos];
1357 	
1358 	                  assert(vars_xwy[1] == SCIPcolGetVar(SCIProwGetCols(row1)[wpos]));
1359 	                  assert(vars_xwy[2] == SCIPcolGetVar(SCIProwGetCols(row1)[ypos]));
1360 	
1361 	                  coefs1[1] = SCIProwGetVals(row1)[wpos];
1362 	                  coefs1[2] = SCIProwGetVals(row1)[ypos];
1363 	
1364 	                  /* look for the second relation: it should be tighter when x == !xfixing than when x == xfixing
1365 	                   * and can be either another implied relation or one of several types of two and one variable
1366 	                   * relations
1367 	                   */
1368 	
1369 	                  /* go through the remaining rows (implied relations) for these three variables */
(59) Event cond_true: Condition "r2 != -1", taking true branch.
(67) Event cond_true: Condition "r2 != -1", taking true branch.
(79) Event loop_begin: Jumped back to beginning of loop.
(80) Event cond_true: Condition "r2 != -1", taking true branch.
1370 	                  for( r2 = row_list[r1]; r2 != -1; r2 = row_list[r2] )
1371 	                  {
1372 	                     /* get the second implied relation */
1373 	                     row2 = prob_rows[r2];
1374 	
1375 	                     assert(SCIProwGetNNonz(row2) == 3);
1376 	                     assert(vars_xwy[0] == SCIPcolGetVar(SCIProwGetCols(row2)[xpos]));
1377 	                     assert(vars_xwy[1] == SCIPcolGetVar(SCIProwGetCols(row2)[wpos]));
1378 	                     assert(vars_xwy[2] == SCIPcolGetVar(SCIProwGetCols(row2)[ypos]));
1379 	
1380 	                     coefs2[0] = SCIProwGetVals(row2)[xpos];
1381 	                     coefs2[1] = SCIProwGetVals(row2)[wpos];
1382 	                     coefs2[2] = SCIProwGetVals(row2)[ypos];
1383 	
1384 	                     /* use the side for which the inequality becomes tighter when x == !xfixing than when x == xfixing */
(60) Event cond_true: Condition "!xfixing", taking true branch.
(61) Event cond_true: Condition "coefs2[0] > 0.", taking true branch.
(68) Event cond_true: Condition "!xfixing", taking true branch.
(69) Event cond_true: Condition "coefs2[0] > 0.", taking true branch.
(81) Event cond_true: Condition "!xfixing", taking true branch.
(82) Event cond_false: Condition "coefs2[0] > 0.", taking false branch.
(83) Event cond_false: Condition "xfixing", taking false branch.
1385 	                     if( (!xfixing && coefs2[0] > 0.0) || (xfixing && coefs2[0] < 0.0) )
1386 	                     {
1387 	                        sidetype2 = SCIP_SIDETYPE_RIGHT;
1388 	                        side2 = SCIProwGetRhs(row2);
(62) Event if_fallthrough: Falling through to end of if statement.
(70) Event if_fallthrough: Falling through to end of if statement.
1389 	                     }
1390 	                     else
(84) Event else_branch: Reached else branch.
1391 	                     {
1392 	                        sidetype2 = SCIP_SIDETYPE_LEFT;
1393 	                        side2 = SCIProwGetLhs(row2);
(63) Event if_end: End of if statement.
(71) Event if_end: End of if statement.
1394 	                     }
1395 	
(64) Event cond_true: Condition "fabs(side2) >= scip->set->num_infinity", taking true branch.
(72) Event cond_false: Condition "fabs(side2) >= scip->set->num_infinity", taking false branch.
(85) Event cond_false: Condition "fabs(side2) >= scip->set->num_infinity", taking false branch.
1396 	                     if( SCIPisInfinity(scip, REALABS(side2)) )
(65) Event continue: Continuing loop.
(73) Event if_end: End of if statement.
(86) Event if_end: End of if statement.
1397 	                        continue;
1398 	
1399 	                     side2 -= SCIProwGetConstant(row2);
1400 	
(74) Event cond_false: Condition "0", taking false branch.
(75) Event loop_end: Reached end of loop.
(87) Event cond_false: Condition "0", taking false branch.
(88) Event loop_end: Reached end of loop.
1401 	                     SCIPdebugMsg(scip, "Two implied relations:\n");
(76) Event cond_false: Condition "(_restat_ = extractProducts(scip, sepadata, vars_xwy, coefs1, coefs2, side1, side2, sidetype1, sidetype2, varmap, xfixing)) != SCIP_OKAY", taking false branch.
(77) Event if_end: End of if statement.
(89) Event deref_parm_in_call: Function "extractProducts" dereferences "sepadata->varssorted". [details]
1402 	                     SCIP_CALL( extractProducts(scip, sepadata, vars_xwy, coefs1, coefs2, side1, side2, sidetype1,
1403 	                        sidetype2, varmap, xfixing) );
(66) Event loop: Looping back.
(78) Event loop: Jumping back to the beginning of the loop.
1404 	                  }
1405 	
1406 	                  /* use global bounds on w */
1407 	                  coefs2[0] = 0.0;
1408 	                  coefs2[1] = 1.0;
1409 	                  coefs2[2] = 0.0;
1410 	                  SCIPdebugMsg(scip, "w global bounds:\n");
1411 	                  if( !SCIPisInfinity(scip, -SCIPvarGetLbGlobal(vars_xwy[1])) )
1412 	                  {
1413 	                     SCIP_CALL( extractProducts(scip, sepadata, vars_xwy, coefs1, coefs2, side1,
1414 	                        SCIPvarGetLbGlobal(vars_xwy[1]), sidetype1, SCIP_SIDETYPE_LEFT, varmap, xfixing) );
1415 	                  }
1416 	
1417 	                  if( !SCIPisInfinity(scip, SCIPvarGetUbGlobal(vars_xwy[1])) )
1418 	                  {
1419 	                     SCIP_CALL( extractProducts(scip, sepadata, vars_xwy, coefs1, coefs2, side1,
1420 	                        SCIPvarGetUbGlobal(vars_xwy[1]), sidetype1, SCIP_SIDETYPE_RIGHT, varmap, xfixing) );
1421 	                  }
1422 	
1423 	                  /* use implied bounds and cliques with w */
1424 	                  if( SCIPvarGetType(vars_xwy[1]) != SCIP_VARTYPE_BINARY )
1425 	                  {
1426 	                     /* w is non-binary - look for implied bounds x == !f => w >=/<= bound */
1427 	                     SCIPdebugMsg(scip, "Implied relation + implied bounds on w:\n");
1428 	                     SCIP_CALL( detectProductsImplbnd(scip, sepadata, coefs1, vars_xwy, side1, sidetype1, 0, 1,
1429 	                           varmap, xfixing) );
1430 	                  }
1431 	                  else
1432 	                  {
1433 	                     /* w is binary - look for cliques containing x and w */
1434 	                     SCIPdebugMsg(scip, "Implied relation + cliques with x and w:\n");
1435 	                     SCIP_CALL( detectProductsClique(scip, sepadata, coefs1, vars_xwy, side1, sidetype1, 0, 1,
1436 	                           varmap, xfixing) );
1437 	                  }
1438 	
1439 	                  /* use unconditional relations (i.e. relations of w and y) */
1440 	
1441 	                  /* implied bound w == 0/1 => y >=/<= bound */
1442 	                  if( SCIPvarGetType(vars_xwy[1]) == SCIP_VARTYPE_BINARY && SCIPvarGetType(vars_xwy[2]) != SCIP_VARTYPE_BINARY )
1443 	                  {
1444 	                     SCIPdebugMsg(scip, "Implied relation + implied bounds with w and y:\n");
1445 	                     SCIP_CALL( detectProductsImplbnd(scip, sepadata, coefs1, vars_xwy, side1, sidetype1, 1, 2, varmap, xfixing) );
1446 	                  }
1447 	
1448 	                  /* implied bound y == 0/1 => w >=/<= bound */
1449 	                  if( SCIPvarGetType(vars_xwy[2]) == SCIP_VARTYPE_BINARY && SCIPvarGetType(vars_xwy[1]) != SCIP_VARTYPE_BINARY )
1450 	                  {
1451 	                     SCIPdebugMsg(scip, "Implied relation + implied bounds with y and w:\n");
1452 	                     SCIP_CALL( detectProductsImplbnd(scip, sepadata, coefs1, vars_xwy, side1, sidetype1, 2, 1, varmap, xfixing) );
1453 	                  }
1454 	
1455 	                  /* cliques containing w and y */
1456 	                  if( SCIPvarGetType(vars_xwy[1]) == SCIP_VARTYPE_BINARY && SCIPvarGetType(vars_xwy[2]) == SCIP_VARTYPE_BINARY )
1457 	                  {
1458 	                     SCIPdebugMsg(scip, "Implied relation + cliques with w and y:\n");
1459 	                     SCIP_CALL( detectProductsClique(scip, sepadata, coefs1, vars_xwy, side1, sidetype1, 1, 2, varmap, xfixing) );
1460 	                  }
1461 	
1462 	                  /* inequalities containing w and y */
1463 	                  if( SCIPvarGetType(vars_xwy[1]) != SCIP_VARTYPE_BINARY && SCIPvarGetType(vars_xwy[2]) != SCIP_VARTYPE_BINARY )
1464 	                  {
1465 	                     SCIPdebugMsg(scip, "Implied relation + unconditional with w and y:\n");
1466 	                     SCIP_CALL( detectProductsUnconditional(scip, sepadata, prob_rows, row_list, hashtable2, coefs1,
1467 	                        vars_xwy, side1, sidetype1, 1, 2, varmap, xfixing) );
1468 	                  }
1469 	               }
(50) Event loop: Looping back.
1470 	            }
1471 	         }
(33) Event loop: Looping back.
(37) Event loop: Looping back.
1472 	      }
1473 	      SCIPfreeBuffer(scip, &foundhashdata);
(20) Event loop: Looping back.
(24) Event loop: Looping back.
1474 	   }
1475 	
1476 	   /* also loop through implied bounds to look for products */
1477 	   for( i = 0; i < SCIPgetNBinVars(scip); ++i )
1478 	   {
1479 	      /* first choose the x variable: it can be any binary variable in the problem */
1480 	      vars_xwy[0] = SCIPgetVars(scip)[i];
1481 	
1482 	      assert(SCIPvarGetType(vars_xwy[0]) == SCIP_VARTYPE_BINARY);
1483 	
1484 	      /* consider both possible values of x */
1485 	      for( f = 0; f <= 1; ++f )
1486 	      {
1487 	         xfixing = f == 1;
1488 	
1489 	         /* go through implications of x */
1490 	         for( r1 = 0; r1 < SCIPvarGetNImpls(vars_xwy[0], xfixing); ++r1 )
1491 	         {
1492 	            /* w is the implication var */
1493 	            vars_xwy[1] = SCIPvarGetImplVars(vars_xwy[0], xfixing)[r1];
1494 	            assert(SCIPvarGetType(vars_xwy[1]) != SCIP_VARTYPE_BINARY);
1495 	
1496 	            /* write the implication as a big-M constraint */
1497 	            implBndToBigM(scip, vars_xwy, 0, 1, SCIPvarGetImplTypes(vars_xwy[0], xfixing)[r1], xfixing,
1498 	                  SCIPvarGetImplBounds(vars_xwy[0], xfixing)[r1], coefs1, &side1);
1499 	            sidetype1 = SCIPvarGetImplTypes(vars_xwy[0], xfixing)[r1] == SCIP_BOUNDTYPE_LOWER ?
1500 	                     SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT;
1501 	
1502 	            /* if the global bound is equal to the implied bound, there is nothing to do */
1503 	            if( SCIPisZero(scip, coefs1[0]) )
1504 	               continue;
1505 	
1506 	            SCIPdebugMsg(scip, "Implication %s == %u  =>  %s %s %g\n", SCIPvarGetName(vars_xwy[0]), xfixing,
1507 	                  SCIPvarGetName(vars_xwy[1]), sidetype1 == SCIP_SIDETYPE_LEFT ? ">=" : "<=",
1508 	                  SCIPvarGetImplBounds(vars_xwy[0], xfixing)[r1]);
1509 	            SCIPdebugMsg(scip, "Written as big-M: %g%s + %s %s %g\n", coefs1[0], SCIPvarGetName(vars_xwy[0]),
1510 	                  SCIPvarGetName(vars_xwy[1]), sidetype1 == SCIP_SIDETYPE_LEFT ? ">=" : "<=", side1);
1511 	
1512 	            /* the second relation is in w and y (y could be anything, but must be in relation with w) */
1513 	
1514 	            /* x does not participate in the second relation, so we immediately set its coefficient to 0.0 */
1515 	            coefs2[0] = 0.0;
1516 	
1517 	            SCIPdebugMsg(scip, "Implic of x = <%s> + implied lb on w = <%s>:\n", SCIPvarGetName(vars_xwy[0]), SCIPvarGetName(vars_xwy[1]));
1518 	
1519 	            /* use implied lower bounds on w: w >= b*y + d */
1520 	            for( r2 = 0; r2 < SCIPvarGetNVlbs(vars_xwy[1]); ++r2 )
1521 	            {
1522 	               vars_xwy[2] = SCIPvarGetVlbVars(vars_xwy[1])[r2];
1523 	               if( vars_xwy[2] == vars_xwy[0] )
1524 	                  continue;
1525 	
1526 	               coefs2[1] = 1.0;
1527 	               coefs2[2] = -SCIPvarGetVlbCoefs(vars_xwy[1])[r2];
1528 	
1529 	               SCIP_CALL( extractProducts(scip, sepadata, vars_xwy, coefs1, coefs2, side1,
1530 	                  SCIPvarGetVlbConstants(vars_xwy[1])[r2], sidetype1, SCIP_SIDETYPE_LEFT, varmap, xfixing) );
1531 	            }
1532 	
1533 	            SCIPdebugMsg(scip, "Implic of x = <%s> + implied ub on w = <%s>:\n", SCIPvarGetName(vars_xwy[0]), SCIPvarGetName(vars_xwy[1]));
1534 	
1535 	            /* use implied upper bounds on w: w <= b*y + d */
1536 	            for( r2 = 0; r2 < SCIPvarGetNVubs(vars_xwy[1]); ++r2 )
1537 	            {
1538 	               vars_xwy[2] = SCIPvarGetVubVars(vars_xwy[1])[r2];
1539 	               if( vars_xwy[2] == vars_xwy[0] )
1540 	                  continue;
1541 	
1542 	               coefs2[1] = 1.0;
1543 	               coefs2[2] = -SCIPvarGetVubCoefs(vars_xwy[1])[r2];
1544 	
1545 	               SCIP_CALL( extractProducts(scip, sepadata, vars_xwy, coefs1, coefs2, side1,
1546 	                  SCIPvarGetVubConstants(vars_xwy[1])[r2], sidetype1, SCIP_SIDETYPE_RIGHT, varmap, xfixing) );
1547 	            }
1548 	
1549 	            /* use unconditional relations containing w */
1550 	            relatedvars = getAdjacentVars(vars_in_2rels, vars_xwy[1], &nrelatedvars);
1551 	            if( relatedvars == NULL )
1552 	               continue;
1553 	
1554 	            for( r2 = 0; r2 < nrelatedvars; ++r2 )
1555 	            {
1556 	               vars_xwy[2] = relatedvars[r2];
1557 	               SCIPdebugMsg(scip, "Implied bound + unconditional with w and y:\n");
1558 	               SCIP_CALL( detectProductsUnconditional(scip, sepadata, prob_rows, row_list, hashtable2, coefs1,
1559 	                  vars_xwy, side1, sidetype1, 1, 2, varmap, xfixing) );
1560 	            }
1561 	         }
1562 	      }
1563 	   }
1564 	
1565 	   /* free memory */
1566 	   clearVarAdjacency(scip, vars_in_2rels);
1567 	   SCIPhashmapFree(&vars_in_2rels);
1568 	
1569 	   SCIPdebugMsg(scip, "Unconditional relations table:\n");
1570 	   for( i = 0; i < SCIPhashtableGetNEntries(hashtable2); ++i )
1571 	   {
1572 	      foundhashdata = (HASHDATA*)SCIPhashtableGetEntry(hashtable2, i);
1573 	      if( foundhashdata == NULL )
1574 	         continue;
1575 	
1576 	      SCIPdebugMsg(scip, "(%s, %s): ", SCIPvarGetName(foundhashdata->vars[0]),
1577 	                   SCIPvarGetName(foundhashdata->vars[1]));
1578 	
1579 	      SCIPfreeBuffer(scip, &foundhashdata);
1580 	   }
1581 	
1582 	   SCIPfreeBufferArray(scip, &row_list);
1583 	
1584 	   SCIPhashtableFree(&hashtable2);
1585 	   SCIPhashtableFree(&hashtable3);
1586 	
1587 	   SCIPfreeBufferArray(scip, &prob_rows);
1588 	
1589 	   return SCIP_OKAY;
1590 	}
1591 	
1592 	/** helper method to create separation data */
1593 	static
1594 	SCIP_RETCODE createSepaData(
1595 	   SCIP*                 scip,               /**< SCIP data structure */
1596 	   SCIP_SEPADATA*        sepadata            /**< separation data */
1597 	   )
1598 	{
1599 	   SCIP_HASHMAP* varmap;
1600 	   int i;
1601 	   SCIP_CONSNONLINEAR_BILINTERM* bilinterms;
1602 	   int varmapsize;
1603 	   int nvars;
1604 	
1605 	   assert(sepadata != NULL);
1606 	
1607 	   /* initialize some fields of sepadata */
(1) Event assign_zero: Assigning: "sepadata->varssorted" = "NULL".
Also see events: [var_deref_model]
1608 	   sepadata->varssorted = NULL;
1609 	   sepadata->varpriorities = NULL;
1610 	   sepadata->bilinvardatamap = NULL;
1611 	   sepadata->eqauxexpr = NULL;
1612 	   sepadata->nbilinvars = 0;
1613 	   sepadata->sbilinvars = 0;
1614 	
1615 	   /* get total number of bilinear terms */
1616 	   sepadata->nbilinterms = SCIPgetNBilinTermsNonlinear(sepadata->conshdlr);
1617 	
1618 	   /* skip if there are no bilinear terms and implicit product detection is off */
(2) Event cond_false: Condition "sepadata->nbilinterms == 0", taking false branch.
1619 	   if( sepadata->nbilinterms == 0 && !sepadata->detecthidden )
(3) Event if_end: End of if statement.
1620 	      return SCIP_OKAY;
1621 	
1622 	   /* the number of variables participating in bilinear products cannot exceed twice the number of bilinear terms;
1623 	    * however, if we detect hidden products, the number of terms is yet unknown, so use the number of variables
1624 	    */
1625 	   nvars = SCIPgetNVars(scip);
(4) Event cond_true: Condition "sepadata->detecthidden", taking true branch.
1626 	   varmapsize = sepadata->detecthidden ? nvars : MIN(nvars, sepadata->nbilinterms * 2);
1627 	
1628 	   /* create variable map */
(5) Event cond_false: Condition "(_restat_ = SCIPhashmapCreate(&varmap, SCIPblkmem(scip), varmapsize)) != SCIP_OKAY", taking false branch.
(6) Event if_end: End of if statement.
1629 	   SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), varmapsize) );
1630 	
1631 	   /* get all bilinear terms from the nonlinear constraint handler */
1632 	   bilinterms = SCIPgetBilinTermsNonlinear(sepadata->conshdlr);
1633 	
1634 	   /* store the information of all variables that appear bilinearly */
(7) Event cond_true: Condition "i < sepadata->nbilinterms", taking true branch.
(11) Event cond_true: Condition "i < sepadata->nbilinterms", taking true branch.
(15) Event cond_false: Condition "i < sepadata->nbilinterms", taking false branch.
1635 	   for( i = 0; i < sepadata->nbilinterms; ++i )
1636 	   {
1637 	      assert(bilinterms[i].x != NULL);
1638 	      assert(bilinterms[i].y != NULL);
1639 	      assert(bilinterms[i].nlockspos + bilinterms[i].nlocksneg > 0);
1640 	
1641 	      /* skip bilinear term if it does not have an auxiliary variable */
(8) Event cond_true: Condition "bilinterms[i].aux.var == NULL", taking true branch.
(12) Event cond_true: Condition "bilinterms[i].aux.var == NULL", taking true branch.
1642 	      if( bilinterms[i].aux.var == NULL )
(9) Event continue: Continuing loop.
(13) Event continue: Continuing loop.
1643 	         continue;
1644 	
1645 	      /* if only original variables should be used, skip products that contain at least one auxiliary variable */
1646 	      if( sepadata->onlyoriginal && (SCIPvarIsRelaxationOnly(bilinterms[i].x) ||
1647 	          SCIPvarIsRelaxationOnly(bilinterms[i].y)) )
1648 	         continue;
1649 	
1650 	      /* coverity[forward_null] */
1651 	      SCIP_CALL( addProductVars(scip, sepadata, bilinterms[i].x, bilinterms[i].y, varmap,
1652 	            bilinterms[i].nlockspos + bilinterms[i].nlocksneg) );
(10) Event loop: Looping back.
(14) Event loop: Looping back.
(16) Event loop_end: Reached end of loop.
1653 	   }
1654 	
(17) Event cond_true: Condition "sepadata->detecthidden", taking true branch.
1655 	   if( sepadata->detecthidden )
1656 	   {
1657 	      int oldnterms = sepadata->nbilinterms;
1658 	
1659 	      /* coverity[forward_null] */
(18) Event var_deref_model: Passing "sepadata" to "detectHiddenProducts", which dereferences null "sepadata->varssorted". [details]
Also see events: [assign_zero]
1660 	      SCIP_CALL( detectHiddenProducts(scip, sepadata, varmap) );
1661 	
1662 	      /* update nbilinterms and bilinterms, as detectHiddenProducts might have found new terms */
1663 	      sepadata->nbilinterms = SCIPgetNBilinTermsNonlinear(sepadata->conshdlr);
1664 	      bilinterms = SCIPgetBilinTermsNonlinear(sepadata->conshdlr);
1665 	
1666 	      if( sepadata->nbilinterms > oldnterms )
1667 	      {
1668 	         SCIPstatisticMessage(" Number of hidden products: %d\n", sepadata->nbilinterms - oldnterms);
1669 	      }
1670 	   }
1671 	
1672 	   SCIPhashmapFree(&varmap);
1673 	
1674 	   if( sepadata->nbilinterms == 0 )
1675 	   {
1676 	      return SCIP_OKAY;
1677 	   }
1678 	
1679 	   /* mark positions of aux.exprs that must be equal to the product */
1680 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &sepadata->eqauxexpr, sepadata->nbilinterms) );
1681 	
1682 	   for( i = 0; i < sepadata->nbilinterms; ++i )
1683 	   {
1684 	      int j;
1685 	
1686 	      sepadata->eqauxexpr[i] = -1;
1687 	      for( j = 0; j < bilinterms[i].nauxexprs; ++j )
1688 	      {
1689 	         assert(bilinterms[i].aux.exprs[j] != NULL);
1690 	
1691 	         if( bilinterms[i].aux.exprs[j]->underestimate && bilinterms[i].aux.exprs[j]->overestimate )
1692 	         {
1693 	            sepadata->eqauxexpr[i] = j;
1694 	            break;
1695 	         }
1696 	      }
1697 	   }
1698 	
1699 	   /* find maxnumber of variables that occur most often and sort them by number of occurrences
1700 	    * (same as normal sort, except that entries at positions maxusedvars..nbilinvars may be unsorted at end)
1701 	    */
1702 	   SCIPselectDownIntPtr(sepadata->varpriorities, (void**) sepadata->varssorted, MIN(sepadata->maxusedvars,sepadata->nbilinvars-1),
1703 	         sepadata->nbilinvars);
1704 	
1705 	   /* capture all variables */
1706 	   for( i = 0; i < sepadata->nbilinvars; ++i )
1707 	   {
1708 	      assert(sepadata->varssorted[i] != NULL);
1709 	      SCIP_CALL( SCIPcaptureVar(scip, sepadata->varssorted[i]) );
1710 	   }
1711 	
1712 	   /* mark that separation data has been created */
1713 	   sepadata->iscreated = TRUE;
1714 	   sepadata->isinitialround = TRUE;
1715 	
1716 	   if( SCIPgetNBilinTermsNonlinear(sepadata->conshdlr) > 0 )
1717 	      SCIPstatisticMessage(" Found bilinear terms\n");
1718 	   else
1719 	      SCIPstatisticMessage(" No bilinear terms\n");
1720 	
1721 	   return SCIP_OKAY;
1722 	}
1723 	
1724 	/** get the positions of the most violated auxiliary under- and overestimators for each product
1725 	 *
1726 	 * -1 means no relation with given product is violated
1727 	 */
1728 	static
1729 	void getBestEstimators(
1730 	   SCIP*                 scip,               /**< SCIP data structure */
1731 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
1732 	   SCIP_SOL*             sol,                /**< solution at which to evaluate the expressions */
1733 	   int*                  bestunderestimators,/**< array of indices of best underestimators for each term */
1734 	   int*                  bestoverestimators  /**< array of indices of best overestimators for each term */
1735 	   )
1736 	{
1737 	   SCIP_Real prodval;
1738 	   SCIP_Real auxval;
1739 	   SCIP_Real prodviol;
1740 	   SCIP_Real viol_below;
1741 	   SCIP_Real viol_above;
1742 	   int i;
1743 	   int j;
1744 	   SCIP_CONSNONLINEAR_BILINTERM* terms;
1745 	
1746 	   assert(bestunderestimators != NULL);
1747 	   assert(bestoverestimators != NULL);
1748 	
1749 	   terms = SCIPgetBilinTermsNonlinear(sepadata->conshdlr);
1750 	
1751 	   for( j = 0; j < SCIPgetNBilinTermsNonlinear(sepadata->conshdlr); ++j )
1752 	   {
1753 	      viol_below = 0.0;
1754 	      viol_above = 0.0;
1755 	
1756 	      /* evaluate the product expression */
1757 	      prodval = SCIPgetSolVal(scip, sol, terms[j].x) * SCIPgetSolVal(scip, sol, terms[j].y);
1758 	
1759 	      bestunderestimators[j] = -1;
1760 	      bestoverestimators[j] = -1;
1761 	
1762 	      /* if there are any auxexprs, look there */
1763 	      for( i = 0; i < terms[j].nauxexprs; ++i )
1764 	      {
1765 	         auxval = SCIPevalBilinAuxExprNonlinear(scip, terms[j].x, terms[j].y, terms[j].aux.exprs[i], sol);
1766 	         prodviol = auxval - prodval;
1767 	
1768 	         if( terms[j].aux.exprs[i]->underestimate && SCIPisFeasGT(scip, auxval, prodval) && prodviol > viol_below )
1769 	         {
1770 	            viol_below = prodviol;
1771 	            bestunderestimators[j] = i;
1772 	         }
1773 	         if( terms[j].aux.exprs[i]->overestimate && SCIPisFeasGT(scip, prodval, auxval) && -prodviol > viol_above )
1774 	         {
1775 	            viol_above = -prodviol;
1776 	            bestoverestimators[j] = i;
1777 	         }
1778 	      }
1779 	
1780 	      /* if the term has a plain auxvar, it will be treated differently - do nothing here */
1781 	   }
1782 	}
1783 	
1784 	/** tests if a row contains too many unknown bilinear terms w.r.t. the parameters */
1785 	static
1786 	SCIP_RETCODE isAcceptableRow(
1787 	   SCIP_SEPADATA*        sepadata,           /**< separation data */
1788 	   SCIP_ROW*             row,                /**< the row to be tested */
1789 	   SCIP_VAR*             var,                /**< the variable that is to be multiplied with row */
1790 	   int*                  currentnunknown,    /**< buffer to store number of unknown terms in current row if acceptable */
1791 	   SCIP_Bool*            acceptable          /**< buffer to store the result */
1792 	   )
1793 	{
1794 	   int i;
1795 	   int idx;
1796 	   SCIP_CONSNONLINEAR_BILINTERM* terms;
1797 	
1798 	   assert(row != NULL);
1799 	   assert(var != NULL);
1800 	
1801 	   *currentnunknown = 0;
1802 	   terms = SCIPgetBilinTermsNonlinear(sepadata->conshdlr);
1803 	
1804 	   for( i = 0; (i < SCIProwGetNNonz(row)) && (sepadata->maxunknownterms < 0 || *currentnunknown <= sepadata->maxunknownterms); ++i )
1805 	   {
1806 	      idx = SCIPgetBilinTermIdxNonlinear(sepadata->conshdlr, var, SCIPcolGetVar(SCIProwGetCols(row)[i]));
1807 	
1808 	      /* if the product hasn't been found, no auxiliary expressions for it are known */
1809 	      if( idx < 0 )
1810 	      {
1811 	         ++(*currentnunknown);
1812 	         continue;
1813 	      }
1814 	
1815 	      /* known terms are only those that have an aux.var or equality estimators */
1816 	      if( sepadata->eqauxexpr[idx] == -1 && !(terms[idx].nauxexprs == 0 && terms[idx].aux.var != NULL) )
1817 	      {
1818 	         ++(*currentnunknown);
1819 	      }
1820 	   }
1821 	
1822 	   *acceptable = sepadata->maxunknownterms < 0 || *currentnunknown <= sepadata->maxunknownterms;
1823 	
1824 	   return SCIP_OKAY;
1825 	}
1826 	
1827 	/** adds coefficients and constant of an auxiliary expression
1828 	 *
1829 	 *  the variables the pointers are pointing to must already be initialized
1830 	 */
1831 	static
1832 	void addAuxexprCoefs(
1833 	   SCIP_VAR*             var1,               /**< first product variable */
1834 	   SCIP_VAR*             var2,               /**< second product variable */
1835 	   SCIP_CONSNONLINEAR_AUXEXPR* auxexpr,      /**< auxiliary expression to be added */
1836 	   SCIP_Real             coef,               /**< coefficient of the auxiliary expression */
1837 	   SCIP_Real*            coefaux,            /**< pointer to add the coefficient of the auxiliary variable */
1838 	   SCIP_Real*            coef1,              /**< pointer to add the coefficient of the first variable */
1839 	   SCIP_Real*            coef2,              /**< pointer to add the coefficient of the second variable */
1840 	   SCIP_Real*            cst                 /**< pointer to add the constant */
1841 	   )
1842 	{
1843 	   assert(auxexpr != NULL);
1844 	   assert(auxexpr->auxvar != NULL);
1845 	   assert(coefaux != NULL);
1846 	   assert(coef1 != NULL);
1847 	   assert(coef2 != NULL);
1848 	   assert(cst != NULL);
1849 	
1850 	   *coefaux += auxexpr->coefs[0] * coef;
1851 	
1852 	   /* in auxexpr, x goes before y and has the smaller index,
1853 	    * so compare vars to figure out which one is x and which is y
1854 	    */
1855 	   if( SCIPvarCompare(var1, var2) < 1 )
1856 	   {
1857 	      *coef1 += auxexpr->coefs[1] * coef;
1858 	      *coef2 += auxexpr->coefs[2] * coef;
1859 	   }
1860 	   else
1861 	   {
1862 	      *coef1 += auxexpr->coefs[2] * coef;
1863 	      *coef2 += auxexpr->coefs[1] * coef;
1864 	   }
1865 	   *cst += coef * auxexpr->cst;
1866 	}
1867 	
1868 	/** add a linear term `coef`*`colvar` multiplied by a bound factor (var - lb(var)) or (ub(var) - var)
1869 	 *
1870 	 *  adds the linear term with `colvar` to `cut` and updates `coefvar` and `cst`
1871 	 */
1872 	static
1873 	SCIP_RETCODE addRltTerm(
1874 	   SCIP*                 scip,               /**< SCIP data structure */
1875 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
1876 	   SCIP_SOL*             sol,                /**< the point to be separated (can be NULL) */
1877 	   int*                  bestunderest,       /**< positions of most violated underestimators for each product term */
1878 	   int*                  bestoverest,        /**< positions of most violated overestimators for each product term */
1879 	   SCIP_ROW*             cut,                /**< cut to which the term is to be added */
1880 	   SCIP_VAR*             var,                /**< multiplier variable */
1881 	   SCIP_VAR*             colvar,             /**< row variable to be multiplied */
1882 	   SCIP_Real             coef,               /**< coefficient of the bilinear term */
1883 	   SCIP_Bool             uselb,              /**< whether we multiply with (var - lb) or (ub - var) */
1884 	   SCIP_Bool             uselhs,             /**< whether to create a cut for the lhs or rhs */
1885 	   SCIP_Bool             local,              /**< whether local or global cuts should be computed */
1886 	   SCIP_Bool             computeEqCut,       /**< whether conditions are fulfilled to compute equality cuts */
1887 	   SCIP_Real*            coefvar,            /**< coefficient of var */
1888 	   SCIP_Real*            cst,                /**< buffer to store the constant part of the cut */
1889 	   SCIP_Bool*            success             /**< buffer to store whether cut was updated successfully */
1890 	   )
1891 	{
1892 	   SCIP_Real lbvar;
1893 	   SCIP_Real ubvar;
1894 	   SCIP_Real refpointvar;
1895 	   SCIP_Real signfactor;
1896 	   SCIP_Real boundfactor;
1897 	   SCIP_Real coefauxvar;
1898 	   SCIP_Real coefcolvar;
1899 	   SCIP_Real coefterm;
1900 	   int auxpos;
1901 	   int idx;
1902 	   SCIP_CONSNONLINEAR_BILINTERM* terms;
1903 	   SCIP_VAR* auxvar;
1904 	
1905 	   terms = SCIPgetBilinTermsNonlinear(sepadata->conshdlr);
1906 	
1907 	   if( computeEqCut )
1908 	   {
1909 	      lbvar = 0.0;
1910 	      ubvar = 0.0;
1911 	   }
1912 	   else
1913 	   {
1914 	      lbvar = local ? SCIPvarGetLbLocal(var) : SCIPvarGetLbGlobal(var);
1915 	      ubvar = local ? SCIPvarGetUbLocal(var) : SCIPvarGetUbGlobal(var);
1916 	   }
1917 	
1918 	   refpointvar = MAX(lbvar, MIN(ubvar, SCIPgetSolVal(scip, sol, var))); /*lint !e666*/
1919 	
1920 	   signfactor = (uselb ? 1.0 : -1.0);
1921 	   boundfactor = (uselb ? -lbvar : ubvar);
1922 	
1923 	   coefterm = coef * signfactor; /* coefficient of the bilinear term */
1924 	   coefcolvar = coef * boundfactor; /* coefficient of the linear term */
1925 	   coefauxvar = 0.0; /* coefficient of the auxiliary variable corresponding to the bilinear term */
1926 	   auxvar = NULL;
1927 	
1928 	   assert(!SCIPisInfinity(scip, REALABS(coefterm)));
1929 	
1930 	   /* first, add the linearisation of the bilinear term */
1931 	
1932 	   idx = SCIPgetBilinTermIdxNonlinear(sepadata->conshdlr, var, colvar);
1933 	   auxpos = -1;
1934 	
1935 	   /* for an implicit term, get the position of the best estimator */
1936 	   if( idx >= 0 && terms[idx].nauxexprs > 0 )
1937 	   {
1938 	      if( computeEqCut )
1939 	      {
1940 	         /* use an equality auxiliary expression (which should exist for computeEqCut to be TRUE) */
1941 	         assert(sepadata->eqauxexpr[idx] >= 0);
1942 	         auxpos = sepadata->eqauxexpr[idx];
1943 	      }
1944 	      else if( (uselhs && coefterm > 0.0) || (!uselhs && coefterm < 0.0) )
1945 	      {
1946 	         /* use an overestimator */
1947 	         auxpos = bestoverest[idx];
1948 	      }
1949 	      else
1950 	      {
1951 	         /* use an underestimator */
1952 	         auxpos = bestunderest[idx];
1953 	      }
1954 	   }
1955 	
1956 	   /* if the term is implicit and a suitable auxiliary expression for var*colvar exists, add the coefficients
1957 	    * of the auxiliary expression for coefterm*var*colvar to coefauxvar, coefcolvar, coefvar and cst
1958 	    */
1959 	   if( auxpos >= 0 )
1960 	   {
1961 	      SCIPdebugMsg(scip, "auxiliary expression for <%s> and <%s> found, will be added to cut:\n",
1962 	                          SCIPvarGetName(colvar), SCIPvarGetName(var));
1963 	      addAuxexprCoefs(var, colvar, terms[idx].aux.exprs[auxpos], coefterm, &coefauxvar, coefvar, &coefcolvar, cst);
1964 	      auxvar = terms[idx].aux.exprs[auxpos]->auxvar;
1965 	   }
1966 	   /* for an existing term, use the auxvar if there is one */
1967 	   else if( idx >= 0 && terms[idx].nauxexprs == 0 && terms[idx].aux.var != NULL )
1968 	   {
1969 	      SCIPdebugMsg(scip, "auxvar for <%s> and <%s> found, will be added to cut:\n",
1970 	                   SCIPvarGetName(colvar), SCIPvarGetName(var));
1971 	      coefauxvar += coefterm;
1972 	      auxvar = terms[idx].aux.var;
1973 	   }
1974 	
1975 	   /* otherwise, use clique information or the McCormick estimator in place of the bilinear term */
1976 	   else if( colvar != var )
1977 	   {
1978 	      SCIP_Bool found_clique = FALSE;
1979 	      SCIP_Real lbcolvar = local ? SCIPvarGetLbLocal(colvar) : SCIPvarGetLbGlobal(colvar);
1980 	      SCIP_Real ubcolvar = local ? SCIPvarGetUbLocal(colvar) : SCIPvarGetUbGlobal(colvar);
1981 	      SCIP_Real refpointcolvar = MAX(lbcolvar, MIN(ubcolvar, SCIPgetSolVal(scip, sol, colvar))); /*lint !e666*/
1982 	
1983 	      assert(!computeEqCut);
1984 	
1985 	      if( REALABS(lbcolvar) > MAXVARBOUND || REALABS(ubcolvar) > MAXVARBOUND )
1986 	      {
1987 	         *success = FALSE;
1988 	         return SCIP_OKAY;
1989 	      }
1990 	
1991 	      SCIPdebugMsg(scip, "auxvar for <%s> and <%s> not found, will linearize the product\n", SCIPvarGetName(colvar), SCIPvarGetName(var));
1992 	
1993 	      /* if both variables are binary, check if they are contained together in some clique */
1994 	      if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY && SCIPvarGetType(colvar) == SCIP_VARTYPE_BINARY )
1995 	      {
1996 	         int c;
1997 	         SCIP_CLIQUE** varcliques;
1998 	
1999 	         varcliques = SCIPvarGetCliques(var, TRUE);
2000 	
2001 	         /* look through cliques containing var */
2002 	         for( c = 0; c < SCIPvarGetNCliques(var, TRUE); ++c )
2003 	         {
2004 	            if( SCIPcliqueHasVar(varcliques[c], colvar, TRUE) ) /* var + colvar <= 1 => var*colvar = 0 */
2005 	            {
2006 	               /* product is zero, add nothing */
2007 	               found_clique = TRUE;
2008 	               break;
2009 	            }
2010 	
2011 	            if( SCIPcliqueHasVar(varcliques[c], colvar, FALSE) ) /* var + (1-colvar) <= 1 => var*colvar = var */
2012 	            {
2013 	               *coefvar += coefterm;
2014 	               found_clique = TRUE;
2015 	               break;
2016 	            }
2017 	         }
2018 	
2019 	         if( !found_clique )
2020 	         {
2021 	            varcliques = SCIPvarGetCliques(var, FALSE);
2022 	
2023 	            /* look through cliques containing complement of var */
2024 	            for( c = 0; c < SCIPvarGetNCliques(var, FALSE); ++c )
2025 	            {
2026 	               if( SCIPcliqueHasVar(varcliques[c], colvar, TRUE) ) /* (1-var) + colvar <= 1 => var*colvar = colvar */
2027 	               {
2028 	                  coefcolvar += coefterm;
2029 	                  found_clique = TRUE;
2030 	                  break;
2031 	               }
2032 	
2033 	               if( SCIPcliqueHasVar(varcliques[c], colvar, FALSE) ) /* (1-var) + (1-colvar) <= 1 => var*colvar = var + colvar - 1 */
2034 	               {
2035 	                  *coefvar += coefterm;
2036 	                  coefcolvar += coefterm;
2037 	                  *cst -= coefterm;
2038 	                  found_clique = TRUE;
2039 	                  break;
2040 	               }
2041 	            }
2042 	         }
2043 	      }
2044 	
2045 	      if( !found_clique )
2046 	      {
2047 	         SCIPdebugMsg(scip, "clique for <%s> and <%s> not found or at least one of them is not binary, will use McCormick\n", SCIPvarGetName(colvar), SCIPvarGetName(var));
2048 	         SCIPaddBilinMcCormick(scip, coefterm, lbvar, ubvar, refpointvar, lbcolvar,
2049 	            ubcolvar, refpointcolvar, uselhs, coefvar, &coefcolvar, cst, success);
2050 	         if( !*success )
2051 	            return SCIP_OKAY;
2052 	      }
2053 	   }
2054 	
2055 	   /* or, if it's a quadratic term, use a secant for overestimation and a gradient for underestimation */
2056 	   else
2057 	   {
2058 	      SCIPdebugMsg(scip, "auxvar for <%s>^2 not found, will use gradient and secant estimators\n", SCIPvarGetName(colvar));
2059 	
2060 	      assert(!computeEqCut);
2061 	
2062 	      /* for a binary var, var^2 = var */
2063 	      if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY )
2064 	      {
2065 	         *coefvar += coefterm;
2066 	      }
2067 	      else
2068 	      {
2069 	         /* depending on over-/underestimation and the sign of the column variable, compute secant or tangent */
2070 	         if( (uselhs && coefterm > 0.0) || (!uselhs && coefterm < 0.0) )
2071 	            SCIPaddSquareSecant(scip, coefterm, lbvar, ubvar, coefvar, cst, success);
2072 	         else
2073 	            SCIPaddSquareLinearization(scip, coefterm, refpointvar, SCIPvarIsIntegral(var), coefvar, cst, success);
2074 	
2075 	         if( !*success )
2076 	            return SCIP_OKAY;
2077 	      }
2078 	   }
2079 	
2080 	   /* add the auxiliary variable if its coefficient is nonzero */
2081 	   if( !SCIPisZero(scip, coefauxvar) )
2082 	   {
2083 	      assert(auxvar != NULL);
2084 	      SCIP_CALL( SCIPaddVarToRow(scip, cut, auxvar, coefauxvar) );
2085 	   }
2086 	
2087 	   /* we are done with the product linearisation, now add the term which comes from multiplying
2088 	    * coef*colvar by the constant part of the bound factor
2089 	    */
2090 	
2091 	   if( colvar != var )
2092 	   {
2093 	      assert(!SCIPisInfinity(scip, REALABS(coefcolvar)));
2094 	      SCIP_CALL( SCIPaddVarToRow(scip, cut, colvar, coefcolvar) );
2095 	   }
2096 	   else
2097 	      *coefvar += coefcolvar;
2098 	
2099 	   return SCIP_OKAY;
2100 	}
2101 	
2102 	/** creates the RLT cut formed by multiplying a given row with (x - lb) or (ub - x)
2103 	 *
2104 	 * In detail:
2105 	 * - The row is multiplied either with (x - lb(x)) or with (ub(x) - x), depending on parameter `uselb`, or by x if
2106 	 *   this is an equality cut
2107 	 * - The (inequality) cut is computed either for lhs or rhs, depending on parameter `uselhs`.
2108 	 * - Terms for which no auxiliary variable and no clique relation exists are replaced by either McCormick, secants,
2109 	 *   or gradient linearization cuts.
2110 	 */
2111 	static
2112 	SCIP_RETCODE computeRltCut(
2113 	   SCIP*                 scip,               /**< SCIP data structure */
2114 	   SCIP_SEPA*            sepa,               /**< separator */
2115 	   SCIP_SEPADATA*        sepadata,           /**< separation data */
2116 	   SCIP_ROW**            cut,                /**< buffer to store the cut */
2117 	   SCIP_ROW*             row,                /**< the row that is used for the rlt cut (NULL if using projected row) */
2118 	   RLT_SIMPLEROW*        projrow,            /**< projected row that is used for the rlt cut (NULL if using row) */
2119 	   SCIP_SOL*             sol,                /**< the point to be separated (can be NULL) */
2120 	   int*                  bestunderest,       /**< positions of most violated underestimators for each product term */
2121 	   int*                  bestoverest,        /**< positions of most violated overestimators for each product term */
2122 	   SCIP_VAR*             var,                /**< the variable that is used for the rlt cuts */
2123 	   SCIP_Bool*            success,            /**< buffer to store whether cut was created successfully */
2124 	   SCIP_Bool             uselb,              /**< whether we multiply with (var - lb) or (ub - var) */
2125 	   SCIP_Bool             uselhs,             /**< whether to create a cut for the lhs or rhs */
2126 	   SCIP_Bool             local,              /**< whether local or global cuts should be computed */
2127 	   SCIP_Bool             computeEqCut,       /**< whether conditions are fulfilled to compute equality cuts */
2128 	   SCIP_Bool             useprojrow          /**< whether to use projected row instead of normal row */
2129 	   )
2130 	{ /*lint --e{413}*/
2131 	   SCIP_Real signfactor;
2132 	   SCIP_Real boundfactor;
2133 	   SCIP_Real lbvar;
2134 	   SCIP_Real ubvar;
2135 	   SCIP_Real coefvar;
2136 	   SCIP_Real consside;
2137 	   SCIP_Real finalside;
2138 	   SCIP_Real cstterm;
2139 	   SCIP_Real lhs;
2140 	   SCIP_Real rhs;
2141 	   SCIP_Real rowcst;
2142 	   int i;
2143 	   const char* rowname;
2144 	   char cutname[SCIP_MAXSTRLEN];
2145 	
2146 	   assert(sepadata != NULL);
2147 	   assert(cut != NULL);
2148 	   assert(useprojrow || row != NULL);
2149 	   assert(!useprojrow || projrow != NULL);
2150 	   assert(var != NULL);
2151 	   assert(success != NULL);
2152 	
2153 	   lhs = useprojrow ? projrow->lhs : SCIProwGetLhs(row);
2154 	   rhs = useprojrow ? projrow->rhs : SCIProwGetRhs(row);
2155 	   rowname = useprojrow ? projrow->name : SCIProwGetName(row);
2156 	   rowcst = useprojrow ? projrow ->cst : SCIProwGetConstant(row);
2157 	
2158 	   assert(!computeEqCut || SCIPisEQ(scip, lhs, rhs));
2159 	
2160 	   *cut = NULL;
2161 	
2162 	   /* get data for given variable */
2163 	   if( computeEqCut )
2164 	   {
2165 	      lbvar = 0.0;
2166 	      ubvar = 0.0;
2167 	   }
2168 	   else
2169 	   {
2170 	      lbvar = local ? SCIPvarGetLbLocal(var) : SCIPvarGetLbGlobal(var);
2171 	      ubvar = local ? SCIPvarGetUbLocal(var) : SCIPvarGetUbGlobal(var);
2172 	   }
2173 	
2174 	   /* get row side */
2175 	   consside = uselhs ? lhs : rhs;
2176 	
2177 	   /* if the bounds are too large or the respective side is infinity, skip this cut */
2178 	   if( (uselb && REALABS(lbvar) > MAXVARBOUND) || (!uselb && REALABS(ubvar) > MAXVARBOUND)
2179 	         || SCIPisInfinity(scip, REALABS(consside)) )
2180 	   {
2181 	      SCIPdebugMsg(scip, "cut generation for %srow <%s>, %s, and variable <%s> with its %s %g not possible\n",
2182 	         useprojrow ? "projected " : "", rowname, uselhs ? "lhs" : "rhs", SCIPvarGetName(var),
2183 	         uselb ? "lower bound" : "upper bound", uselb ? lbvar : ubvar);
2184 	
2185 	      if( REALABS(lbvar) > MAXVARBOUND )
2186 	         SCIPdebugMsg(scip, " because of lower bound\n");
2187 	      if( REALABS(ubvar) > MAXVARBOUND )
2188 	         SCIPdebugMsg(scip, " because of upper bound\n");
2189 	      if( SCIPisInfinity(scip, REALABS(consside)) )
2190 	         SCIPdebugMsg(scip, " because of side %g\n", consside);
2191 	
2192 	      *success = FALSE;
2193 	      return SCIP_OKAY;
2194 	   }
2195 	
2196 	   /* initialize some factors needed for computation */
2197 	   coefvar = 0.0;
2198 	   cstterm = 0.0;
2199 	   signfactor = (uselb ? 1.0 : -1.0);
2200 	   boundfactor = (uselb ? -lbvar : ubvar);
2201 	   *success = TRUE;
2202 	
2203 	   /* create an empty row which we then fill with variables step by step */
2204 	   (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "rlt_%scut_%s_%s_%s_%s_%" SCIP_LONGINT_FORMAT, useprojrow ? "proj" : "", rowname,
2205 	                       uselhs ? "lhs" : "rhs", SCIPvarGetName(var), uselb ? "lb" : "ub", SCIPgetNLPs(scip));
2206 	   SCIP_CALL( SCIPcreateEmptyRowSepa(scip, cut, sepa, cutname, -SCIPinfinity(scip), SCIPinfinity(scip),
2207 	         SCIPgetDepth(scip) > 0 && local, FALSE, FALSE) );  /* TODO SCIPgetDepth() should be replaced by depth that is passed on to the SEPAEXEC calls (?) */
2208 	
2209 	   SCIP_CALL( SCIPcacheRowExtensions(scip, *cut) );
2210 	
2211 	   /* iterate over all variables in the row and add the corresponding terms coef*colvar*(bound factor) to the cuts */
2212 	   for( i = 0; i < (useprojrow ? projrow->nnonz : SCIProwGetNNonz(row)); ++i )
2213 	   {
2214 	      SCIP_VAR* colvar;
2215 	
2216 	      colvar = useprojrow ? projrow->vars[i] : SCIPcolGetVar(SCIProwGetCols(row)[i]);
2217 	      SCIP_CALL( addRltTerm(scip, sepadata, sol, bestunderest, bestoverest, *cut, var, colvar,
2218 	            useprojrow ? projrow->coefs[i] : SCIProwGetVals(row)[i], uselb, uselhs, local, computeEqCut,
2219 	            &coefvar, &cstterm, success) );
2220 	   }
2221 	
2222 	   if( REALABS(cstterm) > MAXVARBOUND )
2223 	   {
2224 	      *success = FALSE;
2225 	      return SCIP_OKAY;
2226 	   }
2227 	
2228 	   /* multiply (x-lb) or (ub -x) with the lhs and rhs of the row */
2229 	   coefvar += signfactor * (rowcst - consside);
2230 	   finalside = boundfactor * (consside - rowcst) - cstterm;
2231 	
2232 	   assert(!SCIPisInfinity(scip, REALABS(coefvar)));
2233 	   assert(!SCIPisInfinity(scip, REALABS(finalside)));
2234 	
2235 	   /* set the coefficient of var and update the side */
2236 	   SCIP_CALL( SCIPaddVarToRow(scip, *cut, var, coefvar) );
2237 	   SCIP_CALL( SCIPflushRowExtensions(scip, *cut) );
2238 	   if( uselhs || computeEqCut )
2239 	   {
2240 	      SCIP_CALL( SCIPchgRowLhs(scip, *cut, finalside) );
2241 	   }
2242 	   if( !uselhs || computeEqCut )
2243 	   {
2244 	      SCIP_CALL( SCIPchgRowRhs(scip, *cut, finalside) );
2245 	   }
2246 	
2247 	   SCIPdebugMsg(scip, "%scut was generated successfully:\n", useprojrow ? "projected " : "");
2248 	#ifdef SCIP_DEBUG
2249 	   SCIP_CALL( SCIPprintRow(scip, *cut, NULL) );
2250 	#endif
2251 	
2252 	   return SCIP_OKAY;
2253 	}
2254 	
2255 	/** store a row projected by fixing all variables that are at bound at sol; the result is a simplified row */
2256 	static
2257 	SCIP_RETCODE createProjRow(
2258 	   SCIP*                 scip,               /**< SCIP data structure */
2259 	   RLT_SIMPLEROW*        simplerow,          /**< pointer to the simplified row */
2260 	   SCIP_ROW*             row,                /**< row to be projected */
2261 	   SCIP_SOL*             sol,                /**< the point to be separated (can be NULL) */
2262 	   SCIP_Bool             local               /**< whether local bounds should be checked */
2263 	   )
2264 	{
2265 	   int i;
2266 	   SCIP_VAR* var;
2267 	   SCIP_Real val;
2268 	   SCIP_Real vlb;
2269 	   SCIP_Real vub;
2270 	
2271 	   assert(simplerow != NULL);
2272 	
2273 	   SCIP_CALL( SCIPduplicateBlockMemoryArray(scip,  &(simplerow->name), SCIProwGetName(row),
2274 	         strlen(SCIProwGetName(row))+1) ); /*lint !e666*/
2275 	   simplerow->nnonz = 0;
2276 	   simplerow->size = 0;
2277 	   simplerow->vars = NULL;
2278 	   simplerow->coefs = NULL;
2279 	   simplerow->lhs = SCIProwGetLhs(row);
2280 	   simplerow->rhs = SCIProwGetRhs(row);
2281 	   simplerow->cst = SCIProwGetConstant(row);
2282 	
2283 	   for( i = 0; i < SCIProwGetNNonz(row); ++i )
2284 	   {
2285 	      var = SCIPcolGetVar(SCIProwGetCols(row)[i]);
2286 	      val = SCIPgetSolVal(scip, sol, var);
2287 	      vlb = local ? SCIPvarGetLbLocal(var) : SCIPvarGetLbGlobal(var);
2288 	      vub = local ? SCIPvarGetUbLocal(var) : SCIPvarGetUbGlobal(var);
2289 	      if( SCIPisFeasEQ(scip, vlb, val) || SCIPisFeasEQ(scip, vub, val) )
2290 	      {
2291 	         /* if we are projecting and the var is at bound, add var as a constant to simplerow */
2292 	         if( !SCIPisInfinity(scip, -simplerow->lhs) )
2293 	            simplerow->lhs -= SCIProwGetVals(row)[i]*val;
2294 	         if( !SCIPisInfinity(scip, simplerow->rhs) )
2295 	            simplerow->rhs -= SCIProwGetVals(row)[i]*val;
2296 	      }
2297 	      else
2298 	      {
2299 	         if( simplerow->nnonz + 1 > simplerow->size )
2300 	         {
2301 	            int newsize;
2302 	
2303 	            newsize = SCIPcalcMemGrowSize(scip, simplerow->nnonz + 1);
2304 	            SCIP_CALL( SCIPreallocBufferArray(scip, &simplerow->coefs, newsize) );
2305 	            SCIP_CALL( SCIPreallocBufferArray(scip, &simplerow->vars, newsize) );
2306 	            simplerow->size = newsize;
2307 	         }
2308 	
2309 	         /* add the term to simplerow */
2310 	         simplerow->vars[simplerow->nnonz] = var;
2311 	         simplerow->coefs[simplerow->nnonz] = SCIProwGetVals(row)[i];
2312 	         ++(simplerow->nnonz);
2313 	      }
2314 	   }
2315 	
2316 	   return SCIP_OKAY;
2317 	}
2318 	
2319 	/** free the projected row */
2320 	static
2321 	void freeProjRow(
2322 	   SCIP*                 scip,               /**< SCIP data structure */
2323 	   RLT_SIMPLEROW*        simplerow           /**< simplified row to be freed */
2324 	   )
2325 	{
2326 	   assert(simplerow != NULL);
2327 	
2328 	   if( simplerow->size > 0 )
2329 	   {
2330 	      assert(simplerow->vars != NULL);
2331 	      assert(simplerow->coefs != NULL);
2332 	
2333 	      SCIPfreeBufferArray(scip, &simplerow->vars);
2334 	      SCIPfreeBufferArray(scip, &simplerow->coefs);
2335 	   }
2336 	   SCIPfreeBlockMemoryArray(scip, &simplerow->name, strlen(simplerow->name)+1);
2337 	}
2338 	
2339 	/** creates the projected problem
2340 	 *
2341 	 *  All variables that are at their bounds at the current solution are added
2342 	 *  to left and/or right hand sides as constant values.
2343 	 */
2344 	static
2345 	SCIP_RETCODE createProjRows(
2346 	   SCIP*                 scip,               /**< SCIP data structure */
2347 	   SCIP_ROW**            rows,               /**< problem rows */
2348 	   int                   nrows,              /**< number of rows */
2349 	   SCIP_SOL*             sol,                /**< the point to be separated (can be NULL) */
2350 	   RLT_SIMPLEROW**       projrows,           /**< the projected rows to be filled */
2351 	   SCIP_Bool             local,              /**< are local cuts allowed? */
2352 	   SCIP_Bool*            allcst              /**< buffer to store whether all projected rows have only constants */
2353 	   )
2354 	{
2355 	   int i;
2356 	
2357 	   assert(scip != NULL);
2358 	   assert(rows != NULL);
2359 	   assert(projrows != NULL);
2360 	   assert(allcst != NULL);
2361 	
2362 	   *allcst = TRUE;
2363 	   SCIP_CALL( SCIPallocBufferArray(scip, projrows, nrows) );
2364 	
2365 	   for( i = 0; i < nrows; ++i )
2366 	   {
2367 	      /* get a simplified and projected row */
2368 	      SCIP_CALL( createProjRow(scip, &(*projrows)[i], rows[i], sol, local) );
2369 	      if( (*projrows)[i].nnonz > 0 )
2370 	         *allcst = FALSE;
2371 	   }
2372 	
2373 	   return SCIP_OKAY;
2374 	}
2375 	
2376 	#ifdef SCIP_DEBUG
2377 	/* prints the projected LP */
2378 	static
2379 	void printProjRows(
2380 	   SCIP*                 scip,               /**< SCIP data structure */
2381 	   RLT_SIMPLEROW*        projrows,           /**< the projected rows */
2382 	   int                   nrows,              /**< number of projected rows */
2383 	   FILE*                 file                /**< output file (or NULL for standard output) */
2384 	   )
2385 	{
2386 	   int i;
2387 	   int j;
2388 	
2389 	   assert(projrows != NULL);
2390 	
2391 	   for( i = 0; i < nrows; ++i )
2392 	   {
2393 	      SCIPinfoMessage(scip, file, "\nproj_row[%d]: ", i);
2394 	      if( !SCIPisInfinity(scip, -projrows[i].lhs) )
2395 	         SCIPinfoMessage(scip, file, "%.15g <= ", projrows[i].lhs);
2396 	      for( j = 0; j < projrows[i].nnonz; ++j )
2397 	      {
2398 	         if( j == 0 )
2399 	         {
2400 	            if( projrows[i].coefs[j] < 0 )
2401 	               SCIPinfoMessage(scip, file, "-");
2402 	         }
2403 	         else
2404 	         {
2405 	            if( projrows[i].coefs[j] < 0 )
2406 	               SCIPinfoMessage(scip, file, " - ");
2407 	            else
2408 	               SCIPinfoMessage(scip, file, " + ");
2409 	         }
2410 	
2411 	         if( projrows[i].coefs[j] != 1.0 )
2412 	            SCIPinfoMessage(scip, file, "%.15g*", REALABS(projrows[i].coefs[j]));
2413 	         SCIPinfoMessage(scip, file, "<%s>", SCIPvarGetName(projrows[i].vars[j]));
2414 	      }
2415 	      if( projrows[i].cst > 0 )
2416 	         SCIPinfoMessage(scip, file, " + %.15g", projrows[i].cst);
2417 	      else if( projrows[i].cst < 0 )
2418 	         SCIPinfoMessage(scip, file, " - %.15g", REALABS(projrows[i].cst));
2419 	
2420 	      if( !SCIPisInfinity(scip, projrows[i].rhs) )
2421 	         SCIPinfoMessage(scip, file, " <= %.15g", projrows[i].rhs);
2422 	   }
2423 	   SCIPinfoMessage(scip, file, "\n");
2424 	}
2425 	#endif
2426 	
2427 	/** frees the projected rows */
2428 	static
2429 	void freeProjRows(
2430 	   SCIP*                 scip,               /**< SCIP data structure */
2431 	   RLT_SIMPLEROW**       projrows,           /**< the projected LP */
2432 	   int                   nrows               /**< number of rows in projrows */
2433 	   )
2434 	{
2435 	   int i;
2436 	
2437 	   for( i = 0; i < nrows; ++i )
2438 	      freeProjRow(scip, &(*projrows)[i]);
2439 	
2440 	   SCIPfreeBufferArray(scip, projrows);
2441 	}
2442 	
2443 	/** mark a row for rlt cut selection
2444 	 *
2445 	 * depending on the sign of the coefficient and violation, set or update mark which cut is required:
2446 	 * - 1 - cuts for axy < aw case,
2447 	 * - 2 - cuts for axy > aw case,
2448 	 * - 3 - cuts for both cases
2449 	 */
2450 	static
2451 	void addRowMark(
2452 	   int                   ridx,               /**< row index */
2453 	   SCIP_Real             a,                  /**< coefficient of x in the row */
2454 	   SCIP_Bool             violatedbelow,      /**< whether the relation auxexpr <= xy is violated */
2455 	   SCIP_Bool             violatedabove,      /**< whether the relation xy <= auxexpr is violated */
2456 	   int*                  row_idcs,           /**< sparse array with indices of marked rows */
2457 	   unsigned int*         row_marks,          /**< sparse array to store the marks */
2458 	   int*                  nmarked             /**< number of marked rows */
2459 	   )
2460 	{
2461 	   unsigned int newmark;
2462 	   int pos;
2463 	   SCIP_Bool exists;
2464 	
2465 	   assert(a != 0.0);
2466 	
2467 	   if( (a > 0.0 && violatedbelow) || (a < 0.0 && violatedabove) )
2468 	      newmark = 1; /* axy < aw case */
2469 	   else
2470 	      newmark = 2; /* axy > aw case */
2471 	
2472 	   /* find row idx in row_idcs */
2473 	   exists = SCIPsortedvecFindInt(row_idcs, ridx, *nmarked, &pos);
2474 	
2475 	   if( exists )
2476 	   {
2477 	      /* we found the row index: update the mark at pos */
2478 	      row_marks[pos] |= newmark;
2479 	   }
2480 	   else /* the given row index does not yet exist in row_idcs */
2481 	   {
2482 	      int i;
2483 	
2484 	      /* insert row index at the correct position */
2485 	      for( i = *nmarked; i > pos; --i )
2486 	      {
2487 	         row_idcs[i] = row_idcs[i-1];
2488 	         row_marks[i] = row_marks[i-1];
2489 	      }
2490 	      row_idcs[pos] = ridx;
2491 	      row_marks[pos] = newmark;
2492 	      (*nmarked)++;
2493 	   }
2494 	}
2495 	
2496 	/** mark all rows that should be multiplied by xj */
2497 	static
2498 	SCIP_RETCODE markRowsXj(
2499 	   SCIP*                 scip,               /**< SCIP data structure */
2500 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
2501 	   SCIP_CONSHDLR*        conshdlr,           /**< nonlinear constraint handler */
2502 	   SCIP_SOL*             sol,                /**< point to be separated (can be NULL) */
2503 	   int                   j,                  /**< index of the multiplier variable in sepadata */
2504 	   SCIP_Bool             local,              /**< are local cuts allowed? */
2505 	   SCIP_HASHMAP*         row_to_pos,         /**< hashmap linking row indices to positions in array */
2506 	   int*                  bestunderest,       /**< positions of most violated underestimators for each product term */
2507 	   int*                  bestoverest,        /**< positions of most violated overestimators for each product term */
2508 	   unsigned int*         row_marks,          /**< sparse array storing the row marks */
2509 	   int*                  row_idcs,           /**< sparse array storing the marked row positions */
2510 	   int*                  nmarked             /**< number of marked rows */
2511 	   )
2512 	{
2513 	   int i;
2514 	   int idx;
2515 	   int ncolrows;
2516 	   int r;
2517 	   int ridx;
2518 	   SCIP_VAR* xi;
2519 	   SCIP_VAR* xj;
2520 	   SCIP_Real vlb;
2521 	   SCIP_Real vub;
2522 	   SCIP_Real vali;
2523 	   SCIP_Real valj;
2524 	   SCIP_Real a;
2525 	   SCIP_COL* coli;
2526 	   SCIP_Real* colvals;
2527 	   SCIP_ROW** colrows;
2528 	   SCIP_CONSNONLINEAR_BILINTERM* terms;
2529 	   SCIP_Bool violatedbelow;
2530 	   SCIP_Bool violatedabove;
2531 	   SCIP_VAR** bilinadjvars;
2532 	   int nbilinadjvars;
2533 	
2534 	   *nmarked = 0;
2535 	
2536 	   xj = sepadata->varssorted[j];
2537 	   assert(xj != NULL);
2538 	
2539 	   valj = SCIPgetSolVal(scip, sol, xj);
2540 	   vlb = local ? SCIPvarGetLbLocal(xj) : SCIPvarGetLbGlobal(xj);
2541 	   vub = local ? SCIPvarGetUbLocal(xj) : SCIPvarGetUbGlobal(xj);
2542 	
2543 	   if( sepadata->useprojection && (SCIPisFeasEQ(scip, vlb, valj) || SCIPisFeasEQ(scip, vub, valj)) )
2544 	   {
2545 	      /* we don't want to multiply by variables that are at bound */
2546 	      SCIPdebugMsg(scip, "Rejected multiplier <%s> in [%g,%g] because it is at bound (current value %g)\n", SCIPvarGetName(xj), vlb, vub, valj);
2547 	      return SCIP_OKAY;
2548 	   }
2549 	
2550 	   terms = SCIPgetBilinTermsNonlinear(conshdlr);
2551 	   bilinadjvars = getAdjacentVars(sepadata->bilinvardatamap, xj, &nbilinadjvars);
2552 	   assert(bilinadjvars != NULL);
2553 	
2554 	   /* for each var which appears in a bilinear product together with xj, mark rows */
2555 	   for( i = 0; i < nbilinadjvars; ++i )
2556 	   {
2557 	      xi = bilinadjvars[i];
2558 	
2559 	      if( SCIPvarGetStatus(xi) != SCIP_VARSTATUS_COLUMN )
2560 	         continue;
2561 	
2562 	      vali = SCIPgetSolVal(scip, sol, xi);
2563 	      vlb = local ? SCIPvarGetLbLocal(xi) : SCIPvarGetLbGlobal(xi);
2564 	      vub = local ? SCIPvarGetUbLocal(xi) : SCIPvarGetUbGlobal(xi);
2565 	
2566 	      /* if we use projection, we aren't interested in products with variables that are at bound */
2567 	      if( sepadata->useprojection && (SCIPisFeasEQ(scip, vlb, vali) || SCIPisFeasEQ(scip, vub, vali)) )
2568 	         continue;
2569 	
2570 	      /* get the index of the bilinear product */
2571 	      idx = SCIPgetBilinTermIdxNonlinear(conshdlr, xj, xi);
2572 	      assert(idx >= 0 && idx < SCIPgetNBilinTermsNonlinear(conshdlr));
2573 	
2574 	      /* skip implicit products if we don't want to add RLT cuts for them */
2575 	      if( !sepadata->hiddenrlt && !terms[idx].existing )
2576 	         continue;
2577 	
2578 	      /* use the most violated under- and overestimators for this product;
2579 	       * if equality cuts are computed, we might end up using a different auxiliary expression;
2580 	       * so this is an optimistic (i.e. taking the largest possible violation) estimation
2581 	       */
2582 	      if( bestunderest == NULL || bestunderest[idx] == -1 )
2583 	      { /* no violated implicit underestimation relations -> either use auxvar or set violatedbelow to FALSE */
2584 	         if( terms[idx].nauxexprs == 0 && terms[idx].aux.var != NULL )
2585 	         {
2586 	            assert(terms[idx].existing);
2587 	            violatedbelow = SCIPisFeasPositive(scip, SCIPgetSolVal(scip, sol, terms[idx].aux.var) - valj * vali);
2588 	         }
2589 	         else
2590 	         {
2591 	            assert(bestunderest != NULL);
2592 	            violatedbelow = FALSE;
2593 	         }
2594 	      }
2595 	      else
2596 	      {
2597 	         assert(bestunderest[idx] >= 0 && bestunderest[idx] < terms[idx].nauxexprs);
2598 	
2599 	         /* if we are here, the relation with the best underestimator must be violated */
2600 	         assert(SCIPisFeasPositive(scip, SCIPevalBilinAuxExprNonlinear(scip, terms[idx].x, terms[idx].y,
2601 	               terms[idx].aux.exprs[bestunderest[idx]], sol) - valj * vali));
2602 	         violatedbelow = TRUE;
2603 	      }
2604 	
2605 	      if( bestoverest == NULL || bestoverest[idx] == -1 )
2606 	      { /* no violated implicit overestimation relations -> either use auxvar or set violatedabove to FALSE */
2607 	         if( terms[idx].nauxexprs == 0 && terms[idx].aux.var != NULL )
2608 	         {
2609 	            assert(terms[idx].existing);
2610 	            violatedabove = SCIPisFeasPositive(scip, valj * vali - SCIPgetSolVal(scip, sol, terms[idx].aux.var));
2611 	         }
2612 	         else
2613 	         {
2614 	            assert(bestoverest != NULL);
2615 	            violatedabove = FALSE;
2616 	         }
2617 	      }
2618 	      else
2619 	      {
2620 	         assert(bestoverest[idx] >= 0 && bestoverest[idx] < terms[idx].nauxexprs);
2621 	
2622 	         /* if we are here, the relation with the best overestimator must be violated */
2623 	         assert(SCIPisFeasPositive(scip, valj * vali - SCIPevalBilinAuxExprNonlinear(scip, terms[idx].x, terms[idx].y,
2624 	               terms[idx].aux.exprs[bestoverest[idx]], sol)));
2625 	         violatedabove = TRUE;
2626 	      }
2627 	
2628 	      /* only violated products contribute to row marks */
2629 	      if( !violatedbelow && !violatedabove )
2630 	      {
2631 	         SCIPdebugMsg(scip, "the product for vars <%s> and <%s> is not violated\n", SCIPvarGetName(xj), SCIPvarGetName(xi));
2632 	         continue;
2633 	      }
2634 	
2635 	      /* get the column of xi */
2636 	      coli = SCIPvarGetCol(xi);
2637 	      colvals = SCIPcolGetVals(coli);
2638 	      ncolrows = SCIPcolGetNNonz(coli);
2639 	      colrows = SCIPcolGetRows(coli);
2640 	
2641 	      SCIPdebugMsg(scip, "marking rows for xj = <%s>, xi = <%s>\n", SCIPvarGetName(xj), SCIPvarGetName(xi));
2642 	
2643 	      /* mark the rows */
2644 	      for( r = 0; r < ncolrows; ++r )
2645 	      {
2646 	         ridx = SCIProwGetIndex(colrows[r]);
2647 	
2648 	         if( !SCIPhashmapExists(row_to_pos, (void*)(size_t)ridx) )
2649 	            continue; /* if row index is not in row_to_pos, it means that storeSuitableRows decided to ignore this row */
2650 	
2651 	         a = colvals[r];
2652 	         if( a == 0.0 )
2653 	            continue;
2654 	
2655 	         SCIPdebugMsg(scip, "Marking row %d\n", ridx);
2656 	         addRowMark(ridx, a, violatedbelow, violatedabove, row_idcs, row_marks, nmarked);
2657 	      }
2658 	   }
2659 	
2660 	   return SCIP_OKAY;
2661 	}
2662 	
2663 	/** adds McCormick inequalities for implicit products */
2664 	static
2665 	SCIP_RETCODE separateMcCormickImplicit(
2666 	   SCIP*                 scip,               /**< SCIP data structure */
2667 	   SCIP_SEPA*            sepa,               /**< separator */
2668 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
2669 	   SCIP_SOL*             sol,                /**< the point to be separated (can be NULL) */
2670 	   int*                  bestunderestimators,/**< indices of auxiliary underestimators with largest violation in sol */
2671 	   int*                  bestoverestimators, /**< indices of auxiliary overestimators with largest violation in sol */
2672 	   SCIP_RESULT*          result              /**< pointer to store the result */
2673 	   )
2674 	{
2675 	   int i;
2676 	   int j;
2677 	   SCIP_CONSNONLINEAR_BILINTERM* terms;
2678 	   SCIP_ROW* cut;
2679 	   char name[SCIP_MAXSTRLEN];
2680 	   SCIP_Bool underestimate;
2681 	   SCIP_Real xcoef;
2682 	   SCIP_Real ycoef;
2683 	   SCIP_Real auxcoef;
2684 	   SCIP_Real constant;
2685 	   SCIP_Bool success;
2686 	   SCIP_CONSNONLINEAR_AUXEXPR* auxexpr;
2687 	   SCIP_Bool cutoff;
2688 	   SCIP_Real refpointx;
2689 	   SCIP_Real refpointy;
2690 	   SCIP_INTERVAL bndx;
2691 	   SCIP_INTERVAL bndy;
2692 	#ifndef NDEBUG
2693 	   SCIP_Real productval;
2694 	   SCIP_Real auxval;
2695 	#endif
2696 	
2697 	   assert(sepadata->nbilinterms == SCIPgetNBilinTermsNonlinear(sepadata->conshdlr));
2698 	   assert(bestunderestimators != NULL && bestoverestimators != NULL);
2699 	
2700 	   cutoff = FALSE;
2701 	   terms = SCIPgetBilinTermsNonlinear(sepadata->conshdlr);
2702 	
2703 	   for( i = 0; i < sepadata->nbilinterms; ++i )
2704 	   {
2705 	      if( terms[i].existing )
2706 	         continue;
2707 	
2708 	      assert(terms[i].nauxexprs > 0);
2709 	
2710 	      bndx.inf = SCIPvarGetLbLocal(terms[i].x);
2711 	      bndx.sup = SCIPvarGetUbLocal(terms[i].x);
2712 	      bndy.inf = SCIPvarGetLbLocal(terms[i].y);
2713 	      bndy.sup = SCIPvarGetUbLocal(terms[i].y);
2714 	      refpointx = SCIPgetSolVal(scip, sol, terms[i].x);
2715 	      refpointy = SCIPgetSolVal(scip, sol, terms[i].y);
2716 	
2717 	      /* adjust the reference points */
2718 	      refpointx = MIN(MAX(refpointx, bndx.inf), bndx.sup); /*lint !e666*/
2719 	      refpointy = MIN(MAX(refpointy, bndy.inf), bndy.sup); /*lint !e666*/
2720 	
2721 	      /* one iteration for underestimation and one for overestimation */
2722 	      for( j = 0; j < 2; ++j )
2723 	      {
2724 	         /* if underestimate, separate xy <= auxexpr; if !underestimate, separate xy >= auxexpr;
2725 	          * the cuts will be:
2726 	          * if underestimate: McCormick_under(xy) - auxexpr <= 0,
2727 	          * if !underestimate: McCormick_over(xy) - auxexpr >= 0
2728 	          */
2729 	         underestimate = j == 0;
2730 	         if( underestimate && bestoverestimators[i] != -1 )
2731 	            auxexpr = terms[i].aux.exprs[bestoverestimators[i]];
2732 	         else if( !underestimate && bestunderestimators[i] != -1 )
2733 	            auxexpr = terms[i].aux.exprs[bestunderestimators[i]];
2734 	         else
2735 	            continue;
2736 	         assert(!underestimate || auxexpr->overestimate);
2737 	         assert(underestimate || auxexpr->underestimate);
2738 	
2739 	#ifndef NDEBUG
2740 	         /* make sure that the term is violated */
2741 	         productval = SCIPgetSolVal(scip, sol, terms[i].x) * SCIPgetSolVal(scip, sol, terms[i].y);
2742 	         auxval = SCIPevalBilinAuxExprNonlinear(scip, terms[i].x, terms[i].y, auxexpr, sol);
2743 	
2744 	         /* if underestimate, then xy <= aux must be violated; otherwise aux <= xy must be violated */
2745 	         assert((underestimate && SCIPisFeasLT(scip, auxval, productval)) ||
2746 	               (!underestimate && SCIPisFeasLT(scip, productval, auxval)));
2747 	#endif
2748 	
2749 	         /* create an empty row */
2750 	         (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "mccormick_%sestimate_implicit_%s*%s_%" SCIP_LONGINT_FORMAT,
2751 	                             underestimate ? "under" : "over", SCIPvarGetName(terms[i].x), SCIPvarGetName(terms[i].y),
2752 	                             SCIPgetNLPs(scip));
2753 	
2754 	         SCIP_CALL(SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), SCIPinfinity(scip), TRUE,
2755 	               FALSE, FALSE) );
2756 	
2757 	         xcoef = 0.0;
2758 	         ycoef = 0.0;
2759 	         auxcoef = 0.0;
2760 	         constant = 0.0;
2761 	         success = TRUE;
2762 	
2763 	         /* subtract auxexpr from the cut */
2764 	         addAuxexprCoefs(terms[i].x, terms[i].y, auxexpr, -1.0, &auxcoef, &xcoef, &ycoef, &constant);
2765 	
2766 	         /* add McCormick terms: ask for an underestimator if relation is xy <= auxexpr, and vice versa */
2767 	         SCIPaddBilinMcCormick(scip, 1.0, bndx.inf, bndx.sup, refpointx, bndy.inf, bndy.sup, refpointy, !underestimate,
2768 	               &xcoef, &ycoef, &constant, &success);
2769 	
2770 	         if( REALABS(constant) > MAXVARBOUND )
2771 	            success = FALSE;
2772 	
2773 	         if( success )
2774 	         {
2775 	            assert(!SCIPisInfinity(scip, REALABS(xcoef)));
2776 	            assert(!SCIPisInfinity(scip, REALABS(ycoef)));
2777 	            assert(!SCIPisInfinity(scip, REALABS(constant)));
2778 	
2779 	            SCIP_CALL( SCIPaddVarToRow(scip, cut, terms[i].x, xcoef) );
2780 	            SCIP_CALL( SCIPaddVarToRow(scip, cut, terms[i].y, ycoef) );
2781 	            SCIP_CALL( SCIPaddVarToRow(scip, cut, auxexpr->auxvar, auxcoef) );
2782 	
2783 	            /* set side */
2784 	            if( underestimate )
2785 	               SCIP_CALL( SCIPchgRowRhs(scip, cut, -constant) );
2786 	            else
2787 	               SCIP_CALL( SCIPchgRowLhs(scip, cut, -constant) );
2788 	
2789 	            /* if the cut is violated, add it to SCIP */
2790 	            if( SCIPisFeasNegative(scip, SCIPgetRowFeasibility(scip, cut)) )
2791 	            {
2792 	               SCIP_CALL( SCIPaddRow(scip, cut, FALSE, &cutoff) );
2793 	               *result = SCIP_SEPARATED;
2794 	            }
2795 	            else
2796 	            {
2797 	               SCIPdebugMsg(scip, "\nMcCormick cut for hidden product <%s>*<%s> was created successfully, but is not violated",
2798 	                            SCIPvarGetName(terms[i].x), SCIPvarGetName(terms[i].y));
2799 	            }
2800 	         }
2801 	
2802 	         /* release the cut */
2803 	         if( cut != NULL )
2804 	         {
2805 	            SCIP_CALL( SCIPreleaseRow(scip, &cut) );
2806 	         }
2807 	
2808 	         if( cutoff )
2809 	         {
2810 	            *result = SCIP_CUTOFF;
2811 	            SCIPdebugMsg(scip, "exit separator because we found a cutoff -> skip\n");
2812 	            return SCIP_OKAY;
2813 	         }
2814 	      }
2815 	   }
2816 	
2817 	   return SCIP_OKAY;
2818 	}
2819 	
2820 	/** builds and adds the RLT cuts */
2821 	static
2822 	SCIP_RETCODE separateRltCuts(
2823 	   SCIP*                 scip,               /**< SCIP data structure */
2824 	   SCIP_SEPA*            sepa,               /**< separator */
2825 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
2826 	   SCIP_CONSHDLR*        conshdlr,           /**< nonlinear constraint handler */
2827 	   SCIP_SOL*             sol,                /**< the point to be separated (can be NULL) */
2828 	   SCIP_HASHMAP*         row_to_pos,         /**< hashmap linking row indices to positions in array */
2829 	   RLT_SIMPLEROW*        projrows,           /**< projected rows */
2830 	   SCIP_ROW**            rows,               /**< problem rows */
2831 	   int                   nrows,              /**< number of problem rows */
2832 	   SCIP_Bool             allowlocal,         /**< are local cuts allowed? */
2833 	   int*                  bestunderestimators,/**< indices of auxiliary underestimators with largest violation in sol */
2834 	   int*                  bestoverestimators, /**< indices of auxiliary overestimators with largest violation in sol */
2835 	   SCIP_RESULT*          result              /**< buffer to store whether separation was successful */
2836 	   )
2837 	{
2838 	   int j;
2839 	   int r;
2840 	   int k;
2841 	   int nmarked;
2842 	   int cutssize;
2843 	   int ncuts;
2844 	   SCIP_VAR* xj;
2845 	   unsigned int* row_marks;
2846 	   int* row_idcs;
2847 	   SCIP_ROW* cut;
2848 	   SCIP_ROW** cuts;
2849 	   SCIP_Bool uselb[4] = {TRUE, TRUE, FALSE, FALSE};
2850 	   SCIP_Bool uselhs[4] = {TRUE, FALSE, TRUE, FALSE};
2851 	   SCIP_Bool success;
2852 	   SCIP_Bool infeasible;
2853 	   SCIP_Bool accepted;
2854 	   SCIP_Bool buildeqcut;
2855 	   SCIP_Bool iseqrow;
2856 	
2857 	   assert(!sepadata->useprojection || projrows != NULL);
2858 	   assert(!sepadata->detecthidden || (bestunderestimators != NULL && bestoverestimators != NULL));
2859 	
2860 	   ncuts = 0;
2861 	   cutssize = 0;
2862 	   cuts = NULL;
2863 	   *result = SCIP_DIDNOTFIND;
2864 	
2865 	   SCIP_CALL( SCIPallocCleanBufferArray(scip, &row_marks, nrows) );
2866 	   SCIP_CALL( SCIPallocBufferArray(scip, &row_idcs, nrows) );
2867 	
2868 	   /* loop through all variables that appear in bilinear products */
2869 	   for( j = 0; j < sepadata->nbilinvars && (sepadata->maxusedvars < 0 || j < sepadata->maxusedvars); ++j )
2870 	   {
2871 	      xj = sepadata->varssorted[j];
2872 	
2873 	      /* mark all rows for multiplier xj */
2874 	      SCIP_CALL( markRowsXj(scip, sepadata, conshdlr, sol, j, allowlocal, row_to_pos, bestunderestimators,
2875 	         bestoverestimators, row_marks, row_idcs, &nmarked) );
2876 	
2877 	      assert(nmarked <= nrows);
2878 	
2879 	      /* generate the projected cut and if it is violated, generate the actual cut */
2880 	      for( r = 0; r < nmarked; ++r )
2881 	      {
2882 	         int pos;
2883 	         int currentnunknown;
2884 	         SCIP_ROW* row;
2885 	
2886 	         assert(row_marks[r] != 0);
2887 	         assert(SCIPhashmapExists(row_to_pos, (void*)(size_t) row_idcs[r])); /*lint !e571 */
2888 	
2889 	         pos = SCIPhashmapGetImageInt(row_to_pos, (void*)(size_t) row_idcs[r]); /*lint !e571 */
2890 	         row = rows[pos];
2891 	         assert(SCIProwGetIndex(row) == row_idcs[r]);
2892 	
2893 	         /* check whether this row and var fulfill the conditions */
2894 	         SCIP_CALL( isAcceptableRow(sepadata, row, xj, &currentnunknown, &accepted) );
2895 	         if( !accepted )
2896 	         {
2897 	            SCIPdebugMsg(scip, "rejected row <%s> for variable <%s> (introduces too many new products)\n", SCIProwGetName(row), SCIPvarGetName(xj));
2898 	            row_marks[r] = 0;
2899 	            continue;
2900 	         }
2901 	
2902 	         SCIPdebugMsg(scip, "accepted row <%s> for variable <%s>\n", SCIProwGetName(rows[r]), SCIPvarGetName(xj));
2903 	#ifdef SCIP_DEBUG
2904 	         SCIP_CALL( SCIPprintRow(scip, rows[r], NULL) );
2905 	#endif
2906 	         iseqrow = SCIPisEQ(scip, SCIProwGetLhs(row), SCIProwGetRhs(row));
2907 	
2908 	         /* if all terms are known and it is an equality row, compute equality cut, that is, multiply row with (x-lb) and/or (ub-x) (but see also @todo at top)
2909 	          * otherwise, multiply row w.r.t. lhs and/or rhs with (x-lb) and/or (ub-x) and estimate product terms that have no aux.var or aux.expr
2910 	          */
2911 	         buildeqcut = (currentnunknown == 0 && iseqrow);
2912 	
2913 	         /* go over all suitable combinations of sides and bounds and compute the respective cuts */
2914 	         for( k = 0; k < 4; ++k )
2915 	         {
2916 	            /* if equality cuts are possible, lhs and rhs cuts are equal so skip rhs */
2917 	            if( buildeqcut )
2918 	            {
2919 	               if( k != 1 )
2920 	                  continue;
2921 	            }
2922 	            /* otherwise which cuts are generated depends on the marks */
2923 	            else
2924 	            {
2925 	               if( row_marks[r] == 1 && uselb[k] == uselhs[k] )
2926 	                  continue;
2927 	
2928 	               if( row_marks[r] == 2 && uselb[k] != uselhs[k] )
2929 	                  continue;
2930 	            }
2931 	
2932 	            success = TRUE;
2933 	            cut = NULL;
2934 	
2935 	            SCIPdebugMsg(scip, "row <%s>, uselb = %u, uselhs = %u\n", SCIProwGetName(row), uselb[k], uselhs[k]);
2936 	
2937 	            if( sepadata->useprojection )
2938 	            {
2939 	               /* if no variables are left in the projected row, the RLT cut will not be violated */
2940 	               if( projrows[pos].nnonz == 0 )
2941 	                  continue;
2942 	
2943 	               /* compute the rlt cut for a projected row first */
2944 	               SCIP_CALL( computeRltCut(scip, sepa, sepadata, &cut, NULL, &(projrows[pos]), sol, bestunderestimators,
2945 	                     bestoverestimators, xj, &success, uselb[k], uselhs[k], allowlocal, buildeqcut, TRUE) );
2946 	
2947 	               /* if the projected cut is not violated, set success to FALSE */
2948 	               if( cut != NULL )
2949 	               {
2950 	                  SCIPdebugMsg(scip, "proj cut viol = %g\n", -SCIPgetRowFeasibility(scip, cut));
2951 	               }
2952 	               if( cut != NULL && !SCIPisFeasPositive(scip, -SCIPgetRowFeasibility(scip, cut)) )
2953 	               {
2954 	                  SCIPdebugMsg(scip, "projected cut is not violated, feasibility = %g\n", SCIPgetRowFeasibility(scip, cut));
2955 	                  success = FALSE;
2956 	               }
2957 	
2958 	               /* release the projected cut */
2959 	               if( cut != NULL )
2960 	                  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
2961 	            }
2962 	
2963 	            /* if we don't use projection or if the projected cut was generated successfully and is violated,
2964 	             * generate the actual cut */
2965 	            if( success )
2966 	            {
2967 	               SCIP_CALL( computeRltCut(scip, sepa, sepadata, &cut, row, NULL, sol, bestunderestimators,
2968 	                     bestoverestimators, xj, &success, uselb[k], uselhs[k], allowlocal, buildeqcut, FALSE) );
2969 	            }
2970 	
2971 	            if( success )
2972 	            {
2973 	               success = SCIPisFeasNegative(scip, SCIPgetRowFeasibility(scip, cut)) || (sepadata->addtopool &&
2974 	                       !SCIProwIsLocal(cut));
2975 	            }
2976 	
2977 	            /* if the cut was created successfully and is violated or (if addtopool == TRUE) globally valid,
2978 	             * it is added to the cuts array */
2979 	            if( success )
2980 	            {
2981 	               if( ncuts + 1 > cutssize )
2982 	               {
2983 	                  int newsize;
2984 	
2985 	                  newsize = SCIPcalcMemGrowSize(scip, ncuts + 1);
2986 	                  SCIP_CALL( SCIPreallocBufferArray(scip, &cuts, newsize) );
2987 	                  cutssize = newsize;
2988 	               }
2989 	               cuts[ncuts] = cut;
2990 	               (ncuts)++;
2991 	            }
2992 	            else
2993 	            {
2994 	               SCIPdebugMsg(scip, "the generation of the cut failed or cut not violated and not added to cutpool\n");
2995 	               /* release the cut */
2996 	               if( cut != NULL )
2997 	               {
2998 	                  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
2999 	               }
3000 	            }
3001 	         }
3002 	
3003 	         /* clear row_marks[r] since it will be used for the next multiplier */
3004 	         row_marks[r] = 0;
3005 	      }
3006 	   }
3007 	
3008 	   /* if cuts were found, we apply an additional filtering procedure, which is similar to sepastore */
3009 	   if( ncuts > 0  )
3010 	   {
3011 	      int nselectedcuts;
3012 	      int i;
3013 	
3014 	      assert(cuts != NULL);
3015 	
3016 	      SCIP_CALL( SCIPselectCutsHybrid(scip, cuts, NULL, NULL, sepadata->goodscore, sepadata->badscore, sepadata->goodmaxparall,
3017 	            sepadata->maxparall, sepadata->dircutoffdistweight, sepadata->efficacyweight, sepadata->objparalweight,
3018 	            0.0, ncuts, 0, sepadata->maxncuts == -1 ? ncuts : sepadata->maxncuts, &nselectedcuts) );
3019 	
3020 	      for( i = 0; i < ncuts; ++i )
3021 	      {
3022 	         assert(cuts[i] != NULL);
3023 	
3024 	         if( i < nselectedcuts )
3025 	         {
3026 	            /* if selected, add global cuts to the pool and local cuts to the sepastore */
3027 	            if( SCIProwIsLocal(cuts[i]) || !sepadata->addtopool )
3028 	            {
3029 	               SCIP_CALL( SCIPaddRow(scip, cuts[i], FALSE, &infeasible) );
3030 	
3031 	               if( infeasible )
3032 	               {
3033 	                  SCIPdebugMsg(scip, "CUTOFF! The cut <%s> revealed infeasibility\n", SCIProwGetName(cuts[i]));
3034 	                  *result = SCIP_CUTOFF;
3035 	               }
3036 	               else
3037 	               {
3038 	                  SCIPdebugMsg(scip, "SEPARATED: added cut to scip\n");
3039 	                  *result = SCIP_SEPARATED;
3040 	               }
3041 	            }
3042 	            else
3043 	            {
3044 	               SCIP_CALL( SCIPaddPoolCut(scip, cuts[i]) );
3045 	            }
3046 	         }
3047 	
3048 	         /* release current cut */
3049 	         SCIP_CALL( SCIPreleaseRow(scip, &cuts[i]) );
3050 	      }
3051 	   }
3052 	
3053 	   SCIPdebugMsg(scip, "exit separator because cut calculation is finished\n");
3054 	
3055 	   SCIPfreeBufferArrayNull(scip, &cuts);
3056 	   SCIPfreeBufferArray(scip, &row_idcs);
3057 	   SCIPfreeCleanBufferArray(scip, &row_marks);
3058 	
3059 	   return SCIP_OKAY;
3060 	}
3061 	
3062 	/*
3063 	 * Callback methods of separator
3064 	 */
3065 	
3066 	/** copy method for separator plugins (called when SCIP copies plugins) */
3067 	static
3068 	SCIP_DECL_SEPACOPY(sepaCopyRlt)
3069 	{  /*lint --e{715}*/
3070 	   assert(scip != NULL);
3071 	   assert(sepa != NULL);
3072 	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
3073 	
3074 	   /* call inclusion method of separator */
3075 	   SCIP_CALL( SCIPincludeSepaRlt(scip) );
3076 	
3077 	   return SCIP_OKAY;
3078 	}
3079 	
3080 	/** destructor of separator to free user data (called when SCIP is exiting) */
3081 	static
3082 	SCIP_DECL_SEPAFREE(sepaFreeRlt)
3083 	{  /*lint --e{715}*/
3084 	   SCIP_SEPADATA* sepadata;
3085 	
3086 	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
3087 	
3088 	   sepadata = SCIPsepaGetData(sepa);
3089 	   assert(sepadata != NULL);
3090 	
3091 	   /* free separator data */
3092 	   SCIPfreeBlockMemory(scip, &sepadata);
3093 	
3094 	   SCIPsepaSetData(sepa, NULL);
3095 	
3096 	   return SCIP_OKAY;
3097 	}
3098 	
3099 	/** solving process deinitialization method of separator (called before branch and bound process data is freed) */
3100 	static
3101 	SCIP_DECL_SEPAEXITSOL(sepaExitsolRlt)
3102 	{  /*lint --e{715}*/
3103 	   SCIP_SEPADATA* sepadata;
3104 	
3105 	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
3106 	
3107 	   sepadata = SCIPsepaGetData(sepa);
3108 	   assert(sepadata != NULL);
3109 	
3110 	   if( sepadata->iscreated )
3111 	   {
3112 	      SCIP_CALL( freeSepaData(scip, sepadata) );
3113 	   }
3114 	
3115 	   return SCIP_OKAY;
3116 	}
3117 	
3118 	/** LP solution separation method of separator */
3119 	static
3120 	SCIP_DECL_SEPAEXECLP(sepaExeclpRlt)
3121 	{  /*lint --e{715}*/
3122 	   SCIP_ROW** prob_rows;
3123 	   SCIP_ROW** rows;
3124 	   SCIP_SEPADATA* sepadata;
3125 	   int ncalls;
3126 	   int nrows;
3127 	   SCIP_HASHMAP* row_to_pos;
3128 	   RLT_SIMPLEROW* projrows;
3129 	
3130 	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
3131 	
3132 	   sepadata = SCIPsepaGetData(sepa);
3133 	   *result = SCIP_DIDNOTRUN;
3134 	
3135 	   if( sepadata->maxncuts == 0 )
3136 	   {
3137 	      SCIPdebugMsg(scip, "exit separator because maxncuts is set to 0\n");
3138 	      return SCIP_OKAY;
3139 	   }
3140 	
3141 	   /* don't run in a sub-SCIP or in probing */
3142 	   if( SCIPgetSubscipDepth(scip) > 0 && !sepadata->useinsubscip )
3143 	   {
3144 	      SCIPdebugMsg(scip, "exit separator because in sub-SCIP\n");
3145 	      return SCIP_OKAY;
3146 	   }
3147 	
3148 	   /* don't run in probing */
3149 	   if( SCIPinProbing(scip) )
3150 	   {
3151 	      SCIPdebugMsg(scip, "exit separator because in probing\n");
3152 	      return SCIP_OKAY;
3153 	   }
3154 	
3155 	   /* only call separator a given number of times at each node */
3156 	   ncalls = SCIPsepaGetNCallsAtNode(sepa);
3157 	   if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
3158 	        || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
3159 	   {
3160 	      SCIPdebugMsg(scip, "exit separator because round limit for this node is reached\n");
3161 	      return SCIP_OKAY;
3162 	   }
3163 	
3164 	   /* if this is called for the first time, create the sepadata and start the initial separation round */
3165 	   if( !sepadata->iscreated )
3166 	   {
3167 	      *result = SCIP_DIDNOTFIND;
3168 	      SCIP_CALL( createSepaData(scip, sepadata) );
3169 	   }
3170 	   assert(sepadata->iscreated || (sepadata->nbilinvars == 0 && sepadata->nbilinterms == 0));
3171 	   assert(sepadata->nbilinterms == SCIPgetNBilinTermsNonlinear(sepadata->conshdlr));
3172 	
3173 	   /* no bilinear terms available -> skip */
3174 	   if( sepadata->nbilinvars == 0 )
3175 	   {
3176 	      SCIPdebugMsg(scip, "exit separator because there are no known bilinear terms\n");
3177 	      return SCIP_OKAY;
3178 	   }
3179 	
3180 	   /* only call separator, if we are not close to terminating */
3181 	   if( SCIPisStopped(scip) )
3182 	   {
3183 	      SCIPdebugMsg(scip, "exit separator because we are too close to terminating\n");
3184 	      return SCIP_OKAY;
3185 	   }
3186 	
3187 	   /* only call separator, if an optimal LP solution is at hand */
3188 	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
3189 	   {
3190 	      SCIPdebugMsg(scip, "exit separator because there is no LP solution at hand\n");
3191 	      return SCIP_OKAY;
3192 	   }
3193 	
3194 	   /* get the rows, depending on settings */
3195 	   if( sepadata->isinitialround || sepadata->onlyoriginal )
3196 	   {
3197 	      SCIP_CALL( getOriginalRows(scip, &prob_rows, &nrows) );
3198 	   }
3199 	   else
3200 	   {
3201 	      SCIP_CALL( SCIPgetLPRowsData(scip, &prob_rows, &nrows) );
3202 	   }
3203 	
3204 	   /* save the suitable rows */
3205 	   SCIP_CALL( SCIPallocBufferArray(scip, &rows, nrows) );
3206 	   SCIP_CALL( SCIPhashmapCreate(&row_to_pos, SCIPblkmem(scip), nrows) );
3207 	
3208 	   SCIP_CALL( storeSuitableRows(scip, sepa, sepadata, prob_rows, rows, &nrows, row_to_pos, allowlocal) );
3209 	
3210 	   if( nrows == 0 ) /* no suitable rows found, free memory and exit */
3211 	   {
3212 	      SCIPhashmapFree(&row_to_pos);
3213 	      SCIPfreeBufferArray(scip, &rows);
3214 	      if( sepadata->isinitialround || sepadata->onlyoriginal )
3215 	      {
3216 	         SCIPfreeBufferArray(scip, &prob_rows);
3217 	         sepadata->isinitialround = FALSE;
3218 	      }
3219 	      return SCIP_OKAY;
3220 	   }
3221 	
3222 	   /* create the projected problem */
3223 	   if( sepadata->useprojection )
3224 	   {
3225 	      SCIP_Bool allcst;
3226 	
3227 	      SCIP_CALL( createProjRows(scip, rows, nrows, NULL, &projrows, allowlocal, &allcst) );
3228 	
3229 	      /* if all projected rows have only constants left, quit */
3230 	      if( allcst )
3231 	         goto TERMINATE;
3232 	
3233 	#ifdef SCIP_DEBUG
3234 	      printProjRows(scip, projrows, nrows, NULL);
3235 	#endif
3236 	   }
3237 	   else
3238 	   {
3239 	      projrows = NULL;
3240 	   }
3241 	
3242 	   /* separate the cuts */
3243 	   if( sepadata->detecthidden )
3244 	   {
3245 	      int* bestunderestimators;
3246 	      int* bestoverestimators;
3247 	
3248 	      /* if we detect implicit products, a term might have more than one estimator in each direction;
3249 	       * save the indices of the most violated estimators
3250 	       */
3251 	      SCIP_CALL( SCIPallocBufferArray(scip, &bestunderestimators, sepadata->nbilinterms) );
3252 	      SCIP_CALL( SCIPallocBufferArray(scip, &bestoverestimators, sepadata->nbilinterms) );
3253 	      getBestEstimators(scip, sepadata, NULL, bestunderestimators, bestoverestimators);
3254 	
3255 	      /* also separate McCormick cuts for implicit products */
3256 	      SCIP_CALL( separateMcCormickImplicit(scip, sepa, sepadata, NULL, bestunderestimators, bestoverestimators,
3257 	            result) );
3258 	
3259 	      if( *result != SCIP_CUTOFF )
3260 	      {
3261 	         SCIP_CALL( separateRltCuts(scip, sepa, sepadata, sepadata->conshdlr, NULL, row_to_pos, projrows, rows, nrows,
3262 	               allowlocal, bestunderestimators, bestoverestimators, result) );
3263 	      }
3264 	
3265 	      SCIPfreeBufferArray(scip, &bestoverestimators);
3266 	      SCIPfreeBufferArray(scip, &bestunderestimators);
3267 	   }
3268 	   else
3269 	   {
3270 	      SCIP_CALL( separateRltCuts(scip, sepa, sepadata, sepadata->conshdlr, NULL, row_to_pos, projrows, rows, nrows,
3271 	            allowlocal, NULL, NULL, result) );
3272 	   }
3273 	
3274 	 TERMINATE:
3275 	   /* free the projected problem */
3276 	   if( sepadata->useprojection )
3277 	   {
3278 	      freeProjRows(scip, &projrows, nrows);
3279 	   }
3280 	
3281 	   SCIPhashmapFree(&row_to_pos);
3282 	   SCIPfreeBufferArray(scip, &rows);
3283 	
3284 	   if( sepadata->isinitialround || sepadata->onlyoriginal )
3285 	   {
3286 	      SCIPfreeBufferArray(scip, &prob_rows);
3287 	      sepadata->isinitialround = FALSE;
3288 	   }
3289 	
3290 	   return SCIP_OKAY;
3291 	}
3292 	
3293 	/*
3294 	 * separator specific interface methods
3295 	 */
3296 	
3297 	/** creates the RLT separator and includes it in SCIP */
3298 	SCIP_RETCODE SCIPincludeSepaRlt(
3299 	   SCIP*                 scip                /**< SCIP data structure */
3300 	   )
3301 	{
3302 	   SCIP_SEPADATA* sepadata;
3303 	   SCIP_SEPA* sepa;
3304 	
3305 	   /* create RLT separator data */
3306 	   SCIP_CALL( SCIPallocClearBlockMemory(scip, &sepadata) );
3307 	   sepadata->conshdlr = SCIPfindConshdlr(scip, "nonlinear");
3308 	   assert(sepadata->conshdlr != NULL);
3309 	
3310 	   /* include separator */
3311 	   SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
3312 	         SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpRlt, NULL, sepadata) );
3313 	
3314 	   /* set non fundamental callbacks via setter functions */
3315 	   SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyRlt) );
3316 	   SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeRlt) );
3317 	   SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolRlt) );
3318 	
3319 	   /* add RLT separator parameters */
3320 	   SCIP_CALL( SCIPaddIntParam(scip,
3321 	         "separating/" SEPA_NAME "/maxncuts",
3322 	         "maximal number of rlt-cuts that are added per round (-1: unlimited)",
3323 	         &sepadata->maxncuts, FALSE, DEFAULT_MAXNCUTS, -1, INT_MAX, NULL, NULL) );
3324 	
3325 	   SCIP_CALL( SCIPaddIntParam(scip,
3326 	         "separating/" SEPA_NAME "/maxunknownterms",
3327 	         "maximal number of unknown bilinear terms a row is still used with (-1: unlimited)",
3328 	         &sepadata->maxunknownterms, FALSE, DEFAULT_MAXUNKNOWNTERMS, -1, INT_MAX, NULL, NULL) );
3329 	
3330 	   SCIP_CALL( SCIPaddIntParam(scip,
3331 	         "separating/" SEPA_NAME "/maxusedvars",
3332 	         "maximal number of variables used to compute rlt cuts (-1: unlimited)",
3333 	         &sepadata->maxusedvars, FALSE, DEFAULT_MAXUSEDVARS, -1, INT_MAX, NULL, NULL) );
3334 	
3335 	   SCIP_CALL( SCIPaddIntParam(scip,
3336 	      "separating/" SEPA_NAME "/maxrounds",
3337 	      "maximal number of separation rounds per node (-1: unlimited)",
3338 	      &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
3339 	
3340 	   SCIP_CALL( SCIPaddIntParam(scip,
3341 	      "separating/" SEPA_NAME "/maxroundsroot",
3342 	      "maximal number of separation rounds in the root node (-1: unlimited)",
3343 	      &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
3344 	
3345 	   SCIP_CALL( SCIPaddBoolParam(scip,
3346 	      "separating/" SEPA_NAME "/onlyeqrows",
3347 	      "if set to true, only equality rows are used for rlt cuts",
3348 	      &sepadata->onlyeqrows, FALSE, DEFAULT_ONLYEQROWS, NULL, NULL) );
3349 	
3350 	   SCIP_CALL( SCIPaddBoolParam(scip,
3351 	      "separating/" SEPA_NAME "/onlycontrows",
3352 	      "if set to true, only continuous rows are used for rlt cuts",
3353 	      &sepadata->onlycontrows, FALSE, DEFAULT_ONLYCONTROWS, NULL, NULL) );
3354 	
3355 	   SCIP_CALL( SCIPaddBoolParam(scip,
3356 	      "separating/" SEPA_NAME "/onlyoriginal",
3357 	      "if set to true, only original rows and variables are used",
3358 	      &sepadata->onlyoriginal, FALSE, DEFAULT_ONLYORIGINAL, NULL, NULL) );
3359 	
3360 	   SCIP_CALL( SCIPaddBoolParam(scip,
3361 	      "separating/" SEPA_NAME "/useinsubscip",
3362 	      "if set to true, rlt is also used in sub-scips",
3363 	      &sepadata->useinsubscip, FALSE, DEFAULT_USEINSUBSCIP, NULL, NULL) );
3364 	
3365 	   SCIP_CALL( SCIPaddBoolParam(scip,
3366 	                               "separating/" SEPA_NAME "/useprojection",
3367 	      "if set to true, projected rows are checked first",
3368 	      &sepadata->useprojection, FALSE, DEFAULT_USEPROJECTION, NULL, NULL) );
3369 	
3370 	   SCIP_CALL( SCIPaddBoolParam(scip,
3371 	                               "separating/" SEPA_NAME "/detecthidden",
3372 	      "if set to true, hidden products are detected and separated by McCormick cuts",
3373 	      &sepadata->detecthidden, FALSE, DEFAULT_DETECTHIDDEN, NULL, NULL) );
3374 	
3375 	   SCIP_CALL( SCIPaddBoolParam(scip,
3376 	                               "separating/" SEPA_NAME "/hiddenrlt",
3377 	      "whether RLT cuts (TRUE) or only McCormick inequalities (FALSE) should be added for hidden products",
3378 	      &sepadata->hiddenrlt, FALSE, DEFAULT_HIDDENRLT, NULL, NULL) );
3379 	
3380 	   SCIP_CALL( SCIPaddBoolParam(scip,
3381 	                               "separating/" SEPA_NAME "/addtopool",
3382 	      "if set to true, globally valid RLT cuts are added to the global cut pool",
3383 	      &sepadata->addtopool, FALSE, DEFAULT_ADDTOPOOL, NULL, NULL) );
3384 	
3385 	   SCIP_CALL( SCIPaddRealParam(scip,
3386 	                               "separating/" SEPA_NAME "/goodscore",
3387 	      "threshold for score of cut relative to best score to be considered good, so that less strict filtering is applied",
3388 	      &sepadata->goodscore, TRUE, DEFAULT_GOODSCORE, 0.0, 1.0, NULL, NULL) );
3389 	
3390 	   SCIP_CALL( SCIPaddRealParam(scip,
3391 	                               "separating/" SEPA_NAME "/badscore",
3392 	      "threshold for score of cut relative to best score to be discarded",
3393 	      &sepadata->badscore, TRUE, DEFAULT_BADSCORE, 0.0, 1.0, NULL, NULL) );
3394 	
3395 	   SCIP_CALL( SCIPaddRealParam(scip,
3396 	                               "separating/" SEPA_NAME "/objparalweight",
3397 	      "weight of objective parallelism in cut score calculation",
3398 	      &sepadata->objparalweight, TRUE, DEFAULT_OBJPARALWEIGHT, 0.0, 1.0, NULL, NULL) );
3399 	
3400 	   SCIP_CALL( SCIPaddRealParam(scip,
3401 	                               "separating/" SEPA_NAME "/efficacyweight",
3402 	      "weight of efficacy in cut score calculation",
3403 	      &sepadata->efficacyweight, TRUE, DEFAULT_EFFICACYWEIGHT, 0.0, 1.0, NULL, NULL) );
3404 	
3405 	   SCIP_CALL( SCIPaddRealParam(scip,
3406 	                               "separating/" SEPA_NAME "/dircutoffdistweight",
3407 	      "weight of directed cutoff distance in cut score calculation",
3408 	      &sepadata->dircutoffdistweight, TRUE, DEFAULT_DIRCUTOFFDISTWEIGHT, 0.0, 1.0, NULL, NULL) );
3409 	
3410 	   SCIP_CALL( SCIPaddRealParam(scip,
3411 	                               "separating/" SEPA_NAME "/goodmaxparall",
3412 	      "maximum parallelism for good cuts",
3413 	      &sepadata->goodmaxparall, TRUE, DEFAULT_GOODMAXPARALL, 0.0, 1.0, NULL, NULL) );
3414 	
3415 	   SCIP_CALL( SCIPaddRealParam(scip,
3416 	                               "separating/" SEPA_NAME "/maxparall",
3417 	      "maximum parallelism for non-good cuts",
3418 	      &sepadata->maxparall, TRUE, DEFAULT_MAXPARALL, 0.0, 1.0, NULL, NULL) );
3419 	
3420 	   return SCIP_OKAY;
3421 	}
3422