Scippy

SCIP

Solving Constraint Integer Programs

compute_symmetry_bliss.cpp
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-2023 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file compute_symmetry_bliss.cpp
26  * @brief interface for symmetry computations to bliss
27  * @author Marc Pfetsch
28  * @author Thomas Rehn
29  * @author Fabian Wegscheider
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #include "compute_symmetry.h"
35 
36 /* include bliss graph */
37 #include <bliss/defs.hh>
38 #include <bliss/graph.hh>
39 
40 #include <string.h>
41 #include <vector>
42 #include <list>
43 #include <math.h>
44 
45 #include "scip/expr_var.h"
46 #include "scip/expr_sum.h"
47 #include "scip/expr_pow.h"
48 #include "scip/expr.h"
49 #include "scip/cons_nonlinear.h"
50 #include "scip/cons_linear.h"
51 
52 using std::vector;
53 
54 
55 /** struct for bliss callback */
56 struct BLISS_Data
57 {
58  SCIP* scip; /**< SCIP pointer */
59  int npermvars; /**< number of variables for permutations */
60  int nperms; /**< number of permutations */
61  int** perms; /**< permutation generators as (nperms x npermvars) matrix */
62  int nmaxperms; /**< maximal number of permutations */
63  int maxgenerators; /**< maximal number of generators constructed (= 0 if unlimited) */
64 };
65 
66 /* ------------------- map for operator types ------------------- */
67 
68 /** gets the key of the given element */
69 static
70 SCIP_DECL_HASHGETKEY(SYMhashGetKeyOptype)
71 { /*lint --e{715}*/
72  return elem;
73 }
74 
75 /** returns TRUE iff both keys are equal
76  *
77  * Compare the types of two operators according to their name, level and, in case of power, exponent.
78  */
79 static
80 SCIP_DECL_HASHKEYEQ(SYMhashKeyEQOptype)
81 {
82  SYM_OPTYPE* k1;
83  SYM_OPTYPE* k2;
84 
85  k1 = (SYM_OPTYPE*) key1;
86  k2 = (SYM_OPTYPE*) key2;
87 
88  /* first check operator name */
89  if ( SCIPexprGetHdlr(k1->expr) != SCIPexprGetHdlr(k2->expr) )
90  return FALSE;
91 
92  /* for pow expressions, also check exponent (TODO should that happen for signpow as well?) */
93  if ( SCIPisExprPower((SCIP*)userptr, k1->expr )
94  && SCIPgetExponentExprPow(k1->expr) != SCIPgetExponentExprPow(k2->expr) ) /*lint !e777*/
95  return FALSE;
96 
97  /* if still undecided, take level */
98  if ( k1->level != k2->level )
99  return FALSE;
100 
101  return TRUE;
102 }
103 
104 /** returns the hash value of the key */
105 static
106 SCIP_DECL_HASHKEYVAL(SYMhashKeyValOptype)
107 { /*lint --e{715}*/
108  SYM_OPTYPE* k;
109  SCIP_Real exponent;
110 
111  k = (SYM_OPTYPE*) key;
112 
113  if ( SCIPisExprPower((SCIP*)userptr, k->expr) )
114  exponent = SCIPgetExponentExprPow(k->expr);
115  else
116  exponent = 1.0;
117 
118  return SCIPhashThree(SCIPrealHashCode(exponent), k->level,
119  SCIPhashKeyValString(NULL, static_cast<void*>(const_cast<char*>(SCIPexprhdlrGetName(SCIPexprGetHdlr(k->expr))))));
120 }
121 
122 /* ------------------- map for constant types ------------------- */
123 
124 /** gets the key of the given element */
125 static
126 SCIP_DECL_HASHGETKEY(SYMhashGetKeyConsttype)
127 { /*lint --e{715}*/
128  return elem;
129 }
130 
131 /** returns TRUE iff both keys are equal
132  *
133  * Compare two constants according to their values.
134  */
135 static
136 SCIP_DECL_HASHKEYEQ(SYMhashKeyEQConsttype)
137 {
138  SYM_CONSTTYPE* k1;
139  SYM_CONSTTYPE* k2;
140 
141  k1 = (SYM_CONSTTYPE*) key1;
142  k2 = (SYM_CONSTTYPE*) key2;
143 
144  return (SCIP_Bool)(k1->value == k2->value); /*lint !e777*/
145 }
146 
147 /** returns the hash value of the key */
148 static
149 SCIP_DECL_HASHKEYVAL(SYMhashKeyValConsttype)
150 { /*lint --e{715}*/
151  SYM_CONSTTYPE* k;
152 
153  k = (SYM_CONSTTYPE*) key;
154 
155  return SCIPrealHashCode(k->value);
156 }
157 
158 /* ------------------- map for constraint side types ------------------- */
159 
160 /** gets the key of the given element */
161 static
162 SCIP_DECL_HASHGETKEY(SYMhashGetKeyRhstype)
163 { /*lint --e{715}*/
164  return elem;
165 }
166 
167 /** returns TRUE iff both keys are equal
168  *
169  * Compare two constraint sides according to lhs and rhs.
170  */
171 static
172 SCIP_DECL_HASHKEYEQ(SYMhashKeyEQRhstype)
173 {
174  SYM_RHSTYPE* k1;
175  SYM_RHSTYPE* k2;
176 
177  k1 = (SYM_RHSTYPE*) key1;
178  k2 = (SYM_RHSTYPE*) key2;
179 
180  if ( k1->lhs != k2->lhs ) /*lint !e777*/
181  return FALSE;
182 
183  return (SCIP_Bool)(k1->rhs == k2->rhs); /*lint !e777*/
184 }
185 
186 /** returns the hash value of the key */
187 static
188 SCIP_DECL_HASHKEYVAL(SYMhashKeyValRhstype)
189 { /*lint --e{715}*/
190  SYM_RHSTYPE* k;
191 
192  k = (SYM_RHSTYPE*) key;
193 
195 }
196 
197 /** callback function for bliss */
198 static
200  void* user_param, /**< parameter supplied at call to bliss */
201  unsigned int n, /**< size of aut vector */
202  const unsigned int* aut /**< automorphism */
203  )
204 {
205  assert( aut != NULL );
206  assert( user_param != NULL );
207 
208  BLISS_Data* data = static_cast<BLISS_Data*>(user_param);
209  assert( data->scip != NULL );
210  assert( data->npermvars < (int) n );
211  assert( data->maxgenerators >= 0);
212 
213  /* make sure we do not generate more that maxgenerators many permutations, if the limit in bliss is not available */
214  if ( data->maxgenerators != 0 && data->nperms >= data->maxgenerators )
215  return;
216 
217  /* copy first part of automorphism */
218  bool isIdentity = true;
219  int* p = 0;
220  if ( SCIPallocBlockMemoryArray(data->scip, &p, data->npermvars) != SCIP_OKAY )
221  return;
222 
223  for (int j = 0; j < data->npermvars; ++j)
224  {
225  /* convert index of variable-level 0-nodes to variable indices */
226  p[j] = (int) aut[j];
227  if ( p[j] != j )
228  isIdentity = false;
229  }
230 
231  /* ignore trivial generators, i.e. generators that only permute the constraints */
232  if ( isIdentity )
233  {
234  SCIPfreeBlockMemoryArray(data->scip, &p, data->npermvars);
235  return;
236  }
237 
238  /* check whether we should allocate space for perms */
239  if ( data->nmaxperms <= 0 )
240  {
241  if ( data->maxgenerators == 0 )
242  data->nmaxperms = 100; /* seems to cover many cases */
243  else
244  data->nmaxperms = data->maxgenerators;
245 
246  if ( SCIPallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms) != SCIP_OKAY )
247  return;
248  }
249  else if ( data->nperms >= data->nmaxperms ) /* check whether we need to resize */
250  {
251  int newsize = SCIPcalcMemGrowSize(data->scip, data->nperms + 1);
252  assert( newsize >= data->nperms );
253  assert( data->maxgenerators == 0 );
254 
255  if ( SCIPreallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms, newsize) != SCIP_OKAY )
256  return;
257 
258  data->nmaxperms = newsize;
259  }
260 
261  data->perms[data->nperms++] = p;
262 }
263 
264 /** Creates the nodes in the graph that correspond to variables. Each variable type gets a unique color
265  *
266  * @pre graph should be empty when this is called
267  */
268 static
270  SCIP* scip, /**< SCIP instance */
271  bliss::Graph* G, /**< Graph to be constructed */
272  SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix (also contains the relevant variables) */
273  int& nnodes, /**< buffer to store number of nodes in graph */
274  const int& nedges, /**< buffer to store number of edges in graph */
275  int& nusedcolors /**< buffer to store number of used colors */
276  )
277 {
278  assert( scip != NULL );
279  assert( G != NULL );
280  assert( nnodes == 0 );
281  assert( nedges == 0 );
282  assert( nusedcolors == 0 );
283  SCIPdebugMsg(scip, "Creating graph with colored nodes for variables.\n");
284 
285  /* add nodes for variables */
286  for (int v = 0; v < matrixdata->npermvars; ++v)
287  {
288  const int color = matrixdata->permvarcolors[v];
289  assert( 0 <= color && color < matrixdata->nuniquevars );
290 
291 #ifndef NDEBUG
292  int node = (int) G->add_vertex((unsigned) color);
293  assert( node == v );
294 #else
295  (void) G->add_vertex((unsigned) color);
296 #endif
297 
298  ++nnodes;
299  }
300 
301  /* this is not exactly true, since we skip auxvars, but it doesn't matter if some colors are not used at all */
302  nusedcolors = matrixdata->nuniquevars;
303 
304  return SCIP_OKAY;
305 }
306 
307 /** Construct linear part of colored graph for symmetry computations
308  *
309  * Construct graph:
310  * - Each variable gets a different node.
311  * - Each constraint gets a different node.
312  * - Each matrix coefficient gets a different node that is connected to the two nodes
313  * corresponding to the respective constraint and variable.
314  *
315  * Each different variable, rhs, matrix coefficient gets a different color that is attached to the corresponding entries.
316  *
317  * @pre This method assumes that the nodes corresponding to permutation variables are already in the graph and that
318  * their node number is equal to their index.
319  */
320 static
322  SCIP* scip, /**< SCIP instance */
323  bliss::Graph* G, /**< Graph to be constructed */
324  SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
325  int& nnodes, /**< buffer to store number of nodes in graph */
326  int& nedges, /**< buffer to store number of edges in graph */
327  int& nusedcolors, /**< buffer to store number of used colors */
328  SCIP_Bool& success /**< whether the construction was successful */
329  )
330 {
331  assert( nnodes == (int) G->get_nof_vertices() );
332  assert( nusedcolors <= nnodes );
333 
334  SCIPdebugMsg(scip, "Filling graph with colored coefficient nodes for linear part.\n");
335 
336  success = TRUE;
337 
338  /* add nodes for rhs of constraints */
339  for (int c = 0; c < matrixdata->nrhscoef; ++c)
340  {
341  const int color = matrixdata->rhscoefcolors[c];
342  assert( 0 <= color && color < matrixdata->nuniquerhs );
343 
344 #ifndef NDEBUG
345  int node = (int) G->add_vertex((unsigned) (nusedcolors + color));
346  assert( node == matrixdata->npermvars + c );
347 #else
348  (void) G->add_vertex((unsigned) (nusedcolors + color));
349 #endif
350 
351  ++nnodes;
352  }
353  assert( (int) G->get_nof_vertices() == matrixdata->npermvars + matrixdata->nrhscoef );
354  nusedcolors += matrixdata->nuniquerhs;
355 
356  /* Grouping of nodes depends on the number of nodes in the bipartite graph class.
357  * If there are more variables than constraints, we group by constraints.
358  * That is, given several variable nodes which are incident to one constraint node by the same color,
359  * we join these variable nodes to the constraint node by only one intermediate node.
360  */
361  const bool groupByConstraints = matrixdata->nrhscoef < matrixdata->npermvars;
362  if ( groupByConstraints )
363  SCIPdebugMsg(scip, "Group intermediate nodes by constraints.\n");
364  else
365  SCIPdebugMsg(scip, "Group intermediate nodes by variables.\n");
366 
367  /* "colored" edges based on all matrix coefficients - loop through ordered matrix coefficients */
368  int ninternodes;
369  if ( groupByConstraints )
370  ninternodes = matrixdata->nrhscoef;
371  else
372  ninternodes = matrixdata->npermvars;
373 
374  int* internodes = NULL;
375  SCIP_CALL( SCIPallocBufferArray(scip, &internodes, ninternodes) ); /*lint !e530*/
376  for (int l = 0; l < ninternodes; ++l)
377  internodes[l] = -1;
378 
379  /* We pass through the matrix coeficients, grouped by color, i.e., different coefficients. If the coeffients appear
380  * in the same row or column, it suffices to only generate a single node (depending on groupByConstraints). We store
381  * this node in the array internodes. In order to avoid reinitialization, we store the node number with increasing
382  * numbers for each color. The smallest number for the current color is stored in firstcolornodenumber. */
383  int oldcolor = -1;
384 #ifndef NDEBUG
385  SCIP_Real oldcoef = SCIP_INVALID;
386 #endif
387  int firstcolornodenumber = -1;
388  for (int j = 0; j < matrixdata->nmatcoef; ++j)
389  {
390  int idx = matrixdata->matidx[j];
391  assert( 0 <= idx && idx < matrixdata->nmatcoef );
392 
393  /* find color corresponding to matrix coefficient */
394  const int color = matrixdata->matcoefcolors[idx];
395  assert( 0 <= color && color < matrixdata->nuniquemat );
396 
397  assert( 0 <= matrixdata->matrhsidx[idx] && matrixdata->matrhsidx[idx] < matrixdata->nrhscoef );
398  assert( 0 <= matrixdata->matvaridx[idx] && matrixdata->matvaridx[idx] < matrixdata->npermvars );
399 
400  const int rhsnode = matrixdata->npermvars + matrixdata->matrhsidx[idx];
401  const int varnode = matrixdata->matvaridx[idx];
402  assert( matrixdata->npermvars <= rhsnode && rhsnode < matrixdata->npermvars + matrixdata->nrhscoef );
403  assert( rhsnode < (int) G->get_nof_vertices() );
404  assert( varnode < (int) G->get_nof_vertices() );
405 
406  /* if we have only one color, we do not need intermediate nodes */
407  if ( matrixdata->nuniquemat == 1 )
408  {
409  G->add_edge((unsigned) varnode, (unsigned) rhsnode);
410  ++nedges;
411  }
412  else
413  {
414  /* if new group of coefficients has been reached */
415  if ( color != oldcolor )
416  {
417  assert( ! SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
418  oldcolor = color;
419  firstcolornodenumber = nnodes;
420 #ifndef NDEBUG
421  oldcoef = matrixdata->matcoef[idx];
422 #endif
423  }
424  else
425  assert( SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
426 
427  int varrhsidx;
428  if ( groupByConstraints )
429  varrhsidx = matrixdata->matrhsidx[idx];
430  else
431  varrhsidx = matrixdata->matvaridx[idx];
432  assert( 0 <= varrhsidx && varrhsidx < ninternodes );
433 
434  if ( internodes[varrhsidx] < firstcolornodenumber )
435  {
436  internodes[varrhsidx] = (int) G->add_vertex((unsigned) (nusedcolors + color));
437  ++nnodes;
438  }
439  assert( internodes[varrhsidx] >= matrixdata->npermvars + matrixdata->nrhscoef );
440  assert( internodes[varrhsidx] >= firstcolornodenumber );
441 
442  /* determine whether graph would be too large for bliss (can only handle int) */
443  if ( nnodes >= INT_MAX/2 )
444  {
445  success = FALSE;
446  break;
447  }
448 
449  G->add_edge((unsigned) varnode, (unsigned) internodes[varrhsidx]);
450  G->add_edge((unsigned) rhsnode, (unsigned) internodes[varrhsidx]);
451  nedges += 2;
452  }
453  }
454 
455  nusedcolors += matrixdata->nuniquemat;
456 
457  SCIPfreeBufferArray(scip, &internodes);
458  return SCIP_OKAY;
459 }
460 
461 /** Construct non-linear part of colored graph for symmetry computations
462  *
463  * Construct graph:
464  * - Each node of the expression trees gets a different node.
465  * - Each coefficient of a sum expression gets its own node connected to the node of the corresponding child.
466  * - Each constraint (with lhs and (!) rhs) gets its own node connected to the corresponding node of the root expression.
467  *
468  * @note: In contrast to the linear part, lhs and rhs are treated together here, so that each unique combination of lhs
469  * and rhs gets its own node. This makes the implementation a lot simpler with the small downside, that different
470  * formulations of the same constraints would not be detected as equivalent, e.g. for
471  * 0 <= x1 + x2 <= 1
472  * 0 <= x3 + x4
473  * x3 + x4 <= 1
474  * there would be no symmetry between (x1,x2) and (x3,x4) detected.
475  *
476  * Each different constraint (sides), sum-expression coefficient, constant and operator type gets a
477  * different color that is attached to the corresponding entries.
478  *
479  * @pre This method assumes that the nodes corresponding to permutation variables are already in the graph and that
480  * their node number is equal to their index.
481  */
482 static
484  SCIP* scip, /**< SCIP instance */
485  bliss::Graph* G, /**< Graph to be constructed */
486  SYM_EXPRDATA* exprdata, /**< data for nonlinear constraints */
487  int& nnodes, /**< buffer to store number of nodes in graph */
488  int& nedges, /**< buffer to store number of edges in graph */
489  int& nusedcolors, /**< number of used colors ind the graph so far */
490  SCIP_Bool& success /**< whether the construction was successful */
491  )
492 {
493  SCIP_HASHTABLE* optypemap;
494  SCIP_HASHTABLE* consttypemap;
495  SCIP_HASHTABLE* sumcoefmap;
496  SCIP_HASHTABLE* rhstypemap;
497  SYM_OPTYPE* uniqueoparray = NULL;
498  SYM_CONSTTYPE* uniqueconstarray = NULL;
499  SYM_CONSTTYPE* sumcoefarray = NULL;
500  SYM_RHSTYPE* uniquerhsarray = NULL;
501  SCIP_CONSHDLR* conshdlr;
502  SCIP_CONS** conss;
503  int nconss;
504  int nuniqueops = 0;
505  int nuniqueconsts = 0;
506  int nuniquecoefs = 0;
507  int nuniquerhs = 0;
508  int oparraysize = exprdata->nuniqueoperators;
509  int constarraysize = exprdata->nuniqueconstants;
510  int coefarraysize = exprdata->nuniquecoefs;
511  int rhsarraysize;
512 
513  assert( scip != NULL );
514  assert( G != NULL );
515  assert( exprdata != NULL );
516  assert( nnodes == (int) G->get_nof_vertices() );
517  assert( nnodes >= nusedcolors );
518 
519  success = TRUE; /*lint !e838*/
520 
521  conshdlr = SCIPfindConshdlr(scip, "nonlinear");
522  nconss = conshdlr != NULL ? SCIPconshdlrGetNConss(conshdlr) : 0;
523  if ( nconss == 0 )
524  return SCIP_OKAY;
525 
526  conss = SCIPconshdlrGetConss(conshdlr);
527  rhsarraysize = nconss;
528 
529  SCIPdebugMsg(scip, "Filling graph with colored coefficient nodes for non-linear part.\n");
530 
531  /* create maps for optypes, constants, sum coefficients and rhs to indices */
532  SCIP_CALL( SCIPhashtableCreate(&optypemap, SCIPblkmem(scip), oparraysize, SYMhashGetKeyOptype,
533  SYMhashKeyEQOptype, SYMhashKeyValOptype, (void*) scip) );
534  SCIP_CALL( SCIPhashtableCreate(&consttypemap, SCIPblkmem(scip), constarraysize, SYMhashGetKeyConsttype,
535  SYMhashKeyEQConsttype, SYMhashKeyValConsttype, (void*) scip) );
536  SCIP_CALL( SCIPhashtableCreate(&sumcoefmap, SCIPblkmem(scip), coefarraysize, SYMhashGetKeyConsttype,
537  SYMhashKeyEQConsttype, SYMhashKeyValConsttype, (void*) scip) );
538  SCIP_CALL( SCIPhashtableCreate(&rhstypemap, SCIPblkmem(scip), rhsarraysize, SYMhashGetKeyRhstype,
539  SYMhashKeyEQRhstype, SYMhashKeyValRhstype, (void*) scip) );
540 
541  assert( optypemap != NULL );
542  assert( consttypemap != NULL );
543  assert( sumcoefmap != NULL );
544  assert( rhstypemap != NULL );
545 
546  /* allocate space for mappings from optypes, constants, sum coefficients and rhs to colors */
547  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &uniqueoparray, oparraysize) );
548  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &uniqueconstarray, constarraysize) );
549  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &sumcoefarray, coefarraysize) );
550  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &uniquerhsarray, rhsarraysize) );
551 
552  SCIP_EXPRITER* it;
553  SCIP_CALL( SCIPcreateExpriter(scip, &it) );
554 
555  /* iterate over all expressions and add the corresponding nodes to the graph */
556  for (int i = 0; i < nconss; ++i)
557  {
558  SCIP_EXPR* rootexpr;
559  vector<int> visitednodes(0);
560  vector<SCIP_Bool> ischildofsum(0);
561  int currentlevel = 0;
562 
563  rootexpr = SCIPgetExprNonlinear(conss[i]);
564 
567 
568  for (SCIP_EXPR* expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it)) /*lint !e441*/ /*lint !e440*/
569  {
570  switch( SCIPexpriterGetStageDFS(it) )
571  {
572  /* upon entering an expression, check its type and add nodes and edges if neccessary */
574  {
575  int node = -1;
576  int parentnode = -1;
577  int color = -1;
578 
579  /* for variable expressions, get the corresponding node that is already in the graph */
580  if ( SCIPisExprVar(scip, expr) )
581  {
582  SCIP_VAR* var = SCIPgetVarExprVar(expr);
583 
584  /* check whether the variable is active; if not, then replace the inactive variable by its aggregation
585  * or its fixed value; note that this step is equivalent as representing an inactive variable as sum
586  * expression
587  */
588  if ( SCIPvarIsActive(var) )
589  {
590  node = SCIPvarGetProbindex(var);
591  assert( node < (int) G->get_nof_vertices() );
592  }
593  else
594  {
595  SCIP_VAR** vars = NULL;
596  SCIP_Real* vals = NULL;
597  SCIP_Real constant = 0;
598  int varsize = 1;
599  int requiredsize;
600  int k;
601 
602  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varsize) );
603  SCIP_CALL( SCIPallocBufferArray(scip, &vals, varsize) );
604 
605  vars[0] = var;
606  vals[0] = 1.0;
607 
608  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, vals, &varsize, varsize, &constant, &requiredsize, TRUE) );
609 
610  if ( requiredsize > varsize )
611  {
612  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, requiredsize) );
613  SCIP_CALL( SCIPreallocBufferArray(scip, &vals, requiredsize) );
614 
615  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, vals, &varsize, requiredsize, &constant, &requiredsize, TRUE) );
616  assert( requiredsize <= varsize );
617  }
618 
619  parentnode = visitednodes[visitednodes.size() - 1];
620  assert( parentnode < (int) G->get_nof_vertices() );
621 
622  /* create nodes for all aggregation variables and coefficients and connect them to the parent node */
623  for ( k = 0; k < requiredsize; ++k )
624  {
625  SYM_CONSTTYPE* ct;
626  int internode;
627 
628  assert( vars[k] != NULL );
629  assert( vals[k] != 0.0 );
630  assert( nuniquecoefs < coefarraysize );
631 
632  ct = &sumcoefarray[nuniquecoefs];
633  ct->value = vals[k];
634 
635  if ( !SCIPhashtableExists(sumcoefmap, (void *) ct) )
636  {
637  SCIP_CALL( SCIPhashtableInsert(sumcoefmap, (void *) ct) );
638  ct->color = nusedcolors++;
639  color = ct->color;
640  nuniquecoefs++;
641  }
642  else
643  {
644  color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(sumcoefmap, (void *) ct))->color;
645  }
646 
647  /* add the intermediate node with the corresponding color */
648  internode = (int) G->add_vertex((unsigned) color);
649  ++nnodes;
650 
651  assert( internode < (int) G->get_nof_vertices() );
652 
653  G->add_edge((unsigned) internode, (unsigned) parentnode);
654  ++nedges;
655 
656  /* connect the intermediate node to its corresponding variable node */
657  node = SCIPvarGetProbindex(vars[k]);
658  assert( node < (int) G->get_nof_vertices() );
659 
660  G->add_edge((unsigned) node, (unsigned) internode);
661  ++nedges;
662  }
663 
664  /* add the node for the constant */
665  if ( constant != 0.0 )
666  {
667  SYM_CONSTTYPE* ct;
668 
669  /* check whether we have to resize */
670  if ( nuniqueconsts >= constarraysize )
671  {
672  int newsize = SCIPcalcMemGrowSize(scip, nuniqueconsts+1);
673  assert( newsize >= 0 );
674  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &uniqueconstarray, constarraysize, newsize) );
675  constarraysize = newsize;
676  }
677 
678  assert( nuniqueconsts < constarraysize );
679 
680  ct = &uniqueconstarray[nuniqueconsts];
681  ct->value = constant;
682 
683  if ( !SCIPhashtableExists(consttypemap, (void *) ct) )
684  {
685  SCIP_CALL( SCIPhashtableInsert(consttypemap, (void *) ct) );
686  ct->color = nusedcolors++;
687  color = ct->color;
688  nuniqueconsts++;
689  }
690  else
691  {
692  color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
693  }
694 
695  /* add the node with a new color */
696  node = (int) G->add_vertex((unsigned) color);
697  ++nnodes;
698 
699  assert( node < (int) G->get_nof_vertices() );
700 
701  G->add_edge((unsigned) node, (unsigned) parentnode);
702  ++nedges;
703  }
704 
705  SCIPfreeBufferArray(scip, &vals);
706  SCIPfreeBufferArray(scip, &vars);
707 
708  /* add a filler node since it will be removed in the next iteration anyway */
709  visitednodes.push_back(nnodes);
710  ischildofsum.push_back(FALSE);
711  ++currentlevel;
712 
713  break;
714  }
715  }
716  /* for constant expressions, get the color of its type (value) or assign a new one */
717  else if ( SCIPisExprValue(scip, expr) )
718  {
719  SYM_CONSTTYPE* ct;
720 
721  assert( nuniqueconsts < constarraysize );
722 
723  ct = &uniqueconstarray[nuniqueconsts];
724  ct->value = SCIPgetValueExprValue(expr);
725 
726  if ( !SCIPhashtableExists(consttypemap, (void *) ct) )
727  {
728  SCIP_CALL( SCIPhashtableInsert(consttypemap, (void *) ct) );
729  ct->color = nusedcolors++;
730  color = ct->color;
731  nuniqueconsts++;
732  }
733  else
734  {
735  color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
736  }
737  }
738  /* for all other expressions, get the color of its operator type or assign a new one */
739  else
740  {
741  SYM_OPTYPE* ot;
742 
743  assert( nuniqueops < oparraysize );
744 
745  ot = &uniqueoparray[nuniqueops];
746 
747  ot->expr = expr;
748  ot->level = currentlevel;
749 
750  if ( !SCIPhashtableExists(optypemap, (void *) ot) )
751  {
752  SCIP_CALL( SCIPhashtableInsert(optypemap, (void *) ot) );
753  ot->color = nusedcolors++;
754  color = ot->color;
755  nuniqueops++;
756  }
757  else
758  {
759  color = ((SYM_OPTYPE*) SCIPhashtableRetrieve(optypemap, (void *) ot))->color;
760  }
761  }
762 
763  /* if this is the root expression, add the constraint side node (will be parent of expression node) */
764  if ( SCIPexpriterGetParentDFS(it) == NULL )
765  {
766  /* add the node corresponding to the constraint */
767  SYM_RHSTYPE* rt;
768  int parentcolor;
769 
770  assert( nuniquerhs < rhsarraysize );
771 
772  rt = &uniquerhsarray[nuniquerhs];
773  rt->lhs = SCIPgetLhsNonlinear(conss[i]);
774  rt->rhs = SCIPgetRhsNonlinear(conss[i]);
775 
776  if ( !SCIPhashtableExists(rhstypemap, (void *) rt) )
777  {
778  SCIP_CALL( SCIPhashtableInsert(rhstypemap, (void *) rt) );
779  rt->color = nusedcolors++;
780  parentcolor = rt->color;
781  nuniquerhs++;
782  }
783  else
784  {
785  parentcolor = ((SYM_RHSTYPE*) SCIPhashtableRetrieve(rhstypemap, (void *) rt))->color;
786  }
787 
788  /* add the constraint side node with the corresponding color */
789  parentnode = (int) G->add_vertex((unsigned) parentcolor);
790  ++nnodes;
791 
792  assert( parentnode < (int) G->get_nof_vertices() );
793  }
794  /* otherwise, get the parentnode stored in visitednodes */
795  else
796  {
797  parentnode = visitednodes[visitednodes.size() - 1];
798  assert( parentnode < (int) G->get_nof_vertices() );
799  }
800 
801  /* in all cases apart from variable expressions, the new node is added with the corresponding color */
802  if ( color != -1 )
803  {
804  node = (int) G->add_vertex((unsigned) color);
805  ++nnodes;
806 
807  assert( node < (int) G->get_nof_vertices() );
808  }
809 
810  /* store the new node so that it can be used as parentnode later */
811  assert( node != -1 );
812  visitednodes.push_back(node);
813  ischildofsum.push_back(FALSE);
814 
815  /* connect the current node with its parent */
816  assert( parentnode != -1 );
817  G->add_edge((unsigned) node, (unsigned) parentnode);
818  ++nedges;
819 
820  /* for sum expression, also add intermediate nodes for the coefficients */
821  if ( SCIPisExprSum(scip, expr) )
822  {
823  SCIP_Real* coefs = SCIPgetCoefsExprSum(expr);
824  int internode;
825 
826  /* iterate over children from last to first, such that visitednodes array is in correct order */
827  for (int j = SCIPexprGetNChildren(expr) - 1; j >= 0; --j)
828  {
829  SYM_CONSTTYPE* ct;
830 
831  assert( nuniquecoefs < coefarraysize );
832 
833  ct = &sumcoefarray[nuniquecoefs];
834  ct->value = coefs[j];
835 
836  if ( !SCIPhashtableExists(sumcoefmap, (void *) ct) )
837  {
838  SCIP_CALL( SCIPhashtableInsert(sumcoefmap, (void *) ct) );
839  ct->color = nusedcolors++;
840  color = ct->color;
841  nuniquecoefs++;
842  }
843  else
844  {
845  color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(sumcoefmap, (void *) ct))->color;
846  }
847 
848  /* add the intermediate node with the corresponding color */
849  internode = (int) G->add_vertex((unsigned) color);
850  ++nnodes;
851  visitednodes.push_back(internode);
852  ischildofsum.push_back(TRUE);
853 
854  assert( internode < (int) G->get_nof_vertices() );
855 
856  G->add_edge((unsigned) internode, (unsigned) node);
857  ++nedges;
858  }
859 
860  /* add node for the constant term of the sum expression */
861  SCIP_Real constval = SCIPgetConstantExprSum(expr);
862  if ( constval != 0.0 )
863  {
864  SYM_CONSTTYPE* ct;
865 
866  /* check whether we have to resize */
867  if ( nuniqueconsts >= constarraysize )
868  {
869  int newsize = SCIPcalcMemGrowSize(scip, nuniqueconsts+1);
870  assert( newsize >= 0 );
871  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &uniqueconstarray, constarraysize, newsize) );
872  constarraysize = newsize;
873  }
874 
875  assert( nuniqueconsts < constarraysize );
876 
877  ct = &uniqueconstarray[nuniqueconsts];
878  ct->value = constval;
879 
880  if ( !SCIPhashtableExists(consttypemap, (void *) ct) )
881  {
882  SCIP_CALL( SCIPhashtableInsert(consttypemap, (void *) ct) );
883  ct->color = nusedcolors++;
884  color = ct->color;
885  nuniqueconsts++;
886  }
887  else
888  {
889  color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
890  }
891 
892  /* add the node with a new color */
893  internode = (int) G->add_vertex((unsigned) color);
894  ++nnodes;
895 
896  assert( node < (int) G->get_nof_vertices() );
897 
898  G->add_edge((unsigned) internode, (unsigned) node);
899  ++nedges;
900  }
901  }
902 
903  currentlevel++;
904  break;
905  }
906 
907  /* when leaving an expression, the nodes that are not needed anymore are erased from the respective arrays */
909  {
910  visitednodes.pop_back();
911  ischildofsum.pop_back();
912  currentlevel--;
913 
914  /* When leaving the child of a sum expression, we have to pop again to get rid of the intermediate nodes
915  * used for the coefficients of summands
916  */
917  if ( !ischildofsum.empty() && ischildofsum[ischildofsum.size() - 1] )
918  {
919  visitednodes.pop_back();
920  ischildofsum.pop_back();
921  }
922 
923  break;
924  }
925 
926  default:
927  SCIPABORT(); /* we should never be called in this stage */
928  break;
929  }
930  }
931 
932  assert( currentlevel == 0 );
933  assert( visitednodes.empty() );
934  assert( ischildofsum.empty() );
935 
936  /* determine whether graph would be too large for bliss (can only handle int) */
937  if ( nnodes >= INT_MAX/2 )
938  {
939  success = FALSE; /*lint !e838*/
940  break;
941  }
942  }
943 
944  /* free everything */
945  SCIPfreeExpriter(&it);
946  SCIPfreeBlockMemoryArrayNull(scip, &uniquerhsarray, rhsarraysize);
947  SCIPfreeBlockMemoryArrayNull(scip, &sumcoefarray, coefarraysize);
948  SCIPfreeBlockMemoryArrayNull(scip, &uniqueconstarray, constarraysize);
949  SCIPfreeBlockMemoryArrayNull(scip, &uniqueoparray, oparraysize);
950  SCIPhashtableFree(&rhstypemap);
951  SCIPhashtableFree(&sumcoefmap);
952  SCIPhashtableFree(&consttypemap);
953  SCIPhashtableFree(&optypemap);
954 
955  return SCIP_OKAY;
956 }
957 
958 /** return whether symmetry can be computed */
960 {
961  return TRUE;
962 }
963 
964 char*
966 
968 
969 char*
971 {
972  blissname = new char[100];
973 #ifdef BLISS_PATCH_PRESENT
974  (void) SCIPsnprintf(blissname, 100, "bliss %sp", bliss::version);
975 #else
976  (void) SCIPsnprintf(blissname, 100, "bliss %s", bliss::version);
977 #endif
978  return blissname;
979 }
980 
981 
982 /** return name of external program used to compute generators */
983 const char* SYMsymmetryGetName(void)
984 {
985  return blissname;
986 }
987 
988 /** return description of external program used to compute generators */
989 const char* SYMsymmetryGetDesc(void)
990 {
991  return "Computing Graph Automorphism Groups by T. Junttila and P. Kaski (www.tcs.hut.fi/Software/bliss/)";
992 }
993 
994 /** compute generators of symmetry group */
996  SCIP* scip, /**< SCIP pointer */
997  int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
998  SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
999  SYM_EXPRDATA* exprdata, /**< data for nonlinear constraints */
1000  int* nperms, /**< pointer to store number of permutations */
1001  int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
1002  int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
1003  SCIP_Real* log10groupsize /**< pointer to store size of group */
1004  )
1005 {
1006  assert( scip != NULL );
1007  assert( matrixdata != NULL );
1008  assert( exprdata != NULL );
1009  assert( nperms != NULL );
1010  assert( nmaxperms != NULL );
1011  assert( perms != NULL );
1012  assert( log10groupsize != NULL );
1013  assert( maxgenerators >= 0 );
1014 
1015  /* init */
1016  *nperms = 0;
1017  *nmaxperms = 0;
1018  *perms = NULL;
1019  *log10groupsize = 0;
1020 
1021  int nnodes = 0;
1022  int nedges = 0;
1023  int nusedcolors = 0;
1024  SCIP_Bool success = FALSE;
1025 
1026  /* create bliss graph */
1027  bliss::Graph G(0);
1028 
1029  /* create nodes corresponding to variables */
1030  SCIP_CALL( createVariableNodes(scip, &G, matrixdata, nnodes, nedges, nusedcolors) );
1031 
1032  assert( nnodes == matrixdata->npermvars );
1033  assert( nusedcolors == matrixdata->nuniquevars );
1034 
1035  /* fill graph with nodes for variables and linear constraints */
1036  SCIP_CALL( fillGraphByLinearConss(scip, &G, matrixdata, nnodes, nedges, nusedcolors, success) );
1037 
1038  if ( !success )
1039  {
1040  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, 0, "Graph construction failed during linear part.\n");
1041  return SCIP_OKAY;
1042  }
1043 
1044  /* add the nodes for nonlinear constraints to the graph */
1045  SCIP_CALL( fillGraphByNonlinearConss(scip, &G, exprdata, nnodes, nedges, nusedcolors, success) );
1046 
1047  if ( !success )
1048  {
1049  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, 0, "Graph construction failed during non-linear part.\n");
1050  return SCIP_OKAY;
1051  }
1052 
1053 #ifdef SCIP_OUTPUT
1054  G.write_dot("debug.dot");
1055 #endif
1056 
1057  SCIPdebugMsg(scip, "Symmetry detection graph has %u nodes.\n", G.get_nof_vertices());
1058 
1059  /* compute automorphisms */
1060  bliss::Stats stats;
1061  BLISS_Data data;
1062  data.scip = scip;
1063  data.npermvars = matrixdata->npermvars;
1064  data.nperms = 0;
1065  data.nmaxperms = 0;
1067  data.perms = NULL;
1068 
1069  /* Prefer splitting partition cells corresponding to variables over those corresponding
1070  * to inequalities. This is because we are only interested in the action
1071  * of the automorphism group on the variables, and we need a base for this action */
1072  G.set_splitting_heuristic(bliss::Graph::shs_f);
1073  /* disable component recursion as advised by Tommi Junttila from bliss */
1074  G.set_component_recursion(false);
1075 
1076  /* do not use a node limit, but set generator limit */
1077 #ifdef BLISS_PATCH_PRESENT
1078  G.set_search_limits(0, (unsigned) maxgenerators);
1079 #endif
1080 
1081 #if BLISS_VERSION_MAJOR >= 1 || BLISS_VERSION_MINOR >= 76
1082  /* lambda function to have access to data and pass it to the blisshook above */
1083  auto reportglue = [&](unsigned int n, const unsigned int* aut) {
1084  blisshook((void*)&data, n, aut);
1085  };
1086 
1087  /* lambda function to have access to stats and terminate the search if maxgenerators are reached */
1088  auto term = [&]() {
1089  return (stats.get_nof_generators() >= (long unsigned int) maxgenerators);
1090  };
1091 
1092  /* start search */
1093  G.find_automorphisms(stats, reportglue, term);
1094 #else
1095  /* start search */
1096  G.find_automorphisms(stats, blisshook, (void*) &data);
1097 #endif
1098 
1099 
1100 #ifdef SCIP_OUTPUT
1101  (void) stats.print(stdout);
1102 #endif
1103 
1104  /* prepare return values */
1105  if ( data.nperms > 0 )
1106  {
1107  *perms = data.perms;
1108  *nperms = data.nperms;
1109  *nmaxperms = data.nmaxperms;
1110  }
1111  else
1112  {
1113  assert( data.perms == NULL );
1114  assert( data.nmaxperms == 0 );
1115  }
1116 
1117  /* determine log10 of symmetry group size */
1118  *log10groupsize = (SCIP_Real) log10l(stats.get_group_size_approx());
1119 
1120  return SCIP_OKAY;
1121 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition: expriter.c:500
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIP_Real * matcoef
static SCIP_RETCODE fillGraphByNonlinearConss(SCIP *scip, bliss::Graph *G, SYM_EXPRDATA *exprdata, int &nnodes, int &nedges, int &nusedcolors, SCIP_Bool &success)
SCIP_Real lhs
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2497
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:886
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3808
SCIP_EXPR * SCIPexpriterGetParentDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:739
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:534
static SCIP_DECL_HASHKEYEQ(SYMhashKeyEQOptype)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
SCIP_Real SCIPgetConstantExprSum(SCIP_EXPR *expr)
Definition: expr_sum.c:1181
static SCIP_DECL_HASHKEYVAL(SYMhashKeyValOptype)
SCIP_Real SCIPgetRhsNonlinear(SCIP_CONS *cons)
const char * SYMsymmetryGetName(void)
static SCIP_RETCODE fillGraphByLinearConss(SCIP *scip, bliss::Graph *G, SYM_MATRIXDATA *matrixdata, int &nnodes, int &nedges, int &nusedcolors, SCIP_Bool &success)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4554
private functions to work with algebraic expressions
#define FALSE
Definition: def.h:96
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10788
SCIP_Real SCIPgetExponentExprPow(SCIP_EXPR *expr)
Definition: expr_pow.c:3352
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
const char * SYMsymmetryGetDesc(void)
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17613
SCIP_Bool SYMcanComputeSymmetry(void)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
char * initStaticBlissName()
#define SCIPhashThree(a, b, c)
Definition: pub_misc.h:521
variable expression handler
#define SCIP_EXPRITER_ENTEREXPR
Definition: type_expr.h:676
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition: expriter.c:682
static char * blissname
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2246
interface for symmetry computations
static void blisshook(void *user_param, unsigned int n, const unsigned int *aut)
SCIP_Real value
SCIP_Real * SCIPgetCoefsExprSum(SCIP_EXPR *expr)
Definition: expr_sum.c:1166
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_MATRIXDATA *matrixdata, SYM_EXPRDATA *exprdata, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize)
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition: expr_var.c:416
static INLINE uint32_t SCIPrealHashCode(double x)
Definition: pub_misc.h:544
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
static SCIP_RETCODE createVariableNodes(SCIP *scip, bliss::Graph *G, SYM_MATRIXDATA *matrixdata, int &nnodes, const int &nedges, int &nusedcolors)
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1432
static SCIP_DECL_HASHGETKEY(SYMhashGetKeyOptype)
SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
#define NULL
Definition: lpi_spx1.cpp:164
power and signed power expression handlers
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1443
#define SCIP_CALL(x)
Definition: def.h:394
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:519
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
Definition: scip_var.c:1738
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4597
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2302
SCIP_EXPR * expr
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIP_Bool
Definition: def.h:93
SCIP_Real rhs
constraint handler for nonlinear constraints specified by algebraic expressions
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:857
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition: expr.c:3831
Constraint handler for linear constraints in their most general form, .
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2558
SCIP_Bool SCIPisExprPower(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1465
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2296
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
Definition: expriter.c:663
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2316
SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:695
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1421
#define SCIP_Real
Definition: def.h:186
#define SCIP_INVALID
Definition: def.h:206
SCIP_Real SCIPgetValueExprValue(SCIP_EXPR *expr)
Definition: expr_value.c:294
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2609
#define SCIP_EXPRITER_LEAVEEXPR
Definition: type_expr.h:679
sum expression handler
#define nnodes
Definition: gastrans.c:74
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition: expriter.c:968
#define SCIPABORT()
Definition: def.h:366
SCIP_Real SCIPgetLhsNonlinear(SCIP_CONS *cons)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17593
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128