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"
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 */
90struct 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};
97typedef 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 */
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 */
111struct 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 */
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 */
177static
178SCIP_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 */
209static
210SCIP_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 */
240static
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 */
314static
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 */
337static
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 */
367static
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 */
411static
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 */
448static
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 */
517static
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 */
547static
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 */
663static
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,
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 */
810static
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 */
858static
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 */
924static
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 */
997static
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 */
1101static
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 */
1229static
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 */
1593static
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 */
1728static
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 */
1785static
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 */
1831static
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 */
1872static
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 */
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 */
2112static
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));
2208 SCIPgetDepth(scip) > 0 && local, FALSE, FALSE) ); /* TODO SCIPgetDepth() should be replaced by depth that is passed on to the SEPAEXEC calls (?) */
2209
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) );
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 */
2257static
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
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 */
2321static
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 */
2345static
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 */
2379static
2380void 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 */
2429static
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 */
2451static
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 */
2498static
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 */
2665static
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;
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
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 */
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 */
2822static
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
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) */
3068static
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 */
3077
3078 return SCIP_OKAY;
3079}
3080
3081/** destructor of separator to free user data (called when SCIP is exiting) */
3082static
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) */
3101static
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 */
3120static
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 */
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 */
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
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
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
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
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}
SCIP_VAR * w
Definition: circlepacking.c:67
SCIP_VAR * a
Definition: circlepacking.c:66
SCIP_VAR ** y
Definition: circlepacking.c:64
SCIP_Real * r
Definition: circlepacking.c:59
SCIP_VAR ** x
Definition: circlepacking.c:63
constraint handler for nonlinear constraints specified by algebraic expressions
hybrid cut selector
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define MAX3(x, y, z)
Definition: def.h:247
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define MIN3(x, y, z)
Definition: def.h:251
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
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:3253
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:3321
power and signed power expression handlers
SCIP_Real SCIPevalBilinAuxExprNonlinear(SCIP *scip, SCIP_VAR *x, SCIP_VAR *y, SCIP_CONSNONLINEAR_AUXEXPR *auxexpr, SCIP_SOL *sol)
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)
int SCIPgetBilinTermIdxNonlinear(SCIP_CONSHDLR *conshdlr, SCIP_VAR *x, SCIP_VAR *y)
SCIP_CONSNONLINEAR_BILINTERM * SCIPgetBilinTermsNonlinear(SCIP_CONSHDLR *conshdlr)
int SCIPgetNBilinTermsNonlinear(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 SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2605
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3088
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3042
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3570
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition: misc.c:3541
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3549
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3357
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2346
int SCIPhashtableGetNEntries(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2777
#define SCIPhashFour(a, b, c, d)
Definition: pub_misc.h:556
void * SCIPhashtableGetEntry(SCIP_HASHTABLE *hashtable, int entryidx)
Definition: misc.c:2785
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
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2608
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2547
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
#define SCIPdebugMsg
Definition: scip_message.h:78
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)
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
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
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
void SCIPswapReals(SCIP_Real *value1, SCIP_Real *value2)
Definition: misc.c:10383
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17042
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:17072
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:17126
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17161
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17151
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:361
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:146
#define SCIPfreeBuffer(scip, ptr)
Definition: scip_mem.h:134
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPallocClearBlockMemory(scip, ptr)
Definition: scip_mem.h:91
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
Definition: scip_mem.h:107
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPallocBuffer(scip, ptr)
Definition: scip_mem.h:122
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition: scip_lp.c:1583
SCIP_Real SCIPgetRowFeasibility(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:2124
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17213
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17238
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17401
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17351
SCIP_SEPA * SCIProwGetOriginSepa(SCIP_ROW *row)
Definition: lp.c:17476
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
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
int SCIProwGetIndex(SCIP_ROW *row)
Definition: lp.c:17361
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
Definition: scip_lp.c:1607
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17258
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17248
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
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:743
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:880
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:167
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip_sepa.c:231
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:633
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:643
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:18270
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17789
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:18292
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18356
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
void SCIPvarGetImplicVarBounds(SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_Real *lb, SCIP_Real *ub)
Definition: var.c:11146
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18373
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17758
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:18302
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:18312
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18402
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18430
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_Bool SCIPvarIsRelaxationOnly(SCIP_VAR *var)
Definition: var.c:17706
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:18282
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18441
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11942
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:18344
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:18324
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:11475
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:18334
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18388
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
void SCIPselectDownIntPtr(int *intarray, void **ptrarray, int k, int len)
SCIP_RETCODE SCIPincludeSepaRlt(SCIP *scip)
Definition: sepa_rlt.c:3299
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
SCIP_Bool SCIPcliqueHasVar(SCIP_CLIQUE *clique, SCIP_VAR *var, SCIP_Bool value)
Definition: implics.c:1141
SCIP_ROW * SCIPconsGetRow(SCIP *scip, SCIP_CONS *cons)
Definition: misc_linear.c:412
bilinear nonlinear handler
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
public methods for LP management
#define SCIPstatisticMessage
Definition: pub_message.h:123
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:664
#define SEPA_PRIORITY
Definition: sepa_rlt.c:53
#define DEFAULT_BADSCORE
Definition: sepa_rlt.c:76
static SCIP_RETCODE isAcceptableRow(SCIP_SEPADATA *sepadata, SCIP_ROW *row, SCIP_VAR *var, int *currentnunknown, SCIP_Bool *acceptable)
Definition: sepa_rlt.c:1786
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:2666
static SCIP_DECL_HASHKEYVAL(hashdataKeyValConss)
Definition: sepa_rlt.c:210
#define DEFAULT_GOODSCORE
Definition: sepa_rlt.c:74
#define DEFAULT_MAXUSEDVARS
Definition: sepa_rlt.c:61
#define SEPA_DELAY
Definition: sepa_rlt.c:58
#define DEFAULT_EFFICACYWEIGHT
Definition: sepa_rlt.c:78
static SCIP_DECL_SEPAEXECLP(sepaExeclpRlt)
Definition: sepa_rlt.c:3121
#define DEFAULT_OBJPARALWEIGHT
Definition: sepa_rlt.c:77
static SCIP_DECL_SEPACOPY(sepaCopyRlt)
Definition: sepa_rlt.c:3069
static SCIP_VAR ** getAdjacentVars(SCIP_HASHMAP *adjvarmap, SCIP_VAR *var, int *nadjacentvars)
Definition: sepa_rlt.c:315
#define DEFAULT_USEPROJECTION
Definition: sepa_rlt.c:69
#define DEFAULT_DETECTHIDDEN
Definition: sepa_rlt.c:70
#define SEPA_DESC
Definition: sepa_rlt.c:52
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:925
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:811
#define MAXVARBOUND
Definition: sepa_rlt.c:83
#define DEFAULT_HIDDENRLT
Definition: sepa_rlt.c:71
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:2823
#define DEFAULT_MAXPARALL
Definition: sepa_rlt.c:81
static void freeProjRow(SCIP *scip, RLT_SIMPLEROW *simplerow)
Definition: sepa_rlt.c:2322
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_rlt.c:64
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:1873
#define SEPA_USESSUBSCIP
Definition: sepa_rlt.c:57
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:859
static SCIP_RETCODE getOriginalRows(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: sepa_rlt.c:412
#define DEFAULT_ONLYORIGINAL
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:1102
static SCIP_DECL_HASHKEYEQ(hashdataKeyEqConss)
Definition: sepa_rlt.c:178
static SCIP_RETCODE createProjRow(SCIP *scip, RLT_SIMPLEROW *simplerow, SCIP_ROW *row, SCIP_SOL *sol, SCIP_Bool local)
Definition: sepa_rlt.c:2258
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:2346
#define DEFAULT_MAXNCUTS
Definition: sepa_rlt.c:62
static SCIP_RETCODE detectHiddenProducts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_HASHMAP *varmap)
Definition: sepa_rlt.c:1230
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:2499
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:1832
#define DEFAULT_USEINSUBSCIP
Definition: sepa_rlt.c:68
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:2113
#define DEFAULT_ADDTOPOOL
Definition: sepa_rlt.c:72
static SCIP_RETCODE createSepaData(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_rlt.c:1594
#define DEFAULT_GOODMAXPARALL
Definition: sepa_rlt.c:80
#define SEPA_MAXBOUNDDIST
Definition: sepa_rlt.c:55
static void clearVarAdjacency(SCIP *scip, SCIP_HASHMAP *adjvarmap)
Definition: sepa_rlt.c:338
#define DEFAULT_DIRCUTOFFDISTWEIGHT
Definition: sepa_rlt.c:79
static SCIP_RETCODE freeSepaData(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_rlt.c:368
#define SEPA_FREQ
Definition: sepa_rlt.c:54
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:449
static SCIP_RETCODE addProductVars(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_VAR *x, SCIP_VAR *y, SCIP_HASHMAP *varmap, int nlocks)
Definition: sepa_rlt.c:548
#define SEPA_NAME
Definition: sepa_rlt.c:51
#define DEFAULT_MAXUNKNOWNTERMS
Definition: sepa_rlt.c:60
static SCIP_RETCODE addAdjacentVars(SCIP *scip, SCIP_HASHMAP *adjvarmap, SCIP_VAR **vars)
Definition: sepa_rlt.c:241
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:998
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:2452
#define DEFAULT_MAXROUNDS
Definition: sepa_rlt.c:63
static void freeProjRows(SCIP *scip, RLT_SIMPLEROW **projrows, int nrows)
Definition: sepa_rlt.c:2430
static SCIP_RETCODE ensureVarsSize(SCIP *scip, SCIP_SEPADATA *sepadata, int n)
Definition: sepa_rlt.c:518
static SCIP_DECL_SEPAFREE(sepaFreeRlt)
Definition: sepa_rlt.c:3083
#define DEFAULT_ONLYEQROWS
Definition: sepa_rlt.c:65
static SCIP_DECL_SEPAEXITSOL(sepaExitsolRlt)
Definition: sepa_rlt.c:3102
static void getBestEstimators(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, int *bestunderestimators, int *bestoverestimators)
Definition: sepa_rlt.c:1729
#define DEFAULT_ONLYCONTROWS
Definition: sepa_rlt.c:66
reformulation-linearization technique separator
SCIP_VAR ** adjacentvars
Definition: sepa_rlt.c:104
SCIP_VAR ** vars
int nrows
Definition: sepa_rlt.c:94
int firstrow
Definition: sepa_rlt.c:95
SCIP_Real rhs
Definition: sepa_rlt.c:161
SCIP_VAR ** vars
Definition: sepa_rlt.c:160
SCIP_Real cst
Definition: sepa_rlt.c:163
const char * name
Definition: sepa_rlt.c:158
SCIP_Real * coefs
Definition: sepa_rlt.c:159
SCIP_Real lhs
Definition: sepa_rlt.c:162
SCIP_CONSNONLINEAR_AUXEXPR ** exprs
union SCIP_ConsNonlinear_BilinTerm::@4 aux
SCIP_Real sup
Definition: intervalarith.h:56
SCIP_Real inf
Definition: intervalarith.h:55
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
@ SCIP_SIDETYPE_RIGHT
Definition: type_lp.h:65
@ SCIP_SIDETYPE_LEFT
Definition: type_lp.h:64
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
enum SCIP_SideType SCIP_SIDETYPE
Definition: type_lp.h:67
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SEPARATED
Definition: type_result.h:49
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:52
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62
@ SCIP_VARSTATUS_COLUMN
Definition: type_var.h:51