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  assert(nviolnlrows > 0);
451 
452  for( i = 0; i < nvars; ++i )
453  {
454  /* adjust point */
455  updatevec[i] = SCIPgetSolVal(scip, point, vars[i]) + updatevec[i] / nviolnlrows;
456  updatevec[i] = MIN(updatevec[i], SCIPvarGetUbLocal(vars[i])); /*lint !e666*/
457  updatevec[i] = MAX(updatevec[i], SCIPvarGetLbLocal(vars[i])); /*lint !e666*/
458 
459  SCIP_CALL( SCIPsetSolVal(scip, point, vars[i], updatevec[i]) );
460  }
461 
462  /* update feasibility */
463  SCIP_CALL( getMinFeas(scip, nlrows, nnlrows, point, minfeas) );
464 
465  /* check stopping criterion */
466  if( r % minimpriter == 0 && r > 0 )
467  {
468  if( *minfeas <= MINFEAS
469  || (*minfeas-lastminfeas) / MAX(REALABS(*minfeas), REALABS(lastminfeas)) < minimprfac ) /*lint !e666*/
470  break;
471  lastminfeas = *minfeas;
472  }
473  }
474 
475 TERMINATE:
476 #ifdef SCIP_DEBUG_IMPROVEPOINT
477  printf("niter=%d minfeas=%e\n", r, *minfeas);
478 #endif
479 
480  SCIPfreeBufferArray(scip, &updatevec);
481  SCIPfreeBufferArray(scip, &grad);
482 
483  return SCIP_OKAY;
484 }
485 
486 /** sorts points w.r.t their feasibilities; points with a feasibility which is too small (w.r.t. the geometric mean of
487  * all feasibilities) will be filtered out
488  */
489 static
491  SCIP* scip, /**< SCIP data structure */
492  SCIP_SOL** points, /**< array containing improved points */
493  SCIP_Real* feasibilities, /**< array containing feasibility for each point (sorted) */
494  int npoints, /**< total number of points */
495  int* nusefulpoints /**< pointer to store the total number of useful points */
496  )
497 {
498  SCIP_Real minfeas;
499  SCIP_Real meanfeas;
500  int i;
501 
502  assert(points != NULL);
503  assert(feasibilities != NULL);
504  assert(npoints > 0);
505  assert(nusefulpoints != NULL);
506 
507  /* sort points w.r.t their feasibilities; non-negative feasibility correspond to feasible points for the NLP */
508  SCIPsortDownRealPtr(feasibilities, (void**)points, npoints);
509  minfeas = feasibilities[npoints - 1];
510 
511  /* check if all points are feasible */
512  if( SCIPisFeasGE(scip, minfeas, 0.0) )
513  {
514  *nusefulpoints = npoints;
515  return SCIP_OKAY;
516  }
517 
518  *nusefulpoints = 0;
519 
520  /* compute shifted geometric mean of feasibilities (shift value = 1 - minfeas) */
521  meanfeas = 1.0;
522  for( i = 0; i < npoints; ++i )
523  {
524  assert(feasibilities[i] - minfeas + 1.0 > 0.0);
525  meanfeas *= pow(feasibilities[i] - minfeas + 1.0, 1.0 / npoints);
526  }
527  meanfeas += minfeas - 1.0;
528  SCIPdebugMsg(scip, "meanfeas = %e\n", meanfeas);
529 
530  /* keep all points with which have a feasibility not much below the geometric mean of infeasibilities */
531  for( i = 0; i < npoints; ++i )
532  {
533  if( SCIPisFeasLT(scip, feasibilities[i], 0.0)
534  && (feasibilities[i] <= 1.05 * meanfeas || SCIPisLE(scip, feasibilities[i], MINFEAS)) )
535  break;
536 
537  ++(*nusefulpoints);
538  }
539 
540  return SCIP_OKAY;
541 }
542 
543 /** returns the relative distance between two points; considers a smaller bounded domain for unbounded variables */
544 static
546  SCIP* scip, /**< SCIP data structure */
547  SCIP_SOL* x, /**< first point */
548  SCIP_SOL* y, /**< second point */
549  SCIP_Real maxboundsize /**< maximum variable domain size for unbounded variables */
550  )
551 {
552  SCIP_VAR** vars;
553  SCIP_Real distance;
554  SCIP_Real solx;
555  SCIP_Real soly;
556  SCIP_Real lb;
557  SCIP_Real ub;
558  int i;
559 
560  assert(x != NULL);
561  assert(y != NULL);
562  assert(SCIPgetNVars(scip) > 0);
563 
564  vars = SCIPgetVars(scip);
565  distance = 0.0;
566 
567  for( i = 0; i < SCIPgetNVars(scip); ++i )
568  {
569  lb = SCIPvarGetLbLocal(vars[i]);
570  ub = SCIPvarGetUbLocal(vars[i]);
571  solx = SCIPgetSolVal(scip, x, vars[i]);
572  soly = SCIPgetSolVal(scip, y, vars[i]);
573 
574  /* adjust lower and upper bounds for unbounded variables*/
575  if( SCIPisInfinity(scip, -lb) && SCIPisInfinity(scip, ub) )
576  {
577  lb = -maxboundsize / 2.0;
578  ub = +maxboundsize / 2.0;
579  }
580  else if( SCIPisInfinity(scip, -lb) )
581  {
582  lb = ub - maxboundsize;
583  }
584  else if( SCIPisInfinity(scip, ub) )
585  {
586  ub = lb + maxboundsize;
587  }
588 
589  /* project solution values to the variable domain */
590  solx = MIN(MAX(solx, lb), ub);
591  soly = MIN(MAX(soly, lb), ub);
592 
593  distance += REALABS(solx - soly) / MAX(1.0, ub - lb);
594  }
595 
596  return distance / SCIPgetNVars(scip);
597 }
598 
599 /** cluster useful points with a greedy algorithm */
600 static
602  SCIP* scip, /**< SCIP data structure */
603  SCIP_SOL** points, /**< array containing improved points */
604  int npoints, /**< total number of points */
605  int* clusteridx, /**< array to store for each point the index of the cluster */
606  int* ncluster, /**< pointer to store the total number of cluster */
607  SCIP_Real maxboundsize, /**< maximum variable domain size for unbounded variables */
608  SCIP_Real maxreldist, /**< maximum relative distance between any two points of the same cluster */
609  int maxncluster /**< maximum number of clusters to compute */
610  )
611 {
612  int i;
613 
614  assert(points != NULL);
615  assert(npoints > 0);
616  assert(clusteridx != NULL);
617  assert(ncluster != NULL);
618  assert(maxreldist >= 0.0);
619  assert(maxncluster >= 0);
620 
621  /* initialize cluster indices */
622  for( i = 0; i < npoints; ++i )
623  clusteridx[i] = INT_MAX;
624 
625  *ncluster = 0;
626 
627  for( i = 0; i < npoints && (*ncluster < maxncluster); ++i )
628  {
629  int j;
630 
631  /* point is already assigned to a cluster */
632  if( clusteridx[i] != INT_MAX )
633  continue;
634 
635  /* create a new cluster for i */
636  clusteridx[i] = *ncluster;
637 
638  for( j = i + 1; j < npoints; ++j )
639  {
640  if( clusteridx[j] == INT_MAX && getRelDistance(scip, points[i], points[j], maxboundsize) <= maxreldist )
641  clusteridx[j] = *ncluster;
642  }
643 
644  ++(*ncluster);
645  }
646 
647 #ifndef NDEBUG
648  for( i = 0; i < npoints; ++i )
649  {
650  assert(clusteridx[i] >= 0);
651  assert(clusteridx[i] < *ncluster || clusteridx[i] == INT_MAX);
652  }
653 #endif
654 
655  return SCIP_OKAY;
656 }
657 
658 /** calls the sub-NLP heuristic for a given cluster */
659 static
661  SCIP* scip, /**< SCIP data structure */
662  SCIP_HEUR* heur, /**< multi-start heuristic */
663  SCIP_HEUR* nlpheur, /**< pointer to NLP local search heuristics */
664  SCIP_SOL** points, /**< array containing improved points */
665  int npoints, /**< total number of points */
666  SCIP_Longint itercontingent, /**< iteration limit for NLP solver */
667  SCIP_Real timelimit, /**< time limit for NLP solver */
668  SCIP_Real minimprove, /**< desired minimal relative improvement in objective function value */
669  SCIP_Bool* success /**< pointer to store if we could find a solution */
670  )
671 {
672  SCIP_VAR** vars;
673  SCIP_SOL* refpoint;
674  SCIP_RESULT nlpresult;
675  SCIP_Real val;
676  int nbinvars;
677  int nintvars;
678  int nvars;
679  int i;
680 
681  assert(points != NULL);
682  assert(npoints > 0);
683 
684  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
685  *success = FALSE;
686 
687  SCIP_CALL( SCIPcreateSol(scip, &refpoint, heur) );
688 
689  /* compute reference point */
690  for( i = 0; i < nvars; ++i )
691  {
692  int p;
693 
694  val = 0.0;
695 
696  for( p = 0; p < npoints; ++p )
697  {
698  assert(points[p] != NULL);
699  val += SCIPgetSolVal(scip, points[p], vars[i]);
700  }
701 
702  SCIP_CALL( SCIPsetSolVal(scip, refpoint, vars[i], val / npoints) );
703  }
704 
705  /* round point for sub-NLP heuristic */
706  SCIP_CALL( SCIProundSol(scip, refpoint, success) );
707  SCIPdebugMsg(scip, "rounding of refpoint successfully? %u\n", *success);
708 
709  /* round variables manually if the locks did not allow us to round them */
710  if( !(*success) )
711  {
712  for( i = 0; i < nbinvars + nintvars; ++i )
713  {
714  val = SCIPgetSolVal(scip, refpoint, vars[i]);
715 
716  if( !SCIPisFeasIntegral(scip, val) )
717  {
718  assert(SCIPisFeasIntegral(scip, SCIPvarGetLbLocal(vars[i])));
719  assert(SCIPisFeasIntegral(scip, SCIPvarGetUbLocal(vars[i])));
720 
721  /* round and adjust value */
722  val = SCIPround(scip, val);
723  val = MIN(val, SCIPvarGetUbLocal(vars[i])); /*lint !e666*/
724  val = MAX(val, SCIPvarGetLbLocal(vars[i])); /*lint !e666*/
725  assert(SCIPisFeasIntegral(scip, val));
726 
727  SCIP_CALL( SCIPsetSolVal(scip, refpoint, vars[i], val) );
728  }
729  }
730  }
731 
732  /* call sub-NLP heuristic */
733  SCIP_CALL( SCIPapplyHeurSubNlp(scip, nlpheur, &nlpresult, refpoint, itercontingent, timelimit, minimprove,
734  NULL, NULL) );
735  SCIP_CALL( SCIPfreeSol(scip, &refpoint) );
736 
737  /* let sub-NLP heuristic decide whether the solution is feasible or not */
738  *success = nlpresult == SCIP_FOUNDSOL;
739 
740  return SCIP_OKAY;
741 }
742 
743 /** recursive helper function to count the number of nodes in a sub-tree */
744 static
745 int getExprSize(
746  SCIP_EXPR* expr /**< expression */
747  )
748 {
749  int sum;
750  int i;
751 
752  assert(expr != NULL);
753 
754  sum = 0;
755  for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
756  {
757  SCIP_EXPR* child = SCIPexprGetChildren(expr)[i];
758  sum += getExprSize(child);
759  }
760  return 1 + sum;
761 }
762 
763 /** returns the number of nodes in an expression tree */
764 static
765 int getExprtreeSize(
766  SCIP_EXPRTREE* tree /**< expression tree */
767  )
768 {
769  if( tree == NULL )
770  return 0;
771  return getExprSize(SCIPexprtreeGetRoot(tree));
772 }
773 
774 /** main function of the multi-start heuristic (see @ref heur_multistart.h for more details); it consists of the
775  * following four steps:
776  *
777  * 1. sampling points in the current domain; for unbounded variables we use a bounded box
778  *
779  * 2. reduce infeasibility by using a gradient descent method
780  *
781  * 3. cluster points; filter points with a too large infeasibility
782  *
783  * 4. compute start point for each cluster and use it in the sub-NLP heuristic (@ref heur_subnlp.h)
784  */
785 static
787  SCIP* scip, /**< SCIP data structure */
788  SCIP_HEUR* heur, /**< heuristic */
789  SCIP_HEURDATA* heurdata, /**< heuristic data */
790  SCIP_RESULT* result /**< pointer to store the result */
791  )
792 {
793  SCIP_NLROW** nlrows;
794  SCIP_SOL** points;
795  SCIP_HASHMAP* varindex;
796  SCIP_Real* feasibilities;
797  SCIP_Real* nlrowgradcosts;
798  int* clusteridx;
799  SCIP_Real gradlimit;
800  SCIP_Real bestobj;
801  int nusefulpoints;
802  int nrndpoints;
803  int ncluster;
804  int nnlrows;
805  int npoints;
806  int start;
807  int i;
808 
809  assert(scip != NULL);
810  assert(heur != NULL);
811  assert(result != NULL);
812  assert(heurdata != NULL);
813 
814  SCIPdebugMsg(scip, "call applyHeur()\n");
815 
816  nlrows = SCIPgetNLPNlRows(scip);
817  nnlrows = SCIPgetNNLPNlRows(scip);
818  bestobj = SCIPgetNSols(scip) > 0 ? MINIMPRFAC * SCIPgetSolTransObj(scip, SCIPgetBestSol(scip)) : SCIPinfinity(scip);
819 
820  if( heurdata->exprinterpreter == NULL )
821  {
822  SCIP_CALL( SCIPexprintCreate(SCIPblkmem(scip), &heurdata->exprinterpreter) );
823  }
824 
825  SCIP_CALL( SCIPallocBufferArray(scip, &points, heurdata->nrndpoints) );
826  SCIP_CALL( SCIPallocBufferArray(scip, &nlrowgradcosts, nnlrows) );
827  SCIP_CALL( SCIPallocBufferArray(scip, &feasibilities, heurdata->nrndpoints) );
828  SCIP_CALL( SCIPallocBufferArray(scip, &clusteridx, heurdata->nrndpoints) );
829  SCIP_CALL( SCIPhashmapCreate(&varindex, SCIPblkmem(scip), SCIPgetNVars(scip)) );
830 
831  /* create an unique mapping of all variables to 0,..,SCIPgetNVars(scip)-1 */
832  for( i = 0; i < SCIPgetNVars(scip); ++i )
833  {
834  SCIP_CALL( SCIPhashmapInsertInt(varindex, (void*)SCIPgetVars(scip)[i], i) );
835  }
836 
837  /* compute estimated costs of computing a gradient for each nlrow */
838  for( i = 0; i < nnlrows; ++i )
839  {
840  nlrowgradcosts[i] = GRADCOSTFAC_LINEAR * SCIPnlrowGetNLinearVars(nlrows[i])
843  }
844 
845  /*
846  * 1. sampling points in the current domain; for unbounded variables we use a bounded box
847  */
848  SCIP_CALL( sampleRandomPoints(scip, points, heurdata->nrndpoints, heurdata->maxboundsize, heurdata->randnumgen,
849  bestobj, &nrndpoints) );
850  assert(nrndpoints >= 0);
851 
852  if( nrndpoints == 0 )
853  goto TERMINATE;
854 
855  /*
856  * 2. improve points via consensus vectors
857  */
858  gradlimit = heurdata->gradlimit == 0.0 ? SCIPinfinity(scip) : heurdata->gradlimit;
859  for( npoints = 0; npoints < nrndpoints && gradlimit >= 0 && !SCIPisStopped(scip); ++npoints )
860  {
861  SCIP_Real gradcosts;
862 
863  SCIP_CALL( improvePoint(scip, nlrows, nnlrows, varindex, heurdata->exprinterpreter, points[npoints],
864  heurdata->maxiter, heurdata->minimprfac, heurdata->minimpriter, &feasibilities[npoints], nlrowgradcosts,
865  &gradcosts) );
866 
867  gradlimit -= gradcosts;
868  SCIPdebugMsg(scip, "improve point %d / %d gradlimit = %g\n", npoints, nrndpoints, gradlimit);
869  }
870  assert(npoints >= 0 && npoints <= nrndpoints);
871 
872  if( npoints == 0 )
873  goto TERMINATE;
874 
875  /*
876  * 3. filter and cluster points
877  */
878  SCIP_CALL( filterPoints(scip, points, feasibilities, npoints, &nusefulpoints) );
879  assert(nusefulpoints >= 0);
880  SCIPdebugMsg(scip, "nusefulpoints = %d\n", nusefulpoints);
881 
882  if( nusefulpoints == 0 )
883  goto TERMINATE;
884 
885  SCIP_CALL( clusterPointsGreedy(scip, points, nusefulpoints, clusteridx, &ncluster, heurdata->maxboundsize,
886  heurdata->maxreldist, heurdata->maxncluster) );
887  assert(ncluster >= 0 && ncluster <= heurdata->maxncluster);
888  SCIPdebugMsg(scip, "ncluster = %d\n", ncluster);
889 
890  SCIPsortIntPtr(clusteridx, (void**)points, nusefulpoints);
891 
892  /*
893  * 4. compute start point for each cluster and use it in the sub-NLP heuristic (@ref heur_subnlp.h)
894  */
895  start = 0;
896  while( start < nusefulpoints && clusteridx[start] != INT_MAX && !SCIPisStopped(scip) )
897  {
898  SCIP_Real timelimit;
899  SCIP_Bool success;
900  int end;
901 
902  end = start;
903  while( end < nusefulpoints && clusteridx[start] == clusteridx[end] )
904  ++end;
905 
906  assert(end - start > 0);
907 
908  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
909  if( !SCIPisInfinity(scip, timelimit) )
910  timelimit -= SCIPgetSolvingTime(scip);
911 
912  /* try to solve sub-NLP if we have enough time left */
913  if( timelimit <= 1.0 )
914  {
915  SCIPdebugMsg(scip, "not enough time left! (%g)\n", timelimit);
916  break;
917  }
918 
919  /* call sub-NLP heuristic */
920  SCIP_CALL( solveNLP(scip, heur, heurdata->heursubnlp, &points[start], end - start, -1LL, timelimit,
921  heurdata->nlpminimpr, &success) );
922  SCIPdebugMsg(scip, "solveNLP result = %d\n", success);
923 
924  if( success )
925  *result = SCIP_FOUNDSOL;
926 
927  /* go to the next cluster */
928  start = end;
929  }
930 
931 TERMINATE:
932  /* free memory */
933  for( i = nrndpoints - 1; i >= 0 ; --i )
934  {
935  assert(points[i] != NULL);
936  SCIP_CALL( SCIPfreeSol(scip, &points[i]) );
937  }
938 
939  SCIPhashmapFree(&varindex);
940  SCIPfreeBufferArray(scip, &clusteridx);
941  SCIPfreeBufferArray(scip, &feasibilities);
942  SCIPfreeBufferArray(scip, &nlrowgradcosts);
943  SCIPfreeBufferArray(scip, &points);
944 
945  return SCIP_OKAY;
946 }
947 
948 /*
949  * Callback methods of primal heuristic
950  */
951 
952 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
953 static
954 SCIP_DECL_HEURCOPY(heurCopyMultistart)
955 { /*lint --e{715}*/
956  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
957 
958  /* call inclusion method of primal heuristic */
960 
961  return SCIP_OKAY;
962 }
963 
964 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
965 static
966 SCIP_DECL_HEURFREE(heurFreeMultistart)
967 { /*lint --e{715}*/
968  SCIP_HEURDATA* heurdata;
969 
970  /* free heuristic data */
971  heurdata = SCIPheurGetData(heur);
972 
973  if( heurdata->exprinterpreter != NULL )
974  {
975  SCIP_CALL( SCIPexprintFree(&heurdata->exprinterpreter) );
976  }
977 
978  SCIPfreeBlockMemory(scip, &heurdata);
979  SCIPheurSetData(heur, NULL);
980 
981  return SCIP_OKAY;
982 }
983 
984 /** initialization method of primal heuristic (called after problem was transformed) */
985 static
986 SCIP_DECL_HEURINIT(heurInitMultistart)
987 { /*lint --e{715}*/
988  SCIP_HEURDATA* heurdata;
989 
990  assert( heur != NULL );
991 
992  heurdata = SCIPheurGetData(heur);
993  assert(heurdata != NULL);
994 
995  SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
997 
998  /* try to find sub-NLP heuristic */
999  heurdata->heursubnlp = SCIPfindHeur(scip, "subnlp");
1000 
1001  return SCIP_OKAY;
1002 }
1003 
1004 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
1005 static
1006 SCIP_DECL_HEUREXIT(heurExitMultistart)
1007 { /*lint --e{715}*/
1008  SCIP_HEURDATA* heurdata;
1009 
1010  assert( heur != NULL );
1011 
1012  heurdata = SCIPheurGetData(heur);
1013  assert(heurdata != NULL);
1014  assert(heurdata->randnumgen != NULL);
1015 
1016  SCIPfreeRandom(scip, &heurdata->randnumgen);
1017 
1018  return SCIP_OKAY;
1019 }
1020 
1021 /** execution method of primal heuristic */
1022 static
1023 SCIP_DECL_HEUREXEC(heurExecMultistart)
1024 { /*lint --e{715}*/
1025  SCIP_HEURDATA* heurdata;
1026 
1027  assert( heur != NULL );
1028 
1029  heurdata = SCIPheurGetData(heur);
1030  assert(heurdata != NULL);
1031 
1032  *result = SCIP_DIDNOTRUN;
1033 
1034  /* check cases for which the heuristic is not applicable */
1035  if( !SCIPisNLPConstructed(scip) || heurdata->heursubnlp == NULL || SCIPgetNNlpis(scip) <= 0 )
1036  return SCIP_OKAY;
1037 
1038  /* check whether the heuristic should be applied for a problem containing integer variables */
1039  if( heurdata->onlynlps && (SCIPgetNBinVars(scip) > 0 || SCIPgetNIntVars(scip) > 0) )
1040  return SCIP_OKAY;
1041 
1042  *result = SCIP_DIDNOTFIND;
1043 
1044  SCIP_CALL( applyHeur(scip, heur, heurdata, result) );
1045 
1046  return SCIP_OKAY;
1047 }
1048 
1049 /*
1050  * primal heuristic specific interface methods
1051  */
1052 
1053 /** creates the multistart primal heuristic and includes it in SCIP */
1055  SCIP* scip /**< SCIP data structure */
1056  )
1057 {
1058  SCIP_HEURDATA* heurdata;
1059  SCIP_HEUR* heur;
1060 
1061  /* create multistart primal heuristic data */
1062  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1063  BMSclearMemory(heurdata);
1064 
1065  /* include primal heuristic */
1066  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1068  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecMultistart, heurdata) );
1069 
1070  assert(heur != NULL);
1071 
1072  /* set non fundamental callbacks via setter functions */
1073  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyMultistart) );
1074  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeMultistart) );
1075  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitMultistart) );
1076  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitMultistart) );
1077 
1078  /* add multistart primal heuristic parameters */
1079  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nrndpoints",
1080  "number of random points generated per execution call",
1081  &heurdata->nrndpoints, FALSE, DEFAULT_NRNDPOINTS, 0, INT_MAX, NULL, NULL) );
1082 
1083  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxboundsize",
1084  "maximum variable domain size for unbounded variables",
1085  &heurdata->maxboundsize, FALSE, DEFAULT_MAXBOUNDSIZE, 0.0, SCIPinfinity(scip), NULL, NULL) );
1086 
1087  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxiter",
1088  "number of iterations to reduce the maximum violation of a point",
1089  &heurdata->maxiter, FALSE, DEFAULT_MAXITER, 0, INT_MAX, NULL, NULL) );
1090 
1091  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprfac",
1092  "minimum required improving factor to proceed in improvement of a single point",
1093  &heurdata->minimprfac, FALSE, DEFAULT_MINIMPRFAC, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
1094 
1095  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minimpriter",
1096  "number of iteration when checking the minimum improvement",
1097  &heurdata->minimpriter, FALSE, DEFAULT_MINIMPRITER, 1, INT_MAX, NULL, NULL) );
1098 
1099  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxreldist",
1100  "maximum distance between two points in the same cluster",
1101  &heurdata->maxreldist, FALSE, DEFAULT_MAXRELDIST, 0.0, SCIPinfinity(scip), NULL, NULL) );
1102 
1103  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nlpminimpr",
1104  "factor by which heuristic should at least improve the incumbent",
1105  &heurdata->nlpminimpr, FALSE, DEFAULT_NLPMINIMPR, 0.0, SCIPinfinity(scip), NULL, NULL) );
1106 
1107  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/gradlimit",
1108  "limit for gradient computations for all improvePoint() calls (0 for no limit)",
1109  &heurdata->gradlimit, FALSE, DEFAULT_GRADLIMIT, 0.0, SCIPinfinity(scip), NULL, NULL) );
1110 
1111  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxncluster",
1112  "maximum number of considered clusters per heuristic call",
1113  &heurdata->maxncluster, FALSE, DEFAULT_MAXNCLUSTER, 0, INT_MAX, NULL, NULL) );
1114 
1115  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlynlps",
1116  "should the heuristic run only on continuous problems?",
1117  &heurdata->onlynlps, FALSE, DEFAULT_ONLYNLPS, NULL, NULL) );
1118 
1119  return SCIP_OKAY;
1120 }
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:3131
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:9967
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:3220
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:3362
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:8614
#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:8604
#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:5715
#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:3013
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:8659
#define MAX(x, y)
Definition: tclique_def.h:83
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:5705
#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:3047
#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