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