Scippy

SCIP

Solving Constraint Integer Programs

expr_product.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file expr_product.c
26  * @ingroup DEFPLUGINS_EXPR
27  * @brief product expression handler
28  * @author Stefan Vigerske
29  * @author Benjamin Mueller
30  * @author Felipe Serrano
31  * @author Ksenia Bestuzheva
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include <string.h>
37 
38 #include "scip/pub_expr.h"
39 #include "scip/expr_product.h"
40 #include "scip/expr_sum.h"
41 #include "scip/expr_pow.h"
42 #include "scip/expr_value.h"
43 #include "scip/expr_exp.h"
44 #include "scip/expr_abs.h"
45 #include "scip/expr_entropy.h"
46 #include "scip/cons_nonlinear.h"
47 #include "scip/pub_misc.h"
48 #include "scip/nlhdlr_bilinear.h"
50 
51 #define EXPRHDLR_NAME "prod"
52 #define EXPRHDLR_DESC "product expression"
53 #define EXPRHDLR_PRECEDENCE 50000
54 #define EXPRHDLR_HASHKEY SCIPcalcFibHash(54949.0)
55 
56 /** macro to activate/deactivate debugging information of simplify method */
57 /*lint -emacro(681,debugSimplify) */
58 /*lint -emacro(506,debugSimplify) */
59 /*lint -emacro(774,debugSimplify) */
60 #ifdef SIMPLIFY_DEBUG
61 #define debugSimplify printf
62 #else
63 #define debugSimplify while( FALSE ) printf
64 #endif
65 
66 
67 /*lint -e777*/
68 
69 /*
70  * Data structures
71  */
72 
73 /** expression data */
74 struct SCIP_ExprData
75 {
76  SCIP_Real coefficient; /**< coefficient */
77 };
78 
79 struct SCIP_ExprhdlrData
80 {
81  SCIP_CONSHDLR* conshdlr; /**< nonlinear constraint handler (to compute estimates for > 2-dim products) */
82 
83  SCIP_Bool expandalways; /**< whether to expand products of a sum and several factors in simplify (SP12b) */
84 };
85 
86 /** node for linked list of expressions */
87 struct exprnode
88 {
89  SCIP_EXPR* expr; /**< expression in node */
90  struct exprnode* next; /**< next node */
91 };
92 
93 typedef struct exprnode EXPRNODE;
94 
95 /*
96  * Local methods
97  */
98 
99 /** evaluation callback for (vertex-polyhedral) functions used as input for facet computation of its envelopes */
100 static
102 {
103  /* funcdata is a pointer to the double holding the coefficient */
104  SCIP_Real ret = *(SCIP_Real*)funcdata;
105  int i;
106 
107  for( i = 0; i < nargs; ++i )
108  ret *= args[i];
109 
110  return ret;
111 }
112 
113 static
115  SCIP* scip, /**< SCIP data structure */
116  SCIP_Real simplifiedcoef, /**< simplified product should be simplifiedcoef * PI simplifiedfactors */
117  EXPRNODE** simplifiedfactors, /**< factors of simplified product */
118  SCIP_Bool expandalways, /**< whether to expand products of a sum and several factors in simplify (SP12b) */
119  SCIP_Bool changed, /**< indicates whether some of the simplified factors was changed */
120  SCIP_EXPR** simplifiedexpr, /**< buffer to store the simplified expression */
121  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
122  void* ownercreatedata /**< data to pass to ownercreate */
123  );
124 
125 /* methods for handling linked list of expressions */
126 
127 /** inserts newnode at beginning of list */
128 static
130  EXPRNODE* newnode, /**< node to insert */
131  EXPRNODE** list /**< list */
132  )
133 {
134  assert(list != NULL);
135  assert(newnode != NULL);
136 
137  newnode->next = *list;
138  *list = newnode;
139 }
140 
141 /** removes first element of list and returns it */
142 static
144  EXPRNODE** list /**< list */
145  )
146 {
147  EXPRNODE* first;
148 
149  assert(list != NULL);
150 
151  if( *list == NULL )
152  return NULL;
153 
154  first = *list;
155  *list = (*list)->next;
156  first->next = NULL;
157 
158  return first;
159 }
160 
161 /** returns length of list */
162 static
164  EXPRNODE* list /**< list */
165  )
166 {
167  int length;
168 
169  if( list == NULL )
170  return 0;
171 
172  length = 1;
173  while( (list=list->next) != NULL )
174  ++length;
175 
176  return length;
177 }
178 
179 /** creates expression node and captures expression */
180 static
182  SCIP* scip, /**< SCIP data structure */
183  SCIP_EXPR* expr, /**< expression stored at node */
184  EXPRNODE** newnode /**< pointer to store node */
185  )
186 {
187  SCIP_CALL( SCIPallocBlockMemory(scip, newnode) );
188 
189  (*newnode)->expr = expr;
190  (*newnode)->next = NULL;
191  SCIPcaptureExpr(expr);
192 
193  return SCIP_OKAY;
194 }
195 
196 /** creates expression list from expressions */
197 static
199  SCIP* scip, /**< SCIP data structure */
200  SCIP_EXPR** exprs, /**< expressions stored in list */
201  int nexprs, /**< number of expressions */
202  EXPRNODE** list /**< pointer to store list */
203  )
204 {
205  int i;
206 
207  assert(*list == NULL);
208  assert(nexprs > 0);
209 
210  debugSimplify("building expr list from %d expressions\n", nexprs);
211  for( i = nexprs - 1; i >= 0; --i )
212  {
213  EXPRNODE* newnode;
214 
215  SCIP_CALL( createExprNode(scip, exprs[i], &newnode) );
216  insertFirstList(newnode, list);
217  }
218  assert(nexprs > 1 || (*list)->next == NULL);
219 
220  return SCIP_OKAY;
221 }
222 
223 /** frees expression node and releases expressions */
224 static
226  SCIP* scip, /**< SCIP data structure */
227  EXPRNODE** node /**< node to be freed */
228  )
229 {
230  assert(node != NULL && *node != NULL);
231 
232  SCIP_CALL( SCIPreleaseExpr(scip, &(*node)->expr) );
233  SCIPfreeBlockMemory(scip, node);
234 
235  return SCIP_OKAY;
236 }
237 
238 /** frees an expression list */
239 static
241  SCIP* scip, /**< SCIP data structure */
242  EXPRNODE** exprlist /**< list */
243  )
244 {
245  EXPRNODE* current;
246 
247  if( *exprlist == NULL )
248  return SCIP_OKAY;
249 
250  current = *exprlist;
251  while( current != NULL )
252  {
253  EXPRNODE* tofree;
254 
255  tofree = current;
256  current = current->next;
257  SCIP_CALL( freeExprNode(scip, &tofree) );
258  }
259  assert(current == NULL);
260  *exprlist = NULL;
261 
262  return SCIP_OKAY;
263 }
264 
265 /* helper functions for simplifying expressions */
266 
267 /** creates a product expression with the elements of exprlist as its children */
268 static
270  SCIP* scip, /**< SCIP data structure */
271  EXPRNODE* exprlist, /**< list containing the children of expr */
272  SCIP_Real coef, /**< coef of expr */
273  SCIP_EXPR** expr, /**< pointer to store the product expression */
274  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
275  void* ownercreatedata /**< data to pass to ownercreate */
276  )
277 {
278  int i;
279  int nchildren;
280  SCIP_EXPR** children;
281 
282  /* asserts SP8 */
283  assert(coef == 1.0);
284  nchildren = listLength(exprlist);
285 
286  SCIP_CALL( SCIPallocBufferArray(scip, &children, nchildren) );
287 
288  for( i = 0; i < nchildren; ++i )
289  {
290  children[i] = exprlist->expr;
291  exprlist = exprlist->next;
292  }
293 
294  assert(exprlist == NULL);
295 
296  SCIP_CALL( SCIPcreateExprProduct(scip, expr, nchildren, children, coef, ownercreate, ownercreatedata) );
297 
298  SCIPfreeBufferArray(scip, &children);
299 
300  return SCIP_OKAY;
301 }
302 
303 /** simplifies a factor of a product expression: base, so that it is a valid children of a simplified product expr
304  *
305  * @note In contrast to other simplify methods, this does *not* return a simplified expression.
306  * Instead, the method is intended to be called only when simplifying a product expression.
307  * Since in general, base is not a simplified child of a product expression, this method returns
308  * a list of expressions L, such that (prod L) = baset *and* each expression in L
309  * is a valid child of a simplified product expression.
310  */
311 static
313  SCIP* scip, /**< SCIP data structure */
314  SCIP_EXPR* factor, /**< expression to be simplified */
315  SCIP_Real* simplifiedcoef, /**< coefficient of parent product expression */
316  EXPRNODE** simplifiedfactor, /**< pointer to store the resulting expression node/list of nodes */
317  SCIP_Bool* changed /**< pointer to store if some term actually got simplified */
318  )
319 {
320  assert(simplifiedfactor != NULL);
321  assert(*simplifiedfactor == NULL);
322  assert(factor != NULL);
323  assert(changed != NULL);
324 
325  /* enforces SP7 */
326  if( SCIPisExprValue(scip, factor) )
327  {
328  *changed = TRUE;
329  *simplifiedcoef *= SCIPgetValueExprValue(factor);
330  return SCIP_OKAY;
331  }
332 
333  /* enforces SP2 */
334  if( SCIPisExprProduct(scip, factor) )
335  {
336  *changed = TRUE;
337 
338  /* assert SP8 */
339  assert(SCIPgetCoefExprProduct(factor) == 1.0);
340  debugSimplify("[simplifyFactor] seeing a product: include its children\n");
341 
342  SCIP_CALL( createExprlistFromExprs(scip, SCIPexprGetChildren(factor), SCIPexprGetNChildren(factor), simplifiedfactor) );
343 
344  return SCIP_OKAY;
345  }
346 
347  /* enforces SP13: a sum with a unique child and no constant -> take the coefficient and use its child as factor */
348  if( SCIPisExprSum(scip, factor) && SCIPexprGetNChildren(factor) == 1 && SCIPgetConstantExprSum(factor) == 0.0 )
349  {
350  *changed = TRUE;
351 
352  /* assert SS8 and SS7 */
353  assert(SCIPgetCoefsExprSum(factor)[0] != 0.0 && SCIPgetCoefsExprSum(factor)[0] != 1.0);
354  debugSimplify("[simplifyFactor] seeing a sum of the form coef * child : take coef and child apart\n");
355 
356  if( SCIPisExprProduct(scip, SCIPexprGetChildren(factor)[0]) )
357  {
358  /* if child is a product, then add its children to exprlist */
360  *simplifiedcoef *= SCIPgetCoefExprProduct(SCIPexprGetChildren(factor)[0]);
361  }
362  else
363  {
364  SCIP_CALL( createExprlistFromExprs(scip, SCIPexprGetChildren(factor), 1, simplifiedfactor) );
365  }
366  *simplifiedcoef *= SCIPgetCoefsExprSum(factor)[0];
367 
368  return SCIP_OKAY;
369  }
370 
371  /* the given (simplified) expression `factor`, can be a child of a simplified product */
372  assert(!SCIPisExprProduct(scip, factor));
373  assert(!SCIPisExprValue(scip, factor));
374 
375  SCIP_CALL( createExprNode(scip, factor, simplifiedfactor) );
376 
377  return SCIP_OKAY;
378 }
379 
380 /** merges tomerge into finalchildren
381  *
382  * Both, tomerge and finalchildren contain expressions that could be the children of a simplified product
383  * (except for SP8 and SP10 which are enforced later).
384  * However, the concatenation of both lists will not in general yield a simplified product expression,
385  * because SP4, SP5 and SP14 could be violated. So the purpose of this method is to enforce SP4, SP5 and SP14.
386  * In the process of enforcing SP4, it could happen that SP2 is violated. Since enforcing SP2
387  * could generate further violations, we remove the affected children from finalchildren
388  * and include them in unsimplifiedchildren for further processing.
389  * @note if tomerge has more than one element, then they are the children of a simplified product expression
390  */
391 static
393  SCIP* scip, /**< SCIP data structure */
394  EXPRNODE* tomerge, /**< list to merge */
395  EXPRNODE** finalchildren, /**< pointer to store the result of merge between tomerge and *finalchildren */
396  EXPRNODE** unsimplifiedchildren,/**< the list of children that should go to the product expression;
397  * they are unsimplified when seen as children of a simplified product */
398  SCIP_Bool* changed, /**< pointer to store if some term actually got simplified */
399  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
400  void* ownercreatedata /**< data to pass to ownercreate */
401  )
402 {
403  EXPRNODE* tomergenode;
404  EXPRNODE* current;
405  EXPRNODE* previous;
406 
407  if( tomerge == NULL )
408  return SCIP_OKAY;
409 
410  if( *finalchildren == NULL )
411  {
412  *finalchildren = tomerge;
413  return SCIP_OKAY;
414  }
415 
416  tomergenode = tomerge;
417  current = *finalchildren;
418  previous = NULL;
419 
420  while( tomergenode != NULL && current != NULL )
421  {
422  int compareres;
423  EXPRNODE* aux;
424  SCIP_EXPR* base1;
425  SCIP_EXPR* base2;
426  SCIP_Real expo1;
427  SCIP_Real expo2;
428  SCIP_Bool issignpower1;
429  SCIP_Bool issignpower2;
430 
431  /* assert invariants */
432  assert(!SCIPisExprValue(scip, tomergenode->expr));
433  assert(!SCIPisExprValue(scip, current->expr));
434  assert(previous == NULL || previous->next == current);
435 
436  /* we are going to multiply the two exprs: current and tomergenode
437  * we first check if they are both exponentials
438  * if so, we multiply them
439  * otherwise, we interpret them as base^exponent
440  * the base of an expr is the expr itself
441  * if type(expr) != pow, otherwise it is the child of pow
442  */
443 
444  /* if both are exponentials, create a new exponential with the sum of their children */
445  if( SCIPisExprExp(scip, current->expr) && SCIPisExprExp(scip, tomergenode->expr) )
446  {
447  SCIP_EXPR* sum;
448  SCIP_EXPR* simplifiedsum;
449  SCIP_EXPR* expexpr;
450  SCIP_EXPR* simplifiedexp;
451 
452  /* inform that expressions changed */
453  *changed = TRUE;
454 
455  /* create sum */
456  SCIP_CALL( SCIPcreateExprSum(scip, &sum, 1, SCIPexprGetChildren(current->expr), NULL, 0.0, ownercreate, ownercreatedata) );
457  SCIP_CALL( SCIPappendExprSumExpr(scip, sum, SCIPexprGetChildren(tomergenode->expr)[0], 1.0) );
458 
459  /* simplify sum */
460  SCIP_CALL( SCIPcallExprSimplify(scip, sum, &simplifiedsum, ownercreate, ownercreatedata) );
461  SCIP_CALL( SCIPreleaseExpr(scip, &sum) );
462 
463  /* create exponential */
464  SCIP_CALL( SCIPcreateExprExp(scip, &expexpr, simplifiedsum, ownercreate, ownercreatedata) );
465  SCIP_CALL( SCIPreleaseExpr(scip, &simplifiedsum) );
466 
467  /* simplify exponential */
468  SCIP_CALL( SCIPcallExprSimplify(scip, expexpr, &simplifiedexp, ownercreate, ownercreatedata) );
469  SCIP_CALL( SCIPreleaseExpr(scip, &expexpr) );
470 
471  /* note that simplified exponential might be a product exp(x) * exp(-x + log(y*z)) -> y*z and so it is not a
472  * valid child of a simplified product; therefore we add it to the unsimplifiedchildren's list
473  */
474 
475  /* replace tomergenode's expression with simplifiedexp */
476  /* TODO: this code repeats below; add new function to avoid duplication */
477  SCIP_CALL( SCIPreleaseExpr(scip, &tomergenode->expr) );
478  tomergenode->expr = simplifiedexp;
479 
480  /* move tomergenode to unsimplifiedchildren */
481  aux = tomergenode;
482  tomergenode = tomergenode->next;
483  insertFirstList(aux, unsimplifiedchildren);
484 
485  /* remove current */
486  if( current == *finalchildren )
487  {
488  assert(previous == NULL);
489  aux = listPopFirst(finalchildren);
490  assert(aux == current);
491  current = *finalchildren;
492  }
493  else
494  {
495  assert(previous != NULL);
496  aux = current;
497  current = current->next;
498  previous->next = current;
499  }
500  SCIP_CALL( freeExprNode(scip, &aux) );
501 
502  continue;
503  }
504 
505  /* they were not exponentials, so collect bases and exponents */
506  if( SCIPisExprPower(scip, current->expr) )
507  {
508  base1 = SCIPexprGetChildren(current->expr)[0];
509  expo1 = SCIPgetExponentExprPow(current->expr);
510  issignpower1 = FALSE;
511  }
512  else if( SCIPisExprSignpower(scip, current->expr) )
513  {
514  base1 = SCIPexprGetChildren(current->expr)[0];
515  expo1 = SCIPgetExponentExprPow(current->expr);
516  issignpower1 = TRUE;
517  }
518  else
519  {
520  base1 = current->expr;
521  expo1 = 1.0;
522  issignpower1 = FALSE;
523  }
524  if( SCIPisExprPower(scip, tomergenode->expr) )
525  {
526  base2 = SCIPexprGetChildren(tomergenode->expr)[0];
527  expo2 = SCIPgetExponentExprPow(tomergenode->expr);
528  issignpower2 = FALSE;
529  }
530  else if( SCIPisExprSignpower(scip, tomergenode->expr) )
531  {
532  base2 = SCIPexprGetChildren(tomergenode->expr)[0];
533  expo2 = SCIPgetExponentExprPow(tomergenode->expr);
534  issignpower2 = TRUE;
535  }
536  else
537  {
538  base2 = tomergenode->expr;
539  expo2 = 1.0;
540  issignpower2 = FALSE;
541  }
542 
543  if( SCIPcompareExpr(scip, base1, base2) == 0 )
544  {
545  /* the bases are the same, so we should try to merge the multiplication of the powers */
546  SCIP_EXPR* power = NULL;
547 
548  if( !issignpower1 && !issignpower2 )
549  {
550  /* and both are normal power, then add to unsimplifiedchildren the resulting expr of simplify(base^(expo1 + expo2)) */
551 #if 0 /* TODO we should not loose the implicit base >= 0 constraint, if there is one, but then we should look at bounds on base; simplify currently doesn't */
552  /*
553  * unless expo1 or expo2 are fractional but expo1+expo2 is not fractional, then we better keep the original
554  * the reason for that is that x^fractional implies a constraint x >= 0
555  */
556  if( (EPSISINT(expo1, 0.0) && EPSISINT(expo2, 0.0)) || !EPSISINT(expo1+expo2, 0.0) ) /*lint !e835*/
557 #endif
558  {
559  SCIP_CALL( SCIPcreateExprPow(scip, &power, base1, expo1 + expo2, ownercreate, ownercreatedata) );
560  }
561  }
562  else if( issignpower1 ^ issignpower2 )
563  {
564  /* exactly one is signpower: sign(x) |x|^expo1 x^expo2 = sign(x)^(1+expo2) |x|^(expo1+expo2), with x = base */
565  if( EPSISINT(expo2, 0.0) ) /*lint !e835*/
566  {
567  if( (int)expo2 % 2 == 0 )
568  {
569  /* if expo2 is even, then sign(x)^(1+expo2) = sign(x), so we have signpower: sign(x) |x|^(expo1+expo2)
570  * TODO: we can remove this case distinction once the simplification of power expressions tranform
571  * |expr|^even -> expr^even, since the call to SCIPcallExprSimplify(scip, conshdlr, power,
572  * &simplifiedpower) below will take care of this.
573  */
574  SCIP_CALL( SCIPcreateExprSignpower(scip, &power, base1, expo1 + expo2, ownercreate, ownercreatedata) );
575  }
576  else
577  {
578  /* if expo2 is odd, then sign(x)^(1+expo2) = 1, so we have |x|^(expo1+expo2) */
579  SCIP_EXPR* absbase;
580 
581  SCIP_CALL( SCIPcreateExprAbs(scip, &absbase, base1, ownercreate, ownercreatedata) );
582  SCIP_CALL( SCIPcreateExprPow(scip, &power, absbase, expo1 + expo2, ownercreate, ownercreatedata) );
583  SCIP_CALL( SCIPreleaseExpr(scip, &absbase) );
584  }
585  }
586  else if( !EPSISINT(expo1+expo2, 0.0) ) /*lint !e835*/
587  {
588  /* if expo2 is fractional and expo1+expo2 is fractional, then we need x >= 0, so we can use x^(expo1+expo2) */
589  SCIP_CALL( SCIPcreateExprPow(scip, &power, base1, expo1 + expo2, ownercreate, ownercreatedata) );
590  }
591  /* else: expo2 is fractional but expo1+expo2 is integral, then we better do not do anything for now
592  * (leave power at NULL)
593  */
594  }
595  else
596  {
597  /* if both are signpower, then we have |base|^(expo1+expo2)
598  * if expo1+expo2 is even, then we can change this to base^(expo1+expo2)
599  */
600  if( EPSISINT(expo1+expo2, 0.0) && (int)(expo1+expo2)%2 == 0 ) /*lint !e835*/
601  {
602  SCIP_CALL( SCIPcreateExprPow(scip, &power, base1, expo1 + expo2, ownercreate, ownercreatedata) );
603  }
604  else
605  {
606  SCIP_EXPR* absbase;
607 
608  SCIP_CALL( SCIPcreateExprAbs(scip, &absbase, base1, ownercreate, ownercreatedata) );
609  SCIP_CALL( SCIPcreateExprPow(scip, &power, absbase, expo1 + expo2, ownercreate, ownercreatedata) );
610  SCIP_CALL( SCIPreleaseExpr(scip, &absbase) );
611  }
612  }
613 
614  if( power != NULL )
615  {
616  /* we have created a new power: simplify again and continue */
617  SCIP_EXPR* simplifiedpower;
618 
619  /* call simplifyPow or simplifySignpower */
620  SCIP_CALL( SCIPcallExprSimplify(scip, power, &simplifiedpower, ownercreate, ownercreatedata) );
621  SCIP_CALL( SCIPreleaseExpr(scip, &power) );
622 
623  /* replace tomergenode's expression with simplifiedpower */
624  SCIP_CALL( SCIPreleaseExpr(scip, &tomergenode->expr) );
625  tomergenode->expr = simplifiedpower;
626 
627  *changed = TRUE;
628 
629  /* move tomergenode to unsimplifiedchildren */
630  aux = tomergenode;
631  tomergenode = tomergenode->next;
632  insertFirstList(aux, unsimplifiedchildren);
633 
634  /* remove current */
635  if( current == *finalchildren )
636  {
637  assert(previous == NULL);
638  aux = listPopFirst(finalchildren);
639  assert(aux == current);
640  current = *finalchildren;
641  }
642  else
643  {
644  assert(previous != NULL);
645  aux = current;
646  current = current->next;
647  previous->next = current;
648  }
649  SCIP_CALL( freeExprNode(scip, &aux) );
650 
651  continue;
652  }
653  }
654 
655  /* bases are not the same, or we do not want to merge them
656  * then expressions cannot be the same
657  * therefore we need to insert tomergenode in finalchildren
658  * for this, we need to take care of the order
659  */
660  compareres = SCIPcompareExpr(scip, current->expr, tomergenode->expr);
661  if( compareres == -1 )
662  {
663  /* current < tomergenode => move current */
664  previous = current;
665  current = current->next;
666  }
667  else
668  {
669  *changed = TRUE;
670  assert(compareres == 1);
671 
672  /* insert: if current is the first node, then insert at beginning; otherwise, insert between previous and current */
673  if( current == *finalchildren )
674  {
675  assert(previous == NULL);
676  aux = tomergenode;
677  tomergenode = tomergenode->next;
678  insertFirstList(aux, finalchildren);
679  previous = *finalchildren;
680  }
681  else
682  {
683  assert(previous != NULL);
684  /* extract */
685  aux = tomergenode;
686  tomergenode = tomergenode->next;
687  /* insert */
688  previous->next = aux;
689  aux->next = current;
690  previous = aux;
691  }
692  }
693  }
694 
695  /* if all nodes of tomerge were merged, we are done */
696  if( tomergenode == NULL )
697  return SCIP_OKAY;
698 
699  assert(current == NULL);
700 
701  /* if all nodes of finalchildren were cancelled by nodes of tomerge (i.e., transfered to unsimplifiedchildren),
702  * then the rest of tomerge is finalchildren
703  */
704  if( *finalchildren == NULL )
705  {
706  assert(previous == NULL);
707  *finalchildren = tomergenode;
708  return SCIP_OKAY;
709  }
710 
711  /* there are still nodes of tomerge unmerged; these nodes are larger than finalchildren, so append at end */
712  assert(previous != NULL && previous->next == NULL);
713  previous->next = tomergenode;
714 
715  return SCIP_OKAY;
716 }
717 
718 /** simplifies the given (simplified) exprs so that they can be factors of a simplified product
719  *
720  * in particular, it will sort and multiply factors whose product leads to new expressions
721  */
722 static
724  SCIP* scip, /**< SCIP data structure */
725  SCIP_EXPR** exprs, /**< factors to be simplified */
726  int nexprs, /**< number of factors */
727  SCIP_Real* simplifiedcoef, /**< buffer to store coefficient of PI exprs; needs to be initialized */
728  EXPRNODE** finalchildren, /**< expr node list to store the simplified factors */
729  SCIP_Bool* changed, /**< buffer to store whether some factor changed */
730  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
731  void* ownercreatedata /**< data to pass to ownercreate */
732  )
733 {
734  EXPRNODE* unsimplifiedchildren;
735 
736  /* set up list of current children (when looking at each of them individually, they are simplified, but as
737  * children of a product expression they might be unsimplified)
738  */
739  unsimplifiedchildren = NULL;
740  SCIP_CALL( createExprlistFromExprs(scip, exprs, nexprs, &unsimplifiedchildren) );
741 
742  *changed = FALSE;
743 
744  /* while there are still children to process */
745  *finalchildren = NULL;
746  while( unsimplifiedchildren != NULL )
747  {
748  EXPRNODE* tomerge;
749  EXPRNODE* first;
750 
751  first = listPopFirst(&unsimplifiedchildren);
752  assert(first != NULL);
753 
754 #ifdef SIMPLIFY_DEBUG
755  debugSimplify("simplifying factor:\n");
756  SCIP_CALL( SCIPprintExpr(scip, first->expr, NULL) );
757  SCIPinfoMessage(scip, NULL, "\n");
758 #endif
759 
760  /* enforces SP2, SP7 and SP13 */
761  tomerge = NULL;
762  SCIP_CALL( simplifyFactor(scip, first->expr, simplifiedcoef, &tomerge, changed) );
763 
764  /* enforces SP4 and SP5 note: merge frees (or uses) the nodes of the tomerge list */
765  SCIP_CALL( mergeProductExprlist(scip, tomerge, finalchildren, &unsimplifiedchildren, changed, ownercreate, ownercreatedata) );
766 
767  /* free first */
768  SCIP_CALL( freeExprlist(scip, &first) );
769 
770  /* if the simplified coefficient is 0, we can return value 0 */
771  if( *simplifiedcoef == 0.0 )
772  {
773  *changed = TRUE;
774  SCIP_CALL( freeExprlist(scip, finalchildren) );
775  SCIP_CALL( freeExprlist(scip, &unsimplifiedchildren) );
776  assert(*finalchildren == NULL);
777  break;
778  }
779  }
780  return SCIP_OKAY;
781 }
782 
783 /* make sure product has at least two children
784  * - if it is empty; return value
785  * - if it has one child and coef = 1; return child
786  * - if it has one child and coef != 1; return (sum 0 coef expr)
787  */
788 static
790  SCIP* scip, /**< SCIP data structure */
791  SCIP_Real simplifiedcoef, /**< simplified product should be simplifiedcoef * PI simplifiedfactors */
792  EXPRNODE* finalchildren, /**< factors of simplified product */
793  SCIP_EXPR** simplifiedexpr, /**< buffer to store the simplified expression */
794  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
795  void* ownercreatedata /**< data to pass to ownercreate */
796  )
797 {
798  /* empty list --> return value */
799  if( finalchildren == NULL )
800  {
801  SCIP_CALL( SCIPcreateExprValue(scip, simplifiedexpr, simplifiedcoef, ownercreate, ownercreatedata) );
802  return SCIP_OKAY;
803  }
804 
805  /* one child and coef equal to 1 --> return child */
806  if( finalchildren->next == NULL && simplifiedcoef == 1.0 )
807  {
808  *simplifiedexpr = finalchildren->expr;
809  SCIPcaptureExpr(*simplifiedexpr);
810  return SCIP_OKAY;
811  }
812 
813  /* one child and coef different from 1 --> return (sum 0 coef child) */
814  if( finalchildren->next == NULL )
815  {
816  SCIP_EXPR* sum;
817 
818  SCIP_CALL( SCIPcreateExprSum(scip, &sum, 1, &(finalchildren->expr), &simplifiedcoef, 0.0, ownercreate, ownercreatedata) );
819 
820  /* simplifying here is necessary, the product could have sums as children e.g., (prod 2 (sum 1 <x>))
821  * -> (sum 0 2 (sum 1 <x>)) and that needs to be simplified to (sum 0 2 <x>)
822  */
823  SCIP_CALL( SCIPcallExprSimplify(scip, sum, simplifiedexpr, ownercreate, ownercreatedata) );
824  SCIP_CALL( SCIPreleaseExpr(scip, &sum) );
825  return SCIP_OKAY;
826  }
827 
828  return SCIP_OKAY;
829 }
830 
831 /** checks if it is entropy expression */
832 static
834  SCIP* scip, /**< SCIP data structure */
835  SCIP_Real simplifiedcoef, /**< simplified product should be simplifiedcoef * PI simplifiedfactors */
836  EXPRNODE* finalchildren, /**< factors of simplified product */
837  SCIP_EXPR** simplifiedexpr, /**< buffer to store the simplified expression */
838  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
839  void* ownercreatedata /**< data to pass to ownercreate */
840  )
841 {
842  SCIP_EXPR* entropicchild = NULL;
843 
844  if( !(finalchildren != NULL && finalchildren->next != NULL && finalchildren->next->next == NULL) )
845  return SCIP_OKAY;
846 
847  /* could be log(expr) * expr, e.g., log(sin(x)) * sin(x) (OR11) */
848  if( strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(finalchildren->expr)), "log") == 0 )
849  {
850  assert(SCIPexprGetNChildren(finalchildren->expr) == 1);
851  if( 0 == SCIPcompareExpr(scip, SCIPexprGetChildren(finalchildren->expr)[0], finalchildren->next->expr) )
852  entropicchild = finalchildren->next->expr;
853  }
854  /* could be expr * log(expr), e.g., (1 + abs(x)) log(1 + abs(x)) (OR11) */
855  else if( strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(finalchildren->next->expr)), "log") == 0 )
856  {
857  assert(SCIPexprGetNChildren(finalchildren->next->expr) == 1);
858  if( 0 == SCIPcompareExpr(scip, SCIPexprGetChildren(finalchildren->next->expr)[0], finalchildren->expr) )
859  entropicchild = finalchildren->expr;
860  }
861 
862  /* success --> replace finalchildren by entropy expression */
863  if( entropicchild != NULL )
864  {
865  SCIP_EXPR* entropy;
866 
867  simplifiedcoef *= -1.0;
868 
869  SCIP_CALL( SCIPcreateExprEntropy(scip, &entropy, entropicchild, ownercreate, ownercreatedata) );
870 
871  /* enforces SP8: if simplifiedcoef != 1.0, transform it into a sum with the (simplified) entropy as child */
872  if( simplifiedcoef != 1.0 )
873  {
874  SCIP_CALL( SCIPcreateExprSum(scip, simplifiedexpr, 1, &entropy, &simplifiedcoef, 0.0, ownercreate, ownercreatedata) );
875  SCIP_CALL( SCIPreleaseExpr(scip, &entropy) );
876  }
877  else
878  *simplifiedexpr = entropy;
879  }
880 
881  return SCIP_OKAY;
882 }
883 
884 /* expands product of two sums or one sum and another expression
885  * -) two sums: (prod (sum c1 s1 ... sn) (sum c2 t1 ... tm)
886  * Builds a sum representing the expansion, where all of its children are simplified, and then simplify the sum
887  * - constant != 0 --> c1 ti or c2 * sj is simplified (ti, sj are not sums, because they are children of a simplified sum)
888  * - sj * ti may be not be simplified, so put them in a product list and simplify them from there
889  * -) one sum: (prod factor (sum c s1 ... sn))
890  * - c != 0 --> c * factor is simplified (i.e. factor is not sum!)
891  * - factor * si may be not be simplified, so put them in a product list and simplify them from there
892  */
893 static
895  SCIP* scip, /**< SCIP data structure */
896  SCIP_Real simplifiedcoef, /**< simplified product should be simplifiedcoef * PI simplifiedfactors */
897  EXPRNODE* finalchildren, /**< factors of simplified product */
898  SCIP_Bool expandalways, /**< whether to expand products of a sum and several factors in simplify (SP12b) */
899  SCIP_EXPR** simplifiedexpr, /**< buffer to store the simplified expression */
900  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
901  void* ownercreatedata /**< data to pass to ownercreate */
902  )
903 {
904  /* we need only two children */
905  if( ! (finalchildren != NULL && finalchildren->next != NULL && finalchildren->next->next == NULL) )
906  return SCIP_OKAY;
907 
908  /* handle both sums case */
909  if( SCIPisExprSum(scip, finalchildren->expr) && SCIPisExprSum(scip, finalchildren->next->expr) )
910  {
911  SCIP_EXPR* expanded = NULL;
912  SCIP_Real c1 = SCIPgetConstantExprSum(finalchildren->expr);
913  SCIP_Real c2 = SCIPgetConstantExprSum(finalchildren->next->expr);
914  int nchildren1 = SCIPexprGetNChildren(finalchildren->expr);
915  int nchildren2 = SCIPexprGetNChildren(finalchildren->next->expr);
916  int j;
917  int k;
918 
919 #ifdef SIMPLIFY_DEBUG
920  debugSimplify("Multiplying sum1 * sum2\n");
921  debugSimplify("sum1: \n");
922  SCIP_CALL( SCIPprintExpr(scip, finalchildren->expr, NULL) );
923  SCIPinfoMessage(scip, NULL, "\n");
924  debugSimplify("sum2: \n");
925  SCIP_CALL( SCIPprintExpr(scip, finalchildren->next->expr, NULL) );
926  SCIPinfoMessage(scip, NULL, "\n");
927 #endif
928  SCIP_CALL( SCIPcreateExprSum(scip, &expanded, 0, NULL, NULL, c1 * c2 * simplifiedcoef, ownercreate, ownercreatedata) );
929 
930  /* multiply c1 * sum2 */
931  if( c1 != 0.0 )
932  {
933  int i;
934 
935  for( i = 0; i < nchildren2; ++i )
936  {
937  SCIP_EXPR* term;
938 
939  term = SCIPexprGetChildren(finalchildren->next->expr)[i];
940  SCIP_CALL( SCIPappendExprSumExpr(scip, expanded, term, SCIPgetCoefsExprSum(finalchildren->next->expr)[i] * c1 * simplifiedcoef) );
941  /* we are just re-using a child here, so do not release term! */
942 #ifdef SIMPLIFY_DEBUG
943  debugSimplify("Multiplying %f * summand2_i\n", c1);
944  debugSimplify("summand2_i: \n");
945  SCIP_CALL( SCIPprintExpr(scip, term, NULL) );
946  SCIPinfoMessage(scip, NULL, "\n");
947 #endif
948  }
949  }
950  /* multiply c2 * sum1 */
951  if( c2 != 0.0 )
952  {
953  int i;
954 
955  for( i = 0; i < nchildren1; ++i )
956  {
957  SCIP_EXPR* term;
958 
959  term = SCIPexprGetChildren(finalchildren->expr)[i];
960  SCIP_CALL( SCIPappendExprSumExpr(scip, expanded, term, SCIPgetCoefsExprSum(finalchildren->expr)[i] * c2 * simplifiedcoef) );
961  /* we are just re-using a child here, so do not release term! */
962 #ifdef SIMPLIFY_DEBUG
963  debugSimplify("Multiplying summand1_i * %f\n", c2);
964  debugSimplify("summand1_i: \n");
965  SCIP_CALL( SCIPprintExpr(scip, term, NULL) );
966  SCIPinfoMessage(scip, NULL, "\n");
967 #endif
968  }
969  }
970  /* multiply sum1 * sum2 without constants */
971  for( j = 0; j < nchildren1; ++j )
972  {
973  SCIP_EXPR* factors[2];
974  SCIP_Real coef1;
975 
976  coef1 = SCIPgetCoefsExprSum(finalchildren->expr)[j];
977  factors[0] = SCIPexprGetChildren(finalchildren->expr)[j];
978  for( k = 0; k < nchildren2; ++k )
979  {
980  EXPRNODE* finalfactors;
981  SCIP_Real factorscoef;
982  SCIP_Real coef2;
983  SCIP_EXPR* term = NULL;
984  SCIP_Bool dummy;
985 
986  coef2 = SCIPgetCoefsExprSum(finalchildren->next->expr)[k];
987  factors[1] = SCIPexprGetChildren(finalchildren->next->expr)[k];
988 
989 #ifdef SIMPLIFY_DEBUG
990  debugSimplify("multiplying %g expr1 * %g expr2\n", coef1, coef2);
991  debugSimplify("expr1:\n");
992  SCIP_CALL( SCIPprintExpr(scip, factors[0], NULL) );
993  SCIPinfoMessage(scip, NULL, "\n");
994  debugSimplify("expr2\n");
995  SCIP_CALL( SCIPprintExpr(scip, factors[1], NULL) );
996  SCIPinfoMessage(scip, NULL, "\n");
997 #endif
998 
999  factorscoef = coef1 * coef2;
1000  SCIP_CALL( simplifyMultiplyChildren(scip, factors, 2, &factorscoef, &finalfactors, &dummy, ownercreate, ownercreatedata) );
1001  assert(factorscoef != 0.0);
1002 
1003 #ifdef SIMPLIFY_DEBUG
1004  {
1005  EXPRNODE* node;
1006  int i;
1007 
1008  debugSimplify("Building product from simplified factors\n");
1009  node = finalfactors;
1010  i = 0;
1011  while( node != NULL )
1012  {
1013  debugSimplify("factor %d (nuses %d):\n", i, SCIPexprGetNUses(node->expr));
1014  SCIP_CALL( SCIPprintExpr(scip, node->expr, NULL) );
1015  SCIPinfoMessage(scip, NULL, "\n");
1016  node = node->next;
1017  i++;
1018  }
1019  }
1020 #endif
1021 
1022  SCIP_CALL( buildSimplifiedProduct(scip, 1.0, &finalfactors, expandalways, TRUE, &term, ownercreate, ownercreatedata) );
1023  assert(finalfactors == NULL);
1024  assert(term != NULL);
1025 
1026 #ifdef SIMPLIFY_DEBUG
1027  debugSimplify("%g expr1 * %g expr2 = %g * product\n", coef1, coef2, coef1 * coef2);
1028  debugSimplify("product: (nused %d)\n", SCIPexprGetNUses(term));
1029  SCIP_CALL( SCIPprintExpr(scip, term, NULL) );
1030  SCIPinfoMessage(scip, NULL, "\n");
1031 #endif
1032 
1033  SCIP_CALL( SCIPappendExprSumExpr(scip, expanded, term, factorscoef * simplifiedcoef) );
1034 
1035  SCIP_CALL( SCIPreleaseExpr(scip, &term) );
1036  }
1037  }
1038 
1039  /* simplify the sum */
1040  SCIP_CALL( SCIPcallExprSimplify(scip, expanded, simplifiedexpr, ownercreate, ownercreatedata) );
1041  SCIP_CALL( SCIPreleaseExpr(scip, &expanded) );
1042 
1043  return SCIP_OKAY;
1044  }
1045 
1046  /* handle one sum case */
1047  if( SCIPisExprSum(scip, finalchildren->expr) || SCIPisExprSum(scip, finalchildren->next->expr) )
1048  {
1049  SCIP_EXPR* expanded = NULL;
1050  SCIP_EXPR* factors[2];
1051  SCIP_EXPR* sum = NULL;
1052  SCIP_Real constant;
1053  int nchildren;
1054  int j;
1055 
1056  if( SCIPisExprSum(scip, finalchildren->expr) )
1057  {
1058  assert(!SCIPisExprSum(scip, finalchildren->next->expr));
1059  sum = finalchildren->expr;
1060  factors[0] = finalchildren->next->expr;
1061  }
1062  else
1063  {
1064  assert(!SCIPisExprSum(scip, finalchildren->expr));
1065  sum = finalchildren->next->expr;
1066  factors[0] = finalchildren->expr;
1067  }
1068  constant = simplifiedcoef * SCIPgetConstantExprSum(sum);
1069  nchildren = SCIPexprGetNChildren(sum);
1070 
1071  SCIP_CALL( SCIPcreateExprSum(scip, &expanded, 1, &factors[0], &constant, 0.0, ownercreate, ownercreatedata) );
1072  /* we are just re-using a child here, so do not release factor! */
1073 
1074  for( j = 0; j < nchildren; ++j )
1075  {
1076  SCIP_Real coef;
1077  SCIP_Real termcoef;
1078  SCIP_Bool dummy;
1079  EXPRNODE* finalfactors;
1080  SCIP_EXPR* term = NULL;
1081 
1082  coef = SCIPgetCoefsExprSum(sum)[j];
1083  factors[1] = SCIPexprGetChildren(sum)[j];
1084 
1085  termcoef = coef;
1086  SCIP_CALL( simplifyMultiplyChildren(scip, factors, 2, &termcoef, &finalfactors, &dummy, ownercreate, ownercreatedata) );
1087  assert(termcoef != 0.0);
1088 
1089  SCIP_CALL( buildSimplifiedProduct(scip, 1.0, &finalfactors, expandalways, TRUE, &term, ownercreate, ownercreatedata) );
1090  assert(finalfactors == NULL);
1091  assert(term != NULL);
1092 
1093  SCIP_CALL( SCIPappendExprSumExpr(scip, expanded, term, termcoef * simplifiedcoef) );
1094  SCIP_CALL( SCIPreleaseExpr(scip, &term) );
1095  }
1096 
1097  /* simplify the sum */
1098  SCIP_CALL( SCIPcallExprSimplify(scip, expanded, simplifiedexpr, ownercreate, ownercreatedata) );
1099  SCIP_CALL( SCIPreleaseExpr(scip, &expanded) );
1100  }
1101 
1102  return SCIP_OKAY;
1103 }
1104 
1105 /* expands product of one sum and other expressions
1106  * -) (prod factor ... factor (sum c s1 ... sn) factor ... factor )
1107  * - c != 0 --> c * factor is simplified (i.e. factor is not sum!)
1108  * - factor ... factor * si may be not be simplified, so put them in a product list and simplify them from there
1109  */
1110 static
1112  SCIP* scip, /**< SCIP data structure */
1113  SCIP_Real simplifiedcoef, /**< simplified product should be simplifiedcoef * prod simplifiedfactors */
1114  EXPRNODE* finalchildren, /**< factors of simplified product */
1115  SCIP_EXPR** simplifiedexpr, /**< buffer to store the simplified expression */
1116  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1117  void* ownercreatedata /**< data to pass to ownercreate */
1118  )
1119 {
1120  EXPRNODE* sum_node = NULL;
1121  EXPRNODE* n;
1122  int nfactors = 0;
1123  SCIP_EXPR** factors;
1124  int nchildren;
1125  SCIP_EXPR* expanded;
1126  int j;
1127 
1128  /* check whether there is exactly one sum, calc number of factors */
1129  for( n = finalchildren; n != NULL; n = n->next )
1130  {
1131  if( SCIPisExprSum(scip, n->expr) )
1132  {
1133  if( sum_node == NULL )
1134  sum_node = n;
1135  else
1136  return SCIP_OKAY; /* more than one sum */
1137  }
1138  else
1139  {
1140  ++nfactors;
1141  }
1142  }
1143  if( sum_node == NULL || nfactors == 0 ) /* no sum or no other factors */
1144  return SCIP_OKAY;
1145 
1146  /* collect exprs of all factors other than the sum */
1147  SCIP_CALL( SCIPallocBufferArray(scip, &factors, nfactors + 1) );
1148  for( n = finalchildren, j = 0; n != NULL; n = n->next )
1149  if( n != sum_node )
1150  factors[j++] = n->expr;
1151 
1152  /* build new sum expression */
1153  nchildren = SCIPexprGetNChildren(sum_node->expr);
1154  SCIP_CALL( SCIPcreateExprSum(scip, &expanded, 0, NULL, NULL, 0.0, ownercreate, ownercreatedata) );
1155 
1156  /* handle constant-from-sum * factors */
1157  if( SCIPgetConstantExprSum(sum_node->expr) != 0.0 )
1158  {
1159  if( nfactors == 1 )
1160  {
1161  SCIP_CALL( SCIPappendExprSumExpr(scip, expanded, factors[0], simplifiedcoef * SCIPgetConstantExprSum(sum_node->expr)) );
1162  }
1163  else
1164  {
1165  SCIP_Real termcoef = 1.0;
1166  SCIP_Bool dummy;
1167  EXPRNODE* finalfactors;
1168  SCIP_EXPR* term = NULL;
1169 
1170  SCIP_CALL( simplifyMultiplyChildren(scip, factors, nfactors, &termcoef, &finalfactors, &dummy, ownercreate, ownercreatedata) );
1171  assert(termcoef != 0.0);
1172 
1173  SCIP_CALL( buildSimplifiedProduct(scip, 1.0, &finalfactors, TRUE, TRUE, &term, ownercreate, ownercreatedata) );
1174  assert(finalfactors == NULL);
1175  assert(term != NULL);
1176 
1177  SCIP_CALL( SCIPappendExprSumExpr(scip, expanded, term, termcoef * simplifiedcoef * SCIPgetConstantExprSum(sum_node->expr)) );
1178  SCIP_CALL( SCIPreleaseExpr(scip, &term) );
1179  }
1180  }
1181 
1182  for( j = 0; j < nchildren; ++j )
1183  {
1184  SCIP_Real coef;
1185  SCIP_Real termcoef;
1186  SCIP_Bool dummy;
1187  EXPRNODE* finalfactors;
1188  SCIP_EXPR* term = NULL;
1189 
1190  coef = SCIPgetCoefsExprSum(sum_node->expr)[j];
1191  factors[nfactors] = SCIPexprGetChildren(sum_node->expr)[j];
1192 
1193  termcoef = coef;
1194  SCIP_CALL( simplifyMultiplyChildren(scip, factors, nfactors + 1, &termcoef, &finalfactors, &dummy, ownercreate, ownercreatedata) );
1195  assert(termcoef != 0.0);
1196 
1197  SCIP_CALL( buildSimplifiedProduct(scip, 1.0, &finalfactors, TRUE, TRUE, &term, ownercreate, ownercreatedata) );
1198  assert(finalfactors == NULL);
1199  assert(term != NULL);
1200 
1201  SCIP_CALL( SCIPappendExprSumExpr(scip, expanded, term, termcoef * simplifiedcoef) );
1202  SCIP_CALL( SCIPreleaseExpr(scip, &term) );
1203  }
1204 
1205  /* simplify the sum */
1206  SCIP_CALL( SCIPcallExprSimplify(scip, expanded, simplifiedexpr, ownercreate, ownercreatedata) );
1207  SCIP_CALL( SCIPreleaseExpr(scip, &expanded) );
1208 
1209  SCIPfreeBufferArray(scip, &factors);
1210 
1211  return SCIP_OKAY;
1212 }
1213 
1214 /** builds a simplified product from simplifiedfactors
1215  *
1216  * @note this function also releases simplifiedfactors
1217  */
1218 static
1220  SCIP* scip, /**< SCIP data structure */
1221  SCIP_Real simplifiedcoef, /**< simplified product should be simplifiedcoef * PI simplifiedfactors */
1222  EXPRNODE** simplifiedfactors, /**< factors of simplified product */
1223  SCIP_Bool expandalways, /**< whether to expand products of a sum and several factors in simplify (SP12b) */
1224  SCIP_Bool changed, /**< indicates whether some of the simplified factors was changed */
1225  SCIP_EXPR** simplifiedexpr, /**< buffer to store the simplified expression */
1226  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1227  void* ownercreatedata /**< data to pass to ownercreate */
1228  )
1229 {
1230  EXPRNODE* finalchildren = *simplifiedfactors;
1231 
1232  /* build product expression from finalchildren and post-simplify */
1233  debugSimplify("[simplifyProduct] finalchildren has length %d\n", listLength(finalchildren));
1234 
1235  *simplifiedexpr = NULL;
1236 
1237  SCIP_CALL( enforceSP11(scip, simplifiedcoef, *simplifiedfactors, simplifiedexpr, ownercreate, ownercreatedata) );
1238  if( *simplifiedexpr != NULL )
1239  goto CLEANUP;
1240 
1241  SCIP_CALL( enforceSP12(scip, simplifiedcoef, *simplifiedfactors, expandalways, simplifiedexpr, ownercreate, ownercreatedata) );
1242  if( *simplifiedexpr != NULL )
1243  goto CLEANUP;
1244 
1245  if( expandalways )
1246  {
1247  SCIP_CALL( enforceSP12b(scip, simplifiedcoef, *simplifiedfactors, simplifiedexpr, ownercreate, ownercreatedata) );
1248  if( *simplifiedexpr != NULL )
1249  goto CLEANUP;
1250  }
1251 
1252  SCIP_CALL( enforceSP10(scip, simplifiedcoef, *simplifiedfactors, simplifiedexpr, ownercreate, ownercreatedata) );
1253  if( *simplifiedexpr != NULL )
1254  goto CLEANUP;
1255 
1256  /* enforces SP8: if simplifiedcoef != 1.0, transform it into a sum with the (simplified) product as child */
1257  if( simplifiedcoef != 1.0 )
1258  {
1259  SCIP_EXPR* aux;
1260  SCIP_EXPR* sum;
1261 
1262  /* create sum */
1263  SCIP_CALL( createExprProductFromExprlist(scip, finalchildren, 1.0, &aux, ownercreate, ownercreatedata) );
1264  SCIP_CALL( SCIPcreateExprSum(scip, &sum, 1, &aux, &simplifiedcoef, 0.0, ownercreate, ownercreatedata) );
1265  SCIP_CALL( SCIPreleaseExpr(scip, &aux) );
1266 
1267  /* simplify sum */
1268  SCIP_CALL( SCIPcallExprSimplify(scip, sum, simplifiedexpr, ownercreate, ownercreatedata) );
1269  SCIP_CALL( SCIPreleaseExpr(scip, &sum) );
1270 
1271  goto CLEANUP;
1272  }
1273 
1274  /* build product expression from list */
1275  if( changed )
1276  {
1277  SCIP_CALL( createExprProductFromExprlist(scip, finalchildren, simplifiedcoef, simplifiedexpr, ownercreate, ownercreatedata) );
1278  goto CLEANUP;
1279  }
1280 
1281 CLEANUP:
1282 
1283  SCIP_CALL( freeExprlist(scip, simplifiedfactors) );
1284  return SCIP_OKAY;
1285 }
1286 
1287 /** computes an estimator for a product as a vertex polyhedral function
1288  *
1289  * Since the product is multilinear, its convex and concave envelopes are piecewise linear.
1290  */
1291 static
1293  SCIP* scip, /**< SCIP data structure */
1294  SCIP_CONSHDLR* conshdlr, /**< nonlinear constraint handler */
1295  int nfactors, /**< number of factors */
1296  SCIP_INTERVAL* bounds, /**< bound for each factor */
1297  SCIP_Real constantfactor, /**< another constant factor */
1298  SCIP_Real* refpoint, /**< reference point where to estimate, or NULL if called from initestimates */
1299  SCIP_Bool overestimate, /**< should estimator overestimate expr (TRUE) or underestimate (FALSE) */
1300  SCIP_Real targetvalue, /**< no need to compute facet if value in xstar would be worse than target value */
1301  SCIP_Real* coefs, /**< array to store cut coefficients */
1302  SCIP_Real* constant, /**< pointer to store cut constant */
1303  SCIP_Bool* success /**< pointer to store whether estimation was successful */
1304  )
1305 {
1306  SCIP_Real* box;
1307  SCIP_Real* xstar;
1308  int nfixed;
1309  int i;
1310 
1311  assert(conshdlr != NULL);
1312  assert(nfactors > 0);
1313  assert(bounds != NULL);
1314  assert(constantfactor != 0.0);
1315  assert(coefs != NULL);
1316  assert(constant != NULL);
1317  assert(success != NULL);
1318 
1319  *success = FALSE;
1320 
1321  /* assemble box, check for unbounded variables, assemble xstar */
1322  SCIP_CALL( SCIPallocBufferArray(scip, &box, 2*nfactors) );
1323  SCIP_CALL( SCIPallocBufferArray(scip, &xstar, nfactors) );
1324  for( i = 0, nfixed = 0; i < nfactors; ++i )
1325  {
1326  assert(!SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, bounds[i]));
1327 
1328  if( SCIPisInfinity(scip, -bounds[i].inf) || SCIPisInfinity(scip, bounds[i].sup) )
1329  {
1330  SCIPdebugMsg(scip, "a factor is unbounded, no cut is possible\n");
1331  goto CLEANUP;
1332  }
1333 
1334  box[2*i] = bounds[i].inf;
1335  box[2*i+1] = bounds[i].sup;
1336 
1337  xstar[i] = refpoint != NULL ? refpoint[i] : 0.5 * (box[2*i] + box[2*i+1]);
1338 
1339  if( SCIPisRelEQ(scip, box[2*i], box[2*i+1]) )
1340  ++nfixed;
1341  }
1342 
1343  if( nfixed < nfactors && nfactors - nfixed <= SCIP_MAXVERTEXPOLYDIM )
1344  {
1346  overestimate, prodfunction, &constantfactor, xstar, box, nfactors, targetvalue, success, coefs, constant) );
1347  }
1348 
1349 CLEANUP:
1350  SCIPfreeBufferArray(scip, &xstar);
1351  SCIPfreeBufferArray(scip, &box);
1352 
1353  return SCIP_OKAY;
1354 }
1355 
1356 /*
1357  * Callback methods of expression handler
1358  */
1359 
1360 /** simplifies a product expression
1361  *
1362  * Summary: we first build a list of expressions (called finalchildren) which will be the children of the simplified product
1363  * and then we process this list in order to enforce SP8 and SP10.
1364  *
1365  * Description: In order to build finalchildren, we first build a list of unsimplified children (called unsimplifiedchildren)
1366  * with the children of the product. Each node of the list is manipulated (see simplifyFactor) in order to satisfy
1367  * SP2 and SP7 as follows:
1368  * - SP7: if the node's expression is a value, multiply the value to the products's coef
1369  * - SP2: if the node's expression is a product, then build a list with the child's children
1370  *
1371  * Then, we merge the built list (or the simplified node) into finalchildren. While merging, nodes from finalchildren
1372  * can go back to unsimplifiedchildren for further processing (see mergeProductExprlist() for more details).
1373  * After building finalchildren, we create the simplified product out of it, taking care that SP8 and SP10 are satisfied
1374  */
1375 static
1376 SCIP_DECL_EXPRSIMPLIFY(simplifyProduct)
1377 { /*lint --e{715}*/
1378  EXPRNODE* finalchildren;
1379  SCIP_Real simplifiedcoef;
1380  SCIP_Bool changed;
1381 
1382  assert(expr != NULL);
1383  assert(simplifiedexpr != NULL);
1384 
1385  simplifiedcoef = SCIPgetCoefExprProduct(expr);
1386 
1387 #ifdef SIMPLIFY_DEBUG
1388  debugSimplify("Simplifying expr:\n");
1389  SCIP_CALL( SCIPprintExpr(scip, expr, NULL) );
1390  SCIPinfoMessage(scip, NULL, "\n");
1391  debugSimplify("First multiplying children\n");
1392 #endif
1393 
1394  /* simplify and multiply factors */
1395  SCIP_CALL( simplifyMultiplyChildren(scip, SCIPexprGetChildren(expr), SCIPexprGetNChildren(expr), &simplifiedcoef,
1396  &finalchildren, &changed, ownercreate, ownercreatedata) );
1397 
1398 #ifdef SIMPLIFY_DEBUG
1399  {
1400  EXPRNODE* node;
1401  int i;
1402 
1403  debugSimplify("Building product from simplified factors\n");
1404  node = finalchildren;
1405  i = 0;
1406  while( node != NULL )
1407  {
1408  debugSimplify("factor %d:\n", i);
1409  SCIP_CALL( SCIPprintExpr(scip, node->expr, NULL) );
1410  SCIPinfoMessage(scip, NULL, "\n");
1411  node = node->next;
1412  i++;
1413  }
1414  }
1415 #endif
1416 
1417  /* get simplified product from simplified factors in finalchildren */
1418  SCIP_CALL( buildSimplifiedProduct(scip, simplifiedcoef, &finalchildren, SCIPexprhdlrGetData(SCIPexprGetHdlr(expr))->expandalways, changed, simplifiedexpr, ownercreate,
1419  ownercreatedata) );
1420  assert(finalchildren == NULL);
1421 
1422  if( *simplifiedexpr == NULL )
1423  {
1424  *simplifiedexpr = expr;
1425 
1426  /* we have to capture it, since it must simulate a "normal" simplified call in which a new expression is created */
1427  SCIPcaptureExpr(*simplifiedexpr);
1428  }
1429  assert(*simplifiedexpr != NULL);
1430 
1431  return SCIP_OKAY;
1432 }
1433 
1434 /** compare two product expressions
1435  *
1436  * The order of two product expressions, u and v, is a lexicographical order on the factors.
1437  *
1438  * Starting from the *last*, we find the first child where they differ, say, the i-th.
1439  * Then u < v <=> u_i < v_i.
1440  * If there is no such children and they have different number of children, then u < v <=> nchildren(u) < nchildren(v).
1441  * If all children are the same and they have the same number of children, then u < v <=> coeff(u) < coeff(v).
1442  * Otherwise, they are the same.
1443  *
1444  * Note: we are assuming expression are simplified, so within u, we have u_1 < u_2, etc.
1445  *
1446  * Example: y * z < x * y * z
1447  */
1448 static
1449 SCIP_DECL_EXPRCOMPARE(compareProduct)
1450 { /*lint --e{715}*/
1451  int compareresult;
1452  int i;
1453  int j;
1454  int nchildren1;
1455  int nchildren2;
1456  SCIP_EXPR** children1;
1457  SCIP_EXPR** children2;
1458 
1459  nchildren1 = SCIPexprGetNChildren(expr1);
1460  nchildren2 = SCIPexprGetNChildren(expr2);
1461  children1 = SCIPexprGetChildren(expr1);
1462  children2 = SCIPexprGetChildren(expr2);
1463 
1464  for( i = nchildren1 - 1, j = nchildren2 - 1; i >= 0 && j >= 0; --i, --j )
1465  {
1466  compareresult = SCIPcompareExpr(scip, children1[i], children2[j]);
1467  if( compareresult != 0 )
1468  return compareresult;
1469  /* expressions are equal, continue */
1470  }
1471 
1472  /* all children of one expression are children of the other expression, use number of children as a tie-breaker */
1473  if( i < j )
1474  {
1475  assert(i == -1);
1476  /* expr1 has less elements, hence expr1 < expr2 */
1477  return -1;
1478  }
1479  if( i > j )
1480  {
1481  assert(j == -1);
1482  /* expr1 has more elements, hence expr1 > expr2 */
1483  return 1;
1484  }
1485 
1486  /* everything is equal, use coefficient as tie-breaker */
1487  assert(i == -1 && j == -1);
1488  if( SCIPgetCoefExprProduct(expr1) < SCIPgetCoefExprProduct(expr2) )
1489  return -1;
1490  if( SCIPgetCoefExprProduct(expr1) > SCIPgetCoefExprProduct(expr2) )
1491  return 1;
1492 
1493  /* they are equal */
1494  return 0;
1495 }
1496 
1497 /** expression handler copy callback */
1498 static
1499 SCIP_DECL_EXPRCOPYHDLR(copyhdlrProduct)
1500 { /*lint --e{715}*/
1502 
1503  return SCIP_OKAY;
1504 }
1505 
1506 /** expression handler free callback */
1507 static
1508 SCIP_DECL_EXPRFREEHDLR(freehdlrProduct)
1509 { /*lint --e{715}*/
1510  assert(scip != NULL);
1511  assert(exprhdlr != NULL);
1512  assert(exprhdlrdata != NULL);
1513  assert(*exprhdlrdata != NULL);
1514 
1515  SCIPfreeBlockMemory(scip, exprhdlrdata);
1516  assert(*exprhdlrdata == NULL);
1517 
1518  return SCIP_OKAY;
1519 }
1520 
1521 /** expression data copy callback */
1522 static
1523 SCIP_DECL_EXPRCOPYDATA(copydataProduct)
1524 { /*lint --e{715}*/
1525  SCIP_EXPRDATA* sourceexprdata;
1526 
1527  assert(targetexprdata != NULL);
1528  assert(sourceexpr != NULL);
1529 
1530  sourceexprdata = SCIPexprGetData(sourceexpr);
1531  assert(sourceexprdata != NULL);
1532 
1533  SCIP_CALL( SCIPduplicateBlockMemory(targetscip, targetexprdata, sourceexprdata) );
1534 
1535  return SCIP_OKAY;
1536 }
1537 
1538 /** expression data free callback */
1539 static
1540 SCIP_DECL_EXPRFREEDATA(freedataProduct)
1541 { /*lint --e{715}*/
1542  SCIP_EXPRDATA* exprdata;
1543 
1544  assert(expr != NULL);
1545 
1546  exprdata = SCIPexprGetData(expr);
1547  assert(exprdata != NULL);
1548 
1549  SCIPfreeBlockMemory(scip, &exprdata);
1550 
1551  SCIPexprSetData(expr, NULL);
1552 
1553  return SCIP_OKAY;
1554 }
1555 
1556 /** expression print callback */
1557 static
1558 SCIP_DECL_EXPRPRINT(printProduct)
1559 { /*lint --e{715}*/
1560  SCIP_EXPRDATA* exprdata;
1561 
1562  assert(expr != NULL);
1563 
1564  exprdata = SCIPexprGetData(expr);
1565  assert(exprdata != NULL);
1566 
1567  switch( stage )
1568  {
1570  {
1571  /* print opening parenthesis, if necessary */
1572  if( EXPRHDLR_PRECEDENCE <= parentprecedence )
1573  {
1574  SCIPinfoMessage(scip, file, "(");
1575  }
1576 
1577  /* print coefficient, if not one */
1578  if( exprdata->coefficient != 1.0 )
1579  {
1580  if( exprdata->coefficient < 0.0 && EXPRHDLR_PRECEDENCE > parentprecedence )
1581  {
1582  SCIPinfoMessage(scip, file, "(%g)", exprdata->coefficient);
1583  }
1584  else
1585  {
1586  SCIPinfoMessage(scip, file, "%g", exprdata->coefficient);
1587  }
1588  }
1589  break;
1590  }
1591 
1593  {
1594  /* print multiplication sign, if not first factor */
1595  if( exprdata->coefficient != 1.0 || currentchild > 0 )
1596  {
1597  SCIPinfoMessage(scip, file, "*");
1598  }
1599  break;
1600  }
1601 
1603  {
1604  break;
1605  }
1606 
1608  {
1609  /* print closing parenthesis, if necessary */
1610  if( EXPRHDLR_PRECEDENCE <= parentprecedence )
1611  {
1612  SCIPinfoMessage(scip, file, ")");
1613  }
1614  break;
1615  }
1616 
1617  default:
1618  /* all stages should have been covered above */
1619  SCIPABORT();
1620  }
1621 
1622  return SCIP_OKAY;
1623 }
1624 
1625 /** product hash callback */
1626 static
1628 { /*lint --e{715}*/
1629  SCIP_EXPRDATA* exprdata;
1630  int c;
1631 
1632  assert(scip != NULL);
1633  assert(expr != NULL);
1634  assert(hashkey != NULL);
1635  assert(childrenhashes != NULL);
1636 
1637  exprdata = SCIPexprGetData(expr);
1638  assert(exprdata != NULL);
1639 
1640  *hashkey = EXPRHDLR_HASHKEY;
1641  *hashkey ^= SCIPcalcFibHash(exprdata->coefficient);
1642 
1643  for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
1644  *hashkey ^= childrenhashes[c];
1645 
1646  return SCIP_OKAY;
1647 }
1648 
1649 /** expression point evaluation callback */
1650 static
1652 { /*lint --e{715}*/
1653  SCIP_EXPRDATA* exprdata;
1654  SCIP_Real childval;
1655  int c;
1656 
1657  assert(expr != NULL);
1658 
1659  exprdata = SCIPexprGetData(expr);
1660  assert(exprdata != NULL);
1661 
1662  *val = exprdata->coefficient;
1663  for( c = 0; c < SCIPexprGetNChildren(expr) && (*val != 0.0); ++c )
1664  {
1665  childval = SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[c]);
1666  assert(childval != SCIP_INVALID);
1667 
1668  *val *= childval;
1669  }
1670 
1671  return SCIP_OKAY;
1672 }
1673 
1674 /** derivative evaluation callback computing <gradient, children.dot>
1675  *
1676  * If expr is \f$\prod_i x_i\f$, then computes \f$\sum_j \prod_{i\neq j} x_i x^{\text{dot}}_j\f$.
1677  */
1678 static
1679 SCIP_DECL_EXPRFWDIFF(fwdiffProduct)
1680 { /*lint --e{715}*/
1681  int c;
1682 
1683  assert(expr != NULL);
1684  assert(dot != NULL);
1685 
1686  assert(SCIPexprGetData(expr) != NULL);
1687 
1688  /* TODO add special handling for nchildren == 2 */
1689 
1690  /**! [SnippetExprFwdiffProduct] */
1691  *dot = 0.0;
1692  for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
1693  {
1694  SCIP_EXPR* child;
1695 
1696  child = SCIPexprGetChildren(expr)[c];
1697 
1698  assert(SCIPexprGetEvalValue(child) != SCIP_INVALID);
1699  assert(SCIPexprGetDot(child) != SCIP_INVALID);
1700 
1701  if( SCIPexprGetDot(child) == 0.0 )
1702  continue;
1703 
1704  if( SCIPexprGetEvalValue(child) != 0.0 )
1705  *dot += SCIPexprGetEvalValue(expr) / SCIPexprGetEvalValue(child) * SCIPexprGetDot(child);
1706  else
1707  {
1708  SCIP_Real partial;
1709  int i;
1710 
1711  partial = SCIPexprGetData(expr)->coefficient;
1712  for( i = 0; i < SCIPexprGetNChildren(expr) && (partial != 0.0); ++i )
1713  {
1714  if( i == c )
1715  continue;
1716 
1717  partial *= SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[i]);
1718  }
1719  *dot += partial * SCIPexprGetDot(child);
1720  }
1721  }
1722  /**! [SnippetExprFwdiffProduct] */
1723 
1724  return SCIP_OKAY;
1725 }
1726 
1727 /** expression backward forward derivative evaluation callback
1728  *
1729  * Computes \f$\frac{\partial}{\partial \text{childidx}} ( \langle \text{gradient}, \text{children.dot}\rangle )\f$.
1730  *
1731  * If expr is \f$\prod_i x_i\f$, and childidx is \f$k\f$ then computes
1732  * \f$\partial_k \sum_j \prod_{i \neq j} x_i x^{\text{dot}}_j
1733  * = \sum_{j \neq k} \prod_{i \neq j, k} x_i x^{\text{dot}}_j\f$
1734  */
1735 static
1736 SCIP_DECL_EXPRBWFWDIFF(bwfwdiffProduct)
1737 { /*lint --e{715}*/
1738  SCIP_EXPR* partialchild;
1739  int c;
1740 
1741  assert(expr != NULL);
1742  assert(bardot != NULL);
1743  assert(SCIPexprGetData(expr) != NULL);
1744  assert(childidx >= 0 && childidx < SCIPexprGetNChildren(expr));
1745 
1746  partialchild = SCIPexprGetChildren(expr)[childidx];
1747  assert(partialchild != NULL);
1748  assert(!SCIPisExprValue(scip, partialchild));
1749  assert(SCIPexprGetEvalValue(partialchild) != SCIP_INVALID);
1750 
1751  /* TODO add special handling for nchildren == 2 */
1752 
1753  /**! [SnippetExprBwfwdiffProduct] */
1754  *bardot = 0.0;
1755  for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
1756  {
1757  SCIP_EXPR* child;
1758 
1759  if( c == childidx )
1760  continue;
1761 
1762  child = SCIPexprGetChildren(expr)[c];
1763 
1764  assert(SCIPexprGetEvalValue(child) != SCIP_INVALID);
1765  assert(SCIPexprGetDot(child) != SCIP_INVALID);
1766 
1767  if( SCIPexprGetDot(child) == 0.0 )
1768  continue;
1769 
1770  if( SCIPexprGetEvalValue(child) != 0.0 && SCIPexprGetEvalValue(partialchild) != 0.0 )
1771  *bardot += SCIPexprGetEvalValue(expr) / (SCIPexprGetEvalValue(child) * SCIPexprGetEvalValue(partialchild)) * SCIPexprGetDot(child);
1772  else
1773  {
1774  SCIP_Real partial;
1775  int i;
1776 
1777  partial = SCIPexprGetData(expr)->coefficient;
1778  for( i = 0; i < SCIPexprGetNChildren(expr) && (partial != 0.0); ++i )
1779  {
1780  if( i == c || i == childidx )
1781  continue;
1782 
1783  partial *= SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[i]);
1784  }
1785  *bardot += partial * SCIPexprGetDot(child);
1786  }
1787  }
1788  /**! [SnippetExprBwfwdiffProduct] */
1789 
1790  return SCIP_OKAY;
1791 }
1792 
1793 /** expression derivative evaluation callback */
1794 static
1795 SCIP_DECL_EXPRBWDIFF(bwdiffProduct)
1796 { /*lint --e{715}*/
1797  SCIP_EXPR* child;
1798 
1799  assert(expr != NULL);
1800  assert(SCIPexprGetData(expr) != NULL);
1801  assert(childidx >= 0 && childidx < SCIPexprGetNChildren(expr));
1802 
1803  child = SCIPexprGetChildren(expr)[childidx];
1804  assert(child != NULL);
1805  assert(!SCIPisExprValue(scip, child));
1806  assert(SCIPexprGetEvalValue(child) != SCIP_INVALID);
1807 
1808  /* TODO add special handling for nchildren == 2 */
1809 
1810  /**! [SnippetExprBwdiffProduct] */
1811  if( !SCIPisZero(scip, SCIPexprGetEvalValue(child)) )
1812  {
1813  *val = SCIPexprGetEvalValue(expr) / SCIPexprGetEvalValue(child);
1814  }
1815  else
1816  {
1817  int i;
1818 
1819  *val = SCIPexprGetData(expr)->coefficient;
1820  for( i = 0; i < SCIPexprGetNChildren(expr) && (*val != 0.0); ++i )
1821  {
1822  if( i == childidx )
1823  continue;
1824 
1825  *val *= SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[i]);
1826  }
1827  }
1828  /**! [SnippetExprBwdiffProduct] */
1829 
1830  return SCIP_OKAY;
1831 }
1832 
1833 /** expression interval evaluation callback */
1834 static
1835 SCIP_DECL_EXPRINTEVAL(intevalProduct)
1836 { /*lint --e{715}*/
1837  SCIP_EXPRDATA* exprdata;
1838  int c;
1839 
1840  assert(expr != NULL);
1841 
1842  exprdata = SCIPexprGetData(expr);
1843  assert(exprdata != NULL);
1844 
1845  /**! [SnippetExprIntevalProduct] */
1846  SCIPintervalSet(interval, exprdata->coefficient);
1847 
1848  SCIPdebugMsg(scip, "inteval %p with %d children: %.20g", (void*)expr, SCIPexprGetNChildren(expr), exprdata->coefficient);
1849 
1850  for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
1851  {
1852  SCIP_INTERVAL childinterval;
1853 
1854  childinterval = SCIPexprGetActivity(SCIPexprGetChildren(expr)[c]);
1855  if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, childinterval) )
1856  {
1857  SCIPintervalSetEmpty(interval);
1858  break;
1859  }
1860 
1861  /* multiply childinterval with the so far computed interval */
1862  SCIPintervalMul(SCIP_INTERVAL_INFINITY, interval, *interval, childinterval);
1863 
1864  SCIPdebugMsgPrint(scip, " *[%.20g,%.20g]", childinterval.inf, childinterval.sup);
1865  }
1866  SCIPdebugMsgPrint(scip, " = [%.20g,%.20g]\n", interval->inf, interval->sup);
1867  /**! [SnippetExprIntevalProduct] */
1868 
1869  return SCIP_OKAY;
1870 }
1871 
1872 /** estimates a multilinear function of the form \f$ f(x) := a \prod_{i = 1}^n x_i \f$
1873  *
1874  * \f$ x_i \f$ are the auxiliary variables of the children.
1875  * If !overestimate, then we look for an affine underestimator of \f$ f(x) \f$ which has a value above targetvalue at \f$ x^* \f$,
1876  * i.e., \f$ g(x) := \alpha^T x + \beta \le f(x)\f$ for all \f$ x \f$ in the domain, such that \f$ \alpha x^* + \beta > \text{targetvalue}\f$.
1877  *
1878  * Since \f$ f(x) \f$ is componentwise linear, its convex envelope is piecewise linear and its value can be computed by
1879  * finding the largest affine underestimator.
1880  * This is done either explicitly (if n=2) or by solving an LP, see SCIPcomputeFacetVertexPolyhedralNonlinear().
1881  */
1882 static
1883 SCIP_DECL_EXPRESTIMATE(estimateProduct)
1884 { /*lint --e{715}*/
1885  SCIP_EXPRDATA* exprdata;
1886  int nchildren;
1887 
1888  assert(scip != NULL);
1889  assert(expr != NULL);
1890  assert(strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), EXPRHDLR_NAME) == 0);
1891  assert(refpoint != NULL);
1892  assert(coefs != NULL);
1893  assert(constant != NULL);
1894  assert(islocal != NULL);
1895  assert(branchcand != NULL);
1896  assert(*branchcand == TRUE);
1897  assert(success != NULL);
1898 
1899  exprdata = SCIPexprGetData(expr);
1900  assert(exprdata != NULL);
1901 
1902  *success = FALSE;
1903  *islocal = TRUE;
1904 
1905  nchildren = SCIPexprGetNChildren(expr);
1906 
1907  /* debug output: prints expression we are trying to estimate, bounds of variables and point */
1908 #ifdef SCIP_DEBUG
1909  {
1910  int c;
1911 
1912  SCIPdebugMsg(scip, "%sestimating product with %d variables\n", overestimate ? "over": "under", SCIPexprGetNChildren(expr));
1913  for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
1914  {
1915  SCIPdebugMsg(scip, "child %d = %g in [%g, %g]\n", c, refpoint[c], localbounds[c].inf, localbounds[c].sup);
1916 
1917  if( SCIPisInfinity(scip, localbounds[c].sup) || SCIPisInfinity(scip, -localbounds[c].inf) )
1918  {
1919  SCIPdebugMsg(scip, "unbounded factor related to\n");
1921  }
1922  }
1923  }
1924 #endif
1925 
1926  /* bilinear term */
1927  if( nchildren == 2 )
1928  {
1929  SCIP_Real refpointx;
1930  SCIP_Real refpointy;
1931  SCIP_INTERVAL bndx;
1932  SCIP_INTERVAL bndy;
1933 
1934  /* collect first variable */
1935  refpointx = refpoint[0];
1936  bndx = localbounds[0];
1938 
1939  /* collect second variable */
1940  refpointy = refpoint[1];
1941  bndy = localbounds[1];
1943 
1944  /* adjust the reference points */
1945  refpointx = MIN(MAX(refpointx, bndx.inf), bndx.sup);
1946  refpointy = MIN(MAX(refpointy, bndy.inf), bndy.sup);
1947 
1948  coefs[0] = 0.0;
1949  coefs[1] = 0.0;
1950  *constant = 0.0;
1951  *success = TRUE;
1952 
1953  SCIPaddBilinMcCormick(scip, exprdata->coefficient, bndx.inf, bndx.sup, refpointx,
1954  bndy.inf, bndy.sup, refpointy, overestimate, &coefs[0], &coefs[1], constant,
1955  success);
1956  }
1957  else
1958  {
1959  SCIP_EXPRHDLRDATA* exprhdlrdata;
1960 
1961  exprhdlrdata = SCIPexprhdlrGetData(SCIPexprGetHdlr(expr));
1962  assert(exprhdlrdata != NULL);
1963 
1964  if( exprhdlrdata->conshdlr != NULL )
1965  {
1966  SCIP_CALL( estimateVertexPolyhedralProduct(scip, exprhdlrdata->conshdlr, nchildren, localbounds, exprdata->coefficient, refpoint, overestimate,
1967  targetvalue, coefs, constant, success) );
1968  }
1969  else
1970  {
1971  SCIPdebugMsg(scip, "no cons_nonlinear included in SCIP, cannot estimate vertex-polyhedral product function\n");
1972  }
1973  }
1974 
1975  return SCIP_OKAY;
1976 }
1977 
1978 /** initial estimators callback */
1979 static
1980 SCIP_DECL_EXPRINITESTIMATES(initestimatesProduct)
1981 {
1982  SCIP_EXPRDATA* exprdata;
1983  SCIP_Bool success = TRUE;
1984  int nchildren;
1985 
1986  assert(scip != NULL);
1987  assert(expr != NULL);
1988  assert(strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), EXPRHDLR_NAME) == 0);
1989  assert(nreturned != NULL);
1990 
1991  nchildren = SCIPexprGetNChildren(expr);
1992 
1993  exprdata = SCIPexprGetData(expr);
1994  assert(exprdata != NULL);
1995 
1996  if( nchildren == 2 )
1997  {
1998  SCIP_INTERVAL bndx = bounds[0];
1999  SCIP_INTERVAL bndy = bounds[1];
2000 
2001  constant[0] = 0.0;
2002  coefs[0][0] = 0.0;
2003  coefs[0][1] = 0.0;
2004 
2005  /* build estimator */
2006  SCIPaddBilinMcCormick(scip, exprdata->coefficient, bndx.inf, bndx.sup, (bndx.inf + bndx.sup) / 2.0,
2007  bndy.inf, bndy.sup, (bndy.inf + bndy.sup ) / 2.0, overestimate, &coefs[0][0], &coefs[0][1],
2008  constant, &success);
2009  }
2010  else
2011  {
2012  SCIP_EXPRHDLRDATA* exprhdlrdata;
2013 
2014  exprhdlrdata = SCIPexprhdlrGetData(SCIPexprGetHdlr(expr));
2015  assert(exprhdlrdata != NULL);
2016 
2017  if( exprhdlrdata->conshdlr != NULL )
2018  {
2019  SCIP_CALL( estimateVertexPolyhedralProduct(scip, exprhdlrdata->conshdlr, nchildren, bounds, exprdata->coefficient, NULL, overestimate,
2020  overestimate ? SCIPinfinity(scip) : -SCIPinfinity(scip), coefs[0], constant, &success) );
2021  }
2022  else
2023  {
2024  SCIPdebugMsg(scip, "no cons_nonlinear included in SCIP, cannot estimate vertex-polyhedral product function\n");
2025  }
2026  }
2027 
2028  if( success )
2029  *nreturned = 1;
2030 
2031  return SCIP_OKAY;
2032 }
2033 
2034 /** expression reverse propagation callback */
2035 static
2036 SCIP_DECL_EXPRREVERSEPROP(reversepropProduct)
2037 { /*lint --e{715}*/
2038  SCIP_EXPRDATA* exprdata;
2039  SCIP_INTERVAL childbounds;
2040  SCIP_INTERVAL otherfactor;
2041  SCIP_INTERVAL zero;
2042  int i;
2043  int j;
2044 
2045  assert(scip != NULL);
2046  assert(expr != NULL);
2047  assert(SCIPexprGetNChildren(expr) > 0);
2048  assert(infeasible != NULL);
2049  assert(childrenbounds != NULL);
2050 
2051  *infeasible = FALSE;
2052 
2053  /* too expensive (runtime here is quadratic in number of children)
2054  * TODO implement something faster for larger numbers of factors, e.g., split product into smaller products
2055  */
2056  if( SCIPexprGetNChildren(expr) > 10 )
2057  return SCIP_OKAY;
2058 
2059  /* not possible to learn bounds on children if expression bounds are unbounded in both directions */
2061  return SCIP_OKAY;
2062 
2063  exprdata = SCIPexprGetData(expr);
2064  assert(exprdata != NULL);
2065 
2066  /**! [SnippetExprReversepropProduct] */
2067  SCIPintervalSet(&zero, 0.0);
2068 
2069  /* f = const * prod_k c_k => c_i solves c_i * (const * prod_{j:j!=i} c_j) = f */
2070  for( i = 0; i < SCIPexprGetNChildren(expr) && !(*infeasible); ++i )
2071  {
2072  SCIPintervalSet(&otherfactor, exprdata->coefficient);
2073 
2074  /* compute prod_{j:j!=i} c_j */
2075  for( j = 0; j < SCIPexprGetNChildren(expr); ++j )
2076  {
2077  if( i == j )
2078  continue;
2079 
2080  /* TODO we should compute these only one time instead of repeating this for almost every i */
2081  childbounds = childrenbounds[j];
2082  if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, childbounds) )
2083  {
2084  *infeasible = TRUE;
2085  return SCIP_OKAY;
2086  }
2087 
2088  SCIPintervalMul(SCIP_INTERVAL_INFINITY, &otherfactor, otherfactor, childbounds);
2089  }
2090 
2091  childbounds = childrenbounds[i];
2092  if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, childbounds) )
2093  {
2094  *infeasible = TRUE;
2095  return SCIP_OKAY;
2096  }
2097 
2098  /* solve x*otherfactor = f for x in c_i */
2099  SCIPintervalSolveUnivariateQuadExpression(SCIP_INTERVAL_INFINITY, &childbounds, zero, otherfactor, bounds, childbounds);
2100 
2101  SCIPdebugMsg(scip, "child %d: solved [%g,%g]*x = [%g,%g] with x in [%g,%g] -> x = [%g,%g]\n", i, otherfactor.inf, otherfactor.sup,
2102  bounds.inf, bounds.sup,
2103  childrenbounds[i].inf, childrenbounds[i].sup,
2104  childbounds.inf, childbounds.sup);
2105 
2106  /* store computed bounds of the expression */
2107  SCIPintervalIntersect(&childrenbounds[i], childrenbounds[i], childbounds);
2108  if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, childrenbounds[i]) )
2109  {
2110  *infeasible = TRUE;
2111  return SCIP_OKAY;
2112  }
2113  }
2114  /**! [SnippetExprReversepropProduct] */
2115 
2116  return SCIP_OKAY;
2117 }
2118 
2119 /** expression curvature detection callback */
2120 static
2121 SCIP_DECL_EXPRCURVATURE(curvatureProduct)
2122 { /*lint --e{715}*/
2123  assert(scip != NULL);
2124  assert(expr != NULL);
2125  assert(success != NULL);
2126  assert(SCIPexprGetNChildren(expr) > 0);
2127 
2128  if( SCIPexprGetNChildren(expr) == 1 )
2129  {
2130  *childcurv = SCIPexprcurvMultiply(SCIPgetCoefExprProduct(expr), exprcurvature);
2131  *success = TRUE;
2132  }
2133  else
2134  {
2135  *success = FALSE;
2136  }
2137 
2138  return SCIP_OKAY;
2139 }
2140 
2141 /** expression monotonicity detection callback */
2142 static
2143 SCIP_DECL_EXPRMONOTONICITY(monotonicityProduct)
2144 { /*lint --e{715}*/
2145  SCIP_Real coef;
2146  int i;
2147  int nneg;
2148 
2149  assert(scip != NULL);
2150  assert(expr != NULL);
2151  assert(result != NULL);
2152  assert(SCIPexprGetNChildren(expr) >= 1);
2153  assert(childidx >= 0);
2154  assert(childidx < SCIPexprGetNChildren(expr));
2155 
2156  coef = SCIPgetCoefExprProduct(expr);
2157 
2158  /* count the number of negative children (except for childidx); if some children changes sign
2159  * -> monotonicity unknown
2160  */
2161  nneg = 0;
2162  for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
2163  {
2164  SCIP_INTERVAL interval;
2165 
2166  if( i == childidx )
2167  continue;
2168 
2169  assert(SCIPexprGetChildren(expr)[i] != NULL);
2171  interval = SCIPexprGetActivity(SCIPexprGetChildren(expr)[i]);
2172 
2173  if( SCIPintervalGetSup(interval) <= 0.0 )
2174  nneg++;
2175  else if( SCIPintervalGetInf(interval) < 0.0 )
2176  {
2177  *result = SCIP_MONOTONE_UNKNOWN;
2178  return SCIP_OKAY;
2179  }
2180  }
2181 
2182  /* note that the monotonicity depends on the sign of the coefficient */
2183  if( nneg % 2 == 0 )
2184  *result = (coef >= 0.0) ? SCIP_MONOTONE_INC : SCIP_MONOTONE_DEC;
2185  else
2186  *result = (coef >= 0.0) ? SCIP_MONOTONE_DEC : SCIP_MONOTONE_INC;
2187 
2188  return SCIP_OKAY;
2189 }
2190 
2191 /** expression integrality detection callback */
2192 static
2193 SCIP_DECL_EXPRINTEGRALITY(integralityProduct)
2194 { /*lint --e{715}*/
2195  SCIP_EXPRDATA* exprdata;
2196  int i;
2197 
2198  assert(scip != NULL);
2199  assert(expr != NULL);
2200  assert(isintegral != NULL);
2201 
2202  exprdata = SCIPexprGetData(expr);
2203  assert(exprdata != NULL);
2204 
2205  *isintegral = EPSISINT(exprdata->coefficient, 0.0); /*lint !e835*/
2206 
2207  for( i = 0; i < SCIPexprGetNChildren(expr) && *isintegral; ++i )
2208  {
2209  SCIP_EXPR* child = SCIPexprGetChildren(expr)[i];
2210  assert(child != NULL);
2211 
2212  *isintegral = SCIPexprIsIntegral(child);
2213  }
2214 
2215  return SCIP_OKAY;
2216 }
2217 
2218 /** expression callback to get information for symmetry detection */
2219 static
2220 SCIP_DECL_EXPRGETSYMDATA(getSymDataProduct)
2221 { /*lint --e{715}*/
2222  assert(scip != NULL);
2223  assert(expr != NULL);
2224  assert(symdata != NULL);
2225 
2226  SCIP_CALL( SCIPallocBlockMemory(scip, symdata) );
2227 
2228  (*symdata)->nconstants = 1;
2229  (*symdata)->ncoefficients = 0;
2230  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*symdata)->constants, 1) );
2231  (*symdata)->constants[0] = SCIPgetCoefExprProduct(expr);
2232 
2233  return SCIP_OKAY;
2234 }
2235 
2236 /** creates the handler for product expressions and includes it into SCIP */
2238  SCIP* scip /**< SCIP data structure */
2239  )
2240 {
2241  SCIP_EXPRHDLRDATA* exprhdlrdata;
2242  SCIP_EXPRHDLR* exprhdlr;
2243 
2244  /* allocate expression handler data */
2245  SCIP_CALL( SCIPallocClearBlockMemory(scip, &exprhdlrdata) );
2246  exprhdlrdata->conshdlr = SCIPfindConshdlr(scip, "nonlinear");
2247 
2249  exprhdlrdata) );
2250  assert(exprhdlr != NULL);
2251 
2252  SCIPexprhdlrSetCopyFreeHdlr(exprhdlr, copyhdlrProduct, freehdlrProduct);
2253  SCIPexprhdlrSetCopyFreeData(exprhdlr, copydataProduct, freedataProduct);
2254  SCIPexprhdlrSetSimplify(exprhdlr, simplifyProduct);
2255  SCIPexprhdlrSetCompare(exprhdlr, compareProduct);
2256  SCIPexprhdlrSetPrint(exprhdlr, printProduct);
2257  SCIPexprhdlrSetIntEval(exprhdlr, intevalProduct);
2258  SCIPexprhdlrSetEstimate(exprhdlr, initestimatesProduct, estimateProduct);
2259  SCIPexprhdlrSetReverseProp(exprhdlr, reversepropProduct);
2260  SCIPexprhdlrSetHash(exprhdlr, hashProduct);
2261  SCIPexprhdlrSetDiff(exprhdlr, bwdiffProduct, fwdiffProduct, bwfwdiffProduct);
2262  SCIPexprhdlrSetCurvature(exprhdlr, curvatureProduct);
2263  SCIPexprhdlrSetMonotonicity(exprhdlr, monotonicityProduct);
2264  SCIPexprhdlrSetIntegrality(exprhdlr, integralityProduct);
2265  SCIPexprhdlrSetGetSymdata(exprhdlr, getSymDataProduct);
2266 
2267  SCIP_CALL( SCIPaddBoolParam(scip, "expr/" EXPRHDLR_NAME "/expandalways",
2268  "whether to expand products of a sum and several factors in simplify",
2269  &exprhdlrdata->expandalways, FALSE, FALSE, NULL, NULL) );
2270 
2271  return SCIP_OKAY;
2272 }
2273 
2274 /** creates a product expression */
2276  SCIP* scip, /**< SCIP data structure */
2277  SCIP_EXPR** expr, /**< pointer where to store expression */
2278  int nchildren, /**< number of children */
2279  SCIP_EXPR** children, /**< children */
2280  SCIP_Real coefficient, /**< constant coefficient of product */
2281  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
2282  void* ownercreatedata /**< data to pass to ownercreate */
2283  )
2284 {
2285  SCIP_EXPRDATA* exprdata;
2286 
2287  /**! [SnippetCreateExprProduct] */
2288  SCIP_CALL( SCIPallocBlockMemory(scip, &exprdata) );
2289  exprdata->coefficient = coefficient;
2290 
2291  SCIP_CALL( SCIPcreateExpr(scip, expr, SCIPgetExprhdlrProduct(scip), exprdata, nchildren, children, ownercreate, ownercreatedata) );
2292  /**! [SnippetCreateExprProduct] */
2293 
2294  return SCIP_OKAY;
2295 }
2296 
2297 /* from pub_expr.h */
2298 
2299 /** gets the constant coefficient of a product expression */
2301  SCIP_EXPR* expr /**< product expression */
2302  )
2303 {
2304  SCIP_EXPRDATA* exprdata;
2305 
2306  assert(expr != NULL);
2307 
2308  exprdata = SCIPexprGetData(expr);
2309  assert(exprdata != NULL);
2310 
2311  return exprdata->coefficient;
2312 }
struct exprnode * next
Definition: expr_product.c:90
static SCIP_DECL_EXPRBWDIFF(bwdiffProduct)
#define NULL
Definition: def.h:267
static SCIP_DECL_VERTEXPOLYFUN(prodfunction)
Definition: expr_product.c:101
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIP_RETCODE SCIPcreateExprPow(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_Real exponent, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_pow.c:3194
static SCIP_DECL_EXPRHASH(hashProduct)
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition: scip_expr.c:1486
SCIP_Bool SCIPintervalIsEntire(SCIP_Real infinity, SCIP_INTERVAL operand)
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1717
static SCIP_RETCODE createExprNode(SCIP *scip, SCIP_EXPR *expr, EXPRNODE **newnode)
Definition: expr_product.c:181
static SCIP_DECL_EXPRINTEVAL(intevalProduct)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3854
SCIP_RETCODE SCIPcreateExprSignpower(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_Real exponent, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_pow.c:3218
void SCIPexprhdlrSetDiff(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRBWDIFF((*bwdiff)), SCIP_DECL_EXPRFWDIFF((*fwdiff)), SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff)))
Definition: expr.c:473
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:545
#define EXPRHDLR_HASHKEY
Definition: expr_product.c:54
static SCIP_DECL_EXPRFREEHDLR(freehdlrProduct)
#define EXPRHDLR_DESC
Definition: expr_product.c:52
SCIP_Real SCIPgetConstantExprSum(SCIP_EXPR *expr)
Definition: expr_sum.c:1567
static SCIP_RETCODE freeExprlist(SCIP *scip, EXPRNODE **exprlist)
Definition: expr_product.c:240
void SCIPexprhdlrSetGetSymdata(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRGETSYMDATA((*getsymdata)))
Definition: expr.c:521
static SCIP_DECL_EXPRSIMPLIFY(simplifyProduct)
static SCIP_DECL_EXPRPRINT(printProduct)
#define debugSimplify
Definition: expr_product.c:63
SCIP_EXPRHDLRDATA * SCIPexprhdlrGetData(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:575
#define FALSE
Definition: def.h:94
#define EPSISINT(x, eps)
Definition: def.h:210
handler for -x*log(x) expressions
struct SCIP_ExprData SCIP_EXPRDATA
Definition: type_expr.h:54
static SCIP_DECL_EXPRESTIMATE(estimateProduct)
SCIP_Real SCIPinfinity(SCIP *scip)
void SCIPintervalSolveUnivariateQuadExpression(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
SCIP_Real SCIPgetExponentExprPow(SCIP_EXPR *expr)
Definition: expr_pow.c:3457
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
static SCIP_DECL_EXPRCOPYHDLR(copyhdlrProduct)
static SCIP_RETCODE estimateVertexPolyhedralProduct(SCIP *scip, SCIP_CONSHDLR *conshdlr, int nfactors, SCIP_INTERVAL *bounds, SCIP_Real constantfactor, SCIP_Real *refpoint, SCIP_Bool overestimate, SCIP_Real targetvalue, SCIP_Real *coefs, SCIP_Real *constant, SCIP_Bool *success)
void SCIPexprhdlrSetHash(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRHASH((*hash)))
Definition: expr.c:451
SCIP_INTERVAL SCIPexprGetActivity(SCIP_EXPR *expr)
Definition: expr.c:4010
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
void SCIPexprhdlrSetIntegrality(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEGRALITY((*integrality)))
Definition: expr.c:440
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
SCIP_RETCODE SCIPcreateExprExp(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_exp.c:510
SCIP_EXPRHDLR * SCIPgetExprhdlrProduct(SCIP *scip)
Definition: scip_expr.c:913
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition: scip_expr.c:1409
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_RETCODE SCIPappendExprSumExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *child, SCIP_Real childcoef)
Definition: expr_sum.c:1151
#define SCIP_EXPRITER_ENTEREXPR
Definition: type_expr.h:692
#define SCIP_EXPRITER_VISITEDCHILD
Definition: type_expr.h:694
#define SCIPdebugMsgPrint
Definition: scip_message.h:79
#define SCIPdebugMsg
Definition: scip_message.h:78
static SCIP_RETCODE createExprlistFromExprs(SCIP *scip, SCIP_EXPR **exprs, int nexprs, EXPRNODE **list)
Definition: expr_product.c:198
SCIP_RETCODE SCIPcreateExprSum(SCIP *scip, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real *coefficients, SCIP_Real constant, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_sum.c:1114
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1464
#define EXPRHDLR_PRECEDENCE
Definition: expr_product.c:53
bilinear nonlinear handler
public functions to work with algebraic expressions
int SCIPcompareExpr(SCIP *scip, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
Definition: scip_expr.c:1734
static SCIP_RETCODE mergeProductExprlist(SCIP *scip, EXPRNODE *tomerge, EXPRNODE **finalchildren, EXPRNODE **unsimplifiedchildren, SCIP_Bool *changed, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_product.c:392
SCIP_EXPRDATA * SCIPexprGetData(SCIP_EXPR *expr)
Definition: expr.c:3887
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3864
SCIP_Real inf
Definition: intervalarith.h:55
SCIP_Real * SCIPgetCoefsExprSum(SCIP_EXPR *expr)
Definition: expr_sum.c:1552
static EXPRNODE * listPopFirst(EXPRNODE **list)
Definition: expr_product.c:143
static SCIP_RETCODE enforceSP10(SCIP *scip, SCIP_Real simplifiedcoef, EXPRNODE *finalchildren, SCIP_EXPR **simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_product.c:789
SCIP_Real SCIPexprGetEvalValue(SCIP_EXPR *expr)
Definition: expr.c:3928
SCIP_RETCODE SCIPcreateExpr(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPRHDLR *exprhdlr, SCIP_EXPRDATA *exprdata, int nchildren, SCIP_EXPR **children, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:974
static SCIP_RETCODE enforceSP12b(SCIP *scip, SCIP_Real simplifiedcoef, EXPRNODE *finalchildren, SCIP_EXPR **simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
SCIP_RETCODE SCIPcomputeFacetVertexPolyhedralNonlinear(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_Bool overestimate, SCIP_DECL_VERTEXPOLYFUN((*function)), void *fundata, SCIP_Real *xstar, SCIP_Real *box, int nallvars, SCIP_Real targetvalue, SCIP_Bool *success, SCIP_Real *facetcoefs, SCIP_Real *facetconstant)
static SCIP_DECL_EXPRMONOTONICITY(monotonicityProduct)
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
static SCIP_RETCODE enforceSP12(SCIP *scip, SCIP_Real simplifiedcoef, EXPRNODE *finalchildren, SCIP_Bool expandalways, SCIP_EXPR **simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_product.c:894
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1442
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
SCIP_RETCODE SCIPcreateExprProduct(SCIP *scip, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real coefficient, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
structs for symmetry computations
power and signed power expression handlers
void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
static SCIP_DECL_EXPRCURVATURE(curvatureProduct)
SCIP_Real SCIPexprGetDot(SCIP_EXPR *expr)
Definition: expr.c:3968
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1453
#define SCIP_CALL(x)
Definition: def.h:380
SCIP_Real sup
Definition: intervalarith.h:56
SCIP_RETCODE SCIPcreateExprValue(SCIP *scip, SCIP_EXPR **expr, SCIP_Real value, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_value.c:270
static SCIP_DECL_EXPRFREEDATA(freedataProduct)
static SCIP_DECL_EXPREVAL(evalProduct)
void SCIPexprhdlrSetCopyFreeHdlr(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYHDLR((*copyhdlr)), SCIP_DECL_EXPRFREEHDLR((*freehdlr)))
Definition: expr.c:370
SCIP_RETCODE SCIPcreateExprEntropy(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_entropy.c:685
static SCIP_DECL_EXPRINITESTIMATES(initestimatesProduct)
#define SCIP_INTERVAL_INFINITY
Definition: def.h:195
SCIP_Real SCIPgetCoefExprProduct(SCIP_EXPR *expr)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
public data structures and miscellaneous methods
static SCIP_DECL_EXPRREVERSEPROP(reversepropProduct)
#define SCIP_Bool
Definition: def.h:91
#define SCIP_DECL_EXPR_OWNERCREATE(x)
Definition: type_expr.h:143
SCIP_RETCODE SCIPcreateExprAbs(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_abs.c:528
void SCIPexprhdlrSetMonotonicity(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRMONOTONICITY((*monotonicity)))
Definition: expr.c:429
static SCIP_DECL_EXPRINTEGRALITY(integralityProduct)
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1417
constraint handler for nonlinear constraints specified by algebraic expressions
#define MIN(x, y)
Definition: def.h:243
void SCIPexprhdlrSetReverseProp(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRREVERSEPROP((*reverseprop)))
Definition: expr.c:510
SCIP_Bool SCIPexprIsIntegral(SCIP_EXPR *expr)
Definition: expr.c:4073
static SCIP_RETCODE freeExprNode(SCIP *scip, EXPRNODE **node)
Definition: expr_product.c:225
static int listLength(EXPRNODE *list)
Definition: expr_product.c:163
struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA
Definition: type_expr.h:195
void SCIPaddBilinMcCormick(SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real *lincoefx, SCIP_Real *lincoefy, SCIP_Real *linconstant, SCIP_Bool *success)
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition: expr.c:3877
SCIP_Bool SCIPisExprPower(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1475
void SCIPexprhdlrSetPrint(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRPRINT((*print)))
Definition: expr.c:396
SCIP_EXPR * expr
Definition: expr_product.c:89
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE createExprProductFromExprlist(SCIP *scip, EXPRNODE *exprlist, SCIP_Real coef, SCIP_EXPR **expr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_product.c:269
void SCIPexprhdlrSetCopyFreeData(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYDATA((*copydata)), SCIP_DECL_EXPRFREEDATA((*freedata)))
Definition: expr.c:383
absolute expression handler
constant value expression handler
product expression handler
void SCIPexprhdlrSetCompare(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOMPARE((*compare)))
Definition: expr.c:462
#define MAX(x, y)
Definition: def.h:239
static SCIP_DECL_EXPRBWFWDIFF(bwfwdiffProduct)
void SCIPintervalMul(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPexprhdlrSetCurvature(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCURVATURE((*curvature)))
Definition: expr.c:418
void SCIPexprSetData(SCIP_EXPR *expr, SCIP_EXPRDATA *exprdata)
Definition: expr.c:3902
static SCIP_DECL_EXPRCOMPARE(compareProduct)
SCIP_RETCODE SCIPincludeExprhdlrProduct(SCIP *scip)
SCIP_Bool SCIPisExprSignpower(SCIP *scip, SCIP_EXPR *expr)
Definition: expr_pow.c:3243
#define SCIP_MAXVERTEXPOLYDIM
SCIP_Bool SCIPisExprExp(SCIP *scip, SCIP_EXPR *expr)
Definition: expr_exp.c:528
#define SCIP_Real
Definition: def.h:173
#define SCIP_INVALID
Definition: def.h:193
SCIP_Real SCIPgetValueExprValue(SCIP_EXPR *expr)
Definition: expr_value.c:294
static SCIP_DECL_EXPRCOPYDATA(copydataProduct)
static void insertFirstList(EXPRNODE *newnode, EXPRNODE **list)
Definition: expr_product.c:129
unsigned int SCIPcalcFibHash(SCIP_Real v)
Definition: misc.c:10347
#define SCIP_EXPRITER_LEAVEEXPR
Definition: type_expr.h:695
void SCIPexprhdlrSetEstimate(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINITESTIMATES((*initestimates)), SCIP_DECL_EXPRESTIMATE((*estimate)))
Definition: expr.c:532
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
sum expression handler
static SCIP_RETCODE simplifyFactor(SCIP *scip, SCIP_EXPR *factor, SCIP_Real *simplifiedcoef, EXPRNODE **simplifiedfactor, SCIP_Bool *changed)
Definition: expr_product.c:312
SCIP_EXPRCURV SCIPexprcurvMultiply(SCIP_Real factor, SCIP_EXPRCURV curvature)
Definition: exprcurv.c:88
static SCIP_RETCODE simplifyMultiplyChildren(SCIP *scip, SCIP_EXPR **exprs, int nexprs, SCIP_Real *simplifiedcoef, EXPRNODE **finalchildren, SCIP_Bool *changed, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_product.c:723
SCIP_RETCODE SCIPdismantleExpr(SCIP *scip, FILE *file, SCIP_EXPR *expr)
Definition: scip_expr.c:1608
#define SCIP_EXPRITER_VISITINGCHILD
Definition: type_expr.h:693
#define EXPRHDLR_NAME
Definition: expr_product.c:51
#define SCIPallocClearBlockMemory(scip, ptr)
Definition: scip_mem.h:91
static SCIP_DECL_EXPRFWDIFF(fwdiffProduct)
static SCIP_RETCODE enforceSP11(SCIP *scip, SCIP_Real simplifiedcoef, EXPRNODE *finalchildren, SCIP_EXPR **simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_product.c:833
SCIP_RETCODE SCIPincludeExprhdlr(SCIP *scip, SCIP_EXPRHDLR **exprhdlr, const char *name, const char *desc, unsigned int precedence, SCIP_DECL_EXPREVAL((*eval)), SCIP_EXPRHDLRDATA *data)
Definition: scip_expr.c:823
#define SCIPABORT()
Definition: def.h:352
int SCIPexprGetNUses(SCIP_EXPR *expr)
Definition: expr.c:3844
void SCIPexprhdlrSetSimplify(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRSIMPLIFY((*simplify)))
Definition: expr.c:499
static SCIP_DECL_EXPRGETSYMDATA(getSymDataProduct)
void SCIPexprhdlrSetIntEval(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEVAL((*inteval)))
Definition: expr.c:488
#define SCIPduplicateBlockMemory(scip, ptr, source)
Definition: scip_mem.h:103
exponential expression handler
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
static SCIP_RETCODE buildSimplifiedProduct(SCIP *scip, SCIP_Real simplifiedcoef, EXPRNODE **simplifiedfactors, SCIP_Bool expandalways, SCIP_Bool changed, SCIP_EXPR **simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)