Scippy

SCIP

Solving Constraint Integer Programs

heur_multistart.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 heur_multistart.c
17  * @ingroup DEFPLUGINS_HEUR
18  * @brief multistart heuristic for convex and nonconvex MINLPs
19  * @author Benjamin Mueller
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "blockmemshell/memory.h"
25 #include "scip/scip_expr.h"
26 #include "scip/pub_expr.h"
27 #include "scip/heur_multistart.h"
28 #include "scip/heur_subnlp.h"
29 #include "scip/pub_heur.h"
30 #include "scip/pub_message.h"
31 #include "scip/pub_misc.h"
32 #include "scip/pub_misc_sort.h"
33 #include "scip/pub_nlp.h"
34 #include "scip/pub_var.h"
35 #include "scip/scip_general.h"
36 #include "scip/scip_heur.h"
37 #include "scip/scip_mem.h"
38 #include "scip/scip_message.h"
39 #include "scip/scip_nlp.h"
40 #include "scip/scip_nlpi.h"
41 #include "scip/scip_numerics.h"
42 #include "scip/scip_param.h"
43 #include "scip/scip_prob.h"
44 #include "scip/scip_randnumgen.h"
45 #include "scip/scip_sol.h"
46 #include "scip/scip_timing.h"
47 #include <string.h>
48 
49 
50 #define HEUR_NAME "multistart"
51 #define HEUR_DESC "multistart heuristic for convex and nonconvex MINLPs"
52 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
53 #define HEUR_PRIORITY -2100000
54 #define HEUR_FREQ 0
55 #define HEUR_FREQOFS 0
56 #define HEUR_MAXDEPTH -1
57 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
58 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
59 
60 #define DEFAULT_RANDSEED 131 /**< initial random seed */
61 #define DEFAULT_NRNDPOINTS 100 /**< default number of generated random points per call */
62 #define DEFAULT_MAXBOUNDSIZE 2e+4 /**< default maximum variable domain size for unbounded variables */
63 #define DEFAULT_MAXITER 300 /**< default number of iterations to reduce the violation of a point */
64 #define DEFAULT_MINIMPRFAC 0.05 /**< default minimum required improving factor to proceed in improvement of a point */
65 #define DEFAULT_MINIMPRITER 10 /**< default number of iteration when checking the minimum improvement */
66 #define DEFAULT_MAXRELDIST 0.15 /**< default maximum distance between two points in the same cluster */
67 #define DEFAULT_GRADLIMIT 5e+6 /**< default limit for gradient computations for all improvePoint() calls */
68 #define DEFAULT_MAXNCLUSTER 3 /**< default maximum number of considered clusters per heuristic call */
69 #define DEFAULT_ONLYNLPS TRUE /**< should the heuristic run only on continuous problems? */
70 
71 #define MINFEAS -1e+4 /**< minimum feasibility for a point; used for filtering and improving
72  * feasibility */
73 #define MINIMPRFAC 0.95 /**< improvement factor used to discard randomly generated points with a
74  * too large objective value */
75 #define GRADCOSTFAC_LINEAR 1.0 /**< gradient cost factor for the number of linear variables */
76 #define GRADCOSTFAC_NONLINEAR 3.0 /**< gradient cost factor for the number of nodes in nonlinear expression */
77 
78 /*
79  * Data structures
80  */
81 
82 /** primal heuristic data */
83 struct SCIP_HeurData
84 {
85  int nrndpoints; /**< number of random points generated per execution call */
86  SCIP_Real maxboundsize; /**< maximum variable domain size for unbounded variables */
87  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
88  SCIP_HEUR* heursubnlp; /**< sub-NLP heuristic */
89 
90  int maxiter; /**< number of iterations to reduce the maximum violation of a point */
91  SCIP_Real minimprfac; /**< minimum required improving factor to proceed in the improvement of a single point */
92  int minimpriter; /**< number of iteration when checking the minimum improvement */
93 
94  SCIP_Real maxreldist; /**< maximum distance between two points in the same cluster */
95  SCIP_Real gradlimit; /**< limit for gradient computations for all improvePoint() calls (0 for no limit) */
96  int maxncluster; /**< maximum number of considered clusters per heuristic call */
97  SCIP_Bool onlynlps; /**< should the heuristic run only on continuous problems? */
98 };
99 
100 
101 /*
102  * Local methods
103  */
104 
105 
106 /** returns an unique index of a variable in the range of 0,..,SCIPgetNVars(scip)-1 */
107 #ifndef NDEBUG
108 static
109 int getVarIndex(
110  SCIP_HASHMAP* varindex, /**< maps variables to indicies between 0,..,SCIPgetNVars(scip)-1 */
111  SCIP_VAR* var /**< variable */
112  )
113 {
114  assert(varindex != NULL);
115  assert(var != NULL);
116  assert(SCIPhashmapExists(varindex, (void*)var));
117 
118  return SCIPhashmapGetImageInt(varindex, (void*)var);
119 }
120 #else
121 #define getVarIndex(varindex,var) (SCIPhashmapGetImageInt((varindex), (void*)(var)))
122 #endif
123 
124 /** samples and stores random points; stores points which have a better objective value than the current incumbent
125  * solution
126  */
127 static
129  SCIP* scip, /**< SCIP data structure */
130  SCIP_SOL** rndpoints, /**< array to store all random points */
131  int nmaxrndpoints, /**< maximum number of random points to compute */
132  SCIP_Real maxboundsize, /**< maximum variable domain size for unbounded variables */
133  SCIP_RANDNUMGEN* randnumgen, /**< random number generator */
134  SCIP_Real bestobj, /**< objective value in the transformed space of the current incumbent */
135  int* nstored /**< pointer to store the number of randomly generated points */
136  )
137 {
138  SCIP_VAR** vars;
139  SCIP_SOL* sol;
140  SCIP_Real val;
141  SCIP_Real lb;
142  SCIP_Real ub;
143  int nvars;
144  int niter;
145  int i;
146 
147  assert(scip != NULL);
148  assert(rndpoints != NULL);
149  assert(nmaxrndpoints > 0);
150  assert(maxboundsize > 0.0);
151  assert(randnumgen != NULL);
152  assert(nstored != NULL);
153 
154  vars = SCIPgetVars(scip);
155  nvars = SCIPgetNVars(scip);
156  *nstored = 0;
157 
158  SCIP_CALL( SCIPcreateSol(scip, &sol, NULL) );
159 
160  for( niter = 0; niter < 3 * nmaxrndpoints && *nstored < nmaxrndpoints; ++niter )
161  {
162  for( i = 0; i < nvars; ++i )
163  {
164  lb = MIN(SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])); /*lint !e666*/
165  ub = MAX(SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])); /*lint !e666*/
166 
167  if( SCIPisFeasEQ(scip, lb, ub) )
168  val = (lb + ub) / 2.0;
169  /* use a smaller domain for unbounded variables */
170  else if( !SCIPisInfinity(scip, -lb) && !SCIPisInfinity(scip, ub) )
171  val = SCIPrandomGetReal(randnumgen, lb, ub);
172  else if( !SCIPisInfinity(scip, -lb) )
173  val = lb + SCIPrandomGetReal(randnumgen, 0.0, maxboundsize);
174  else if( !SCIPisInfinity(scip, ub) )
175  val = ub - SCIPrandomGetReal(randnumgen, 0.0, maxboundsize);
176  else
177  {
178  assert(SCIPisInfinity(scip, -lb) && SCIPisInfinity(scip, ub));
179  val = SCIPrandomGetReal(randnumgen, -0.5*maxboundsize, 0.5*maxboundsize);
180  }
181  assert(SCIPisFeasGE(scip, val, lb) && SCIPisFeasLE(scip, val, ub));
182 
183  /* set solution value; round the sampled point for integer variables */
184  if( SCIPvarGetType(vars[i]) < SCIP_VARTYPE_CONTINUOUS )
185  val = SCIPfeasRound(scip, val);
186  SCIP_CALL( SCIPsetSolVal(scip, sol, vars[i], val) );
187  }
188 
189  /* add solution if it is good enough */
190  if( SCIPisLE(scip, SCIPgetSolTransObj(scip, sol), bestobj) )
191  {
192  SCIP_CALL( SCIPcreateSolCopy(scip, &rndpoints[*nstored], sol) );
193  ++(*nstored);
194  }
195  }
196  assert(*nstored <= nmaxrndpoints);
197  SCIPdebugMsg(scip, "found %d randomly generated points\n", *nstored);
198 
199  SCIP_CALL( SCIPfreeSol(scip, &sol) );
200 
201  return SCIP_OKAY;
202 }
203 
204 /** computes the minimum feasibility of a given point; a negative value means that there is an infeasibility */
205 static
207  SCIP* scip, /**< SCIP data structure */
208  SCIP_NLROW** nlrows, /**< array containing all nlrows */
209  int nnlrows, /**< total number of nlrows */
210  SCIP_SOL* sol, /**< solution */
211  SCIP_Real* minfeas /**< buffer to store the minimum feasibility */
212  )
213 {
214  SCIP_Real tmp;
215  int i;
216 
217  assert(scip != NULL);
218  assert(sol != NULL);
219  assert(minfeas != NULL);
220  assert(nlrows != NULL);
221  assert(nnlrows > 0);
222 
223  *minfeas = SCIPinfinity(scip);
224 
225  for( i = 0; i < nnlrows; ++i )
226  {
227  assert(nlrows[i] != NULL);
228 
229  SCIP_CALL( SCIPgetNlRowSolFeasibility(scip, nlrows[i], sol, &tmp) );
230  *minfeas = MIN(*minfeas, tmp);
231  }
232 
233  return SCIP_OKAY;
234 }
235 
236 /** computes the gradient for a given point and nonlinear row */
237 static
239  SCIP* scip, /**< SCIP data structure */
240  SCIP_NLROW* nlrow, /**< nonlinear row */
241  SCIP_SOL* sol, /**< solution to compute the gradient for */
242  SCIP_HASHMAP* varindex, /**< maps variables to indicies between 0,..,SCIPgetNVars(scip)-1 uniquely */
243  SCIP_EXPRITER* exprit, /**< expression iterator that can be used */
244  SCIP_Real* grad, /**< buffer to store the gradient; grad[varindex(i)] corresponds to SCIPgetVars(scip)[i] */
245  SCIP_Real* norm /**< buffer to store ||grad||^2 */
246  )
247 {
248  SCIP_EXPR* expr;
249  SCIP_VAR* var;
250  int i;
251 
252  assert(scip != NULL);
253  assert(nlrow != NULL);
254  assert(varindex != NULL);
255  assert(sol != NULL);
256  assert(norm != NULL);
257 
258  BMSclearMemoryArray(grad, SCIPgetNVars(scip));
259  *norm = 0.0;
260 
261  /* linear part */
262  for( i = 0; i < SCIPnlrowGetNLinearVars(nlrow); i++ )
263  {
264  var = SCIPnlrowGetLinearVars(nlrow)[i];
265  assert(var != NULL);
266  assert(getVarIndex(varindex, var) >= 0 && getVarIndex(varindex, var) < SCIPgetNVars(scip));
267 
268  grad[getVarIndex(varindex, var)] += SCIPnlrowGetLinearCoefs(nlrow)[i];
269  }
270 
271  /* expression part */
272  expr = SCIPnlrowGetExpr(nlrow);
273 
274  if( expr != NULL )
275  {
276  assert(exprit != NULL);
277 
278  SCIP_CALL( SCIPevalExprGradient(scip, expr, sol, 0L) );
279 
280  /* TODO: change this when nlrows store the vars */
282  for( ; !SCIPexpriterIsEnd(exprit); expr = SCIPexpriterGetNext(exprit) ) /*lint !e441*/ /*lint !e440*/
283  {
284  if( !SCIPisExprVar(scip, expr) )
285  continue;
286 
287  var = SCIPgetVarExprVar(expr);
288  assert(var != NULL);
289  assert(getVarIndex(varindex, var) >= 0 && getVarIndex(varindex, var) < SCIPgetNVars(scip));
290 
291  grad[getVarIndex(varindex, var)] += SCIPexprGetDerivative(expr);
292  }
293  }
294 
295  /* compute ||grad||^2 */
296  for( i = 0; i < SCIPgetNVars(scip); ++i )
297  *norm += SQR(grad[i]);
298 
299  return SCIP_OKAY;
300 }
301 
302 /** use consensus vectors to improve feasibility for a given starting point */
303 static
305  SCIP* scip, /**< SCIP data structure */
306  SCIP_NLROW** nlrows, /**< array containing all nlrows */
307  int nnlrows, /**< total number of nlrows */
308  SCIP_HASHMAP* varindex, /**< maps variables to indicies between 0,..,SCIPgetNVars(scip)-1 */
309  SCIP_SOL* point, /**< random generated point */
310  int maxiter, /**< maximum number of iterations */
311  SCIP_Real minimprfac, /**< minimum required improving factor to proceed in the improvement of a single point */
312  int minimpriter, /**< number of iteration when checking the minimum improvement */
313  SCIP_Real* minfeas, /**< pointer to store the minimum feasibility */
314  SCIP_Real* nlrowgradcosts, /**< estimated costs for each gradient computation */
315  SCIP_Real* gradcosts /**< pointer to store the estimated gradient costs */
316  )
317 {
318  SCIP_VAR** vars;
319  SCIP_EXPRITER* exprit;
320  SCIP_Real* grad;
321  SCIP_Real* updatevec;
322  SCIP_Real lastminfeas;
323  int nvars;
324  int r;
325  int i;
326 
327  assert(varindex != NULL);
328  assert(point != NULL);
329  assert(maxiter > 0);
330  assert(minfeas != NULL);
331  assert(nlrows != NULL);
332  assert(nnlrows > 0);
333  assert(nlrowgradcosts != NULL);
334  assert(gradcosts != NULL);
335 
336  *gradcosts = 0.0;
337 
338  SCIP_CALL( getMinFeas(scip, nlrows, nnlrows, point, minfeas) );
339 #ifdef SCIP_DEBUG_IMPROVEPOINT
340  printf("start minfeas = %e\n", *minfeas);
341 #endif
342 
343  /* stop since start point is feasible */
344  if( !SCIPisFeasLT(scip, *minfeas, 0.0) )
345  {
346 #ifdef SCIP_DEBUG_IMPROVEPOINT
347  printf("start point is feasible");
348 #endif
349  return SCIP_OKAY;
350  }
351 
352  lastminfeas = *minfeas;
353  vars = SCIPgetVars(scip);
354  nvars = SCIPgetNVars(scip);
355 
356  SCIP_CALL( SCIPallocBufferArray(scip, &grad, nvars) );
357  SCIP_CALL( SCIPallocBufferArray(scip, &updatevec, nvars) );
358  SCIP_CALL( SCIPcreateExpriter(scip, &exprit) );
359 
360  /* main loop */
361  for( r = 0; r < maxiter && SCIPisFeasLT(scip, *minfeas, 0.0); ++r )
362  {
363  SCIP_Real feasibility;
364  SCIP_Real activity;
365  SCIP_Real nlrownorm;
366  SCIP_Real scale;
367  int nviolnlrows;
368 
369  BMSclearMemoryArray(updatevec, nvars);
370  nviolnlrows = 0;
371 
372  for( i = 0; i < nnlrows; ++i )
373  {
374  int j;
375 
376  SCIP_CALL( SCIPgetNlRowSolFeasibility(scip, nlrows[i], point, &feasibility) );
377 
378  /* do not consider non-violated constraints */
379  if( SCIPisFeasGE(scip, feasibility, 0.0) )
380  continue;
381 
382  /* increase number of violated nlrows */
383  ++nviolnlrows;
384 
385  SCIP_CALL( SCIPgetNlRowSolActivity(scip, nlrows[i], point, &activity) );
386  SCIP_CALL( computeGradient(scip, nlrows[i], point, varindex, exprit, grad, &nlrownorm) );
387 
388  /* update estimated costs for computing gradients */
389  *gradcosts += nlrowgradcosts[i];
390 
391  /* stop if the gradient disappears at the current point */
392  if( SCIPisZero(scip, nlrownorm) )
393  {
394 #ifdef SCIP_DEBUG_IMPROVEPOINT
395  printf("gradient vanished at current point -> stop\n");
396 #endif
397  goto TERMINATE;
398  }
399 
400  /* compute -g(x_k) / ||grad(g)(x_k)||^2 for a constraint g(x_k) <= 0 */
401  scale = -feasibility / nlrownorm;
402  if( !SCIPisInfinity(scip, SCIPnlrowGetRhs(nlrows[i])) && SCIPisGT(scip, activity, SCIPnlrowGetRhs(nlrows[i])) )
403  scale *= -1.0;
404 
405  /* skip nonliner row if the scaler is too small or too large */
406  if( SCIPisEQ(scip, scale, 0.0) || SCIPisHugeValue(scip, REALABS(scale)) )
407  continue;
408 
409  for( j = 0; j < nvars; ++j )
410  updatevec[j] += scale * grad[j];
411  }
412 
413  /* if there are no violated rows, stop since start point is feasible */
414  if( nviolnlrows == 0 )
415  {
416  assert(updatevec[i] == 0.0);
417  return SCIP_OKAY;
418  }
419 
420  for( i = 0; i < nvars; ++i )
421  {
422  /* adjust point */
423  updatevec[i] = SCIPgetSolVal(scip, point, vars[i]) + updatevec[i] / nviolnlrows;
424  updatevec[i] = MIN(updatevec[i], SCIPvarGetUbLocal(vars[i])); /*lint !e666*/
425  updatevec[i] = MAX(updatevec[i], SCIPvarGetLbLocal(vars[i])); /*lint !e666*/
426 
427  SCIP_CALL( SCIPsetSolVal(scip, point, vars[i], updatevec[i]) );
428  }
429 
430  /* update feasibility */
431  SCIP_CALL( getMinFeas(scip, nlrows, nnlrows, point, minfeas) );
432 
433  /* check stopping criterion */
434  if( r % minimpriter == 0 && r > 0 )
435  {
436  if( *minfeas <= MINFEAS
437  || (*minfeas-lastminfeas) / MAX(REALABS(*minfeas), REALABS(lastminfeas)) < minimprfac ) /*lint !e666*/
438  break;
439  lastminfeas = *minfeas;
440  }
441  }
442 
443 TERMINATE:
444 #ifdef SCIP_DEBUG_IMPROVEPOINT
445  printf("niter=%d minfeas=%e\n", r, *minfeas);
446 #endif
447 
448  SCIPfreeExpriter(&exprit);
449 
450  SCIPfreeBufferArray(scip, &updatevec);
451  SCIPfreeBufferArray(scip, &grad);
452 
453  return SCIP_OKAY;
454 }
455 
456 /** sorts points w.r.t their feasibilities; points with a feasibility which is too small (w.r.t. the geometric mean of
457  * all feasibilities) will be filtered out
458  */
459 static
461  SCIP* scip, /**< SCIP data structure */
462  SCIP_SOL** points, /**< array containing improved points */
463  SCIP_Real* feasibilities, /**< array containing feasibility for each point (sorted) */
464  int npoints, /**< total number of points */
465  int* nusefulpoints /**< pointer to store the total number of useful points */
466  )
467 {
468  SCIP_Real minfeas;
469  SCIP_Real meanfeas;
470  int i;
471 
472  assert(points != NULL);
473  assert(feasibilities != NULL);
474  assert(npoints > 0);
475  assert(nusefulpoints != NULL);
476 
477  /* sort points w.r.t their feasibilities; non-negative feasibility correspond to feasible points for the NLP */
478  SCIPsortDownRealPtr(feasibilities, (void**)points, npoints);
479  minfeas = feasibilities[npoints - 1];
480 
481  /* check if all points are feasible */
482  if( SCIPisFeasGE(scip, minfeas, 0.0) )
483  {
484  *nusefulpoints = npoints;
485  return SCIP_OKAY;
486  }
487 
488  *nusefulpoints = 0;
489 
490  /* compute shifted geometric mean of feasibilities (shift value = 1 - minfeas) */
491  meanfeas = 1.0;
492  for( i = 0; i < npoints; ++i )
493  {
494  assert(feasibilities[i] - minfeas + 1.0 > 0.0);
495  meanfeas *= pow(feasibilities[i] - minfeas + 1.0, 1.0 / npoints);
496  }
497  meanfeas += minfeas - 1.0;
498  SCIPdebugMsg(scip, "meanfeas = %e\n", meanfeas);
499 
500  /* keep all points with which have a feasibility not much below the geometric mean of infeasibilities */
501  for( i = 0; i < npoints; ++i )
502  {
503  if( SCIPisFeasLT(scip, feasibilities[i], 0.0)
504  && (feasibilities[i] <= 1.05 * meanfeas || SCIPisLE(scip, feasibilities[i], MINFEAS)) )
505  break;
506 
507  ++(*nusefulpoints);
508  }
509 
510  return SCIP_OKAY;
511 }
512 
513 /** returns the relative distance between two points; considers a smaller bounded domain for unbounded variables */
514 static
516  SCIP* scip, /**< SCIP data structure */
517  SCIP_SOL* x, /**< first point */
518  SCIP_SOL* y, /**< second point */
519  SCIP_Real maxboundsize /**< maximum variable domain size for unbounded variables */
520  )
521 {
522  SCIP_VAR** vars;
523  SCIP_Real distance;
524  SCIP_Real solx;
525  SCIP_Real soly;
526  SCIP_Real lb;
527  SCIP_Real ub;
528  int i;
529 
530  assert(x != NULL);
531  assert(y != NULL);
532 
533  vars = SCIPgetVars(scip);
534  distance = 0.0;
535 
536  if( SCIPgetNVars(scip) == 0 )
537  return 0.0;
538 
539  for( i = 0; i < SCIPgetNVars(scip); ++i )
540  {
541  lb = SCIPvarGetLbLocal(vars[i]);
542  ub = SCIPvarGetUbLocal(vars[i]);
543  solx = SCIPgetSolVal(scip, x, vars[i]);
544  soly = SCIPgetSolVal(scip, y, vars[i]);
545 
546  /* adjust lower and upper bounds for unbounded variables*/
547  if( SCIPisInfinity(scip, -lb) && SCIPisInfinity(scip, ub) )
548  {
549  lb = -maxboundsize / 2.0;
550  ub = +maxboundsize / 2.0;
551  }
552  else if( SCIPisInfinity(scip, -lb) )
553  {
554  lb = ub - maxboundsize;
555  }
556  else if( SCIPisInfinity(scip, ub) )
557  {
558  ub = lb + maxboundsize;
559  }
560 
561  /* project solution values to the variable domain */
562  solx = MIN(MAX(solx, lb), ub);
563  soly = MIN(MAX(soly, lb), ub);
564 
565  distance += REALABS(solx - soly) / MAX(1.0, ub - lb);
566  }
567 
568  return distance / SCIPgetNVars(scip);
569 }
570 
571 /** cluster useful points with a greedy algorithm */
572 static
574  SCIP* scip, /**< SCIP data structure */
575  SCIP_SOL** points, /**< array containing improved points */
576  int npoints, /**< total number of points */
577  int* clusteridx, /**< array to store for each point the index of the cluster */
578  int* ncluster, /**< pointer to store the total number of cluster */
579  SCIP_Real maxboundsize, /**< maximum variable domain size for unbounded variables */
580  SCIP_Real maxreldist, /**< maximum relative distance between any two points of the same cluster */
581  int maxncluster /**< maximum number of clusters to compute */
582  )
583 {
584  int i;
585 
586  assert(points != NULL);
587  assert(npoints > 0);
588  assert(clusteridx != NULL);
589  assert(ncluster != NULL);
590  assert(maxreldist >= 0.0);
591  assert(maxncluster >= 0);
592 
593  /* initialize cluster indices */
594  for( i = 0; i < npoints; ++i )
595  clusteridx[i] = INT_MAX;
596 
597  *ncluster = 0;
598 
599  for( i = 0; i < npoints && (*ncluster < maxncluster); ++i )
600  {
601  int j;
602 
603  /* point is already assigned to a cluster */
604  if( clusteridx[i] != INT_MAX )
605  continue;
606 
607  /* create a new cluster for i */
608  clusteridx[i] = *ncluster;
609 
610  for( j = i + 1; j < npoints; ++j )
611  {
612  if( clusteridx[j] == INT_MAX && getRelDistance(scip, points[i], points[j], maxboundsize) <= maxreldist )
613  clusteridx[j] = *ncluster;
614  }
615 
616  ++(*ncluster);
617  }
618 
619 #ifndef NDEBUG
620  for( i = 0; i < npoints; ++i )
621  {
622  assert(clusteridx[i] >= 0);
623  assert(clusteridx[i] < *ncluster || clusteridx[i] == INT_MAX);
624  }
625 #endif
626 
627  return SCIP_OKAY;
628 }
629 
630 /** calls the sub-NLP heuristic for a given cluster */
631 static
633  SCIP* scip, /**< SCIP data structure */
634  SCIP_HEUR* heur, /**< multi-start heuristic */
635  SCIP_HEUR* nlpheur, /**< pointer to NLP local search heuristics */
636  SCIP_SOL** points, /**< array containing improved points */
637  int npoints, /**< total number of points */
638  SCIP_Bool* success /**< pointer to store if we could find a solution */
639  )
640 {
641  SCIP_VAR** vars;
642  SCIP_SOL* refpoint;
643  SCIP_RESULT nlpresult;
644  SCIP_Real val;
645  int nbinvars;
646  int nintvars;
647  int nvars;
648  int i;
649 
650  assert(points != NULL);
651  assert(npoints > 0);
652 
653  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
654  *success = FALSE;
655 
656  SCIP_CALL( SCIPcreateSol(scip, &refpoint, heur) );
657 
658  /* compute reference point */
659  for( i = 0; i < nvars; ++i )
660  {
661  int p;
662 
663  val = 0.0;
664 
665  for( p = 0; p < npoints; ++p )
666  {
667  assert(points[p] != NULL);
668  val += SCIPgetSolVal(scip, points[p], vars[i]);
669  }
670 
671  SCIP_CALL( SCIPsetSolVal(scip, refpoint, vars[i], val / npoints) );
672  }
673 
674  /* round point for sub-NLP heuristic */
675  SCIP_CALL( SCIProundSol(scip, refpoint, success) );
676  SCIPdebugMsg(scip, "rounding of refpoint successfully? %u\n", *success);
677 
678  /* round variables manually if the locks did not allow us to round them */
679  if( !(*success) )
680  {
681  for( i = 0; i < nbinvars + nintvars; ++i )
682  {
683  val = SCIPgetSolVal(scip, refpoint, vars[i]);
684 
685  if( !SCIPisFeasIntegral(scip, val) )
686  {
687  assert(SCIPisFeasIntegral(scip, SCIPvarGetLbLocal(vars[i])));
688  assert(SCIPisFeasIntegral(scip, SCIPvarGetUbLocal(vars[i])));
689 
690  /* round and adjust value */
691  val = SCIPround(scip, val);
692  val = MIN(val, SCIPvarGetUbLocal(vars[i])); /*lint !e666*/
693  val = MAX(val, SCIPvarGetLbLocal(vars[i])); /*lint !e666*/
694  assert(SCIPisFeasIntegral(scip, val));
695 
696  SCIP_CALL( SCIPsetSolVal(scip, refpoint, vars[i], val) );
697  }
698  }
699  }
700 
701  /* call sub-NLP heuristic */
702  SCIP_CALL( SCIPapplyHeurSubNlp(scip, nlpheur, &nlpresult, refpoint, NULL) );
703  SCIP_CALL( SCIPfreeSol(scip, &refpoint) );
704 
705  /* let sub-NLP heuristic decide whether the solution is feasible or not */
706  *success = nlpresult == SCIP_FOUNDSOL;
707 
708  return SCIP_OKAY;
709 }
710 
711 /** recursive helper function to count the number of nodes in a sub-expr */
712 static
713 int getExprSize(
714  SCIP_EXPR* expr /**< expression */
715  )
716 {
717  int sum;
718  int i;
719 
720  assert(expr != NULL);
721 
722  sum = 0;
723  for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
724  {
725  SCIP_EXPR* child = SCIPexprGetChildren(expr)[i];
726  sum += getExprSize(child);
727  }
728  return 1 + sum;
729 }
730 
731 /** main function of the multi-start heuristic (see @ref heur_multistart.h for more details); it consists of the
732  * following four steps:
733  *
734  * 1. sampling points in the current domain; for unbounded variables we use a bounded box
735  *
736  * 2. reduce infeasibility by using a gradient descent method
737  *
738  * 3. cluster points; filter points with a too large infeasibility
739  *
740  * 4. compute start point for each cluster and use it in the sub-NLP heuristic (@ref heur_subnlp.h)
741  */
742 static
744  SCIP* scip, /**< SCIP data structure */
745  SCIP_HEUR* heur, /**< heuristic */
746  SCIP_HEURDATA* heurdata, /**< heuristic data */
747  SCIP_RESULT* result /**< pointer to store the result */
748  )
749 {
750  SCIP_NLROW** nlrows;
751  SCIP_SOL** points;
752  SCIP_HASHMAP* varindex;
753  SCIP_Real* feasibilities;
754  SCIP_Real* nlrowgradcosts;
755  int* clusteridx;
756  SCIP_Real gradlimit;
757  SCIP_Real bestobj;
758  int nusefulpoints;
759  int nrndpoints;
760  int ncluster;
761  int nnlrows;
762  int npoints;
763  int start;
764  int i;
765 
766  assert(scip != NULL);
767  assert(heur != NULL);
768  assert(result != NULL);
769  assert(heurdata != NULL);
770 
771  SCIPdebugMsg(scip, "call applyHeur()\n");
772 
773  nlrows = SCIPgetNLPNlRows(scip);
774  nnlrows = SCIPgetNNLPNlRows(scip);
775  bestobj = SCIPgetNSols(scip) > 0 ? MINIMPRFAC * SCIPgetSolTransObj(scip, SCIPgetBestSol(scip)) : SCIPinfinity(scip);
776 
777  SCIP_CALL( SCIPallocBufferArray(scip, &points, heurdata->nrndpoints) );
778  SCIP_CALL( SCIPallocBufferArray(scip, &nlrowgradcosts, nnlrows) );
779  SCIP_CALL( SCIPallocBufferArray(scip, &feasibilities, heurdata->nrndpoints) );
780  SCIP_CALL( SCIPallocBufferArray(scip, &clusteridx, heurdata->nrndpoints) );
781  SCIP_CALL( SCIPhashmapCreate(&varindex, SCIPblkmem(scip), SCIPgetNVars(scip)) );
782 
783  /* create an unique mapping of all variables to 0,..,SCIPgetNVars(scip)-1 */
784  for( i = 0; i < SCIPgetNVars(scip); ++i )
785  {
786  SCIP_CALL( SCIPhashmapInsertInt(varindex, (void*)SCIPgetVars(scip)[i], i) );
787  }
788 
789  /* compute estimated costs of computing a gradient for each nlrow */
790  for( i = 0; i < nnlrows; ++i )
791  {
792  nlrowgradcosts[i] = GRADCOSTFAC_LINEAR * SCIPnlrowGetNLinearVars(nlrows[i]);
793  if( SCIPnlrowGetExpr(nlrows[i]) != NULL )
794  nlrowgradcosts[i] += GRADCOSTFAC_NONLINEAR * getExprSize(SCIPnlrowGetExpr(nlrows[i]));
795  }
796 
797  /*
798  * 1. sampling points in the current domain; for unbounded variables we use a bounded box
799  */
800  SCIP_CALL( sampleRandomPoints(scip, points, heurdata->nrndpoints, heurdata->maxboundsize, heurdata->randnumgen,
801  bestobj, &nrndpoints) );
802  assert(nrndpoints >= 0);
803 
804  if( nrndpoints == 0 )
805  goto TERMINATE;
806 
807  /*
808  * 2. improve points via consensus vectors
809  */
810  gradlimit = heurdata->gradlimit == 0.0 ? SCIPinfinity(scip) : heurdata->gradlimit;
811  for( npoints = 0; npoints < nrndpoints && gradlimit >= 0 && !SCIPisStopped(scip); ++npoints )
812  {
813  SCIP_Real gradcosts;
814 
815  SCIP_CALL( improvePoint(scip, nlrows, nnlrows, varindex, points[npoints],
816  heurdata->maxiter, heurdata->minimprfac, heurdata->minimpriter, &feasibilities[npoints], nlrowgradcosts,
817  &gradcosts) );
818 
819  gradlimit -= gradcosts;
820  SCIPdebugMsg(scip, "improve point %d / %d gradlimit = %g\n", npoints, nrndpoints, gradlimit);
821  }
822  assert(npoints >= 0 && npoints <= nrndpoints);
823 
824  if( npoints == 0 )
825  goto TERMINATE;
826 
827  /*
828  * 3. filter and cluster points
829  */
830  SCIP_CALL( filterPoints(scip, points, feasibilities, npoints, &nusefulpoints) );
831  assert(nusefulpoints >= 0);
832  SCIPdebugMsg(scip, "nusefulpoints = %d\n", nusefulpoints);
833 
834  if( nusefulpoints == 0 )
835  goto TERMINATE;
836 
837  SCIP_CALL( clusterPointsGreedy(scip, points, nusefulpoints, clusteridx, &ncluster, heurdata->maxboundsize,
838  heurdata->maxreldist, heurdata->maxncluster) );
839  assert(ncluster >= 0 && ncluster <= heurdata->maxncluster);
840  SCIPdebugMsg(scip, "ncluster = %d\n", ncluster);
841 
842  SCIPsortIntPtr(clusteridx, (void**)points, nusefulpoints);
843 
844  /*
845  * 4. compute start point for each cluster and use it in the sub-NLP heuristic (@ref heur_subnlp.h)
846  */
847  start = 0;
848  while( start < nusefulpoints && clusteridx[start] != INT_MAX && !SCIPisStopped(scip) )
849  {
850  SCIP_Bool success;
851  int end;
852 
853  end = start;
854  while( end < nusefulpoints && clusteridx[start] == clusteridx[end] )
855  ++end;
856 
857  assert(end - start > 0);
858 
859  /* call sub-NLP heuristic */
860  SCIP_CALL( solveNLP(scip, heur, heurdata->heursubnlp, &points[start], end - start, &success) );
861  SCIPdebugMsg(scip, "solveNLP result = %u\n", success);
862 
863  if( success )
864  *result = SCIP_FOUNDSOL;
865 
866  /* go to the next cluster */
867  start = end;
868  }
869 
870 TERMINATE:
871  /* free memory */
872  for( i = nrndpoints - 1; i >= 0 ; --i )
873  {
874  assert(points[i] != NULL);
875  SCIP_CALL( SCIPfreeSol(scip, &points[i]) );
876  }
877 
878  SCIPhashmapFree(&varindex);
879  SCIPfreeBufferArray(scip, &clusteridx);
880  SCIPfreeBufferArray(scip, &feasibilities);
881  SCIPfreeBufferArray(scip, &nlrowgradcosts);
882  SCIPfreeBufferArray(scip, &points);
883 
884  return SCIP_OKAY;
885 }
886 
887 /*
888  * Callback methods of primal heuristic
889  */
890 
891 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
892 static
893 SCIP_DECL_HEURCOPY(heurCopyMultistart)
894 { /*lint --e{715}*/
895  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
896 
897  /* call inclusion method of primal heuristic */
899 
900  return SCIP_OKAY;
901 }
902 
903 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
904 static
905 SCIP_DECL_HEURFREE(heurFreeMultistart)
906 { /*lint --e{715}*/
907  SCIP_HEURDATA* heurdata;
908 
909  /* free heuristic data */
910  heurdata = SCIPheurGetData(heur);
911 
912  SCIPfreeBlockMemory(scip, &heurdata);
913  SCIPheurSetData(heur, NULL);
914 
915  return SCIP_OKAY;
916 }
917 
918 /** initialization method of primal heuristic (called after problem was transformed) */
919 static
920 SCIP_DECL_HEURINIT(heurInitMultistart)
921 { /*lint --e{715}*/
922  SCIP_HEURDATA* heurdata;
923 
924  assert( heur != NULL );
925 
926  heurdata = SCIPheurGetData(heur);
927  assert(heurdata != NULL);
928 
929  SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
931 
932  /* try to find sub-NLP heuristic */
933  heurdata->heursubnlp = SCIPfindHeur(scip, "subnlp");
934 
935  return SCIP_OKAY;
936 }
937 
938 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
939 static
940 SCIP_DECL_HEUREXIT(heurExitMultistart)
941 { /*lint --e{715}*/
942  SCIP_HEURDATA* heurdata;
943 
944  assert( heur != NULL );
945 
946  heurdata = SCIPheurGetData(heur);
947  assert(heurdata != NULL);
948  assert(heurdata->randnumgen != NULL);
949 
950  SCIPfreeRandom(scip, &heurdata->randnumgen);
951 
952  return SCIP_OKAY;
953 }
954 
955 /** execution method of primal heuristic */
956 static
957 SCIP_DECL_HEUREXEC(heurExecMultistart)
958 { /*lint --e{715}*/
959  SCIP_HEURDATA* heurdata;
960 
961  assert( heur != NULL );
962 
963  heurdata = SCIPheurGetData(heur);
964  assert(heurdata != NULL);
965 
966  *result = SCIP_DIDNOTRUN;
967 
968  /* check cases for which the heuristic is not applicable */
969  if( !SCIPisNLPConstructed(scip) || heurdata->heursubnlp == NULL || SCIPgetNNlpis(scip) <= 0 )
970  return SCIP_OKAY;
971 
972  /* check whether the heuristic should be applied for a problem containing integer variables */
973  if( heurdata->onlynlps && (SCIPgetNBinVars(scip) > 0 || SCIPgetNIntVars(scip) > 0) )
974  return SCIP_OKAY;
975 
976  *result = SCIP_DIDNOTFIND;
977 
978  SCIP_CALL( applyHeur(scip, heur, heurdata, result) );
979 
980  return SCIP_OKAY;
981 }
982 
983 /*
984  * primal heuristic specific interface methods
985  */
986 
987 /** creates the multistart primal heuristic and includes it in SCIP */
989  SCIP* scip /**< SCIP data structure */
990  )
991 {
992  SCIP_HEURDATA* heurdata;
993  SCIP_HEUR* heur;
994 
995  /* create multistart primal heuristic data */
996  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
997  BMSclearMemory(heurdata);
998 
999  /* include primal heuristic */
1000  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1002  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecMultistart, heurdata) );
1003 
1004  assert(heur != NULL);
1005 
1006  /* set non fundamental callbacks via setter functions */
1007  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyMultistart) );
1008  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeMultistart) );
1009  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitMultistart) );
1010  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitMultistart) );
1011 
1012  /* add multistart primal heuristic parameters */
1013  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nrndpoints",
1014  "number of random points generated per execution call",
1015  &heurdata->nrndpoints, FALSE, DEFAULT_NRNDPOINTS, 0, INT_MAX, NULL, NULL) );
1016 
1017  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxboundsize",
1018  "maximum variable domain size for unbounded variables",
1019  &heurdata->maxboundsize, FALSE, DEFAULT_MAXBOUNDSIZE, 0.0, SCIPinfinity(scip), NULL, NULL) );
1020 
1021  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxiter",
1022  "number of iterations to reduce the maximum violation of a point",
1023  &heurdata->maxiter, FALSE, DEFAULT_MAXITER, 0, INT_MAX, NULL, NULL) );
1024 
1025  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprfac",
1026  "minimum required improving factor to proceed in improvement of a single point",
1027  &heurdata->minimprfac, FALSE, DEFAULT_MINIMPRFAC, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
1028 
1029  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minimpriter",
1030  "number of iteration when checking the minimum improvement",
1031  &heurdata->minimpriter, FALSE, DEFAULT_MINIMPRITER, 1, INT_MAX, NULL, NULL) );
1032 
1033  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxreldist",
1034  "maximum distance between two points in the same cluster",
1035  &heurdata->maxreldist, FALSE, DEFAULT_MAXRELDIST, 0.0, SCIPinfinity(scip), NULL, NULL) );
1036 
1037  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/gradlimit",
1038  "limit for gradient computations for all improvePoint() calls (0 for no limit)",
1039  &heurdata->gradlimit, FALSE, DEFAULT_GRADLIMIT, 0.0, SCIPinfinity(scip), NULL, NULL) );
1040 
1041  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxncluster",
1042  "maximum number of considered clusters per heuristic call",
1043  &heurdata->maxncluster, FALSE, DEFAULT_MAXNCLUSTER, 0, INT_MAX, NULL, NULL) );
1044 
1045  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlynlps",
1046  "should the heuristic run only on continuous problems?",
1047  &heurdata->onlynlps, FALSE, DEFAULT_ONLYNLPS, NULL, NULL) );
1048 
1049  return SCIP_OKAY;
1050 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2081
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
#define MINFEAS
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:101
#define HEUR_NAME
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
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3798
#define HEUR_TIMING
static int getVarIndex(SCIP_HASHMAP *varindex, SCIP_VAR *var)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
public methods for timing
void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
#define DEFAULT_MAXNCLUSTER
SCIP_Real SCIPfeasRound(SCIP *scip, SCIP_Real val)
SCIP_VAR ** SCIPnlrowGetLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:1774
static SCIP_DECL_HEURINIT(heurInitMultistart)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1865
#define DEFAULT_MAXBOUNDSIZE
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
SCIP_RETCODE SCIPapplyHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *refpoint, SCIP_SOL *resultsol)
Definition: heur_subnlp.c:1757
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
SCIP_Real SCIPnlrowGetRhs(SCIP_NLROW *nlrow)
Definition: nlp.c:1814
static SCIP_DECL_HEUREXEC(heurExecMultistart)
int SCIPnlrowGetNLinearVars(SCIP_NLROW *nlrow)
Definition: nlp.c:1764
#define HEUR_USESSUBSCIP
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
public methods for problem variables
static SCIP_RETCODE improvePoint(SCIP *scip, SCIP_NLROW **nlrows, int nnlrows, SCIP_HASHMAP *varindex, SCIP_SOL *point, int maxiter, SCIP_Real minimprfac, int minimpriter, SCIP_Real *minfeas, SCIP_Real *nlrowgradcosts, SCIP_Real *gradcosts)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
SCIP_RETCODE SCIPgetNlRowSolActivity(SCIP *scip, SCIP_NLROW *nlrow, SCIP_SOL *sol, SCIP_Real *activity)
Definition: scip_nlp.c:1454
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE getMinFeas(SCIP *scip, SCIP_NLROW **nlrows, int nnlrows, SCIP_SOL *sol, SCIP_Real *minfeas)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
static SCIP_DECL_HEURCOPY(heurCopyMultistart)
#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
SCIP_VAR ** x
Definition: circlepacking.c:54
SCIP_RETCODE SCIPevalExprGradient(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: scip_expr.c:1656
public methods for numerical tolerances
public functions to work with algebraic expressions
static SCIP_DECL_HEURFREE(heurFreeMultistart)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
static SCIP_RETCODE solveNLP(SCIP *scip, SCIP_HEUR *heur, SCIP_HEUR *nlpheur, SCIP_SOL **points, int npoints, SCIP_Bool *success)
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
int SCIPgetNNlpis(SCIP *scip)
Definition: scip_nlpi.c:190
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3808
public methods for NLPI solver interfaces
#define DEFAULT_RANDSEED
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:609
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:249
#define MINIMPRFAC
#define DEFAULT_NRNDPOINTS
SCIP_Real SCIPexprGetDerivative(SCIP_EXPR *expr)
Definition: expr.c:3898
#define DEFAULT_MINIMPRFAC
static SCIP_RETCODE applyHeur(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
#define DEFAULT_MAXITER
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition: expr_var.c:407
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
public functions to work with algebraic expressions
#define HEUR_FREQOFS
#define DEFAULT_ONLYNLPS
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1482
static int getExprSize(SCIP_EXPR *expr)
#define REALABS(x)
Definition: def.h:201
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:310
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define GRADCOSTFAC_LINEAR
static SCIP_DECL_HEUREXIT(heurExitMultistart)
#define GRADCOSTFAC_NONLINEAR
public methods for primal heuristic plugins and divesets
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2300
public methods for NLP management
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE filterPoints(SCIP *scip, SCIP_SOL **points, SCIP_Real *feasibilities, int npoints, int *nusefulpoints)
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
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
#define SCIP_Bool
Definition: def.h:84
#define HEUR_MAXDEPTH
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2446
#define MAX(x, y)
Definition: tclique_def.h:83
#define DEFAULT_MINIMPRITER
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
static SCIP_RETCODE sampleRandomPoints(SCIP *scip, SCIP_SOL **rndpoints, int nmaxrndpoints, SCIP_Real maxboundsize, SCIP_RANDNUMGEN *randnumgen, SCIP_Real bestobj, int *nstored)
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:848
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define BMSclearMemory(ptr)
Definition: memory.h:122
#define HEUR_DISPCHAR
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2036
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10025
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1991
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2314
public methods for nonlinear relaxation
#define HEUR_FREQ
SCIP_Real * SCIPnlrowGetLinearCoefs(SCIP_NLROW *nlrow)
Definition: nlp.c:1784
SCIP_Real * r
Definition: circlepacking.c:50
methods for sorting joint arrays of various types
general public methods
static SCIP_Real getRelDistance(SCIP *scip, SCIP_SOL *x, SCIP_SOL *y, SCIP_Real maxboundsize)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetNlRowSolFeasibility(SCIP *scip, SCIP_NLROW *nlrow, SCIP_SOL *sol, SCIP_Real *feasibility)
Definition: scip_nlp.c:1488
public methods for solutions
public methods for random numbers
public methods for message output
NLP local search primal heuristic using sub-SCIPs.
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
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
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
SCIP_VAR ** y
Definition: circlepacking.c:55
#define HEUR_DESC
public methods for message handling
#define DEFAULT_GRADLIMIT
static SCIP_RETCODE computeGradient(SCIP *scip, SCIP_NLROW *nlrow, SCIP_SOL *sol, SCIP_HASHMAP *varindex, SCIP_EXPRITER *exprit, SCIP_Real *grad, SCIP_Real *norm)
static SCIP_RETCODE clusterPointsGreedy(SCIP *scip, SCIP_SOL **points, int npoints, int *clusteridx, int *ncluster, SCIP_Real maxboundsize, SCIP_Real maxreldist, int maxncluster)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPincludeHeurMultistart(SCIP *scip)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
public methods for primal heuristics
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition: expriter.c:959
SCIPallocBlockMemory(scip, subsol))
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
#define DEFAULT_MAXRELDIST
public methods for global and local (sub)problems
SCIP_Real SCIPround(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
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_param.c:130
#define HEUR_PRIORITY
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
SCIP_EXPR * SCIPnlrowGetExpr(SCIP_NLROW *nlrow)
Definition: nlp.c:1794
multistart heuristic for convex and nonconvex MINLPs
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
memory allocation routines