Scippy

SCIP

Solving Constraint Integer Programs

sepa_rlt.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 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 };
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 };
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
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
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
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
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
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
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
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 
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);
572  varmapsize = sepadata->detecthidden ? nvars : MIN(nvars, sepadata->nbilinterms * 2);
573 
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 
582  if( xpos == INT_MAX )
583  {
584  /* add x to sepadata and initialise its priority */
585  SCIP_CALL( SCIPhashmapInsertInt(varmap, (void*)(size_t) xidx, sepadata->nbilinvars) ); /*lint !e571*/
586  SCIP_CALL( ensureVarsSize(scip, sepadata, sepadata->nbilinvars + 1) );
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
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 
712  SCIPdebugMsg(scip, "Extracting product from two implied relations:\n");
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 ? ">=" : "<=",
715  f ? d1 - a1 : d1);
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 ? ">=" : "<=",
718  f ? d2 : d2 - a2);
719 
720  /* cannot use a global bound on x to detect a product */
721  if( (b1 == 0.0 && c1 == 0.0) || (b2 == 0.0 && c2 == 0.0) )
722  return SCIP_OKAY;
723 
724  /* cannot use a global bound on y to detect a non-redundant product relation */
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;
729  }
730 
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 */
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;
747  }
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;
755  }
756 
757  /* the linear relations imply a product only if the inequality signs are similar */
758  if( sidetype1 != sidetype2 )
759  return SCIP_OKAY;
760 
761  /* when b1c2 = b2c1, the linear relations do not imply a product relation */
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;
766  }
767 
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 */
787  overestimate = (sidetype1 == SCIP_SIDETYPE_LEFT && mult > 0.0) || (sidetype1 == SCIP_SIDETYPE_RIGHT && mult < 0.0);
788 
789  SCIPdebugMsg(scip, "found suitable implied rels (w,x,y): %g<%s> + %g<%s> + %g<%s> <= %g\n", a1,
790  SCIPvarGetName(x), b1, SCIPvarGetName(w), c1, SCIPvarGetName(y), d1);
791  SCIPdebugMsg(scip, " and %g<%s> + %g<%s> + %g<%s> <= %g\n", a2, SCIPvarGetName(x),
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 
800  SCIPdebugMsg(scip, "product: <%s><%s> %s %g<%s> + %g<%s> + %g<%s> + %g\n", SCIPvarGetName(x), SCIPvarGetName(y),
801  overestimate ? "<=" : ">=", A, SCIPvarGetName(x), B, SCIPvarGetName(w), C, SCIPvarGetName(y), D);
802 
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
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
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
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
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 */
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 */
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
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 */
1266  SCIP_CALL( getOriginalRows(scip, &prob_rows, &nrows) );
1267 
1268  if( nrows == 0 )
1269  {
1270  SCIPfreeBufferArray(scip, &prob_rows);
1271  return SCIP_OKAY;
1272  }
1273 
1274  /* create tables of implied and unconditional relations */
1275  SCIP_CALL( SCIPhashtableCreate(&hashtable3, SCIPblkmem(scip), nrows, SCIPhashGetKeyStandard,
1276  hashdataKeyEqConss, hashdataKeyValConss, NULL) );
1277  SCIP_CALL( SCIPhashtableCreate(&hashtable2, SCIPblkmem(scip), nrows, SCIPhashGetKeyStandard,
1278  hashdataKeyEqConss, hashdataKeyValConss, NULL) );
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);
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 */
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 */
1292  for( i = 0; i < SCIPhashtableGetNEntries(hashtable3); ++i )
1293  {
1294  foundhashdata = (HASHDATA*)SCIPhashtableGetEntry(hashtable3, i);
1295  if( foundhashdata == NULL )
1296  continue;
1297 
1298  SCIPdebugMsg(scip, "(<%s>, <%s>, <%s>): ", SCIPvarGetName(foundhashdata->vars[0]),
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  */
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 */
1311  if( SCIPvarGetType(vars_xwy[0]) != SCIP_VARTYPE_BINARY )
1312  continue;
1313 
1314  /* the first row might be an implication from f == 0 or f == 1: try both */
1315  for( f = 0; f <= 1; ++f )
1316  {
1317  xfixing = f == 1;
1318 
1319  /* go through implied relations for the corresponding three variables */
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 */
1334  if( (!xfixing && coefs1[0] > 0.0) || (xfixing && coefs1[0] < 0.0) )
1335  {
1336  sidetype1 = SCIP_SIDETYPE_LEFT;
1337  side1 = SCIProwGetLhs(row1);
1338  }
1339  else
1340  {
1341  sidetype1 = SCIP_SIDETYPE_RIGHT;
1342  side1 = SCIProwGetRhs(row1);
1343  }
1344 
1345  if( SCIPisInfinity(scip, REALABS(side1)) )
1346  continue;
1347 
1348  side1 -= SCIProwGetConstant(row1);
1349 
1350  /* permute w and y */
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 */
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 */
1385  if( (!xfixing && coefs2[0] > 0.0) || (xfixing && coefs2[0] < 0.0) )
1386  {
1387  sidetype2 = SCIP_SIDETYPE_RIGHT;
1388  side2 = SCIProwGetRhs(row2);
1389  }
1390  else
1391  {
1392  sidetype2 = SCIP_SIDETYPE_LEFT;
1393  side2 = SCIProwGetLhs(row2);
1394  }
1395 
1396  if( SCIPisInfinity(scip, REALABS(side2)) )
1397  continue;
1398 
1399  side2 -= SCIProwGetConstant(row2);
1400 
1401  SCIPdebugMsg(scip, "Two implied relations:\n");
1402  SCIP_CALL( extractProducts(scip, sepadata, vars_xwy, coefs1, coefs2, side1, side2, sidetype1,
1403  sidetype2, varmap, xfixing) );
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  }
1470  }
1471  }
1472  }
1473  SCIPfreeBuffer(scip, &foundhashdata);
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 ?
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
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 */
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 */
1619  if( sepadata->nbilinterms == 0 && !sepadata->detecthidden )
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);
1626  varmapsize = sepadata->detecthidden ? nvars : MIN(nvars, sepadata->nbilinterms * 2);
1627 
1628  /* create variable map */
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 */
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 */
1642  if( bilinterms[i].aux.var == NULL )
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[var_deref_model] */
1651  SCIP_CALL( addProductVars(scip, sepadata, bilinterms[i].x, bilinterms[i].y, varmap,
1652  bilinterms[i].nlockspos + bilinterms[i].nlocksneg) );
1653  }
1654 
1655  if( sepadata->detecthidden )
1656  {
1657  int oldnterms = sepadata->nbilinterms;
1658 
1659  /* coverity[var_deref_model] */
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;
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
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;
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
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;
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 */
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  /* coverity[var_deref_model] */
2085  SCIP_CALL( SCIPaddVarToRow(scip, cut, auxvar, coefauxvar) );
2086  }
2087 
2088  /* we are done with the product linearisation, now add the term which comes from multiplying
2089  * coef*colvar by the constant part of the bound factor
2090  */
2091 
2092  if( colvar != var )
2093  {
2094  assert(!SCIPisInfinity(scip, REALABS(coefcolvar)));
2095  SCIP_CALL( SCIPaddVarToRow(scip, cut, colvar, coefcolvar) );
2096  }
2097  else
2098  *coefvar += coefcolvar;
2099 
2100  return SCIP_OKAY;
2101 }
2102 
2103 /** creates the RLT cut formed by multiplying a given row with (x - lb) or (ub - x)
2104  *
2105  * In detail:
2106  * - The row is multiplied either with (x - lb(x)) or with (ub(x) - x), depending on parameter `uselb`, or by x if
2107  * this is an equality cut
2108  * - The (inequality) cut is computed either for lhs or rhs, depending on parameter `uselhs`.
2109  * - Terms for which no auxiliary variable and no clique relation exists are replaced by either McCormick, secants,
2110  * or gradient linearization cuts.
2111  */
2112 static
2114  SCIP* scip, /**< SCIP data structure */
2115  SCIP_SEPA* sepa, /**< separator */
2116  SCIP_SEPADATA* sepadata, /**< separation data */
2117  SCIP_ROW** cut, /**< buffer to store the cut */
2118  SCIP_ROW* row, /**< the row that is used for the rlt cut (NULL if using projected row) */
2119  RLT_SIMPLEROW* projrow, /**< projected row that is used for the rlt cut (NULL if using row) */
2120  SCIP_SOL* sol, /**< the point to be separated (can be NULL) */
2121  int* bestunderest, /**< positions of most violated underestimators for each product term */
2122  int* bestoverest, /**< positions of most violated overestimators for each product term */
2123  SCIP_VAR* var, /**< the variable that is used for the rlt cuts */
2124  SCIP_Bool* success, /**< buffer to store whether cut was created successfully */
2125  SCIP_Bool uselb, /**< whether we multiply with (var - lb) or (ub - var) */
2126  SCIP_Bool uselhs, /**< whether to create a cut for the lhs or rhs */
2127  SCIP_Bool local, /**< whether local or global cuts should be computed */
2128  SCIP_Bool computeEqCut, /**< whether conditions are fulfilled to compute equality cuts */
2129  SCIP_Bool useprojrow /**< whether to use projected row instead of normal row */
2130  )
2131 { /*lint --e{413}*/
2132  SCIP_Real signfactor;
2133  SCIP_Real boundfactor;
2134  SCIP_Real lbvar;
2135  SCIP_Real ubvar;
2136  SCIP_Real coefvar;
2137  SCIP_Real consside;
2138  SCIP_Real finalside;
2139  SCIP_Real cstterm;
2140  SCIP_Real lhs;
2141  SCIP_Real rhs;
2142  SCIP_Real rowcst;
2143  int i;
2144  const char* rowname;
2145  char cutname[SCIP_MAXSTRLEN];
2146 
2147  assert(sepadata != NULL);
2148  assert(cut != NULL);
2149  assert(useprojrow || row != NULL);
2150  assert(!useprojrow || projrow != NULL);
2151  assert(var != NULL);
2152  assert(success != NULL);
2153 
2154  lhs = useprojrow ? projrow->lhs : SCIProwGetLhs(row);
2155  rhs = useprojrow ? projrow->rhs : SCIProwGetRhs(row);
2156  rowname = useprojrow ? projrow->name : SCIProwGetName(row);
2157  rowcst = useprojrow ? projrow ->cst : SCIProwGetConstant(row);
2158 
2159  assert(!computeEqCut || SCIPisEQ(scip, lhs, rhs));
2160 
2161  *cut = NULL;
2162 
2163  /* get data for given variable */
2164  if( computeEqCut )
2165  {
2166  lbvar = 0.0;
2167  ubvar = 0.0;
2168  }
2169  else
2170  {
2171  lbvar = local ? SCIPvarGetLbLocal(var) : SCIPvarGetLbGlobal(var);
2172  ubvar = local ? SCIPvarGetUbLocal(var) : SCIPvarGetUbGlobal(var);
2173  }
2174 
2175  /* get row side */
2176  consside = uselhs ? lhs : rhs;
2177 
2178  /* if the bounds are too large or the respective side is infinity, skip this cut */
2179  if( (uselb && REALABS(lbvar) > MAXVARBOUND) || (!uselb && REALABS(ubvar) > MAXVARBOUND)
2180  || SCIPisInfinity(scip, REALABS(consside)) )
2181  {
2182  SCIPdebugMsg(scip, "cut generation for %srow <%s>, %s, and variable <%s> with its %s %g not possible\n",
2183  useprojrow ? "projected " : "", rowname, uselhs ? "lhs" : "rhs", SCIPvarGetName(var),
2184  uselb ? "lower bound" : "upper bound", uselb ? lbvar : ubvar);
2185 
2186  if( REALABS(lbvar) > MAXVARBOUND )
2187  SCIPdebugMsg(scip, " because of lower bound\n");
2188  if( REALABS(ubvar) > MAXVARBOUND )
2189  SCIPdebugMsg(scip, " because of upper bound\n");
2190  if( SCIPisInfinity(scip, REALABS(consside)) )
2191  SCIPdebugMsg(scip, " because of side %g\n", consside);
2192 
2193  *success = FALSE;
2194  return SCIP_OKAY;
2195  }
2196 
2197  /* initialize some factors needed for computation */
2198  coefvar = 0.0;
2199  cstterm = 0.0;
2200  signfactor = (uselb ? 1.0 : -1.0);
2201  boundfactor = (uselb ? -lbvar : ubvar);
2202  *success = TRUE;
2203 
2204  /* create an empty row which we then fill with variables step by step */
2205  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "rlt_%scut_%s_%s_%s_%s_%" SCIP_LONGINT_FORMAT, useprojrow ? "proj" : "", rowname,
2206  uselhs ? "lhs" : "rhs", SCIPvarGetName(var), uselb ? "lb" : "ub", SCIPgetNLPs(scip));
2207  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, cut, sepa, cutname, -SCIPinfinity(scip), SCIPinfinity(scip),
2208  SCIPgetDepth(scip) > 0 && local, FALSE, FALSE) ); /* TODO SCIPgetDepth() should be replaced by depth that is passed on to the SEPAEXEC calls (?) */
2209 
2210  SCIP_CALL( SCIPcacheRowExtensions(scip, *cut) );
2211 
2212  /* iterate over all variables in the row and add the corresponding terms coef*colvar*(bound factor) to the cuts */
2213  for( i = 0; i < (useprojrow ? projrow->nnonz : SCIProwGetNNonz(row)); ++i )
2214  {
2215  SCIP_VAR* colvar;
2216 
2217  colvar = useprojrow ? projrow->vars[i] : SCIPcolGetVar(SCIProwGetCols(row)[i]);
2218  SCIP_CALL( addRltTerm(scip, sepadata, sol, bestunderest, bestoverest, *cut, var, colvar,
2219  useprojrow ? projrow->coefs[i] : SCIProwGetVals(row)[i], uselb, uselhs, local, computeEqCut,
2220  &coefvar, &cstterm, success) );
2221  }
2222 
2223  if( REALABS(cstterm) > MAXVARBOUND )
2224  {
2225  *success = FALSE;
2226  return SCIP_OKAY;
2227  }
2228 
2229  /* multiply (x-lb) or (ub -x) with the lhs and rhs of the row */
2230  coefvar += signfactor * (rowcst - consside);
2231  finalside = boundfactor * (consside - rowcst) - cstterm;
2232 
2233  assert(!SCIPisInfinity(scip, REALABS(coefvar)));
2234  assert(!SCIPisInfinity(scip, REALABS(finalside)));
2235 
2236  /* set the coefficient of var and update the side */
2237  SCIP_CALL( SCIPaddVarToRow(scip, *cut, var, coefvar) );
2238  SCIP_CALL( SCIPflushRowExtensions(scip, *cut) );
2239  if( uselhs || computeEqCut )
2240  {
2241  SCIP_CALL( SCIPchgRowLhs(scip, *cut, finalside) );
2242  }
2243  if( !uselhs || computeEqCut )
2244  {
2245  SCIP_CALL( SCIPchgRowRhs(scip, *cut, finalside) );
2246  }
2247 
2248  SCIPdebugMsg(scip, "%scut was generated successfully:\n", useprojrow ? "projected " : "");
2249 #ifdef SCIP_DEBUG
2250  SCIP_CALL( SCIPprintRow(scip, *cut, NULL) );
2251 #endif
2252 
2253  return SCIP_OKAY;
2254 }
2255 
2256 /** store a row projected by fixing all variables that are at bound at sol; the result is a simplified row */
2257 static
2259  SCIP* scip, /**< SCIP data structure */
2260  RLT_SIMPLEROW* simplerow, /**< pointer to the simplified row */
2261  SCIP_ROW* row, /**< row to be projected */
2262  SCIP_SOL* sol, /**< the point to be separated (can be NULL) */
2263  SCIP_Bool local /**< whether local bounds should be checked */
2264  )
2265 {
2266  int i;
2267  SCIP_VAR* var;
2268  SCIP_Real val;
2269  SCIP_Real vlb;
2270  SCIP_Real vub;
2271 
2272  assert(simplerow != NULL);
2273 
2274  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(simplerow->name), SCIProwGetName(row),
2275  strlen(SCIProwGetName(row))+1) ); /*lint !e666*/
2276  simplerow->nnonz = 0;
2277  simplerow->size = 0;
2278  simplerow->vars = NULL;
2279  simplerow->coefs = NULL;
2280  simplerow->lhs = SCIProwGetLhs(row);
2281  simplerow->rhs = SCIProwGetRhs(row);
2282  simplerow->cst = SCIProwGetConstant(row);
2283 
2284  for( i = 0; i < SCIProwGetNNonz(row); ++i )
2285  {
2286  var = SCIPcolGetVar(SCIProwGetCols(row)[i]);
2287  val = SCIPgetSolVal(scip, sol, var);
2288  vlb = local ? SCIPvarGetLbLocal(var) : SCIPvarGetLbGlobal(var);
2289  vub = local ? SCIPvarGetUbLocal(var) : SCIPvarGetUbGlobal(var);
2290  if( SCIPisFeasEQ(scip, vlb, val) || SCIPisFeasEQ(scip, vub, val) )
2291  {
2292  /* if we are projecting and the var is at bound, add var as a constant to simplerow */
2293  if( !SCIPisInfinity(scip, -simplerow->lhs) )
2294  simplerow->lhs -= SCIProwGetVals(row)[i]*val;
2295  if( !SCIPisInfinity(scip, simplerow->rhs) )
2296  simplerow->rhs -= SCIProwGetVals(row)[i]*val;
2297  }
2298  else
2299  {
2300  if( simplerow->nnonz + 1 > simplerow->size )
2301  {
2302  int newsize;
2303 
2304  newsize = SCIPcalcMemGrowSize(scip, simplerow->nnonz + 1);
2305  SCIP_CALL( SCIPreallocBufferArray(scip, &simplerow->coefs, newsize) );
2306  SCIP_CALL( SCIPreallocBufferArray(scip, &simplerow->vars, newsize) );
2307  simplerow->size = newsize;
2308  }
2309 
2310  /* add the term to simplerow */
2311  simplerow->vars[simplerow->nnonz] = var;
2312  simplerow->coefs[simplerow->nnonz] = SCIProwGetVals(row)[i];
2313  ++(simplerow->nnonz);
2314  }
2315  }
2316 
2317  return SCIP_OKAY;
2318 }
2319 
2320 /** free the projected row */
2321 static
2322 void freeProjRow(
2323  SCIP* scip, /**< SCIP data structure */
2324  RLT_SIMPLEROW* simplerow /**< simplified row to be freed */
2325  )
2326 {
2327  assert(simplerow != NULL);
2328 
2329  if( simplerow->size > 0 )
2330  {
2331  assert(simplerow->vars != NULL);
2332  assert(simplerow->coefs != NULL);
2333 
2334  SCIPfreeBufferArray(scip, &simplerow->vars);
2335  SCIPfreeBufferArray(scip, &simplerow->coefs);
2336  }
2337  SCIPfreeBlockMemoryArray(scip, &simplerow->name, strlen(simplerow->name)+1);
2338 }
2339 
2340 /** creates the projected problem
2341  *
2342  * All variables that are at their bounds at the current solution are added
2343  * to left and/or right hand sides as constant values.
2344  */
2345 static
2347  SCIP* scip, /**< SCIP data structure */
2348  SCIP_ROW** rows, /**< problem rows */
2349  int nrows, /**< number of rows */
2350  SCIP_SOL* sol, /**< the point to be separated (can be NULL) */
2351  RLT_SIMPLEROW** projrows, /**< the projected rows to be filled */
2352  SCIP_Bool local, /**< are local cuts allowed? */
2353  SCIP_Bool* allcst /**< buffer to store whether all projected rows have only constants */
2354  )
2355 {
2356  int i;
2357 
2358  assert(scip != NULL);
2359  assert(rows != NULL);
2360  assert(projrows != NULL);
2361  assert(allcst != NULL);
2362 
2363  *allcst = TRUE;
2364  SCIP_CALL( SCIPallocBufferArray(scip, projrows, nrows) );
2365 
2366  for( i = 0; i < nrows; ++i )
2367  {
2368  /* get a simplified and projected row */
2369  SCIP_CALL( createProjRow(scip, &(*projrows)[i], rows[i], sol, local) );
2370  if( (*projrows)[i].nnonz > 0 )
2371  *allcst = FALSE;
2372  }
2373 
2374  return SCIP_OKAY;
2375 }
2376 
2377 #ifdef SCIP_DEBUG
2378 /* prints the projected LP */
2379 static
2380 void printProjRows(
2381  SCIP* scip, /**< SCIP data structure */
2382  RLT_SIMPLEROW* projrows, /**< the projected rows */
2383  int nrows, /**< number of projected rows */
2384  FILE* file /**< output file (or NULL for standard output) */
2385  )
2386 {
2387  int i;
2388  int j;
2389 
2390  assert(projrows != NULL);
2391 
2392  for( i = 0; i < nrows; ++i )
2393  {
2394  SCIPinfoMessage(scip, file, "\nproj_row[%d]: ", i);
2395  if( !SCIPisInfinity(scip, -projrows[i].lhs) )
2396  SCIPinfoMessage(scip, file, "%.15g <= ", projrows[i].lhs);
2397  for( j = 0; j < projrows[i].nnonz; ++j )
2398  {
2399  if( j == 0 )
2400  {
2401  if( projrows[i].coefs[j] < 0 )
2402  SCIPinfoMessage(scip, file, "-");
2403  }
2404  else
2405  {
2406  if( projrows[i].coefs[j] < 0 )
2407  SCIPinfoMessage(scip, file, " - ");
2408  else
2409  SCIPinfoMessage(scip, file, " + ");
2410  }
2411 
2412  if( projrows[i].coefs[j] != 1.0 )
2413  SCIPinfoMessage(scip, file, "%.15g*", REALABS(projrows[i].coefs[j]));
2414  SCIPinfoMessage(scip, file, "<%s>", SCIPvarGetName(projrows[i].vars[j]));
2415  }
2416  if( projrows[i].cst > 0 )
2417  SCIPinfoMessage(scip, file, " + %.15g", projrows[i].cst);
2418  else if( projrows[i].cst < 0 )
2419  SCIPinfoMessage(scip, file, " - %.15g", REALABS(projrows[i].cst));
2420 
2421  if( !SCIPisInfinity(scip, projrows[i].rhs) )
2422  SCIPinfoMessage(scip, file, " <= %.15g", projrows[i].rhs);
2423  }
2424  SCIPinfoMessage(scip, file, "\n");
2425 }
2426 #endif
2427 
2428 /** frees the projected rows */
2429 static
2430 void freeProjRows(
2431  SCIP* scip, /**< SCIP data structure */
2432  RLT_SIMPLEROW** projrows, /**< the projected LP */
2433  int nrows /**< number of rows in projrows */
2434  )
2435 {
2436  int i;
2437 
2438  for( i = 0; i < nrows; ++i )
2439  freeProjRow(scip, &(*projrows)[i]);
2440 
2441  SCIPfreeBufferArray(scip, projrows);
2442 }
2443 
2444 /** mark a row for rlt cut selection
2445  *
2446  * depending on the sign of the coefficient and violation, set or update mark which cut is required:
2447  * - 1 - cuts for axy < aw case,
2448  * - 2 - cuts for axy > aw case,
2449  * - 3 - cuts for both cases
2450  */
2451 static
2452 void addRowMark(
2453  int ridx, /**< row index */
2454  SCIP_Real a, /**< coefficient of x in the row */
2455  SCIP_Bool violatedbelow, /**< whether the relation auxexpr <= xy is violated */
2456  SCIP_Bool violatedabove, /**< whether the relation xy <= auxexpr is violated */
2457  int* row_idcs, /**< sparse array with indices of marked rows */
2458  unsigned int* row_marks, /**< sparse array to store the marks */
2459  int* nmarked /**< number of marked rows */
2460  )
2461 {
2462  unsigned int newmark;
2463  int pos;
2464  SCIP_Bool exists;
2465 
2466  assert(a != 0.0);
2467 
2468  if( (a > 0.0 && violatedbelow) || (a < 0.0 && violatedabove) )
2469  newmark = 1; /* axy < aw case */
2470  else
2471  newmark = 2; /* axy > aw case */
2472 
2473  /* find row idx in row_idcs */
2474  exists = SCIPsortedvecFindInt(row_idcs, ridx, *nmarked, &pos);
2475 
2476  if( exists )
2477  {
2478  /* we found the row index: update the mark at pos */
2479  row_marks[pos] |= newmark;
2480  }
2481  else /* the given row index does not yet exist in row_idcs */
2482  {
2483  int i;
2484 
2485  /* insert row index at the correct position */
2486  for( i = *nmarked; i > pos; --i )
2487  {
2488  row_idcs[i] = row_idcs[i-1];
2489  row_marks[i] = row_marks[i-1];
2490  }
2491  row_idcs[pos] = ridx;
2492  row_marks[pos] = newmark;
2493  (*nmarked)++;
2494  }
2495 }
2496 
2497 /** mark all rows that should be multiplied by xj */
2498 static
2500  SCIP* scip, /**< SCIP data structure */
2501  SCIP_SEPADATA* sepadata, /**< separator data */
2502  SCIP_CONSHDLR* conshdlr, /**< nonlinear constraint handler */
2503  SCIP_SOL* sol, /**< point to be separated (can be NULL) */
2504  int j, /**< index of the multiplier variable in sepadata */
2505  SCIP_Bool local, /**< are local cuts allowed? */
2506  SCIP_HASHMAP* row_to_pos, /**< hashmap linking row indices to positions in array */
2507  int* bestunderest, /**< positions of most violated underestimators for each product term */
2508  int* bestoverest, /**< positions of most violated overestimators for each product term */
2509  unsigned int* row_marks, /**< sparse array storing the row marks */
2510  int* row_idcs, /**< sparse array storing the marked row positions */
2511  int* nmarked /**< number of marked rows */
2512  )
2513 {
2514  int i;
2515  int idx;
2516  int ncolrows;
2517  int r;
2518  int ridx;
2519  SCIP_VAR* xi;
2520  SCIP_VAR* xj;
2521  SCIP_Real vlb;
2522  SCIP_Real vub;
2523  SCIP_Real vali;
2524  SCIP_Real valj;
2525  SCIP_Real a;
2526  SCIP_COL* coli;
2527  SCIP_Real* colvals;
2528  SCIP_ROW** colrows;
2530  SCIP_Bool violatedbelow;
2531  SCIP_Bool violatedabove;
2532  SCIP_VAR** bilinadjvars;
2533  int nbilinadjvars;
2534 
2535  *nmarked = 0;
2536 
2537  xj = sepadata->varssorted[j];
2538  assert(xj != NULL);
2539 
2540  valj = SCIPgetSolVal(scip, sol, xj);
2541  vlb = local ? SCIPvarGetLbLocal(xj) : SCIPvarGetLbGlobal(xj);
2542  vub = local ? SCIPvarGetUbLocal(xj) : SCIPvarGetUbGlobal(xj);
2543 
2544  if( sepadata->useprojection && (SCIPisFeasEQ(scip, vlb, valj) || SCIPisFeasEQ(scip, vub, valj)) )
2545  {
2546  /* we don't want to multiply by variables that are at bound */
2547  SCIPdebugMsg(scip, "Rejected multiplier <%s> in [%g,%g] because it is at bound (current value %g)\n", SCIPvarGetName(xj), vlb, vub, valj);
2548  return SCIP_OKAY;
2549  }
2550 
2551  terms = SCIPgetBilinTermsNonlinear(conshdlr);
2552  bilinadjvars = getAdjacentVars(sepadata->bilinvardatamap, xj, &nbilinadjvars);
2553  assert(bilinadjvars != NULL);
2554 
2555  /* for each var which appears in a bilinear product together with xj, mark rows */
2556  for( i = 0; i < nbilinadjvars; ++i )
2557  {
2558  xi = bilinadjvars[i];
2559 
2561  continue;
2562 
2563  vali = SCIPgetSolVal(scip, sol, xi);
2564  vlb = local ? SCIPvarGetLbLocal(xi) : SCIPvarGetLbGlobal(xi);
2565  vub = local ? SCIPvarGetUbLocal(xi) : SCIPvarGetUbGlobal(xi);
2566 
2567  /* if we use projection, we aren't interested in products with variables that are at bound */
2568  if( sepadata->useprojection && (SCIPisFeasEQ(scip, vlb, vali) || SCIPisFeasEQ(scip, vub, vali)) )
2569  continue;
2570 
2571  /* get the index of the bilinear product */
2572  idx = SCIPgetBilinTermIdxNonlinear(conshdlr, xj, xi);
2573  assert(idx >= 0 && idx < SCIPgetNBilinTermsNonlinear(conshdlr));
2574 
2575  /* skip implicit products if we don't want to add RLT cuts for them */
2576  if( !sepadata->hiddenrlt && !terms[idx].existing )
2577  continue;
2578 
2579  /* use the most violated under- and overestimators for this product;
2580  * if equality cuts are computed, we might end up using a different auxiliary expression;
2581  * so this is an optimistic (i.e. taking the largest possible violation) estimation
2582  */
2583  if( bestunderest == NULL || bestunderest[idx] == -1 )
2584  { /* no violated implicit underestimation relations -> either use auxvar or set violatedbelow to FALSE */
2585  if( terms[idx].nauxexprs == 0 && terms[idx].aux.var != NULL )
2586  {
2587  assert(terms[idx].existing);
2588  violatedbelow = SCIPisFeasPositive(scip, SCIPgetSolVal(scip, sol, terms[idx].aux.var) - valj * vali);
2589  }
2590  else
2591  {
2592  assert(bestunderest != NULL);
2593  violatedbelow = FALSE;
2594  }
2595  }
2596  else
2597  {
2598  assert(bestunderest[idx] >= 0 && bestunderest[idx] < terms[idx].nauxexprs);
2599 
2600  /* if we are here, the relation with the best underestimator must be violated */
2601  assert(SCIPisFeasPositive(scip, SCIPevalBilinAuxExprNonlinear(scip, terms[idx].x, terms[idx].y,
2602  terms[idx].aux.exprs[bestunderest[idx]], sol) - valj * vali));
2603  violatedbelow = TRUE;
2604  }
2605 
2606  if( bestoverest == NULL || bestoverest[idx] == -1 )
2607  { /* no violated implicit overestimation relations -> either use auxvar or set violatedabove to FALSE */
2608  if( terms[idx].nauxexprs == 0 && terms[idx].aux.var != NULL )
2609  {
2610  assert(terms[idx].existing);
2611  violatedabove = SCIPisFeasPositive(scip, valj * vali - SCIPgetSolVal(scip, sol, terms[idx].aux.var));
2612  }
2613  else
2614  {
2615  assert(bestoverest != NULL);
2616  violatedabove = FALSE;
2617  }
2618  }
2619  else
2620  {
2621  assert(bestoverest[idx] >= 0 && bestoverest[idx] < terms[idx].nauxexprs);
2622 
2623  /* if we are here, the relation with the best overestimator must be violated */
2624  assert(SCIPisFeasPositive(scip, valj * vali - SCIPevalBilinAuxExprNonlinear(scip, terms[idx].x, terms[idx].y,
2625  terms[idx].aux.exprs[bestoverest[idx]], sol)));
2626  violatedabove = TRUE;
2627  }
2628 
2629  /* only violated products contribute to row marks */
2630  if( !violatedbelow && !violatedabove )
2631  {
2632  SCIPdebugMsg(scip, "the product for vars <%s> and <%s> is not violated\n", SCIPvarGetName(xj), SCIPvarGetName(xi));
2633  continue;
2634  }
2635 
2636  /* get the column of xi */
2637  coli = SCIPvarGetCol(xi);
2638  colvals = SCIPcolGetVals(coli);
2639  ncolrows = SCIPcolGetNNonz(coli);
2640  colrows = SCIPcolGetRows(coli);
2641 
2642  SCIPdebugMsg(scip, "marking rows for xj = <%s>, xi = <%s>\n", SCIPvarGetName(xj), SCIPvarGetName(xi));
2643 
2644  /* mark the rows */
2645  for( r = 0; r < ncolrows; ++r )
2646  {
2647  ridx = SCIProwGetIndex(colrows[r]);
2648 
2649  if( !SCIPhashmapExists(row_to_pos, (void*)(size_t)ridx) )
2650  continue; /* if row index is not in row_to_pos, it means that storeSuitableRows decided to ignore this row */
2651 
2652  a = colvals[r];
2653  if( a == 0.0 )
2654  continue;
2655 
2656  SCIPdebugMsg(scip, "Marking row %d\n", ridx);
2657  addRowMark(ridx, a, violatedbelow, violatedabove, row_idcs, row_marks, nmarked);
2658  }
2659  }
2660 
2661  return SCIP_OKAY;
2662 }
2663 
2664 /** adds McCormick inequalities for implicit products */
2665 static
2667  SCIP* scip, /**< SCIP data structure */
2668  SCIP_SEPA* sepa, /**< separator */
2669  SCIP_SEPADATA* sepadata, /**< separator data */
2670  SCIP_SOL* sol, /**< the point to be separated (can be NULL) */
2671  int* bestunderestimators,/**< indices of auxiliary underestimators with largest violation in sol */
2672  int* bestoverestimators, /**< indices of auxiliary overestimators with largest violation in sol */
2673  SCIP_RESULT* result /**< pointer to store the result */
2674  )
2675 {
2676  int i;
2677  int j;
2679  SCIP_ROW* cut;
2680  char name[SCIP_MAXSTRLEN];
2681  SCIP_Bool underestimate;
2682  SCIP_Real xcoef;
2683  SCIP_Real ycoef;
2684  SCIP_Real auxcoef;
2685  SCIP_Real constant;
2686  SCIP_Bool success;
2687  SCIP_CONSNONLINEAR_AUXEXPR* auxexpr;
2688  SCIP_Bool cutoff;
2689  SCIP_Real refpointx;
2690  SCIP_Real refpointy;
2691  SCIP_INTERVAL bndx;
2692  SCIP_INTERVAL bndy;
2693 #ifndef NDEBUG
2694  SCIP_Real productval;
2695  SCIP_Real auxval;
2696 #endif
2697 
2698  assert(sepadata->nbilinterms == SCIPgetNBilinTermsNonlinear(sepadata->conshdlr));
2699  assert(bestunderestimators != NULL && bestoverestimators != NULL);
2700 
2701  cutoff = FALSE;
2702  terms = SCIPgetBilinTermsNonlinear(sepadata->conshdlr);
2703 
2704  for( i = 0; i < sepadata->nbilinterms; ++i )
2705  {
2706  if( terms[i].existing )
2707  continue;
2708 
2709  assert(terms[i].nauxexprs > 0);
2710 
2711  bndx.inf = SCIPvarGetLbLocal(terms[i].x);
2712  bndx.sup = SCIPvarGetUbLocal(terms[i].x);
2713  bndy.inf = SCIPvarGetLbLocal(terms[i].y);
2714  bndy.sup = SCIPvarGetUbLocal(terms[i].y);
2715  refpointx = SCIPgetSolVal(scip, sol, terms[i].x);
2716  refpointy = SCIPgetSolVal(scip, sol, terms[i].y);
2717 
2718  /* adjust the reference points */
2719  refpointx = MIN(MAX(refpointx, bndx.inf), bndx.sup); /*lint !e666*/
2720  refpointy = MIN(MAX(refpointy, bndy.inf), bndy.sup); /*lint !e666*/
2721 
2722  /* one iteration for underestimation and one for overestimation */
2723  for( j = 0; j < 2; ++j )
2724  {
2725  /* if underestimate, separate xy <= auxexpr; if !underestimate, separate xy >= auxexpr;
2726  * the cuts will be:
2727  * if underestimate: McCormick_under(xy) - auxexpr <= 0,
2728  * if !underestimate: McCormick_over(xy) - auxexpr >= 0
2729  */
2730  underestimate = j == 0;
2731  if( underestimate && bestoverestimators[i] != -1 )
2732  auxexpr = terms[i].aux.exprs[bestoverestimators[i]];
2733  else if( !underestimate && bestunderestimators[i] != -1 )
2734  auxexpr = terms[i].aux.exprs[bestunderestimators[i]];
2735  else
2736  continue;
2737  assert(!underestimate || auxexpr->overestimate);
2738  assert(underestimate || auxexpr->underestimate);
2739 
2740 #ifndef NDEBUG
2741  /* make sure that the term is violated */
2742  productval = SCIPgetSolVal(scip, sol, terms[i].x) * SCIPgetSolVal(scip, sol, terms[i].y);
2743  auxval = SCIPevalBilinAuxExprNonlinear(scip, terms[i].x, terms[i].y, auxexpr, sol);
2744 
2745  /* if underestimate, then xy <= aux must be violated; otherwise aux <= xy must be violated */
2746  assert((underestimate && SCIPisFeasLT(scip, auxval, productval)) ||
2747  (!underestimate && SCIPisFeasLT(scip, productval, auxval)));
2748 #endif
2749 
2750  /* create an empty row */
2751  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "mccormick_%sestimate_implicit_%s*%s_%" SCIP_LONGINT_FORMAT,
2752  underestimate ? "under" : "over", SCIPvarGetName(terms[i].x), SCIPvarGetName(terms[i].y),
2753  SCIPgetNLPs(scip));
2754 
2755  SCIP_CALL(SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), SCIPinfinity(scip), TRUE,
2756  FALSE, FALSE) );
2757 
2758  xcoef = 0.0;
2759  ycoef = 0.0;
2760  auxcoef = 0.0;
2761  constant = 0.0;
2762  success = TRUE;
2763 
2764  /* subtract auxexpr from the cut */
2765  addAuxexprCoefs(terms[i].x, terms[i].y, auxexpr, -1.0, &auxcoef, &xcoef, &ycoef, &constant);
2766 
2767  /* add McCormick terms: ask for an underestimator if relation is xy <= auxexpr, and vice versa */
2768  SCIPaddBilinMcCormick(scip, 1.0, bndx.inf, bndx.sup, refpointx, bndy.inf, bndy.sup, refpointy, !underestimate,
2769  &xcoef, &ycoef, &constant, &success);
2770 
2771  if( REALABS(constant) > MAXVARBOUND )
2772  success = FALSE;
2773 
2774  if( success )
2775  {
2776  assert(!SCIPisInfinity(scip, REALABS(xcoef)));
2777  assert(!SCIPisInfinity(scip, REALABS(ycoef)));
2778  assert(!SCIPisInfinity(scip, REALABS(constant)));
2779 
2780  SCIP_CALL( SCIPaddVarToRow(scip, cut, terms[i].x, xcoef) );
2781  SCIP_CALL( SCIPaddVarToRow(scip, cut, terms[i].y, ycoef) );
2782  SCIP_CALL( SCIPaddVarToRow(scip, cut, auxexpr->auxvar, auxcoef) );
2783 
2784  /* set side */
2785  if( underestimate )
2786  SCIP_CALL( SCIPchgRowRhs(scip, cut, -constant) );
2787  else
2788  SCIP_CALL( SCIPchgRowLhs(scip, cut, -constant) );
2789 
2790  /* if the cut is violated, add it to SCIP */
2791  if( SCIPisFeasNegative(scip, SCIPgetRowFeasibility(scip, cut)) )
2792  {
2793  SCIP_CALL( SCIPaddRow(scip, cut, FALSE, &cutoff) );
2794  *result = SCIP_SEPARATED;
2795  }
2796  else
2797  {
2798  SCIPdebugMsg(scip, "\nMcCormick cut for hidden product <%s>*<%s> was created successfully, but is not violated",
2799  SCIPvarGetName(terms[i].x), SCIPvarGetName(terms[i].y));
2800  }
2801  }
2802 
2803  /* release the cut */
2804  if( cut != NULL )
2805  {
2806  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
2807  }
2808 
2809  if( cutoff )
2810  {
2811  *result = SCIP_CUTOFF;
2812  SCIPdebugMsg(scip, "exit separator because we found a cutoff -> skip\n");
2813  return SCIP_OKAY;
2814  }
2815  }
2816  }
2817 
2818  return SCIP_OKAY;
2819 }
2820 
2821 /** builds and adds the RLT cuts */
2822 static
2824  SCIP* scip, /**< SCIP data structure */
2825  SCIP_SEPA* sepa, /**< separator */
2826  SCIP_SEPADATA* sepadata, /**< separator data */
2827  SCIP_CONSHDLR* conshdlr, /**< nonlinear constraint handler */
2828  SCIP_SOL* sol, /**< the point to be separated (can be NULL) */
2829  SCIP_HASHMAP* row_to_pos, /**< hashmap linking row indices to positions in array */
2830  RLT_SIMPLEROW* projrows, /**< projected rows */
2831  SCIP_ROW** rows, /**< problem rows */
2832  int nrows, /**< number of problem rows */
2833  SCIP_Bool allowlocal, /**< are local cuts allowed? */
2834  int* bestunderestimators,/**< indices of auxiliary underestimators with largest violation in sol */
2835  int* bestoverestimators, /**< indices of auxiliary overestimators with largest violation in sol */
2836  SCIP_RESULT* result /**< buffer to store whether separation was successful */
2837  )
2838 {
2839  int j;
2840  int r;
2841  int k;
2842  int nmarked;
2843  int cutssize;
2844  int ncuts;
2845  SCIP_VAR* xj;
2846  unsigned int* row_marks;
2847  int* row_idcs;
2848  SCIP_ROW* cut;
2849  SCIP_ROW** cuts;
2850  SCIP_Bool uselb[4] = {TRUE, TRUE, FALSE, FALSE};
2851  SCIP_Bool uselhs[4] = {TRUE, FALSE, TRUE, FALSE};
2852  SCIP_Bool success;
2853  SCIP_Bool infeasible;
2854  SCIP_Bool accepted;
2855  SCIP_Bool buildeqcut;
2856  SCIP_Bool iseqrow;
2857 
2858  assert(!sepadata->useprojection || projrows != NULL);
2859  assert(!sepadata->detecthidden || (bestunderestimators != NULL && bestoverestimators != NULL));
2860 
2861  ncuts = 0;
2862  cutssize = 0;
2863  cuts = NULL;
2864  *result = SCIP_DIDNOTFIND;
2865 
2866  SCIP_CALL( SCIPallocCleanBufferArray(scip, &row_marks, nrows) );
2867  SCIP_CALL( SCIPallocBufferArray(scip, &row_idcs, nrows) );
2868 
2869  /* loop through all variables that appear in bilinear products */
2870  for( j = 0; j < sepadata->nbilinvars && (sepadata->maxusedvars < 0 || j < sepadata->maxusedvars); ++j )
2871  {
2872  xj = sepadata->varssorted[j];
2873 
2874  /* mark all rows for multiplier xj */
2875  SCIP_CALL( markRowsXj(scip, sepadata, conshdlr, sol, j, allowlocal, row_to_pos, bestunderestimators,
2876  bestoverestimators, row_marks, row_idcs, &nmarked) );
2877 
2878  assert(nmarked <= nrows);
2879 
2880  /* generate the projected cut and if it is violated, generate the actual cut */
2881  for( r = 0; r < nmarked; ++r )
2882  {
2883  int pos;
2884  int currentnunknown;
2885  SCIP_ROW* row;
2886 
2887  assert(row_marks[r] != 0);
2888  assert(SCIPhashmapExists(row_to_pos, (void*)(size_t) row_idcs[r])); /*lint !e571 */
2889 
2890  pos = SCIPhashmapGetImageInt(row_to_pos, (void*)(size_t) row_idcs[r]); /*lint !e571 */
2891  row = rows[pos];
2892  assert(SCIProwGetIndex(row) == row_idcs[r]);
2893 
2894  /* check whether this row and var fulfill the conditions */
2895  SCIP_CALL( isAcceptableRow(sepadata, row, xj, &currentnunknown, &accepted) );
2896  if( !accepted )
2897  {
2898  SCIPdebugMsg(scip, "rejected row <%s> for variable <%s> (introduces too many new products)\n", SCIProwGetName(row), SCIPvarGetName(xj));
2899  row_marks[r] = 0;
2900  continue;
2901  }
2902 
2903  SCIPdebugMsg(scip, "accepted row <%s> for variable <%s>\n", SCIProwGetName(rows[r]), SCIPvarGetName(xj));
2904 #ifdef SCIP_DEBUG
2905  SCIP_CALL( SCIPprintRow(scip, rows[r], NULL) );
2906 #endif
2907  iseqrow = SCIPisEQ(scip, SCIProwGetLhs(row), SCIProwGetRhs(row));
2908 
2909  /* 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)
2910  * 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
2911  */
2912  buildeqcut = (currentnunknown == 0 && iseqrow);
2913 
2914  /* go over all suitable combinations of sides and bounds and compute the respective cuts */
2915  for( k = 0; k < 4; ++k )
2916  {
2917  /* if equality cuts are possible, lhs and rhs cuts are equal so skip rhs */
2918  if( buildeqcut )
2919  {
2920  if( k != 1 )
2921  continue;
2922  }
2923  /* otherwise which cuts are generated depends on the marks */
2924  else
2925  {
2926  if( row_marks[r] == 1 && uselb[k] == uselhs[k] )
2927  continue;
2928 
2929  if( row_marks[r] == 2 && uselb[k] != uselhs[k] )
2930  continue;
2931  }
2932 
2933  success = TRUE;
2934  cut = NULL;
2935 
2936  SCIPdebugMsg(scip, "row <%s>, uselb = %u, uselhs = %u\n", SCIProwGetName(row), uselb[k], uselhs[k]);
2937 
2938  if( sepadata->useprojection )
2939  {
2940  /* if no variables are left in the projected row, the RLT cut will not be violated */
2941  if( projrows[pos].nnonz == 0 )
2942  continue;
2943 
2944  /* compute the rlt cut for a projected row first */
2945  SCIP_CALL( computeRltCut(scip, sepa, sepadata, &cut, NULL, &(projrows[pos]), sol, bestunderestimators,
2946  bestoverestimators, xj, &success, uselb[k], uselhs[k], allowlocal, buildeqcut, TRUE) );
2947 
2948  /* if the projected cut is not violated, set success to FALSE */
2949  if( cut != NULL )
2950  {
2951  SCIPdebugMsg(scip, "proj cut viol = %g\n", -SCIPgetRowFeasibility(scip, cut));
2952  }
2953  if( cut != NULL && !SCIPisFeasPositive(scip, -SCIPgetRowFeasibility(scip, cut)) )
2954  {
2955  SCIPdebugMsg(scip, "projected cut is not violated, feasibility = %g\n", SCIPgetRowFeasibility(scip, cut));
2956  success = FALSE;
2957  }
2958 
2959  /* release the projected cut */
2960  if( cut != NULL )
2961  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
2962  }
2963 
2964  /* if we don't use projection or if the projected cut was generated successfully and is violated,
2965  * generate the actual cut */
2966  if( success )
2967  {
2968  SCIP_CALL( computeRltCut(scip, sepa, sepadata, &cut, row, NULL, sol, bestunderestimators,
2969  bestoverestimators, xj, &success, uselb[k], uselhs[k], allowlocal, buildeqcut, FALSE) );
2970  }
2971 
2972  if( success )
2973  {
2974  success = SCIPisFeasNegative(scip, SCIPgetRowFeasibility(scip, cut)) || (sepadata->addtopool &&
2975  !SCIProwIsLocal(cut));
2976  }
2977 
2978  /* if the cut was created successfully and is violated or (if addtopool == TRUE) globally valid,
2979  * it is added to the cuts array */
2980  if( success )
2981  {
2982  if( ncuts + 1 > cutssize )
2983  {
2984  int newsize;
2985 
2986  newsize = SCIPcalcMemGrowSize(scip, ncuts + 1);
2987  SCIP_CALL( SCIPreallocBufferArray(scip, &cuts, newsize) );
2988  cutssize = newsize;
2989  }
2990  cuts[ncuts] = cut;
2991  (ncuts)++;
2992  }
2993  else
2994  {
2995  SCIPdebugMsg(scip, "the generation of the cut failed or cut not violated and not added to cutpool\n");
2996  /* release the cut */
2997  if( cut != NULL )
2998  {
2999  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3000  }
3001  }
3002  }
3003 
3004  /* clear row_marks[r] since it will be used for the next multiplier */
3005  row_marks[r] = 0;
3006  }
3007  }
3008 
3009  /* if cuts were found, we apply an additional filtering procedure, which is similar to sepastore */
3010  if( ncuts > 0 )
3011  {
3012  int nselectedcuts;
3013  int i;
3014 
3015  assert(cuts != NULL);
3016 
3017  SCIP_CALL( SCIPselectCutsHybrid(scip, cuts, NULL, NULL, sepadata->goodscore, sepadata->badscore, sepadata->goodmaxparall,
3018  sepadata->maxparall, sepadata->dircutoffdistweight, sepadata->efficacyweight, sepadata->objparalweight,
3019  0.0, ncuts, 0, sepadata->maxncuts == -1 ? ncuts : sepadata->maxncuts, &nselectedcuts) );
3020 
3021  for( i = 0; i < ncuts; ++i )
3022  {
3023  assert(cuts[i] != NULL);
3024 
3025  if( i < nselectedcuts )
3026  {
3027  /* if selected, add global cuts to the pool and local cuts to the sepastore */
3028  if( SCIProwIsLocal(cuts[i]) || !sepadata->addtopool )
3029  {
3030  SCIP_CALL( SCIPaddRow(scip, cuts[i], FALSE, &infeasible) );
3031 
3032  if( infeasible )
3033  {
3034  SCIPdebugMsg(scip, "CUTOFF! The cut <%s> revealed infeasibility\n", SCIProwGetName(cuts[i]));
3035  *result = SCIP_CUTOFF;
3036  }
3037  else
3038  {
3039  SCIPdebugMsg(scip, "SEPARATED: added cut to scip\n");
3040  *result = SCIP_SEPARATED;
3041  }
3042  }
3043  else
3044  {
3045  SCIP_CALL( SCIPaddPoolCut(scip, cuts[i]) );
3046  }
3047  }
3048 
3049  /* release current cut */
3050  SCIP_CALL( SCIPreleaseRow(scip, &cuts[i]) );
3051  }
3052  }
3053 
3054  SCIPdebugMsg(scip, "exit separator because cut calculation is finished\n");
3055 
3056  SCIPfreeBufferArrayNull(scip, &cuts);
3057  SCIPfreeBufferArray(scip, &row_idcs);
3058  SCIPfreeCleanBufferArray(scip, &row_marks);
3059 
3060  return SCIP_OKAY;
3061 }
3062 
3063 /*
3064  * Callback methods of separator
3065  */
3066 
3067 /** copy method for separator plugins (called when SCIP copies plugins) */
3068 static
3069 SCIP_DECL_SEPACOPY(sepaCopyRlt)
3070 { /*lint --e{715}*/
3071  assert(scip != NULL);
3072  assert(sepa != NULL);
3073  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
3074 
3075  /* call inclusion method of separator */
3076  SCIP_CALL( SCIPincludeSepaRlt(scip) );
3077 
3078  return SCIP_OKAY;
3079 }
3080 
3081 /** destructor of separator to free user data (called when SCIP is exiting) */
3082 static
3083 SCIP_DECL_SEPAFREE(sepaFreeRlt)
3084 { /*lint --e{715}*/
3085  SCIP_SEPADATA* sepadata;
3086 
3087  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
3088 
3089  sepadata = SCIPsepaGetData(sepa);
3090  assert(sepadata != NULL);
3091 
3092  /* free separator data */
3093  SCIPfreeBlockMemory(scip, &sepadata);
3094 
3095  SCIPsepaSetData(sepa, NULL);
3096 
3097  return SCIP_OKAY;
3098 }
3099 
3100 /** solving process deinitialization method of separator (called before branch and bound process data is freed) */
3101 static
3102 SCIP_DECL_SEPAEXITSOL(sepaExitsolRlt)
3103 { /*lint --e{715}*/
3104  SCIP_SEPADATA* sepadata;
3105 
3106  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
3107 
3108  sepadata = SCIPsepaGetData(sepa);
3109  assert(sepadata != NULL);
3110 
3111  if( sepadata->iscreated )
3112  {
3113  SCIP_CALL( freeSepaData(scip, sepadata) );
3114  }
3115 
3116  return SCIP_OKAY;
3117 }
3118 
3119 /** LP solution separation method of separator */
3120 static
3121 SCIP_DECL_SEPAEXECLP(sepaExeclpRlt)
3122 { /*lint --e{715}*/
3123  SCIP_ROW** prob_rows;
3124  SCIP_ROW** rows;
3125  SCIP_SEPADATA* sepadata;
3126  int ncalls;
3127  int nrows;
3128  SCIP_HASHMAP* row_to_pos;
3129  RLT_SIMPLEROW* projrows;
3130 
3131  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
3132 
3133  sepadata = SCIPsepaGetData(sepa);
3134  *result = SCIP_DIDNOTRUN;
3135 
3136  if( sepadata->maxncuts == 0 )
3137  {
3138  SCIPdebugMsg(scip, "exit separator because maxncuts is set to 0\n");
3139  return SCIP_OKAY;
3140  }
3141 
3142  /* don't run in a sub-SCIP or in probing */
3143  if( SCIPgetSubscipDepth(scip) > 0 && !sepadata->useinsubscip )
3144  {
3145  SCIPdebugMsg(scip, "exit separator because in sub-SCIP\n");
3146  return SCIP_OKAY;
3147  }
3148 
3149  /* don't run in probing */
3150  if( SCIPinProbing(scip) )
3151  {
3152  SCIPdebugMsg(scip, "exit separator because in probing\n");
3153  return SCIP_OKAY;
3154  }
3155 
3156  /* only call separator a given number of times at each node */
3157  ncalls = SCIPsepaGetNCallsAtNode(sepa);
3158  if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
3159  || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
3160  {
3161  SCIPdebugMsg(scip, "exit separator because round limit for this node is reached\n");
3162  return SCIP_OKAY;
3163  }
3164 
3165  /* if this is called for the first time, create the sepadata and start the initial separation round */
3166  if( !sepadata->iscreated )
3167  {
3168  *result = SCIP_DIDNOTFIND;
3169  SCIP_CALL( createSepaData(scip, sepadata) );
3170  }
3171  assert(sepadata->iscreated || (sepadata->nbilinvars == 0 && sepadata->nbilinterms == 0));
3172  assert(sepadata->nbilinterms == SCIPgetNBilinTermsNonlinear(sepadata->conshdlr));
3173 
3174  /* no bilinear terms available -> skip */
3175  if( sepadata->nbilinvars == 0 )
3176  {
3177  SCIPdebugMsg(scip, "exit separator because there are no known bilinear terms\n");
3178  return SCIP_OKAY;
3179  }
3180 
3181  /* only call separator, if we are not close to terminating */
3182  if( SCIPisStopped(scip) )
3183  {
3184  SCIPdebugMsg(scip, "exit separator because we are too close to terminating\n");
3185  return SCIP_OKAY;
3186  }
3187 
3188  /* only call separator, if an optimal LP solution is at hand */
3190  {
3191  SCIPdebugMsg(scip, "exit separator because there is no LP solution at hand\n");
3192  return SCIP_OKAY;
3193  }
3194 
3195  /* get the rows, depending on settings */
3196  if( sepadata->isinitialround || sepadata->onlyoriginal )
3197  {
3198  SCIP_CALL( getOriginalRows(scip, &prob_rows, &nrows) );
3199  }
3200  else
3201  {
3202  SCIP_CALL( SCIPgetLPRowsData(scip, &prob_rows, &nrows) );
3203  }
3204 
3205  /* save the suitable rows */
3206  SCIP_CALL( SCIPallocBufferArray(scip, &rows, nrows) );
3207  SCIP_CALL( SCIPhashmapCreate(&row_to_pos, SCIPblkmem(scip), nrows) );
3208 
3209  SCIP_CALL( storeSuitableRows(scip, sepa, sepadata, prob_rows, rows, &nrows, row_to_pos, allowlocal) );
3210 
3211  if( nrows == 0 ) /* no suitable rows found, free memory and exit */
3212  {
3213  SCIPhashmapFree(&row_to_pos);
3214  SCIPfreeBufferArray(scip, &rows);
3215  if( sepadata->isinitialround || sepadata->onlyoriginal )
3216  {
3217  SCIPfreeBufferArray(scip, &prob_rows);
3218  sepadata->isinitialround = FALSE;
3219  }
3220  return SCIP_OKAY;
3221  }
3222 
3223  /* create the projected problem */
3224  if( sepadata->useprojection )
3225  {
3226  SCIP_Bool allcst;
3227 
3228  SCIP_CALL( createProjRows(scip, rows, nrows, NULL, &projrows, allowlocal, &allcst) );
3229 
3230  /* if all projected rows have only constants left, quit */
3231  if( allcst )
3232  goto TERMINATE;
3233 
3234 #ifdef SCIP_DEBUG
3235  printProjRows(scip, projrows, nrows, NULL);
3236 #endif
3237  }
3238  else
3239  {
3240  projrows = NULL;
3241  }
3242 
3243  /* separate the cuts */
3244  if( sepadata->detecthidden )
3245  {
3246  int* bestunderestimators;
3247  int* bestoverestimators;
3248 
3249  /* if we detect implicit products, a term might have more than one estimator in each direction;
3250  * save the indices of the most violated estimators
3251  */
3252  SCIP_CALL( SCIPallocBufferArray(scip, &bestunderestimators, sepadata->nbilinterms) );
3253  SCIP_CALL( SCIPallocBufferArray(scip, &bestoverestimators, sepadata->nbilinterms) );
3254  getBestEstimators(scip, sepadata, NULL, bestunderestimators, bestoverestimators);
3255 
3256  /* also separate McCormick cuts for implicit products */
3257  SCIP_CALL( separateMcCormickImplicit(scip, sepa, sepadata, NULL, bestunderestimators, bestoverestimators,
3258  result) );
3259 
3260  if( *result != SCIP_CUTOFF )
3261  {
3262  SCIP_CALL( separateRltCuts(scip, sepa, sepadata, sepadata->conshdlr, NULL, row_to_pos, projrows, rows, nrows,
3263  allowlocal, bestunderestimators, bestoverestimators, result) );
3264  }
3265 
3266  SCIPfreeBufferArray(scip, &bestoverestimators);
3267  SCIPfreeBufferArray(scip, &bestunderestimators);
3268  }
3269  else
3270  {
3271  SCIP_CALL( separateRltCuts(scip, sepa, sepadata, sepadata->conshdlr, NULL, row_to_pos, projrows, rows, nrows,
3272  allowlocal, NULL, NULL, result) );
3273  }
3274 
3275  TERMINATE:
3276  /* free the projected problem */
3277  if( sepadata->useprojection )
3278  {
3279  freeProjRows(scip, &projrows, nrows);
3280  }
3281 
3282  SCIPhashmapFree(&row_to_pos);
3283  SCIPfreeBufferArray(scip, &rows);
3284 
3285  if( sepadata->isinitialround || sepadata->onlyoriginal )
3286  {
3287  SCIPfreeBufferArray(scip, &prob_rows);
3288  sepadata->isinitialround = FALSE;
3289  }
3290 
3291  return SCIP_OKAY;
3292 }
3293 
3294 /*
3295  * separator specific interface methods
3296  */
3297 
3298 /** creates the RLT separator and includes it in SCIP */
3300  SCIP* scip /**< SCIP data structure */
3301  )
3302 {
3303  SCIP_SEPADATA* sepadata;
3304  SCIP_SEPA* sepa;
3305 
3306  /* create RLT separator data */
3307  SCIP_CALL( SCIPallocClearBlockMemory(scip, &sepadata) );
3308  sepadata->conshdlr = SCIPfindConshdlr(scip, "nonlinear");
3309  assert(sepadata->conshdlr != NULL);
3310 
3311  /* include separator */
3313  SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpRlt, NULL, sepadata) );
3314 
3315  /* set non fundamental callbacks via setter functions */
3316  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyRlt) );
3317  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeRlt) );
3318  SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolRlt) );
3319 
3320  /* add RLT separator parameters */
3321  SCIP_CALL( SCIPaddIntParam(scip,
3322  "separating/" SEPA_NAME "/maxncuts",
3323  "maximal number of rlt-cuts that are added per round (-1: unlimited)",
3324  &sepadata->maxncuts, FALSE, DEFAULT_MAXNCUTS, -1, INT_MAX, NULL, NULL) );
3325 
3326  SCIP_CALL( SCIPaddIntParam(scip,
3327  "separating/" SEPA_NAME "/maxunknownterms",
3328  "maximal number of unknown bilinear terms a row is still used with (-1: unlimited)",
3329  &sepadata->maxunknownterms, FALSE, DEFAULT_MAXUNKNOWNTERMS, -1, INT_MAX, NULL, NULL) );
3330 
3331  SCIP_CALL( SCIPaddIntParam(scip,
3332  "separating/" SEPA_NAME "/maxusedvars",
3333  "maximal number of variables used to compute rlt cuts (-1: unlimited)",
3334  &sepadata->maxusedvars, FALSE, DEFAULT_MAXUSEDVARS, -1, INT_MAX, NULL, NULL) );
3335 
3336  SCIP_CALL( SCIPaddIntParam(scip,
3337  "separating/" SEPA_NAME "/maxrounds",
3338  "maximal number of separation rounds per node (-1: unlimited)",
3339  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
3340 
3341  SCIP_CALL( SCIPaddIntParam(scip,
3342  "separating/" SEPA_NAME "/maxroundsroot",
3343  "maximal number of separation rounds in the root node (-1: unlimited)",
3344  &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
3345 
3347  "separating/" SEPA_NAME "/onlyeqrows",
3348  "if set to true, only equality rows are used for rlt cuts",
3349  &sepadata->onlyeqrows, FALSE, DEFAULT_ONLYEQROWS, NULL, NULL) );
3350 
3352  "separating/" SEPA_NAME "/onlycontrows",
3353  "if set to true, only continuous rows are used for rlt cuts",
3354  &sepadata->onlycontrows, FALSE, DEFAULT_ONLYCONTROWS, NULL, NULL) );
3355 
3357  "separating/" SEPA_NAME "/onlyoriginal",
3358  "if set to true, only original rows and variables are used",
3359  &sepadata->onlyoriginal, FALSE, DEFAULT_ONLYORIGINAL, NULL, NULL) );
3360 
3362  "separating/" SEPA_NAME "/useinsubscip",
3363  "if set to true, rlt is also used in sub-scips",
3364  &sepadata->useinsubscip, FALSE, DEFAULT_USEINSUBSCIP, NULL, NULL) );
3365 
3367  "separating/" SEPA_NAME "/useprojection",
3368  "if set to true, projected rows are checked first",
3369  &sepadata->useprojection, FALSE, DEFAULT_USEPROJECTION, NULL, NULL) );
3370 
3372  "separating/" SEPA_NAME "/detecthidden",
3373  "if set to true, hidden products are detected and separated by McCormick cuts",
3374  &sepadata->detecthidden, FALSE, DEFAULT_DETECTHIDDEN, NULL, NULL) );
3375 
3377  "separating/" SEPA_NAME "/hiddenrlt",
3378  "whether RLT cuts (TRUE) or only McCormick inequalities (FALSE) should be added for hidden products",
3379  &sepadata->hiddenrlt, FALSE, DEFAULT_HIDDENRLT, NULL, NULL) );
3380 
3382  "separating/" SEPA_NAME "/addtopool",
3383  "if set to true, globally valid RLT cuts are added to the global cut pool",
3384  &sepadata->addtopool, FALSE, DEFAULT_ADDTOPOOL, NULL, NULL) );
3385 
3387  "separating/" SEPA_NAME "/goodscore",
3388  "threshold for score of cut relative to best score to be considered good, so that less strict filtering is applied",
3389  &sepadata->goodscore, TRUE, DEFAULT_GOODSCORE, 0.0, 1.0, NULL, NULL) );
3390 
3392  "separating/" SEPA_NAME "/badscore",
3393  "threshold for score of cut relative to best score to be discarded",
3394  &sepadata->badscore, TRUE, DEFAULT_BADSCORE, 0.0, 1.0, NULL, NULL) );
3395 
3397  "separating/" SEPA_NAME "/objparalweight",
3398  "weight of objective parallelism in cut score calculation",
3399  &sepadata->objparalweight, TRUE, DEFAULT_OBJPARALWEIGHT, 0.0, 1.0, NULL, NULL) );
3400 
3402  "separating/" SEPA_NAME "/efficacyweight",
3403  "weight of efficacy in cut score calculation",
3404  &sepadata->efficacyweight, TRUE, DEFAULT_EFFICACYWEIGHT, 0.0, 1.0, NULL, NULL) );
3405 
3407  "separating/" SEPA_NAME "/dircutoffdistweight",
3408  "weight of directed cutoff distance in cut score calculation",
3409  &sepadata->dircutoffdistweight, TRUE, DEFAULT_DIRCUTOFFDISTWEIGHT, 0.0, 1.0, NULL, NULL) );
3410 
3412  "separating/" SEPA_NAME "/goodmaxparall",
3413  "maximum parallelism for good cuts",
3414  &sepadata->goodmaxparall, TRUE, DEFAULT_GOODMAXPARALL, 0.0, 1.0, NULL, NULL) );
3415 
3417  "separating/" SEPA_NAME "/maxparall",
3418  "maximum parallelism for non-good cuts",
3419  &sepadata->maxparall, TRUE, DEFAULT_MAXPARALL, 0.0, 1.0, NULL, NULL) );
3420 
3421  return SCIP_OKAY;
3422 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3570
#define DEFAULT_GOODMAXPARALL
Definition: sepa_rlt.c:82
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:18293
#define NULL
Definition: def.h:267
#define DEFAULT_MAXUNKNOWNTERMS
Definition: sepa_rlt.c:61
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:11476
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
static SCIP_RETCODE extractProducts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_VAR **vars_xwy, SCIP_Real *coefs1, SCIP_Real *coefs2, SCIP_Real d1, SCIP_Real d2, SCIP_SIDETYPE sidetype1, SCIP_SIDETYPE sidetype2, SCIP_HASHMAP *varmap, SCIP_Bool f)
Definition: sepa_rlt.c:666
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_SEPAEXITSOL(sepaExitsolRlt)
Definition: sepa_rlt.c:3104
void * SCIPhashtableGetEntry(SCIP_HASHTABLE *hashtable, int entryidx)
Definition: misc.c:2785
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_SEPA * SCIProwGetOriginSepa(SCIP_ROW *row)
Definition: lp.c:17476
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3357
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2547
#define DEFAULT_HIDDENRLT
Definition: sepa_rlt.c:72
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
static SCIP_RETCODE addRltTerm(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, int *bestunderest, int *bestoverest, SCIP_ROW *cut, SCIP_VAR *var, SCIP_VAR *colvar, SCIP_Real coef, SCIP_Bool uselb, SCIP_Bool uselhs, SCIP_Bool local, SCIP_Bool computeEqCut, SCIP_Real *coefvar, SCIP_Real *cst, SCIP_Bool *success)
Definition: sepa_rlt.c:1875
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:18271
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18079
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define DEFAULT_USEINSUBSCIP
Definition: sepa_rlt.c:69
#define DEFAULT_DIRCUTOFFDISTWEIGHT
Definition: sepa_rlt.c:81
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17161
static SCIP_VAR ** getAdjacentVars(SCIP_HASHMAP *adjvarmap, SCIP_VAR *var, int *nadjacentvars)
Definition: sepa_rlt.c:317
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17213
hybrid cut selector
static void freeProjRow(SCIP *scip, RLT_SIMPLEROW *simplerow)
Definition: sepa_rlt.c:2324
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18442
static void freeProjRows(SCIP *scip, RLT_SIMPLEROW **projrows, int nrows)
Definition: sepa_rlt.c:2432
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17351
SCIP_ROW * SCIPconsGetRow(SCIP *scip, SCIP_CONS *cons)
Definition: misc_linear.c:412
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1250
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
#define DEFAULT_MAXUSEDVARS
Definition: sepa_rlt.c:62
SCIP_Bool SCIPcliqueHasVar(SCIP_CLIQUE *clique, SCIP_VAR *var, SCIP_Bool value)
Definition: implics.c:1141
SCIP_VAR ** vars
Definition: sepa_rlt.c:162
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
#define FALSE
Definition: def.h:94
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
#define DEFAULT_BADSCORE
Definition: sepa_rlt.c:78
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:17072
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2605
#define DEFAULT_EFFICACYWEIGHT
Definition: sepa_rlt.c:80
int SCIPgetNBilinTermsNonlinear(SCIP_CONSHDLR *conshdlr)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
#define TRUE
Definition: def.h:93
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:743
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
#define SCIPstatisticMessage
Definition: pub_message.h:123
static SCIP_RETCODE addAdjacentVars(SCIP *scip, SCIP_HASHMAP *adjvarmap, SCIP_VAR **vars)
Definition: sepa_rlt.c:243
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:18313
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
#define SEPA_USESSUBSCIP
Definition: sepa_rlt.c:58
int SCIPgetBilinTermIdxNonlinear(SCIP_CONSHDLR *conshdlr, SCIP_VAR *x, SCIP_VAR *y)
#define DEFAULT_OBJPARALWEIGHT
Definition: sepa_rlt.c:79
SCIP_VAR ** vars
static SCIP_DECL_HASHKEYEQ(hashdataKeyEqConss)
Definition: sepa_rlt.c:180
static SCIP_RETCODE detectProductsImplbnd(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real *coefs1, SCIP_VAR **vars_xwy, SCIP_Real side1, SCIP_SIDETYPE sidetype1, int binvarpos, int implvarpos, SCIP_HASHMAP *varmap, SCIP_Bool f)
Definition: sepa_rlt.c:861
void SCIPswapReals(SCIP_Real *value1, SCIP_Real *value2)
Definition: misc.c:10383
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SEPA_MAXBOUNDDIST
Definition: sepa_rlt.c:55
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:18283
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3088
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_ADDTOPOOL
Definition: sepa_rlt.c:73
void SCIPselectDownIntPtr(int *intarray, void **ptrarray, int k, int len)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
int firstrow
Definition: sepa_rlt.c:97
SCIP_VAR ** x
Definition: circlepacking.c:63
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18431
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIP_Real SCIPgetRowFeasibility(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:2124
bilinear nonlinear handler
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:633
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2296
SCIP_Real lhs
Definition: sepa_rlt.c:164
#define MIN3(x, y, z)
Definition: def.h:251
#define DEFAULT_ONLYORIGINAL
Definition: sepa_rlt.c:68
#define SEPA_DESC
Definition: sepa_rlt.c:52
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_VAR ** adjacentvars
Definition: sepa_rlt.c:106
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
static SCIP_RETCODE computeRltCut(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_ROW **cut, SCIP_ROW *row, RLT_SIMPLEROW *projrow, SCIP_SOL *sol, int *bestunderest, int *bestoverest, SCIP_VAR *var, SCIP_Bool *success, SCIP_Bool uselb, SCIP_Bool uselhs, SCIP_Bool local, SCIP_Bool computeEqCut, SCIP_Bool useprojrow)
Definition: sepa_rlt.c:2115
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18089
SCIP_VAR * w
Definition: circlepacking.c:67
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_Real inf
Definition: intervalarith.h:55
#define SCIPhashFour(a, b, c, d)
Definition: pub_misc.h:556
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition: misc.c:3541
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3549
#define SEPA_NAME
Definition: sepa_rlt.c:51
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17151
#define SCIPallocBuffer(scip, ptr)
Definition: scip_mem.h:122
static SCIP_RETCODE addProductVars(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_VAR *x, SCIP_VAR *y, SCIP_HASHMAP *varmap, int nlocks)
Definition: sepa_rlt.c:550
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17401
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:880
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
#define MAX3(x, y, z)
Definition: def.h:247
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:18345
static SCIP_DECL_SEPAEXECLP(sepaExeclpRlt)
Definition: sepa_rlt.c:3123
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:643
static SCIP_RETCODE detectProductsUnconditional(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW **rows, int *row_list, SCIP_HASHTABLE *hashtable, SCIP_Real *coefs1, SCIP_VAR **vars_xwy, SCIP_Real side1, SCIP_SIDETYPE sidetype1, int varpos1, int varpos2, SCIP_HASHMAP *varmap, SCIP_Bool f)
Definition: sepa_rlt.c:1000
power and signed power expression handlers
#define REALABS(x)
Definition: def.h:197
static SCIP_RETCODE storeSuitableRows(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_ROW **prob_rows, SCIP_ROW **rows, int *nrows, SCIP_HASHMAP *row_to_pos, SCIP_Bool allowlocal)
Definition: sepa_rlt.c:451
static void addRowMark(int ridx, SCIP_Real a, SCIP_Bool violatedbelow, SCIP_Bool violatedabove, int *row_idcs, unsigned int *row_marks, int *nmarked)
Definition: sepa_rlt.c:2454
#define SCIP_CALL(x)
Definition: def.h:380
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
Definition: scip_mem.h:107
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:18303
SCIP_Real sup
Definition: intervalarith.h:56
SCIP_Bool SCIPvarIsRelaxationOnly(SCIP_VAR *var)
Definition: var.c:17707
static SCIP_DECL_HASHKEYVAL(hashdataKeyValConss)
Definition: sepa_rlt.c:212
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:18335
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
SCIP_Real rhs
Definition: sepa_rlt.c:163
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17238
union SCIP_ConsNonlinear_BilinTerm::@4 aux
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip_sepa.c:109
static void getBestEstimators(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, int *bestunderestimators, int *bestoverestimators)
Definition: sepa_rlt.c:1731
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17248
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18389
static void addAuxexprCoefs(SCIP_VAR *var1, SCIP_VAR *var2, SCIP_CONSNONLINEAR_AUXEXPR *auxexpr, SCIP_Real coef, SCIP_Real *coefaux, SCIP_Real *coef1, SCIP_Real *coef2, SCIP_Real *cst)
Definition: sepa_rlt.c:1834
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip_sepa.c:231
#define SCIP_Bool
Definition: def.h:91
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
Definition: scip_lp.c:1607
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
SCIP_CONSNONLINEAR_BILINTERM * SCIPgetBilinTermsNonlinear(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPselectCutsHybrid(SCIP *scip, SCIP_ROW **cuts, SCIP_ROW **forcedcuts, SCIP_RANDNUMGEN *randnumgen, SCIP_Real goodscorefac, SCIP_Real badscorefac, SCIP_Real goodmaxparall, SCIP_Real maxparall, SCIP_Real dircutoffdistweight, SCIP_Real efficacyweight, SCIP_Real objparalweight, SCIP_Real intsupportweight, int ncuts, int nforcedcuts, int maxselectedcuts, int *nselectedcuts)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
constraint handler for nonlinear constraints specified by algebraic expressions
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18357
#define SEPA_DELAY
Definition: sepa_rlt.c:59
int nrows
Definition: sepa_rlt.c:96
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:361
static SCIP_DECL_SEPAFREE(sepaFreeRlt)
Definition: sepa_rlt.c:3085
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11943
#define SEPA_PRIORITY
Definition: sepa_rlt.c:53
#define MIN(x, y)
Definition: def.h:243
public methods for LP management
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1453
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition: scip_lp.c:1583
#define DEFAULT_MAXROUNDS
Definition: sepa_rlt.c:64
void SCIPaddSquareSecant(SCIP *scip, SCIP_Real sqrcoef, SCIP_Real lb, SCIP_Real ub, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
Definition: expr_pow.c:3322
SCIP_Real SCIPevalBilinAuxExprNonlinear(SCIP *scip, SCIP_VAR *x, SCIP_VAR *y, SCIP_CONSNONLINEAR_AUXEXPR *auxexpr, SCIP_SOL *sol)
static SCIP_RETCODE createSepaData(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_rlt.c:1596
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17790
void SCIPaddBilinMcCormick(SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real *lincoefx, SCIP_Real *lincoefy, SCIP_Real *linconstant, SCIP_Bool *success)
#define DEFAULT_ONLYCONTROWS
Definition: sepa_rlt.c:67
static SCIP_RETCODE fillRelationTables(SCIP *scip, SCIP_ROW **prob_rows, int nrows, SCIP_HASHTABLE *hashtable2, SCIP_HASHTABLE *hashtable3, SCIP_HASHMAP *vars_in_2rels, int *row_list)
Definition: sepa_rlt.c:1104
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2608
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18403
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
#define DEFAULT_USEPROJECTION
Definition: sepa_rlt.c:70
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2346
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
reformulation-linearization technique separator
SCIP_Real * r
Definition: circlepacking.c:59
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18374
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17258
static SCIP_RETCODE separateRltCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_HASHMAP *row_to_pos, RLT_SIMPLEROW *projrows, SCIP_ROW **rows, int nrows, SCIP_Bool allowlocal, int *bestunderestimators, int *bestoverestimators, SCIP_RESULT *result)
Definition: sepa_rlt.c:2825
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
#define SCIPfreeBuffer(scip, ptr)
Definition: scip_mem.h:134
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:17126
#define MAX(x, y)
Definition: def.h:239
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:167
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17042
#define MAXVARBOUND
Definition: sepa_rlt.c:85
static SCIP_RETCODE getOriginalRows(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: sepa_rlt.c:414
static SCIP_RETCODE markRowsXj(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, int j, SCIP_Bool local, SCIP_HASHMAP *row_to_pos, int *bestunderest, int *bestoverest, unsigned int *row_marks, int *row_idcs, int *nmarked)
Definition: sepa_rlt.c:2501
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3042
static SCIP_DECL_SEPACOPY(sepaCopyRlt)
Definition: sepa_rlt.c:3071
static SCIP_RETCODE freeSepaData(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_rlt.c:370
SCIP_Real cst
Definition: sepa_rlt.c:165
SCIP_Real * coefs
Definition: sepa_rlt.c:161
SCIP_VAR * a
Definition: circlepacking.c:66
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17539
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1216
#define SCIP_Real
Definition: def.h:173
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:146
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:718
SCIP_VAR ** y
Definition: circlepacking.c:64
static SCIP_RETCODE createProjRow(SCIP *scip, RLT_SIMPLEROW *simplerow, SCIP_ROW *row, SCIP_SOL *sol, SCIP_Bool local)
Definition: sepa_rlt.c:2260
static SCIP_RETCODE separateMcCormickImplicit(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, int *bestunderestimators, int *bestoverestimators, SCIP_RESULT *result)
Definition: sepa_rlt.c:2668
#define SCIP_INVALID
Definition: def.h:193
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:18325
int SCIPhashtableGetNEntries(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2777
#define DEFAULT_DETECTHIDDEN
Definition: sepa_rlt.c:71
static void implBndToBigM(SCIP *scip, SCIP_VAR **vars_xwy, int binvarpos, int implvarpos, SCIP_BOUNDTYPE bndtype, SCIP_Bool binval, SCIP_Real implbnd, SCIP_Real *coefs, SCIP_Real *side)
Definition: sepa_rlt.c:813
static SCIP_RETCODE ensureVarsSize(SCIP *scip, SCIP_SEPADATA *sepadata, int n)
Definition: sepa_rlt.c:520
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17759
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17585
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_rlt.c:65
int SCIProwGetIndex(SCIP_ROW *row)
Definition: lp.c:17361
SCIP_RETCODE SCIPinsertBilinearTermImplicitNonlinear(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_VAR *x, SCIP_VAR *y, SCIP_VAR *auxvar, SCIP_Real coefx, SCIP_Real coefy, SCIP_Real coefaux, SCIP_Real cst, SCIP_Bool overestimate)
#define DEFAULT_MAXNCUTS
Definition: sepa_rlt.c:63
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
#define DEFAULT_GOODSCORE
Definition: sepa_rlt.c:75
void SCIPaddSquareLinearization(SCIP *scip, SCIP_Real sqrcoef, SCIP_Real refpoint, SCIP_Bool isint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
Definition: expr_pow.c:3254
#define DEFAULT_ONLYEQROWS
Definition: sepa_rlt.c:66
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
#define SCIPallocClearBlockMemory(scip, ptr)
Definition: scip_mem.h:91
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
#define DEFAULT_MAXPARALL
Definition: sepa_rlt.c:83
static void clearVarAdjacency(SCIP *scip, SCIP_HASHMAP *adjvarmap)
Definition: sepa_rlt.c:340
static SCIP_RETCODE createProjRows(SCIP *scip, SCIP_ROW **rows, int nrows, SCIP_SOL *sol, RLT_SIMPLEROW **projrows, SCIP_Bool local, SCIP_Bool *allcst)
Definition: sepa_rlt.c:2348
SCIP_Longint SCIPgetNLPs(SCIP *scip)
static SCIP_RETCODE detectHiddenProducts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_HASHMAP *varmap)
Definition: sepa_rlt.c:1232
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17611
static SCIP_RETCODE isAcceptableRow(SCIP_SEPADATA *sepadata, SCIP_ROW *row, SCIP_VAR *var, int *currentnunknown, SCIP_Bool *acceptable)
Definition: sepa_rlt.c:1788
SCIP_RETCODE SCIPincludeSepaRlt(SCIP *scip)
Definition: sepa_rlt.c:3301
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
void SCIPvarGetImplicVarBounds(SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_Real *lb, SCIP_Real *ub)
Definition: var.c:11147
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
const char * name
Definition: sepa_rlt.c:160
SCIP_CONSNONLINEAR_AUXEXPR ** exprs
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:52
#define SEPA_FREQ
Definition: sepa_rlt.c:54
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
static SCIP_RETCODE detectProductsClique(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real *coefs1, SCIP_VAR **vars_xwy, SCIP_Real side1, SCIP_SIDETYPE sidetype1, int varpos1, int varpos2, SCIP_HASHMAP *varmap, SCIP_Bool f)
Definition: sepa_rlt.c:927
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
enum SCIP_SideType SCIP_SIDETYPE
Definition: type_lp.h:67