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