Scippy

SCIP

Solving Constraint Integer Programs

sepa_gauge.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file sepa_gauge.c
17  * @ingroup DEFPLUGINS_SEPA
18  * @brief gauge separator
19  * @author Felipe Serrano
20  *
21  * @todo should separator only be run when SCIPallColsInLP is true?
22  * @todo add SCIPisStopped(scip) to the condition of time consuming loops
23  * @todo check if it makes sense to implement the copy callback
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 #include <assert.h>
29 #include <string.h>
30 
31 #include "blockmemshell/memory.h"
32 #include "scip/scip_nlpi.h"
33 #include "scip/nlpi_ipopt.h"
34 #include "scip/nlpioracle.h"
35 #include "scip/scip_expr.h"
36 #include "scip/pub_expr.h"
37 #include "scip/pub_lp.h"
38 #include "scip/pub_message.h"
39 #include "scip/pub_misc.h"
40 #include "scip/pub_nlp.h"
41 #include "scip/pub_sepa.h"
42 #include "scip/pub_var.h"
43 #include "scip/scip_cut.h"
44 #include "scip/scip_lp.h"
45 #include "scip/scip_mem.h"
46 #include "scip/scip_message.h"
47 #include "scip/scip_nlp.h"
48 #include "scip/scip_numerics.h"
49 #include "scip/scip_param.h"
50 #include "scip/scip_prob.h"
51 #include "scip/scip_sepa.h"
52 #include "scip/scip_sol.h"
53 #include "scip/scip_solvingstats.h"
54 #include "scip/scip_timing.h"
55 #include "scip/sepa_gauge.h"
56 #include <string.h>
57 
58 
59 #define SEPA_NAME "gauge"
60 #define SEPA_DESC "gauge separator"
61 #define SEPA_PRIORITY 0
62 #define SEPA_FREQ -1
63 #define SEPA_MAXBOUNDDIST 1.0
64 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
65 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
66 
67 #define VIOLATIONFAC 100 /**< constraints regarded as violated when violation > VIOLATIONFAC*SCIPfeastol */
68 #define MAX_ITER 75 /**< maximum number of iterations for the line search */
69 
70 #define DEFAULT_NLPITERLIM 1000 /**< default NLP iteration limit */
71 
72 #define NLPFEASFAC 1e-1/**< NLP feasibility tolerance = NLPFEASFAC * SCIP's feasibility tolerance */
73 
74 #define INTERIOROBJVARLB -100 /**< lower bound of the objective variable when computing interior point */
75 
76 /*
77  * Data structures
78  */
79 
80 /** side that makes a nlrow convex */
82 {
83  LHS = 0, /**< left hand side */
84  RHS = 1 /**< right hand side */
85 };
86 typedef enum ConvexSide CONVEXSIDE;
87 
88 /** position of a point */
90 {
91  INTERIOR = 0, /**< point is in the interior of the region */
92  BOUNDARY = 1, /**< point is in the boundary of the region */
93  EXTERIOR = 2 /**< point is in the exterior of the region */
94 };
95 typedef enum Position POSITION;
96 
97 /** separator data */
98 struct SCIP_SepaData
99 {
100  SCIP_NLROW** nlrows; /**< stores convex nlrows */
101  CONVEXSIDE* convexsides; /**< which sides make the nlrows convex */
102  int* nlrowsidx; /**< indices of nlrows that violate the current lp solution */
103  int nnlrowsidx; /**< total number of convex nonlinear nlrows that violate the current lp solution */
104  int nnlrows; /**< total number of convex nonlinear nlrows */
105  int nlrowssize; /**< memory allocated for nlrows, convexsides and nlrowsidx */
106 
107  SCIP_Bool isintsolavailable; /**< do we have an interior point available? */
108  SCIP_Bool skipsepa; /**< whether separator should be skipped */
109  SCIP_SOL* intsol; /**< stores interior point */
110 
111  int ncuts; /**< number of cuts generated */
112 
113  /* parameters */
114  int nlpiterlimit; /**< iteration limit of NLP solver; 0 for no limit */
115 };
116 
117 /*
118  * Local methods
119  */
120 
121 /** stores, from the constraints represented by nlrows, the nonlinear convex ones in sepadata */
122 static
124  SCIP* scip, /**< SCIP data structure */
125  SCIP_SEPADATA* sepadata, /**< separator data */
126  SCIP_NLROW** nlrows, /**< nlrows from which to store convex ones */
127  int nnlrows /**< number of nlrows */
128  )
129 {
130  int i;
131 
132  assert(scip != NULL);
133  assert(sepadata != NULL);
134  assert(nlrows != NULL);
135  assert(nnlrows > 0);
136 
137  SCIPdebugMsg(scip, "storing convex nlrows\n");
138 
139  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(sepadata->nlrows), nnlrows) );
140  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(sepadata->convexsides), nnlrows) );
141  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(sepadata->nlrowsidx), nnlrows) );
142  sepadata->nlrowssize = nnlrows;
143 
144  sepadata->nnlrows = 0;
145  for( i = 0; i < nnlrows; ++i )
146  {
147  SCIP_NLROW* nlrow;
148 
149  nlrow = nlrows[i];
150  assert(nlrow != NULL);
151 
152  /* linear case */
154  continue;
155 
156  /* nonlinear case */
158  {
159  sepadata->convexsides[sepadata->nnlrows] = RHS;
160  sepadata->nlrows[sepadata->nnlrows] = nlrow;
161  ++(sepadata->nnlrows);
162  }
163  else if( !SCIPisInfinity(scip, -SCIPnlrowGetLhs(nlrow)) && SCIPnlrowGetCurvature(nlrow) == SCIP_EXPRCURV_CONCAVE )
164  {
165  sepadata->convexsides[sepadata->nnlrows] = LHS;
166  sepadata->nlrows[sepadata->nnlrows] = nlrow;
167  ++(sepadata->nnlrows);
168  }
169  }
170 
171  return SCIP_OKAY;
172 }
173 
174 /** computes an interior point of a convex NLP relaxation
175  *
176  * builds the convex relaxation, modifies it to find an interior
177  * point, solves it and frees it; more details in @ref sepa_gauge.h
178  *
179  * @note the method also counts the number of nonlinear convex constraints and if there are < 2, then the convex
180  * relaxation is not interesting and the separator will not run again
181  */
182 static
184  SCIP* scip, /**< SCIP data structure */
185  SCIP_SEPADATA* sepadata /**< separator data */
186  )
187 {
188  SCIP_NLPIORACLE* nlpioracle;
189  SCIP_NLPIPROBLEM* nlpiprob;
190  SCIP_NLPI* nlpi;
191  SCIP_HASHMAP* var2nlpiidx;
192  SCIP_Real objvarlb;
193  SCIP_Real minusone;
194  SCIP_Real one;
195  int nconvexnlrows;
196  int objvaridx;
197  int nconss;
198  int nvars;
199  int i;
200 
201  assert(scip != NULL);
202  assert(sepadata != NULL);
203  assert(!sepadata->skipsepa);
204 
205  SCIPdebugMsg(scip, "Computing interior point\n");
206 
207  /* create convex relaxation NLP */
208  assert(SCIPgetNNlpis(scip) > 0);
209 
210  nlpi = SCIPgetNlpis(scip)[0];
211  assert(nlpi != NULL);
212 
213  nvars = SCIPgetNVars(scip);
214  SCIP_CALL( SCIPhashmapCreate(&var2nlpiidx, SCIPblkmem(scip), nvars) );
215  SCIP_CALL( SCIPcreateNlpiProblemFromNlRows(scip, nlpi, &nlpiprob, "gauge-interiorpoint-nlp", SCIPgetNLPNlRows(scip), SCIPgetNNLPNlRows(scip), var2nlpiidx,
216  NULL, NULL, SCIPgetCutoffbound(scip), FALSE, TRUE) );
217 
218  /* add objective variable; the problem is \min t, s.t. g(x) <= t, l(x) <= 0, where g are nonlinear and l linear */
219  objvaridx = nvars;
220  objvarlb = INTERIOROBJVARLB;
221  one = 1.0;
222  SCIP_CALL( SCIPaddNlpiVars(scip, nlpi, nlpiprob, 1, &objvarlb, NULL, NULL) );
223  SCIP_CALL( SCIPsetNlpiObjective(scip, nlpi, nlpiprob, 1, &objvaridx, &one, NULL, 0.0) );
224 
225  /* add objective variables to constraints; for this we need to get nlpi oracle to have access to number of
226  * constraints and which constraints are nonlinear
227  */
228  /* @todo: this code is only valid when using IPOPT and needs to be changed when new NLP solvers get interfaced */
229  assert(strcmp(SCIPnlpiGetName(nlpi), "ipopt") == 0);
230  nlpioracle = (SCIP_NLPIORACLE *)SCIPgetNlpiOracleIpopt(nlpiprob);
231  assert(nlpioracle != NULL);
232  assert(SCIPnlpiOracleGetNVars(nlpioracle) == objvaridx + 1);
233 
234  minusone = -1.0;
235  nconvexnlrows = 0;
236  nconss = SCIPnlpiOracleGetNConstraints(nlpioracle);
237  for( i = 0; i < nconss; i++ )
238  {
239  if( SCIPnlpiOracleIsConstraintNonlinear(nlpioracle, i) )
240  {
241  SCIP_CALL( SCIPchgNlpiLinearCoefs(scip, nlpi, nlpiprob, i, 1, &objvaridx, &minusone) );
242  ++nconvexnlrows;
243  }
244  }
245  SCIPdebug( SCIP_CALL( SCIPnlpiOraclePrintProblem(scip, nlpioracle, NULL) ) );
246 
247  /* check if convex relaxation is interesting */
248  if( nconvexnlrows < 2 )
249  {
250  SCIPdebugMsg(scip, "convex relaxation is not interesting, only %d nonlinear convex rows; abort\n", nconvexnlrows);
251  sepadata->skipsepa = TRUE;
252  goto CLEANUP;
253  }
254 
255  /* add linear rows */
256  SCIP_CALL( SCIPaddNlpiProblemRows(scip, nlpi, nlpiprob, var2nlpiidx, SCIPgetLPRows(scip), SCIPgetNLPRows(scip)) );
257 
258  /* compute interior point */
259  SCIPdebugMsg(scip, "starting interior point computation\n");
260  SCIP_CALL( SCIPsolveNlpi(scip, nlpi, nlpiprob,
261  .iterlimit = sepadata->nlpiterlimit > 0 ? sepadata->nlpiterlimit : INT_MAX,
262  .feastol = NLPFEASFAC * SCIPfeastol(scip),
263  .opttol = MAX(SCIPfeastol(scip), SCIPdualfeastol(scip))) ); /*lint !e666*/
264  SCIPdebugMsg(scip, "finish interior point computation\n");
265 
266 #ifdef SCIP_DEBUG
267  {
268  SCIP_NLPSTATISTICS nlpstatistics;
269 
270  /* get statistics */
271  SCIP_CALL( SCIPgetNlpiStatistics(scip, nlpi, nlpiprob, &nlpstatistics) );
272 
273  SCIPdebugMsg(scip, "nlpi took iters %d, time %g searching for an find interior point: solstat %d\n",
274  nlpstatistics.niterations, nlpstatistics.totaltime,
275  SCIPgetNlpiSolstat(scip, nlpi, nlpiprob));
276  }
277 #endif
278 
279  if( SCIPgetNlpiSolstat(scip, nlpi, nlpiprob) <= SCIP_NLPSOLSTAT_FEASIBLE )
280  {
281  SCIP_Real* nlpisol;
282 
283  SCIP_CALL( SCIPgetNlpiSolution(scip, nlpi, nlpiprob, &nlpisol, NULL, NULL, NULL, NULL) );
284 
285  assert(nlpisol != NULL);
286  SCIPdebugMsg(scip, "NLP solved: sol found has objvalue = %g\n", nlpisol[objvaridx]);
287 
288  /* if we found an interior point store it */
289  if( SCIPisFeasNegative(scip, nlpisol[objvaridx]) )
290  {
291  SCIPdebugMsg(scip, "Interior point found!, storing it\n");
292  SCIP_CALL( SCIPcreateSol(scip, &sepadata->intsol, NULL) );
293  for( i = 0; i < nvars; i ++ )
294  {
295  SCIP_VAR* var;
296 
297  var = SCIPgetVars(scip)[i];
298  assert(SCIPhashmapExists(var2nlpiidx, (void*)var) );
299 
300  /* @todo: filter zero? */
301  SCIP_CALL( SCIPsetSolVal(scip, sepadata->intsol, var,
302  nlpisol[SCIPhashmapGetImageInt(var2nlpiidx, (void *)var)]) );
303  }
304 
305  sepadata->isintsolavailable = TRUE;
306  }
307  else
308  {
309  SCIPdebugMsg(scip, "We got a feasible point but not interior (objval: %g)\n", nlpisol[objvaridx]);
310  sepadata->skipsepa = TRUE;
311  }
312  }
313  else
314  {
315  SCIPdebugMsg(scip, "We couldn't get an interior point (stat: %d)\n", SCIPgetNlpiSolstat(scip, nlpi, nlpiprob));
316  sepadata->skipsepa = TRUE;
317  }
318 
319 CLEANUP:
320  /* free memory */
321  SCIPhashmapFree(&var2nlpiidx);
322  SCIP_CALL( SCIPfreeNlpiProblem(scip, nlpi, &nlpiprob) );
323 
324  return SCIP_OKAY;
325 }
326 
327 
328 /** find whether point is in the interior, at the boundary, or in the exterior of the region described by the
329  * intersection of `nlrows[i]` &le; rhs if `convexsides[i]` = RHS or lhs &le; `nlrows[i]` if `convexsides[i]` = LHS
330  *
331  * @note point corresponds to a convex combination between the LP solution and the interior point
332  */
333 static
335  SCIP* scip, /**< SCIP data structure */
336  SCIP_NLROW** nlrows, /**< nlrows defining the region */
337  int* nlrowsidx, /**< indices of nlrows defining the region */
338  int nnlrowsidx, /**< number of nlrows indices */
339  CONVEXSIDE* convexsides, /**< sides of the nlrows involved in the region */
340  SCIP_SOL* point, /**< point for which we want to know its position */
341  POSITION* position /**< buffer to store position of sol */
342  )
343 {
344  int i;
345 
346  assert(scip != NULL);
347  assert(nlrows != NULL);
348  assert(convexsides != NULL);
349  assert(nnlrowsidx > 0);
350  assert(point != NULL);
351  assert(position != NULL);
352 
353  *position = INTERIOR;
354  for( i = 0; i < nnlrowsidx; i++ )
355  {
356  SCIP_NLROW* nlrow;
357  SCIP_Real activity;
358  CONVEXSIDE convexside;
359 
360  nlrow = nlrows[nlrowsidx[i]];
361  convexside = convexsides[nlrowsidx[i]];
362 
363  /* compute activity of nlrow at point */
364  SCIP_CALL( SCIPgetNlRowSolActivity(scip, nlrow, point, &activity) );
365 
366  if( convexside == RHS )
367  {
368  assert(!SCIPisInfinity(scip, SCIPnlrowGetRhs(nlrow)));
369 
370  /* if nlrow <= rhs is violated, then we are in the exterior */
371  if( SCIPisFeasGT(scip, activity, SCIPnlrowGetRhs(nlrow)) )
372  {
373  *position = EXTERIOR;
374  SCIPdebugMsg(scip, "exterior because cons <%s> has activity %g. rhs: %g\n", SCIPnlrowGetName(nlrow),
375  activity, SCIPnlrowGetRhs(nlrow));
376  SCIPdebug( SCIPprintNlRow(scip, nlrow, NULL) );
377 
378  return SCIP_OKAY;
379  }
380 
381  /* if nlrow(point) == rhs, then we are currently at the boundary */
382  if( SCIPisFeasEQ(scip, activity, SCIPnlrowGetRhs(nlrow)) )
383  *position = BOUNDARY;
384  }
385  else
386  {
387  assert(!SCIPisInfinity(scip, -SCIPnlrowGetLhs(nlrow)));
388  assert(convexside == LHS);
389 
390  /* if lhs <= nlrow is violated, then we are in the exterior */
391  if( SCIPisFeasLT(scip, activity, SCIPnlrowGetLhs(nlrow)) )
392  {
393  *position = EXTERIOR;
394  return SCIP_OKAY;
395  }
396 
397  /* if lhs == nlrow(point), then we are currently at the boundary */
398  if( SCIPisFeasEQ(scip, activity, SCIPnlrowGetLhs(nlrow)) )
399  *position = BOUNDARY;
400  }
401  }
402 
403  return SCIP_OKAY;
404 }
405 
406 
407 /** returns, in convexcomb, the convex combination
408  * \f$ \lambda\, \text{endpoint} + (1 - \lambda) \text{startpoint} = \text{startpoint} + \lambda (\text{endpoint} - \text{startpoint})\f$
409  */
410 static
412  SCIP* scip, /**< SCIP data structure */
413  SCIP_Real lambda, /**< convex combination multiplier */
414  SCIP_SOL* startpoint, /**< point corresponding to \f$ \lambda = 0 \f$ */
415  SCIP_SOL* endpoint, /**< point corresponding to \f$ \lambda = 1 \f$ */
416  SCIP_SOL* convexcomb /**< solution to store convex combination of intsol and tosepasol */
417  )
418 {
419  SCIP_VAR** vars;
420  int nvars;
421  int i;
422 
423  assert(scip != NULL);
424  assert(startpoint != NULL);
425  assert(endpoint != NULL);
426  assert(convexcomb != NULL);
427 
428  vars = SCIPgetVars(scip);
429  nvars = SCIPgetNVars(scip);
430 
431  for( i = 0; i < nvars; i++ )
432  {
433  SCIP_Real val;
434  SCIP_VAR* var;
435 
436  var = vars[i];
437  val = lambda * SCIPgetSolVal(scip, endpoint, var) + (1.0 - lambda) * SCIPgetSolVal(scip, startpoint, var);
438 
439  if( !SCIPisZero(scip, val) )
440  {
441  SCIP_CALL( SCIPsetSolVal(scip, convexcomb, var, val) );
442  }
443  else
444  {
445  SCIP_CALL( SCIPsetSolVal(scip, convexcomb, var, 0.0) );
446  }
447  }
448 
449  return SCIP_OKAY;
450 }
451 
452 
453 /** performs binary search to find the point belonging to the segment [`intsol`, `tosepasol`] that intersects the boundary
454  * of the region described by the intersection of `nlrows[i]` &le; rhs if `convexsides[i] = RHS` or lhs &le; `nlrows[i]` if not,
455  * for i in `nlrowsidx`
456  */
457 static
459  SCIP* scip, /**< SCIP data structure */
460  SCIP_NLROW** nlrows, /**< nlrows defining the region */
461  int* nlrowsidx, /**< indices of nlrows defining the region */
462  int nnlrowsidx, /**< number of nlrows indices */
463  CONVEXSIDE* convexsides, /**< sides of the nlrows involved in the region */
464  SCIP_SOL* intsol, /**< point acting as 'interior point' */
465  SCIP_SOL* tosepasol, /**< solution that should be separated */
466  SCIP_SOL* sol, /**< convex combination of intsol and lpsol */
467  POSITION* position /**< buffer to store position of sol */
468  )
469 {
470  SCIP_Real lb;
471  SCIP_Real ub;
472  int i;
473 
474  assert(scip != NULL);
475  assert(nlrows != NULL);
476  assert(nlrowsidx != NULL);
477  assert(convexsides != NULL);
478  assert(intsol != NULL);
479  assert(tosepasol != NULL);
480  assert(sol != NULL);
481  assert(position != NULL);
482 
483  SCIPdebugMsg(scip, "starting binary search\n");
484  lb = 0.0; /* corresponds to intsol */
485  ub = 1.0; /* corresponds to tosepasol */
486  for( i = 0; i < MAX_ITER; i++ )
487  {
488  /* sol = (ub+lb)/2 * lpsol + (1 - (ub+lb)/2) * intsol */
489  SCIP_CALL( buildConvexCombination(scip, (ub + lb)/2.0, intsol, tosepasol, sol) );
490 
491  /* find poisition of point: boundary, interior, exterior */
492  SCIP_CALL( findPointPosition(scip, nlrows, nlrowsidx, nnlrowsidx, convexsides, sol, position) );
493  SCIPdebugMsg(scip, "Position: %d, lambda: %g\n", *position, (ub + lb)/2.0);
494 
495  switch( *position )
496  {
497  case BOUNDARY:
498  SCIPdebugMsg(scip, "Done\n");
499  return SCIP_OKAY;
500 
501  case INTERIOR:
502  /* want to be closer to tosepasol */
503  lb = (ub + lb)/2.0;
504  break;
505 
506  case EXTERIOR:
507  /* want to be closer to intsol */
508  ub = (ub + lb)/2.0;
509  break;
510  }
511  }
512  SCIPdebugMsg(scip, "Done\n");
513  return SCIP_OKAY;
514 }
515 
516 
517 /** computes gradient cut (linearization) of nlrow at sol */
518 static
520  SCIP* scip, /**< SCIP data structure */
521  SCIP_SOL* sol, /**< point used to construct gradient cut (x_0) */
522  SCIP_NLROW* nlrow, /**< constraint */
523  CONVEXSIDE convexside, /**< whether we use rhs or lhs of nlrow */
524  SCIP_EXPRITER* exprit, /**< expression iterator that can be used */
525  SCIP_ROW* row, /**< storage for cut */
526  SCIP_Bool* success /**< buffer to store whether the gradient was finite */
527  )
528 {
529  SCIP_EXPR* expr;
530  SCIP_Real exprval;
531  SCIP_Real gradx0; /* <grad f(x_0), x_0> */
532  int i;
533 
534  assert(scip != NULL);
535  assert(nlrow != NULL);
536  assert(row != NULL);
537 
538  gradx0 = 0.0;
539  *success = TRUE;
540 
541  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
542 
543 #ifdef CUT_DEBUG
544  SCIPdebug( SCIP_CALL( SCIPprintNlRow(scip, nlrow, NULL) ) );
545 #endif
546 
547  /* linear part */
548  for( i = 0; i < SCIPnlrowGetNLinearVars(nlrow); i++ )
549  {
550  SCIP_CALL( SCIPaddVarToRow(scip, row, SCIPnlrowGetLinearVars(nlrow)[i], SCIPnlrowGetLinearCoefs(nlrow)[i]) );
551  }
552 
553  expr = SCIPnlrowGetExpr(nlrow);
554  assert(expr != NULL);
555 
556  SCIP_CALL( SCIPevalExprGradient(scip, expr, sol, 0L) );
557 
559  for( ; !SCIPexpriterIsEnd(exprit); expr = SCIPexpriterGetNext(exprit) ) /*lint !e441*/ /*lint !e440*/
560  {
561  SCIP_Real grad;
562  SCIP_VAR* var;
563 
564  if( !SCIPisExprVar(scip, expr) )
565  continue;
566 
567  grad = SCIPexprGetDerivative(expr);
568  var = SCIPgetVarExprVar(expr);
569  assert(var != NULL);
570 
571  /* check gradient entries: function might not be differentiable */
572  if( !SCIPisFinite(grad) || grad == SCIP_INVALID ) /*lint !e777*/
573  {
574  *success = FALSE;
575  break;
576  }
577  /* SCIPdebugMsg(scip, "grad w.r.t. <%s> (%g) = %g, gradx0 += %g\n", SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var), grad, grad * SCIPgetSolVal(scip, sol, var)); */
578 
579  gradx0 += grad * SCIPgetSolVal(scip, sol, var);
580  SCIP_CALL( SCIPaddVarToRow(scip, row, var, grad) );
581  }
582 
583  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
584 
585  /* if there was a problem computing the cut -> return */
586  if( ! *success )
587  return SCIP_OKAY;
588 
589 #ifdef CUT_DEBUG
590  SCIPdebugMsg(scip, "gradient: ");
591  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
592  SCIPdebugMsg(scip, "gradient dot x_0: %g\n", gradx0);
593 #endif
594 
595  /* gradient cut is linear part + f(x_0) - <grad f(x_0), x_0> + <grad f(x_0), x> <= rhs or >= lhs */
596  exprval = SCIPexprGetEvalValue(SCIPnlrowGetExpr(nlrow));
597  assert(exprval != SCIP_INVALID); /* we should have noticed a domain error above */ /*lint !e777*/
598  if( convexside == RHS )
599  {
600  assert(!SCIPisInfinity(scip, SCIPnlrowGetRhs(nlrow)));
601  SCIP_CALL( SCIPchgRowRhs(scip, row, SCIPnlrowGetRhs(nlrow) - SCIPnlrowGetConstant(nlrow) - exprval + gradx0) );
602  }
603  else
604  {
605  assert(convexside == LHS);
606  assert(!SCIPisInfinity(scip, -SCIPnlrowGetLhs(nlrow)));
607  SCIP_CALL( SCIPchgRowLhs(scip, row, SCIPnlrowGetLhs(nlrow) - SCIPnlrowGetConstant(nlrow) - exprval + gradx0) );
608  }
609 
610 #ifdef CUT_DEBUG
611  SCIPdebugMsg(scip, "gradient cut: ");
612  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
613 #endif
614 
615  return SCIP_OKAY;
616 }
617 
618 /** tries to generate gradient cuts at the point on the segment [`intsol`, `tosepasol`] that intersecs the boundary of the
619  * convex relaxation
620  *
621  * -# checks that the relative interior of the segment actually intersects the boundary
622  * (this check is needed since `intsol` is not necessarily an interior point)
623  * -# finds point on the boundary
624  * -# generates gradient cut at point on the boundary
625  */
626 static
628  SCIP* scip, /**< SCIP data structure */
629  SCIP_SEPA* sepa, /**< the cut separator itself */
630  SCIP_SOL* tosepasol, /**< solution that should be separated */
631  SCIP_RESULT* result /**< pointer to store the result of the separation call */
632  )
633 {
634  SCIP_SEPADATA* sepadata;
635  SCIP_NLROW** nlrows;
636  CONVEXSIDE* convexsides;
637  SCIP_SOL* sol;
638  SCIP_SOL* intsol;
639  POSITION position;
640  int* nlrowsidx;
641  int nnlrowsidx;
642  int i;
643  SCIP_EXPRITER* exprit;
644 
645  assert(sepa != NULL);
646 
647  sepadata = SCIPsepaGetData(sepa);
648  assert(sepadata != NULL);
649 
650  intsol = sepadata->intsol;
651  nlrows = sepadata->nlrows;
652  nlrowsidx = sepadata->nlrowsidx;
653  nnlrowsidx = sepadata->nnlrowsidx;
654  convexsides = sepadata->convexsides;
655 
656  assert(intsol != NULL);
657  assert(nlrows != NULL);
658  assert(nlrowsidx != NULL);
659  assert(nnlrowsidx > 0);
660  assert(convexsides != NULL);
661 
662  /* to evaluate the nlrow one needs a solution */
663  SCIP_CALL( SCIPcreateSol(scip, &sol, NULL) );
664 
665  /* don't separate if, under SCIP tolerances, only a slight perturbation of the interior point in the direction of
666  * tosepasol gives a point that is in the exterior */
667  SCIP_CALL( buildConvexCombination(scip, VIOLATIONFAC * SCIPfeastol(scip), intsol, tosepasol, sol) );
668  SCIP_CALL( findPointPosition(scip, nlrows, nlrowsidx, nnlrowsidx, convexsides, sol, &position) );
669 
670  if( position == EXTERIOR )
671  {
672 #ifdef SCIP_DEBUG
673  SCIPdebugMsg(scip, "segment joining intsol and tosepasol seems to be contained in the exterior of the region, can't separate\n");
674  /* move from intsol in the direction of -tosepasol to check if we are really tangent to the region */
675  SCIP_CALL( buildConvexCombination(scip, -1e-3, intsol, tosepasol, sol) );
676  SCIP_CALL( findPointPosition(scip, nlrows, nlrowsidx, nnlrowsidx, convexsides, sol, &position) );
677  if( position == EXTERIOR )
678  {
679  SCIPdebugMsg(scip, "line through intsol and tosepasol is tangent to region; can't separate\n");
680  }
681  SCIP_CALL( findPointPosition(scip, nlrows, nlrowsidx, nnlrowsidx, convexsides, intsol, &position) );
682  printf("Position of intsol is %s\n",
683  position == EXTERIOR ? "exterior" : position == INTERIOR ? "interior": "boundary");
684  SCIP_CALL( findPointPosition(scip, nlrows, nlrowsidx, nnlrowsidx, convexsides, tosepasol, &position) );
685  printf("Position of tosepasol is %s\n",
686  position == EXTERIOR ? "exterior" : position == INTERIOR ? "interior": "boundary");
687 
688  /* slightly move from intsol in the direction of +-tosepasol */
689  SCIP_CALL( buildConvexCombination(scip, 1e-5, intsol, tosepasol, sol) );
690  SCIP_CALL( findPointPosition(scip, nlrows, nlrowsidx, nnlrowsidx, convexsides, sol, &position) );
691  printf("Position of intsol + 0.00001(tosepasol - inisol) is %s\n",
692  position == EXTERIOR ? "exterior" : position == INTERIOR ? "interior": "boundary");
693  SCIPdebug( SCIPprintSol(scip, sol, NULL, FALSE) );
694 
695  SCIP_CALL( buildConvexCombination(scip, -1e-5, intsol, tosepasol, sol) );
696  SCIP_CALL( findPointPosition(scip, nlrows, nlrowsidx, nnlrowsidx, convexsides, sol, &position) );
697  printf("Position of intsol - 0.00001(tosepasol - inisol) is %s\n",
698  position == EXTERIOR ? "exterior" : position == INTERIOR ? "interior": "boundary");
699  SCIPdebug( SCIPprintSol(scip, sol, NULL, FALSE) );
700 #endif
701  *result = SCIP_DIDNOTFIND;
702  goto CLEANUP;
703  }
704 
705  /* find point on boundary */
706  if( position != BOUNDARY )
707  {
708  SCIP_CALL( findBoundaryPoint(scip, nlrows, nlrowsidx, nnlrowsidx, convexsides, intsol, tosepasol, sol,
709  &position) );
710 
711  /* if MAX_ITER weren't enough to find a point in the boundary we don't separate */
712  if( position != BOUNDARY )
713  {
714  SCIPdebugMsg(scip, "couldn't find boundary point, don't separate\n");
715  goto CLEANUP;
716  }
717  }
718 
719  /** @todo: could probably be moved inside generateCut */
720  SCIP_CALL( SCIPcreateExpriter(scip, &exprit) );
721 
722  /* generate cuts at sol */
723  for( i = 0; i < nnlrowsidx; i++ )
724  {
725  SCIP_NLROW* nlrow;
726  SCIP_ROW* row;
727  SCIP_Real activity;
728  CONVEXSIDE convexside;
729  SCIP_Bool success;
730  char rowname[SCIP_MAXSTRLEN];
731 
732  nlrow = nlrows[nlrowsidx[i]];
733  convexside = convexsides[nlrowsidx[i]];
734 
735  (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_%u", SCIPnlrowGetName(nlrow), ++(sepadata->ncuts));
736 
737  /* only separate nlrows that are tight at the boundary point */
738  SCIP_CALL( SCIPgetNlRowSolActivity(scip, nlrow, sol, &activity) );
739  SCIPdebugMsg(scip, "cons <%s> at boundary point has activity: %g\n", SCIPnlrowGetName(nlrow), activity);
740 
741  if( (convexside == RHS && !SCIPisFeasEQ(scip, activity, SCIPnlrowGetRhs(nlrow)))
742  || (convexside == LHS && !SCIPisFeasEQ(scip, activity, SCIPnlrowGetLhs(nlrow))) )
743  continue;
744 
745  /* cut is globally valid, since we work on nlrows from the NLP built at the root node, which are globally valid */
746  /* @todo: when local nlrows get supported in SCIP, one can think of recomputing the interior point */
747  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, rowname, -SCIPinfinity(scip), SCIPinfinity(scip),
748  FALSE, FALSE , TRUE) );
749  SCIP_CALL( generateCut(scip, sol, nlrow, convexside, exprit, row, &success) );
750 
751  /* add cut */
752  SCIPdebugMsg(scip, "cut <%s> has efficacy %g\n", SCIProwGetName(row), SCIPgetCutEfficacy(scip, NULL, row));
753  if( success && SCIPisCutEfficacious(scip, NULL, row) )
754  {
755  SCIP_Bool infeasible;
756 
757  SCIPdebugMsg(scip, "adding cut\n");
758  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
759 
760  if( infeasible )
761  {
762  *result = SCIP_CUTOFF;
763  SCIP_CALL( SCIPreleaseRow(scip, &row) );
764  break;
765  }
766  else
767  {
768  *result = SCIP_SEPARATED;
769  }
770  }
771 
772  /* release the row */
773  SCIP_CALL( SCIPreleaseRow(scip, &row) );
774  }
775 
776  SCIPfreeExpriter(&exprit);
777 
778 CLEANUP:
779  SCIP_CALL( SCIPfreeSol(scip, &sol) );
780 
781  return SCIP_OKAY;
782 }
783 
784 /*
785  * Callback methods of separator
786  */
787 
788 
789 /** destructor of separator to free user data (called when SCIP is exiting) */
790 static
791 SCIP_DECL_SEPAFREE(sepaFreeGauge)
792 { /*lint --e{715}*/
793  SCIP_SEPADATA* sepadata;
794 
795  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
796 
797  /* free separator data */
798  sepadata = SCIPsepaGetData(sepa);
799  assert(sepadata != NULL);
800 
801  SCIPfreeBlockMemory(scip, &sepadata);
802 
803  SCIPsepaSetData(sepa, NULL);
804 
805  return SCIP_OKAY;
806 }
807 
808 
809 /** solving process deinitialization method of separator (called before branch and bound process data is freed) */
810 static
811 SCIP_DECL_SEPAEXITSOL(sepaExitsolGauge)
812 { /*lint --e{715}*/
813  SCIP_SEPADATA* sepadata;
814 
815  assert(sepa != NULL);
816 
817  sepadata = SCIPsepaGetData(sepa);
818 
819  assert(sepadata != NULL);
820 
821  /* free memory and reset data */
822  if( sepadata->isintsolavailable )
823  {
824  SCIPfreeBlockMemoryArray(scip, &sepadata->nlrowsidx, sepadata->nlrowssize);
825  SCIPfreeBlockMemoryArray(scip, &sepadata->convexsides, sepadata->nlrowssize);
826  SCIPfreeBlockMemoryArray(scip, &sepadata->nlrows, sepadata->nlrowssize);
827  SCIP_CALL( SCIPfreeSol(scip, &sepadata->intsol) );
828 
829  sepadata->nnlrows = 0;
830  sepadata->nnlrowsidx = 0;
831  sepadata->nlrowssize = 0;
832  sepadata->isintsolavailable = FALSE;
833  }
834  assert(sepadata->nnlrows == 0);
835  assert(sepadata->nnlrowsidx == 0);
836  assert(sepadata->nlrowssize == 0);
837  assert(sepadata->isintsolavailable == FALSE);
838 
839  sepadata->skipsepa = FALSE;
840 
841  return SCIP_OKAY;
842 }
843 
844 
845 /** LP solution separation method of separator */
846 static
847 SCIP_DECL_SEPAEXECLP(sepaExeclpGauge)
848 { /*lint --e{715}*/
849  SCIP_SEPADATA* sepadata;
850  SCIP_SOL* lpsol;
851  int i;
852 
853  assert(scip != NULL);
854  assert(sepa != NULL);
855 
856  sepadata = SCIPsepaGetData(sepa);
857 
858  assert(sepadata != NULL);
859 
860  *result = SCIP_DIDNOTRUN;
861 
862  /* do not run if there is no interesting convex relaxation (with at least two nonlinear convex constraint) */
863  if( sepadata->skipsepa )
864  {
865  SCIPdebugMsg(scip, "not running because convex relaxation is uninteresting\n");
866  return SCIP_OKAY;
867  }
868 
869  /* do not run if SCIP has not constructed an NLP */
870  if( !SCIPisNLPConstructed(scip) )
871  {
872  SCIPdebugMsg(scip, "NLP not constructed, skipping gauge separator\n");
873  return SCIP_OKAY;
874  }
875 
876  /* do not run if SCIP has no way of solving nonlinear problems */
877  if( SCIPgetNNlpis(scip) == 0 )
878  {
879  SCIPdebugMsg(scip, "Skip gauge separator: no nlpi and SCIP can't solve nonlinear problems without a nlpi\n");
880  return SCIP_OKAY;
881  }
882 
883  /* if we don't have an interior point compute one; if we fail to compute one, then separator will not be run again;
884  * otherwise, we also store the convex nlrows in sepadata
885  */
886  if( !sepadata->isintsolavailable )
887  {
888  /* @todo: one could store the convex nonlinear rows inside computeInteriorPoint */
889  SCIP_CALL( computeInteriorPoint(scip, sepadata) );
890  assert(sepadata->skipsepa || sepadata->isintsolavailable);
891 
892  if( sepadata->skipsepa )
893  return SCIP_OKAY;
894 
896  }
897 
898 #ifdef SCIP_DISABLED_CODE
899  /* get interior point: try to compute an interior point, otherwise use primal solution, otherwise use NLP solution */
900  /* @todo: - decide order:
901  * - we can also use convex combination of solutions; there is a function SCIPvarGetAvgSol!
902  * - can add an event handler to only update when a new solution has been found
903  */
904  if( !sepadata->isintsolavailable )
905  {
906  if( SCIPgetNSols(scip) > 0 )
907  {
908  SCIPdebugMsg(scip, "Using current primal solution as interior point!\n");
909  SCIP_CALL( SCIPcreateSolCopy(scip, &sepadata->intsol, SCIPgetBestSol(scip)) );
910  sepadata->isintsolavailable = TRUE;
911  }
913  {
914  SCIPdebugMsg(scip, "Using NLP solution as interior point!\n");
915  SCIP_CALL( SCIPcreateNLPSol(scip, &sepadata->intsol, NULL) );
916  sepadata->isintsolavailable = TRUE;
917  }
918  else
919  {
920  SCIPdebugMsg(scip, "We couldn't find an interior point, don't have a feasible nor an NLP solution; skip separator\n");
921  return SCIP_OKAY;
922  }
923  }
924 #endif
925 
926  /* store lp sol (or pseudo sol when lp is not solved) to be able to use it to compute nlrows' activities */
928 
929  /* store indices of relevant constraints, ie, the ones that violate the lp sol */
930  sepadata->nnlrowsidx = 0;
931  for( i = 0; i < sepadata->nnlrows; i++ )
932  {
933  SCIP_NLROW* nlrow;
934  SCIP_Real activity;
935 
936  nlrow = sepadata->nlrows[i];
937 
938  SCIP_CALL( SCIPgetNlRowSolActivity(scip, nlrow, lpsol, &activity) );
939 
940  if( sepadata->convexsides[i] == RHS )
941  {
942  assert(!SCIPisInfinity(scip, SCIPnlrowGetRhs(nlrow)));
943 
944  if( activity - SCIPnlrowGetRhs(nlrow) < VIOLATIONFAC * SCIPfeastol(scip) )
945  continue;
946  }
947  else
948  {
949  assert(sepadata->convexsides[i] == LHS);
950  assert(!SCIPisInfinity(scip, -SCIPnlrowGetLhs(nlrow)));
951 
952  if( SCIPnlrowGetLhs(nlrow) - activity < VIOLATIONFAC * SCIPfeastol(scip) )
953  continue;
954  }
955 
956  sepadata->nlrowsidx[sepadata->nnlrowsidx] = i;
957  ++(sepadata->nnlrowsidx);
958  }
959 
960  /* separate only if there are violated nlrows */
961  SCIPdebugMsg(scip, "there are %d violated nlrows\n", sepadata->nnlrowsidx);
962  if( sepadata->nnlrowsidx > 0 )
963  {
964  SCIP_CALL( separateCuts(scip, sepa, lpsol, result) );
965  }
966 
967  /* free lpsol */
968  SCIP_CALL( SCIPfreeSol(scip, &lpsol) );
969 
970  return SCIP_OKAY;
971 }
972 
973 
974 /*
975  * separator specific interface methods
976  */
977 
978 /** creates the gauge separator and includes it in SCIP */
980  SCIP* scip /**< SCIP data structure */
981  )
982 {
983  SCIP_SEPADATA* sepadata;
984  SCIP_SEPA* sepa;
985 
986  /* create gauge separator data */
987  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
988 
989  /* this sets all data in sepadata to 0 */
990  BMSclearMemory(sepadata);
991 
992  /* include separator */
995  sepaExeclpGauge, NULL,
996  sepadata) );
997 
998  assert(sepa != NULL);
999 
1000  /* set non fundamental callbacks via setter functions */
1001  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeGauge) );
1002  SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolGauge) );
1003 
1004  /* add gauge separator parameters */
1005  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/nlpiterlimit",
1006  "iteration limit of NLP solver; 0 for no limit",
1007  &sepadata->nlpiterlimit, TRUE, DEFAULT_NLPITERLIM, 0, INT_MAX, NULL, NULL) );
1008 
1009  return SCIP_OKAY;
1010 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SEPA_DESC
Definition: sepa_gauge.c:60
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip_lp.c:596
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:332
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition: expriter.c:491
SCIP_Real SCIPfeastol(SCIP *scip)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
void * SCIPgetNlpiOracleIpopt(SCIP_NLPIPROBLEM *nlpiproblem)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:101
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1626
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for memory management
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1649
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
public methods for timing
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17284
SCIP_VAR ** SCIPnlrowGetLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:1774
methods to store an NLP and request function, gradient, and Hessian values
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPdualfeastol(SCIP *scip)
static SCIP_RETCODE computeInteriorPoint(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_gauge.c:183
#define FALSE
Definition: def.h:87
gauge separator
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
const char * SCIPnlrowGetName(SCIP_NLROW *nlrow)
Definition: nlp.c:1843
static SCIP_DECL_SEPAFREE(sepaFreeGauge)
Definition: sepa_gauge.c:791
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
#define SCIPdebug(x)
Definition: pub_message.h:84
enum Position POSITION
Definition: sepa_gauge.c:95
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:720
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_Real SCIPnlrowGetRhs(SCIP_NLROW *nlrow)
Definition: nlp.c:1814
enum ConvexSide CONVEXSIDE
Definition: sepa_gauge.c:86
int SCIPnlrowGetNLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:1764
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define DEFAULT_NLPITERLIM
Definition: sepa_gauge.c:70
const char * SCIPnlpiGetName(SCIP_NLPI *nlpi)
Definition: nlpi.c:693
SCIP_RETCODE SCIPgetNlRowSolActivity(SCIP *scip, SCIP_NLROW *nlrow, SCIP_SOL *sol, SCIP_Real *activity)
Definition: scip_nlp.c:1454
SCIP_EXPRCURV SCIPnlrowGetCurvature(SCIP_NLROW *nlrow)
Definition: nlp.c:1824
SCIP_NLPI ** SCIPgetNlpis(SCIP *scip)
Definition: scip_nlpi.c:177
SCIP_RETCODE SCIPnlpiOraclePrintProblem(SCIP *scip, SCIP_NLPIORACLE *oracle, FILE *file)
Definition: nlpioracle.c:2445
#define SCIPdebugMsg
Definition: scip_message.h:69
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_param.c:74
public methods for separator plugins
SCIP_RETCODE SCIPevalExprGradient(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: scip_expr.c:1656
public methods for numerical tolerances
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:610
#define SEPA_MAXBOUNDDIST
Definition: sepa_gauge.c:63
public functions to work with algebraic expressions
public methods for querying solving statistics
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
Definition: sepa_gauge.c:84
int SCIPgetNNlpis(SCIP *scip)
Definition: scip_nlpi.c:190
static SCIP_DECL_SEPAEXITSOL(sepaExitsolGauge)
Definition: sepa_gauge.c:811
public methods for NLPI solver interfaces
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:108
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:609
SCIP_Real SCIPexprGetEvalValue(SCIP_EXPR *expr)
Definition: expr.c:3872
int SCIPnlpiOracleGetNConstraints(SCIP_NLPIORACLE *oracle)
Definition: nlpioracle.c:1717
static SCIP_RETCODE storeNonlinearConvexNlrows(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_NLROW **nlrows, int nnlrows)
Definition: sepa_gauge.c:123
SCIP_Real SCIPexprGetDerivative(SCIP_EXPR *expr)
Definition: expr.c:3898
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition: expr_var.c:407
int SCIPnlpiOracleGetNVars(SCIP_NLPIORACLE *oracle)
Definition: nlpioracle.c:1707
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
public functions to work with algebraic expressions
static SCIP_DECL_SEPAEXECLP(sepaExeclpGauge)
Definition: sepa_gauge.c:847
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
SCIP_Real totaltime
Definition: type_nlpi.h:191
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:620
#define NULL
Definition: lpi_spx1.cpp:155
#define SEPA_NAME
Definition: sepa_gauge.c:59
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:617
#define NLPFEASFAC
Definition: sepa_gauge.c:72
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:310
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:241
SCIP_RETCODE SCIPincludeSepaGauge(SCIP *scip)
Definition: sepa_gauge.c:979
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2300
public methods for NLP management
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_sepa.c:100
SCIP_RETCODE SCIPaddNlpiProblemRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_ROW **rows, int nrows)
Definition: scip_nlpi.c:772
Ipopt NLP interface.
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
public data structures and miscellaneous methods
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip_sepa.c:222
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
Definition: scip_lp.c:1598
SCIP_NLPSOLSTAT SCIPnlpGetSolstat(SCIP_NLP *nlp)
Definition: nlp.c:4378
#define MAX(x, y)
Definition: tclique_def.h:83
public methods for LP management
#define SEPA_DELAY
Definition: sepa_gauge.c:65
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_lp.c:1444
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition: scip_lp.c:1574
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:85
public methods for cuts and aggregation rows
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:848
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
SCIP_Bool SCIPnlpiOracleIsConstraintNonlinear(SCIP_NLPIORACLE *oracle, int considx)
Definition: nlpioracle.c:1838
#define SEPA_PRIORITY
Definition: sepa_gauge.c:61
SCIP_RETCODE SCIPcreateNlpiProblemFromNlRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **nlpiprob, const char *name, SCIP_NLROW **nlrows, int nnlrows, SCIP_HASHMAP *var2idx, SCIP_HASHMAP *nlrow2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
Definition: scip_nlpi.c:434
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define SCIPsolveNlpi(scip, nlpi,...)
Definition: scip_nlpi.h:199
#define BMSclearMemory(ptr)
Definition: memory.h:122
public methods for the LP relaxation, rows and columns
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1991
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2314
public methods for nonlinear relaxation
SCIP_Real * SCIPnlrowGetLinearCoefs(SCIP_NLROW *nlrow)
Definition: nlp.c:1784
static SCIP_RETCODE generateCut(SCIP *scip, SCIP_SOL *sol, SCIP_NLROW *nlrow, CONVEXSIDE convexside, SCIP_EXPRITER *exprit, SCIP_ROW *row, SCIP_Bool *success)
Definition: sepa_gauge.c:519
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
SCIP_RETCODE SCIPcreateNLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:389
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:158
Position
Definition: sepa_gauge.c:89
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
public methods for solutions
Definition: sepa_gauge.c:83
#define SEPA_FREQ
Definition: sepa_gauge.c:62
public methods for message output
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1421
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1946
#define SCIP_Real
Definition: def.h:177
static SCIP_RETCODE buildConvexCombination(SCIP *scip, SCIP_Real lambda, SCIP_SOL *startpoint, SCIP_SOL *endpoint, SCIP_SOL *convexcomb)
Definition: sepa_gauge.c:411
public methods for message handling
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *tosepasol, SCIP_RESULT *result)
Definition: sepa_gauge.c:627
#define SCIP_INVALID
Definition: def.h:197
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2197
SCIP_RETCODE SCIPprintNlRow(SCIP *scip, SCIP_NLROW *nlrow, FILE *file)
Definition: scip_nlp.c:1547
SCIP_RETCODE SCIPcreateCurrentSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:474
#define SCIPisFinite(x)
Definition: pub_misc.h:1892
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
#define INTERIOROBJVARLB
Definition: sepa_gauge.c:74
ConvexSide
public methods for separators
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition: expriter.c:959
SCIPallocBlockMemory(scip, subsol))
SCIP_Real SCIPnlrowGetConstant(SCIP_NLROW *nlrow)
Definition: nlp.c:1754
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
static SCIP_RETCODE findPointPosition(SCIP *scip, SCIP_NLROW **nlrows, int *nlrowsidx, int nnlrowsidx, CONVEXSIDE *convexsides, SCIP_SOL *point, POSITION *position)
Definition: sepa_gauge.c:334
SCIP_Real SCIPnlrowGetLhs(SCIP_NLROW *nlrow)
Definition: nlp.c:1804
#define SEPA_USESSUBSCIP
Definition: sepa_gauge.c:64
public methods for global and local (sub)problems
static SCIP_RETCODE findBoundaryPoint(SCIP *scip, SCIP_NLROW **nlrows, int *nlrowsidx, int nnlrowsidx, CONVEXSIDE *convexsides, SCIP_SOL *intsol, SCIP_SOL *tosepasol, SCIP_SOL *sol, POSITION *position)
Definition: sepa_gauge.c:458
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
#define VIOLATIONFAC
Definition: sepa_gauge.c:67
enum ConvexSide CONVEXSIDE
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:43
SCIP_EXPR * SCIPnlrowGetExpr(SCIP_NLROW *nlrow)
Definition: nlp.c:1794
#define MAX_ITER
Definition: sepa_gauge.c:68
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
memory allocation routines
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1766