Scippy

SCIP

Solving Constraint Integer Programs

sepa_eccuts.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-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file sepa_eccuts.c
17  * @brief edge concave cut separator
18  * @author Benjamin Müller
19  */
20 
21 /**@todo only count number of fixed variables in the edge concave terms */
22 /**@todo only add nonlinear row aggregations where at least ...% of the variables (bilinear terms?) are in edge concave
23  * terms */
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 #include <assert.h>
27 #include <string.h>
28 
29 #include "scip/scipdefplugins.h"
30 #include "scip/sepa_eccuts.h"
31 #include "scip/cons_xor.h"
32 #include "scip/nlp.h"
33 #include "tclique/tclique.h"
34 
35 #define SEPA_NAME "eccuts"
36 #define SEPA_DESC "separator for edge-concave functions"
37 #define SEPA_PRIORITY -13000
38 #define SEPA_FREQ -1
39 #define SEPA_MAXBOUNDDIST 1.0
40 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
41 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
42 
43 #define CLIQUE_MAXFIRSTNODEWEIGHT 1000 /**< maximum weight of branching nodes in level 0; 0 if not used for cliques
44  * with at least one fractional node) */
45 #define CLIQUE_MINWEIGHT 0 /**< lower bound for weight of generated cliques */
46 #define CLIQUE_MAXNTREENODES 10000 /**< maximal number of nodes of b&b tree */
47 #define CLIQUE_BACKTRACKFREQ 10000 /**< frequency to backtrack to first level of tree (0: no premature backtracking) */
48 
49 #define DEFAULT_DYNAMICCUTS TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */
50 #define DEFAULT_MAXROUNDS 10 /**< maximal number of separation rounds per node (-1: unlimited) */
51 #define DEFAULT_MAXROUNDSROOT 250 /**< maximal number of separation rounds in the root node (-1: unlimited) */
52 #define DEFAULT_MAXDEPTH -1 /**< maximal depth at which the separator is applied */
53 #define DEFAULT_MAXSEPACUTS 10 /**< maximal number of e.c. cuts separated per separation round */
54 #define DEFAULT_MAXSEPACUTSROOT 50 /**< maximal number of e.c. cuts separated per separation round in root node */
55 #define DEFAULT_CUTMAXRANGE 1e+7 /**< maximal coefficient range of a cut (maximal coefficient divided by minimal
56  * coefficient) in order to be added to LP relaxation */
57 #define DEFAULT_MINVIOLATION 0.3 /**< minimal violation of an e.c. cut to be separated */
58 #define DEFAULT_MINAGGRSIZE 3 /**< search for e.c. aggregation of at least this size (has to be >= 3) */
59 #define DEFAULT_MAXAGGRSIZE 4 /**< search for e.c. aggregation of at most this size (has to be >= minaggrsize) */
60 #define DEFAULT_MAXBILINTERMS 500 /**< maximum number of bilinear terms allowed to be in a quadratic constraint */
61 #define DEFAULT_MAXSTALLROUNDS 5 /**< maximum number of unsuccessful rounds in the e.c. aggregation search */
62 
63 #define SUBSCIP_NODELIMIT 100LL /**< node limit to solve the sub-SCIP */
64 
65 #define ADJUSTFACETTOL 1e-6 /**< adjust resulting facets in checkRikun() up to a violation of this value */
66 #define USEDUALSIMPLEX TRUE /**< use dual or primal simplex algorithm? */
67 
68 /** first values for 2^n */
69 static const int poweroftwo[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192 };
70 
71 /*
72  * Data structures
73  */
74 
75 /** data to store a single edge-concave aggregations; an edge-concave aggregation of a quadratic constraint is a subset
76  * of nonconvex bilinear terms
77  */
78 struct EcAggr
79 {
80  SCIP_VAR** vars; /**< variables */
81  int nvars; /**< number of variables */
82  int varsize; /**< size of vars array */
83 
84  SCIP_Real* termcoefs; /**< coefficients of bilinear terms */
85  int* termvars1; /**< index of the first variable of each bilinear term */
86  int* termvars2; /**< index of the second variable of each bilinear term*/
87  int nterms; /**< number of bilinear terms in the aggregation */
88  int termsize; /**< size of term{coefs,vars1,vars2} arrays */
89 };
90 typedef struct EcAggr SCIP_ECAGGR;
91 
92 /** data to store all edge-concave aggregations and the remaining part of a nonlinear row of the form g(x) <= rhs */
93 struct NlrowAggr
94 {
95  SCIP_NLROW* nlrow; /**< nonlinear row aggregation */
96  SCIP_Bool rhsaggr; /**< consider nonlinear row aggregation for g(x) <= rhs (TRUE) or
97  * g(x) >= lhs (FALSE) */
98 
99  SCIP_ECAGGR** ecaggr; /**< array with all edge-concave aggregations */
100  int necaggr; /**< number of edge-concave aggregation */
102  SCIP_VAR** linvars; /**< linear variables */
103  SCIP_Real* lincoefs; /**< linear coefficients */
104  int nlinvars; /**< number of linear variables */
106  SCIP_VAR** quadvars; /**< quadratic variables */
107  int* quadvar2aggr; /**< stores in which edge-concave aggregation the i-th quadratic variable
108  * is contained (< 0: in no edge-concave aggregation) */
109  int nquadvars; /**< number of quadratic variables */
110 
111  SCIP_VAR** remtermvars1; /**< first quadratic variable of remaining bilinear terms */
112  SCIP_VAR** remtermvars2; /**< second quadratic variable of remaining bilinear terms */
113  SCIP_Real* remtermcoefs; /**< coefficients for each remaining bilinear term */
114  int nremterms; /**< number of remaining bilinear terms */
115  int remtermsize; /**< size of remterm* arrays */
117  SCIP_Real rhs; /**< rhs of the nonlinear row */
118  SCIP_Real constant; /**< constant part of the nonlinear row */
119 };
120 typedef struct NlrowAggr SCIP_NLROWAGGR;
121 
122 /** separator data */
123 struct SCIP_SepaData
124 {
125  SCIP_NLROWAGGR** nlrowaggrs; /**< array containing all nonlinear row aggregations */
126  int nnlrowaggrs; /**< number of nonlinear row aggregations */
127  int nlrowaggrssize; /**< size of nlrowaggrs array */
128  SCIP_Bool searchedforaggr; /**< flag if we already searched for nlrow aggregation candidates */
129  int minaggrsize; /**< only search for e.c. aggregations of at least this size (has to be >= 3) */
130  int maxaggrsize; /**< only search for e.c. aggregations of at most this size (has to be >= minaggrsize) */
131  int maxecsize; /**< largest edge concave aggregation size */
132  int maxbilinterms; /**< maximum number of bilinear terms allowed to be in a quadratic constraint */
133  int maxstallrounds; /**< maximum number of unsuccessful rounds in the e.c. aggregation search */
134 
135  SCIP_LPI* lpi; /**< LP interface to solve the LPs to compute the facets of the convex envelopes */
136  int lpisize; /**< maximum size of e.c. aggregations which can be handled by the LP interface */
137 
138  SCIP_Real cutmaxrange; /**< maximal coef range of a cut (maximal coefficient divided by minimal
139  * coefficient) in order to be added to LP relaxation */
140  SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */
141  SCIP_Real minviolation; /**< minimal violation of an e.c. cut to be separated */
142 
143  int maxrounds; /**< maximal number of separation rounds per node (-1: unlimited) */
144  int maxroundsroot; /**< maximal number of separation rounds in the root node (-1: unlimited) */
145  int maxdepth; /**< maximal depth at which the separator is applied */
146  int maxsepacuts; /**< maximal number of e.c. cuts separated per separation round */
147  int maxsepacutsroot; /**< maximal number of e.c. cuts separated per separation round in root node */
148 
149 #ifdef SCIP_STATISTIC
150  SCIP_Real aggrsearchtime; /**< total time spent for searching edge concave aggregations */
151  int nlhsnlrowaggrs; /**< number of found nonlinear row aggregations for SCIP_NLROWs of the form g(x) <= rhs */
152  int nrhsnlrowaggrs; /**< number of found nonlinear row aggregations for SCIP_NLROWs of the form g(x) >= lhs */
153 #endif
154 };
155 
156 
157 /*
158  * Local methods
159  */
160 
161 /** creates and empty edge-concave aggregation (without bilinear terms) */
162 static
164  SCIP* scip, /**< SCIP data structure */
165  SCIP_ECAGGR** ecaggr, /**< pointer to store the edge-concave aggregation */
166  int nquadvars, /**< number of quadratic variables */
167  int nquadterms /**< number of bilinear terms */
168  )
169 {
170  assert(scip != NULL);
171  assert(ecaggr != NULL);
172  assert(nquadvars > 0);
173  assert(nquadterms >= nquadvars);
174 
175  SCIP_CALL( SCIPallocBlockMemory(scip, ecaggr) );
176 
177  (*ecaggr)->nvars = 0;
178  (*ecaggr)->nterms = 0;
179  (*ecaggr)->varsize = nquadvars;
180  (*ecaggr)->termsize = nquadterms;
181 
182  /* allocate enough memory for the quadratic variables and bilinear terms */
183  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*ecaggr)->vars, nquadvars) );
184  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*ecaggr)->termcoefs, nquadterms) );
185  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*ecaggr)->termvars1, nquadterms) );
186  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*ecaggr)->termvars2, nquadterms) );
187 
188  return SCIP_OKAY;
189 }
190 
191 /** frees and edge-concave aggregation */
192 static
194  SCIP* scip, /**< SCIP data structure */
195  SCIP_ECAGGR** ecaggr /**< pointer to store the edge-concave aggregation */
196  )
197 {
198  assert(scip != NULL);
199  assert(ecaggr != NULL);
200 
201  SCIPfreeBlockMemoryArray(scip, &((*ecaggr)->termcoefs), (*ecaggr)->termsize);
202  SCIPfreeBlockMemoryArray(scip, &((*ecaggr)->termvars1), (*ecaggr)->termsize);
203  SCIPfreeBlockMemoryArray(scip, &((*ecaggr)->termvars2), (*ecaggr)->termsize);
204  SCIPfreeBlockMemoryArray(scip, &((*ecaggr)->vars), (*ecaggr)->varsize);
205 
206  SCIPfreeBlockMemory(scip, ecaggr);
207  *ecaggr = NULL;
208 
209  return SCIP_OKAY;
210 }
211 
212 /** adds a quadratic variable to an edge-concave aggregation */
213 static
215  SCIP_ECAGGR* ecaggr, /**< pointer to store the edge-concave aggregation */
216  SCIP_VAR* x /**< first variable */
217  )
218 {
219  ecaggr->vars[ ecaggr->nvars++ ] = x;
220  return SCIP_OKAY;
221 }
222 
223 /** adds a bilinear term to an edge-concave aggregation */
224 static
226  SCIP* scip, /**< SCIP data structure */
227  SCIP_ECAGGR* ecaggr, /**< pointer to store the edge-concave aggregation */
228  SCIP_VAR* x, /**< first variable */
229  SCIP_VAR* y, /**< second variable */
230  SCIP_Real coef /**< bilinear coefficient */
231  )
232 {
233  int idx1;
234  int idx2;
235  int i;
236 
237  assert(x != NULL);
238  assert(y != NULL);
239  assert(ecaggr->nterms + 1 <= ((ecaggr->nvars + 1) * ecaggr->nvars) / 2);
240  assert(!SCIPisZero(scip, coef));
241 
242  idx1 = -1;
243  idx2 = -1;
244 
245  /* search for the quadratic variables in the e.c. aggregation */
246  for( i = 0; i < ecaggr->nvars && (idx1 == -1 || idx2 == -1); ++i )
247  {
248  if( ecaggr->vars[i] == x )
249  idx1 = i;
250  if( ecaggr->vars[i] == y )
251  idx2 = i;
252  }
253 
254  assert(idx1 != -1 && idx2 != -1);
255 
256  ecaggr->termcoefs[ ecaggr->nterms ] = coef;
257  ecaggr->termvars1[ ecaggr->nterms ] = idx1;
258  ecaggr->termvars2[ ecaggr->nterms ] = idx2;
259  ++(ecaggr->nterms);
260 
261  return SCIP_OKAY;
262 }
263 
264 #ifdef SCIP_DEBUG
265 /** prints an edge-concave aggregation */
266 static
267 void ecaggrPrint(
268  SCIP* scip, /**< SCIP data structure */
269  SCIP_ECAGGR* ecaggr /**< pointer to store the edge-concave aggregation */
270  )
271 {
272  int i;
273 
274  assert(scip != NULL);
275  assert(ecaggr != NULL);
276 
277  SCIPdebugMsg(scip, " nvars = %d nterms = %d\n", ecaggr->nvars, ecaggr->nterms);
278  SCIPdebugMsg(scip, " vars: ");
279  for( i = 0; i < ecaggr->nvars; ++i )
280  SCIPdebugMsgPrint(scip, "%s ", SCIPvarGetName(ecaggr->vars[i]));
281  SCIPdebugMsgPrint(scip, "\n");
282 
283  SCIPdebugMsg(scip, " terms: ");
284  for( i = 0; i < ecaggr->nterms; ++i )
285  {
286  SCIP_VAR* x;
287  SCIP_VAR* y;
288 
289  x = ecaggr->vars[ ecaggr->termvars1[i] ];
290  y = ecaggr->vars[ ecaggr->termvars2[i] ];
291  SCIPdebugMsgPrint(scip, "%e %s * %s ", ecaggr->termcoefs[i], SCIPvarGetName(x), SCIPvarGetName(y) );
292  }
293  SCIPdebugMsgPrint(scip, "\n");
294 }
295 #endif
296 
297 /** stores linear terms in a given nonlinear row aggregation */
298 static
300  SCIP* scip, /**< SCIP data structure */
301  SCIP_NLROWAGGR* nlrowaggr, /**< nonlinear row aggregation */
302  SCIP_VAR** linvars, /**< linear variables */
303  SCIP_Real* lincoefs, /**< linear coefficients */
304  int nlinvars /**< number of linear variables */
305  )
306 {
307  assert(scip != NULL);
308  assert(nlrowaggr != NULL);
309  assert(linvars != NULL || nlinvars == 0);
310  assert(lincoefs != NULL || nlinvars == 0);
311  assert(nlinvars >= 0);
312 
313  nlrowaggr->nlinvars = nlinvars;
314  nlrowaggr->linvars = NULL;
315  nlrowaggr->lincoefs = NULL;
316 
317  if( nlinvars > 0 )
318  {
319  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nlrowaggr->linvars, nlinvars) );
320  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nlrowaggr->lincoefs, nlinvars) );
321  BMScopyMemoryArray(nlrowaggr->linvars, linvars, nlinvars);
322  BMScopyMemoryArray(nlrowaggr->lincoefs, lincoefs, nlinvars);
323  }
324 
325  /* if we have a nlrow of the form g(x) >= lhs, multiply every coefficient by -1 */
326  if( !nlrowaggr->rhsaggr )
327  {
328  int i;
329 
330  for( i = 0; i < nlrowaggr->nlinvars; ++i )
331  nlrowaggr->lincoefs[i] *= -1.0;
332  }
333 
334  return SCIP_OKAY;
335 }
336 
337 /** stores quadratic variables in a given nonlinear row aggregation */
338 static
340  SCIP* scip, /**< SCIP data structure */
341  SCIP_NLROWAGGR* nlrowaggr, /**< nonlinear row aggregation */
342  SCIP_VAR** quadvars, /**< quadratic variables */
343  int nquadvars /**< number of quadratic variables */
344  )
345 {
346  assert(scip != NULL);
347  assert(nlrowaggr != NULL);
348  assert(quadvars != NULL);
349  assert(nquadvars > 0);
350 
351  nlrowaggr->nquadvars = nquadvars;
352  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nlrowaggr->quadvars, nquadvars) );
353  BMScopyMemoryArray(nlrowaggr->quadvars, quadvars, nquadvars);
354 
355  return SCIP_OKAY;
356 }
357 
358 /** adds a remaining bilinear term to a given nonlinear row aggregation */
359 static
361  SCIP* scip, /**< SCIP data structure */
362  SCIP_NLROWAGGR* nlrowaggr, /**< nonlinear row aggregation */
363  SCIP_VAR* x, /**< first variable */
364  SCIP_VAR* y, /**< second variable */
365  SCIP_Real coef /**< bilinear coefficient */
366  )
367 {
368  assert(nlrowaggr != NULL);
369  assert(x != NULL);
370  assert(y != NULL);
371  assert(coef != 0.0);
372 
373  nlrowaggr->remtermcoefs[ nlrowaggr->nremterms ] = coef;
374  nlrowaggr->remtermvars1[ nlrowaggr->nremterms ] = x;
375  nlrowaggr->remtermvars2[ nlrowaggr->nremterms ] = y;
376  ++(nlrowaggr->nremterms);
377 
378  return SCIP_OKAY;
379 }
380 
381 /** creates a nonlinear row aggregation */
382 static
384  SCIP* scip, /**< SCIP data structure */
385  SCIP_NLROW* nlrow, /**< nonlinear row */
386  SCIP_NLROWAGGR** nlrowaggr, /**< pointer to store the nonlinear row aggregation */
387  int* quadvar2aggr, /**< mapping between quadratic variables and edge-concave aggregation
388  * stores a negative value if the quadratic variables does not belong
389  * to any aggregation */
390  int nfound, /**< number of edge-concave aggregations */
391  SCIP_Bool rhsaggr /**< consider nonlinear row aggregation for g(x) <= rhs (TRUE) or
392  * lhs <= g(x) (FALSE) */
393  )
394 {
395  int* aggrnvars; /* count the number of variables in each e.c. aggregations */
396  int* aggrnterms; /* count the number of bilinear terms in each e.c. aggregations */
397  int nquadelems;
398  int nquadvars;
399  int nremterms;
400  int i;
401 
402  assert(scip != NULL);
403  assert(nlrow != NULL);
404  assert(nlrowaggr != NULL);
405  assert(quadvar2aggr != NULL);
406  assert(nfound > 0);
407 
408  nquadelems = SCIPnlrowGetNQuadElems(nlrow);
409  nquadvars = SCIPnlrowGetNQuadVars(nlrow);
410  nremterms = 0;
411 
412  SCIP_CALL( SCIPallocBufferArray(scip, &aggrnvars, nfound) );
413  SCIP_CALL( SCIPallocBufferArray(scip, &aggrnterms, nfound) );
414 
415  /* create an empty nonlinear row aggregation */
416  SCIP_CALL( SCIPallocBlockMemory(scip, nlrowaggr) );
417  (*nlrowaggr)->nlrow = nlrow;
418  (*nlrowaggr)->rhsaggr = rhsaggr;
419  (*nlrowaggr)->nquadvars = nquadvars;
420  (*nlrowaggr)->rhs = rhsaggr ? SCIPnlrowGetRhs(nlrow) : -SCIPnlrowGetLhs(nlrow);
421  (*nlrowaggr)->constant = rhsaggr ? SCIPnlrowGetConstant(nlrow) : -SCIPnlrowGetConstant(nlrow);
422 
423  (*nlrowaggr)->quadvars = NULL;
424  (*nlrowaggr)->quadvar2aggr = NULL;
425  (*nlrowaggr)->remtermcoefs = NULL;
426  (*nlrowaggr)->remtermvars1 = NULL;
427  (*nlrowaggr)->remtermvars2 = NULL;
428  (*nlrowaggr)->nquadvars = 0;
429  (*nlrowaggr)->nremterms = 0;
430 
431  /* copy quadvar2aggr array */
432  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlrowaggr)->quadvar2aggr, nquadvars) );
433  BMScopyMemoryArray((*nlrowaggr)->quadvar2aggr, quadvar2aggr, nquadvars);
434 
435  /* store all linear terms */
437  SCIPnlrowGetNLinearVars(nlrow)) );
438 
439  /* store all quadratic variables */
441  assert((*nlrowaggr)->nquadvars == nquadvars);
442 
443  for( i = 0; i < nfound; ++i )
444  {
445  aggrnvars[i] = 0;
446  aggrnterms[i] = 0;
447  }
448 
449  /* count the number of variables in each e.c. aggregation */
450  for( i = 0; i < nquadvars; ++i )
451  {
452  if( quadvar2aggr[i] >= 0)
453  ++aggrnvars[ quadvar2aggr[i] ];
454  }
455 
456  /* count the number of bilinear terms in each e.c. aggregation */
457  for( i = 0; i < nquadelems; ++i )
458  {
459  SCIP_QUADELEM* quadelem;
460  SCIP_Real coef;
461  int idx1;
462  int idx2;
463 
464  quadelem = &SCIPnlrowGetQuadElems(nlrow)[i];
465  idx1 = quadvar2aggr[quadelem->idx1];
466  idx2 = quadvar2aggr[quadelem->idx2];
467  coef = rhsaggr ? quadelem->coef : -quadelem->coef;
468 
469  /* variables has to belong to the same e.c. aggregation; bilinear / quadratic term has to be concave */
470  if( idx1 >= 0 && idx2 >= 0 && idx1 == idx2 && (quadelem->idx1 != quadelem->idx2 || SCIPisNegative(scip, coef) ) )
471  ++aggrnterms[idx1];
472  else
473  ++nremterms;
474  }
475 
476  /* create all edge-concave aggregations (empty) and remaining terms */
477  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlrowaggr)->ecaggr, nfound) );
478  if( nremterms > 0 )
479  {
480  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlrowaggr)->remtermcoefs, nremterms) );
481  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlrowaggr)->remtermvars1, nremterms) );
482  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlrowaggr)->remtermvars2, nremterms) );
483  (*nlrowaggr)->remtermsize = nremterms;
484  }
485  (*nlrowaggr)->necaggr = nfound;
486 
487  for( i = 0; i < nfound; ++i )
488  {
489  SCIP_CALL( ecaggrCreateEmpty(scip, &(*nlrowaggr)->ecaggr[i], aggrnvars[i], aggrnterms[i]) );
490  }
491 
492  /* add quadratic variables to the edge-concave aggregations */
493  for( i = 0; i < nquadvars; ++i )
494  {
495  int idx;
496 
497  idx = quadvar2aggr[i];
498 
499  if( idx >= 0)
500  {
501  SCIPdebugMsg(scip, "add quadvar %d to aggr. %d\n", i, idx);
502  SCIP_CALL( ecaggrAddQuadvar((*nlrowaggr)->ecaggr[idx], SCIPnlrowGetQuadVars(nlrow)[i]) );
503  }
504  }
505 
506  /* add the bilinear /quadratic terms to the edge-concave aggregations or in the remaining part */
507  for( i = 0; i < nquadelems; ++i )
508  {
509  SCIP_QUADELEM* quadelem;
510  SCIP_VAR* x;
511  SCIP_VAR* y;
512  SCIP_Real coef;
513  int idx1;
514  int idx2;
515 
516  quadelem = &SCIPnlrowGetQuadElems(nlrow)[i];
517  x = SCIPnlrowGetQuadVars(nlrow)[quadelem->idx1];
518  y = SCIPnlrowGetQuadVars(nlrow)[quadelem->idx2];
519  idx1 = quadvar2aggr[quadelem->idx1];
520  idx2 = quadvar2aggr[quadelem->idx2];
521  coef = rhsaggr ? quadelem->coef : -quadelem->coef;
522 
523  if( idx1 >= 0 && idx2 >= 0 && idx1 == idx2 && (quadelem->idx1 != quadelem->idx2 || SCIPisNegative(scip, coef) ) )
524  {
525  SCIP_CALL( ecaggrAddBilinTerm(scip, (*nlrowaggr)->ecaggr[idx1], x, y, coef) );
526  SCIPdebugMsg(scip, "add term %e *%d*%d to aggr. %d\n", coef, quadelem->idx1, quadelem->idx2, idx1);
527  }
528  else
529  {
530  SCIP_CALL( nlrowaggrAddRemBilinTerm(scip, *nlrowaggr, x, y, coef) );
531  SCIPdebugMsg(scip, "add term %e *%d*%d to the remaining part\n", coef, quadelem->idx1, quadelem->idx2);
532  }
533  }
534 
535  /* free allocated memory */
536  SCIPfreeBufferArray(scip, &aggrnterms);
537  SCIPfreeBufferArray(scip, &aggrnvars);
538 
539  return SCIP_OKAY;
540 }
541 
542 /** frees a nonlinear row aggregation */
543 static
545  SCIP* scip, /**< SCIP data structure */
546  SCIP_NLROWAGGR** nlrowaggr /**< pointer to free the nonlinear row aggregation */
547  )
548 {
549  int i;
550 
551  assert(scip != NULL);
552  assert(nlrowaggr != NULL);
553  assert(*nlrowaggr != NULL);
554  (*nlrowaggr)->nlrow = NULL;
555  assert((*nlrowaggr)->quadvars != NULL);
556  assert((*nlrowaggr)->nquadvars > 0);
557  assert((*nlrowaggr)->nremterms >= 0);
558 
559  /* free remaining part */
560  SCIPfreeBlockMemoryArrayNull(scip, &(*nlrowaggr)->remtermcoefs, (*nlrowaggr)->remtermsize);
561  SCIPfreeBlockMemoryArrayNull(scip, &(*nlrowaggr)->remtermvars1, (*nlrowaggr)->remtermsize);
562  SCIPfreeBlockMemoryArrayNull(scip, &(*nlrowaggr)->remtermvars2, (*nlrowaggr)->remtermsize);
563 
564  /* free quadratic variables */
565  SCIPfreeBlockMemoryArray(scip, &(*nlrowaggr)->quadvars, (*nlrowaggr)->nquadvars);
566  SCIPfreeBlockMemoryArray(scip, &(*nlrowaggr)->quadvar2aggr, (*nlrowaggr)->nquadvars);
567  (*nlrowaggr)->quadvars = NULL;
568  (*nlrowaggr)->quadvar2aggr = NULL;
569  (*nlrowaggr)->nquadvars = 0;
570 
571  /* free linear part */
572  if( (*nlrowaggr)->nlinvars > 0 )
573  {
574  SCIPfreeBlockMemoryArray(scip, &(*nlrowaggr)->linvars, (*nlrowaggr)->nlinvars);
575  SCIPfreeBlockMemoryArray(scip, &(*nlrowaggr)->lincoefs, (*nlrowaggr)->nlinvars);
576  (*nlrowaggr)->linvars = 0;
577  (*nlrowaggr)->linvars = NULL;
578  (*nlrowaggr)->lincoefs = NULL;
579  }
580 
581  /* free edge-concave aggregations */
582  for( i = 0; i < (*nlrowaggr)->necaggr; ++i )
583  {
584  SCIP_CALL( ecaggrFree(scip, &(*nlrowaggr)->ecaggr[i]) );
585  }
586  SCIPfreeBlockMemoryArray(scip, &(*nlrowaggr)->ecaggr, (*nlrowaggr)->necaggr);
587 
588  /* free nlrow aggregation */
589  SCIPfreeBlockMemory(scip, nlrowaggr);
590 
591  return SCIP_OKAY;
592 }
593 
594 #ifdef SCIP_DEBUG
595 /** prints a nonlinear row aggregation */
596 static
597 void nlrowaggrPrint(
598  SCIP* scip, /**< SCIP data structure */
599  SCIP_NLROWAGGR* nlrowaggr /**< nonlinear row aggregation */
600  )
601 {
602  int i;
603 
604  SCIPdebugMsg(scip, " nlrowaggr rhs = %e\n", nlrowaggr->rhs);
605  SCIPdebugMsg(scip, " #remaining terms = %d\n", nlrowaggr->nremterms);
606 
607  SCIPdebugMsg(scip, "remaining terms: ");
608  for( i = 0; i < nlrowaggr->nremterms; ++i )
609  SCIPdebugMsgPrint(scip, "%e %s * %s + ", nlrowaggr->remtermcoefs[i], SCIPvarGetName(nlrowaggr->remtermvars1[i]),
610  SCIPvarGetName(nlrowaggr->remtermvars2[i]) );
611  for( i = 0; i < nlrowaggr->nlinvars; ++i )
612  SCIPdebugMsgPrint(scip, "%e %s + ", nlrowaggr->lincoefs[i], SCIPvarGetName(nlrowaggr->linvars[i]) );
613  SCIPdebugMsgPrint(scip, "\n");
614 
615  for( i = 0; i < nlrowaggr->necaggr; ++i )
616  {
617  SCIPdebugMsg(scip, "print e.c. aggr %d\n", i);
618  ecaggrPrint(scip, nlrowaggr->ecaggr[i]);
619  }
620  return;
621 }
622 #endif
623 
624 /** creates separator data */
625 static
627  SCIP* scip, /**< SCIP data structure */
628  SCIP_SEPADATA** sepadata /**< pointer to store separator data */
629  )
630 {
631  assert(scip != NULL);
632  assert(sepadata != NULL);
633 
634  SCIP_CALL( SCIPallocBlockMemory(scip, sepadata) );
635  BMSclearMemory(*sepadata);
636 
637  return SCIP_OKAY;
638 }
639 
640 /** frees all nonlinear row aggregations */
641 static
643  SCIP* scip, /**< SCIP data structure */
644  SCIP_SEPADATA* sepadata /**< pointer to store separator data */
645  )
646 {
647  assert(scip != NULL);
648  assert(sepadata != NULL);
649 
650  /* free nonlinear row aggregations */
651  if( sepadata->nlrowaggrs != NULL )
652  {
653  int i;
654 
655  for( i = sepadata->nnlrowaggrs - 1; i >= 0; --i )
656  {
657  SCIP_CALL( nlrowaggrFree(scip, &sepadata->nlrowaggrs[i]) );
658  }
659 
660  SCIPfreeBlockMemoryArray(scip, &sepadata->nlrowaggrs, sepadata->nlrowaggrssize);
661 
662  sepadata->nlrowaggrs = NULL;
663  sepadata->nnlrowaggrs = 0;
664  sepadata->nlrowaggrssize = 0;
665  }
666 
667  return SCIP_OKAY;
668 }
669 
670 /** frees separator data */
671 static
673  SCIP* scip, /**< SCIP data structure */
674  SCIP_SEPADATA** sepadata /**< pointer to store separator data */
675  )
676 {
677  assert(scip != NULL);
678  assert(sepadata != NULL);
679  assert(*sepadata != NULL);
680 
681  /* free nonlinear row aggregations */
682  SCIP_CALL( sepadataFreeNlrows(scip, *sepadata) );
683 
684  /* free LP interface */
685  if( (*sepadata)->lpi != NULL )
686  {
687  SCIP_CALL( SCIPlpiFree(&((*sepadata)->lpi)) );
688  (*sepadata)->lpisize = 0;
689  }
690 
691  SCIPfreeBlockMemory(scip, sepadata);
692 
693  return SCIP_OKAY;
694 }
695 
696 /** adds a nonlinear row aggregation to the separator data */
697 static
699  SCIP* scip, /**< SCIP data structure */
700  SCIP_SEPADATA* sepadata, /**< separator data */
701  SCIP_NLROWAGGR* nlrowaggr /**< non-linear row aggregation */
702  )
703 {
704  int i;
705 
706  assert(scip != NULL);
707  assert(sepadata != NULL);
708  assert(nlrowaggr != NULL);
709 
710  if( sepadata->nlrowaggrssize == 0 )
711  {
712  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &sepadata->nlrowaggrs, 2) ); /*lint !e506*/
713  sepadata->nlrowaggrssize = 2;
714  }
715  else if( sepadata->nlrowaggrssize < sepadata->nnlrowaggrs + 1 )
716  {
717  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &sepadata->nlrowaggrs, sepadata->nlrowaggrssize, 2 * sepadata->nlrowaggrssize) ); /*lint !e506 !e647*/
718  sepadata->nlrowaggrssize *= 2;
719  assert(sepadata->nlrowaggrssize >= sepadata->nnlrowaggrs + 1);
720  }
721 
722  sepadata->nlrowaggrs[ sepadata->nnlrowaggrs ] = nlrowaggr;
723  ++(sepadata->nnlrowaggrs);
724 
725  /* update maximum e.c. aggregation size */
726  for( i = 0; i < nlrowaggr->necaggr; ++i )
727  sepadata->maxecsize = MAX(sepadata->maxecsize, nlrowaggr->ecaggr[i]->nvars);
728 
729 #ifdef SCIP_STATISTIC
730  /* update statistics */
731  if( nlrowaggr->rhsaggr )
732  ++(sepadata->nrhsnlrowaggrs);
733  else
734  ++(sepadata->nlhsnlrowaggrs);
735 #endif
736 
737  return SCIP_OKAY;
738 }
739 
740 /** returns min{val-lb,ub-val} / (ub-lb) */
741 static
742 SCIP_Real phi(
743  SCIP* scip, /**< SCIP data structure */
744  SCIP_Real val, /**< solution value */
745  SCIP_Real lb, /**< lower bound */
746  SCIP_Real ub /**< upper bound */
747  )
748 {
749  if( SCIPisFeasEQ(scip, lb, ub) )
750  return 0.0;
751 
752  /* adjust */
753  val = MAX(val, lb);
754  val = MIN(val, ub);
755 
756  return MIN(ub - val, val - lb) / (ub - lb);
757 }
758 
759 /** creates an MIP to search for cycles with an odd number of positive edges in the graph representation of a nonlinear
760  * row; the model uses directed binary arc flow variables; we introduce for all quadratic elements a forward and
761  * backward edge; if the term is quadratic (e.g., loop in the graph) we fix the corresponding variables to zero; this
762  * leads to an easy mapping of quadratic elements and the variables of the MIP
763  */
764 static
766  SCIP* scip, /**< SCIP data structure */
767  SCIP* subscip, /**< auxiliary SCIP to search aggregations */
768  SCIP_SEPADATA* sepadata, /**< separator data */
769  SCIP_NLROW* nlrow, /**< nonlinear row */
770  SCIP_Bool rhsaggr, /**< consider nonlinear row aggregation for g(x) <= rhs (TRUE) or
771  * lhs <= g(x) (FALSE) */
772  SCIP_VAR** forwardarcs, /**< array to store all forward arc variables */
773  SCIP_VAR** backwardarcs, /**< array to store all backward arc variables */
774  SCIP_Real* nodeweights, /**< weights for each node of the graph */
775  int* nedges /**< pointer to store the number of nonexcluded edges in the graph */
776  )
777 {
778  SCIP_VAR** oddcyclearcs;
779  SCIP_CONS** flowcons;
780  SCIP_CONS* cyclelengthcons;
781  SCIP_CONS* oddcyclecons;
782  char name[SCIP_MAXSTRLEN];
783  int noddcyclearcs;
784  int nnodes;
785  int narcs;
786  int i;
787 
788  assert(subscip != NULL);
789  assert(forwardarcs != NULL);
790  assert(backwardarcs != NULL);
791  assert(nedges != NULL);
792  assert(sepadata->minaggrsize <= sepadata->maxaggrsize);
793 
794  narcs = SCIPnlrowGetNQuadElems(nlrow);
795  nnodes = SCIPnlrowGetNQuadVars(nlrow);
796  *nedges = 0;
797 
798  assert(narcs > 0);
799  assert(nnodes > 0);
800 
801  noddcyclearcs = 0;
802  SCIP_CALL( SCIPallocBufferArray(subscip, &oddcyclearcs, 2*narcs) );
803 
804  /* create problem with default plug-ins */
805  SCIP_CALL( SCIPcreateProbBasic(subscip, "E.C. aggregation MIP") );
808 
809  /* create forward and backward arc variables; loops are fixed to zero */
810  for( i = 0; i < narcs; ++i )
811  {
812  SCIP_CONS* noparallelcons;
813  SCIP_QUADELEM* quadelem;
814  SCIP_Real edgeweight;
815  SCIP_Real ub;
816 
817  quadelem = &SCIPnlrowGetQuadElems(nlrow)[i];
818 
819  edgeweight = (quadelem->idx1 == quadelem->idx2) ? 0.0 : nodeweights[quadelem->idx1] + nodeweights[quadelem->idx2];
820  SCIPdebugMsg(scip, "edge {%d,%d} = {%s,%s} coeff=%e edgeweight=%e\n", quadelem->idx1, quadelem->idx2,
821  SCIPvarGetName(SCIPnlrowGetQuadVars(nlrow)[quadelem->idx1]),
822  SCIPvarGetName(SCIPnlrowGetQuadVars(nlrow)[quadelem->idx2]), quadelem->coef, edgeweight);
823 
824  ub = (quadelem->idx1 == quadelem->idx2) ? 0.0 : 1.0;
825 
826  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "x#%d#%d", quadelem->idx1, quadelem->idx2);
827  SCIP_CALL( SCIPcreateVarBasic(subscip, &forwardarcs[i], name, 0.0, ub, 0.01 + edgeweight, SCIP_VARTYPE_BINARY) );
828  SCIP_CALL( SCIPaddVar(subscip, forwardarcs[i]) );
829 
830  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "x#%d#%d", quadelem->idx2, quadelem->idx1);
831  SCIP_CALL( SCIPcreateVarBasic(subscip, &backwardarcs[i], name, 0.0, ub, 0.01 + edgeweight, SCIP_VARTYPE_BINARY) );
832  SCIP_CALL( SCIPaddVar(subscip, backwardarcs[i]) );
833 
834  /* do not create redundant constraints for loops */
835  if( quadelem->idx1 == quadelem->idx2 )
836  continue;
837 
838  ++(*nedges);
839 
840  /* store all arcs which are important for the odd cycle property (no loops) */
841  if( rhsaggr && SCIPisPositive(scip, quadelem->coef) )
842  {
843  oddcyclearcs[noddcyclearcs++] = forwardarcs[i];
844  oddcyclearcs[noddcyclearcs++] = backwardarcs[i];
845  }
846 
847  if( !rhsaggr && SCIPisNegative(scip, quadelem->coef) )
848  {
849  oddcyclearcs[noddcyclearcs++] = forwardarcs[i];
850  oddcyclearcs[noddcyclearcs++] = backwardarcs[i];
851  }
852 
853  /* add constraints to ensure no parallel edges */
854  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cons_noparalleledges");
855  SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &noparallelcons, name, 0, NULL, NULL, 0.0, 1.0) );
856  SCIP_CALL( SCIPaddCoefLinear(subscip, noparallelcons, forwardarcs[i], 1.0) );
857  SCIP_CALL( SCIPaddCoefLinear(subscip, noparallelcons, backwardarcs[i], 1.0) );
858  SCIP_CALL( SCIPaddCons(subscip, noparallelcons) );
859  SCIP_CALL( SCIPreleaseCons(subscip, &noparallelcons) );
860  }
861 
862  /* odd cycle property constraint */
863  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cons_oddcycle");
864  SCIP_CALL( SCIPcreateConsBasicXor(subscip, &oddcyclecons, name, TRUE, noddcyclearcs, oddcyclearcs) );
865  SCIP_CALL( SCIPaddCons(subscip, oddcyclecons) );
866  SCIP_CALL( SCIPreleaseCons(subscip, &oddcyclecons) );
867  SCIPfreeBufferArray(subscip, &oddcyclearcs);
868 
869  /* cycle length constraint */
870  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cons_cyclelength");
871  SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &cyclelengthcons, name, 0, NULL, NULL,
872  (SCIP_Real) sepadata->minaggrsize, (SCIP_Real) sepadata->maxaggrsize) );
873 
874  for( i = 0; i < narcs; ++i )
875  {
876  SCIP_CALL( SCIPaddCoefLinear(subscip, cyclelengthcons, forwardarcs[i], 1.0) );
877  SCIP_CALL( SCIPaddCoefLinear(subscip, cyclelengthcons, backwardarcs[i], 1.0) );
878  }
879 
880  SCIP_CALL( SCIPaddCons(subscip, cyclelengthcons) );
881  SCIP_CALL( SCIPreleaseCons(subscip, &cyclelengthcons) );
882 
883  /* create flow conservation constraints */
884  SCIP_CALL( SCIPallocBufferArray(subscip, &flowcons, nnodes) );
885 
886  for( i = 0; i < nnodes; ++i )
887  {
888  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cons_flowconservation#%d", i);
889  SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &flowcons[i], name, 0, NULL, NULL, 0.0, 0.0) );
890  }
891 
892  for( i = 0; i < narcs; ++i )
893  {
894  int u;
895  int v;
896 
897  u = SCIPnlrowGetQuadElems(nlrow)[i].idx1;
898  assert(u >= 0 && u < SCIPnlrowGetNQuadVars(nlrow));
899  v = SCIPnlrowGetQuadElems(nlrow)[i].idx2;
900  assert(v >= 0 && v < SCIPnlrowGetNQuadVars(nlrow));
901 
902  SCIP_CALL( SCIPaddCoefLinear(subscip, flowcons[u], forwardarcs[i], 1.0) );
903  SCIP_CALL( SCIPaddCoefLinear(subscip, flowcons[u], backwardarcs[i], -1.0) );
904 
905  SCIP_CALL( SCIPaddCoefLinear(subscip, flowcons[v], forwardarcs[i], -1.0) );
906  SCIP_CALL( SCIPaddCoefLinear(subscip, flowcons[v], backwardarcs[i], 1.0) );
907  }
908 
909  for( i = 0; i < nnodes; ++i )
910  {
911  SCIP_CALL( SCIPaddCons(subscip, flowcons[i]) );
912  SCIP_CALL( SCIPreleaseCons(subscip, &flowcons[i]) );
913  }
914 
915  SCIPfreeBufferArray(subscip, &flowcons);
916 
917  return SCIP_OKAY;
918 }
919 
920 /** fixed all arc variables (u,v) for which u or v is already in an edge-concave aggregation */
921 static
923  SCIP* subscip, /**< auxiliary SCIP to search aggregations */
924  SCIP_NLROW* nlrow, /**< nonlinear row */
925  SCIP_VAR** forwardarcs, /**< forward arc variables */
926  SCIP_VAR** backwardarcs, /**< backward arc variables */
927  int* quadvar2aggr, /**< mapping of quadvars to e.c. aggr. index (< 0: in no aggr.) */
928  int* nedges /**< pointer to store the number of nonexcluded edges */
929  )
930 {
931  int i;
932 
933  assert(subscip != NULL);
934  assert(nlrow != NULL);
935  assert(forwardarcs != NULL);
936  assert(backwardarcs != NULL);
937  assert(quadvar2aggr != NULL);
938  assert(nedges != NULL);
939 
940  SCIP_CALL( SCIPfreeTransform(subscip) );
941 
942  /* recompute the number of edges */
943  *nedges = 0;
944 
945  /* fix each arc to 0 if at least one of its nodes is contained in an e.c. aggregation */
946  for( i = 0; i < SCIPnlrowGetNQuadElems(nlrow); ++i )
947  {
948  SCIP_QUADELEM* quadelem;
949 
950  quadelem = &SCIPnlrowGetQuadElems(nlrow)[i];
951 
952  if( quadvar2aggr[quadelem->idx1] != -1 || quadvar2aggr[quadelem->idx2] != -1 )
953  {
954  SCIP_CALL( SCIPchgVarUb(subscip, forwardarcs[i], 0.0) );
955  SCIP_CALL( SCIPchgVarUb(subscip, backwardarcs[i], 0.0) );
956  }
957  else
958  *nedges += (quadelem->idx1 != quadelem->idx2) ? 1 : 0;
959  }
960 
961  return SCIP_OKAY;
962 }
963 
964 /** stores the best edge-concave aggregation found by the MIP model */
965 static
967  SCIP* subscip, /**< auxiliary SCIP to search aggregations */
968  SCIP_NLROW* nlrow, /**< nonlinear row */
969  SCIP_VAR** forwardarcs, /**< forward arc variables */
970  SCIP_VAR** backwardarcs, /**< backward arc variables */
971  int* quadvar2aggr, /**< mapping of quadvars to e.c. aggr. index (< 0: in no aggr.) */
972  int nfoundsofar /**< number of e.c. aggregation found so far */
973  )
974 {
975  SCIP_SOL* sol;
976  int i;
977 
978  assert(subscip != NULL);
979  assert(nlrow != NULL);
980  assert(forwardarcs != NULL);
981  assert(backwardarcs != NULL);
982  assert(quadvar2aggr != NULL);
983  assert(nfoundsofar >= 0);
984  assert(SCIPgetStatus(subscip) < SCIP_STATUS_INFEASIBLE);
985  assert(SCIPgetNSols(subscip) > 0);
986 
987  sol = SCIPgetBestSol(subscip);
988  assert(sol != NULL);
989 
990  for( i = 0; i < SCIPnlrowGetNQuadElems(nlrow); ++i )
991  {
992  SCIP_QUADELEM* quadelem;
993 
994  quadelem = &SCIPnlrowGetQuadElems(nlrow)[i];
995 
996  if( SCIPisGT(subscip, SCIPgetSolVal(subscip, sol, forwardarcs[i]), 0.5)
997  || SCIPisGT(subscip, SCIPgetSolVal(subscip, sol, backwardarcs[i]), 0.5) )
998  {
999  assert(quadvar2aggr[quadelem->idx1] == -1 || quadvar2aggr[quadelem->idx1] == nfoundsofar);
1000  assert(quadvar2aggr[quadelem->idx2] == -1 || quadvar2aggr[quadelem->idx2] == nfoundsofar);
1001 
1002  quadvar2aggr[quadelem->idx1] = nfoundsofar;
1003  quadvar2aggr[quadelem->idx2] = nfoundsofar;
1004  }
1005  }
1006 
1007  return SCIP_OKAY;
1008 }
1009 
1010 /** searches for edge-concave aggregations with an MIP model based on binary flow variables */
1011 static
1013  SCIP* subscip, /**< SCIP data structure */
1014  SCIP_Real timelimit, /**< time limit to solve the MIP */
1015  int nedges, /**< number of nonexcluded undirected edges */
1016  SCIP_Bool* aggrleft, /**< pointer to store if there might be a left aggregation */
1017  SCIP_Bool* found /**< pointer to store if we have found an aggregation */
1018  )
1019 {
1020  assert(subscip != NULL);
1021  assert(aggrleft != NULL);
1022  assert(found != NULL);
1023  assert(nedges >= 0);
1024 
1025  *aggrleft = TRUE;
1026  *found = FALSE;
1027 
1028  if( SCIPisLE(subscip, timelimit, 0.0) )
1029  return SCIP_OKAY;
1030 
1031  /* set working limits */
1032  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
1033  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/totalnodes", SUBSCIP_NODELIMIT) );
1034 
1035  /* set heuristics to aggressive */
1037 
1038  /* disable output to console in optimized mode, enable in SCIP's debug mode */
1039 #ifdef SCIP_DEBUG
1040  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
1041  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1) );
1042 #else
1043  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1044 #endif
1045 
1046  SCIP_CALL( SCIPsolve(subscip) );
1047 
1048  /* no more aggregation left if the MIP is infeasible */
1049  if( SCIPgetStatus(subscip) >= SCIP_STATUS_INFEASIBLE )
1050  {
1051  *found = FALSE;
1052  *aggrleft = FALSE;
1053  return SCIP_OKAY;
1054  }
1055 
1056  if( SCIPgetNSols(subscip) > 0 )
1057  {
1058  *found = TRUE;
1059  *aggrleft = TRUE;
1060 
1061 #ifdef SCIP_DEBUG
1062  if( SCIPgetNSols(subscip) > 0 )
1063  {
1064  SCIP_CALL( SCIPprintSol(subscip, SCIPgetBestSol(subscip), NULL , FALSE) );
1065  }
1066 #endif
1067  }
1068 
1069  return SCIP_OKAY;
1070 }
1071 
1072 /** creates a tclique graph from a given nonlinear row
1073  *
1074  * SCIP's clique code can only handle integer node weights; all node weights are scaled by a factor of 100; since the
1075  * clique code ignores nodes with weight of zero, we add an offset of 100 to each weight
1076  */
1077 static
1079  SCIP* scip, /**< SCIP data structure */
1080  SCIP_NLROW* nlrow, /**< nonlinear row */
1081  TCLIQUE_GRAPH** graph, /**< TCLIQUE graph structure */
1082  SCIP_Real* nodeweights /**< weights for each quadratic variable (nodes in the graph) */
1083  )
1084 {
1085  int i;
1086 
1087  assert(graph != NULL);
1088  assert(nlrow != NULL);
1089 
1090  /* create the tclique graph */
1091  if( !tcliqueCreate(graph) )
1092  {
1093  SCIPerrorMessage("could not create clique graph\n");
1094  return SCIP_ERROR;
1095  }
1096 
1097  /* add all nodes to the tclique graph */
1098  for( i = 0; i < SCIPnlrowGetNQuadVars(nlrow); ++i )
1099  {
1100  int nodeweight;
1101 
1102  /* note: clique code can only handle integer weights */
1103  nodeweight = 100 + (int)(100 * nodeweights[i]);
1104  /* SCIPdebugMsg(scip, "%d (%s): nodeweight %d \n", i, SCIPvarGetName(SCIPnlrowGetQuadVars(nlrow)[i]), nodeweight); */
1105 
1106  if( !tcliqueAddNode(*graph, i, nodeweight) )
1107  {
1108  SCIPerrorMessage("could not add node to clique graph\n");
1109  return SCIP_ERROR;
1110  }
1111  }
1112 
1113  /* add all edges */
1114  for( i = 0; i < SCIPnlrowGetNQuadElems(nlrow); ++i )
1115  {
1116  SCIP_QUADELEM* quadelem;
1117  SCIP_VAR* bilinvar1;
1118  SCIP_VAR* bilinvar2;
1119 
1120  quadelem = &SCIPnlrowGetQuadElems(nlrow)[i];
1121  assert(quadelem != NULL);
1122  assert(!SCIPisZero(scip, quadelem->coef));
1123 
1124  bilinvar1 = SCIPnlrowGetQuadVars(nlrow)[quadelem->idx1];
1125  bilinvar2 = SCIPnlrowGetQuadVars(nlrow)[quadelem->idx2];
1126  assert(bilinvar1 != NULL);
1127  assert(bilinvar2 != NULL);
1128 
1129  /* do not add the edge {i,i} */
1130  if( bilinvar1 == bilinvar2 )
1131  continue;
1132 
1133  assert(quadelem->idx1 != quadelem->idx2);
1134 
1135 #ifdef SCIP_DEBUG_DETAILED
1136  SCIPdebugMsg(scip, " add edge (%d, %d) = (%s,%s) to tclique graph\n",
1137  SCIPvarGetIndex(bilinvar1), SCIPvarGetIndex(bilinvar2),
1138  SCIPvarGetName(bilinvar1), SCIPvarGetName(bilinvar2));
1139 #endif
1140 
1141  if( !tcliqueAddEdge(*graph, quadelem->idx1, quadelem->idx2) )
1142  {
1143  SCIPerrorMessage("could not add edge to clique graph\n");
1144  return SCIP_ERROR;
1145  }
1146  }
1147 
1148  /* flush the clique graph */
1149  if( !tcliqueFlush(*graph) )
1150  {
1151  SCIPerrorMessage("could not flush the clique graph\n");
1152  return SCIP_ERROR;
1153  }
1154 
1155  return SCIP_OKAY;
1156 }
1157 
1158 /** searches for edge-concave aggregations by computing cliques in the graph representation of a given nonlinear row
1159  * update graph, compute clique, store clique; after computing a clique we heuristically check if the clique contains
1160  * at least one good cycle
1161  */
1162 static
1164  SCIP* scip, /**< SCIP data structure */
1165  TCLIQUE_GRAPH* graph, /**< TCLIQUE graph structure */
1166  SCIP_SEPADATA* sepadata, /**< separator data */
1167  SCIP_NLROW* nlrow, /**< nonlinear row */
1168  int* quadvar2aggr, /**< mapping of quadvars to e.c. aggr. index (< 0: in no aggr.) */
1169  int nfoundsofar, /**< number of e.c. aggregation found so far */
1170  SCIP_Bool rhsaggr, /**< consider nonlinear row aggregation for g(x) <= rhs (TRUE) or
1171  * lhs <= g(x) (FALSE) */
1172  SCIP_Bool* foundaggr, /**< pointer to store if we have found an aggregation */
1173  SCIP_Bool* foundclique /**< pointer to store if we have found a clique */
1174  )
1175 {
1176  SCIP_HASHMAP* cliquemap;
1177  TCLIQUE_STATUS status;
1178  int* maxcliquenodes;
1179  int* degrees;
1180  int nmaxcliquenodes;
1181  int maxcliqueweight;
1182  int noddcycleedges;
1183  int ntwodegrees;
1184  int aggrsize;
1185  int i;
1186 
1187  assert(graph != NULL);
1188  assert(nfoundsofar >= 0);
1189  assert(foundaggr != NULL);
1190  assert(foundclique != NULL);
1191  assert(SCIPnlrowGetNQuadVars(nlrow) == tcliqueGetNNodes(graph));
1192 
1193  cliquemap = NULL;
1194  *foundaggr = FALSE;
1195  *foundclique = FALSE;
1196 
1197  /* exclude all nodes which are already in an edge-concave aggregation (no flush is needed) */
1198  for( i = 0; i < SCIPnlrowGetNQuadVars(nlrow); ++i )
1199  {
1200  if( quadvar2aggr[i] != -1 )
1201  {
1202  SCIPdebugMsg(scip, "exclude node %d from clique graph\n", i);
1203  tcliqueChangeWeight(graph, i, 0);
1204  }
1205  }
1206 
1207  SCIP_CALL( SCIPallocBufferArray(scip, &maxcliquenodes, SCIPnlrowGetNQuadVars(nlrow)) );
1208 
1209  /* solve clique problem */
1210  tcliqueMaxClique(tcliqueGetNNodes, tcliqueGetWeights, tcliqueIsEdge, tcliqueSelectAdjnodes, graph, NULL, NULL,
1211  maxcliquenodes, &nmaxcliquenodes, &maxcliqueweight, CLIQUE_MAXFIRSTNODEWEIGHT, CLIQUE_MINWEIGHT,
1212  CLIQUE_MAXNTREENODES, CLIQUE_BACKTRACKFREQ, 0, -1, NULL, &status);
1213 
1214  if( status != TCLIQUE_OPTIMAL || nmaxcliquenodes < sepadata->minaggrsize )
1215  goto TERMINATE;
1216 
1217  *foundclique = TRUE;
1218  aggrsize = MIN(sepadata->maxaggrsize, nmaxcliquenodes);
1219  SCIP_CALL( SCIPhashmapCreate(&cliquemap, SCIPblkmem(scip), aggrsize) );
1220 
1221  for( i = 0; i < aggrsize; ++i )
1222  {
1223  SCIP_CALL( SCIPhashmapInsert(cliquemap, (void*) (size_t) maxcliquenodes[i], NULL) );
1224  }
1225 
1226  /* count the degree of good cycle edges for each node in the clique */
1227  SCIP_CALL( SCIPallocBufferArray(scip, &degrees, aggrsize) );
1228  BMSclearMemoryArray(degrees, aggrsize);
1229  ntwodegrees = 0;
1230 
1231  /* count the number of positive or negative edges (depending on <= rhs or >= lhs) */
1232  noddcycleedges = 0;
1233  for( i = 0; i < SCIPnlrowGetNQuadElems(nlrow); ++i )
1234  {
1235  SCIP_QUADELEM* quadelem;
1236  SCIP_Bool isoddcycleedge;
1237 
1238  quadelem = &SCIPnlrowGetQuadElems(nlrow)[i];
1239  isoddcycleedge = (rhsaggr && SCIPisPositive(scip, quadelem->coef))
1240  || (!rhsaggr && SCIPisNegative(scip, quadelem->coef));
1241 
1242  if( isoddcycleedge
1243  && SCIPhashmapExists(cliquemap, (void*) (size_t) quadelem->idx1)
1244  && SCIPhashmapExists(cliquemap, (void*) (size_t) quadelem->idx2) )
1245  {
1246  ++noddcycleedges;
1247  ++degrees[quadelem->idx1];
1248  ++degrees[quadelem->idx2];
1249  }
1250  }
1251 
1252  /* count the number of nodes with exactly two incident odd cycle edges */
1253  for( i = 0; i < aggrsize; ++i )
1254  if( degrees[i] == 2 )
1255  ++ntwodegrees;
1256 
1257  /* check cases for which we are sure that there are no good cycles in the clique */
1258  if( noddcycleedges == 0 || (aggrsize == 3 && noddcycleedges == 2) || (aggrsize == 4 && ntwodegrees == 4) )
1259  *foundaggr = FALSE;
1260  else
1261  *foundaggr = TRUE;
1262 
1263  /* add the found clique as an edge-concave aggregation or exclude the nodes from the remaining search */
1264  for( i = 0; i < aggrsize; ++i )
1265  {
1266  quadvar2aggr[ maxcliquenodes[i] ] = *foundaggr ? nfoundsofar : -2;
1267  SCIPdebugMsg(scip, "%s %d\n", *foundaggr ? "aggregate node: " : "exclude node: ", maxcliquenodes[i]);
1268  }
1269 
1270  SCIPfreeBufferArray(scip, &degrees);
1271 
1272 TERMINATE:
1273  if( cliquemap != NULL )
1274  SCIPhashmapFree(&cliquemap);
1275  SCIPfreeBufferArray(scip, &maxcliquenodes);
1276 
1277  return SCIP_OKAY;
1278 }
1279 
1280 /** helper function for searchEcAggr() */
1281 static
1283  SCIP* scip, /**< SCIP data structure */
1284  SCIP* subscip, /**< sub-SCIP data structure */
1285  SCIP_SEPADATA* sepadata, /**< separator data */
1286  SCIP_NLROW* nlrow, /**< nonlinear row */
1287  SCIP_SOL* sol, /**< current solution (might be NULL) */
1288  SCIP_Bool rhsaggr, /**< consider nonlinear row aggregation for g(x) <= rhs (TRUE) or g(x) >= lhs (FALSE) */
1289  int* quadvar2aggr, /**< array to store for each quadratic variable in which edge-concave
1290  * aggregation it is stored (< 0: in no aggregation); size has to be at
1291  * least SCIPnlrowGetNQuadVars(nlrow) */
1292  int* nfound /**< pointer to store the number of found e.c. aggregations */
1293  )
1294 {
1295  TCLIQUE_GRAPH* graph = NULL;
1296  SCIP_VAR** forwardarcs;
1297  SCIP_VAR** backwardarcs;
1298  SCIP_VAR** quadvars;
1299  SCIP_Real* nodeweights;
1300  SCIP_Real timelimit;
1301  SCIP_RETCODE retcode;
1302  int nunsucces = 0;
1303  int nedges = 0;
1304  int nquadelems;
1305  int nquadvars;
1306  int i;
1307 
1308  assert(subscip != NULL);
1309  assert(quadvar2aggr != NULL);
1310  assert(nfound != NULL);
1311 
1312  quadvars = SCIPnlrowGetQuadVars(nlrow);
1313  nquadvars = SCIPnlrowGetNQuadVars(nlrow);
1314  nquadelems = SCIPnlrowGetNQuadElems(nlrow);
1315 
1316  retcode = SCIP_OKAY;
1317  *nfound = 0;
1318 
1319  /* arrays to store all arc variables of the MIP model; note that we introduce variables even for loops in the graph
1320  * to have an easy mapping from the edges of the graph to the quadratic elements
1321  */
1322  SCIP_CALL( SCIPallocBufferArray(scip, &nodeweights, nquadvars) );
1323  SCIP_CALL( SCIPallocBufferArray(scip, &forwardarcs, nquadelems) );
1324  SCIP_CALL( SCIPallocBufferArray(scip, &backwardarcs, nquadelems) );
1325 
1326  /* inititialize mapping from quadvars to e.c. aggregation index (-1: quadvar is in no aggregation); compute node
1327  * weights
1328  */
1329  for( i = 0; i < SCIPnlrowGetNQuadVars(nlrow); ++i )
1330  {
1331  SCIP_VAR* var = quadvars[i];
1332  quadvar2aggr[i] = -1;
1333  nodeweights[i] = phi(scip, SCIPgetSolVal(scip, sol, var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var) );
1334  SCIPdebugMsg(scip, "%s = %e (%e in [%e, %e])\n", SCIPvarGetName(var), nodeweights[i], SCIPgetSolVal(scip, sol, var),
1336  }
1337 
1338  SCIP_CALL( createMIP(scip, subscip, sepadata, nlrow, rhsaggr, forwardarcs, backwardarcs, nodeweights, &nedges) );
1339  assert(nedges >= 0);
1340  SCIPdebugMsg(scip, "nedges (without loops) = %d\n", nedges);
1341 
1342  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1343 
1344  /* main loop to search for edge-concave aggregations */
1345  while( !SCIPisStopped(scip) )
1346  {
1347  SCIP_Bool aggrleft;
1348  SCIP_Bool found;
1349 
1350  SCIPdebugMsg(scip, "#remaining edges = %d\n", nedges);
1351 
1352  /* not enough edges left */
1353  if( nedges < sepadata->minaggrsize )
1354  break;
1355 
1356  /* check whether there is enough time left; update the remaining time */
1357  if( !SCIPisInfinity(scip, timelimit) )
1358  {
1359  timelimit -= SCIPgetSolvingTime(scip);
1360  if( timelimit <= 0.0 )
1361  {
1362  SCIPdebugMsg(scip, "skip aggregation search since no time left\n");
1363  goto TERMINATE;
1364  }
1365  }
1366 
1367  /* 1.a - search for edge-concave aggregation with the help of the MIP model */
1368  SCIP_CALL( searchEcAggrWithMIP(subscip, timelimit, nedges, &aggrleft, &found) );
1369 
1370  /* 1.b - there are no more edge-concave aggregations left */
1371  if( !aggrleft )
1372  {
1373  SCIPdebugMsg(scip, "no more aggregation left\n");
1374  break;
1375  }
1376 
1377  if( found )
1378  {
1379  SCIP_CALL( storeAggrFromMIP(subscip, nlrow, forwardarcs, backwardarcs, quadvar2aggr, *nfound) );
1380  ++(*nfound);
1381  nunsucces = 0;
1382  }
1383  /* try to find an edge-concave aggregation by computing cliques */
1384  else
1385  {
1386  SCIP_Bool foundaggr;
1387  SCIP_Bool foundclique;
1388 
1389  ++nunsucces;
1390 
1391  /* create graph if necessary */
1392  if( graph == NULL )
1393  {
1394  SCIP_CALL_TERMINATE( retcode, createTcliqueGraph(scip, nlrow, &graph, nodeweights), TERMINATE );
1395  }
1396 
1397  /* 2.a - search and store a single edge-concave aggregation by computing a clique with a good cycle */
1398  SCIP_CALL_FINALLY( searchEcAggrWithCliques(scip, graph, sepadata, nlrow, quadvar2aggr, *nfound, rhsaggr,
1399  &foundaggr, &foundclique), tcliqueFree(&graph) );
1400 
1401  if( foundaggr )
1402  {
1403  assert(foundclique);
1404  ++(*nfound);
1405  nunsucces = 0;
1406  }
1407  else
1408  ++nunsucces;
1409 
1410  /* 2.b - no clique of at least minaggrsize size found */
1411  if( !foundclique )
1412  {
1413  assert(!foundaggr);
1414  SCIPdebugMsg(scip, "did not find a clique to exclude -> leave aggregation search\n");
1415  break;
1416  }
1417  }
1418 
1419  /* leave the algorithm if we did not find something for maxstallrounds many iterations */
1420  if( nunsucces >= sepadata->maxstallrounds && *nfound == 0 )
1421  {
1422  SCIPdebugMsg(scip, "did not find an e.c. aggregation for %d iterations\n", nunsucces);
1423  break;
1424  }
1425 
1426  /* exclude all edges used in the last aggregation and nodes found in the clique solution */
1427  SCIP_CALL_FINALLY( updateMIP(subscip, nlrow, forwardarcs, backwardarcs, quadvar2aggr, &nedges), tcliqueFree(&graph) );
1428  }
1429 
1430 TERMINATE:
1431 
1432 #ifdef SCIP_DEBUG
1433  SCIPdebugMsg(scip, "aggregations found:\n");
1434  for( i = 0; i < nquadvars; ++i )
1435  {
1436  SCIPdebugMsg(scip, " %d in %d\n", i, quadvar2aggr[i]);
1437  }
1438 #endif
1439 
1440  /* free clique graph */
1441  if( graph != NULL )
1442  tcliqueFree(&graph);
1443 
1444  /* free sub-SCIP */
1445  for( i = 0; i < nquadelems; ++i )
1446  {
1447  SCIP_CALL( SCIPreleaseVar(subscip, &forwardarcs[i]) );
1448  SCIP_CALL( SCIPreleaseVar(subscip, &backwardarcs[i]) );
1449  }
1450 
1451  SCIPfreeBufferArray(scip, &backwardarcs);
1452  SCIPfreeBufferArray(scip, &forwardarcs);
1453  SCIPfreeBufferArray(scip, &nodeweights);
1454 
1455  return retcode;
1456 }
1457 
1458 /** computes a partitioning into edge-concave aggregations for a given (quadratic) nonlinear row; each aggregation has
1459  * to contain a cycle with an odd number of positive weighted edges (good cycles) in the corresponding graph representation
1460  *
1461  * For this we use the following algorithm:
1462  *
1463  * -# use a MIP model based on binary flow variables to compute good cycles and store the implied subgraphs as an e.c. aggr.
1464  * -# if we find a good cycle, store the implied subgraph, delete it from the graph representation and go to 1)
1465  * -# if the MIP model is infeasible (there are no good cycles), STOP
1466  * -# we compute a large clique C if the MIP model fails (because of working limits, etc)
1467  * -# if we find a good cycle in C, store the implied subgraph of C, delete it from the graph representation and go to 1)
1468  * -# if C is not large enough, STOP
1469  */
1470 static
1472  SCIP* scip, /**< SCIP data structure */
1473  SCIP_SEPADATA* sepadata, /**< separator data */
1474  SCIP_NLROW* nlrow, /**< nonlinear row */
1475  SCIP_SOL* sol, /**< current solution (might be NULL) */
1476  SCIP_Bool rhsaggr, /**< consider nonlinear row aggregation for g(x) <= rhs (TRUE) or g(x) >= lhs (FALSE) */
1477  int* quadvar2aggr, /**< array to store for each quadratic variable in which edge-concave
1478  * aggregation it is stored (< 0: in no aggregation); size has to be at
1479  * least SCIPnlrowGetNQuadVars(nlrow) */
1480  int* nfound /**< pointer to store the number of found e.c. aggregations */
1481  )
1482 {
1483  SCIP* subscip;
1484  SCIP_RETCODE retcode;
1485 
1486  /* create and set up a sub-SCIP */
1487  SCIP_CALL_FINALLY( SCIPcreate(&subscip), (void)SCIPfree(&subscip) );
1488 
1489  retcode = doSeachEcAggr(scip, subscip, sepadata, nlrow, sol, rhsaggr, quadvar2aggr, nfound);
1490 
1491  SCIP_CALL( SCIPfree(&subscip) );
1492  SCIP_CALL( retcode );
1493 
1494  return SCIP_OKAY;
1495 }
1496 
1497 /** returns whether a given nonlinear row can be used to compute edge-concave aggregations for which their convex
1498  * envelope could dominate the termwise bilinear relaxation; this is the case if there exists at least one cycle with
1499  * an odd number of positive edges in the corresponding graph representation of the nonlinear row
1500  */
1501 static
1503  SCIP* scip, /**< SCIP data structure */
1504  SCIP_SEPADATA* sepadata, /**< separator data */
1505  SCIP_NLROW* nlrow, /**< nonlinear row representation of a nonlinear constraint */
1506  SCIP_Bool* rhscandidate, /**< pointer to store if we should compute edge-concave aggregations for
1507  * the <= rhs case */
1508  SCIP_Bool* lhscandidate /**< pointer to store if we should compute edge-concave aggregations for
1509  * the >= lhs case */
1510  )
1511 {
1512  int* degrees;
1513  int ninterestingnodes;
1514  int nposedges;
1515  int nnegedges;
1516  int i;
1517 
1518  assert(rhscandidate != NULL);
1519  assert(lhscandidate != NULL);
1520 
1521  *rhscandidate = TRUE;
1522  *lhscandidate = TRUE;
1523 
1524  /* skip if the nlrow is not in the NLP, there are other nonlinearities, or too few quadratic variables */
1525  if( !SCIPnlrowIsInNLP(nlrow) || SCIPnlrowGetExprtree(nlrow) != NULL
1526  || SCIPnlrowGetNQuadVars(nlrow) < sepadata->minaggrsize )
1527  {
1528  *rhscandidate = FALSE;
1529  *lhscandidate = FALSE;
1530  return SCIP_OKAY;
1531  }
1532 
1533  /* check for infinite rhs or lhs */
1534  if( SCIPisInfinity(scip, REALABS(SCIPnlrowGetRhs(nlrow))) )
1535  *rhscandidate = FALSE;
1536  if( SCIPisInfinity(scip, REALABS(SCIPnlrowGetLhs(nlrow))) )
1537  *lhscandidate = FALSE;
1538 
1539  SCIP_CALL( SCIPallocBufferArray(scip, &degrees, SCIPnlrowGetNQuadVars(nlrow)) );
1540  BMSclearMemoryArray(degrees, SCIPnlrowGetNQuadVars(nlrow));
1541 
1542  ninterestingnodes = 0;
1543  nposedges = 0;
1544  nnegedges = 0;
1545 
1546  for( i = 0; i < SCIPnlrowGetNQuadElems(nlrow); ++i )
1547  {
1548  SCIP_QUADELEM* quadelem;
1549  SCIP_VAR* x;
1550  SCIP_VAR* y;
1551 
1552  quadelem = &SCIPnlrowGetQuadElems(nlrow)[i];
1553  x = SCIPnlrowGetQuadVars(nlrow)[quadelem->idx1];
1554  y = SCIPnlrowGetQuadVars(nlrow)[quadelem->idx2];
1555 
1556  /* do not consider loops or global fixed variables */
1557  if( quadelem->idx1 != quadelem->idx2
1559  && !SCIPisEQ(scip, SCIPvarGetLbGlobal(y), SCIPvarGetUbGlobal(y)) )
1560  {
1561  ++degrees[quadelem->idx1];
1562  ++degrees[quadelem->idx2];
1563 
1564  /* count the number of nodes with a degree of at least 2 */
1565  if( degrees[quadelem->idx1] == 2 )
1566  ++ninterestingnodes;
1567  if( degrees[quadelem->idx2] == 2 )
1568  ++ninterestingnodes;
1569 
1570  nposedges += SCIPisPositive(scip, quadelem->coef) ? 1 : 0;
1571  nnegedges += SCIPisNegative(scip, quadelem->coef) ? 1 : 0;
1572  }
1573  }
1574 
1575  SCIPfreeBufferArray(scip, &degrees);
1576 
1577  SCIPdebugMsg(scip, "nlrow contains: %d edges\n", nposedges + nnegedges);
1578 
1579  /* too many edges, too few edges, or to few nodes with degree at least 2 in the graph */
1580  if( nposedges + nnegedges > sepadata->maxbilinterms || nposedges + nnegedges < sepadata->minaggrsize
1581  || ninterestingnodes < sepadata->minaggrsize )
1582  {
1583  *rhscandidate = FALSE;
1584  *lhscandidate = FALSE;
1585  return SCIP_OKAY;
1586  }
1587 
1588  /* check if there are enough positive/negative edges; for a 3-clique there has to be an odd number of those edges */
1589  if( nposedges == 0 || (nposedges + nnegedges == 3 && (nposedges % 2) == 0) )
1590  *rhscandidate = FALSE;
1591  if( nnegedges == 0 || (nposedges + nnegedges == 3 && (nnegedges % 2) == 0) )
1592  *lhscandidate = FALSE;
1593 
1594  return SCIP_OKAY;
1595 }
1596 
1597 /** finds and stores edge-concave aggregations for a given nonlinear row */
1598 static
1600  SCIP* scip, /**< SCIP data structure */
1601  SCIP_SEPADATA* sepadata, /**< separator data */
1602  SCIP_NLROW* nlrow, /**< nonlinear row */
1603  SCIP_SOL* sol /**< current solution (might be NULL) */
1604  )
1605 {
1606  int* quadvar2aggr;
1607  SCIP_Bool rhscandidate;
1608  SCIP_Bool lhscandidate;
1609 
1610  assert(scip != NULL);
1611  assert(nlrow != NULL);
1612  assert(sepadata != NULL);
1613 
1614  SCIP_CALL( SCIPallocBufferArray(scip, &quadvar2aggr, SCIPnlrowGetNQuadVars(nlrow)) ); /*lint !e705*/
1615 
1616 #ifdef SCIP_DEBUG
1617  SCIPdebugMsg(scip, "search for edge-concave aggregation for the nonlinear row: \n");
1618  SCIP_CALL( SCIPnlrowPrint(nlrow, SCIPgetMessagehdlr(scip), NULL) );
1619 #endif
1620 
1621  /* check obvious conditions for existing cycles with an odd number of positive/negative edges */
1622  SCIP_CALL( isCandidate(scip, sepadata, nlrow, &rhscandidate, &lhscandidate) );
1623  SCIPdebugMsg(scip, "rhs candidate = %u lhs candidate = %u\n", rhscandidate, lhscandidate);
1624 
1625  /* search for edge-concave aggregations (consider <= rhs) */
1626  if( rhscandidate )
1627  {
1628  SCIP_NLROWAGGR* nlrowaggr;
1629  int nfound;
1630 
1631  assert(!SCIPisInfinity(scip, REALABS(SCIPnlrowGetRhs(nlrow))));
1632 
1633  SCIPdebugMsg(scip, "consider <= rhs\n");
1634  SCIP_CALL( searchEcAggr(scip, sepadata, nlrow, sol, TRUE, quadvar2aggr, &nfound) );
1635 
1636  if( nfound > 0 )
1637  {
1638  SCIP_CALL( nlrowaggrCreate(scip, nlrow, &nlrowaggr, quadvar2aggr, nfound, TRUE) );
1639  assert(nlrow != NULL);
1640  SCIPdebug(nlrowaggrPrint(scip, nlrowaggr));
1641  SCIP_CALL( sepadataAddNlrowaggr(scip, sepadata, nlrowaggr) );
1642  }
1643  }
1644 
1645  /* search for edge-concave aggregations (consider <= lhs) */
1646  if( lhscandidate )
1647  {
1648  SCIP_NLROWAGGR* nlrowaggr;
1649  int nfound;
1650 
1651  assert(!SCIPisInfinity(scip, REALABS(SCIPnlrowGetLhs(nlrow))));
1652 
1653  SCIPdebugMsg(scip, "consider >= lhs\n");
1654  SCIP_CALL( searchEcAggr(scip, sepadata, nlrow, sol, FALSE, quadvar2aggr, &nfound) );
1655 
1656  if( nfound > 0 )
1657  {
1658  SCIP_CALL( nlrowaggrCreate(scip, nlrow, &nlrowaggr, quadvar2aggr, nfound, FALSE) );
1659  assert(nlrow != NULL);
1660  SCIPdebug(nlrowaggrPrint(scip, nlrowaggr));
1661  SCIP_CALL( sepadataAddNlrowaggr(scip, sepadata, nlrowaggr) );
1662  }
1663  }
1664 
1665  SCIPfreeBufferArray(scip, &quadvar2aggr);
1666  return SCIP_OKAY;
1667 }
1668 
1669 /*
1670  * methods to compute edge-concave cuts
1671  */
1672 
1673 #ifdef SCIP_DEBUG
1674 /** prints a given facet (candidate) */
1675 static
1676 void printFacet(
1677  SCIP* scip, /**< SCIP data structure */
1678  SCIP_VAR** vars, /**< variables contained in the edge-concave aggregation */
1679  int nvars, /**< number of variables contained in the edge-concave aggregation */
1680  SCIP_Real* facet, /**< current facet candidate */
1681  SCIP_Real facetval /**< facet evaluated at the current solution */
1682  )
1683 {
1684  int i;
1685 
1686  SCIPdebugMsg(scip, "print facet (val=%e): ", facetval);
1687  for( i = 0; i < nvars; ++i )
1688  SCIPdebugMsgPrint(scip, "%e %s + ", facet[i], SCIPvarGetName(vars[i]));
1689  SCIPdebugMsgPrint(scip, "%e\n", facet[nvars]);
1690 }
1691 #endif
1692 
1693 /** checks if a facet is really an underestimate for all corners of the domain [l,u]; because of numerics it can happen
1694  * that a facet violates a corner of the domain; to make the facet valid we subtract the maximum violation from the
1695  * constant part of the facet; its a good excersise to write a comment describing the gray code...
1696  */
1697 static
1699  SCIP* scip, /**< SCIP data structure */
1700  SCIP_ECAGGR* ecaggr, /**< edge-concave aggregation data */
1701  SCIP_Real* fvals, /**< array containing all corner values of the aggregation */
1702  SCIP_Real* facet /**< current facet candidate (of dimension ecaggr->nvars + 1) */
1703  )
1704 {
1705  SCIP_Real maxviolation;
1706  SCIP_Real val;
1707  unsigned int i;
1708  unsigned int ncorner;
1709  unsigned int prev;
1710 
1711  assert(scip != NULL);
1712  assert(ecaggr != NULL);
1713  assert(fvals != NULL);
1714  assert(facet != NULL);
1715 
1716  ncorner = (unsigned int) poweroftwo[ecaggr->nvars];
1717  maxviolation = 0.0;
1718 
1719  /* check for the origin */
1720  val = facet[ecaggr->nvars];
1721  for( i = 0; i < (unsigned int) ecaggr->nvars; ++i )
1722  val += facet[i] * SCIPvarGetLbLocal(ecaggr->vars[i]);
1723 
1724  /* update maximum violation */
1725  maxviolation = MAX(val - fvals[0], maxviolation);
1726  assert(SCIPisFeasEQ(scip, maxviolation, 0.0));
1727 
1728  prev = 0;
1729  for( i = 1; i < ncorner; ++i )
1730  {
1731  unsigned int gray;
1732  unsigned int diff;
1733  unsigned int pos;
1734 
1735  gray = i ^ (i >> 1);
1736  diff = gray ^ prev;
1737 
1738  /* compute position of unique 1 of diff */
1739  pos = 0;
1740  while( (diff >>= 1) != 0 )
1741  ++pos;
1742 
1743  if( gray > prev )
1744  val += facet[pos] * (SCIPvarGetUbLocal(ecaggr->vars[pos]) - SCIPvarGetLbLocal(ecaggr->vars[pos]));
1745  else
1746  val -= facet[pos] * (SCIPvarGetUbLocal(ecaggr->vars[pos]) - SCIPvarGetLbLocal(ecaggr->vars[pos]));
1747 
1748  /* update maximum violation */
1749  maxviolation = MAX(val - fvals[gray], maxviolation);
1750  assert(SCIPisFeasEQ(scip, maxviolation, 0.0));
1751 
1752  prev = gray;
1753  }
1754 
1755  SCIPdebugMsg(scip, "maximum violation of facet: %2.8e\n", maxviolation);
1756 
1757  /* there seem to be numerical problems if the violation is too large; in this case we reject the facet */
1758  if( maxviolation > ADJUSTFACETTOL )
1759  return FALSE;
1760 
1761  /* adjust constant part of the facet */
1762  facet[ecaggr->nvars] -= maxviolation;
1763 
1764  return TRUE;
1765 }
1766 
1767 /** set up LP interface to solve LPs to compute the facet of the convex envelope */
1768 static
1770  SCIP* scip, /**< SCIP data structure */
1771  SCIP_SEPADATA* sepadata /**< separation data */
1772  )
1773 {
1774  SCIP_Real* obj;
1775  SCIP_Real* lb;
1776  SCIP_Real* ub;
1777  SCIP_Real* val;
1778  int* beg;
1779  int* ind;
1780  int nnonz;
1781  int ncols;
1782  int nrows;
1783  int i;
1784  int k;
1785 
1786  assert(scip != NULL);
1787  assert(sepadata != NULL);
1788  assert(sepadata->nnlrowaggrs > 0);
1789 
1790  /* LP interface has been already created with enough rows/columns*/
1791  if( sepadata->lpi != NULL && sepadata->lpisize >= sepadata->maxecsize )
1792  return SCIP_OKAY;
1793 
1794  /* size of lpi is too small; reconstruct lpi */
1795  if( sepadata->lpi != NULL )
1796  {
1797  SCIP_CALL( SCIPlpiFree(&sepadata->lpi) );
1798  sepadata->lpi = NULL;
1799  }
1800 
1801  assert(sepadata->lpi == NULL);
1802  SCIP_CALL( SCIPlpiCreate(&(sepadata->lpi), SCIPgetMessagehdlr(scip), "e.c. LP", SCIP_OBJSEN_MINIMIZE) );
1803  sepadata->lpisize = sepadata->maxecsize;
1804 
1805  nrows = sepadata->maxecsize + 1;
1806  ncols = poweroftwo[nrows - 1];
1807  nnonz = (ncols * (nrows + 1)) / 2;
1808  k = 0;
1809 
1810  /* allocate necessary memory */
1811  SCIP_CALL( SCIPallocBufferArray(scip, &obj, ncols) );
1812  SCIP_CALL( SCIPallocBufferArray(scip, &lb, ncols) );
1813  SCIP_CALL( SCIPallocBufferArray(scip, &ub, ncols) );
1814  SCIP_CALL( SCIPallocBufferArray(scip, &beg, ncols) );
1815  SCIP_CALL( SCIPallocBufferArray(scip, &val, nnonz) );
1816  SCIP_CALL( SCIPallocBufferArray(scip, &ind, nnonz) );
1817 
1818  /* calculate nonzero entries in the LP; set obj, lb, and ub to zero */
1819  for( i = 0; i < ncols; ++i )
1820  {
1821  int row;
1822  int a;
1823 
1824  obj[i] = 0.0;
1825  lb[i] = 0.0;
1826  ub[i] = 0.0;
1827 
1828  SCIPdebugMsg(scip, "col %i starts at position %d\n", i, k);
1829  beg[i] = k;
1830  row = 0;
1831  a = 1;
1832 
1833  /* iterate through the bit representation of i */
1834  while( a <= i )
1835  {
1836  if( (a & i) != 0 )
1837  {
1838  val[k] = 1.0;
1839  ind[k] = row;
1840 
1841  SCIPdebugMsg(scip, " val[%d][%d] = 1 (position %d)\n", row, i, k);
1842 
1843  ++k;
1844  }
1845 
1846  a <<= 1; /*lint !e701*/
1847  ++row;
1848  assert(poweroftwo[row] == a);
1849  }
1850 
1851  /* put 1 as a coefficient for sum_{i} \lambda_i = 1 row (last row) */
1852  val[k] = 1.0;
1853  ind[k] = nrows - 1;
1854  ++k;
1855  SCIPdebugMsg(scip, " val[%d][%d] = 1 (position %d)\n", nrows - 1, i, k);
1856  }
1857  assert(k == nnonz);
1858 
1859  /*
1860  * add all columns to the LP interface
1861  * CPLEX needs the row to exist before adding columns, so we create the rows with dummy sides
1862  * note that the assert is not needed once somebody fixes the LPI
1863  */
1864  assert(nrows <= ncols);
1865  SCIP_CALL( SCIPlpiAddRows(sepadata->lpi, nrows, obj, obj, NULL, 0, NULL, NULL, NULL) );
1866  SCIP_CALL( SCIPlpiAddCols(sepadata->lpi, ncols, obj, lb, ub, NULL, nnonz, beg, ind, val) );
1867 
1868  /* free allocated memory */
1869  SCIPfreeBufferArray(scip, &ind);
1870  SCIPfreeBufferArray(scip, &val);
1871  SCIPfreeBufferArray(scip, &beg);
1872  SCIPfreeBufferArray(scip, &ub);
1873  SCIPfreeBufferArray(scip, &lb);
1874  SCIPfreeBufferArray(scip, &obj);
1875 
1876  return SCIP_OKAY;
1877 }
1878 
1879 /** evaluates an edge-concave aggregation at a corner of the domain [l,u] */
1880 static
1882  SCIP_ECAGGR* ecaggr, /**< edge-concave aggregation data */
1883  int k /**< k-th corner */
1884  )
1885 {
1886  SCIP_Real val;
1887  int i;
1888 
1889  assert(ecaggr != NULL);
1890  assert(k >= 0 && k < poweroftwo[ecaggr->nvars]);
1891 
1892  val = 0.0;
1893 
1894  for( i = 0; i < ecaggr->nterms; ++i )
1895  {
1896  SCIP_Real coef;
1897  SCIP_Real bound1;
1898  SCIP_Real bound2;
1899  int idx1;
1900  int idx2;
1901 
1902  idx1 = ecaggr->termvars1[i];
1903  idx2 = ecaggr->termvars2[i];
1904  coef = ecaggr->termcoefs[i];
1905  assert(idx1 >= 0 && idx1 < ecaggr->nvars);
1906  assert(idx2 >= 0 && idx2 < ecaggr->nvars);
1907 
1908  bound1 = ((poweroftwo[idx1]) & k) == 0 ? SCIPvarGetLbLocal(ecaggr->vars[idx1]) : SCIPvarGetUbLocal(ecaggr->vars[idx1]);
1909  bound2 = ((poweroftwo[idx2]) & k) == 0 ? SCIPvarGetLbLocal(ecaggr->vars[idx2]) : SCIPvarGetUbLocal(ecaggr->vars[idx2]);
1910 
1911  val += coef * bound1 * bound2;
1912  }
1913 
1914  return val;
1915 }
1916 
1917 /** returns (val - lb) / (ub - lb) for a in [lb, ub] */
1918 static
1920  SCIP* scip, /**< SCIP data structure */
1921  SCIP_Real lb, /**< lower bound */
1922  SCIP_Real ub, /**< upper bound */
1923  SCIP_Real val /**< value in [lb,ub] */
1924  )
1925 {
1926  assert(scip != NULL);
1927  assert(!SCIPisInfinity(scip, -lb));
1928  assert(!SCIPisInfinity(scip, ub));
1929  assert(!SCIPisInfinity(scip, REALABS(val)));
1930  assert(!SCIPisFeasEQ(scip, ub - lb, 0.0)); /* this would mean that a variable has been fixed */
1931 
1932  /* adjust val */
1933  val = MIN(val, ub);
1934  val = MAX(val, lb);
1935 
1936  val = (val - lb) / (ub - lb);
1937  assert(val >= 0.0 && val <= 1.0);
1938 
1939  return val;
1940 }
1941 
1942 /** computes a facet of the convex envelope of an edge concave aggregation
1943  *
1944  * The algorithm solves the following LP:
1945  * \f{eqnarray}{
1946  * min & \sum_i \lambda_i f(v_i)\\
1947  * s.t. & \sum_i \lambda_i v_i = x\\
1948  * & \sum_i \lambda_i = 1\\
1949  * & \lambda_i \geq 0
1950  * \f}
1951  * where f is an edge concave function, \f$x\f$ in \f$[l,u]\f$ is a solution of the current relaxation, and \f$v_i\f$ are the vertices
1952  * of \f$[l,u]\f$; the method transforms the problem to the domain \f$[0,1]^n\f$, computes a facet, and transforms this facet to the
1953  * original space; the dual solution of the LP above are the coefficients of the facet
1954  *
1955  * The complete algorithm works as follows:
1956  *
1957  * -# compute f(v_i) for each corner v_i of [l,u]
1958  * -# set up the described LP for the transformed space
1959  * -# solve the LP and store the resulting facet for the transformed space
1960  * -# transform the facet to original space
1961  * -# adjust and check facet with the algorithm of Rikun et al.
1962  */
1963 static
1965  SCIP* scip, /**< SCIP data structure */
1966  SCIP_SEPADATA* sepadata, /**< separation data */
1967  SCIP_SOL* sol, /**< solution (might be NULL) */
1968  SCIP_ECAGGR* ecaggr, /**< edge-concave aggregation data */
1969  SCIP_Real* facet, /**< array to store the coefficients of the resulting facet; size has to be at least (ecaggr->nvars + 1) */
1970  SCIP_Real* facetval, /**< pointer to store the value of the facet evaluated at the current solution */
1971  SCIP_Bool* success /**< pointer to store if we have found a facet */
1972  )
1973 {
1974  SCIP_Real* fvals;
1975  SCIP_Real* side;
1976  SCIP_Real* lb;
1977  SCIP_Real* ub;
1978  SCIP_Real perturbation;
1979  int* inds;
1980  int ncorner;
1981  int ncols;
1982  int nrows;
1983  int i;
1984 
1985  assert(scip != NULL);
1986  assert(sepadata != NULL);
1987  assert(ecaggr != NULL);
1988  assert(facet != NULL);
1989  assert(facetval != NULL);
1990  assert(success != NULL);
1991  assert(ecaggr->nvars <= sepadata->maxecsize);
1992 
1993  *facetval = -SCIPinfinity(scip);
1994  *success = FALSE;
1995 
1996  /* create LP if this has not been done yet */
1997  SCIP_CALL( createLP(scip, sepadata) );
1998 
1999  assert(sepadata->lpi != NULL);
2000  assert(sepadata->lpisize >= ecaggr->nvars);
2001 
2002  SCIP_CALL( SCIPlpiGetNCols(sepadata->lpi, &ncols) );
2003  SCIP_CALL( SCIPlpiGetNRows(sepadata->lpi, &nrows) );
2004  ncorner = poweroftwo[ecaggr->nvars];
2005 
2006  assert(ncorner <= ncols);
2007  assert(ecaggr->nvars + 1 <= nrows);
2008  assert(nrows <= ncols);
2009 
2010  /* allocate necessary memory */
2011  SCIP_CALL( SCIPallocBufferArray(scip, &fvals, ncols) );
2012  SCIP_CALL( SCIPallocBufferArray(scip, &inds, ncols) );
2013  SCIP_CALL( SCIPallocBufferArray(scip, &lb, ncols) );
2014  SCIP_CALL( SCIPallocBufferArray(scip, &ub, ncols) );
2015  SCIP_CALL( SCIPallocBufferArray(scip, &side, ncols) );
2016 
2017  /*
2018  * 1. compute f(v_i) for each corner v_i of [l,u]
2019  * 2. set up the described LP for the transformed space
2020  */
2021  for( i = 0; i < ncols; ++i )
2022  {
2023  fvals[i] = i < ncorner ? evalCorner(ecaggr, i) : 0.0;
2024  inds[i] = i;
2025 
2026  /* update bounds; fix variables to zero which are currently not in the LP */
2027  lb[i] = 0.0;
2028  ub[i] = i < ncorner ? 1.0 : 0.0;
2029  SCIPdebugMsg(scip, "bounds of LP col %d = [%e, %e]; obj = %e\n", i, lb[i], ub[i], fvals[i]);
2030  }
2031 
2032  /* update lhs and rhs */
2033  perturbation = 0.001;
2034  for( i = 0; i < nrows; ++i )
2035  {
2036  /* note that the last row corresponds to sum_{j} \lambda_j = 1 */
2037  if( i < ecaggr->nvars )
2038  {
2039  SCIP_VAR* x;
2040 
2041  x = ecaggr->vars[i];
2042  assert(x != NULL);
2043 
2044  side[i] = transformValue(scip, SCIPvarGetLbLocal(x), SCIPvarGetUbLocal(x), SCIPgetSolVal(scip, sol, x));
2045 
2046  /* perturb point to enforce an LP solution with ecaggr->nvars + 1 nonzero */
2047  side[i] += side[i] > perturbation ? -perturbation : perturbation;
2048  perturbation /= 1.2;
2049  }
2050  else
2051  {
2052  side[i] = (i == nrows - 1) ? 1.0 : 0.0;
2053  }
2054 
2055  SCIPdebugMsg(scip, "LP row %d in [%e, %e]\n", i, side[i], side[i]);
2056  }
2057 
2058  /* update LP */
2059  SCIP_CALL( SCIPlpiChgObj(sepadata->lpi, ncols, inds, fvals) );
2060  SCIP_CALL( SCIPlpiChgBounds(sepadata->lpi, ncols, inds, lb, ub) );
2061  SCIP_CALL( SCIPlpiChgSides(sepadata->lpi, nrows, inds, side, side) );
2062 
2063  /* free memory used to build the LP */
2064  SCIPfreeBufferArray(scip, &side);
2065  SCIPfreeBufferArray(scip, &ub);
2066  SCIPfreeBufferArray(scip, &lb);
2067  SCIPfreeBufferArray(scip, &inds);
2068 
2069  /*
2070  * 3. solve the LP and store the resulting facet for the transformed space
2071  */
2072  if( USEDUALSIMPLEX ) /*lint !e774 !e506*/
2073  {
2074  SCIP_CALL( SCIPlpiSolveDual(sepadata->lpi) );
2075  }
2076  else
2077  {
2078  SCIP_CALL( SCIPlpiSolvePrimal(sepadata->lpi) );
2079  }
2080 
2081  /* the dual solution corresponds to the coefficients of the facet in the transformed problem; note that it might be
2082  * the case that the dual solution has more components than the facet array
2083  */
2084  if( ecaggr->nvars + 1 == ncols )
2085  {
2086  SCIP_CALL( SCIPlpiGetSol(sepadata->lpi, NULL, NULL, facet, NULL, NULL) );
2087  }
2088  else
2089  {
2090  SCIP_Real* dualsol;
2091 
2092  SCIP_CALL( SCIPallocBufferArray(scip, &dualsol, nrows) );
2093 
2094  /* get the dual solution */
2095  SCIP_CALL( SCIPlpiGetSol(sepadata->lpi, NULL, NULL, dualsol, NULL, NULL) );
2096 
2097  for( i = 0; i < ecaggr->nvars; ++i )
2098  facet[i] = dualsol[i];
2099 
2100  /* constant part of the facet is the last component of the dual solution */
2101  facet[ecaggr->nvars] = dualsol[nrows - 1];
2102 
2103  SCIPfreeBufferArray(scip, &dualsol);
2104  }
2105 
2106 #ifdef SCIP_DEBUG
2107  SCIPdebugMsg(scip, "facet for the transformed problem: ");
2108  for( i = 0; i < ecaggr->nvars; ++i )
2109  {
2110  SCIPdebugMsgPrint(scip, "%3.4e * %s + ", facet[i], SCIPvarGetName(ecaggr->vars[i]));
2111  }
2112  SCIPdebugMsgPrint(scip, "%3.4e\n", facet[ecaggr->nvars]);
2113 #endif
2114 
2115  /*
2116  * 4. transform the facet to original space
2117  * we now have the linear underestimator L(x) = beta^T x + beta_0, which needs to be transform to the original space
2118  * the underestimator in the original space, G(x) = alpha^T x + alpha_0, is given by G(x) = L(T(x)), where T(.) is
2119  * the transformation applied in step 2; therefore,
2120  * alpha_i = beta_i/(ub_i - lb_i)
2121  * alpha_0 = beta_0 - sum_i lb_i * beta_i/(ub_i - lb_i)
2122  */
2123 
2124  SCIPdebugMsg(scip, "facet in orig. space: ");
2125  *facetval = 0.0;
2126 
2127  for( i = 0; i < ecaggr->nvars; ++i )
2128  {
2129  SCIP_Real varlb;
2130  SCIP_Real varub;
2131 
2132  varlb = SCIPvarGetLbLocal(ecaggr->vars[i]);
2133  varub = SCIPvarGetUbLocal(ecaggr->vars[i]);
2134  assert(!SCIPisEQ(scip, varlb, varub));
2135 
2136  /* substract (\beta_i * lb_i) / (ub_i - lb_i) from current alpha_0 */
2137  facet[ecaggr->nvars] -= (facet[i] * varlb) / (varub - varlb);
2138 
2139  /* set \alpha_i := \beta_i / (ub_i - lb_i) */
2140  facet[i] = facet[i] / (varub - varlb);
2141  *facetval += facet[i] * SCIPgetSolVal(scip, sol, ecaggr->vars[i]);
2142 
2143  SCIPdebugMsgPrint(scip, "%3.4e * %s + ", facet[i], SCIPvarGetName(ecaggr->vars[i]));
2144  }
2145 
2146  /* add constant part to the facet value */
2147  *facetval += facet[ecaggr->nvars];
2148  SCIPdebugMsgPrint(scip, "%3.4e\n", facet[ecaggr->nvars]);
2149 
2150  /*
2151  * 5. adjust and check facet with the algorithm of Rikun et al.
2152  */
2153 
2154  if( checkRikun(scip, ecaggr, fvals, facet) )
2155  {
2156  SCIPdebugMsg(scip, "facet pass the check of Rikun et al.\n");
2157  *success = TRUE;
2158  }
2159 
2160  /* free allocated memory */
2161  SCIPfreeBufferArray(scip, &fvals);
2162 
2163  return SCIP_OKAY;
2164 }
2165 
2166 /*
2167  * miscellaneous methods
2168  */
2169 
2170 /** method to add a facet of the convex envelope of an edge-concave aggregation to a given cut */
2171 static
2173  SCIP* scip, /**< SCIP data structure */
2174  SCIP_SOL* sol, /**< current solution (might be NULL) */
2175  SCIP_ROW* cut, /**< current cut (modifiable) */
2176  SCIP_Real* facet, /**< coefficient of the facet (dimension nvars + 1) */
2177  SCIP_VAR** vars, /**< variables of the facet */
2178  int nvars, /**< number of variables in the facet */
2179  SCIP_Real* cutconstant, /**< pointer to update the constant part of the facet */
2180  SCIP_Real* cutactivity, /**< pointer to update the activity of the cut */
2181  SCIP_Bool* success /**< pointer to store if everything went fine */
2182  )
2183 {
2184  int i;
2185 
2186  assert(cut != NULL);
2187  assert(facet != NULL);
2188  assert(vars != NULL);
2189  assert(nvars > 0);
2190  assert(cutconstant != NULL);
2191  assert(cutactivity != NULL);
2192  assert(success != NULL);
2193 
2194  *success = TRUE;
2195 
2196  for( i = 0; i < nvars; ++i )
2197  {
2198  if( SCIPisInfinity(scip, REALABS(facet[i])) )
2199  {
2200  *success = FALSE;
2201  return SCIP_OKAY;
2202  }
2203 
2204  if( !SCIPisZero(scip, facet[i]) )
2205  {
2206  /* add only a constant if the variable has been fixed */
2207  if( SCIPvarGetLbLocal(vars[i]) == SCIPvarGetUbLocal(vars[i]) ) /*lint !e777*/
2208  {
2209  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[i]), SCIPgetSolVal(scip, sol, vars[i])));
2210  *cutconstant += facet[i] * SCIPgetSolVal(scip, sol, vars[i]);
2211  *cutactivity += facet[i] * SCIPgetSolVal(scip, sol, vars[i]);
2212  }
2213  else
2214  {
2215  *cutactivity += facet[i] * SCIPgetSolVal(scip, sol, vars[i]);
2216  SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[i], facet[i]) );
2217  }
2218  }
2219  }
2220 
2221  /* add constant part of the facet */
2222  *cutconstant += facet[nvars];
2223  *cutactivity += facet[nvars];
2224 
2225  return SCIP_OKAY;
2226 }
2227 
2228 /** method to add an linear term to a given cut */
2229 static
2231  SCIP* scip, /**< SCIP data structure */
2232  SCIP_SOL* sol, /**< current solution (might be NULL) */
2233  SCIP_ROW* cut, /**< current cut (modifiable) */
2234  SCIP_VAR* x, /**< linear variable */
2235  SCIP_Real coeff, /**< coefficient */
2236  SCIP_Real* cutconstant, /**< pointer to update the constant part of the facet */
2237  SCIP_Real* cutactivity, /**< pointer to update the activity of the cut */
2238  SCIP_Bool* success /**< pointer to store if everything went fine */
2239  )
2240 {
2241  SCIP_Real activity;
2242 
2243  assert(cut != NULL);
2244  assert(x != NULL);
2245  assert(!SCIPisZero(scip, coeff));
2246  assert(!SCIPisInfinity(scip, coeff));
2247  assert(cutconstant != NULL);
2248  assert(cutactivity != NULL);
2249  assert(success != NULL);
2250 
2251  *success = TRUE;
2252  activity = SCIPgetSolVal(scip, sol, x) * coeff;
2253 
2254  /* do not add a term if the activity is -infinity */
2255  if( SCIPisInfinity(scip, -1.0 * REALABS(activity)) )
2256  {
2257  *success = FALSE;
2258  return SCIP_OKAY;
2259  }
2260 
2261  /* add activity to the constant part if the variable has been fixed */
2262  if( SCIPvarGetLbLocal(x) == SCIPvarGetUbLocal(x) ) /*lint !e777*/
2263  {
2264  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(x), SCIPgetSolVal(scip, sol, x)));
2265  *cutconstant += activity;
2266  SCIPdebugMsg(scip, "add to cut: %e\n", activity);
2267  }
2268  else
2269  {
2270  SCIP_CALL( SCIPaddVarToRow(scip, cut, x, coeff) );
2271  SCIPdebugMsg(scip, "add to cut: %e * %s\n", coeff, SCIPvarGetName(x));
2272  }
2273 
2274  *cutactivity += activity;
2275 
2276  return SCIP_OKAY;
2277 }
2278 
2279 /** method to add an underestimate of a bilinear term to a given cut */
2280 static
2282  SCIP* scip, /**< SCIP data structure */
2283  SCIP_SOL* sol, /**< current solution (might be NULL) */
2284  SCIP_ROW* cut, /**< current cut (modifiable) */
2285  SCIP_VAR* x, /**< first bilinear variable */
2286  SCIP_VAR* y, /**< seconds bilinear variable */
2287  SCIP_Real coeff, /**< coefficient */
2288  SCIP_Real* cutconstant, /**< pointer to update the constant part of the facet */
2289  SCIP_Real* cutactivity, /**< pointer to update the activity of the cut */
2290  SCIP_Bool* success /**< pointer to store if everything went fine */
2291  )
2292 {
2293  SCIP_Real activity;
2294 
2295  assert(cut != NULL);
2296  assert(x != NULL);
2297  assert(y != NULL);
2298  assert(!SCIPisZero(scip, coeff));
2299  assert(cutconstant != NULL);
2300  assert(cutactivity != NULL);
2301  assert(success != NULL);
2302 
2303  *success = TRUE;
2304  activity = coeff * SCIPgetSolVal(scip, sol, x) * SCIPgetSolVal(scip, sol, y);
2305 
2306  if( SCIPisInfinity(scip, REALABS(coeff)) )
2307  {
2308  *success = FALSE;
2309  return SCIP_OKAY;
2310  }
2311 
2312  /* do not add a term if the activity is -infinity */
2313  if( SCIPisInfinity(scip, -1.0 * REALABS(activity)) )
2314  {
2315  *success = FALSE;
2316  return SCIP_OKAY;
2317  }
2318 
2319  /* quadratic case */
2320  if( x == y )
2321  {
2322  SCIP_Real refpoint;
2323  SCIP_Real lincoef;
2324  SCIP_Real linconst;
2325 
2326  lincoef = 0.0;
2327  linconst = 0.0;
2328  refpoint = SCIPgetSolVal(scip, sol, x);
2329 
2330  /* adjust the reference point */
2331  refpoint = SCIPisLT(scip, refpoint, SCIPvarGetLbLocal(x)) ? SCIPvarGetLbLocal(x) : refpoint;
2332  refpoint = SCIPisGT(scip, refpoint, SCIPvarGetUbLocal(x)) ? SCIPvarGetUbLocal(x) : refpoint;
2333  assert(SCIPisLE(scip, refpoint, SCIPvarGetUbLocal(x)) && SCIPisGE(scip, refpoint, SCIPvarGetLbLocal(x)));
2334 
2335  if( SCIPisPositive(scip, coeff) )
2336  SCIPaddSquareLinearization(scip, coeff, refpoint, SCIPvarIsIntegral(x), &lincoef, &linconst, success);
2337  else
2338  SCIPaddSquareSecant(scip, coeff, SCIPvarGetLbLocal(x), SCIPvarGetUbLocal(x), refpoint, &lincoef, &linconst, success);
2339 
2340  *cutactivity += lincoef * refpoint + linconst;
2341  *cutconstant += linconst;
2342 
2343  /* add underestimate to cut */
2344  SCIP_CALL( SCIPaddVarToRow(scip, cut, x, lincoef) );
2345 
2346  SCIPdebugMsg(scip, "add to cut: %e * %s + %e\n", lincoef, SCIPvarGetName(x), linconst);
2347  }
2348  /* bilinear case */
2349  else
2350  {
2351  SCIP_Real refpointx;
2352  SCIP_Real refpointy;
2353  SCIP_Real lincoefx;
2354  SCIP_Real lincoefy;
2355  SCIP_Real linconst;
2356 
2357  lincoefx = 0.0;
2358  lincoefy = 0.0;
2359  linconst = 0.0;
2360  refpointx = SCIPgetSolVal(scip, sol, x);
2361  refpointy = SCIPgetSolVal(scip, sol, y);
2362 
2363  /* adjust the reference points */
2364  refpointx = SCIPisLT(scip, refpointx, SCIPvarGetLbLocal(x)) ? SCIPvarGetLbLocal(x) : refpointx;
2365  refpointx = SCIPisGT(scip, refpointx, SCIPvarGetUbLocal(x)) ? SCIPvarGetUbLocal(x) : refpointx;
2366  refpointy = SCIPisLT(scip, refpointy, SCIPvarGetLbLocal(y)) ? SCIPvarGetLbLocal(y) : refpointy;
2367  refpointy = SCIPisGT(scip, refpointy, SCIPvarGetUbLocal(y)) ? SCIPvarGetUbLocal(y) : refpointy;
2368  assert(SCIPisLE(scip, refpointx, SCIPvarGetUbLocal(x)) && SCIPisGE(scip, refpointx, SCIPvarGetLbLocal(x)));
2369  assert(SCIPisLE(scip, refpointy, SCIPvarGetUbLocal(y)) && SCIPisGE(scip, refpointy, SCIPvarGetLbLocal(y)));
2370 
2372  SCIPvarGetUbLocal(y), refpointy, FALSE, &lincoefx, &lincoefy, &linconst, success);
2373 
2374  *cutactivity += lincoefx * refpointx + lincoefy * refpointy + linconst;
2375  *cutconstant += linconst;
2376 
2377  /* add underestimate to cut */
2378  SCIP_CALL( SCIPaddVarToRow(scip, cut, x, lincoefx) );
2379  SCIP_CALL( SCIPaddVarToRow(scip, cut, y, lincoefy) );
2380 
2381  SCIPdebugMsg(scip, "add to cut: %e * %s + %e * %s + %e\n", lincoefx, SCIPvarGetName(x), lincoefy,
2382  SCIPvarGetName(y), linconst);
2383  }
2384 
2385  return SCIP_OKAY;
2386 }
2387 
2388 /** method to compute and and a cut for a nonlinear row aggregation and a given solution; we compute for each edge
2389  * concave aggregation one facet; the remaining bilinear terms will be underestimated with McCormick, secants or
2390  * linearizations; constant and linear terms will be added to the cut directly
2391  */
2392 static
2394  SCIP* scip, /**< SCIP data structure */
2395  SCIP_SEPA* sepa, /**< separator */
2396  SCIP_SEPADATA* sepadata, /**< separator data */
2397  SCIP_NLROWAGGR* nlrowaggr, /**< nonlinear row aggregation */
2398  SCIP_SOL* sol, /**< current solution (might be NULL) */
2399  SCIP_Bool* separated, /**< pointer to store if we could separate the current solution */
2400  SCIP_Bool* cutoff /**< pointer to store if the current node gets cut off */
2401  )
2402 {
2403  SCIP_ROW* cut;
2404  SCIP_Real* bestfacet;
2405  SCIP_Real bestfacetval;
2406  SCIP_Real cutconstant;
2407  SCIP_Real cutactivity;
2408  int bestfacetsize;
2409  char cutname[SCIP_MAXSTRLEN];
2410  SCIP_Bool found;
2411  SCIP_Bool islocalcut;
2412  int i;
2413 
2414  assert(separated != NULL);
2415  assert(cutoff != NULL);
2416  assert(nlrowaggr->necaggr > 0);
2417  assert(nlrowaggr->nlrow != NULL);
2418  assert(SCIPnlrowIsInNLP(nlrowaggr->nlrow));
2419 
2420  *separated = FALSE;
2421  *cutoff = FALSE;
2422  islocalcut = SCIPgetDepth(scip) != 0;
2423 
2424  /* create the cut */
2425  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "ec");
2426  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), SCIPinfinity(scip), islocalcut, FALSE,
2427  sepadata->dynamiccuts) );
2428  SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
2429 
2430  /* track rhs and activity of the cut */
2431  cutconstant = nlrowaggr->constant;
2432  cutactivity = 0.0;
2433 
2434  /* allocate necessary memory */
2435  bestfacetsize = sepadata->maxaggrsize + 1;
2436  SCIP_CALL( SCIPallocBufferArray(scip, &bestfacet, bestfacetsize) );
2437 
2438 #ifdef SCIP_DEBUG
2439  SCIP_CALL( SCIPnlrowPrint(nlrowaggr->nlrow, SCIPgetMessagehdlr(scip), NULL) );
2440 
2441  SCIPdebugMsg(scip, "current solution:\n");
2442  for( i = 0; i < SCIPgetNVars(scip); ++i )
2443  {
2444  SCIP_VAR* var = SCIPgetVars(scip)[i];
2445  SCIPdebugMsg(scip, " %s = [%e, %e] solval = %e\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var),
2446  SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var));
2447  }
2448 #endif
2449 
2450  /* compute a facet for each edge-concave aggregation */
2451  for( i = 0; i < nlrowaggr->necaggr; ++i )
2452  {
2453  SCIP_ECAGGR* ecaggr;
2454  SCIP_Bool success;
2455 
2456  ecaggr = nlrowaggr->ecaggr[i];
2457  assert(ecaggr != NULL);
2458 
2459  /* compute a facet of the convex envelope */
2460  SCIP_CALL( SCIPcomputeConvexEnvelopeFacet(scip, sepadata, sol, ecaggr, bestfacet, &bestfacetval, &found) );
2461 
2462  SCIPdebugMsg(scip, "found facet for edge-concave aggregation %d/%d ? %s\n", i, nlrowaggr->necaggr,
2463  found ? "yes" : "no");
2464 
2465 #ifdef SCIP_DEBUG
2466  if( found )
2467  printFacet(scip, ecaggr->vars, ecaggr->nvars, bestfacet, bestfacetval);
2468 #endif
2469 
2470  /* do not add any cut because we did not found a facet for at least one edge-concave aggregation */
2471  if( !found ) /*lint !e774*/
2472  goto TERMINATE;
2473 
2474  /* add facet to the cut and update the rhs and activity of the cut */
2475  SCIP_CALL( addFacetToCut(scip, sol, cut, bestfacet, ecaggr->vars, ecaggr->nvars, &cutconstant, &cutactivity,
2476  &success) );
2477 
2478  if( !success )
2479  goto TERMINATE;
2480  }
2481 
2482  /* compute an underestimate for each bilinear term which is not in any edge-concave aggregation */
2483  for( i = 0; i < nlrowaggr->nremterms; ++i )
2484  {
2485  SCIP_VAR* x;
2486  SCIP_VAR* y;
2487  SCIP_Bool success;
2488 
2489  x = nlrowaggr->remtermvars1[i];
2490  y = nlrowaggr->remtermvars2[i];
2491  assert(x != NULL);
2492  assert(y != NULL);
2493 
2494  SCIP_CALL( addBilinearTermToCut(scip, sol, cut, x, y, nlrowaggr->remtermcoefs[i], &cutconstant, &cutactivity,
2495  &success) );
2496 
2497  if( !success )
2498  goto TERMINATE;
2499  }
2500 
2501  /* add all linear terms to the cut */
2502  for( i = 0; i < nlrowaggr->nlinvars; ++i )
2503  {
2504  SCIP_VAR* x;
2505  SCIP_Real coef;
2506  SCIP_Bool success;
2507 
2508  x = nlrowaggr->linvars[i];
2509  assert(x != NULL);
2510 
2511  coef = nlrowaggr->lincoefs[i];
2512 
2513  SCIP_CALL( addLinearTermToCut(scip, sol, cut, x, coef, &cutconstant, &cutactivity, &success) );
2514 
2515  if( !success )
2516  goto TERMINATE;
2517  }
2518 
2519  SCIPdebugMsg(scip, "cut activity = %e rhs(nlrow) = %e\n", cutactivity, nlrowaggr->rhs);
2520 
2521  /* set rhs of the cut (substract the constant part of the cut) */
2522  SCIP_CALL( SCIPchgRowRhs(scip, cut, nlrowaggr->rhs - cutconstant) );
2523  SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
2524 
2525  /* check activity of the row; this assert can fail because of numerics */
2526  /* assert(SCIPisFeasEQ(scip, cutactivity - cutconstant, SCIPgetRowSolActivity(scip, cut, sol)) ); */
2527 
2528 #ifdef SCIP_DEBUG
2529  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
2530 #endif
2531 
2532  SCIPdebugMsg(scip, "EC cut <%s>: act=%f eff=%f rank=%d range=%e\n",
2533  SCIProwGetName(cut), SCIPgetRowSolActivity(scip, cut, sol), SCIPgetCutEfficacy(scip, sol, cut),
2534  SCIProwGetRank(cut), SCIPgetRowMaxCoef(scip, cut) / SCIPgetRowMinCoef(scip, cut) );
2535 
2536  /* try to add the cut has a finite rhs, is efficacious, and does not exceed the maximum cut range */
2537  if( !SCIPisInfinity(scip, nlrowaggr->rhs - cutconstant) && SCIPisCutEfficacious(scip, sol, cut)
2538  && SCIPgetRowMaxCoef(scip, cut) / SCIPgetRowMinCoef(scip, cut) < sepadata->cutmaxrange )
2539  {
2540  /* add the cut if it is separating the given solution by at least minviolation */
2541  if( SCIPisGE(scip, cutactivity - nlrowaggr->rhs, sepadata->minviolation) )
2542  {
2543  SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
2544  *separated = TRUE;
2545  SCIPdebugMsg(scip, "added separating cut\n");
2546  }
2547 
2548  if( !(*cutoff) && !islocalcut )
2549  {
2550  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
2551  SCIPdebugMsg(scip, "added cut to cut pool\n");
2552  }
2553  }
2554 
2555 TERMINATE:
2556  /* free allocated memory */
2557  SCIPfreeBufferArray(scip, &bestfacet);
2558 
2559  /* release the row */
2560  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
2561 
2562  return SCIP_OKAY;
2563 }
2564 
2565 /** returns whether it is possible to compute a cut for a given nonlinear row aggregation */
2566 static
2568  SCIP* scip, /**< SCIP data structure */
2569  SCIP_SOL* sol, /**< current solution (might be NULL) */
2570  SCIP_NLROWAGGR* nlrowaggr /**< nonlinear row aggregation */
2571  )
2572 {
2573  int i;
2574 
2575  assert(scip != NULL);
2576  assert(nlrowaggr != NULL);
2577 
2578  if( !SCIPnlrowIsInNLP(nlrowaggr->nlrow) )
2579  {
2580  SCIPdebugMsg(scip, "nlrow is not in NLP anymore\n");
2581  return FALSE;
2582  }
2583 
2584  for( i = 0; i < nlrowaggr->nquadvars; ++i )
2585  {
2586  SCIP_VAR* var = nlrowaggr->quadvars[i];
2587  assert(var != NULL);
2588 
2589  /* check whether the variable has infinite bounds */
2591  || SCIPisInfinity(scip, REALABS(SCIPgetSolVal(scip, sol, var))) )
2592  {
2593  SCIPdebugMsg(scip, "nlrow aggregation contains unbounded variables\n");
2594  return FALSE;
2595  }
2596 
2597  /* check whether the variable has been fixed and is in one edge-concave aggregation */
2598  if( nlrowaggr->quadvar2aggr[i] >= 0 && SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
2599  {
2600  SCIPdebugMsg(scip, "nlrow aggregation contains fixed variables in an e.c. aggregation\n");
2601  return FALSE;
2602  }
2603  }
2604 
2605  return TRUE;
2606 }
2607 
2608 /** searches and tries to add edge-concave cuts */
2609 static
2611  SCIP* scip, /**< SCIP data structure */
2612  SCIP_SEPA* sepa, /**< separator */
2613  SCIP_SEPADATA* sepadata, /**< separator data */
2614  SCIP_SOL* sol, /**< current solution */
2615  SCIP_RESULT* result /**< pointer to store the result of the separation call */
2616  )
2617 {
2618  int nmaxcuts;
2619  int ncuts;
2620  int i;
2621 
2622  assert(*result == SCIP_DIDNOTRUN);
2623 
2624  SCIPdebugMsg(scip, "separate cuts...\n");
2625 
2626  /* skip if there are no nonlinear row aggregations */
2627  if( sepadata->nnlrowaggrs == 0 )
2628  {
2629  SCIPdebugMsg(scip, "no aggregations exists -> skip call\n");
2630  return SCIP_OKAY;
2631  }
2632 
2633  /* get the maximal number of cuts allowed in a separation round */
2634  nmaxcuts = SCIPgetDepth(scip) == 0 ? sepadata->maxsepacutsroot : sepadata->maxsepacuts;
2635  ncuts = 0;
2636 
2637  /* try to compute cuts for each nonlinear row independently */
2638  for( i = 0; i < sepadata->nnlrowaggrs && ncuts < nmaxcuts && !SCIPisStopped(scip); ++i )
2639  {
2640  SCIP_NLROWAGGR* nlrowaggr;
2641  SCIP_Bool separated;
2642  SCIP_Bool cutoff;
2643 
2644  nlrowaggr = sepadata->nlrowaggrs[i];
2645  assert(nlrowaggr != NULL);
2646 
2647  /* skip nonlinear aggregations for which it is obviously not possible to compute a cut */
2648  if( !isPossibleToComputeCut(scip, sol, nlrowaggr) )
2649  return SCIP_OKAY;
2650 
2651  *result = (*result == SCIP_DIDNOTRUN) ? SCIP_DIDNOTFIND : *result;
2652 
2653  SCIPdebugMsg(scip, "try to compute a cut for nonlinear row aggregation %d\n", i);
2654 
2655  /* compute and add cut */
2656  SCIP_CALL( computeCut(scip, sepa, sepadata, nlrowaggr, sol, &separated, &cutoff) );
2657  SCIPdebugMsg(scip, "found a cut: %s cutoff: %s\n", separated ? "yes" : "no", cutoff ? "yes" : "no");
2658 
2659  /* stop if the current node gets cut off */
2660  if( cutoff )
2661  {
2662  assert(separated);
2663  *result = SCIP_CUTOFF;
2664  return SCIP_OKAY;
2665  }
2666 
2667  /* do not compute more cuts if we already separated the given solution */
2668  if( separated )
2669  {
2670  assert(!cutoff);
2671  *result = SCIP_SEPARATED;
2672  ++ncuts;
2673  }
2674  }
2675 
2676  return SCIP_OKAY;
2677 }
2678 
2679 /*
2680  * Callback methods of separator
2681  */
2682 
2683 /** copy method for separator plugins (called when SCIP copies plugins) */
2684 static
2685 SCIP_DECL_SEPACOPY(sepaCopyEccuts)
2686 { /*lint --e{715}*/
2687  assert(scip != NULL);
2688  assert(sepa != NULL);
2689  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2690 
2691  /* call inclusion method of constraint handler */
2693 
2694  return SCIP_OKAY;
2695 }
2696 
2697 /** destructor of separator to free user data (called when SCIP is exiting) */
2698 static
2699 SCIP_DECL_SEPAFREE(sepaFreeEccuts)
2700 { /*lint --e{715}*/
2701  SCIP_SEPADATA* sepadata;
2702 
2703  sepadata = SCIPsepaGetData(sepa);
2704  assert(sepadata != NULL);
2705 
2706  SCIP_CALL( sepadataFree(scip, &sepadata) );
2707  SCIPsepaSetData(sepa, NULL);
2708 
2709  return SCIP_OKAY;
2710 }
2711 
2712 /** solving process deinitialization method of separator (called before branch and bound process data is freed) */
2713 static
2714 SCIP_DECL_SEPAEXITSOL(sepaExitsolEccuts)
2715 { /*lint --e{715}*/
2716  SCIP_SEPADATA* sepadata;
2717 
2718  sepadata = SCIPsepaGetData(sepa);
2719  assert(sepadata != NULL);
2720 
2721  /* print statistics */
2722 #ifdef SCIP_STATISTIC
2723  SCIPstatisticMessage("rhs-AGGR %d\n", sepadata->nrhsnlrowaggrs);
2724  SCIPstatisticMessage("lhs-AGGR %d\n", sepadata->nlhsnlrowaggrs);
2725  SCIPstatisticMessage("aggr. search time = %f\n", sepadata->aggrsearchtime);
2726 #endif
2727 
2728  /* free nonlinear row aggregations */
2729  SCIP_CALL( sepadataFreeNlrows(scip, sepadata) );
2730 
2731  /* mark that we should search again for nonlinear row aggregations */
2732  sepadata->searchedforaggr = FALSE;
2733 
2734  SCIPdebugMsg(scip, "exitsol\n");
2735 
2736  return SCIP_OKAY;
2737 }
2738 
2739 /** LP solution separation method of separator */
2740 static
2741 SCIP_DECL_SEPAEXECLP(sepaExeclpEccuts)
2742 { /*lint --e{715}*/
2743  SCIP_SEPADATA* sepadata;
2744  int depth;
2745  int ncalls;
2746 
2747  sepadata = SCIPsepaGetData(sepa);
2748  assert(sepadata != NULL);
2749 
2750  *result = SCIP_DIDNOTRUN;
2751 
2752  if( !allowlocal )
2753  return SCIP_OKAY;
2754 
2755  /* check min- and maximal aggregation size */
2756  if( sepadata->maxaggrsize < sepadata->minaggrsize )
2757  return SCIP_PARAMETERWRONGVAL;
2758 
2759  /* only call separator, if we are not close to terminating */
2760  if( SCIPisStopped(scip) )
2761  return SCIP_OKAY;
2762 
2763  /* skip if the LP is not constructed yet */
2764  if( !SCIPisNLPConstructed(scip) )
2765  {
2766  SCIPdebugMsg(scip, "Skip since NLP is not constructed yet.\n");
2767  return SCIP_OKAY;
2768  }
2769 
2770  depth = SCIPgetDepth(scip);
2771 
2772  /* only call separator up to a maximum depth */
2773  if ( sepadata->maxdepth >= 0 && depth > sepadata->maxdepth )
2774  return SCIP_OKAY;
2775 
2776  /* only call separator a given number of times at each node */
2777  ncalls = SCIPsepaGetNCallsAtNode(sepa);
2778  if ( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
2779  || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
2780  return SCIP_OKAY;
2781 
2782  /* search for nonlinear row aggregations */
2783  if( !sepadata->searchedforaggr )
2784  {
2785  int i;
2786 
2787  SCIPstatistic( sepadata->aggrsearchtime -= SCIPgetTotalTime(scip) );
2788 
2789  SCIPdebugMsg(scip, "search for nonlinear row aggregations\n");
2790  for( i = 0; i < SCIPgetNNLPNlRows(scip) && !SCIPisStopped(scip); ++i )
2791  {
2792  SCIP_NLROW* nlrow = SCIPgetNLPNlRows(scip)[i];
2793  SCIP_CALL( findAndStoreEcAggregations(scip, sepadata, nlrow, NULL) );
2794  }
2795  sepadata->searchedforaggr = TRUE;
2796 
2797  SCIPstatistic( sepadata->aggrsearchtime += SCIPgetTotalTime(scip) );
2798  }
2799 
2800  /* search for edge-concave cuts */
2801  SCIP_CALL( separateCuts(scip, sepa, sepadata, NULL, result) );
2802 
2803  return SCIP_OKAY;
2804 }
2805 
2806 /*
2807  * separator specific interface methods
2808  */
2809 
2810 /** creates the edge concave separator and includes it in SCIP */
2812  SCIP* scip /**< SCIP data structure */
2813  )
2814 {
2815  SCIP_SEPADATA* sepadata;
2816  SCIP_SEPA* sepa;
2817 
2818  /* create eccuts separator data */
2819  SCIP_CALL( sepadataCreate(scip, &sepadata) );
2820 
2821  /* include separator */
2823  SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpEccuts, NULL, sepadata) );
2824 
2825  assert(sepa != NULL);
2826 
2827  /* set non fundamental callbacks via setter functions */
2828  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyEccuts) );
2829  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeEccuts) );
2830  SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolEccuts) );
2831 
2832  /* add eccuts separator parameters */
2834  "separating/" SEPA_NAME "/dynamiccuts",
2835  "should generated cuts be removed from the LP if they are no longer tight?",
2836  &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
2837 
2838  SCIP_CALL( SCIPaddIntParam(scip,
2839  "separating/" SEPA_NAME "/maxrounds",
2840  "maximal number of eccuts separation rounds per node (-1: unlimited)",
2841  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
2842 
2843  SCIP_CALL( SCIPaddIntParam(scip,
2844  "separating/" SEPA_NAME "/maxroundsroot",
2845  "maximal number of eccuts separation rounds in the root node (-1: unlimited)",
2846  &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
2847 
2848  SCIP_CALL( SCIPaddIntParam(scip,
2849  "separating/" SEPA_NAME "/maxdepth",
2850  "maximal depth at which the separator is applied (-1: unlimited)",
2851  &sepadata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
2852 
2853  SCIP_CALL( SCIPaddIntParam(scip,
2854  "separating/" SEPA_NAME "/maxsepacuts",
2855  "maximal number of edge-concave cuts separated per separation round",
2856  &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
2857 
2858  SCIP_CALL( SCIPaddIntParam(scip,
2859  "separating/" SEPA_NAME "/maxsepacutsroot",
2860  "maximal number of edge-concave cuts separated per separation round in the root node",
2861  &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
2862 
2863  SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/cutmaxrange",
2864  "maximal coef. range of a cut (max coef. divided by min coef.) in order to be added to LP relaxation",
2865  &sepadata->cutmaxrange, FALSE, DEFAULT_CUTMAXRANGE, 0.0, SCIPinfinity(scip), NULL, NULL) );
2866 
2867  SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/minviolation",
2868  "minimal violation of an edge-concave cut to be separated",
2869  &sepadata->minviolation, FALSE, DEFAULT_MINVIOLATION, 0.0, 0.5, NULL, NULL) );
2870 
2871  SCIP_CALL( SCIPaddIntParam(scip,
2872  "separating/" SEPA_NAME "/minaggrsize",
2873  "search for edge-concave aggregations of at least this size",
2874  &sepadata->minaggrsize, TRUE, DEFAULT_MINAGGRSIZE, 3, 5, NULL, NULL) );
2875 
2876  SCIP_CALL( SCIPaddIntParam(scip,
2877  "separating/" SEPA_NAME "/maxaggrsize",
2878  "search for edge-concave aggregations of at most this size",
2879  &sepadata->maxaggrsize, TRUE, DEFAULT_MAXAGGRSIZE, 3, 5, NULL, NULL) );
2880 
2881  SCIP_CALL( SCIPaddIntParam(scip,
2882  "separating/" SEPA_NAME "/maxbilinterms",
2883  "maximum number of bilinear terms allowed to be in a quadratic constraint",
2884  &sepadata->maxbilinterms, TRUE, DEFAULT_MAXBILINTERMS, 0, INT_MAX, NULL, NULL) );
2885 
2886  SCIP_CALL( SCIPaddIntParam(scip,
2887  "separating/" SEPA_NAME "/maxstallrounds",
2888  "maximum number of unsuccessful rounds in the edge-concave aggregation search",
2889  &sepadata->maxstallrounds, TRUE, DEFAULT_MAXSTALLROUNDS, 0, INT_MAX, NULL, NULL) );
2890 
2891  return SCIP_OKAY;
2892 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:116
#define USEDUALSIMPLEX
Definition: sepa_eccuts.c:68
SCIP_Real * remtermcoefs
Definition: sepa_eccuts.c:115
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: sepa_eccuts.c:2612
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:105
int * quadvar2aggr
Definition: sepa_eccuts.c:109
SCIP_Bool rhsaggr
Definition: sepa_eccuts.c:98
SCIP_RETCODE SCIPlpiGetNRows(SCIP_LPI *lpi, int *nrows)
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:513
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:436
#define NULL
Definition: def.h:239
enum TCLIQUE_Status TCLIQUE_STATUS
Definition: tclique.h:59
SCIP_RETCODE SCIPnlrowPrint(SCIP_NLROW *nlrow, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: nlp.c:2290
SCIP_RETCODE SCIPlpiFree(SCIP_LPI **lpi)
#define narcs
Definition: gastrans.c:68
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:99
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:284
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1547
static SCIP_RETCODE createMIP(SCIP *scip, SCIP *subscip, SCIP_SEPADATA *sepadata, SCIP_NLROW *nlrow, SCIP_Bool rhsaggr, SCIP_VAR **forwardarcs, SCIP_VAR **backwardarcs, SCIP_Real *nodeweights, int *nedges)
Definition: sepa_eccuts.c:767
static SCIP_RETCODE addFacetToCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Real *facet, SCIP_VAR **vars, int nvars, SCIP_Real *cutconstant, SCIP_Real *cutactivity, SCIP_Bool *success)
Definition: sepa_eccuts.c:2174
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
int nremterms
Definition: sepa_eccuts.c:116
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1570
SCIP_RETCODE SCIPlpiGetSol(SCIP_LPI *lpi, SCIP_Real *objval, SCIP_Real *primsol, SCIP_Real *dualsol, SCIP_Real *activity, SCIP_Real *redcost)
SCIP_Real rhs
Definition: sepa_eccuts.c:119
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17343
#define SEPA_DELAY
Definition: sepa_eccuts.c:41
#define SEPA_DESC
Definition: sepa_eccuts.c:36
SCIP_VAR ** remtermvars1
Definition: sepa_eccuts.c:113
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:379
#define SCIP_MAXSTRLEN
Definition: def.h:260
SCIP_RETCODE SCIPlpiSolvePrimal(SCIP_LPI *lpi)
static SCIP_DECL_SEPACOPY(sepaCopyEccuts)
Definition: sepa_eccuts.c:2687
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1602
#define CLIQUE_MINWEIGHT
Definition: sepa_eccuts.c:46
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17399
#define SCIP_CALL_FINALLY(x, y)
Definition: def.h:393
static SCIP_DECL_SEPAEXITSOL(sepaExitsolEccuts)
Definition: sepa_eccuts.c:2716
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE sepadataFreeNlrows(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_eccuts.c:644
#define SEPA_PRIORITY
Definition: sepa_eccuts.c:37
SCIP_Real * termcoefs
Definition: sepa_eccuts.c:86
SCIP_RETCODE SCIPlpiChgSides(SCIP_LPI *lpi, int nrows, const int *ind, const SCIP_Real *lhs, const SCIP_Real *rhs)
#define CLIQUE_MAXNTREENODES
Definition: sepa_eccuts.c:47
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16928
static SCIP_RETCODE searchEcAggrWithCliques(SCIP *scip, TCLIQUE_GRAPH *graph, SCIP_SEPADATA *sepadata, SCIP_NLROW *nlrow, int *quadvar2aggr, int nfoundsofar, SCIP_Bool rhsaggr, SCIP_Bool *foundaggr, SCIP_Bool *foundclique)
Definition: sepa_eccuts.c:1165
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
int varsize
Definition: sepa_eccuts.c:84
static SCIP_RETCODE SCIPcomputeConvexEnvelopeFacet(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_ECAGGR *ecaggr, SCIP_Real *facet, SCIP_Real *facetval, SCIP_Bool *success)
Definition: sepa_eccuts.c:1966
static SCIP_RETCODE searchEcAggrWithMIP(SCIP *subscip, SCIP_Real timelimit, int nedges, SCIP_Bool *aggrleft, SCIP_Bool *found)
Definition: sepa_eccuts.c:1014
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:996
#define FALSE
Definition: def.h:65
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
SCIP_NLROW * nlrow
Definition: sepa_eccuts.c:97
#define CLIQUE_MAXFIRSTNODEWEIGHT
Definition: sepa_eccuts.c:43
SCIP_ECAGGR ** ecaggr
Definition: sepa_eccuts.c:101
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10017
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:64
#define SCIPdebug(x)
Definition: pub_message.h:74
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:689
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIPstatisticMessage
Definition: pub_message.h:104
int SCIPnlrowGetNQuadVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3276
SCIP_Real SCIPnlrowGetRhs(SCIP_NLROW *nlrow)
Definition: nlp.c:3384
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:184
static SCIP_RETCODE sepadataFree(SCIP *scip, SCIP_SEPADATA **sepadata)
Definition: sepa_eccuts.c:674
SCIP_VAR ** remtermvars2
Definition: sepa_eccuts.c:114
static SCIP_RETCODE createTcliqueGraph(SCIP *scip, SCIP_NLROW *nlrow, TCLIQUE_GRAPH **graph, SCIP_Real *nodeweights)
Definition: sepa_eccuts.c:1080
int SCIPnlrowGetNLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3246
SCIP_RETCODE SCIPlpiGetNCols(SCIP_LPI *lpi, int *ncols)
edge concave cut separator
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
SCIP_VAR ** quadvars
Definition: sepa_eccuts.c:108
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:171
tclique user interface
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:339
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:220
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:694
#define SCIPdebugMsgPrint
Definition: scip_message.h:89
#define SCIPdebugMsg
Definition: scip_message.h:88
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:155
SCIP_VAR ** x
Definition: circlepacking.c:54
SCIP_RETCODE SCIPlpiCreate(SCIP_LPI **lpi, SCIP_MESSAGEHDLR *messagehdlr, const char *name, SCIP_OBJSEN objsen)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:223
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:491
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1823
SCIP_RETCODE SCIPlpiAddCols(SCIP_LPI *lpi, int ncols, const SCIP_Real *obj, const SCIP_Real *lb, const SCIP_Real *ub, char **colnames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:600
int SCIPnlrowGetNQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3323
static SCIP_RETCODE ecaggrCreateEmpty(SCIP *scip, SCIP_ECAGGR **ecaggr, int nquadvars, int nquadterms)
Definition: sepa_eccuts.c:165
#define DEFAULT_MAXSTALLROUNDS
Definition: sepa_eccuts.c:63
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3025
SCIP_RETCODE SCIPlpiSolveDual(SCIP_LPI *lpi)
static SCIP_RETCODE ecaggrFree(SCIP *scip, SCIP_ECAGGR **ecaggr)
Definition: sepa_eccuts.c:195
int * termvars1
Definition: sepa_eccuts.c:87
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17353
static SCIP_Bool isPossibleToComputeCut(SCIP *scip, SCIP_SOL *sol, SCIP_NLROWAGGR *nlrowaggr)
Definition: sepa_eccuts.c:2569
#define SEPA_NAME
Definition: sepa_eccuts.c:35
SCIP_RETCODE SCIPcreateConsBasicXor(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_Bool rhs, int nvars, SCIP_VAR **vars)
Definition: cons_xor.c:5714
SCIP_Real coef
Definition: type_expr.h:104
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:161
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1298
SCIP_RETCODE SCIPlpiAddRows(SCIP_LPI *lpi, int nrows, const SCIP_Real *lhs, const SCIP_Real *rhs, char **rownames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
SCIP_Bool SCIPnlrowIsInNLP(SCIP_NLROW *nlrow)
Definition: nlp.c:3433
SCIP_VAR ** SCIPnlrowGetQuadVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3286
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2577
int nterms
Definition: sepa_eccuts.c:89
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)
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
static SCIP_RETCODE doSeachEcAggr(SCIP *scip, SCIP *subscip, SCIP_SEPADATA *sepadata, SCIP_NLROW *nlrow, SCIP_SOL *sol, SCIP_Bool rhsaggr, int *quadvar2aggr, int *nfound)
Definition: sepa_eccuts.c:1284
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1805
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
SCIP_VAR ** vars
Definition: sepa_eccuts.c:82
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
#define SEPA_FREQ
Definition: sepa_eccuts.c:38
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:816
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:519
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:128
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4703
static SCIP_Real phi(SCIP *scip, SCIP_Real val, SCIP_Real lb, SCIP_Real ub)
Definition: sepa_eccuts.c:744
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
static SCIP_RETCODE sepadataAddNlrowaggr(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_NLROWAGGR *nlrowaggr)
Definition: sepa_eccuts.c:700
static SCIP_RETCODE storeAggrFromMIP(SCIP *subscip, SCIP_NLROW *nlrow, SCIP_VAR **forwardarcs, SCIP_VAR **backwardarcs, int *quadvar2aggr, int nfoundsofar)
Definition: sepa_eccuts.c:968
internal methods for NLP management
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:610
#define REALABS(x)
Definition: def.h:174
SCIP_Real constant
Definition: sepa_eccuts.c:120
static SCIP_RETCODE addBilinearTermToCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_VAR *x, SCIP_VAR *y, SCIP_Real coeff, SCIP_Real *cutconstant, SCIP_Real *cutactivity, SCIP_Bool *success)
Definition: sepa_eccuts.c:2283
void tcliqueMaxClique(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_WEIGHT maxfirstnodeweight, TCLIQUE_WEIGHT minweight, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, int *ntreenodes, TCLIQUE_STATUS *status)
SCIP_QUADELEM * SCIPnlrowGetQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3333
#define DEFAULT_MAXAGGRSIZE
Definition: sepa_eccuts.c:61
#define DEFAULT_CUTMAXRANGE
Definition: sepa_eccuts.c:56
#define SCIP_CALL(x)
Definition: def.h:351
int termsize
Definition: sepa_eccuts.c:90
int nlinvars
Definition: sepa_eccuts.c:106
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:294
SCIP_Real * lincoefs
Definition: sepa_eccuts.c:105
#define DEFAULT_MAXDEPTH
Definition: sepa_eccuts.c:53
void SCIPaddSquareSecant(SCIP *scip, SCIP_Real sqrcoef, SCIP_Real lb, SCIP_Real ub, SCIP_Real refpoint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
#define DEFAULT_MINVIOLATION
Definition: sepa_eccuts.c:59
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:178
#define DEFAULT_MAXSEPACUTS
Definition: sepa_eccuts.c:54
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip_solve.c:3367
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip_sepa.c:300
static SCIP_RETCODE nlrowaggrAddRemBilinTerm(SCIP *scip, SCIP_NLROWAGGR *nlrowaggr, SCIP_VAR *x, SCIP_VAR *y, SCIP_Real coef)
Definition: sepa_eccuts.c:362
#define DEFAULT_MAXSEPACUTSROOT
Definition: sepa_eccuts.c:55
#define SCIP_Bool
Definition: def.h:62
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
Definition: scip_lp.c:1519
static SCIP_RETCODE nlrowaggrStoreQuadraticVars(SCIP *scip, SCIP_NLROWAGGR *nlrowaggr, SCIP_VAR **quadvars, int nquadvars)
Definition: sepa_eccuts.c:341
SCIP_RETCODE SCIPincludeSepaEccuts(SCIP *scip)
Definition: sepa_eccuts.c:2813
int nquadvars
Definition: struct_nlp.h:80
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:715
SCIP_VAR ** linvars
Definition: sepa_eccuts.c:104
static SCIP_RETCODE searchEcAggr(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_NLROW *nlrow, SCIP_SOL *sol, SCIP_Bool rhsaggr, int *quadvar2aggr, int *nfound)
Definition: sepa_eccuts.c:1473
static SCIP_Real transformValue(SCIP *scip, SCIP_Real lb, SCIP_Real ub, SCIP_Real val)
Definition: sepa_eccuts.c:1921
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:405
#define MIN(x, y)
Definition: def.h:209
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:578
#define SUBSCIP_NODELIMIT
Definition: sepa_eccuts.c:65
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:1365
#define DEFAULT_MAXBILINTERMS
Definition: sepa_eccuts.c:62
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:138
int nquadvars
Definition: sepa_eccuts.c:111
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2280
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:116
static SCIP_RETCODE nlrowaggrCreate(SCIP *scip, SCIP_NLROW *nlrow, SCIP_NLROWAGGR **nlrowaggr, int *quadvar2aggr, int nfound, SCIP_Bool rhsaggr)
Definition: sepa_eccuts.c:385
int nvars
Definition: sepa_eccuts.c:83
static SCIP_RETCODE isCandidate(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_NLROW *nlrow, SCIP_Bool *rhscandidate, SCIP_Bool *lhscandidate)
Definition: sepa_eccuts.c:1504
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2045
static SCIP_RETCODE nlrowaggrStoreLinearTerms(SCIP *scip, SCIP_NLROWAGGR *nlrowaggr, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nlinvars)
Definition: sepa_eccuts.c:301
#define BMSclearMemory(ptr)
Definition: memory.h:111
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:16958
SCIP_RETCODE SCIPlpiChgBounds(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *lb, const SCIP_Real *ub)
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2044
SCIP_EXPRTREE * SCIPnlrowGetExprtree(SCIP_NLROW *nlrow)
Definition: nlp.c:3364
static SCIP_RETCODE nlrowaggrFree(SCIP *scip, SCIP_NLROWAGGR **nlrowaggr)
Definition: sepa_eccuts.c:546
Constraint handler for XOR constraints, .
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1474
#define CLIQUE_BACKTRACKFREQ
Definition: sepa_eccuts.c:48
#define MAX(x, y)
Definition: def.h:208
static SCIP_RETCODE addLinearTermToCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_VAR *x, SCIP_Real coeff, SCIP_Real *cutconstant, SCIP_Real *cutactivity, SCIP_Bool *success)
Definition: sepa_eccuts.c:2232
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:236
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2379
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE createLP(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_eccuts.c:1771
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1724
static SCIP_RETCODE findAndStoreEcAggregations(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_NLROW *nlrow, SCIP_SOL *sol)
Definition: sepa_eccuts.c:1601
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_eccuts.c:52
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
SCIP_VAR * a
Definition: circlepacking.c:57
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1999
#define DEFAULT_DYNAMICCUTS
Definition: sepa_eccuts.c:50
struct SCIP_LPi SCIP_LPI
Definition: type_lpi.h:96
#define SCIPstatistic(x)
Definition: pub_message.h:101
#define SCIP_Real
Definition: def.h:150
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:739
static SCIP_DECL_SEPAEXECLP(sepaExeclpEccuts)
Definition: sepa_eccuts.c:2743
#define SCIP_CALL_TERMINATE(retcode, x, TERM)
Definition: def.h:372
SCIP_VAR ** y
Definition: circlepacking.c:55
static SCIP_DECL_SEPAFREE(sepaFreeEccuts)
Definition: sepa_eccuts.c:2701
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2094
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17026
SCIP_Real SCIPgetTotalTime(SCIP *scip)
Definition: scip_timing.c:409
static SCIP_RETCODE sepadataCreate(SCIP *scip, SCIP_SEPADATA **sepadata)
Definition: sepa_eccuts.c:628
static SCIP_Real evalCorner(SCIP_ECAGGR *ecaggr, int k)
Definition: sepa_eccuts.c:1883
SCIP_RETCODE SCIPlpiChgObj(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *obj)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real * SCIPnlrowGetLinearCoefs(SCIP_NLROW *nlrow)
Definition: nlp.c:3266
TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
#define ADJUSTFACETTOL
Definition: sepa_eccuts.c:67
static SCIP_RETCODE computeCut(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_NLROWAGGR *nlrowaggr, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff)
Definition: sepa_eccuts.c:2395
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17409
#define nnodes
Definition: gastrans.c:65
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:117
#define DEFAULT_MINAGGRSIZE
Definition: sepa_eccuts.c:60
SCIP_VAR ** SCIPnlrowGetLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3256
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2874
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
SCIP_Real SCIPnlrowGetConstant(SCIP_NLROW *nlrow)
Definition: nlp.c:3236
static SCIP_RETCODE ecaggrAddBilinTerm(SCIP *scip, SCIP_ECAGGR *ecaggr, SCIP_VAR *x, SCIP_VAR *y, SCIP_Real coef)
Definition: sepa_eccuts.c:227
SCIP_Real SCIPnlrowGetLhs(SCIP_NLROW *nlrow)
Definition: nlp.c:3374
static const int poweroftwo[]
Definition: sepa_eccuts.c:71
#define SEPA_USESSUBSCIP
Definition: sepa_eccuts.c:40
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16920
#define DEFAULT_MAXROUNDS
Definition: sepa_eccuts.c:51
#define SEPA_MAXBOUNDDIST
Definition: sepa_eccuts.c:39
int * termvars2
Definition: sepa_eccuts.c:88
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410
default SCIP plugins
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:211
static SCIP_RETCODE ecaggrAddQuadvar(SCIP_ECAGGR *ecaggr, SCIP_VAR *x)
Definition: sepa_eccuts.c:216
static SCIP_RETCODE updateMIP(SCIP *subscip, SCIP_NLROW *nlrow, SCIP_VAR **forwardarcs, SCIP_VAR **backwardarcs, int *quadvar2aggr, int *nedges)
Definition: sepa_eccuts.c:924
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:636
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:38
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:129
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:371
void SCIPaddSquareLinearization(SCIP *scip, SCIP_Real sqrcoef, SCIP_Real refpoint, SCIP_Bool isint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
static SCIP_Bool checkRikun(SCIP *scip, SCIP_ECAGGR *ecaggr, SCIP_Real *fvals, SCIP_Real *facet)
Definition: sepa_eccuts.c:1700
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1824