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