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