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-2017 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 email to 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 /** computes a partitioning into edge-concave aggregations for a given (quadratic) nonlinear row; each aggregation has
1281  * to contain a cycle with an odd number of positive weighted edges (good cycles) in the corresponding graph representation
1282  *
1283  * For this we use the following algorithm:
1284  *
1285  * -# use a MIP model based on binary flow variables to compute good cycles and store the implied subgraphs as an e.c. aggr.
1286  * -# if we find a good cycle, store the implied subgraph, delete it from the graph representation and go to 1)
1287  * -# if the MIP model is infeasible (there are no good cycles), STOP
1288  * -# we compute a large clique C if the MIP model fails (because of working limits, etc)
1289  * -# if we find a good cycle in C, store the implied subgraph of C, delete it from the graph representation and go to 1)
1290  * -# if C is not large enough, STOP
1291  */
1292 static
1294  SCIP* scip, /**< SCIP data structure */
1295  SCIP_SEPADATA* sepadata, /**< separator data */
1296  SCIP_NLROW* nlrow, /**< nonlinear row */
1297  SCIP_SOL* sol, /**< current solution (might be NULL) */
1298  SCIP_Bool rhsaggr, /**< consider nonlinear row aggregation for g(x) <= rhs (TRUE) or g(x) >= lhs (FALSE) */
1299  int* quadvar2aggr, /**< array to store for each quadratic variable in which edge-concave
1300  * aggregation it is stored (< 0: in no aggregation); size has to be at
1301  * least SCIPnlrowGetNQuadVars(nlrow) */
1302  int* nfound /**< pointer to store the number of found e.c. aggregations */
1303  )
1304 {
1305  SCIP* subscip;
1306  TCLIQUE_GRAPH* graph;
1307  SCIP_VAR** forwardarcs;
1308  SCIP_VAR** backwardarcs;
1309  SCIP_VAR** quadvars;
1310  SCIP_Real* nodeweights;
1311  SCIP_Real timelimit;
1312  int nquadelems;
1313  int nquadvars;
1314  int nunsucces;
1315  int nedges;
1316  int i;
1317 
1318  assert(quadvar2aggr != NULL);
1319  assert(nfound != NULL);
1320 
1321  quadvars = SCIPnlrowGetQuadVars(nlrow);
1322  nquadvars = SCIPnlrowGetNQuadVars(nlrow);
1323  nquadelems = SCIPnlrowGetNQuadElems(nlrow);
1324 
1325  graph = NULL;
1326  *nfound = 0;
1327  nunsucces = 0;
1328 
1329  /* inititialize mapping from quadvars to e.c. aggregation index (-1: quadvar is in no aggregation); compute node
1330  * weights
1331  */
1332  SCIP_CALL( SCIPallocBufferArray(scip, &nodeweights, nquadvars) );
1333  for( i = 0; i < SCIPnlrowGetNQuadVars(nlrow); ++i )
1334  {
1335  SCIP_VAR* var = quadvars[i];
1336  quadvar2aggr[i] = -1;
1337  nodeweights[i] = phi(scip, SCIPgetSolVal(scip, sol, var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var) );
1338  SCIPdebugMsg(scip, "%s = %e (%e in [%e, %e])\n", SCIPvarGetName(var), nodeweights[i], SCIPgetSolVal(scip, sol, var),
1340  }
1341 
1342  /* create and set up a sub-SCIP */
1343  SCIP_CALL( SCIPcreate(&subscip) );
1344 
1345  /* arrays to store all arc variables of the MIP model; note that we introduce variables even for loops in the graph
1346  * to have an easy mapping from the edges of the graph to the quadratic elements
1347  */
1348  SCIP_CALL( SCIPallocBlockMemoryArray(subscip, &forwardarcs, nquadelems) );
1349  SCIP_CALL( SCIPallocBlockMemoryArray(subscip, &backwardarcs, nquadelems) );
1350 
1351  SCIP_CALL( createMIP(scip, subscip, sepadata, nlrow, rhsaggr, forwardarcs, backwardarcs, nodeweights, &nedges) );
1352  assert(nedges >= 0);
1353  SCIPdebugMsg(scip, "nedges (without loops) = %d\n", nedges);
1354 
1355  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1356 
1357  /* main loop to search for edge-concave aggregations */
1358  while( !SCIPisStopped(scip) )
1359  {
1360  SCIP_Bool aggrleft;
1361  SCIP_Bool found;
1362 
1363  SCIPdebugMsg(scip, "#remaining edges = %d\n", nedges);
1364 
1365  /* not enough edges left */
1366  if( nedges < sepadata->minaggrsize )
1367  break;
1368 
1369  /* check whether there is enough time left; update the remaining time */
1370  if( !SCIPisInfinity(scip, timelimit) )
1371  {
1372  timelimit -= SCIPgetSolvingTime(scip);
1373  if( timelimit <= 0.0 )
1374  {
1375  SCIPdebugMsg(scip, "skip aggregation search since no time left\n");
1376  goto TERMINATE;
1377  }
1378  }
1379 
1380  /* 1.a - search for edge-concave aggregation with the help of the MIP model */
1381  SCIP_CALL( searchEcAggrWithMIP(subscip, timelimit, nedges, &aggrleft, &found) );
1382 
1383  /* 1.b - there are no more edge-concave aggregations left */
1384  if( !aggrleft )
1385  {
1386  SCIPdebugMsg(scip, "no more aggregation left\n");
1387  break;
1388  }
1389 
1390  if( found )
1391  {
1392  SCIP_CALL( storeAggrFromMIP(subscip, nlrow, forwardarcs, backwardarcs, quadvar2aggr, *nfound) );
1393  ++(*nfound);
1394  nunsucces = 0;
1395  }
1396  /* try to find an edge-concave aggregation by computing cliques */
1397  else
1398  {
1399  SCIP_Bool foundaggr;
1400  SCIP_Bool foundclique;
1401 
1402  ++nunsucces;
1403 
1404  /* create graph if necessary */
1405  if( graph == NULL )
1406  {
1407  SCIP_CALL( createTcliqueGraph(scip, nlrow, &graph, nodeweights) );
1408  assert(graph != NULL);
1409  }
1410 
1411  /* 2.a - search and store a single edge-concave aggregation by computing a clique with a good cycle */
1412  SCIP_CALL( searchEcAggrWithCliques(scip, graph, sepadata, nlrow, quadvar2aggr, *nfound, rhsaggr,
1413  &foundaggr, &foundclique) );
1414 
1415  if( foundaggr )
1416  {
1417  assert(foundclique);
1418  ++(*nfound);
1419  nunsucces = 0;
1420  }
1421  else
1422  ++nunsucces;
1423 
1424  /* 2.b - no clique of at least minaggrsize size found */
1425  if( !foundclique )
1426  {
1427  assert(!foundaggr);
1428  SCIPdebugMsg(scip, "did not find a clique to exclude -> leave aggregation search\n");
1429  break;
1430  }
1431  }
1432 
1433  /* leave the algorithm if we did not find something for maxstallrounds many iterations */
1434  if( nunsucces >= sepadata->maxstallrounds && *nfound == 0 )
1435  {
1436  SCIPdebugMsg(scip, "did not find an e.c. aggregation for %d iterations\n", nunsucces);
1437  break;
1438  }
1439 
1440  /* exclude all edges used in the last aggregation and nodes found in the clique solution */
1441  SCIP_CALL( updateMIP(subscip, nlrow, forwardarcs, backwardarcs, quadvar2aggr, &nedges) );
1442  }
1443 
1444 TERMINATE:
1445 
1446 #ifdef SCIP_DEBUG
1447  SCIPdebugMsg(scip, "aggregations found:\n");
1448  for( i = 0; i < nquadvars; ++i )
1449  {
1450  SCIPdebugMsg(scip, " %d in %d\n", i, quadvar2aggr[i]);
1451  }
1452 #endif
1453 
1454  /* free clique graph */
1455  if( graph != NULL )
1456  tcliqueFree(&graph);
1457 
1458  /* free sub-SCIP */
1459  for( i = 0; i < nquadelems; ++i )
1460  {
1461  SCIP_CALL( SCIPreleaseVar(subscip, &forwardarcs[i]) );
1462  SCIP_CALL( SCIPreleaseVar(subscip, &backwardarcs[i]) );
1463  }
1464 
1465  SCIPfreeBlockMemoryArray(subscip, &backwardarcs, nquadelems);
1466  SCIPfreeBlockMemoryArray(subscip, &forwardarcs, nquadelems);
1467  SCIP_CALL( SCIPfree(&subscip) );
1468 
1469  SCIPfreeBufferArray(scip, &nodeweights);
1470 
1471  return SCIP_OKAY;
1472 }
1473 
1474 /** returns whether a given nonlinear row can be used to compute edge-concave aggregations for which their convex
1475  * envelope could dominate the termwise bilinear relaxation; this is the case if there exists at least one cycle with
1476  * an odd number of positive edges in the corresponding graph representation of the nonlinear row
1477  */
1478 static
1480  SCIP* scip, /**< SCIP data structure */
1481  SCIP_SEPADATA* sepadata, /**< separator data */
1482  SCIP_NLROW* nlrow, /**< nonlinear row representation of a nonlinear constraint */
1483  SCIP_Bool* rhscandidate, /**< pointer to store if we should compute edge-concave aggregations for
1484  * the <= rhs case */
1485  SCIP_Bool* lhscandidate /**< pointer to store if we should compute edge-concave aggregations for
1486  * the >= lhs case */
1487  )
1488 {
1489  int* degrees;
1490  int ninterestingnodes;
1491  int nposedges;
1492  int nnegedges;
1493  int i;
1494 
1495  assert(rhscandidate != NULL);
1496  assert(lhscandidate != NULL);
1497 
1498  *rhscandidate = TRUE;
1499  *lhscandidate = TRUE;
1500 
1501  /* skip if the nlrow is not in the NLP, there are other nonlinearities, or too few quadratic variables */
1502  if( !SCIPnlrowIsInNLP(nlrow) || SCIPnlrowGetExprtree(nlrow) != NULL
1503  || SCIPnlrowGetNQuadVars(nlrow) < sepadata->minaggrsize )
1504  {
1505  *rhscandidate = FALSE;
1506  *lhscandidate = FALSE;
1507  return SCIP_OKAY;
1508  }
1509 
1510  /* check for infinite rhs or lhs */
1511  if( SCIPisInfinity(scip, REALABS(SCIPnlrowGetRhs(nlrow))) )
1512  *rhscandidate = FALSE;
1513  if( SCIPisInfinity(scip, REALABS(SCIPnlrowGetLhs(nlrow))) )
1514  *lhscandidate = FALSE;
1515 
1516  SCIP_CALL( SCIPallocBufferArray(scip, &degrees, SCIPnlrowGetNQuadVars(nlrow)) );
1517  BMSclearMemoryArray(degrees, SCIPnlrowGetNQuadVars(nlrow));
1518 
1519  ninterestingnodes = 0;
1520  nposedges = 0;
1521  nnegedges = 0;
1522 
1523  for( i = 0; i < SCIPnlrowGetNQuadElems(nlrow); ++i )
1524  {
1525  SCIP_QUADELEM* quadelem;
1526  SCIP_VAR* x;
1527  SCIP_VAR* y;
1528 
1529  quadelem = &SCIPnlrowGetQuadElems(nlrow)[i];
1530  x = SCIPnlrowGetQuadVars(nlrow)[quadelem->idx1];
1531  y = SCIPnlrowGetQuadVars(nlrow)[quadelem->idx2];
1532 
1533  /* do not consider loops or global fixed variables */
1534  if( quadelem->idx1 != quadelem->idx2
1536  && !SCIPisEQ(scip, SCIPvarGetLbGlobal(y), SCIPvarGetUbGlobal(y)) )
1537  {
1538  ++degrees[quadelem->idx1];
1539  ++degrees[quadelem->idx2];
1540 
1541  /* count the number of nodes with a degree of at least 2 */
1542  if( degrees[quadelem->idx1] == 2 )
1543  ++ninterestingnodes;
1544  if( degrees[quadelem->idx2] == 2 )
1545  ++ninterestingnodes;
1546 
1547  nposedges += SCIPisPositive(scip, quadelem->coef) ? 1 : 0;
1548  nnegedges += SCIPisNegative(scip, quadelem->coef) ? 1 : 0;
1549  }
1550  }
1551 
1552  SCIPfreeBufferArray(scip, &degrees);
1553 
1554  SCIPdebugMsg(scip, "nlrow contains: %d edges\n", nposedges + nnegedges);
1555 
1556  /* too many edges, too few edges, or to few nodes with degree at least 2 in the graph */
1557  if( nposedges + nnegedges > sepadata->maxbilinterms || nposedges + nnegedges < sepadata->minaggrsize
1558  || ninterestingnodes < sepadata->minaggrsize )
1559  {
1560  *rhscandidate = FALSE;
1561  *lhscandidate = FALSE;
1562  return SCIP_OKAY;
1563  }
1564 
1565  /* check if there are enough positive/negative edges; for a 3-clique there has to be an odd number of those edges */
1566  if( nposedges == 0 || (nposedges + nnegedges == 3 && (nposedges % 2) == 0) )
1567  *rhscandidate = FALSE;
1568  if( nnegedges == 0 || (nposedges + nnegedges == 3 && (nnegedges % 2) == 0) )
1569  *lhscandidate = FALSE;
1570 
1571  return SCIP_OKAY;
1572 }
1573 
1574 /** finds and stores edge-concave aggregations for a given nonlinear row */
1575 static
1577  SCIP* scip, /**< SCIP data structure */
1578  SCIP_SEPADATA* sepadata, /**< separator data */
1579  SCIP_NLROW* nlrow, /**< nonlinear row */
1580  SCIP_SOL* sol /**< current solution (might be NULL) */
1581  )
1582 {
1583  int* quadvar2aggr;
1584  SCIP_Bool rhscandidate;
1585  SCIP_Bool lhscandidate;
1586 
1587  assert(scip != NULL);
1588  assert(nlrow != NULL);
1589  assert(sepadata != NULL);
1590 
1591  SCIP_CALL( SCIPallocBufferArray(scip, &quadvar2aggr, SCIPnlrowGetNQuadVars(nlrow)) ); /*lint !e705*/
1592 
1593 #ifdef SCIP_DEBUG
1594  SCIPdebugMsg(scip, "search for edge-concave aggregation for the nonlinear row: \n");
1595  SCIP_CALL( SCIPnlrowPrint(nlrow, SCIPgetMessagehdlr(scip), NULL) );
1596 #endif
1597 
1598  /* check obvious conditions for existing cycles with an odd number of positive/negative edges */
1599  SCIP_CALL( isCandidate(scip, sepadata, nlrow, &rhscandidate, &lhscandidate) );
1600  SCIPdebugMsg(scip, "rhs candidate = %u lhs candidate = %u\n", rhscandidate, lhscandidate);
1601 
1602  /* search for edge-concave aggregations (consider <= rhs) */
1603  if( rhscandidate )
1604  {
1605  SCIP_NLROWAGGR* nlrowaggr;
1606  int nfound;
1607 
1608  assert(!SCIPisInfinity(scip, REALABS(SCIPnlrowGetRhs(nlrow))));
1609 
1610  SCIPdebugMsg(scip, "consider <= rhs\n");
1611  SCIP_CALL( searchEcAggr(scip, sepadata, nlrow, sol, TRUE, quadvar2aggr, &nfound) );
1612 
1613  if( nfound > 0 )
1614  {
1615  SCIP_CALL( nlrowaggrCreate(scip, nlrow, &nlrowaggr, quadvar2aggr, nfound, TRUE) );
1616  assert(nlrow != NULL);
1617  SCIPdebug(nlrowaggrPrint(scip, nlrowaggr));
1618  SCIP_CALL( sepadataAddNlrowaggr(scip, sepadata, nlrowaggr) );
1619  }
1620  }
1621 
1622  /* search for edge-concave aggregations (consider <= lhs) */
1623  if( lhscandidate )
1624  {
1625  SCIP_NLROWAGGR* nlrowaggr;
1626  int nfound;
1627 
1628  assert(!SCIPisInfinity(scip, REALABS(SCIPnlrowGetLhs(nlrow))));
1629 
1630  SCIPdebugMsg(scip, "consider >= lhs\n");
1631  SCIP_CALL( searchEcAggr(scip, sepadata, nlrow, sol, FALSE, quadvar2aggr, &nfound) );
1632 
1633  if( nfound > 0 )
1634  {
1635  SCIP_CALL( nlrowaggrCreate(scip, nlrow, &nlrowaggr, quadvar2aggr, nfound, FALSE) );
1636  assert(nlrow != NULL);
1637  SCIPdebug(nlrowaggrPrint(scip, nlrowaggr));
1638  SCIP_CALL( sepadataAddNlrowaggr(scip, sepadata, nlrowaggr) );
1639  }
1640  }
1641 
1642  SCIPfreeBufferArray(scip, &quadvar2aggr);
1643  return SCIP_OKAY;
1644 }
1645 
1646 /*
1647  * methods to compute edge-concave cuts
1648  */
1649 
1650 #ifdef SCIP_DEBUG
1651 /** prints a given facet (candidate) */
1652 static
1653 void printFacet(
1654  SCIP* scip, /**< SCIP data structure */
1655  SCIP_VAR** vars, /**< variables contained in the edge-concave aggregation */
1656  int nvars, /**< number of variables contained in the edge-concave aggregation */
1657  SCIP_Real* facet, /**< current facet candidate */
1658  SCIP_Real facetval /**< facet evaluated at the current solution */
1659  )
1660 {
1661  int i;
1662 
1663  SCIPdebugMsg(scip, "print facet (val=%e): ", facetval);
1664  for( i = 0; i < nvars; ++i )
1665  SCIPdebugMsgPrint(scip, "%e %s + ", facet[i], SCIPvarGetName(vars[i]));
1666  SCIPdebugMsgPrint(scip, "%e\n", facet[nvars]);
1667 }
1668 #endif
1669 
1670 /** checks if a facet is really an underestimate for all corners of the domain [l,u]; because of numerics it can happen
1671  * that a facet violates a corner of the domain; to make the facet valid we subtract the maximum violation from the
1672  * constant part of the facet; its a good excersise to write a comment describing the gray code...
1673  */
1674 static
1676  SCIP* scip, /**< SCIP data structure */
1677  SCIP_ECAGGR* ecaggr, /**< edge-concave aggregation data */
1678  SCIP_Real* fvals, /**< array containing all corner values of the aggregation */
1679  SCIP_Real* facet /**< current facet candidate (of dimension ecaggr->nvars + 1) */
1680  )
1681 {
1682  SCIP_Real maxviolation;
1683  SCIP_Real val;
1684  unsigned int i;
1685  unsigned int ncorner;
1686  unsigned int prev;
1687 
1688  assert(scip != NULL);
1689  assert(ecaggr != NULL);
1690  assert(fvals != NULL);
1691  assert(facet != NULL);
1692 
1693  ncorner = (unsigned int) poweroftwo[ecaggr->nvars];
1694  maxviolation = 0.0;
1695 
1696  /* check for the origin */
1697  val = facet[ecaggr->nvars];
1698  for( i = 0; i < (unsigned int) ecaggr->nvars; ++i )
1699  val += facet[i] * SCIPvarGetLbLocal(ecaggr->vars[i]);
1700 
1701  /* update maximum violation */
1702  maxviolation = MAX(val - fvals[0], maxviolation);
1703  assert(SCIPisFeasEQ(scip, maxviolation, 0.0));
1704 
1705  prev = 0;
1706  for( i = 1; i < ncorner; ++i )
1707  {
1708  unsigned int gray;
1709  unsigned int diff;
1710  unsigned int pos;
1711 
1712  gray = i ^ (i >> 1);
1713  diff = gray ^ prev;
1714 
1715  /* compute position of unique 1 of diff */
1716  pos = 0;
1717  while( (diff >>= 1) != 0 )
1718  ++pos;
1719 
1720  if( gray > prev )
1721  val += facet[pos] * (SCIPvarGetUbLocal(ecaggr->vars[pos]) - SCIPvarGetLbLocal(ecaggr->vars[pos]));
1722  else
1723  val -= facet[pos] * (SCIPvarGetUbLocal(ecaggr->vars[pos]) - SCIPvarGetLbLocal(ecaggr->vars[pos]));
1724 
1725 
1726  /* update maximum violation */
1727  maxviolation = MAX(val - fvals[gray], maxviolation);
1728  assert(SCIPisFeasEQ(scip, maxviolation, 0.0));
1729 
1730  prev = gray;
1731  }
1732 
1733  SCIPdebugMsg(scip, "maximum violation of facet: %2.8e\n", maxviolation);
1734 
1735  /* there seem to be numerical problems if the violation is too large; in this case we reject the facet */
1736  if( maxviolation > ADJUSTFACETTOL )
1737  return FALSE;
1738 
1739  /* adjust constant part of the facet */
1740  facet[ecaggr->nvars] -= maxviolation;
1741 
1742  return TRUE;
1743 }
1744 
1745 /** set up LP interface to solve LPs to compute the facet of the convex envelope */
1746 static
1748  SCIP* scip, /**< SCIP data structure */
1749  SCIP_SEPADATA* sepadata /**< separation data */
1750  )
1751 {
1752  SCIP_Real* obj;
1753  SCIP_Real* lb;
1754  SCIP_Real* ub;
1755  SCIP_Real* val;
1756  int* beg;
1757  int* ind;
1758  int nnonz;
1759  int ncols;
1760  int nrows;
1761  int i;
1762  int k;
1763 
1764  assert(scip != NULL);
1765  assert(sepadata != NULL);
1766  assert(sepadata->nnlrowaggrs > 0);
1767 
1768  /* LP interface has been already created with enough rows/columns*/
1769  if( sepadata->lpi != NULL && sepadata->lpisize >= sepadata->maxecsize )
1770  return SCIP_OKAY;
1771 
1772  /* size of lpi is too small; reconstruct lpi */
1773  if( sepadata->lpi != NULL )
1774  {
1775  SCIP_CALL( SCIPlpiFree(&sepadata->lpi) );
1776  sepadata->lpi = NULL;
1777  }
1778 
1779  assert(sepadata->lpi == NULL);
1780  SCIP_CALL( SCIPlpiCreate(&(sepadata->lpi), SCIPgetMessagehdlr(scip), "e.c. LP", SCIP_OBJSEN_MINIMIZE) );
1781  sepadata->lpisize = sepadata->maxecsize;
1782 
1783  nrows = sepadata->maxecsize + 1;
1784  ncols = poweroftwo[nrows - 1];
1785  nnonz = (ncols * (nrows + 1)) / 2;
1786  k = 0;
1787 
1788  /* allocate necessary memory */
1789  SCIP_CALL( SCIPallocBufferArray(scip, &obj, ncols) );
1790  SCIP_CALL( SCIPallocBufferArray(scip, &lb, ncols) );
1791  SCIP_CALL( SCIPallocBufferArray(scip, &ub, ncols) );
1792  SCIP_CALL( SCIPallocBufferArray(scip, &beg, ncols) );
1793  SCIP_CALL( SCIPallocBufferArray(scip, &val, nnonz) );
1794  SCIP_CALL( SCIPallocBufferArray(scip, &ind, nnonz) );
1795 
1796  /* calculate nonzero entries in the LP; set obj, lb, and ub to zero */
1797  for( i = 0; i < ncols; ++i )
1798  {
1799  int row;
1800  int a;
1801 
1802  obj[i] = 0.0;
1803  lb[i] = 0.0;
1804  ub[i] = 0.0;
1805 
1806  SCIPdebugMsg(scip, "col %i starts at position %d\n", i, k);
1807  beg[i] = k;
1808  row = 0;
1809  a = 1;
1810 
1811  /* iterate through the bit representation of i */
1812  while( a <= i )
1813  {
1814  if( (a & i) != 0 )
1815  {
1816  val[k] = 1.0;
1817  ind[k] = row;
1818 
1819  SCIPdebugMsg(scip, " val[%d][%d] = 1 (position %d)\n", row, i, k);
1820 
1821  ++k;
1822  }
1823 
1824  a <<= 1; /*lint !e701*/
1825  ++row;
1826  assert(poweroftwo[row] == a);
1827  }
1828 
1829  /* put 1 as a coefficient for sum_{i} \lambda_i = 1 row (last row) */
1830  val[k] = 1.0;
1831  ind[k] = nrows - 1;
1832  ++k;
1833  SCIPdebugMsg(scip, " val[%d][%d] = 1 (position %d)\n", nrows - 1, i, k);
1834  }
1835  assert(k == nnonz);
1836 
1837  /*
1838  * add all columns to the LP interface
1839  * CPLEX needs the row to exist before adding columns, so we create the rows with dummy sides
1840  * note that the assert is not needed once somebody fixes the LPI
1841  */
1842  assert(nrows <= ncols);
1843  SCIP_CALL( SCIPlpiAddRows(sepadata->lpi, nrows, obj, obj, NULL, 0, NULL, NULL, NULL) );
1844  SCIP_CALL( SCIPlpiAddCols(sepadata->lpi, ncols, obj, lb, ub, NULL, nnonz, beg, ind, val) );
1845 
1846  /* free allocated memory */
1847  SCIPfreeBufferArray(scip, &ind);
1848  SCIPfreeBufferArray(scip, &val);
1849  SCIPfreeBufferArray(scip, &beg);
1850  SCIPfreeBufferArray(scip, &ub);
1851  SCIPfreeBufferArray(scip, &lb);
1852  SCIPfreeBufferArray(scip, &obj);
1853 
1854  return SCIP_OKAY;
1855 }
1856 
1857 /** evaluates an edge-concave aggregation at a corner of the domain [l,u] */
1858 static
1860  SCIP_ECAGGR* ecaggr, /**< edge-concave aggregation data */
1861  int k /**< k-th corner */
1862  )
1863 {
1864  SCIP_Real val;
1865  int i;
1866 
1867  assert(ecaggr != NULL);
1868  assert(k >= 0 && k < poweroftwo[ecaggr->nvars]);
1869 
1870  val = 0.0;
1871 
1872  for( i = 0; i < ecaggr->nterms; ++i )
1873  {
1874  SCIP_Real coef;
1875  SCIP_Real bound1;
1876  SCIP_Real bound2;
1877  int idx1;
1878  int idx2;
1879 
1880  idx1 = ecaggr->termvars1[i];
1881  idx2 = ecaggr->termvars2[i];
1882  coef = ecaggr->termcoefs[i];
1883  assert(idx1 >= 0 && idx1 < ecaggr->nvars);
1884  assert(idx2 >= 0 && idx2 < ecaggr->nvars);
1885 
1886  bound1 = ((poweroftwo[idx1]) & k) == 0 ? SCIPvarGetLbLocal(ecaggr->vars[idx1]) : SCIPvarGetUbLocal(ecaggr->vars[idx1]);
1887  bound2 = ((poweroftwo[idx2]) & k) == 0 ? SCIPvarGetLbLocal(ecaggr->vars[idx2]) : SCIPvarGetUbLocal(ecaggr->vars[idx2]);
1888 
1889  val += coef * bound1 * bound2;
1890  }
1891 
1892  return val;
1893 }
1894 
1895 /** returns (val - lb) / (ub - lb) for a in [lb, ub] */
1896 static
1898  SCIP* scip, /**< SCIP data structure */
1899  SCIP_Real lb, /**< lower bound */
1900  SCIP_Real ub, /**< upper bound */
1901  SCIP_Real val /**< value in [lb,ub] */
1902  )
1903 {
1904  assert(scip != NULL);
1905  assert(!SCIPisInfinity(scip, -lb));
1906  assert(!SCIPisInfinity(scip, ub));
1907  assert(!SCIPisInfinity(scip, REALABS(val)));
1908  assert(!SCIPisFeasEQ(scip, ub - lb, 0.0)); /* this would mean that a variable has been fixed */
1909 
1910  /* adjust val */
1911  val = MIN(val, ub);
1912  val = MAX(val, lb);
1913 
1914  val = (val - lb) / (ub - lb);
1915  assert(val >= 0.0 && val <= 1.0);
1916 
1917  return val;
1918 }
1919 
1920 /** computes a facet of the convex envelope of an edge concave aggregation
1921  *
1922  * The algorithm solves the following LP:
1923  * \f{eqnarray}{
1924  * min & \sum_i \lambda_i f(v_i)\\
1925  * s.t. & \sum_i \lambda_i v_i = x\\
1926  * & \sum_i \lambda_i = 1\\
1927  * & \lambda_i \geq 0
1928  * \f}
1929  * 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
1930  * 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
1931  * original space; the dual solution of the LP above are the coefficients of the facet
1932  *
1933  * The complete algorithm works as follows:
1934  *
1935  * -# compute f(v_i) for each corner v_i of [l,u]
1936  * -# set up the described LP for the transformed space
1937  * -# solve the LP and store the resulting facet for the transformed space
1938  * -# transform the facet to original space
1939  * -# adjust and check facet with the algorithm of Rikun et al.
1940  */
1941 static
1943  SCIP* scip, /**< SCIP data structure */
1944  SCIP_SEPADATA* sepadata, /**< separation data */
1945  SCIP_SOL* sol, /**< solution (might be NULL) */
1946  SCIP_ECAGGR* ecaggr, /**< edge-concave aggregation data */
1947  SCIP_Real* facet, /**< array to store the coefficients of the resulting facet; size has to be at least (ecaggr->nvars + 1) */
1948  SCIP_Real* facetval, /**< pointer to store the value of the facet evaluated at the current solution */
1949  SCIP_Bool* success /**< pointer to store if we have found a facet */
1950  )
1951 {
1952  SCIP_Real* fvals;
1953  SCIP_Real* side;
1954  SCIP_Real* lb;
1955  SCIP_Real* ub;
1956  SCIP_Real perturbation;
1957  int* inds;
1958  int ncorner;
1959  int ncols;
1960  int nrows;
1961  int i;
1962 
1963  assert(scip != NULL);
1964  assert(sepadata != NULL);
1965  assert(ecaggr != NULL);
1966  assert(facet != NULL);
1967  assert(facetval != NULL);
1968  assert(success != NULL);
1969  assert(ecaggr->nvars <= sepadata->maxecsize);
1970 
1971  *facetval = -SCIPinfinity(scip);
1972  *success = FALSE;
1973 
1974  /* create LP if this has not been done yet */
1975  SCIP_CALL( createLP(scip, sepadata) );
1976 
1977  assert(sepadata->lpi != NULL);
1978  assert(sepadata->lpisize >= ecaggr->nvars);
1979 
1980  SCIP_CALL( SCIPlpiGetNCols(sepadata->lpi, &ncols) );
1981  SCIP_CALL( SCIPlpiGetNRows(sepadata->lpi, &nrows) );
1982  ncorner = poweroftwo[ecaggr->nvars];
1983 
1984  assert(ncorner <= ncols);
1985  assert(ecaggr->nvars + 1 <= nrows);
1986  assert(nrows <= ncols);
1987 
1988  /* allocate necessary memory */
1989  SCIP_CALL( SCIPallocBufferArray(scip, &fvals, ncols) );
1990  SCIP_CALL( SCIPallocBufferArray(scip, &inds, ncols) );
1991  SCIP_CALL( SCIPallocBufferArray(scip, &lb, ncols) );
1992  SCIP_CALL( SCIPallocBufferArray(scip, &ub, ncols) );
1993  SCIP_CALL( SCIPallocBufferArray(scip, &side, ncols) );
1994 
1995  /*
1996  * 1. compute f(v_i) for each corner v_i of [l,u]
1997  * 2. set up the described LP for the transformed space
1998  */
1999  for( i = 0; i < ncols; ++i )
2000  {
2001  fvals[i] = i < ncorner ? evalCorner(ecaggr, i) : 0.0;
2002  inds[i] = i;
2003 
2004  /* update bounds; fix variables to zero which are currently not in the LP */
2005  lb[i] = 0.0;
2006  ub[i] = i < ncorner ? 1.0 : 0.0;
2007  SCIPdebugMsg(scip, "bounds of LP col %d = [%e, %e]; obj = %e\n", i, lb[i], ub[i], fvals[i]);
2008  }
2009 
2010  /* update lhs and rhs */
2011  perturbation = 0.001;
2012  for( i = 0; i < nrows; ++i )
2013  {
2014  /* note that the last row corresponds to sum_{j} \lambda_j = 1 */
2015  if( i < ecaggr->nvars )
2016  {
2017  SCIP_VAR* x;
2018 
2019  x = ecaggr->vars[i];
2020  assert(x != NULL);
2021 
2022  side[i] = transformValue(scip, SCIPvarGetLbLocal(x), SCIPvarGetUbLocal(x), SCIPgetSolVal(scip, sol, x));
2023 
2024  /* perturb point to enforce an LP solution with ecaggr->nvars + 1 nonzero */
2025  side[i] += side[i] > perturbation ? -perturbation : perturbation;
2026  perturbation /= 1.2;
2027  }
2028  else
2029  {
2030  side[i] = (i == nrows - 1) ? 1.0 : 0.0;
2031  }
2032 
2033  SCIPdebugMsg(scip, "LP row %d in [%e, %e]\n", i, side[i], side[i]);
2034  }
2035 
2036  /* update LP */
2037  SCIP_CALL( SCIPlpiChgObj(sepadata->lpi, ncols, inds, fvals) );
2038  SCIP_CALL( SCIPlpiChgBounds(sepadata->lpi, ncols, inds, lb, ub) );
2039  SCIP_CALL( SCIPlpiChgSides(sepadata->lpi, nrows, inds, side, side) );
2040 
2041  /* free memory used to build the LP */
2042  SCIPfreeBufferArray(scip, &side);
2043  SCIPfreeBufferArray(scip, &ub);
2044  SCIPfreeBufferArray(scip, &lb);
2045  SCIPfreeBufferArray(scip, &inds);
2046 
2047  /*
2048  * 3. solve the LP and store the resulting facet for the transformed space
2049  */
2050  if( USEDUALSIMPLEX ) /*lint !e774 !e506*/
2051  {
2052  SCIP_CALL( SCIPlpiSolveDual(sepadata->lpi) );
2053  }
2054  else
2055  {
2056  SCIP_CALL( SCIPlpiSolvePrimal(sepadata->lpi) );
2057  }
2058 
2059  /* the dual solution corresponds to the coefficients of the facet in the transformed problem; note that it might be
2060  * the case that the dual solution has more components than the facet array
2061  */
2062  if( ecaggr->nvars + 1 == ncols )
2063  {
2064  SCIP_CALL( SCIPlpiGetSol(sepadata->lpi, NULL, NULL, facet, NULL, NULL) );
2065  }
2066  else
2067  {
2068  SCIP_Real* dualsol;
2069 
2070  SCIP_CALL( SCIPallocBufferArray(scip, &dualsol, nrows) );
2071 
2072  /* get the dual solution */
2073  SCIP_CALL( SCIPlpiGetSol(sepadata->lpi, NULL, NULL, dualsol, NULL, NULL) );
2074 
2075  for( i = 0; i < ecaggr->nvars; ++i )
2076  facet[i] = dualsol[i];
2077 
2078  /* constant part of the facet is the last component of the dual solution */
2079  facet[ecaggr->nvars] = dualsol[nrows - 1];
2080 
2081  SCIPfreeBufferArray(scip, &dualsol);
2082  }
2083 
2084 #ifdef SCIP_DEBUG
2085  SCIPdebugMsg(scip, "facet for the transformed problem: ");
2086  for( i = 0; i < ecaggr->nvars; ++i )
2087  {
2088  SCIPdebugMsgPrint(scip, "%3.4e * %s + ", facet[i], SCIPvarGetName(ecaggr->vars[i]));
2089  }
2090  SCIPdebugMsgPrint(scip, "%3.4e\n", facet[ecaggr->nvars]);
2091 #endif
2092 
2093  /*
2094  * 4. transform the facet to original space
2095  * we now have the linear underestimator L(x) = beta^T x + beta_0, which needs to be transform to the original space
2096  * the underestimator in the original space, G(x) = alpha^T x + alpha_0, is given by G(x) = L(T(x)), where T(.) is
2097  * the transformation applied in step 2; therefore,
2098  * alpha_i = beta_i/(ub_i - lb_i)
2099  * alpha_0 = beta_0 - sum_i lb_i * beta_i/(ub_i - lb_i)
2100  */
2101 
2102  SCIPdebugMsg(scip, "facet in orig. space: ");
2103  *facetval = 0.0;
2104 
2105  for( i = 0; i < ecaggr->nvars; ++i )
2106  {
2107  SCIP_Real varlb;
2108  SCIP_Real varub;
2109 
2110  varlb = SCIPvarGetLbLocal(ecaggr->vars[i]);
2111  varub = SCIPvarGetUbLocal(ecaggr->vars[i]);
2112  assert(!SCIPisEQ(scip, varlb, varub));
2113 
2114  /* substract (\beta_i * lb_i) / (ub_i - lb_i) from current alpha_0 */
2115  facet[ecaggr->nvars] -= (facet[i] * varlb) / (varub - varlb);
2116 
2117  /* set \alpha_i := \beta_i / (ub_i - lb_i) */
2118  facet[i] = facet[i] / (varub - varlb);
2119  *facetval += facet[i] * SCIPgetSolVal(scip, sol, ecaggr->vars[i]);
2120 
2121  SCIPdebugMsgPrint(scip, "%3.4e * %s + ", facet[i], SCIPvarGetName(ecaggr->vars[i]));
2122  }
2123 
2124  /* add constant part to the facet value */
2125  *facetval += facet[ecaggr->nvars];
2126  SCIPdebugMsgPrint(scip, "%3.4e\n", facet[ecaggr->nvars]);
2127 
2128  /*
2129  * 5. adjust and check facet with the algorithm of Rikun et al.
2130  */
2131 
2132  if( checkRikun(scip, ecaggr, fvals, facet) )
2133  {
2134  SCIPdebugMsg(scip, "facet pass the check of Rikun et al.\n");
2135  *success = TRUE;
2136  }
2137 
2138  /* free allocated memory */
2139  SCIPfreeBufferArray(scip, &fvals);
2140 
2141  return SCIP_OKAY;
2142 }
2143 
2144 /*
2145  * miscellaneous methods
2146  */
2147 
2148 /** method to add a facet of the convex envelope of an edge-concave aggregation to a given cut */
2149 static
2151  SCIP* scip, /**< SCIP data structure */
2152  SCIP_SOL* sol, /**< current solution (might be NULL) */
2153  SCIP_ROW* cut, /**< current cut (modifiable) */
2154  SCIP_Real* facet, /**< coefficient of the facet (dimension nvars + 1) */
2155  SCIP_VAR** vars, /**< variables of the facet */
2156  int nvars, /**< number of variables in the facet */
2157  SCIP_Real* cutconstant, /**< pointer to update the constant part of the facet */
2158  SCIP_Real* cutactivity, /**< pointer to update the activity of the cut */
2159  SCIP_Bool* success /**< pointer to store if everything went fine */
2160  )
2161 {
2162  int i;
2163 
2164  assert(cut != NULL);
2165  assert(facet != NULL);
2166  assert(vars != NULL);
2167  assert(nvars > 0);
2168  assert(cutconstant != NULL);
2169  assert(cutactivity != NULL);
2170  assert(success != NULL);
2171 
2172  *success = TRUE;
2173 
2174  for( i = 0; i < nvars; ++i )
2175  {
2176  if( SCIPisInfinity(scip, REALABS(facet[i])) )
2177  {
2178  *success = FALSE;
2179  return SCIP_OKAY;
2180  }
2181 
2182  if( !SCIPisZero(scip, facet[i]) )
2183  {
2184  /* add only a constant if the variable has been fixed */
2185  if( SCIPvarGetLbLocal(vars[i]) == SCIPvarGetUbLocal(vars[i]) ) /*lint !e777*/
2186  {
2187  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[i]), SCIPgetSolVal(scip, sol, vars[i])));
2188  *cutconstant += facet[i] * SCIPgetSolVal(scip, sol, vars[i]);
2189  *cutactivity += facet[i] * SCIPgetSolVal(scip, sol, vars[i]);
2190  }
2191  else
2192  {
2193  *cutactivity += facet[i] * SCIPgetSolVal(scip, sol, vars[i]);
2194  SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[i], facet[i]) );
2195  }
2196  }
2197  }
2198 
2199  /* add constant part of the facet */
2200  *cutconstant += facet[nvars];
2201  *cutactivity += facet[nvars];
2202 
2203  return SCIP_OKAY;
2204 }
2205 
2206 /** method to add an linear term to a given cut */
2207 static
2209  SCIP* scip, /**< SCIP data structure */
2210  SCIP_SOL* sol, /**< current solution (might be NULL) */
2211  SCIP_ROW* cut, /**< current cut (modifiable) */
2212  SCIP_VAR* x, /**< linear variable */
2213  SCIP_Real coeff, /**< coefficient */
2214  SCIP_Real* cutconstant, /**< pointer to update the constant part of the facet */
2215  SCIP_Real* cutactivity, /**< pointer to update the activity of the cut */
2216  SCIP_Bool* success /**< pointer to store if everything went fine */
2217  )
2218 {
2219  SCIP_Real activity;
2220 
2221  assert(cut != NULL);
2222  assert(x != NULL);
2223  assert(!SCIPisZero(scip, coeff));
2224  assert(!SCIPisInfinity(scip, coeff));
2225  assert(cutconstant != NULL);
2226  assert(cutactivity != NULL);
2227  assert(success != NULL);
2228 
2229  *success = TRUE;
2230  activity = SCIPgetSolVal(scip, sol, x) * coeff;
2231 
2232  /* do not add a term if the activity is -infinity */
2233  if( SCIPisInfinity(scip, -1.0 * REALABS(activity)) )
2234  {
2235  *success = FALSE;
2236  return SCIP_OKAY;
2237  }
2238 
2239  /* add activity to the constant part if the variable has been fixed */
2240  if( SCIPvarGetLbLocal(x) == SCIPvarGetUbLocal(x) ) /*lint !e777*/
2241  {
2242  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(x), SCIPgetSolVal(scip, sol, x)));
2243  *cutconstant += activity;
2244  SCIPdebugMsg(scip, "add to cut: %e\n", activity);
2245  }
2246  else
2247  {
2248  SCIP_CALL( SCIPaddVarToRow(scip, cut, x, coeff) );
2249  SCIPdebugMsg(scip, "add to cut: %e * %s\n", coeff, SCIPvarGetName(x));
2250  }
2251 
2252  *cutactivity += activity;
2253 
2254  return SCIP_OKAY;
2255 }
2256 
2257 /** method to add an underestimate of a bilinear term to a given cut */
2258 static
2260  SCIP* scip, /**< SCIP data structure */
2261  SCIP_SOL* sol, /**< current solution (might be NULL) */
2262  SCIP_ROW* cut, /**< current cut (modifiable) */
2263  SCIP_VAR* x, /**< first bilinear variable */
2264  SCIP_VAR* y, /**< seconds bilinear variable */
2265  SCIP_Real coeff, /**< coefficient */
2266  SCIP_Real* cutconstant, /**< pointer to update the constant part of the facet */
2267  SCIP_Real* cutactivity, /**< pointer to update the activity of the cut */
2268  SCIP_Bool* success /**< pointer to store if everything went fine */
2269  )
2270 {
2271  SCIP_Real activity;
2272 
2273  assert(cut != NULL);
2274  assert(x != NULL);
2275  assert(y != NULL);
2276  assert(!SCIPisZero(scip, coeff));
2277  assert(cutconstant != NULL);
2278  assert(cutactivity != NULL);
2279  assert(success != NULL);
2280 
2281  *success = TRUE;
2282  activity = coeff * SCIPgetSolVal(scip, sol, x) * SCIPgetSolVal(scip, sol, y);
2283 
2284  if( SCIPisInfinity(scip, REALABS(coeff)) )
2285  {
2286  *success = FALSE;
2287  return SCIP_OKAY;
2288  }
2289 
2290  /* do not add a term if the activity is -infinity */
2291  if( SCIPisInfinity(scip, -1.0 * REALABS(activity)) )
2292  {
2293  *success = FALSE;
2294  return SCIP_OKAY;
2295  }
2296 
2297  /* quadratic case */
2298  if( x == y )
2299  {
2300  SCIP_Real refpoint;
2301  SCIP_Real lincoef;
2302  SCIP_Real linconst;
2303 
2304  lincoef = 0.0;
2305  linconst = 0.0;
2306  refpoint = SCIPgetSolVal(scip, sol, x);
2307 
2308  /* adjust the reference point */
2309  refpoint = SCIPisLT(scip, refpoint, SCIPvarGetLbLocal(x)) ? SCIPvarGetLbLocal(x) : refpoint;
2310  refpoint = SCIPisGT(scip, refpoint, SCIPvarGetUbLocal(x)) ? SCIPvarGetUbLocal(x) : refpoint;
2311  assert(SCIPisLE(scip, refpoint, SCIPvarGetUbLocal(x)) && SCIPisGE(scip, refpoint, SCIPvarGetLbLocal(x)));
2312 
2313  if( SCIPisPositive(scip, coeff) )
2314  SCIPaddSquareLinearization(scip, coeff, refpoint, SCIPvarIsIntegral(x), &lincoef, &linconst, success);
2315  else
2316  SCIPaddSquareSecant(scip, coeff, SCIPvarGetLbLocal(x), SCIPvarGetUbLocal(x), refpoint, &lincoef, &linconst, success);
2317 
2318  *cutactivity += lincoef * refpoint + linconst;
2319  *cutconstant += linconst;
2320 
2321  /* add underestimate to cut */
2322  SCIP_CALL( SCIPaddVarToRow(scip, cut, x, lincoef) );
2323 
2324  SCIPdebugMsg(scip, "add to cut: %e * %s + %e\n", lincoef, SCIPvarGetName(x), linconst);
2325  }
2326  /* bilinear case */
2327  else
2328  {
2329  SCIP_Real refpointx;
2330  SCIP_Real refpointy;
2331  SCIP_Real lincoefx;
2332  SCIP_Real lincoefy;
2333  SCIP_Real linconst;
2334 
2335  lincoefx = 0.0;
2336  lincoefy = 0.0;
2337  linconst = 0.0;
2338  refpointx = SCIPgetSolVal(scip, sol, x);
2339  refpointy = SCIPgetSolVal(scip, sol, y);
2340 
2341  /* adjust the reference points */
2342  refpointx = SCIPisLT(scip, refpointx, SCIPvarGetLbLocal(x)) ? SCIPvarGetLbLocal(x) : refpointx;
2343  refpointx = SCIPisGT(scip, refpointx, SCIPvarGetUbLocal(x)) ? SCIPvarGetUbLocal(x) : refpointx;
2344  refpointy = SCIPisLT(scip, refpointy, SCIPvarGetLbLocal(y)) ? SCIPvarGetLbLocal(y) : refpointy;
2345  refpointy = SCIPisGT(scip, refpointy, SCIPvarGetUbLocal(y)) ? SCIPvarGetUbLocal(y) : refpointy;
2346  assert(SCIPisLE(scip, refpointx, SCIPvarGetUbLocal(x)) && SCIPisGE(scip, refpointx, SCIPvarGetLbLocal(x)));
2347  assert(SCIPisLE(scip, refpointy, SCIPvarGetUbLocal(y)) && SCIPisGE(scip, refpointy, SCIPvarGetLbLocal(y)));
2348 
2350  SCIPvarGetUbLocal(y), refpointy, FALSE, &lincoefx, &lincoefy, &linconst, success);
2351 
2352  *cutactivity += lincoefx * refpointx + lincoefy * refpointy + linconst;
2353  *cutconstant += linconst;
2354 
2355  /* add underestimate to cut */
2356  SCIP_CALL( SCIPaddVarToRow(scip, cut, x, lincoefx) );
2357  SCIP_CALL( SCIPaddVarToRow(scip, cut, y, lincoefy) );
2358 
2359  SCIPdebugMsg(scip, "add to cut: %e * %s + %e * %s + %e\n", lincoefx, SCIPvarGetName(x), lincoefy,
2360  SCIPvarGetName(y), linconst);
2361  }
2362 
2363  return SCIP_OKAY;
2364 }
2365 
2366 /** method to compute and and a cut for a nonlinear row aggregation and a given solution; we compute for each edge
2367  * concave aggregation one facet; the remaining bilinear terms will be underestimated with McCormick, secants or
2368  * linearizations; constant and linear terms will be added to the cut directly
2369  */
2370 static
2372  SCIP* scip, /**< SCIP data structure */
2373  SCIP_SEPA* sepa, /**< separator */
2374  SCIP_SEPADATA* sepadata, /**< separator data */
2375  SCIP_NLROWAGGR* nlrowaggr, /**< nonlinear row aggregation */
2376  SCIP_SOL* sol, /**< current solution (might be NULL) */
2377  SCIP_Bool* separated, /**< pointer to store if we could separate the current solution */
2378  SCIP_Bool* cutoff /**< pointer to store if the current node gets cut off */
2379  )
2380 {
2381  SCIP_ROW* cut;
2382  SCIP_Real* bestfacet;
2383  SCIP_Real bestfacetval;
2384  SCIP_Real cutconstant;
2385  SCIP_Real cutactivity;
2386  int bestfacetsize;
2387  char cutname[SCIP_MAXSTRLEN];
2388  SCIP_Bool found;
2389  SCIP_Bool islocalcut;
2390  int i;
2391 
2392  assert(separated != NULL);
2393  assert(cutoff != NULL);
2394  assert(nlrowaggr->necaggr > 0);
2395  assert(nlrowaggr->nlrow != NULL);
2396  assert(SCIPnlrowIsInNLP(nlrowaggr->nlrow));
2397 
2398  *separated = FALSE;
2399  *cutoff = FALSE;
2400  islocalcut = SCIPgetDepth(scip) != 0;
2401 
2402  /* create the cut */
2403  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "ec");
2404  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), SCIPinfinity(scip), islocalcut, FALSE,
2405  sepadata->dynamiccuts) );
2406  SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
2407 
2408  /* track rhs and activity of the cut */
2409  cutconstant = nlrowaggr->constant;
2410  cutactivity = 0.0;
2411 
2412  /* allocate necessary memory */
2413  bestfacetsize = sepadata->maxaggrsize + 1;
2414  SCIP_CALL( SCIPallocBufferArray(scip, &bestfacet, bestfacetsize) );
2415 
2416 #ifdef SCIP_DEBUG
2417  SCIP_CALL( SCIPnlrowPrint(nlrowaggr->nlrow, SCIPgetMessagehdlr(scip), NULL) );
2418 
2419  SCIPdebugMsg(scip, "current solution:\n");
2420  for( i = 0; i < SCIPgetNVars(scip); ++i )
2421  {
2422  SCIP_VAR* var = SCIPgetVars(scip)[i];
2423  SCIPdebugMsg(scip, " %s = [%e, %e] solval = %e\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var),
2424  SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var));
2425  }
2426 #endif
2427 
2428  /* compute a facet for each edge-concave aggregation */
2429  for( i = 0; i < nlrowaggr->necaggr; ++i )
2430  {
2431  SCIP_ECAGGR* ecaggr;
2432  SCIP_Bool success;
2433 
2434  ecaggr = nlrowaggr->ecaggr[i];
2435  assert(ecaggr != NULL);
2436 
2437  /* compute a facet of the convex envelope */
2438  SCIP_CALL( SCIPcomputeConvexEnvelopeFacet(scip, sepadata, sol, ecaggr, bestfacet, &bestfacetval, &found) );
2439 
2440  SCIPdebugMsg(scip, "found facet for edge-concave aggregation %d/%d ? %s\n", i, nlrowaggr->necaggr,
2441  found ? "yes" : "no");
2442 
2443 #ifdef SCIP_DEBUG
2444  if( found )
2445  printFacet(scip, ecaggr->vars, ecaggr->nvars, bestfacet, bestfacetval);
2446 #endif
2447 
2448  /* do not add any cut because we did not found a facet for at least one edge-concave aggregation */
2449  if( !found ) /*lint !e774*/
2450  goto TERMINATE;
2451 
2452  /* add facet to the cut and update the rhs and activity of the cut */
2453  SCIP_CALL( addFacetToCut(scip, sol, cut, bestfacet, ecaggr->vars, ecaggr->nvars, &cutconstant, &cutactivity,
2454  &success) );
2455 
2456  if( !success )
2457  goto TERMINATE;
2458  }
2459 
2460  /* compute an underestimate for each bilinear term which is not in any edge-concave aggregation */
2461  for( i = 0; i < nlrowaggr->nremterms; ++i )
2462  {
2463  SCIP_VAR* x;
2464  SCIP_VAR* y;
2465  SCIP_Bool success;
2466 
2467  x = nlrowaggr->remtermvars1[i];
2468  y = nlrowaggr->remtermvars2[i];
2469  assert(x != NULL);
2470  assert(y != NULL);
2471 
2472  SCIP_CALL( addBilinearTermToCut(scip, sol, cut, x, y, nlrowaggr->remtermcoefs[i], &cutconstant, &cutactivity,
2473  &success) );
2474 
2475  if( !success )
2476  goto TERMINATE;
2477  }
2478 
2479  /* add all linear terms to the cut */
2480  for( i = 0; i < nlrowaggr->nlinvars; ++i )
2481  {
2482  SCIP_VAR* x;
2483  SCIP_Real coef;
2484  SCIP_Bool success;
2485 
2486  x = nlrowaggr->linvars[i];
2487  assert(x != NULL);
2488 
2489  coef = nlrowaggr->lincoefs[i];
2490 
2491  SCIP_CALL( addLinearTermToCut(scip, sol, cut, x, coef, &cutconstant, &cutactivity, &success) );
2492 
2493  if( !success )
2494  goto TERMINATE;
2495  }
2496 
2497  SCIPdebugMsg(scip, "cut activity = %e rhs(nlrow) = %e\n", cutactivity, nlrowaggr->rhs);
2498 
2499  /* set rhs of the cut (substract the constant part of the cut) */
2500  SCIP_CALL( SCIPchgRowRhs(scip, cut, nlrowaggr->rhs - cutconstant) );
2501  SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
2502 
2503  /* check activity of the row; this assert can fail because of numerics */
2504  /* assert(SCIPisFeasEQ(scip, cutactivity - cutconstant, SCIPgetRowSolActivity(scip, cut, sol)) ); */
2505 
2506 #ifdef SCIP_DEBUG
2507  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
2508 #endif
2509 
2510  SCIPdebugMsg(scip, "EC cut <%s>: act=%f eff=%f rank=%d range=%e\n",
2511  SCIProwGetName(cut), SCIPgetRowSolActivity(scip, cut, sol), SCIPgetCutEfficacy(scip, sol, cut),
2512  SCIProwGetRank(cut), SCIPgetRowMaxCoef(scip, cut) / SCIPgetRowMinCoef(scip, cut) );
2513 
2514  /* try to add the cut has a finite rhs, is efficacious, and does not exceed the maximum cut range */
2515  if( !SCIPisInfinity(scip, nlrowaggr->rhs - cutconstant) && SCIPisCutEfficacious(scip, sol, cut)
2516  && SCIPgetRowMaxCoef(scip, cut) / SCIPgetRowMinCoef(scip, cut) < sepadata->cutmaxrange )
2517  {
2518  /* add the cut if it is separating the given solution by at least minviolation */
2519  if( SCIPisGE(scip, cutactivity - nlrowaggr->rhs, sepadata->minviolation) )
2520  {
2521  SCIP_CALL( SCIPaddCut(scip, sol, cut, FALSE, cutoff) );
2522  *separated = TRUE;
2523  SCIPdebugMsg(scip, "added separating cut\n");
2524  }
2525 
2526  if( !(*cutoff) && !islocalcut )
2527  {
2528  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
2529  SCIPdebugMsg(scip, "added cut to cut pool\n");
2530  }
2531  }
2532 
2533 TERMINATE:
2534  /* free allocated memory */
2535  SCIPfreeBufferArray(scip, &bestfacet);
2536 
2537  /* release the row */
2538  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
2539 
2540  return SCIP_OKAY;
2541 }
2542 
2543 /** returns whether it is possible to compute a cut for a given nonlinear row aggregation */
2544 static
2546  SCIP* scip, /**< SCIP data structure */
2547  SCIP_SOL* sol, /**< current solution (might be NULL) */
2548  SCIP_NLROWAGGR* nlrowaggr /**< nonlinear row aggregation */
2549  )
2550 {
2551  int i;
2552 
2553  assert(scip != NULL);
2554  assert(nlrowaggr != NULL);
2555 
2556  if( !SCIPnlrowIsInNLP(nlrowaggr->nlrow) )
2557  {
2558  SCIPdebugMsg(scip, "nlrow is not in NLP anymore\n");
2559  return FALSE;
2560  }
2561 
2562  for( i = 0; i < nlrowaggr->nquadvars; ++i )
2563  {
2564  SCIP_VAR* var = nlrowaggr->quadvars[i];
2565  assert(var != NULL);
2566 
2567  /* check whether the variable has infinite bounds */
2569  || SCIPisInfinity(scip, REALABS(SCIPgetSolVal(scip, sol, var))) )
2570  {
2571  SCIPdebugMsg(scip, "nlrow aggregation contains unbounded variables\n");
2572  return FALSE;
2573  }
2574 
2575  /* check whether the variable has been fixed and is in one edge-concave aggregation */
2576  if( nlrowaggr->quadvar2aggr[i] >= 0 && SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
2577  {
2578  SCIPdebugMsg(scip, "nlrow aggregation contains fixed variables in an e.c. aggregation\n");
2579  return FALSE;
2580  }
2581  }
2582 
2583  return TRUE;
2584 }
2585 
2586 /** searches and tries to add edge-concave cuts */
2587 static
2589  SCIP* scip, /**< SCIP data structure */
2590  SCIP_SEPA* sepa, /**< separator */
2591  SCIP_SEPADATA* sepadata, /**< separator data */
2592  SCIP_SOL* sol, /**< current solution */
2593  SCIP_RESULT* result /**< pointer to store the result of the separation call */
2594  )
2595 {
2596  int nmaxcuts;
2597  int ncuts;
2598  int i;
2599 
2600  assert(*result == SCIP_DIDNOTRUN);
2601 
2602  SCIPdebugMsg(scip, "separate cuts...\n");
2603 
2604  /* skip if there are no nonlinear row aggregations */
2605  if( sepadata->nnlrowaggrs == 0 )
2606  {
2607  SCIPdebugMsg(scip, "no aggregations exists -> skip call\n");
2608  return SCIP_OKAY;
2609  }
2610 
2611  /* get the maximal number of cuts allowed in a separation round */
2612  nmaxcuts = SCIPgetDepth(scip) == 0 ? sepadata->maxsepacutsroot : sepadata->maxsepacuts;
2613  ncuts = 0;
2614 
2615  /* try to compute cuts for each nonlinear row independently */
2616  for( i = 0; i < sepadata->nnlrowaggrs && ncuts < nmaxcuts && !SCIPisStopped(scip); ++i )
2617  {
2618  SCIP_NLROWAGGR* nlrowaggr;
2619  SCIP_Bool separated;
2620  SCIP_Bool cutoff;
2621 
2622  nlrowaggr = sepadata->nlrowaggrs[i];
2623  assert(nlrowaggr != NULL);
2624 
2625  /* skip nonlinear aggregations for which it is obviously not possible to compute a cut */
2626  if( !isPossibleToComputeCut(scip, sol, nlrowaggr) )
2627  return SCIP_OKAY;
2628 
2629  *result = (*result == SCIP_DIDNOTRUN) ? SCIP_DIDNOTFIND : *result;
2630 
2631  SCIPdebugMsg(scip, "try to compute a cut for nonlinear row aggregation %d\n", i);
2632 
2633  /* compute and add cut */
2634  SCIP_CALL( computeCut(scip, sepa, sepadata, nlrowaggr, sol, &separated, &cutoff) );
2635  SCIPdebugMsg(scip, "found a cut: %s cutoff: %s\n", separated ? "yes" : "no", cutoff ? "yes" : "no");
2636 
2637  /* stop if the current node gets cut off */
2638  if( cutoff )
2639  {
2640  assert(separated);
2641  *result = SCIP_CUTOFF;
2642  return SCIP_OKAY;
2643  }
2644 
2645  /* do not compute more cuts if we already separated the given solution */
2646  if( separated )
2647  {
2648  assert(!cutoff);
2649  *result = SCIP_SEPARATED;
2650  ++ncuts;
2651  }
2652  }
2653 
2654  return SCIP_OKAY;
2655 }
2656 
2657 /*
2658  * Callback methods of separator
2659  */
2660 
2661 /** copy method for separator plugins (called when SCIP copies plugins) */
2662 static
2663 SCIP_DECL_SEPACOPY(sepaCopyEccuts)
2664 { /*lint --e{715}*/
2665  assert(scip != NULL);
2666  assert(sepa != NULL);
2667  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2668 
2669  /* call inclusion method of constraint handler */
2671 
2672  return SCIP_OKAY;
2673 }
2674 
2675 /** destructor of separator to free user data (called when SCIP is exiting) */
2676 static
2677 SCIP_DECL_SEPAFREE(sepaFreeEccuts)
2678 { /*lint --e{715}*/
2679  SCIP_SEPADATA* sepadata;
2680 
2681  sepadata = SCIPsepaGetData(sepa);
2682  assert(sepadata != NULL);
2683 
2684  SCIP_CALL( sepadataFree(scip, &sepadata) );
2685  SCIPsepaSetData(sepa, NULL);
2686 
2687  return SCIP_OKAY;
2688 }
2689 
2690 /** solving process deinitialization method of separator (called before branch and bound process data is freed) */
2691 static
2692 SCIP_DECL_SEPAEXITSOL(sepaExitsolEccuts)
2693 { /*lint --e{715}*/
2694  SCIP_SEPADATA* sepadata;
2695 
2696  sepadata = SCIPsepaGetData(sepa);
2697  assert(sepadata != NULL);
2698 
2699  /* print statistics */
2700 #ifdef SCIP_STATISTIC
2701  SCIPstatisticMessage("rhs-AGGR %d\n", sepadata->nrhsnlrowaggrs);
2702  SCIPstatisticMessage("lhs-AGGR %d\n", sepadata->nlhsnlrowaggrs);
2703  SCIPstatisticMessage("aggr. search time = %f\n", sepadata->aggrsearchtime);
2704 #endif
2705 
2706  /* free nonlinear row aggregations */
2707  SCIP_CALL( sepadataFreeNlrows(scip, sepadata) );
2708 
2709  /* mark that we should search again for nonlinear row aggregations */
2710  sepadata->searchedforaggr = FALSE;
2711 
2712  SCIPdebugMsg(scip, "exitsol\n");
2713 
2714  return SCIP_OKAY;
2715 }
2716 
2717 /** LP solution separation method of separator */
2718 static
2719 SCIP_DECL_SEPAEXECLP(sepaExeclpEccuts)
2720 { /*lint --e{715}*/
2721  SCIP_SEPADATA* sepadata;
2722  int depth;
2723  int ncalls;
2724 
2725  sepadata = SCIPsepaGetData(sepa);
2726  assert(sepadata != NULL);
2727 
2728  *result = SCIP_DIDNOTRUN;
2729 
2730  /* check min- and maximal aggregation size */
2731  if( sepadata->maxaggrsize < sepadata->minaggrsize )
2732  return SCIP_PARAMETERWRONGVAL;
2733 
2734  /* only call separator, if we are not close to terminating */
2735  if( SCIPisStopped(scip) )
2736  return SCIP_OKAY;
2737 
2738  /* skip if the LP is not constructed yet */
2739  if( !SCIPisNLPConstructed(scip) )
2740  {
2741  SCIPdebugMsg(scip, "Skip since NLP is not constructed yet.\n");
2742  return SCIP_OKAY;
2743  }
2744 
2745  depth = SCIPgetDepth(scip);
2746 
2747  /* only call separator up to a maximum depth */
2748  if ( sepadata->maxdepth >= 0 && depth > sepadata->maxdepth )
2749  return SCIP_OKAY;
2750 
2751  /* only call separator a given number of times at each node */
2752  ncalls = SCIPsepaGetNCallsAtNode(sepa);
2753  if ( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
2754  || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
2755  return SCIP_OKAY;
2756 
2757  /* search for nonlinear row aggregations */
2758  if( !sepadata->searchedforaggr )
2759  {
2760  int i;
2761 
2762  SCIPstatistic( sepadata->aggrsearchtime -= SCIPgetTotalTime(scip) );
2763 
2764  SCIPdebugMsg(scip, "search for nonlinear row aggregations\n");
2765  for( i = 0; i < SCIPgetNNLPNlRows(scip) && !SCIPisStopped(scip); ++i )
2766  {
2767  SCIP_NLROW* nlrow = SCIPgetNLPNlRows(scip)[i];
2768  SCIP_CALL( findAndStoreEcAggregations(scip, sepadata, nlrow, NULL) );
2769  }
2770  sepadata->searchedforaggr = TRUE;
2771 
2772  SCIPstatistic( sepadata->aggrsearchtime += SCIPgetTotalTime(scip) );
2773  }
2774 
2775  /* search for edge-concave cuts */
2776  SCIP_CALL( separateCuts(scip, sepa, sepadata, NULL, result) );
2777 
2778  return SCIP_OKAY;
2779 }
2780 
2781 /*
2782  * separator specific interface methods
2783  */
2784 
2785 /** creates the edge concave separator and includes it in SCIP */
2787  SCIP* scip /**< SCIP data structure */
2788  )
2789 {
2790  SCIP_SEPADATA* sepadata;
2791  SCIP_SEPA* sepa;
2792 
2793  /* create eccuts separator data */
2794  SCIP_CALL( sepadataCreate(scip, &sepadata) );
2795 
2796  /* include separator */
2798  SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpEccuts, NULL, sepadata) );
2799 
2800  assert(sepa != NULL);
2801 
2802  /* set non fundamental callbacks via setter functions */
2803  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyEccuts) );
2804  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeEccuts) );
2805  SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolEccuts) );
2806 
2807  /* add eccuts separator parameters */
2809  "separating/" SEPA_NAME "/dynamiccuts",
2810  "should generated cuts be removed from the LP if they are no longer tight?",
2811  &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
2812 
2813  SCIP_CALL( SCIPaddIntParam(scip,
2814  "separating/" SEPA_NAME "/maxrounds",
2815  "maximal number of eccuts separation rounds per node (-1: unlimited)",
2816  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
2817 
2818  SCIP_CALL( SCIPaddIntParam(scip,
2819  "separating/" SEPA_NAME "/maxroundsroot",
2820  "maximal number of eccuts separation rounds in the root node (-1: unlimited)",
2821  &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
2822 
2823  SCIP_CALL( SCIPaddIntParam(scip,
2824  "separating/" SEPA_NAME "/maxdepth",
2825  "maximal depth at which the separator is applied (-1: unlimited)",
2826  &sepadata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
2827 
2828  SCIP_CALL( SCIPaddIntParam(scip,
2829  "separating/" SEPA_NAME "/maxsepacuts",
2830  "maximal number of edge-concave cuts separated per separation round",
2831  &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
2832 
2833  SCIP_CALL( SCIPaddIntParam(scip,
2834  "separating/" SEPA_NAME "/maxsepacutsroot",
2835  "maximal number of edge-concave cuts separated per separation round in the root node",
2836  &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
2837 
2838  SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/cutmaxrange",
2839  "maximal coef. range of a cut (max coef. divided by min coef.) in order to be added to LP relaxation",
2840  &sepadata->cutmaxrange, FALSE, DEFAULT_CUTMAXRANGE, 0.0, SCIPinfinity(scip), NULL, NULL) );
2841 
2842  SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/minviolation",
2843  "minimal violation of an edge-concave cut to be separated",
2844  &sepadata->minviolation, FALSE, DEFAULT_MINVIOLATION, 0.0, 0.5, NULL, NULL) );
2845 
2846  SCIP_CALL( SCIPaddIntParam(scip,
2847  "separating/" SEPA_NAME "/minaggrsize",
2848  "search for edge-concave aggregations of at least this size",
2849  &sepadata->minaggrsize, TRUE, DEFAULT_MINAGGRSIZE, 3, 5, NULL, NULL) );
2850 
2851  SCIP_CALL( SCIPaddIntParam(scip,
2852  "separating/" SEPA_NAME "/maxaggrsize",
2853  "search for edge-concave aggregations of at most this size",
2854  &sepadata->maxaggrsize, TRUE, DEFAULT_MAXAGGRSIZE, 3, 5, NULL, NULL) );
2855 
2856  SCIP_CALL( SCIPaddIntParam(scip,
2857  "separating/" SEPA_NAME "/maxbilinterms",
2858  "maximum number of bilinear terms allowed to be in a quadratic constraint",
2859  &sepadata->maxbilinterms, TRUE, DEFAULT_MAXBILINTERMS, 0, INT_MAX, NULL, NULL) );
2860 
2861  SCIP_CALL( SCIPaddIntParam(scip,
2862  "separating/" SEPA_NAME "/maxstallrounds",
2863  "maximum number of unsuccessful rounds in the edge-concave aggregation search",
2864  &sepadata->maxstallrounds, TRUE, DEFAULT_MAXSTALLROUNDS, 0, INT_MAX, NULL, NULL) );
2865 
2866  return SCIP_OKAY;
2867 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21975
#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:2590
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:21964
int * quadvar2aggr
Definition: sepa_eccuts.c:109
SCIP_Bool rhsaggr
Definition: sepa_eccuts.c:98
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip.c:31194
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:45371
enum TCLIQUE_Status TCLIQUE_STATUS
Definition: tclique.h:57
SCIP_RETCODE SCIPnlrowPrint(SCIP_NLROW *nlrow, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: nlp.c:2289
#define narcs
Definition: gastrans.c:68
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21958
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip.c:30965
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30363
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
SCIP_RETCODE SCIPlpiSolveDual(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:1726
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:2152
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46320
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:38
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30386
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:17169
#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.c:4461
#define SCIP_MAXSTRLEN
Definition: def.h:225
static SCIP_DECL_SEPACOPY(sepaCopyEccuts)
Definition: sepa_eccuts.c:2665
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:30418
#define CLIQUE_MINWEIGHT
Definition: sepa_eccuts.c:46
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:46110
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17225
static SCIP_DECL_SEPAEXITSOL(sepaExitsolEccuts)
Definition: sepa_eccuts.c:2694
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46037
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
#define CLIQUE_MAXNTREENODES
Definition: sepa_eccuts.c:47
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16450
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.c:18461
int varsize
Definition: sepa_eccuts.c:84
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)
Definition: lpi_clp.cpp:649
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:1944
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.c:5078
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2764
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)
Definition: scip.c:46050
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:46122
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:632
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPlpiFree(SCIP_LPI **lpi)
Definition: lpi_clp.cpp:549
SCIP_RETCODE SCIPlpiChgObj(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *obj)
Definition: lpi_clp.cpp:1099
#define SCIPstatisticMessage
Definition: pub_message.h:104
int SCIPnlrowGetNQuadVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3275
SCIP_Real SCIPnlrowGetRhs(SCIP_NLROW *nlrow)
Definition: nlp.c:3383
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.c:17394
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:3245
edge concave cut separator
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
SCIP_VAR ** quadvars
Definition: sepa_eccuts.c:108
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip.c:1228
tclique user interface
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45985
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:696
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21956
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip.c:7402
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip.c:4776
SCIP_RETCODE SCIPlpiGetNCols(SCIP_LPI *lpi, int *ncols)
Definition: lpi_clp.cpp:1294
#define SCIPdebugMsgPrint
Definition: scip.h:452
#define SCIPdebugMsg
Definition: scip.h:451
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.c:4237
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip.c:9874
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip.c:31172
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30621
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:543
int SCIPnlrowGetNQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3322
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:2996
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:17179
static SCIP_Bool isPossibleToComputeCut(SCIP *scip, SCIP_SOL *sol, SCIP_NLROWAGGR *nlrowaggr)
Definition: sepa_eccuts.c:2547
#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:5685
SCIP_Real coef
Definition: type_expr.h:102
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:33891
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip.c:10934
SCIP_RETCODE SCIPlpiGetNRows(SCIP_LPI *lpi, int *nrows)
Definition: lpi_clp.cpp:1276
SCIP_Bool SCIPnlrowIsInNLP(SCIP_NLROW *nlrow)
Definition: nlp.c:3432
SCIP_VAR ** SCIPnlrowGetQuadVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3285
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:15846
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)
Definition: scip.c:33188
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30603
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12459
SCIP_VAR ** vars
Definition: sepa_eccuts.c:82
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45998
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:759
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip.c:921
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45753
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21795
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:16555
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:2797
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:553
SCIP_RETCODE SCIPlpiChgSides(SCIP_LPI *lpi, int nrows, const int *ind, const SCIP_Real *lhs, const SCIP_Real *rhs)
Definition: lpi_clp.cpp:1028
#define NULL
Definition: lpi_spx1.cpp:137
#define REALABS(x)
Definition: def.h:169
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:2261
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:3332
#define DEFAULT_MAXAGGRSIZE
Definition: sepa_eccuts.c:61
#define DEFAULT_CUTMAXRANGE
Definition: sepa_eccuts.c:56
#define SCIP_CALL(x)
Definition: def.h:316
int termsize
Definition: sepa_eccuts.c:90
int nlinvars
Definition: sepa_eccuts.c:106
SCIP_Real * lincoefs
Definition: sepa_eccuts.c:105
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:33999
#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)
Definition: scip.c:33091
SCIP_RETCODE SCIPlpiGetSol(SCIP_LPI *lpi, SCIP_Real *objval, SCIP_Real *primsol, SCIP_Real *dualsol, SCIP_Real *activity, SCIP_Real *redcost)
Definition: lpi_clp.cpp:2671
#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.c:7360
#define DEFAULT_MAXSEPACUTS
Definition: sepa_eccuts.c:54
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21991
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip.c:16947
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip.c:7482
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:61
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
Definition: scip.c:30335
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:2788
int nquadvars
Definition: struct_nlp.h:80
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42321
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:1295
#define MAX(x, y)
Definition: tclique_def.h:75
static SCIP_Real transformValue(SCIP *scip, SCIP_Real lb, SCIP_Real ub, SCIP_Real val)
Definition: sepa_eccuts.c:1899
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:34094
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4660
#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.c:30181
#define DEFAULT_MAXBILINTERMS
Definition: sepa_eccuts.c:62
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:33868
int nquadvars
Definition: sepa_eccuts.c:111
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:39059
SCIP_RETCODE SCIPlpiSolvePrimal(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:1653
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:93
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:1481
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)
Definition: lpi_clp.cpp:793
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:46061
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip.c:30843
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:88
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:16480
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11680
SCIP_EXPRTREE * SCIPnlrowGetExprtree(SCIP_NLROW *nlrow)
Definition: nlp.c:3363
static SCIP_RETCODE nlrowaggrFree(SCIP *scip, SCIP_NLROWAGGR **nlrowaggr)
Definition: sepa_eccuts.c:546
SCIP_RETCODE SCIPlpiChgBounds(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *lb, const SCIP_Real *ub)
Definition: lpi_clp.cpp:952
Constraint handler for XOR constraints, .
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30290
#define CLIQUE_BACKTRACKFREQ
Definition: sepa_eccuts.c:48
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:2210
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip.c:7418
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:39158
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46024
static SCIP_RETCODE createLP(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_eccuts.c:1749
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:11360
static SCIP_RETCODE findAndStoreEcAggregations(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_NLROW *nlrow, SCIP_SOL *sol)
Definition: sepa_eccuts.c:1578
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_eccuts.c:52
SCIP_RETCODE SCIPlpiCreate(SCIP_LPI **lpi, SCIP_MESSAGEHDLR *messagehdlr, const char *name, SCIP_OBJSEN objsen)
Definition: lpi_clp.cpp:480
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27417
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11635
#define DEFAULT_DYNAMICCUTS
Definition: sepa_eccuts.c:50
#define SCIPstatistic(x)
Definition: pub_message.h:101
#define SCIP_Real
Definition: def.h:145
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
static SCIP_DECL_SEPAEXECLP(sepaExeclpEccuts)
Definition: sepa_eccuts.c:2721
static SCIP_DECL_SEPAFREE(sepaFreeEccuts)
Definition: sepa_eccuts.c:2679
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:30892
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:16852
SCIP_Real SCIPgetTotalTime(SCIP *scip)
Definition: scip.c:45344
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:1861
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46098
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46011
SCIP_Real * SCIPnlrowGetLinearCoefs(SCIP_NLROW *nlrow)
Definition: nlp.c:3265
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:2373
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17235
#define nnodes
Definition: gastrans.c:65
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:21976
#define DEFAULT_MINAGGRSIZE
Definition: sepa_eccuts.c:60
SCIP_VAR ** SCIPnlrowGetLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3255
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2845
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:89
SCIP_Real SCIPnlrowGetConstant(SCIP_NLROW *nlrow)
Definition: nlp.c:3235
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:3373
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:16746
#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.c:38182
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.c:4293
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.c:4718
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.c:4211
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:774
void SCIPaddSquareLinearization(SCIP *scip, SCIP_Real sqrcoef, SCIP_Real refpoint, SCIP_Bool isint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
Definition: scip.c:33023
static SCIP_Bool checkRikun(SCIP *scip, SCIP_ECAGGR *ecaggr, SCIP_Real *fvals, SCIP_Real *facet)
Definition: sepa_eccuts.c:1677
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip.c:38601