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