Scippy

SCIP

Solving Constraint Integer Programs

sepa_convexproj.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file sepa_convexproj.c
17  * @brief convexproj separator
18  * @author Felipe Serrano
19  *
20  * @todo should separator only be run when SCIPallColsInLP is true?
21  * @todo check if it makes sense to implement the copy callback
22  * @todo add SCIPisStopped(scip) to the condition of time consuming loops
23  */
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 #include <assert.h>
27 #include <string.h>
28 
29 #include "scip/sepa_convexproj.h"
30 #include "scip/nlp.h"
31 #include "nlpi/exprinterpret.h"
32 #include "nlpi/nlpi.h"
33 
34 
35 #define SEPA_NAME "convexproj"
36 #define SEPA_DESC "separate at projection of point onto convex region"
37 #define SEPA_PRIORITY 0
38 #define SEPA_FREQ -1
39 #define SEPA_MAXBOUNDDIST 1.0
40 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
41 #define SEPA_DELAY TRUE /**< should separation method be delayed, if other separators found cuts? */
42 
43 #define DEFAULT_MAXDEPTH -1 /* maximum depth at which the separator is applied; -1 means no limit */
44 #define DEFAULT_NLPTIMELIMIT 0.0 /**< default time limit of NLP solver; 0.0 for no limit */
45 #define DEFAULT_NLPITERLIM 250 /**< default NLP iteration limit */
46 
47 #define VIOLATIONFAC 100 /* points regarded violated if max violation > VIOLATIONFAC*SCIPfeastol */
48 
49 #define NLPVERBOSITY 0 /**< NLP solver verbosity */
50 
51 /*
52  * Data structures
53  */
54 
55 /** side that makes an nlrow convex */
57 {
58  LHS = 0, /**< left hand side */
59  RHS = 1 /**< right hand side */
60 };
61 typedef enum ConvexSide CONVEXSIDE;
62 
63 /** separator data
64  * it keeps the nlpi which represents the projection problem (see sepa_convexproj.h); it also keeps the convex nlrows
65  * and the side which actually makes them convex; when separating, we use the nlpi to compute the projection and then
66  * the convex nlrows to compute the actual gradient cuts */
67 struct SCIP_SepaData
68 {
69  SCIP_NLPI* nlpi; /**< nlpi used to create the nlpi problem */
70  SCIP_NLPIPROBLEM* nlpiprob; /**< nlpi problem representing the convex NLP relaxation */
71  SCIP_VAR** nlpivars; /**< array containing all variables of the nlpi */
72  SCIP_HASHMAP* var2nlpiidx; /**< mapping between variables and nlpi indices */
73  int nlpinvars; /**< total number of nlpi variables */
74 
75  SCIP_Bool skipsepa; /**< should separator be skipped? */
76 
77  SCIP_NLROW** nlrows; /**< convex nlrows */
78  CONVEXSIDE* convexsides; /**< which sides make the nlrows convex */
79  SCIP_Real* constraintviolation;/**< array storing the violation of constraint by current solution; 0.0 if it is not violated */
80  int nnlrows; /**< total number of nlrows */
81  int nlrowssize; /**< memory allocated for nlrows, convexsides and nlrowsidx */
82 
83  SCIP_EXPRINT* exprinterpreter; /**< expression interpreter to compute gradients */
84 
85  /* parameter */
86  SCIP_Real nlptimelimit; /**< time limit of NLP solver; 0.0 for no limit */
87  int nlpiterlimit; /**< iteration limit of NLP solver; 0 for no limit */
88  int maxdepth; /**< maximal depth at which the separator is applied */
89 
90  int ncuts; /**< number of cuts generated */
91 };
92 
93 
94 /*
95  * Local methods
96  */
97 
98 /** clears the sepadata data */
99 static
101  SCIP* scip, /**< SCIP data structure */
102  SCIP_SEPADATA* sepadata /**< separator data */
103  )
104 {
105  assert(sepadata != NULL);
106 
107  /* nlrowssize gets allocated first and then its decided whether to create the nlpiprob */
108  if( sepadata->nlrowssize > 0 )
109  {
110  SCIPfreeBlockMemoryArray(scip, &sepadata->constraintviolation, sepadata->nlrowssize);
111  SCIPfreeBlockMemoryArray(scip, &sepadata->convexsides, sepadata->nlrowssize);
112  SCIPfreeBlockMemoryArray(scip, &sepadata->nlrows, sepadata->nlrowssize);
113  sepadata->nlrowssize = 0;
114  }
115 
116  if( sepadata->nlpiprob != NULL )
117  {
118  assert(sepadata->nlpi != NULL);
119 
120  SCIPfreeBlockMemoryArray(scip, &sepadata->nlpivars, sepadata->nlpinvars);
121 
122  SCIPhashmapFree(&sepadata->var2nlpiidx);
123  SCIP_CALL( SCIPnlpiFreeProblem(sepadata->nlpi, &sepadata->nlpiprob) );
124  SCIP_CALL( SCIPexprintFree(&sepadata->exprinterpreter) );
125 
126  sepadata->nlpinvars = 0;
127  sepadata->nnlrows = 0;
128  }
129  assert(sepadata->nlpinvars == 0);
130  assert(sepadata->nnlrows == 0);
131  assert(sepadata->nlrowssize == 0);
132 
133  sepadata->skipsepa = FALSE;
134 
135  return SCIP_OKAY;
136 }
137 
138 /** computes gradient of exprtree at projection */
139 static
141  SCIP* scip, /**< SCIP data structure */
142  SCIP_EXPRINT* exprint, /**< expressions interpreter */
143  SCIP_SOL* projection, /**< point where we compute gradient */
144  SCIP_EXPRTREE* exprtree, /**< exprtree for which we compute the gradient */
145  SCIP_Real* grad /**< buffer to store the gradient */
146  )
147 {
148  SCIP_Real* x;
149  SCIP_Real val;
150  int nvars;
151  int i;
152 
153  assert(scip != NULL);
154  assert(exprint != NULL);
155  assert(projection != NULL);
156  assert(exprtree != NULL);
157  assert(grad != NULL);
158 
159  nvars = SCIPexprtreeGetNVars(exprtree);
160  assert(nvars > 0);
161 
162  SCIP_CALL( SCIPallocBufferArray(scip, &x, nvars) );
163 
164  /* compile expression exprtree, if not done before */
165  if( SCIPexprtreeGetInterpreterData(exprtree) == NULL )
166  {
167  SCIP_CALL( SCIPexprintCompile(exprint, exprtree) );
168  }
169 
170  for( i = 0; i < nvars; ++i )
171  {
172  x[i] = SCIPgetSolVal(scip, projection, SCIPexprtreeGetVars(exprtree)[i]);
173  }
174 
175  SCIP_CALL( SCIPexprintGrad(exprint, exprtree, x, TRUE, &val, grad) );
176 
177  /*SCIPdebug( for( i = 0; i < nvars; ++i ) printf("%e [%s]\n", grad[i], SCIPvarGetName(SCIPexprtreeGetVars(exprtree)[i])) );*/
178 
179  SCIPfreeBufferArray(scip, &x);
180 
181  return SCIP_OKAY;
182 }
183 
184 /** computes gradient cut (linearization) of nlrow at projection */
185 static
187  SCIP* scip, /**< SCIP data structure */
188  SCIP_SEPA* sepa, /**< the cut separator itself */
189  SCIP_EXPRINT* exprint, /**< expression interpreter */
190  SCIP_SOL* projection, /**< point where we compute gradient cut */
191  SCIP_NLROW* nlrow, /**< constraint for which we generate gradient cut */
192  CONVEXSIDE convexside, /**< which side makes the nlrow convex */
193  SCIP_Real activity, /**< activity of constraint at projection */
194  SCIP_ROW** row /**< storage for cut */
195  )
196 {
197  char rowname[SCIP_MAXSTRLEN];
198  SCIP_SEPADATA* sepadata;
199  SCIP_Real gradx0; /* <grad f(x_0), x_0> */
200  int i;
201 
202  assert(scip != NULL);
203  assert(sepa != NULL);
204  assert(exprint != NULL);
205  assert(nlrow != NULL);
206  assert(row != NULL);
207 
208  sepadata = SCIPsepaGetData(sepa);
209 
210  assert(sepadata != NULL);
211 
212  gradx0 = 0.0;
213 
214  /* an nlrow has a linear part, quadratic part and expression tree; ideally one would just build the gradient but we
215  * do not know if the different parts share variables or not, so we can't just build the gradient; for this reason
216  * we create the row right away and compute the gradients of each part independently and add them to the row; the
217  * row takes care to add coeffs corresponding to the same variable when they appear in different parts of the nlrow
218  * NOTE: a gradient cut is globally valid whenever the constraint from which it is deduced is globally valid; since
219  * we build the convex relaxation using only globally valid constraints, the cuts are globally valid
220  */
221  (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "proj_cut_%s_%u", SCIPnlrowGetName(nlrow), ++(sepadata->ncuts));
222  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, row, sepa, rowname, -SCIPinfinity(scip), SCIPinfinity(scip), TRUE, FALSE ,
223  TRUE) );
224 
225  SCIP_CALL( SCIPcacheRowExtensions(scip, *row) );
226 
227  /* linear part */
228  for( i = 0; i < SCIPnlrowGetNLinearVars(nlrow); i++ )
229  {
230  gradx0 += SCIPgetSolVal(scip, projection, SCIPnlrowGetLinearVars(nlrow)[i]) * SCIPnlrowGetLinearCoefs(nlrow)[i];
231  SCIP_CALL( SCIPaddVarToRow(scip, *row, SCIPnlrowGetLinearVars(nlrow)[i], SCIPnlrowGetLinearCoefs(nlrow)[i]) );
232  }
233 
234  /* quadratic part */
235  for( i = 0; i < SCIPnlrowGetNQuadElems(nlrow); i++ )
236  {
237  SCIP_VAR* var1;
238  SCIP_VAR* var2;
239  SCIP_Real grad1;
240  SCIP_Real grad2;
241 
242  var1 = SCIPnlrowGetQuadVars(nlrow)[SCIPnlrowGetQuadElems(nlrow)[i].idx1];
243  var2 = SCIPnlrowGetQuadVars(nlrow)[SCIPnlrowGetQuadElems(nlrow)[i].idx2];
244  grad1 = SCIPnlrowGetQuadElems(nlrow)[i].coef * SCIPgetSolVal(scip, projection, var2);
245  grad2 = SCIPnlrowGetQuadElems(nlrow)[i].coef * SCIPgetSolVal(scip, projection, var1);
246 
247  SCIP_CALL( SCIPaddVarToRow(scip, *row, var1, grad1) );
248  SCIP_CALL( SCIPaddVarToRow(scip, *row, var2, grad2) );
249 
250  gradx0 += grad1 * SCIPgetSolVal(scip, projection, var1) + grad2 * SCIPgetSolVal(scip, projection, var2);
251  }
252 
253  /* expression tree part */
254  {
255  SCIP_Real* grad;
256  SCIP_EXPRTREE* tree;
257 
258  tree = SCIPnlrowGetExprtree(nlrow);
259 
260  if( tree != NULL && SCIPexprtreeGetNVars(tree) > 0 )
261  {
262  SCIP_CALL( SCIPallocBufferArray(scip, &grad, SCIPexprtreeGetNVars(tree)) );
263 
264  SCIP_CALL( computeGradient(scip, sepadata->exprinterpreter, projection, tree, grad) );
265 
266  for( i = 0; i < SCIPexprtreeGetNVars(tree); i++ )
267  {
268  gradx0 += grad[i] * SCIPgetSolVal(scip, projection, SCIPexprtreeGetVars(tree)[i]);
269  SCIP_CALL( SCIPaddVarToRow(scip, *row, SCIPexprtreeGetVars(tree)[i], grad[i]) );
270  }
271 
272  SCIPfreeBufferArray(scip, &grad);
273  }
274  }
275 
276  SCIP_CALL( SCIPflushRowExtensions(scip, *row) );
277 
278  SCIPdebugPrintf("gradient: ");
279  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, *row, NULL) ) );
280  SCIPdebugPrintf("gradient dot x_0: %g\n", gradx0);
281 
282  /* gradient cut is f(x_0) - <grad f(x_0), x_0> + <grad f(x_0), x> <= rhs or >= lhs */
283  if( convexside == RHS )
284  {
285  assert(!SCIPisInfinity(scip, SCIPnlrowGetRhs(nlrow)));
286  SCIP_CALL( SCIPchgRowRhs(scip, *row, SCIPnlrowGetRhs(nlrow) - activity + gradx0) );
287  }
288  else
289  {
290  assert(convexside == LHS);
291  assert(!SCIPisInfinity(scip, -SCIPnlrowGetLhs(nlrow)));
292  SCIP_CALL( SCIPchgRowLhs(scip, *row, SCIPnlrowGetLhs(nlrow) - activity + gradx0) );
293  }
294 
295  SCIPdebugPrintf("gradient cut: ");
296  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, *row, NULL) ) );
297 
298  return SCIP_OKAY;
299 }
300 
301 /** set quadratic part of objective function: \f$ \sum_i x_i^2 \f$; the objective function is \f$ ||x - x_0||^2 \f$,
302  * where \f$ x_0 \f$ is the point to separate; the only part that changes is the term \f$ -2 \langle x_0, x \rangle \f$
303  * which is linear and is set every time we want to separate a point, see separateCuts
304  */
305 static
307  SCIP* scip, /**< SCIP data structure */
308  SCIP_SEPADATA* sepadata /**< the cut separator data */
309  )
310 {
311  SCIP_QUADELEM* quadelems;
312  int i;
313 
314  assert(scip != NULL);
315  assert(sepadata != NULL);
316  assert(sepadata->nlpi != NULL);
317  assert(sepadata->nlpiprob != NULL);
318  assert(sepadata->var2nlpiidx != NULL);
319  assert(sepadata->nlpinvars > 0);
320 
321  SCIP_CALL( SCIPallocBufferArray(scip, &quadelems, sepadata->nlpinvars) );
322  for( i = 0; i < sepadata->nlpinvars; i++ )
323  {
324  SCIP_VAR* var;
325 
326  var = sepadata->nlpivars[i];
327  assert(SCIPhashmapExists(sepadata->var2nlpiidx, (void*)var) );
328 
329  quadelems[i].idx1 = (int)(size_t)SCIPhashmapGetImage(sepadata->var2nlpiidx, (void*)var);
330  quadelems[i].idx2 = quadelems[i].idx1;
331  quadelems[i].coef = 1.0;
332  }
333 
334  /* set quadratic part of objective function */
335  SCIP_CALL( SCIPnlpiSetObjective(sepadata->nlpi, sepadata->nlpiprob,
336  0, NULL, NULL, sepadata->nlpinvars, quadelems, NULL, NULL, 0.0) );
337 
338  /* free memory */
339  SCIPfreeBufferArray(scip, &quadelems);
340 
341  return SCIP_OKAY;
342 }
343 
344 /** projects sol onto convex relaxation (stored in sepadata) and tries to generate gradient cuts at the projection
345  * it generates cuts only for the constraints that were violated by the LP solution and are now active or still
346  * violated (in case we don't solve to optimality).
347  * @todo: store a feasible solution if one is found to use as warmstart
348  */
349 static
351  SCIP* scip, /**< SCIP data structure */
352  SCIP_SEPA* sepa, /**< the cut separator itself */
353  SCIP_SOL* sol, /**< solution that should be separated */
354  SCIP_RESULT* result /**< pointer to store the result of the separation call */
355  )
356 {
357  SCIP_SEPADATA* sepadata;
358  SCIP_SOL* projection;
359  SCIP_Real* linvals;
360  SCIP_Real* nlpisol;
361  SCIP_Real timelimit;
362  int nlpinvars;
363  int i;
364  int iterlimit;
365  int* lininds;
366  SCIP_Bool nlpunstable;
367 
368  nlpunstable = FALSE;
369 
370  assert(sepa != NULL);
371 
372  sepadata = SCIPsepaGetData(sepa);
373 
374  assert(result != NULL);
375  assert(sepadata != NULL);
376  assert(sepadata->nnlrows > 0);
377  assert(sepadata->nlpi != NULL);
378  assert(sepadata->nlpinvars > 0);
379  assert(sepadata->nlrows != NULL);
380  assert(sepadata->nlpiprob != NULL);
381  assert(sepadata->var2nlpiidx != NULL);
382  assert(sepadata->convexsides != NULL);
383  assert(sepadata->constraintviolation != NULL);
384 
385  nlpinvars = sepadata->nlpinvars;
386  /* set linear part of objective function: \norm(x - x^0)^2 = \norm(x)^2 - \sum 2 * x_i * x^0_i + const
387  * we ignore the constant; x0 is `sol`
388  */
389  SCIP_CALL( SCIPallocBufferArray(scip, &linvals, nlpinvars) );
390  SCIP_CALL( SCIPallocBufferArray(scip, &lininds, nlpinvars) );
391  for( i = 0; i < nlpinvars; i++ )
392  {
393  SCIP_VAR* var;
394 
395  var = sepadata->nlpivars[i];
396  assert(SCIPhashmapExists(sepadata->var2nlpiidx, (void*)var) );
397 
398  lininds[i] = (int)(size_t)SCIPhashmapGetImage(sepadata->var2nlpiidx, (void*)var);
399  linvals[i] = - 2.0 * SCIPgetSolVal(scip, sol, var);
400 
401  /* if coefficient is too large, don't separate */
402  if( SCIPisHugeValue(scip, REALABS(linvals[i])) )
403  {
404  SCIPdebugMsg(scip, "Don't separate points too close to infinity\n");
405  goto CLEANUP;
406  }
407  }
408 
409  /* set linear part of objective function */
410  SCIP_CALL( SCIPnlpiChgLinearCoefs(sepadata->nlpi, sepadata->nlpiprob, -1, nlpinvars, lininds, linvals) );
411 
412  /* set parameters in nlpi; time and iterations limit, tolerance, verbosity; for time limit, get time limit of scip;
413  * if scip doesn't have much time left, don't run separator. otherwise, timelimit is the minimum between whats left
414  * for scip and the timelimit setting
415  */
416  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
417  if( !SCIPisInfinity(scip, timelimit) )
418  {
419  timelimit -= SCIPgetSolvingTime(scip);
420  if( timelimit <= 1.0 )
421  {
422  SCIPdebugMsg(scip, "skip NLP solve; no time left\n");
423  goto CLEANUP;
424  }
425  }
426  if( sepadata->nlptimelimit > 0.0 )
427  timelimit = MIN(sepadata->nlptimelimit, timelimit);
428  SCIP_CALL( SCIPnlpiSetRealPar(sepadata->nlpi, sepadata->nlpiprob, SCIP_NLPPAR_TILIM, timelimit) );
429 
430  iterlimit = sepadata->nlpiterlimit > 0 ? sepadata->nlpiterlimit : INT_MAX;
431  SCIP_CALL( SCIPnlpiSetIntPar(sepadata->nlpi, sepadata->nlpiprob, SCIP_NLPPAR_ITLIM, iterlimit) );
432  SCIP_CALL( SCIPnlpiSetRealPar(sepadata->nlpi, sepadata->nlpiprob, SCIP_NLPPAR_FEASTOL, SCIPfeastol(scip) / 10.0) ); /* use tighter tolerances for the NLP solver */
433  SCIP_CALL( SCIPnlpiSetRealPar(sepadata->nlpi, sepadata->nlpiprob, SCIP_NLPPAR_RELOBJTOL, MAX(SCIPfeastol(scip), SCIPdualfeastol(scip))) ); /*lint !e666*/
434  SCIP_CALL( SCIPnlpiSetIntPar(sepadata->nlpi, sepadata->nlpiprob, SCIP_NLPPAR_VERBLEVEL, NLPVERBOSITY) );
435 
436  /* compute the projection onto the convex NLP relaxation */
437  SCIP_CALL( SCIPnlpiSolve(sepadata->nlpi, sepadata->nlpiprob) );
438  SCIPdebugMsg(scip, "NLP solstat = %d\n", SCIPnlpiGetSolstat(sepadata->nlpi, sepadata->nlpiprob));
439 
440  /* if solution is feasible, add cuts */
441  switch( SCIPnlpiGetSolstat(sepadata->nlpi, sepadata->nlpiprob) )
442  {
445  /* @todo: if solution is optimal, we might as well add the cut <x - P(x_0), x_0 - P(x_0)> <= 0
446  * even though this cut is implied by all the gradient cuts of the rows active at the projection,
447  * we do not add them all (only the gradient cuts of constraints that violated the LP solution */
449  /* generate cuts for violated constraints (at sol) that are active or still violated at the projection, since
450  * a suboptimal solution or numerical issues could give a solution of the projection problem where constraints
451  * are not active; if the solution of the projection problem is in the interior of the region, we do nothing
452  */
453 
454  /* get solution: build SCIP_SOL out of nlpi sol */
455  SCIP_CALL( SCIPnlpiGetSolution(sepadata->nlpi, sepadata->nlpiprob, &nlpisol, NULL, NULL, NULL, NULL) );
456  assert(nlpisol != NULL);
457 
458  SCIP_CALL( SCIPcreateSol(scip, &projection, NULL) );
459  for( i = 0; i < nlpinvars; i++ )
460  {
461  SCIP_VAR* var;
462 
463  var = sepadata->nlpivars[i];
464  assert(SCIPhashmapExists(sepadata->var2nlpiidx, (void*)var) );
465 
466  SCIP_CALL( SCIPsetSolVal(scip, projection, var,
467  nlpisol[(int)(size_t)SCIPhashmapGetImage(sepadata->var2nlpiidx, (void *)var)]) );
468  }
469  SCIPdebug( SCIPprintSol(scip, projection, NULL, TRUE) );
470 
471  /* check for active or violated constraints */
472  for( i = 0; i < sepadata->nnlrows; ++i )
473  {
474  SCIP_NLROW* nlrow;
475  CONVEXSIDE convexside;
476  SCIP_Real activity;
477 
478  /* ignore constraints that are not violated by `sol` */
479  if( SCIPisFeasZero(scip, sepadata->constraintviolation[i]) )
480  continue;
481 
482  convexside = sepadata->convexsides[i];
483  nlrow = sepadata->nlrows[i];
484  assert(nlrow != NULL);
485 
486  /* check for currently active constraints at projected point */
487  SCIP_CALL( SCIPgetNlRowSolActivity(scip, nlrow, projection, &activity) );
488 
489  SCIPdebugMsg(scip, "NlRow activity at nlpi solution: %g <= %g <= %g\n", SCIPnlrowGetLhs(nlrow), activity,
490  SCIPnlrowGetRhs(nlrow) );
491 
492  /* if nlrow is active or violates the projection, build gradient cut at projection */
493  if( (convexside == RHS && SCIPisFeasGE(scip, activity, SCIPnlrowGetRhs(nlrow)))
494  || (convexside == LHS && SCIPisFeasLE(scip, activity, SCIPnlrowGetLhs(nlrow))) )
495  {
496  SCIP_ROW* row;
497 
498  SCIP_CALL( generateCut(scip, sepa, sepadata->exprinterpreter, projection, nlrow, convexside, activity,
499  &row) );
500 
501  SCIPdebugMsg(scip, "active or violated nlrow: (sols vio: %e)\n", sepadata->constraintviolation[i]);
502  SCIPdebug( SCIP_CALL( SCIPprintNlRow(scip, nlrow, NULL) ) );
503  SCIPdebugMsg(scip, "cut with efficacy %g generated\n", SCIPgetCutEfficacy(scip, sol, row));
504  SCIPdebug( SCIPprintRow(scip, row, NULL) );
505 
506  /* add cut if it is efficacious for the point we want to separate (sol) */
507  if( SCIPisCutEfficacious(scip, sol, row) )
508  {
509  SCIP_Bool infeasible;
510 
511  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
512 
513  if( infeasible )
514  {
515  *result = SCIP_CUTOFF;
516  SCIP_CALL( SCIPreleaseRow(scip, &row) );
517  break;
518  }
519  else
520  {
521  *result = SCIP_SEPARATED;
522  }
523  }
524 
525  /* release the row */
526  SCIP_CALL( SCIPreleaseRow(scip, &row) );
527  }
528  }
529 
530 #ifdef SCIP_DEBUG
531  {
532  SCIP_Real distance;
533 
534  /* compute distance between LP sol and its projection (only makes sense when it is optimal) */
535  distance = 0.0;
536  for( i = 0; i < SCIPgetNNLPVars(scip); ++i )
537  {
538  SCIP_VAR* var;
539 
540  var = SCIPgetNLPVars(scip)[i];
541  assert(var != NULL);
542 
543  /* assert NLP solution is within the bounds of the variable (only make sense when sol is optimal) */
544  if( !SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)) )
545  assert(SCIPisFeasLE(scip, SCIPvarGetLbLocal(var), SCIPvarGetNLPSol(var)));
546  if( !SCIPisInfinity(scip, SCIPvarGetUbLocal(var)) )
547  assert(SCIPisFeasLE(scip, SCIPvarGetNLPSol(var), SCIPvarGetUbLocal(var)));
548 
549  /*SCIPdebugMsg(scip, "NLP sol (LP sol): %s = %f (%g)\n", SCIPvarGetName(var),
550  * SCIPvarGetNLPSol(var), SCIPgetSolVal(scip, sol, var));
551  */
552 
553  distance += SQR( SCIPvarGetNLPSol(var) - SCIPgetSolVal(scip, sol, var) );
554  }
555 
556  SCIPdebugMsg(scip, "NLP objval: %e, distance: %e\n", SCIPgetNLPObjval(scip), distance);
557  }
558 #endif
559 
560  /* free solution */
561  SCIP_CALL( SCIPfreeSol(scip, &projection) );
562  break;
563 
566  /* fallthrough;
567  * @todo: write what it means to be locinfeasible and why it can't be used to cutoff the node */
569  /* unknown... assume numerical issues */
570  nlpunstable = TRUE;
571  break;
572 
574  default:
575  SCIPerrorMessage("Projection NLP is not unbounded by construction, should not get here!\n");
576  SCIPABORT();
577  nlpunstable = TRUE;
578  }
579 
580 
581  /* if nlp is detected to be unstable, don't try to separate again */
582  if( nlpunstable )
583  {
584  /* @todo: maybe change objective function to \sum [(x_i - x_i^*)/max(|x_i^*|, 1)]^2
585  * or some other scaling when unstable and try again.
586  * maybe free it here */
587  sepadata->skipsepa = TRUE;
588  }
589 
590  /* reset objective */
591  BMSclearMemoryArray(linvals, nlpinvars);
592  SCIP_CALL( SCIPnlpiChgLinearCoefs(sepadata->nlpi, sepadata->nlpiprob, -1, nlpinvars, lininds, linvals) );
593 
594 CLEANUP:
595  /* free memory */
596  SCIPfreeBufferArray(scip, &lininds);
597  SCIPfreeBufferArray(scip, &linvals);
598 
599  return SCIP_OKAY;
600 }
601 
602 /** computes the violation and maximum violation of the convex nlrows stored in sepadata wrt sol */
603 static
605  SCIP* scip, /**< SCIP data structure */
606  SCIP_SEPADATA* sepadata, /**< separator data */
607  SCIP_SOL* sol, /**< solution that should be separated */
608  SCIP_Real* maxviolation /**< buffer to store maximum violation */
609  )
610 {
611  SCIP_NLROW* nlrow;
612  int i;
613 
614  assert(sepadata != NULL);
615  assert(sepadata->nnlrows > 0);
616  assert(sepadata->nlrows != NULL);
617  assert(sepadata->convexsides != NULL);
618  assert(sepadata->constraintviolation != NULL);
619 
620  *maxviolation = 0.0;
621  for( i = 0; i < sepadata->nnlrows; i++ )
622  {
623  SCIP_Real activity;
624  SCIP_Real violation;
625 
626  nlrow = sepadata->nlrows[i];
627 
628  /* get activity of nlrow */
629  SCIP_CALL( SCIPgetNlRowSolActivity(scip, nlrow, sol, &activity) );
630 
631  /* violation = max{activity - rhs, 0.0} when convex and max{lhs - activity, 0.0} when concave */
632  if( sepadata->convexsides[i] == RHS )
633  {
635  assert(!SCIPisInfinity(scip, SCIPnlrowGetRhs(nlrow)));
636 
637  violation = activity - SCIPnlrowGetRhs(nlrow);
638  sepadata->constraintviolation[i] = MAX(violation, 0.0);
639  }
640  if( sepadata->convexsides[i] == LHS )
641  {
643  assert(!SCIPisInfinity(scip, -SCIPnlrowGetLhs(nlrow)));
644 
645  violation = SCIPnlrowGetLhs(nlrow) - activity;
646  sepadata->constraintviolation[i] = MAX(violation, 0.0);
647  }
648 
649  /* compute maximum */
650  if( *maxviolation < sepadata->constraintviolation[i] )
651  *maxviolation = sepadata->constraintviolation[i];
652  }
653 
654  SCIPdebugMsg(scip, "Maximum violation %g\n", *maxviolation);
655 
656  return SCIP_OKAY;
657 }
658 
659 
660 /** stores, from the constraints represented by nlrows, the nonlinear convex ones in sepadata */
661 static
663  SCIP* scip, /**< SCIP data structure */
664  SCIP_SEPADATA* sepadata, /**< separator data */
665  SCIP_NLROW** nlrows, /**< nlrows from which to store convex ones */
666  int nnlrows /**< number of nlrows */
667  )
668 {
669  int i;
670 
671  assert(scip != NULL);
672  assert(sepadata != NULL);
673 
674  SCIPdebugMsg(scip, "storing convex nlrows\n");
675 
676  sepadata->nlrowssize = nnlrows;
677  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(sepadata->nlrows), nnlrows) );
678  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(sepadata->convexsides), nnlrows) );
679  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(sepadata->constraintviolation), nnlrows) );
680 
681  /* count the number of nonlinear convex rows and store them */
682  sepadata->nnlrows = 0;
683  for( i = 0; i < nnlrows; ++i )
684  {
685  SCIP_NLROW* nlrow;
686 
687  nlrow = nlrows[i];
688  assert(nlrow != NULL);
689 
690  /* linear case */
692  (SCIPnlrowGetNQuadElems(nlrow) == 0 && SCIPnlrowGetExprtree(nlrow) == NULL) )
693  continue;
694 
695  /* nonlinear case */
697  {
698  sepadata->convexsides[sepadata->nnlrows] = RHS;
699  sepadata->nlrows[sepadata->nnlrows] = nlrow;
700  ++(sepadata->nnlrows);
701  }
702  else if( !SCIPisInfinity(scip, -SCIPnlrowGetLhs(nlrow)) && SCIPnlrowGetCurvature(nlrow) == SCIP_EXPRCURV_CONCAVE )
703  {
704  sepadata->convexsides[sepadata->nnlrows] = LHS;
705  sepadata->nlrows[sepadata->nnlrows] = nlrow;
706  ++(sepadata->nnlrows);
707  }
708  }
709 
710  return SCIP_OKAY;
711 }
712 
713 
714 /*
715  * Callback methods of separator
716  */
717 
718 
719 /** destructor of separator to free user data (called when SCIP is exiting) */
720 static
721 SCIP_DECL_SEPAFREE(sepaFreeConvexproj)
722 { /*lint --e{715}*/
723  SCIP_SEPADATA* sepadata;
724 
725  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
726 
727  /* free separator data */
728  sepadata = SCIPsepaGetData(sepa);
729  assert(sepadata != NULL);
730 
731  SCIP_CALL( sepadataClear(scip, sepadata) );
732 
733  SCIPfreeBlockMemory(scip, &sepadata);
734 
735  SCIPsepaSetData(sepa, NULL);
736 
737  return SCIP_OKAY;
738 }
739 
740 /** solving process deinitialization method of separator (called before branch and bound process data is freed) */
741 static
742 SCIP_DECL_SEPAEXITSOL(sepaExitsolConvexproj)
743 { /*lint --e{715}*/
744  SCIP_SEPADATA* sepadata;
745 
746  assert(sepa != NULL);
747 
748  sepadata = SCIPsepaGetData(sepa);
749 
750  assert(sepadata != NULL);
751 
752  SCIP_CALL( sepadataClear(scip, sepadata) );
753 
754  return SCIP_OKAY;
755 }
756 
757 
758 /** LP solution separation method of separator */
759 static
760 SCIP_DECL_SEPAEXECLP(sepaExeclpConvexproj)
761 { /*lint --e{715}*/
762 
763  SCIP_Real maxviolation;
764  SCIP_SOL* lpsol;
765  SCIP_SEPADATA* sepadata;
766 
767  *result = SCIP_DIDNOTRUN;
768 
769  sepadata = SCIPsepaGetData(sepa);
770  assert(sepadata != NULL);
771 
772  /* do not run if there is no interesting convex relaxation (with at least one nonlinear convex constraint),
773  * or if we have found it to be numerically unstable
774  * @todo: should it be with at least 2 nonlinear convex constraints?
775  */
776  if( sepadata->skipsepa )
777  {
778  SCIPdebugMsg(scip, "not running because convex relaxation is uninteresting or numerically unstable\n");
779  return SCIP_OKAY;
780  }
781 
782  /* the separator needs an NLP solver */
783  if( SCIPgetNNlpis(scip) == 0 )
784  return SCIP_OKAY;
785 
786  /* only call separator up to a maximum depth */
787  if( sepadata->maxdepth >= 0 && SCIPgetDepth(scip) > sepadata->maxdepth )
788  return SCIP_OKAY;
789 
790  /* only call separator, if we are not close to terminating */
791  if( SCIPisStopped(scip) )
792  return SCIP_OKAY;
793 
794  /* do not run if SCIP does not have constructed an NLP */
795  if( !SCIPisNLPConstructed(scip) )
796  {
797  SCIPdebugMsg(scip, "NLP not constructed, skipping convex projection separator\n");
798  return SCIP_OKAY;
799  }
800 
801  /* recompute convex NLP relaxation if the variable set changed and we are still at the root node
802  * @todo: does it make sense to do this??? */
803  if( sepadata->nlpiprob != NULL && SCIPgetNVars(scip) != sepadata->nlpinvars && SCIPgetDepth(scip) == 0 )
804  {
805  SCIP_CALL( sepadataClear(scip, sepadata) );
806  assert(sepadata->nlpiprob == NULL);
807  }
808 
809  /* create or update convex NLP relaxation */
810  if( sepadata->nlpiprob == NULL )
811  {
812  /* store convex nonlinear constraints */
814 
815  /* check that convex NLP relaxation is interesting (more than one nonlinear constraint) */
816  if( sepadata->nnlrows < 1 )
817  {
818  SCIPdebugMsg(scip, "convex relaxation uninteresting, don't run\n");
819  sepadata->skipsepa = TRUE;
820  return SCIP_OKAY;
821  }
822 
823  /* create the expression interpreter */
824  SCIP_CALL( SCIPexprintCreate(SCIPblkmem(scip), &sepadata->exprinterpreter) );
825 
826  sepadata->nlpinvars = SCIPgetNVars(scip);
827  sepadata->nlpi = SCIPgetNlpis(scip)[0];
828  assert(sepadata->nlpi != NULL);
829 
830  SCIP_CALL( SCIPnlpiCreateProblem(sepadata->nlpi, &sepadata->nlpiprob, "convexproj-nlp") );
831  SCIP_CALL( SCIPhashmapCreate(&sepadata->var2nlpiidx, SCIPblkmem(scip), sepadata->nlpinvars) );
832  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &sepadata->nlpivars, SCIPgetVars(scip), sepadata->nlpinvars) ); /*lint !e666*/
833 
835  sepadata->nlpiprob, sepadata->var2nlpiidx, NULL, SCIPgetCutoffbound(scip), FALSE, TRUE) );
836 
837  /* add rows of the LP */
838  if( SCIPgetDepth(scip) == 0 )
839  {
840  SCIP_CALL( SCIPaddNlpiProbRows(scip, sepadata->nlpi, sepadata->nlpiprob, sepadata->var2nlpiidx,
842  }
843 
844  /* set quadratic part of objective function */
845  SCIP_CALL( setQuadraticObj(scip, sepadata) );
846  }
847  else
848  {
849  SCIP_CALL( SCIPupdateNlpiProb(scip, sepadata->nlpi, sepadata->nlpiprob, sepadata->var2nlpiidx,
850  sepadata->nlpivars, sepadata->nlpinvars, SCIPgetCutoffbound(scip)) );
851  }
852 
853  /* assert that the lp solution satisfies the cutoff bound; if this fails then we shouldn't have a cutoff bound in the
854  * nlpi, since then the projection could be in the interior of the actual convex relaxation */
857 
858  /* get current sol: LP or pseudo solution if LP sol is not available */
859  SCIP_CALL( SCIPcreateCurrentSol(scip, &lpsol, NULL) );
860 
861  /* do not run if current solution's violation is small */
862  SCIP_CALL( computeMaxViolation(scip, sepadata, lpsol, &maxviolation) );
863  if( maxviolation < VIOLATIONFAC * SCIPfeastol(scip) )
864  {
865  SCIPdebugMsg(scip, "solution doesn't violate constraints enough, do not separate\n");
866  SCIP_CALL( SCIPfreeSol(scip, &lpsol) );
867  return SCIP_OKAY;
868  }
869 
870  /* run the separator */
871  *result = SCIP_DIDNOTFIND;
872 
873  /* separateCuts computes the projection and then gradient cuts on each constraint that was originally violated */
874  SCIP_CALL( separateCuts(scip, sepa, lpsol, result) );
875 
876  /* free memory */
877  SCIP_CALL( SCIPfreeSol(scip, &lpsol) );
878 
879  return SCIP_OKAY;
880 }
881 
882 
883 /*
884  * separator specific interface methods
885  */
886 
887 /** creates the convexproj separator and includes it in SCIP */
889  SCIP* scip /**< SCIP data structure */
890  )
891 {
892  SCIP_SEPADATA* sepadata;
893  SCIP_SEPA* sepa;
894 
895  /* create convexproj separator data */
896  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
897 
898  /* this sets all data in sepadata to 0 */
899  BMSclearMemory(sepadata);
900 
901  /* include separator */
904  sepaExeclpConvexproj, NULL,
905  sepadata) );
906  assert(sepa != NULL);
907 
908  /* set non fundamental callbacks via setter functions */
909  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeConvexproj) );
910  SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolConvexproj) );
911 
912  /* add convexproj separator parameters */
913  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxdepth",
914  "maximal depth at which the separator is applied (-1: unlimited)",
915  &sepadata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
916 
917  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nlpiterlimit",
918  "iteration limit of NLP solver; 0 for no limit",
919  &sepadata->nlpiterlimit, TRUE, DEFAULT_NLPITERLIM, 0, INT_MAX, NULL, NULL) );
920 
921  SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/nlptimelimit",
922  "time limit of NLP solver; 0.0 for no limit",
923  &sepadata->nlptimelimit, TRUE, DEFAULT_NLPTIMELIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
924 
925  return SCIP_OKAY;
926 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22604
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip.c:29669
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47357
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip.c:31456
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:46300
convexproj separator
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:46437
static SCIP_RETCODE storeNonlinearConvexNlrows(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_NLROW **nlrows, int nnlrows)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip.c:31227
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30607
SCIP_VAR ** SCIPgetNLPVars(SCIP *scip)
Definition: scip.c:31294
methods to interpret (evaluate) an expression tree "fast"
static SCIP_DECL_SEPAEXECLP(sepaExeclpConvexproj)
static SCIP_RETCODE computeMaxViolation(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *maxviolation)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:43447
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30630
SCIP_RETCODE SCIPcreateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLROW **nlrows, int nnlrows, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
Definition: scip.c:34026
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip.c:4489
#define SCIP_MAXSTRLEN
Definition: def.h:259
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:30662
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
internal methods for NLPI solver interfaces
SCIP_RETCODE SCIPnlpiCreateProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem, const char *name)
Definition: nlpi.c:211
static SCIP_DECL_SEPAEXITSOL(sepaExitsolConvexproj)
SCIP_RETCODE SCIPnlpiGetSolution(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_Real **primalvalues, SCIP_Real **consdualvalues, SCIP_Real **varlbdualvalues, SCIP_Real **varubdualvalues, SCIP_Real *objval)
Definition: nlpi.c:537
SCIP_Real SCIPdualfeastol(SCIP *scip)
Definition: scip.c:46465
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47344
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
static SCIP_RETCODE setQuadraticObj(SCIP *scip, SCIP_SEPADATA *sepadata)
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:646
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPexprintCompile(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree)
SCIP_Real SCIPnlrowGetRhs(SCIP_NLROW *nlrow)
Definition: nlp.c:3383
int SCIPnlrowGetNLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3245
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
SCIP_RETCODE SCIPgetNlRowSolActivity(SCIP *scip, SCIP_NLROW *nlrow, SCIP_SOL *sol, SCIP_Real *activity)
Definition: scip.c:32929
SCIP_EXPRCURV SCIPnlrowGetCurvature(SCIP_NLROW *nlrow)
Definition: nlp.c:3393
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4265
SCIP_VAR ** SCIPexprtreeGetVars(SCIP_EXPRTREE *tree)
Definition: nlp.c:101
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip.c:31434
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:557
int SCIPnlrowGetNQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3322
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3025
SCIP_RETCODE SCIPnlpiSolve(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:497
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:22599
SCIP_Real coef
Definition: type_expr.h:102
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:34522
int SCIPgetNNLPVars(SCIP *scip)
Definition: scip.c:31316
SCIP_VAR ** SCIPnlrowGetQuadVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3285
#define SEPA_PRIORITY
#define SCIPerrorMessage
Definition: pub_message.h:45
#define SCIPdebugPrintf
Definition: pub_message.h:80
SCIP_RETCODE SCIPexprintCreate(BMS_BLKMEM *blkmem, SCIP_EXPRINT **exprint)
SCIP_RETCODE SCIPincludeSepaConvexproj(SCIP *scip)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:46725
internal methods for NLP management
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:567
SCIP_RETCODE SCIPaddNlpiProbRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_ROW **rows, int nrows)
Definition: scip.c:34401
int SCIPgetNNlpis(SCIP *scip)
Definition: scip.c:9602
#define REALABS(x)
Definition: def.h:173
int SCIPexprtreeGetNVars(SCIP_EXPRTREE *tree)
Definition: expr.c:8612
int SCIPgetNLPRows(SCIP *scip)
Definition: scip.c:29690
SCIP_QUADELEM * SCIPnlrowGetQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3332
#define SEPA_DESC
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47318
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:34655
SCIP_NLPSOLSTAT SCIPnlpiGetSolstat(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:511
SCIP_RETCODE SCIPnlpiSetObjective(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nlins, const int *lininds, const SCIP_Real *linvals, int nquadelems, const SCIP_QUADELEM *quadelems, const int *exprvaridxs, const SCIP_EXPRTREE *exprtree, const SCIP_Real constant)
Definition: nlpi.c:300
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip.c:7385
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
Definition: scip.c:47045
SCIP_RETCODE SCIPnlpiFreeProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem)
Definition: nlpi.c:224
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:38765
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip.c:7507
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
Definition: scip.c:30579
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
SCIP_RETCODE SCIPupdateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2nlpiidx, SCIP_VAR **nlpivars, int nlpinvars, SCIP_Real cutoffbound)
Definition: scip.c:34349
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
Definition: var.c:17663
static SCIP_RETCODE computeGradient(SCIP *scip, SCIP_EXPRINT *exprint, SCIP_SOL *projection, SCIP_EXPRTREE *exprtree, SCIP_Real *grad)
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
SCIP_RETCODE SCIPnlpiSetIntPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, int ival)
Definition: nlpi.c:636
SCIP_EXPRINTDATA * SCIPexprtreeGetInterpreterData(SCIP_EXPRTREE *tree)
Definition: expr.c:8657
#define MAX(x, y)
Definition: tclique_def.h:75
#define DEFAULT_MAXDEPTH
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip.c:30425
#define SEPA_NAME
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition: scip.c:30555
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:34499
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:38529
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
#define BMSclearMemory(ptr)
Definition: memory.h:111
SCIP_RETCODE SCIPexprintGrad(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Bool new_varvals, SCIP_Real *val, SCIP_Real *gradient)
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
#define SCIP_REAL_MAX
Definition: def.h:150
SCIP_EXPRTREE * SCIPnlrowGetExprtree(SCIP_NLROW *nlrow)
Definition: nlp.c:3363
static SCIP_RETCODE generateCut(SCIP *scip, SCIP_SEPA *sepa, SCIP_EXPRINT *exprint, SCIP_SOL *projection, SCIP_NLROW *nlrow, CONVEXSIDE convexside, SCIP_Real activity, SCIP_ROW **row)
#define DEFAULT_NLPITERLIM
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30534
#define SEPA_FREQ
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip.c:7443
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29366
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11761
#define SEPA_USESSUBSCIP
#define SCIP_Real
Definition: def.h:149
#define NLPVERBOSITY
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
static SCIP_DECL_SEPAFREE(sepaFreeConvexproj)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:31154
SCIP_RETCODE SCIPprintNlRow(SCIP *scip, SCIP_NLROW *nlrow, FILE *file)
Definition: scip.c:33022
SCIP_RETCODE SCIPcreateCurrentSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:38027
SCIP_RETCODE SCIPnlpiChgLinearCoefs(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, const int idx, int nvals, const int *varidxs, const SCIP_Real *vals)
Definition: nlpi.c:395
SCIP_Real SCIPgetNLPObjval(SCIP *scip)
Definition: scip.c:31681
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46983
SCIP_Real * SCIPnlrowGetLinearCoefs(SCIP_NLROW *nlrow)
Definition: nlp.c:3265
const char * SCIPnlrowGetName(SCIP_NLROW *nlrow)
Definition: nlp.c:3412
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
SCIP_VAR ** SCIPnlrowGetLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3255
ConvexSide
SCIP_NLPI ** SCIPgetNlpis(SCIP *scip)
Definition: scip.c:9589
SCIP_RETCODE SCIPexprintFree(SCIP_EXPRINT **exprint)
#define SEPA_MAXBOUNDDIST
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
#define SEPA_DELAY
SCIP_Real SCIPnlrowGetLhs(SCIP_NLROW *nlrow)
Definition: nlp.c:3373
#define SCIPABORT()
Definition: def.h:322
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38905
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4321
enum ConvexSide CONVEXSIDE
#define DEFAULT_NLPTIMELIMIT
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:38
static SCIP_RETCODE sepadataClear(SCIP *scip, SCIP_SEPADATA *sepadata)
#define VIOLATIONFAC
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37872
SCIP_RETCODE SCIPnlpiSetRealPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, SCIP_Real dval)
Definition: nlpi.c:671
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip.c:39319