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