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_subnlp.c
17 * @ingroup DEFPLUGINS_HEUR
18 * @brief NLP local search primal heuristic using sub-SCIPs
19 * @author Stefan Vigerske
20 *
21 * @todo set cutoff or similar in NLP
22 */
23
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25
26 #include "blockmemshell/memory.h"
27 #include "nlpi/nlpi.h"
28 #include "nlpi/nlpi_ipopt.h"
29 #include "scip/cons_bounddisjunction.h"
30 #include "scip/cons_knapsack.h"
31 #include "scip/cons_linear.h"
32 #include "scip/cons_logicor.h"
33 #include "scip/cons_setppc.h"
34 #include "scip/cons_varbound.h"
35 #include "scip/heur_subnlp.h"
36 #include "scip/pub_cons.h"
37 #include "scip/pub_event.h"
38 #include "scip/pub_heur.h"
39 #include "scip/pub_message.h"
40 #include "scip/pub_misc.h"
41 #include "scip/pub_sol.h"
42 #include "scip/pub_var.h"
43 #include "scip/scip_branch.h"
44 #include "scip/scip_cons.h"
45 #include "scip/scip_copy.h"
46 #include "scip/scip_event.h"
47 #include "scip/scip_general.h"
48 #include "scip/scip_heur.h"
49 #include "scip/scip_lp.h"
50 #include "scip/scip_mem.h"
51 #include "scip/scip_message.h"
52 #include "scip/scip_nlp.h"
53 #include "scip/scip_numerics.h"
54 #include "scip/scip_param.h"
55 #include "scip/scip_pricer.h"
56 #include "scip/scip_prob.h"
57 #include "scip/scip_sol.h"
58 #include "scip/scip_solve.h"
59 #include "scip/scip_solvingstats.h"
60 #include "scip/scip_timing.h"
61 #include "scip/scip_var.h"
62 #include <string.h>
63
64 #define HEUR_NAME "subnlp"
65 #define HEUR_DESC "primal heuristic that performs a local search in an NLP after fixing integer variables and presolving"
66 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
67 #define HEUR_PRIORITY -2000000
68 #define HEUR_FREQ 1
69 #define HEUR_FREQOFS 0
70 #define HEUR_MAXDEPTH -1
71 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
72 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? we set this to FALSE because we want this heuristic to also run within other heuristics */
73
74 /*
75 * Data structures
76 */
77
78 /** primal heuristic data */
79 struct SCIP_HeurData
80 {
81 SCIP* subscip; /**< copy of CIP where presolving and NLP solving is done */
82 SCIP_Bool triedsetupsubscip; /**< whether we have tried to setup a sub-SCIP */
83 SCIP_Bool subscipisvalid; /**< whether all constraints have been copied */
84 int nseriousnlpierror; /**< number of consecutive serious NLP solver failures (memout, ...) */
85 SCIP_EVENTHDLR* eventhdlr; /**< event handler for global bound change events */
86
87 int nvars; /**< number of active transformed variables in SCIP */
88 int nsubvars; /**< number of original variables in sub-SCIP */
89 SCIP_VAR** var_subscip2scip; /**< mapping variables in sub-SCIP to SCIP variables */
90 SCIP_VAR** var_scip2subscip; /**< mapping variables in SCIP to sub-SCIP variables */
91
92 SCIP_SOL* startcand; /**< candidate for start point for heuristic */
93 SCIP_Real startcandviol; /**< violation of start point candidate w.r.t. constraint that reported this candidate */
94 SCIP_SOL* lastsol; /**< pointer to last found solution (or NULL if none), not captured, thus may be dangling */
95
96 SCIP_NLPSTATISTICS* nlpstatistics; /**< statistics from NLP solver */
97 SCIP_Bool comblinearconsadded;/**< whether the linear constraint adding method has been called for combinatorial constraints already */
98 SCIP_Bool contlinearconsadded;/**< whether the linear constraint adding method has been called for continuous constraints already */
99
100 int nlpverblevel; /**< verbosity level of NLP solver */
101 int nlpiterlimit; /**< iteration limit of NLP solver; 0 for off */
102 SCIP_Real nlptimelimit; /**< time limit of NLP solver; 0 for off */
103 SCIP_Real resolvetolfactor; /**< factor for feasibility tolerance when resolving NLP due to disagreement of feasibility */
104 SCIP_Bool resolvefromscratch; /**< whether a resolve of an NLP due to disagreement of feasibility should be from the original starting point or the infeasible solution */
105 char* nlpoptfile; /**< name of NLP solver specific option file */
106 SCIP_Real minimprove; /**< desired minimal improvement in objective function value when running heuristic */
107 int maxpresolverounds; /**< limit on number of presolve rounds in sub-SCIP */
108 SCIP_Bool forbidfixings; /**< whether to add constraints that forbid specific fixations that turned out to be infeasible */
109 SCIP_Bool keepcopy; /**< whether to keep SCIP copy or to create new copy each time heuristic is applied */
110
111 SCIP_Longint iterused; /**< number of iterations used so far */
112 int iteroffset; /**< number of iterations added to the contingent of the total number of iterations */
113 SCIP_Real iterquot; /**< contingent of NLP iterations in relation to the number of nodes in SCIP */
114 int itermin; /**< minimal number of iterations required to start local search */
115 SCIP_Bool runalways; /**< whether to run NLP heuristic always (independent of iteroffset,iterquot,itermin) */
116 int nsolfound; /**< number of solutions found in this run (because we give authorship of solutions we found to the heuristic that proposed the starting point) */
117 };
118
119
120 /*
121 * Local methods
122 */
123
124 /** indicates whether the heuristic should be running, i.e., whether we expect something nonlinear after fixing all discrete variables */
125 static
runHeuristic(SCIP * scip)126 SCIP_Bool runHeuristic(
127 SCIP* scip /**< SCIP data structure */
128 )
129 {
130 assert(scip != NULL);
131
132 /* do not run heuristic if no NLP solver is available */
133 if( SCIPgetNNlpis(scip) <= 0 )
134 return FALSE;
135
136 /* do not run heuristic if no continuous nonlinear variables are present */
137 if( !SCIPisNLPConstructed(scip) || !SCIPhasNLPContinuousNonlinearity(scip) )
138 return FALSE;
139
140 return TRUE;
141 }
142
143 /** creates copy of CIP from problem in SCIP */
144 static
createSubSCIP(SCIP * scip,SCIP_HEURDATA * heurdata)145 SCIP_RETCODE createSubSCIP(
146 SCIP* scip, /**< SCIP data structure */
147 SCIP_HEURDATA* heurdata /**< heuristic data structure */
148 )
149 {
150 int nvars;
151 SCIP_VAR** vars;
152 SCIP_VAR** subvars;
153 SCIP_VAR* var;
154 SCIP_VAR* subvar;
155 SCIP_Bool success;
156 char probname[SCIP_MAXSTRLEN];
157 int i;
158 SCIP_HASHMAP* varsmap;
159 SCIP_HASHMAP* conssmap;
160 #ifdef SCIP_DEBUG
161 static const SCIP_Bool copydisplays = TRUE;
162 static const SCIP_Bool copyreader = TRUE;
163 #else
164 static const SCIP_Bool copydisplays = FALSE;
165 static const SCIP_Bool copyreader = FALSE;
166 #endif
167 SCIP_NLPI* ipopt;
168
169 assert(heurdata != NULL);
170 assert(heurdata->subscip == NULL);
171
172 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
173
174 heurdata->triedsetupsubscip = TRUE;
175
176 /* initializing the subproblem */
177 SCIP_CALL( SCIPcreate(&heurdata->subscip) );
178
179 /* create variable hash mapping scip -> subscip */
180 SCIP_CALL( SCIPhashmapCreate(&varsmap, SCIPblkmem(scip), nvars) );
181
182 /* create sub-SCIP copy of CIP */
183
184 /* copy interesting plugins */
185 success = TRUE;
186 SCIP_CALL( SCIPcopyPlugins(scip, heurdata->subscip,
187 copyreader, /* readers */
188 FALSE, /* pricers */
189 TRUE, /* conshdlrs */
190 FALSE, /* conflicthdlrs */
191 TRUE, /* presolvers */
192 FALSE, /* relaxators */
193 FALSE, /* separators */
194 TRUE, /* propagators */
195 FALSE, /* heuristics */
196 TRUE, /* eventhandler */
197 TRUE, /* nodeselectors (SCIP gives an error if there is none) */
198 FALSE, /* branchrules */
199 copydisplays, /* displays */
200 FALSE, /* tables */
201 FALSE, /* dialogs */
202 TRUE, /* nlpis */
203 TRUE, /* message handler */
204 &success) );
205 if( !success )
206 {
207 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "In heur_subnlp: failed to copy some plugins to sub-SCIP, continue anyway\n");
208 }
209
210 /* check if we still have NLPI's in subscip */
211 if( SCIPgetNNlpis(heurdata->subscip) <= 0 )
212 {
213 SCIPdebugMsg(scip, "some NLPIs from main SCIP did not copy into sub-SCIP, give up heuristic.\n");
214 SCIP_CALL( SCIPfree(&heurdata->subscip) );
215 SCIPhashmapFree(&varsmap);
216
217 return SCIP_OKAY;
218 }
219
220 /* copy parameter settings */
221 SCIP_CALL( SCIPcopyParamSettings(scip, heurdata->subscip) );
222
223 /* create problem in sub-SCIP */
224 /* get name of the original problem and add "subnlp" */
225 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_subnlp", SCIPgetProbName(scip));
226 SCIP_CALL( SCIPhashmapCreate(&conssmap, SCIPblkmem(scip), SCIPgetNConss(scip)) );
227 SCIP_CALL( SCIPcopyProb(scip, heurdata->subscip, varsmap, conssmap, TRUE, probname) );
228
229 /* copy all variables */
230 SCIP_CALL( SCIPcopyVars(scip, heurdata->subscip, varsmap, NULL, NULL, NULL, 0, TRUE) );
231
232 /* copy as many constraints as possible */
233 SCIP_CALL( SCIPcopyConss(scip, heurdata->subscip, varsmap, conssmap, TRUE, FALSE, &heurdata->subscipisvalid) );
234 SCIPhashmapFree(&conssmap);
235 if( !heurdata->subscipisvalid )
236 {
237 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "In heur_subnlp: failed to copy some constraints to sub-SCIP, continue anyway\n");
238 SCIPdebugMsg(scip, "In heur_subnlp: failed to copy some constraints to sub-SCIP, continue anyway\n");
239 }
240
241 /* create arrays translating scip transformed vars to subscip original vars, and vice versa
242 * capture variables in SCIP and sub-SCIP
243 * catch global bound change events
244 */
245
246 SCIP_CALL( SCIPgetVarsData(heurdata->subscip, &subvars, &heurdata->nsubvars, NULL, NULL, NULL, NULL) );
247
248 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &heurdata->var_subscip2scip, heurdata->nsubvars) );
249
250 heurdata->nvars = nvars;
251 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &heurdata->var_scip2subscip, heurdata->nvars) );
252
253 /* we need to get all subscip variables, also those which are copies of fixed variables from the main scip
254 * therefore we iterate over the hashmap
255 */
256 for( i = 0; i < SCIPhashmapGetNEntries(varsmap); ++i )
257 {
258 SCIP_HASHMAPENTRY* entry;
259 entry = SCIPhashmapGetEntry(varsmap, i);
260 if( entry != NULL )
261 {
262 var = (SCIP_VAR*) SCIPhashmapEntryGetOrigin(entry);
263 subvar = (SCIP_VAR*) SCIPhashmapEntryGetImage(entry);
264 assert(subvar != NULL);
265 assert(SCIPvarGetProbindex(subvar) >= 0);
266 assert(SCIPvarGetProbindex(subvar) <= heurdata->nsubvars);
267
268 if( SCIPvarIsActive(var) )
269 {
270 assert(SCIPvarGetProbindex(var) <= heurdata->nvars);
271 assert(heurdata->var_scip2subscip[SCIPvarGetProbindex(var)] == NULL); /* assert that we have no mapping for this var yet */
272 heurdata->var_scip2subscip[SCIPvarGetProbindex(var)] = subvar;
273 }
274
275 assert(heurdata->var_subscip2scip[SCIPvarGetProbindex(subvar)] == NULL); /* assert that we have no mapping for this subvar yet */
276 heurdata->var_subscip2scip[SCIPvarGetProbindex(subvar)] = var;
277 }
278 }
279
280 for( i = 0; i < heurdata->nsubvars; ++i )
281 {
282 subvar = SCIPgetVars(heurdata->subscip)[i];
283 assert(SCIPvarGetProbindex(subvar) == i);
284 var = heurdata->var_subscip2scip[i];
285
286 SCIP_CALL( SCIPcaptureVar(scip, var) );
287 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, subvar) );
288
289 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetLbGlobal(subvar)));
290 assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), SCIPvarGetUbGlobal(subvar)));
291
292 SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_GBDCHANGED, heurdata->eventhdlr, (SCIP_EVENTDATA*)heurdata, NULL) );
293 }
294
295 #ifndef NDEBUG
296 for( i = 0; i < heurdata->nvars; ++i )
297 {
298 assert(heurdata->var_scip2subscip[i] == NULL || (SCIP_VAR*)SCIPhashmapGetImage(varsmap, (void*)vars[i]) == heurdata->var_scip2subscip[i]);
299 }
300 for( i = 0; i < heurdata->nsubvars; ++i )
301 {
302 assert(heurdata->var_subscip2scip[i] != NULL);
303 assert((SCIP_VAR*)SCIPhashmapGetImage(varsmap, (void*)heurdata->var_subscip2scip[i]) == subvars[i]);
304 }
305 #endif
306
307 /* do not need hashmap anymore */
308 SCIPhashmapFree(&varsmap);
309
310 /* initialize data structure for NLP solve statistics */
311 SCIP_CALL( SCIPnlpStatisticsCreate(SCIPblkmem(scip), &heurdata->nlpstatistics) );
312
313 /* do not abort subproblem on CTRL-C */
314 SCIP_CALL( SCIPsetBoolParam(heurdata->subscip, "misc/catchctrlc", FALSE) );
315
316 /* disable keeping solutions from one subscip solve for next solve (with usually different fixings) */
317 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "limits/maxorigsol", 0) );
318
319 /* disable output to console */
320 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 0) );
321
322 /* reset some limits to default values, in case users changed them in main scip (SCIPcopy copies parameter values :-() */
323 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/absgap") );
324 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/bestsol") );
325 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/gap") );
326 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/restarts") );
327 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/solutions") );
328 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/time") );
329 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/totalnodes") );
330
331 /* disable restarts (not sure they could be triggered on continuous problems anyway)
332 * keep normal presolving, but disable components presolver
333 * heuristics and separators were not copied into subscip, so should not need to switch off
334 */
335 if( !SCIPisParamFixed(heurdata->subscip, "constraints/components/maxprerounds") )
336 {
337 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "constraints/components/maxprerounds", 0) );
338 }
339 if( !SCIPisParamFixed(heurdata->subscip, "presolving/maxrestarts") )
340 {
341 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "presolving/maxrestarts", 0) );
342 }
343
344 #ifdef SCIP_DEBUG
345 /* for debugging, enable SCIP output */
346 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 5) );
347 #endif
348
349 /* enable infeasible problem heuristic in Ipopt */
350 ipopt = SCIPfindNlpi(heurdata->subscip, "ipopt");
351 if( ipopt != NULL )
352 SCIPsetModifiedDefaultSettingsIpopt(ipopt, "expect_infeasible_problem yes\n", TRUE);
353
354 return SCIP_OKAY;
355 }
356
357 /** free sub-SCIP data structure */
358 static
freeSubSCIP(SCIP * scip,SCIP_HEURDATA * heurdata)359 SCIP_RETCODE freeSubSCIP(
360 SCIP* scip, /**< SCIP data structure */
361 SCIP_HEURDATA* heurdata /**< heuristic data structure */
362 )
363 {
364 SCIP_VAR** subvars;
365 int nsubvars;
366 int i;
367 SCIP_VAR* var;
368 SCIP_VAR* subvar;
369
370 assert(scip != NULL);
371 assert(heurdata != NULL);
372
373 assert(heurdata->subscip != NULL);
374
375 /* free NLP statistics */
376 if( heurdata->nlpstatistics != NULL )
377 SCIPnlpStatisticsFree(SCIPblkmem(scip), &heurdata->nlpstatistics);
378 assert(heurdata->nlpstatistics == NULL);
379
380 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, NULL, NULL, NULL, NULL) );
381 assert(nsubvars == heurdata->nsubvars);
382
383 /* drop global bound change events
384 * release variables in SCIP and sub-SCIP
385 */
386 for( i = 0; i < heurdata->nsubvars; ++i )
387 {
388 subvar = subvars[i];
389 assert(subvar != NULL);
390 assert(SCIPvarGetProbindex(subvar) == i);
391
392 var = heurdata->var_subscip2scip[SCIPvarGetProbindex(subvar)];
393 assert(var != NULL);
394 assert(SCIPvarGetProbindex(var) <= heurdata->nvars);
395 assert(!SCIPvarIsActive(var) || heurdata->var_scip2subscip[SCIPvarGetProbindex(var)] == subvar);
396
397 SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_GBDCHANGED, heurdata->eventhdlr, (SCIP_EVENTDATA*)heurdata, -1) );
398
399 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &subvar) );
400 SCIP_CALL( SCIPreleaseVar(scip, &var) );
401 }
402
403 /* free variable mappings subscip -> scip and scip -> subscip */
404 SCIPfreeBlockMemoryArray(scip, &heurdata->var_subscip2scip, heurdata->nsubvars);
405 SCIPfreeBlockMemoryArray(scip, &heurdata->var_scip2subscip, heurdata->nvars);
406 heurdata->nsubvars = 0;
407 heurdata->nvars = 0;
408
409 /* free sub-SCIP */
410 SCIP_CALL( SCIPfree(&heurdata->subscip) );
411
412 return SCIP_OKAY;
413 }
414
415 /** process variable global bound change event */
416 static
SCIP_DECL_EVENTEXEC(processVarEvent)417 SCIP_DECL_EVENTEXEC(processVarEvent)
418 {
419 SCIP_HEURDATA* heurdata;
420 SCIP_VAR* var;
421 SCIP_VAR* subvar;
422 int idx;
423
424 assert(scip != NULL);
425 assert(event != NULL);
426 assert(eventdata != NULL);
427 assert(eventhdlr != NULL);
428
429 heurdata = (SCIP_HEURDATA*)eventdata;
430 assert(heurdata != NULL);
431
432 var = SCIPeventGetVar(event);
433 assert(var != NULL);
434
435 idx = SCIPvarGetProbindex(var);
436 /* if event corresponds to an active variable, we can easily look up the corresponding subvar
437 * if it is an inactive variable that has been copied to the subproblem,
438 * then we need to check the subscip2scip mapping
439 * @todo we could do this faster if we keep the variables mapping from SCIPcopy around
440 */
441 if( idx >= 0 )
442 {
443 assert(idx < heurdata->nvars);
444
445 subvar = heurdata->var_scip2subscip[idx];
446 }
447 else
448 {
449 for( idx = 0; idx < heurdata->nsubvars; ++idx )
450 {
451 if( heurdata->var_subscip2scip[idx] == var )
452 break;
453 }
454 assert(idx < heurdata->nsubvars);
455 subvar = SCIPgetVars(heurdata->subscip)[idx];
456 }
457 assert(subvar != NULL);
458
459 if( SCIPeventGetType(event) & SCIP_EVENTTYPE_GLBCHANGED )
460 {
461 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, SCIPvarGetLbGlobal(var)) );
462 }
463
464 if( SCIPeventGetType(event) & SCIP_EVENTTYPE_GUBCHANGED )
465 {
466 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, SCIPvarGetUbGlobal(var)) );
467 }
468
469 return SCIP_OKAY;
470 }
471
472 /** adds linear constraints from a SCIP instance to its NLP */
473 static
addLinearConstraints(SCIP * scip,SCIP_CONSHDLR * conshdlr,SCIP_Bool addcombconss,SCIP_Bool addcontconss)474 SCIP_RETCODE addLinearConstraints(
475 SCIP* scip, /**< SCIP data structure */
476 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */
477 SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints to NLP */
478 SCIP_Bool addcontconss /**< whether to add continuous linear constraints to NLP */
479 )
480 {
481 SCIP_CONS** conss;
482 int nconss;
483 SCIP_NLROW* nlrow;
484 int i;
485 int j;
486 SCIP_Bool iscombinatorial;
487 int nvars;
488 SCIP_VAR** vars;
489
490 assert(scip != NULL);
491 assert(conshdlr != NULL);
492
493 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
494 conss = SCIPconshdlrGetConss(conshdlr);
495
496 if( nconss == 0 )
497 return SCIP_OKAY;
498
499 for( i = 0; i < nconss; ++i )
500 {
501 /* skip local and redundant constraints */
502 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
503 continue;
504
505 /* under some circumstances, this method may be called even though the problem has been shown to be infeasible in presolve already
506 * this infeasibility may come from a linear constraint with lhs > rhs
507 * the NLP does not allow such constraints, so we skip them here
508 */
509 if( !SCIPisRelLE(scip, SCIPgetLhsLinear(scip, conss[i]), SCIPgetRhsLinear(scip, conss[i])) )
510 continue;
511
512 nvars = SCIPgetNVarsLinear(scip, conss[i]);
513 vars = SCIPgetVarsLinear(scip, conss[i]);
514
515 /* check if constraint should be added, only need this check if we do not wanna any constraint anyway */
516 if( !addcombconss || !addcontconss )
517 {
518 iscombinatorial = TRUE;
519
520 for( j = 0; j < nvars; ++j )
521 if( SCIPvarGetType(vars[j]) >= SCIP_VARTYPE_CONTINUOUS )
522 {
523 iscombinatorial = FALSE;
524 break;
525 }
526
527 /* skip constraint, if not of interest */
528 if( (iscombinatorial && !addcombconss) || (!iscombinatorial && !addcontconss) )
529 continue;
530 }
531
532 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
533 SCIPgetNVarsLinear(scip, conss[i]), SCIPgetVarsLinear(scip, conss[i]), SCIPgetValsLinear(scip, conss[i]),
534 0, NULL, 0, NULL, NULL,
535 SCIPgetLhsLinear(scip, conss[i]), SCIPgetRhsLinear(scip, conss[i]),
536 SCIP_EXPRCURV_LINEAR) );
537
538 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
539 SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) );
540 }
541
542 return SCIP_OKAY;
543 }
544
545 /** adds variable bound constraints from a SCIP instance to its NLP */
546 static
addVarboundConstraints(SCIP * scip,SCIP_CONSHDLR * conshdlr,SCIP_Bool addcombconss,SCIP_Bool addcontconss)547 SCIP_RETCODE addVarboundConstraints(
548 SCIP* scip, /**< SCIP data structure */
549 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */
550 SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints to NLP */
551 SCIP_Bool addcontconss /**< whether to add continuous linear constraints to NLP */
552 )
553 {
554 SCIP_CONS** conss;
555 int nconss;
556 SCIP_NLROW* nlrow;
557 int i;
558 SCIP_VAR* vars[2];
559 SCIP_Real coefs[2];
560 SCIP_Bool iscombinatorial;
561
562 assert(scip != NULL);
563 assert(conshdlr != NULL);
564
565 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
566 conss = SCIPconshdlrGetConss(conshdlr);
567
568 if( nconss == 0 )
569 return SCIP_OKAY;
570
571 for( i = 0; i < nconss; ++i )
572 {
573 /* skip local and redundant constraints */
574 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
575 continue;
576
577 vars[0] = SCIPgetVarVarbound(scip, conss[i]);
578 vars[1] = SCIPgetVbdvarVarbound(scip, conss[i]);
579
580 iscombinatorial = SCIPvarGetType(vars[0]) < SCIP_VARTYPE_CONTINUOUS && SCIPvarGetType(vars[1]) < SCIP_VARTYPE_CONTINUOUS;
581
582 /* skip constraint, if not of interest */
583 if( (iscombinatorial && !addcombconss) || (!iscombinatorial && !addcontconss) )
584 continue;
585
586 coefs[0] = 1.0;
587 coefs[1] = SCIPgetVbdcoefVarbound(scip, conss[i]);
588
589 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
590 2, vars, coefs,
591 0, NULL, 0, NULL, NULL,
592 SCIPgetLhsVarbound(scip, conss[i]), SCIPgetRhsVarbound(scip, conss[i]),
593 SCIP_EXPRCURV_LINEAR) );
594
595 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
596 SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) );
597 }
598
599 return SCIP_OKAY;
600 }
601
602 /** adds logic-or constraints to NLP */
603 static
addLogicOrConstraints(SCIP * scip,SCIP_CONSHDLR * conshdlr)604 SCIP_RETCODE addLogicOrConstraints(
605 SCIP* scip, /**< SCIP data structure */
606 SCIP_CONSHDLR* conshdlr /**< constraint handler for linear constraints */
607 )
608 {
609 SCIP_CONS** conss;
610 int nconss;
611 SCIP_NLROW* nlrow;
612 int i;
613 int j;
614 SCIP_Real* coefs;
615 int coefssize;
616 int nvars;
617
618 assert(scip != NULL);
619 assert(conshdlr != NULL);
620
621 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
622 if( !nconss )
623 return SCIP_OKAY;
624
625 conss = SCIPconshdlrGetConss(conshdlr);
626
627 coefs = NULL;
628 coefssize = 0;
629
630 for( i = 0; i < nconss; ++i )
631 {
632 /* skip local and redundant constraints */
633 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
634 continue;
635
636 nvars = SCIPgetNVarsLogicor(scip, conss[i]);
637
638 if( coefssize < nvars )
639 {
640 if( coefs == NULL )
641 {
642 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) );
643 }
644 else
645 {
646 SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, nvars) );
647 }
648 for( j = coefssize; j < nvars; ++j )
649 coefs[j] = 1.0;
650 coefssize = nvars;
651 }
652
653 /* logic or constraints: 1 <= sum_j x_j */
654
655 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
656 nvars, SCIPgetVarsLogicor(scip, conss[i]), coefs,
657 0, NULL, 0, NULL, NULL,
658 1.0, SCIPinfinity(scip),
659 SCIP_EXPRCURV_LINEAR) );
660
661 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
662 SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) );
663 }
664
665 SCIPfreeBufferArrayNull(scip, &coefs);
666
667 return SCIP_OKAY;
668 }
669
670 /** adds setppc constraints to NLP */
671 static
addSetppcConstraints(SCIP * scip,SCIP_CONSHDLR * conshdlr)672 SCIP_RETCODE addSetppcConstraints(
673 SCIP* scip, /**< SCIP data structure */
674 SCIP_CONSHDLR* conshdlr /**< constraint handler for linear constraints */
675 )
676 {
677 SCIP_CONS** conss;
678 int nconss;
679 SCIP_NLROW* nlrow;
680 int i;
681 int j;
682 SCIP_Real* coefs;
683 int coefssize;
684 int nvars;
685 SCIP_Real lhs;
686 SCIP_Real rhs;
687
688 assert(scip != NULL);
689 assert(conshdlr != NULL);
690
691 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
692 if( !nconss )
693 return SCIP_OKAY;
694
695 conss = SCIPconshdlrGetConss(conshdlr);
696
697 coefs = NULL;
698 coefssize = 0;
699
700 for( i = 0; i < nconss; ++i )
701 {
702 /* skip local and redundant constraints */
703 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
704 continue;
705
706 nvars = SCIPgetNVarsSetppc(scip, conss[i]);
707
708 if( coefssize < nvars )
709 {
710 if( coefs == NULL )
711 {
712 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) );
713 }
714 else
715 {
716 SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, nvars) );
717 }
718 for( j = coefssize; j < nvars; ++j )
719 coefs[j] = 1.0;
720 coefssize = nvars;
721 }
722
723 /* setppc constraint: 1 ~ sum_j x_j */
724
725 switch( SCIPgetTypeSetppc(scip, conss[i]) )
726 {
727 case SCIP_SETPPCTYPE_PARTITIONING:
728 lhs = 1.0;
729 rhs = 1.0;
730 break;
731
732 case SCIP_SETPPCTYPE_PACKING:
733 lhs = -SCIPinfinity(scip);
734 rhs = 1.0;
735 break;
736
737 case SCIP_SETPPCTYPE_COVERING:
738 lhs = 1.0;
739 rhs = SCIPinfinity(scip);
740 break;
741
742 default:
743 SCIPerrorMessage("unexpected setppc type\n");
744 return SCIP_ERROR;
745 }
746
747 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
748 nvars, SCIPgetVarsSetppc(scip, conss[i]), coefs,
749 0, NULL, 0, NULL, NULL,
750 lhs, rhs,
751 SCIP_EXPRCURV_LINEAR) );
752
753 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
754 SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) );
755 }
756
757 SCIPfreeBufferArrayNull(scip, &coefs);
758
759 return SCIP_OKAY;
760 }
761
762 /** adds knapsack constraints to NLP */
763 static
addKnapsackConstraints(SCIP * scip,SCIP_CONSHDLR * conshdlr)764 SCIP_RETCODE addKnapsackConstraints(
765 SCIP* scip, /**< SCIP data structure */
766 SCIP_CONSHDLR* conshdlr /**< constraint handler for linear constraints */
767 )
768 {
769 SCIP_CONS** conss;
770 int nconss;
771 SCIP_NLROW* nlrow;
772 int i;
773 int j;
774 SCIP_Real* coefs;
775 int coefssize;
776 int nvars;
777
778 assert(scip != NULL);
779 assert(conshdlr != NULL);
780
781 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
782 if( !nconss )
783 return SCIP_OKAY;
784
785 conss = SCIPconshdlrGetConss(conshdlr);
786 assert(conss != NULL);
787
788 coefs = NULL;
789 coefssize = 0;
790
791 for( i = 0; i < nconss; ++i )
792 {
793 SCIP_Longint* weights;
794
795 /* skip local and redundant constraints */
796 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
797 continue;
798
799 nvars = SCIPgetNVarsKnapsack(scip, conss[i]);
800
801 if( coefssize < nvars )
802 {
803 if( coefs == NULL )
804 {
805 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) );
806 }
807 else
808 {
809 SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, nvars) );
810 }
811 coefssize = nvars;
812 }
813
814 weights = SCIPgetWeightsKnapsack(scip, conss[i]);
815 for( j = 0; j < nvars; ++j )
816 coefs[j] = (SCIP_Real)weights[j]; /*lint !e613*/
817
818 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
819 nvars, SCIPgetVarsKnapsack(scip, conss[i]), coefs,
820 0, NULL, 0, NULL, NULL,
821 -SCIPinfinity(scip), (SCIP_Real)SCIPgetCapacityKnapsack(scip, conss[i]),
822 SCIP_EXPRCURV_LINEAR) );
823
824 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
825 SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) );
826 }
827
828 SCIPfreeBufferArrayNull(scip, &coefs);
829
830 return SCIP_OKAY;
831 }
832
833 /** adds combinatorial and/or continuous variants of linear constraints from a SCIP instance to its NLP */
834 static
addLinearConstraintsToNlp(SCIP * scip,SCIP_Bool addcombconss,SCIP_Bool addcontconss)835 SCIP_RETCODE addLinearConstraintsToNlp(
836 SCIP* scip, /**< SCIP data structure */
837 SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints to NLP */
838 SCIP_Bool addcontconss /**< whether to add continuous linear constraints to NLP */
839 )
840 {
841 SCIP_CONSHDLR* conshdlr;
842
843 /* add linear constraints */
844 conshdlr = SCIPfindConshdlr(scip, "linear");
845 if( conshdlr != NULL )
846 {
847 SCIP_CALL( addLinearConstraints(scip, conshdlr, addcombconss, addcontconss) );
848 }
849
850 /* add varbound constraints */
851 conshdlr = SCIPfindConshdlr(scip, "varbound");
852 if( conshdlr != NULL )
853 {
854 SCIP_CALL( addVarboundConstraints(scip, conshdlr, addcombconss, addcontconss) );
855 }
856
857 if( addcombconss )
858 {
859 /* add logic-or constraints */
860 conshdlr = SCIPfindConshdlr(scip, "logicor");
861 if( conshdlr != NULL )
862 {
863 SCIP_CALL( addLogicOrConstraints(scip, conshdlr) );
864 }
865
866 /* add setppc constraints */
867 conshdlr = SCIPfindConshdlr(scip, "setppc");
868 if( conshdlr != NULL )
869 {
870 SCIP_CALL( addSetppcConstraints(scip, conshdlr) );
871 }
872
873 /* add knapsack constraints */
874 conshdlr = SCIPfindConshdlr(scip, "knapsack");
875 if( conshdlr != NULL )
876 {
877 SCIP_CALL( addKnapsackConstraints(scip, conshdlr) );
878 }
879 }
880
881 return SCIP_OKAY;
882 }
883
884 /* creates a SCIP_SOL in our SCIP space out of the solution from NLP solver in sub-SCIP */
885 static
createSolFromNLP(SCIP * scip,SCIP_HEUR * heur,SCIP_SOL ** sol,SCIP_HEUR * authorheur)886 SCIP_RETCODE createSolFromNLP(
887 SCIP* scip, /**< SCIP data structure */
888 SCIP_HEUR* heur, /**< heuristic data structure */
889 SCIP_SOL** sol, /**< buffer to store solution value; if pointing to NULL, then a new solution is created, otherwise values in the given one are overwritten */
890 SCIP_HEUR* authorheur /**< the heuristic which should be registered as author of the solution */
891 )
892 {
893 SCIP_HEURDATA* heurdata;
894 SCIP_VAR** vars;
895 int nvars;
896 SCIP_VAR* var;
897 SCIP_VAR* subvar;
898 SCIP_Real solval;
899 int i;
900
901 assert(scip != NULL);
902 assert(heur != NULL);
903 assert(sol != NULL);
904
905 heurdata = SCIPheurGetData(heur);
906 assert(heurdata != NULL);
907
908 if( *sol == NULL )
909 {
910 SCIP_CALL( SCIPcreateSol(scip, sol, authorheur) );
911 }
912 else
913 {
914 SCIPsolSetHeur(*sol, authorheur);
915 }
916
917 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
918
919 assert(nvars >= heurdata->nvars);
920 for( i = 0; i < heurdata->nvars; ++i )
921 {
922 var = vars[i];
923 assert(var != NULL);
924 assert(SCIPvarIsActive(var)); /* SCIPgetVarsData should have given us only active vars */
925
926 subvar = heurdata->var_scip2subscip[i];
927 if( subvar == NULL )
928 solval = MIN(MAX(0.0, SCIPvarGetLbLocal(var)), SCIPvarGetUbLocal(var)); /*lint !e666*/
929 else
930 solval = SCIPvarGetNLPSol(subvar);
931
932 assert(solval != SCIP_INVALID); /*lint !e777*/
933 SCIP_CALL( SCIPsetSolVal(scip, *sol, var, solval) );
934 }
935
936 for( ; i < nvars; ++i )
937 {
938 var = vars[i];
939 assert(var != NULL);
940 assert(SCIPvarIsActive(var)); /* SCIPgetVarsData should have given us only active vars */
941
942 solval = MIN(MAX(0.0, SCIPvarGetLbLocal(var)), SCIPvarGetUbLocal(var)); /*lint !e666*/
943 SCIP_CALL( SCIPsetSolVal(scip, *sol, var, solval) );
944 }
945
946 return SCIP_OKAY;
947 }
948
949 /* creates a SCIP_SOL in our SCIP space out of the SCIP_SOL from a sub-SCIP */
950 static
createSolFromSubScipSol(SCIP * scip,SCIP_HEUR * heur,SCIP_SOL ** sol,SCIP_SOL * subsol,SCIP_HEUR * authorheur)951 SCIP_RETCODE createSolFromSubScipSol(
952 SCIP* scip, /**< SCIP data structure */
953 SCIP_HEUR* heur, /**< heuristic data structure */
954 SCIP_SOL** sol, /**< buffer to store solution value; if pointing to NULL, then a new solution is created, otherwise values in the given one are overwritten */
955 SCIP_SOL* subsol, /**< solution of sub-SCIP */
956 SCIP_HEUR* authorheur /**< the heuristic which should be registered as author of the solution */
957 )
958 {
959 SCIP_HEURDATA* heurdata;
960 SCIP_VAR** vars;
961 int nvars;
962 SCIP_VAR* var;
963 SCIP_VAR* subvar;
964 SCIP_Real solval;
965 int i;
966
967 assert(scip != NULL);
968 assert(heur != NULL);
969 assert(sol != NULL);
970 assert(subsol != NULL);
971
972 heurdata = SCIPheurGetData(heur);
973 assert(heurdata != NULL);
974
975 if( *sol == NULL )
976 {
977 SCIP_CALL( SCIPcreateSol(scip, sol, authorheur) );
978 }
979 else
980 {
981 SCIPsolSetHeur(*sol, authorheur);
982 }
983
984 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
985
986 assert(nvars >= heurdata->nvars);
987 for( i = 0; i < heurdata->nvars; ++i )
988 {
989 var = vars[i];
990 assert(var != NULL);
991
992 if( !SCIPvarIsActive(var) )
993 continue;
994
995 subvar = heurdata->var_scip2subscip[i];
996 if( subvar == NULL )
997 solval = MIN(MAX(0.0, SCIPvarGetLbLocal(var)), SCIPvarGetUbLocal(var)); /*lint !e666*/
998 else
999 solval = SCIPgetSolVal(heurdata->subscip, subsol, subvar);
1000
1001 assert(solval != SCIP_INVALID); /*lint !e777*/
1002 SCIP_CALL( SCIPsetSolVal(scip, *sol, var, solval) );
1003 }
1004
1005 for( ; i < nvars; ++i )
1006 {
1007 var = vars[i];
1008 assert(var != NULL);
1009
1010 if( !SCIPvarIsActive(var) )
1011 continue;
1012
1013 solval = MIN(MAX(0.0, SCIPvarGetLbLocal(var)), SCIPvarGetUbLocal(var)); /*lint !e666*/
1014 SCIP_CALL( SCIPsetSolVal(scip, *sol, var, solval) );
1015 }
1016
1017 return SCIP_OKAY;
1018 }
1019
1020 /* solves the subNLP specified in subscip */
1021 static
solveSubNLP(SCIP * scip,SCIP_HEUR * heur,SCIP_RESULT * result,SCIP_SOL * refpoint,SCIP_Longint itercontingent,SCIP_Real timelimit,SCIP_Longint * iterused,SCIP_Bool tighttolerances,SCIP_SOL * resultsol)1022 SCIP_RETCODE solveSubNLP(
1023 SCIP* scip, /**< original SCIP data structure */
1024 SCIP_HEUR* heur, /**< heuristic data structure */
1025 SCIP_RESULT* result, /**< buffer to store result, DIDNOTFIND, FOUNDSOL, or CUTOFF */
1026 SCIP_SOL* refpoint, /**< point to take fixation of discrete variables from, and startpoint for NLP solver; if NULL, then LP solution is used */
1027 SCIP_Longint itercontingent, /**< iteration limit for NLP solver, or -1 for default of NLP heuristic */
1028 SCIP_Real timelimit, /**< time limit for NLP solver */
1029 SCIP_Longint* iterused, /**< buffer to store number of iterations used by NLP solver, or NULL if not of interest */
1030 SCIP_Bool tighttolerances, /**< whether to use tight feasibility tolerances and reduce presolve */
1031 SCIP_SOL* resultsol /**< a solution where to store found solution values, if any, or NULL if to try adding to SCIP */
1032 )
1033 {
1034 SCIP_HEURDATA* heurdata;
1035 SCIP_RETCODE retcode;
1036 SCIP_Real* startpoint;
1037 SCIP_VAR* var;
1038 SCIP_VAR* subvar;
1039 int i;
1040 SCIP_HEUR* authorheur; /* the heuristic which will be the author of a solution, if found */
1041
1042 assert(scip != NULL);
1043 assert(heur != NULL);
1044 assert(result != NULL);
1045
1046 heurdata = SCIPheurGetData(heur);
1047 assert(heurdata != NULL);
1048
1049 /* if NLP timelimit is set to 0.0, then return immediately
1050 * Previously, we were still running scip presolve, assuming the caller wanted to see if the instance is still feasible after presolve.
1051 * But now we want to set a timelimit also for the scip presolve, and it is easiest to use timelimit for this.
1052 */
1053 if( timelimit == 0.0 )
1054 goto CLEANUP;
1055
1056 if( tighttolerances )
1057 {
1058 SCIP_Real sumepsilon;
1059
1060 /* reduce feasibility tolerance of sub-SCIP and do less aggressive presolve */
1061 SCIP_CALL( SCIPsetRealParam(heurdata->subscip, "numerics/feastol", heurdata->resolvetolfactor*SCIPfeastol(scip)) );
1062 SCIP_CALL( SCIPsetRealParam(heurdata->subscip, "numerics/epsilon", heurdata->resolvetolfactor*SCIPepsilon(scip)) );
1063 SCIP_CALL( SCIPgetRealParam(scip, "numerics/sumepsilon", &sumepsilon) );
1064 SCIP_CALL( SCIPsetRealParam(heurdata->subscip, "numerics/sumepsilon", heurdata->resolvetolfactor*sumepsilon) );
1065 SCIP_CALL( SCIPsetPresolving(heurdata->subscip, SCIP_PARAMSETTING_FAST, TRUE) );
1066
1067 if( !SCIPisParamFixed(heurdata->subscip, "constraints/linear/aggregatevariables") )
1068 {
1069 SCIP_CALL( SCIPsetBoolParam(heurdata->subscip, "constraints/linear/aggregatevariables", FALSE) );
1070 }
1071 }
1072
1073 /* transform sub-SCIP */
1074 SCIP_CALL( SCIPtransformProb(heurdata->subscip) );
1075
1076 /* presolve sub-SCIP
1077 * set scip timelimit in case presolve is unexpectedly expensive
1078 * set node limit to 1 so that presolve can go
1079 * reset maxpresolverounds, in case user changed or we reset presolving settings
1080 */
1081 SCIP_CALL( SCIPsetRealParam(heurdata->subscip, "limits/time", timelimit) );
1082 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) );
1083 if( !SCIPisParamFixed(heurdata->subscip, "presolving/maxrounds") )
1084 {
1085 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "presolving/maxrounds", heurdata->maxpresolverounds) );
1086 }
1087 SCIP_CALL( SCIPpresolve(heurdata->subscip) );
1088 if( SCIPpressedCtrlC(heurdata->subscip) )
1089 {
1090 SCIPdebugMsg(scip, "SCIP presolve interrupted by user\n");
1091 goto CLEANUP;
1092 }
1093 if( SCIPgetStage(heurdata->subscip) == SCIP_STAGE_SOLVED )
1094 {
1095 /* presolve probably found the subproblem infeasible */
1096 SCIPdebugMsg(scip, "SCIP returned from presolve in stage solved with status %d\n", SCIPgetStatus(heurdata->subscip));
1097 /* if presolve found subproblem infeasible, report this to caller by setting *result to cutoff */
1098 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_INFEASIBLE )
1099 *result = SCIP_CUTOFF;
1100 goto CLEANUP;
1101 }
1102 if( SCIPgetStage(heurdata->subscip) == SCIP_STAGE_PRESOLVING )
1103 {
1104 /* presolve was stopped because some still existing limit was hit (e.g., memory) */
1105 SCIPdebugMsg(scip, "SCIP returned from presolve in stage presolving with status %d\n", SCIPgetStatus(heurdata->subscip));
1106 /* if presolve found subproblem infeasible, report this to caller by setting *result to cutoff */
1107 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_INFEASIBLE )
1108 *result = SCIP_CUTOFF;
1109 goto CLEANUP;
1110 }
1111 assert(SCIPgetStage(heurdata->subscip) == SCIP_STAGE_PRESOLVED);
1112
1113 if( SCIPgetNVars(heurdata->subscip) > 0 )
1114 {
1115 /* do initial solve, i.e., "solve" root node with node limit 0 (should do scip.c::initSolve and then stop immediately in solve.c::SCIPsolveCIP) */
1116 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 0LL) );
1117 retcode = SCIPsolve(heurdata->subscip);
1118
1119 /* If no NLP was constructed, then there were no nonlinearities after presolve.
1120 * So we increase the nodelimit to 1 and hope that SCIP will find some solution to this probably linear subproblem.
1121 */
1122 if( retcode == SCIP_OKAY && SCIPgetStage(heurdata->subscip) != SCIP_STAGE_SOLVED && !SCIPisNLPConstructed(heurdata->subscip) )
1123 {
1124 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) );
1125 retcode = SCIPsolve(heurdata->subscip);
1126 }
1127 }
1128 else
1129 {
1130 /* If all variables were removed by presolve, but presolve did not end with status SOLVED,
1131 * then we run solve, still with nodelimit=1, and hope to find some (maybe trivial) solution.
1132 */
1133 retcode = SCIPsolve(heurdata->subscip);
1134 }
1135
1136 /* errors in solving the subproblem should not kill the overall solving process;
1137 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
1138 if ( retcode != SCIP_OKAY )
1139 {
1140 #ifndef NDEBUG
1141 SCIP_CALL( retcode );
1142 #endif
1143 SCIPwarningMessage(scip, "Error while solving subproblem in subnlp heuristic; sub-SCIP terminated with code <%d>\n", retcode);
1144 goto CLEANUP;
1145 }
1146
1147 /* if the refpoint comes from a heuristic, then make it the author of a found solution,
1148 * otherwise let the subNLP heuristic claim authorship
1149 */
1150 if( refpoint == NULL || SCIPsolGetHeur(refpoint) == NULL )
1151 authorheur = heur;
1152 else
1153 authorheur = SCIPsolGetHeur(refpoint);
1154
1155 /* if sub-SCIP found solutions already, then pass them to main scip */
1156 for( i = 0; i < SCIPgetNSols(heurdata->subscip); ++i )
1157 {
1158 SCIP_Bool stored;
1159
1160 if( resultsol == NULL )
1161 {
1162 SCIP_SOL* sol;
1163
1164 sol = NULL;
1165 SCIP_CALL( createSolFromSubScipSol(scip, heur, &sol, SCIPgetSols(heurdata->subscip)[i], authorheur) );
1166
1167 heurdata->lastsol = sol; /* remember just the pointer so we might recognize if this solution comes back as startingpoint */
1168 SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, TRUE, FALSE, TRUE, &stored) );
1169 if( stored )
1170 {
1171 if( heurdata->nlpverblevel >= 1 )
1172 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "SCIP stored solution from sub-SCIP root node\n");
1173 else
1174 {
1175 SCIPdebugMsg(scip, "SCIP stored solution from sub-SCIP root node\n");
1176 }
1177 *result = SCIP_FOUNDSOL;
1178 ++heurdata->nsolfound;
1179 break;
1180 }
1181 else
1182 {
1183 if( heurdata->nlpverblevel >= 1 )
1184 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "SCIP did not store sub-SCIP optimal solution\n");
1185 else
1186 {
1187 SCIPdebugMsg(scip, "SCIP did not store sub-SCIP optimal solution\n");
1188 }
1189 }
1190 }
1191 else
1192 {
1193 SCIP_CALL( createSolFromSubScipSol(scip, heur, &resultsol, SCIPgetSols(heurdata->subscip)[i], authorheur) );
1194
1195 heurdata->lastsol = resultsol;
1196 SCIP_CALL( SCIPcheckSol(scip, resultsol, FALSE, FALSE, TRUE, FALSE, TRUE, &stored) );
1197 if( stored )
1198 {
1199 if( heurdata->nlpverblevel >= 1 )
1200 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "SCIP solution from sub-SCIP root node is feasible\n");
1201 else
1202 {
1203 SCIPdebugMsg(scip, "SCIP solution from sub-SCIP root node is feasible\n");
1204 }
1205 *result = SCIP_FOUNDSOL;
1206 ++heurdata->nsolfound;
1207 break;
1208 }
1209 else
1210 {
1211 if( heurdata->nlpverblevel >= 1 )
1212 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "SCIP solution form sub-SCIP root node is not feasible\n");
1213 else
1214 {
1215 SCIPdebugMsg(scip, "SCIP solution form sub-SCIP root node is not feasible\n");
1216 }
1217 }
1218 }
1219 }
1220
1221 /* we should either have variables, or the problem was trivial, in which case it should have been solved */
1222 assert(SCIPgetNVars(heurdata->subscip) > 0 || SCIPgetStage(heurdata->subscip) == SCIP_STAGE_SOLVED);
1223
1224 /* if subscip is infeasible here, we signal this to the caller */
1225 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_INFEASIBLE )
1226 {
1227 if( heurdata->nlpverblevel >= 1 )
1228 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "sub-SCIP detected infeasibility\n");
1229 else
1230 {
1231 SCIPdebugMsg(scip, "sub-SCIP detected infeasibility\n");
1232 }
1233
1234 assert(SCIPgetStage(heurdata->subscip) == SCIP_STAGE_SOLVED);
1235 *result = SCIP_CUTOFF;
1236 goto CLEANUP;
1237 }
1238
1239 /* if we stopped for some other reason, or there is no NLP, we also stop */
1240 if( SCIPgetStage(heurdata->subscip) == SCIP_STAGE_SOLVED || !SCIPisNLPConstructed(heurdata->subscip) )
1241 goto CLEANUP;
1242
1243 /* in most cases, the status should be nodelimit
1244 * in some cases, if the sub-SCIP is very easy, it may report optimal, so we do not need invoke an NLP solver
1245 * if the presolve found the problem infeasible, then there is no use in solving an NLP
1246 * if the user interrupted or a timelimit was reached, then we should also stop here
1247 * unbounded is very unlikely to happen, in most cases, it should have been concluded in the main scip already
1248 */
1249 switch( SCIPgetStatus(heurdata->subscip) )
1250 {
1251 case SCIP_STATUS_NODELIMIT:
1252 break; /* this is the status that is most likely happening */
1253 case SCIP_STATUS_TOTALNODELIMIT:
1254 case SCIP_STATUS_STALLNODELIMIT:
1255 case SCIP_STATUS_GAPLIMIT:
1256 case SCIP_STATUS_SOLLIMIT:
1257 case SCIP_STATUS_BESTSOLLIMIT:
1258 /* these should not happen, but if one does, it's safe to go to CLEANUP */
1259 SCIPABORT(); /*lint -fallthrough*/
1260 case SCIP_STATUS_OPTIMAL:
1261 case SCIP_STATUS_INFEASIBLE:
1262 case SCIP_STATUS_USERINTERRUPT:
1263 case SCIP_STATUS_TIMELIMIT:
1264 case SCIP_STATUS_MEMLIMIT:
1265 case SCIP_STATUS_UNBOUNDED:
1266 case SCIP_STATUS_INFORUNBD:
1267 goto CLEANUP;
1268 default:
1269 SCIPerrorMessage("unexpected status of sub-SCIP: <%d>\n", SCIPgetStatus(heurdata->subscip));
1270 return SCIP_ERROR;
1271 } /*lint !e788*/
1272
1273 /* add non-combinatorial linear constraints from subscip into subNLP (shall be replaced by catching row events in NLP) */
1274 SCIP_CALL( addLinearConstraintsToNlp(heurdata->subscip, FALSE, TRUE) );
1275
1276 /* set starting values (=refpoint, if not NULL; otherwise LP solution (or pseudo solution)) */
1277 SCIP_CALL( SCIPallocBufferArray(scip, &startpoint, SCIPgetNNLPVars(heurdata->subscip)) );
1278
1279 if( heurdata->nlpverblevel >= 2 )
1280 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "set NLP starting point\n");
1281
1282 for( i = 0; i < SCIPgetNNLPVars(heurdata->subscip); ++i )
1283 {
1284 SCIP_Real scalar;
1285 SCIP_Real constant;
1286
1287 subvar = SCIPgetNLPVars(heurdata->subscip)[i];
1288
1289 /* gets corresponding original variable */
1290 scalar = 1.0;
1291 constant = 0.0;
1292 SCIP_CALL( SCIPvarGetOrigvarSum(&subvar, &scalar, &constant) );
1293 if( subvar == NULL )
1294 {
1295 startpoint[i] = constant;
1296
1297 if( heurdata->nlpverblevel >= 2 && !SCIPisZero(heurdata->subscip, startpoint[i]) )
1298 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "%s = %e\n", SCIPvarGetName(SCIPgetNLPVars(heurdata->subscip)[i]), startpoint[i]);
1299
1300 continue;
1301 }
1302
1303 assert(SCIPvarGetProbindex(subvar) >= 0);
1304 assert(SCIPvarGetProbindex(subvar) < heurdata->nsubvars);
1305 var = heurdata->var_subscip2scip[SCIPvarGetProbindex(subvar)];
1306 if( var == NULL || REALABS(SCIPgetSolVal(scip, refpoint, var)) > 1.0e+12 )
1307 startpoint[i] = MIN(MAX(0.0, SCIPvarGetLbGlobal(subvar)), SCIPvarGetUbGlobal(subvar)); /*lint !e666*/
1308 else
1309 /* scalar*subvar+constant corresponds to nlpvar[i], so nlpvar[i] gets value scalar*varval+constant */
1310 startpoint[i] = scalar * SCIPgetSolVal(scip, refpoint, var) + constant;
1311
1312 if( heurdata->nlpverblevel >= 2 && !SCIPisZero(heurdata->subscip, startpoint[i]) )
1313 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "%s = %e\n", SCIPvarGetName(SCIPgetNLPVars(heurdata->subscip)[i]), startpoint[i]);
1314 }
1315 SCIP_CALL( SCIPsetNLPInitialGuess(heurdata->subscip, startpoint) );
1316
1317 SCIPfreeBufferArray(scip, &startpoint);
1318
1319 *result = SCIP_DIDNOTFIND;
1320
1321 /* setup NLP parameters */
1322
1323 if( tighttolerances )
1324 {
1325 /* set feasibility tolerance, if tighttolerances is set */
1326 SCIP_CALL( SCIPsetNLPRealPar(heurdata->subscip, SCIP_NLPPAR_FEASTOL, heurdata->resolvetolfactor*SCIPfeastol(scip)) );
1327 }
1328 /* TODO Would it make sense to already start with a tighter feastol than SCIP's?
1329 else
1330 {
1331 SCIP_CALL( SCIPsetNLPRealPar(heurdata->subscip, SCIP_NLPPAR_FEASTOL, 0.1*SCIPfeastol(scip)) );
1332 }
1333 */
1334
1335 /* set option file to use by NLP solver */
1336 if( heurdata->nlpoptfile != NULL && *heurdata->nlpoptfile != '\0' )
1337 {
1338 SCIP_CALL( SCIPsetNLPStringPar(heurdata->subscip, SCIP_NLPPAR_OPTFILE, heurdata->nlpoptfile) );
1339 }
1340
1341 /* set iteration limit for NLP solver */
1342 if( itercontingent == -1 && heurdata->nlpiterlimit > 0 )
1343 itercontingent = heurdata->nlpiterlimit;
1344 if( itercontingent > 0 )
1345 {
1346 SCIP_CALL( SCIPsetNLPIntPar(heurdata->subscip, SCIP_NLPPAR_ITLIM, (int)MIN(INT_MAX, itercontingent)) );
1347 }
1348
1349 /* set time limit for NLP solver */
1350 SCIP_CALL( SCIPsetNLPRealPar(heurdata->subscip, SCIP_NLPPAR_TILIM, timelimit) );
1351
1352 /* set verbosity of NLP solver */
1353 SCIP_CALL( SCIPsetNLPIntPar(heurdata->subscip, SCIP_NLPPAR_VERBLEVEL, heurdata->nlpverblevel) );
1354
1355 /* let the NLP solver do its magic */
1356 SCIPdebugMsg(scip, "start NLP solve with iteration limit %" SCIP_LONGINT_FORMAT " and timelimit %g\n", itercontingent, timelimit);
1357 SCIP_CALL( SCIPsolveNLP(heurdata->subscip) );
1358
1359 SCIPdebugMsg(scip, "NLP solver returned with termination status %d and solution status %d, objective value is %g\n",
1360 SCIPgetNLPTermstat(heurdata->subscip), SCIPgetNLPSolstat(heurdata->subscip), SCIPgetNLPObjval(heurdata->subscip));
1361
1362 if( SCIPgetNLPTermstat(heurdata->subscip) >= SCIP_NLPTERMSTAT_MEMERR )
1363 {
1364 /* oops, something did not go well at all */
1365 if( heurdata->nlpverblevel >= 1 )
1366 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "NLP solver in subNLP heuristic for problem <%s> returned with bad termination status %d.",
1367 SCIPgetProbName(scip), SCIPgetNLPTermstat(heurdata->subscip));
1368
1369 ++(heurdata->nseriousnlpierror);
1370 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL,
1371 "NLP solver in subNLP heuristic for problem <%s> returned with bad termination status %d. This was the %d%s successive time.\n",
1372 SCIPgetProbName(scip), SCIPgetNLPTermstat(heurdata->subscip), heurdata->nseriousnlpierror,
1373 heurdata->nseriousnlpierror == 1 ? "st" : heurdata->nseriousnlpierror == 2 ? "nd" : heurdata->nseriousnlpierror == 3 ? "rd" : "th");
1374 if( heurdata->nseriousnlpierror >= 5 )
1375 {
1376 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Will not run NLP heuristic again for this run.\n");
1377 SCIP_CALL( freeSubSCIP(scip, heurdata) );
1378 }
1379 goto CLEANUP;
1380 }
1381 heurdata->nseriousnlpierror = 0;
1382
1383 SCIP_CALL( SCIPgetNLPStatistics(heurdata->subscip, heurdata->nlpstatistics) );
1384
1385 if( iterused != NULL )
1386 *iterused += SCIPnlpStatisticsGetNIterations(heurdata->nlpstatistics);
1387 SCIPdebugMsg(scip, "NLP solver used %d iterations and %g seconds\n",
1388 SCIPnlpStatisticsGetNIterations(heurdata->nlpstatistics), SCIPnlpStatisticsGetTotalTime(heurdata->nlpstatistics));
1389
1390 /* NLP solver claims it found a feasible (maybe even optimal) solution
1391 * if the objective value is better than our cutoff, then try to add it
1392 * if we do not plan to add the solution (resultsol != NULL), then also check it if objective value is not better than objlimit
1393 */
1394 if( SCIPgetNLPSolstat(heurdata->subscip) <= SCIP_NLPSOLSTAT_FEASIBLE && (resultsol != NULL || SCIPisLE(scip, SCIPgetNLPObjval(heurdata->subscip), SCIPgetObjlimit(heurdata->subscip))) )
1395 {
1396 if( resultsol == NULL )
1397 {
1398 SCIP_SOL* sol;
1399 SCIP_Bool stored;
1400
1401 sol = NULL;
1402 SCIP_CALL( createSolFromNLP(scip, heur, &sol, authorheur) );
1403
1404 heurdata->lastsol = sol; /* remember just the pointer so we might recognize if this solution comes back as startingpoint */
1405 if( heurdata->resolvefromscratch )
1406 {
1407 #ifdef SCIP_DEBUG
1408 /* print the infeasibilities to stdout */
1409 SCIP_CALL( SCIPtrySolFree(scip, &sol, TRUE, TRUE, TRUE, FALSE, TRUE, &stored) );
1410 #else
1411 SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, TRUE, FALSE, TRUE, &stored) );
1412 #endif
1413 }
1414 else
1415 {
1416 #ifdef SCIP_DEBUG
1417 /* print the infeasibilities to stdout */
1418 SCIP_CALL( SCIPtrySol(scip, sol, TRUE, TRUE, TRUE, FALSE, TRUE, &stored) );
1419 #else
1420 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, TRUE, &stored) );
1421 #endif
1422 }
1423
1424 if( stored )
1425 { /* SCIP stored solution (yippi!), so we are done */
1426 if( heurdata->nlpverblevel >= 1 )
1427 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "SCIP stored subnlp solution\n");
1428 else
1429 {
1430 SCIPdebugMsg(scip, "SCIP stored subnlp solution\n");
1431 }
1432
1433 *result = SCIP_FOUNDSOL;
1434 ++heurdata->nsolfound;
1435 }
1436 else if( !tighttolerances && heurdata->resolvetolfactor < 1.0 )
1437 {
1438 /* if SCIP does not like solution, we try again with tighter tolerances recreate subproblem and resolve with tighter tolerances */
1439 if( heurdata->nlpverblevel >= 1 )
1440 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "solution reported by NLP solver not feasible for SCIP, resolve with feasibility tolerance %g and epsilon %g\n",
1441 heurdata->resolvetolfactor*SCIPfeastol(scip), heurdata->resolvetolfactor*SCIPepsilon(scip));
1442 else
1443 {
1444 SCIPdebugMsg(scip, "solution reported by NLP solver not feasible for SCIP, resolve with feasibility tolerance %g and epsilon %g\n",
1445 heurdata->resolvetolfactor*SCIPfeastol(scip), heurdata->resolvetolfactor*SCIPepsilon(scip));
1446 }
1447
1448 /* free transformed problem */
1449 SCIP_CALL( SCIPfreeTransform(heurdata->subscip) );
1450
1451 SCIP_CALL( solveSubNLP(scip, heur, result, heurdata->resolvefromscratch ? refpoint : sol, itercontingent, timelimit, iterused, TRUE, NULL) );
1452 }
1453 else
1454 {
1455 if( heurdata->nlpverblevel >= 1 )
1456 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "solution reported by NLP solver not stored by SCIP\n");
1457 else
1458 {
1459 SCIPdebugMsg(scip, "solution reported by NLP solver not stored by SCIP\n");
1460 }
1461 }
1462
1463 if( sol != NULL )
1464 {
1465 SCIP_CALL( SCIPfreeSol(scip, &sol) );
1466 }
1467 }
1468 else
1469 {
1470 SCIP_Bool feasible;
1471
1472 SCIP_CALL( createSolFromNLP(scip, heur, &resultsol, authorheur) );
1473
1474 heurdata->lastsol = resultsol;
1475 #ifdef SCIP_DEBUG
1476 /* print the infeasibilities to stdout */
1477 SCIP_CALL( SCIPcheckSol(scip, resultsol, TRUE, TRUE, TRUE, FALSE, TRUE, &feasible) );
1478 #else
1479 SCIP_CALL( SCIPcheckSol(scip, resultsol, FALSE, FALSE, TRUE, FALSE, TRUE, &feasible) );
1480 #endif
1481 if( feasible )
1482 {
1483 /* SCIP find solution feasible, so we are done */
1484 if( heurdata->nlpverblevel >= 1 )
1485 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "solution reported by NLP solver feasible for SCIP\n");
1486 else
1487 {
1488 SCIPdebugMsg(scip, "solution reported by NLP solver feasible for SCIP\n");
1489 }
1490 *result = SCIP_FOUNDSOL;
1491 ++heurdata->nsolfound;
1492 }
1493 else if( !tighttolerances && heurdata->resolvetolfactor < 1.0 )
1494 {
1495 /* free transformed problem */
1496 SCIP_CALL( SCIPfreeTransform(heurdata->subscip) );
1497
1498 /* if SCIP does not like solution, we try again with tighter tolerances
1499 * recreate subproblem and resolve with tighter tolerances
1500 */
1501 if( heurdata->nlpverblevel >= 1 )
1502 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip),
1503 "solution reported by NLP solver not feasible for SCIP, resolve with feasibility tolerance %g and epsilon %g\n",
1504 heurdata->resolvetolfactor*SCIPfeastol(scip), heurdata->resolvetolfactor*SCIPepsilon(scip));
1505 else
1506 {
1507 SCIPdebugMsg(scip, "solution reported by NLP solver not feasible for SCIP, resolve with feasibility tolerance %g and epsilon %g\n",
1508 heurdata->resolvetolfactor*SCIPfeastol(scip), heurdata->resolvetolfactor*SCIPepsilon(scip));
1509 }
1510
1511 SCIP_CALL( solveSubNLP(scip, heur, result, heurdata->resolvefromscratch ? refpoint : resultsol, itercontingent, timelimit, iterused, TRUE, resultsol) );
1512 }
1513 else
1514 {
1515 if( heurdata->nlpverblevel >= 1 )
1516 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "solution reported by NLP solver not feasible for SCIP\n");
1517 else
1518 {
1519 SCIPdebugMsg(scip, "solution reported by NLP solver not feasible for SCIP\n");
1520 }
1521 }
1522 }
1523 }
1524 else if( heurdata->nlpverblevel >= 1 )
1525 {
1526 /* print the violation of the NLP solution candidate */
1527 if( SCIPgetNLPSolstat(heurdata->subscip) > SCIP_NLPSOLSTAT_FEASIBLE )
1528 {
1529 SCIP_SOL* sol;
1530 SCIP_Bool feasible;
1531
1532 sol = NULL;
1533 SCIP_CALL( createSolFromNLP(scip, heur, &sol, authorheur) );
1534
1535 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "subnlp solution is infeasible\n");
1536
1537 /* print the infeasibilities to stdout */
1538 SCIP_CALL( SCIPcheckSol(scip, sol, TRUE, TRUE, TRUE, FALSE, TRUE, &feasible) );
1539
1540 SCIP_CALL( SCIPfreeSol(scip, &sol) );
1541 }
1542 else if( heurdata->nlpverblevel >= 1
1543 && !SCIPisLE(scip, SCIPgetNLPObjval(heurdata->subscip), SCIPgetObjlimit(heurdata->subscip)) )
1544 {
1545 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "subnlp solution objval %e is above the objlimit %e\n",
1546 SCIPgetNLPObjval(heurdata->subscip), SCIPgetObjlimit(heurdata->subscip));
1547 }
1548 }
1549
1550 CLEANUP:
1551 if( heurdata->subscip != NULL )
1552 {
1553 SCIP_CALL( SCIPfreeTransform(heurdata->subscip) );
1554 if( tighttolerances )
1555 {
1556 SCIP_Real sumepsilon;
1557
1558 /* reset feasibility tolerance of sub-SCIP */
1559 SCIP_CALL( SCIPsetRealParam(heurdata->subscip, "numerics/feastol", SCIPfeastol(scip)) );
1560 SCIP_CALL( SCIPsetRealParam(heurdata->subscip, "numerics/epsilon", SCIPepsilon(scip)) );
1561 SCIP_CALL( SCIPgetRealParam(scip, "numerics/sumepsilon", &sumepsilon) );
1562 SCIP_CALL( SCIPsetRealParam(heurdata->subscip, "numerics/sumepsilon", sumepsilon) );
1563
1564 /* reset presolve to subnlp defaults (see createSubSCIP) */
1565 SCIP_CALL( SCIPsetPresolving(heurdata->subscip, SCIP_PARAMSETTING_DEFAULT, TRUE) );
1566 if( !SCIPisParamFixed(heurdata->subscip, "constraints/components/maxprerounds") )
1567 {
1568 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "constraints/components/maxprerounds", 0) );
1569 }
1570 SCIP_CALL( SCIPresetParam(heurdata->subscip, "constraints/linear/aggregatevariables") );
1571 }
1572 }
1573
1574 if( iterused != NULL && *iterused == 0 )
1575 *iterused = 1;
1576
1577 return SCIP_OKAY;
1578 }
1579
1580
1581 /** adds a set covering or bound disjunction constraint to the original problem */
1582 static
forbidFixation(SCIP * scip,SCIP_HEURDATA * heurdata)1583 SCIP_RETCODE forbidFixation(
1584 SCIP* scip, /**< SCIP data structure */
1585 SCIP_HEURDATA* heurdata /**< heuristic data */
1586 )
1587 {
1588 SCIP_VAR** subvars;
1589 int nsubvars;
1590 int nsubbinvars;
1591 int nsubintvars;
1592 SCIP_VAR* var;
1593 SCIP_VAR* subvar;
1594 SCIP_CONS* cons;
1595 SCIP_VAR** consvars;
1596 int nconsvars;
1597 char name[SCIP_MAXSTRLEN];
1598 int i;
1599 SCIP_Real fixval;
1600
1601 assert(scip != NULL);
1602
1603 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) );
1604 assert(nsubvars == heurdata->nsubvars);
1605
1606 if( nsubbinvars == 0 && nsubintvars == 0 )
1607 {
1608 /* If we did not fix any discrete variables but found the "sub"CIP infeasible, then also the CIP is infeasible. */
1609 SCIPdebugMsg(scip, "heur_subnlp found subCIP infeasible after fixing no variables, something is strange here...\n");
1610 return SCIP_OKAY;
1611 }
1612
1613 /* initialize */
1614 cons = NULL;
1615 consvars = NULL;
1616
1617 /* create constraint name */
1618 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "subnlp_cutoff");
1619
1620 /* if all discrete variables in the CIP are binary, then we create a set covering constraint
1621 * sum_{x_i fixed at 0} x_i + sum_{x_i fixed at 1} ~x_i >= 1
1622 */
1623 if( nsubintvars == 0 )
1624 {
1625 /* allocate memory for constraint variables */
1626 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nsubbinvars) );
1627
1628 /* get fixations of discrete variables
1629 * to be sure, we take the values that were put into the subCIP before
1630 */
1631 nconsvars = 0;
1632 for( i = nsubbinvars - 1; i >= 0; --i )
1633 {
1634 subvar = subvars[i];
1635 assert(SCIPvarGetProbindex(subvar) == i);
1636
1637 var = heurdata->var_subscip2scip[i];
1638 assert(var != NULL || SCIPisEQ(scip, SCIPvarGetLbGlobal(subvar), SCIPvarGetUbGlobal(subvar))); /* otherwise we should have exited in the variable fixation loop */
1639 if( var == NULL )
1640 continue;
1641
1642 fixval = SCIPvarGetLbGlobal(subvar);
1643 assert(fixval == SCIPvarGetUbGlobal(subvar)); /* variable should be fixed in sub-SCIP */ /*lint !e777*/
1644 assert(fixval == 0.0 || fixval == 1.0); /* we have rounded values before fixing */
1645
1646 if( fixval == 0.0 )
1647 {
1648 /* variable fixed at lower bound */
1649 consvars[nconsvars] = var;
1650 }
1651 else
1652 {
1653 SCIP_CALL( SCIPgetNegatedVar(scip, var, &consvars[nconsvars]) );
1654 }
1655
1656 ++nconsvars;
1657 }
1658
1659 /* create conflict constraint
1660 * In undercover, ConsLogicor is used, since then the inequality is not added to the LP.
1661 * However, I may want to use Setcover to avoid that the same fixing is computed by some LP based heuristic again.
1662 */
1663 SCIP_CALL( SCIPcreateConsSetcover(scip, &cons, name, nconsvars, consvars,
1664 FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
1665 }
1666 else
1667 {
1668 /* if there are also integer variable, then create a bound disjunction constraint
1669 * x_1 >= fixval_1 + 1 || x_1 <= fixval_1 - 1 || x_2 >= fixval_2 + 1 || x_2 <= fixval_2 - 1 || ...
1670 */
1671 SCIP_BOUNDTYPE* boundtypes;
1672 SCIP_Real* bounds;
1673
1674 /* allocate memory for constraint variables, boundtypes, and bounds
1675 * (there should be at most two literals for each integer variable)
1676 */
1677 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nsubbinvars + 2*nsubintvars) );
1678 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, nsubbinvars + 2*nsubintvars) );
1679 SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nsubbinvars + 2*nsubintvars) );
1680
1681 /* get fixations of discrete variables
1682 * to be sure, we take the values that were put into the subCIP before
1683 */
1684 nconsvars = 0;
1685 for( i = nsubbinvars + nsubintvars - 1; i >= 0; --i )
1686 {
1687 subvar = subvars[i];
1688 assert(SCIPvarGetProbindex(subvar) == i);
1689
1690 var = heurdata->var_subscip2scip[i];
1691 assert(var != NULL || SCIPisEQ(scip, SCIPvarGetLbGlobal(subvar), SCIPvarGetUbGlobal(subvar))); /* otherwise we should have exited in the variable fixation loop */
1692
1693 if( var == NULL )
1694 continue;
1695
1696 fixval = SCIPvarGetLbGlobal(subvar);
1697 assert(fixval == SCIPvarGetUbGlobal(subvar)); /* variable should be fixed in sub-SCIP */ /*lint !e777*/
1698 assert(SCIPceil(scip, fixval - 0.5) == fixval); /* we have rounded values before fixing */ /*lint !e777*/
1699 assert(SCIPvarGetType(var) != SCIP_VARTYPE_BINARY || SCIPvarGetLbGlobal(var) == fixval || SCIPvarGetUbGlobal(var) == fixval); /* for binaries, the fixval should be either 0.0 or 1.0 */ /*lint !e777*/
1700
1701 if( SCIPvarGetLbGlobal(var) < fixval )
1702 {
1703 assert(nconsvars < nsubbinvars + 2*nsubintvars);
1704
1705 /* literal x_i <= fixval-1 */
1706 boundtypes[nconsvars] = SCIP_BOUNDTYPE_UPPER;
1707 bounds[nconsvars] = fixval - 1.0;
1708 consvars[nconsvars] = var;
1709 ++nconsvars;
1710 }
1711
1712 if( SCIPvarGetUbGlobal(var) > fixval )
1713 {
1714 assert(nconsvars < nsubbinvars + 2*nsubintvars);
1715
1716 /* literal x_i >= fixval+1 */
1717 boundtypes[nconsvars] = SCIP_BOUNDTYPE_LOWER;
1718 bounds[nconsvars] = fixval + 1.0;
1719 consvars[nconsvars] = var;
1720 ++nconsvars;
1721 }
1722 }
1723
1724 /* create conflict constraint */
1725 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, name, nconsvars, consvars, boundtypes, bounds,
1726 FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
1727
1728 SCIPfreeBufferArray(scip, &bounds);
1729 SCIPfreeBufferArray(scip, &boundtypes);
1730 SCIPfreeBufferArray(scip, &consvars);
1731 }
1732
1733 /* add and release constraint if created successfully */
1734 if( cons != NULL )
1735 {
1736 SCIPdebugMsg(scip, "adding constraint to forbid fixation in main problem\n");
1737 /* SCIPdebugPrintCons(scip, cons, NULL); */
1738 SCIP_CALL( SCIPaddCons(scip, cons) );
1739 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1740 }
1741
1742 /* free memory */
1743 SCIPfreeBufferArrayNull(scip, &consvars);
1744
1745 return SCIP_OKAY;
1746 }
1747
1748
1749 /** main procedure of the subNLP heuristic */
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)1750 SCIP_RETCODE SCIPapplyHeurSubNlp(
1751 SCIP* scip, /**< original SCIP data structure */
1752 SCIP_HEUR* heur, /**< heuristic data structure */
1753 SCIP_RESULT* result, /**< pointer to store result of: did not run, solution found, no solution found, or fixing is infeasible (cutoff) */
1754 SCIP_SOL* refpoint, /**< point to take fixation of discrete variables from, and startpoint for NLP solver; if NULL, then LP solution is used */
1755 SCIP_Longint itercontingent, /**< iteration limit for NLP solver, or -1 for default of NLP heuristic */
1756 SCIP_Real timelimit, /**< time limit for NLP solver */
1757 SCIP_Real minimprove, /**< desired minimal relative improvement in objective function value */
1758 SCIP_Longint* iterused, /**< buffer to store number of iterations used by NLP solver, or NULL if not of interest */
1759 SCIP_SOL* resultsol /**< a solution where to store found solution values, if any, or NULL if to try adding to SCIP */
1760 )
1761 {
1762 SCIP_HEURDATA* heurdata;
1763 SCIP_VAR* var;
1764 SCIP_VAR* subvar;
1765 int i;
1766 SCIP_Real cutoff;
1767
1768 assert(scip != NULL);
1769 assert(heur != NULL);
1770
1771 /* get heuristic's data */
1772 heurdata = SCIPheurGetData(heur);
1773 assert(heurdata != NULL);
1774
1775 /* try to setup NLP if not tried before */
1776 if( heurdata->subscip == NULL && !heurdata->triedsetupsubscip )
1777 {
1778 SCIP_CALL( createSubSCIP(scip, heurdata) );
1779 }
1780
1781 *result = SCIP_DIDNOTRUN;
1782
1783 /* not initialized */
1784 if( heurdata->subscip == NULL )
1785 return SCIP_OKAY;
1786
1787 assert(heurdata->nsubvars > 0);
1788 assert(heurdata->var_subscip2scip != NULL);
1789 assert(!SCIPisTransformed(heurdata->subscip));
1790
1791 if( iterused != NULL )
1792 *iterused = 0;
1793
1794 /* fix discrete variables in sub-SCIP */
1795 if( SCIPgetNBinVars(heurdata->subscip) || SCIPgetNIntVars(heurdata->subscip) )
1796 {
1797 SCIP_Real fixval;
1798 SCIP_VAR** subvars;
1799 int nsubvars;
1800 int nsubbinvars;
1801 int nsubintvars;
1802
1803 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) );
1804 assert(nsubvars == heurdata->nsubvars);
1805
1806 /* fix discrete variables to values in startpoint */
1807 for( i = nsubbinvars + nsubintvars - 1; i >= 0; --i )
1808 {
1809 subvar = subvars[i];
1810 assert(SCIPvarGetProbindex(subvar) == i);
1811
1812 var = heurdata->var_subscip2scip[i];
1813 assert(var != NULL);
1814
1815 /* at this point, variables in subscip and in our scip should have same bounds */
1816 assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(subvar), SCIPvarGetLbGlobal(var)));
1817 assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(subvar), SCIPvarGetUbGlobal(var)));
1818
1819 fixval = SCIPgetSolVal(scip, refpoint, var);
1820
1821 /* only run heuristic on integer feasible points */
1822 if( !SCIPisFeasIntegral(scip, fixval) )
1823 {
1824 if( refpoint || SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
1825 {
1826 SCIPdebugMsg(scip, "skip NLP heuristic because start candidate not integer feasible: var <%s> has value %g\n", SCIPvarGetName(var), fixval);
1827 goto CLEANUP;
1828 }
1829 /* otherwise we desperately wanna run the NLP heur, so we continue and round what we have */
1830 }
1831 /* if we do not really have a startpoint, then we should take care that we do not fix variables to very large values
1832 * thus, we set to 0.0 here and project on bounds below
1833 */
1834 if( REALABS(fixval) > 1E+10 && !refpoint && SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
1835 fixval = 0.0;
1836
1837 /* fixing variables to infinity causes problems, we should not have been passed such a solution as refpoint */
1838 assert(!SCIPisInfinity(scip, REALABS(fixval)));
1839
1840 /* round fractional variables to the nearest integer,
1841 * use exact integral value, if the variable is only integral within numerical tolerances
1842 */
1843 fixval = SCIPfloor(scip, fixval+0.5);
1844
1845 /* adjust value to the global bounds of the corresponding SCIP variable */
1846 fixval = MAX(fixval, SCIPvarGetLbGlobal(var)); /*lint !e666*/
1847 fixval = MIN(fixval, SCIPvarGetUbGlobal(var)); /*lint !e666*/
1848
1849 /* SCIPdebugMsg(scip, "fix variable <%s> to %g\n", SCIPvarGetName(var), fixval); */
1850 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, fixval) );
1851 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, fixval) );
1852 }
1853 }
1854
1855 /* if there is already a solution, add an objective cutoff in sub-SCIP */
1856 if( SCIPgetNSols(scip) > 0 )
1857 {
1858 SCIP_Real upperbound;
1859
1860 assert( !SCIPisInfinity(scip, SCIPgetUpperbound(scip)) );
1861
1862 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
1863
1864 if( !SCIPisInfinity(scip, -SCIPgetLowerbound(scip)) )
1865 {
1866 cutoff = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
1867 }
1868 else
1869 {
1870 if( SCIPgetUpperbound(scip) >= 0 )
1871 cutoff = ( 1.0 - minimprove ) * SCIPgetUpperbound(scip);
1872 else
1873 cutoff = ( 1.0 + minimprove ) * SCIPgetUpperbound(scip);
1874 }
1875 cutoff = MIN(upperbound, cutoff);
1876 SCIP_CALL( SCIPsetObjlimit(heurdata->subscip, cutoff) );
1877 SCIPdebugMsg(scip, "set objective limit %g\n", cutoff);
1878 }
1879 else
1880 cutoff = SCIPinfinity(scip);
1881
1882 /* solve the subNLP and try to add solution to SCIP */
1883 SCIP_CALL( solveSubNLP(scip, heur, result, refpoint, itercontingent, timelimit, iterused, FALSE, resultsol) );
1884
1885 if( heurdata->subscip == NULL )
1886 {
1887 /* something horrible must have happened that we decided to give up completely on this heuristic */
1888 *result = SCIP_DIDNOTFIND;
1889 return SCIP_OKAY;
1890 }
1891 assert(!SCIPisTransformed(heurdata->subscip));
1892
1893 if( *result == SCIP_CUTOFF )
1894 {
1895 if( heurdata->subscipisvalid && SCIPgetNActivePricers(scip) == 0 )
1896 {
1897 /* if the subNLP is valid and turned out to be globally infeasible (i.e., proven by SCIP), then we forbid this fixation in the main problem */
1898 if( SCIPisInfinity(scip, cutoff) && heurdata->forbidfixings )
1899 {
1900 SCIP_CALL( forbidFixation(scip, heurdata) );
1901 }
1902 }
1903 else
1904 {
1905 /* if the subNLP turned out to be globally infeasible but we are not sure that we have a valid copy, we change to DIDNOTFIND */
1906 *result = SCIP_DIDNOTFIND;
1907 }
1908 }
1909
1910 CLEANUP:
1911 /* if the heuristic was applied before solving has started, then destroy subSCIP, since EXITSOL may not be called
1912 * also if keepcopy is disabled, then destroy subSCIP
1913 */
1914 if( SCIPgetStage(scip) < SCIP_STAGE_SOLVING || !heurdata->keepcopy )
1915 {
1916 SCIP_CALL( freeSubSCIP(scip, heurdata) );
1917 heurdata->triedsetupsubscip = FALSE;
1918 }
1919 else if( SCIPgetNBinVars(heurdata->subscip) || SCIPgetNIntVars(heurdata->subscip) )
1920 {
1921 /* undo fixing of discrete variables in sub-SCIP */
1922 SCIP_VAR** subvars;
1923 int nsubvars;
1924 int nsubbinvars;
1925 int nsubintvars;
1926
1927 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) );
1928 assert(nsubvars == heurdata->nsubvars);
1929
1930 /* set bounds of discrete variables to original values */
1931 for( i = nsubbinvars + nsubintvars - 1; i >= 0; --i )
1932 {
1933 subvar = subvars[i];
1934 assert(SCIPvarGetProbindex(subvar) == i);
1935
1936 var = heurdata->var_subscip2scip[i];
1937 assert(var != NULL);
1938
1939 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, SCIPvarGetLbGlobal(var)) );
1940 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, SCIPvarGetUbGlobal(var)) );
1941 }
1942 }
1943
1944 return SCIP_OKAY;
1945 }
1946
1947 /** for a given solution, resolves the corresponding subNLP and updates solution values for continuous variables, if NLP solution is feasible in original problem */
SCIPresolveSolHeurSubNlp(SCIP * scip,SCIP_HEUR * heur,SCIP_SOL * sol,SCIP_Bool * success,SCIP_Longint itercontingent,SCIP_Real timelimit)1948 SCIP_RETCODE SCIPresolveSolHeurSubNlp(
1949 SCIP* scip, /**< original SCIP data structure */
1950 SCIP_HEUR* heur, /**< heuristic data structure */
1951 SCIP_SOL* sol, /**< solution for which to solve NLP, and where to store resolved solution values */
1952 SCIP_Bool* success, /**< buffer where to store whether a feasible solution was found */
1953 SCIP_Longint itercontingent, /**< iteration limit for NLP solver, or -1 for default of NLP heuristic */
1954 SCIP_Real timelimit /**< time limit for NLP solver */
1955 )
1956 {
1957 SCIP_HEURDATA* heurdata;
1958 SCIP_VAR* var;
1959 SCIP_VAR* subvar;
1960 int i;
1961 SCIP_Real cutoff;
1962 SCIP_RESULT result;
1963
1964 assert(scip != NULL);
1965 assert(heur != NULL);
1966 assert(sol != NULL);
1967 assert(success != NULL);
1968
1969 /* get heuristic's data */
1970 heurdata = SCIPheurGetData(heur);
1971 assert(heurdata != NULL);
1972
1973 /* try to setup NLP if not tried before */
1974 if( heurdata->subscip == NULL && !heurdata->triedsetupsubscip )
1975 {
1976 SCIP_CALL( createSubSCIP(scip, heurdata) );
1977 }
1978
1979 *success = FALSE;
1980
1981 /* not initialized */
1982 if( heurdata->subscip == NULL )
1983 return SCIP_OKAY;
1984
1985 assert(heurdata->nsubvars > 0);
1986 assert(heurdata->var_subscip2scip != NULL);
1987 assert(!SCIPisTransformed(heurdata->subscip));
1988
1989 result = SCIP_DIDNOTRUN;
1990
1991 /* fix discrete variables in subSCIP */
1992 if( SCIPgetNBinVars(heurdata->subscip) || SCIPgetNIntVars(heurdata->subscip) )
1993 {
1994 SCIP_Real fixval;
1995 SCIP_VAR** subvars;
1996 int nsubvars;
1997 int nsubbinvars;
1998 int nsubintvars;
1999
2000 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) );
2001 assert(nsubvars == heurdata->nsubvars);
2002
2003 /* fix discrete variables to values in startpoint */
2004 for( i = nsubbinvars + nsubintvars - 1; i >= 0; --i )
2005 {
2006 subvar = subvars[i];
2007 assert(SCIPvarGetProbindex(subvar) == i);
2008
2009 var = heurdata->var_subscip2scip[i];
2010 assert(var != NULL);
2011
2012 /* at this point, variables in subscip and in our scip should have same bounds */
2013 assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(subvar), SCIPvarGetLbGlobal(var)));
2014 assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(subvar), SCIPvarGetUbGlobal(var)));
2015
2016 fixval = SCIPgetSolVal(scip, sol, var);
2017
2018 /* only run heuristic on integer feasible points */
2019 if( !SCIPisFeasIntegral(scip, fixval) )
2020 {
2021 SCIPdebugMsg(scip, "skip NLP heuristic because start candidate not integer feasible: var <%s> has value %g\n", SCIPvarGetName(var), fixval);
2022 goto CLEANUP;
2023 /* otherwise we desperately want to run the NLP heur, so we continue and round what we have */
2024 }
2025
2026 /* round fractional variables to the nearest integer,
2027 * use exact integral value, if the variable is only integral within numerical tolerances
2028 */
2029 fixval = SCIPround(scip, fixval);
2030
2031 /* adjust value to the global bounds of the corresponding SCIP variable */
2032 fixval = MAX(fixval, SCIPvarGetLbGlobal(var)); /*lint !e666*/
2033 fixval = MIN(fixval, SCIPvarGetUbGlobal(var)); /*lint !e666*/
2034
2035 /* SCIPdebugMsg(scip, "fix variable <%s> to %g\n", SCIPvarGetName(var), fixval); */
2036 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, fixval) );
2037 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, fixval) );
2038 }
2039 }
2040
2041 /* if there is already a solution, add an objective cutoff in subSCIP */
2042 cutoff = SCIPgetSolOrigObj(scip, sol);
2043 if( SCIPgetObjsense(scip) == SCIP_OBJSENSE_MINIMIZE )
2044 {
2045 cutoff += 0.01 * REALABS(cutoff);
2046 }
2047 else
2048 {
2049 cutoff -= 0.01 * REALABS(cutoff);
2050 }
2051 cutoff = SCIPtransformObj(scip, cutoff);
2052 SCIPdebugMsg(scip, "set objective limit %g\n", cutoff);
2053 SCIP_CALL( SCIPsetObjlimit(heurdata->subscip, cutoff) );
2054
2055 /* solve the subNLP and try to add solution to SCIP */
2056 SCIP_CALL( solveSubNLP(scip, heur, &result, sol, itercontingent, timelimit, NULL, FALSE, sol) );
2057
2058 if( heurdata->subscip == NULL )
2059 {
2060 /* something horrible must have happened that we decided to give up completely on this heuristic */
2061 return SCIP_OKAY;
2062 }
2063 assert(!SCIPisTransformed(heurdata->subscip));
2064
2065 if( result == SCIP_FOUNDSOL )
2066 *success = TRUE;
2067
2068 CLEANUP:
2069 /* if the heuristic was applied before solving has started, then destroy subSCIP, since EXITSOL may not be called
2070 * also if keepcopy is not set, then destroy subSCIP
2071 */
2072 if( SCIPgetStage(scip) < SCIP_STAGE_SOLVING || !heurdata->keepcopy )
2073 {
2074 SCIP_CALL( freeSubSCIP(scip, heurdata) );
2075 heurdata->triedsetupsubscip = FALSE;
2076 }
2077 else if( SCIPgetNBinVars(heurdata->subscip) || SCIPgetNIntVars(heurdata->subscip) )
2078 {
2079 /* undo fixing of discrete variables in subSCIP */
2080 SCIP_VAR** subvars;
2081 int nsubvars;
2082 int nsubbinvars;
2083 int nsubintvars;
2084
2085 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) );
2086 assert(nsubvars == heurdata->nsubvars);
2087
2088 /* set bounds of discrete variables to original values */
2089 for( i = nsubbinvars + nsubintvars - 1; i >= 0; --i )
2090 {
2091 subvar = subvars[i];
2092 assert(SCIPvarGetProbindex(subvar) == i);
2093
2094 var = heurdata->var_subscip2scip[i];
2095 assert(var != NULL);
2096
2097 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, SCIPvarGetLbGlobal(var)) );
2098 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, SCIPvarGetUbGlobal(var)) );
2099 }
2100 }
2101
2102 return SCIP_OKAY;
2103 }
2104
2105 /*
2106 * Callback methods of primal heuristic
2107 */
2108
2109 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
2110 static
SCIP_DECL_HEURCOPY(heurCopySubNlp)2111 SCIP_DECL_HEURCOPY(heurCopySubNlp)
2112 { /*lint --e{715}*/
2113 assert(scip != NULL);
2114 assert(heur != NULL);
2115 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2116
2117 /* call inclusion method of primal heuristic */
2118 SCIP_CALL( SCIPincludeHeurSubNlp(scip) );
2119
2120 return SCIP_OKAY;
2121 }
2122
2123 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
2124 static
SCIP_DECL_HEURFREE(heurFreeSubNlp)2125 SCIP_DECL_HEURFREE(heurFreeSubNlp)
2126 {
2127 SCIP_HEURDATA* heurdata;
2128 assert(scip != NULL);
2129 assert(heur != NULL);
2130
2131 heurdata = SCIPheurGetData(heur);
2132 assert(heurdata != NULL);
2133 assert(heurdata->subscip == NULL);
2134 assert(heurdata->var_subscip2scip == NULL);
2135 assert(heurdata->var_scip2subscip == NULL);
2136 assert(heurdata->startcand == NULL);
2137
2138 SCIPfreeBlockMemory(scip, &heurdata);
2139
2140 return SCIP_OKAY;
2141 }
2142
2143 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
2144 static
SCIP_DECL_HEURINITSOL(heurInitsolSubNlp)2145 SCIP_DECL_HEURINITSOL(heurInitsolSubNlp)
2146 {
2147 SCIP_HEURDATA* heurdata;
2148
2149 assert(scip != NULL);
2150 assert(heur != NULL);
2151
2152 /* skip setting up sub-SCIP if heuristic is disabled or we do not want to run the heuristic */
2153 if( SCIPheurGetFreq(heur) < 0 || !runHeuristic(scip) )
2154 return SCIP_OKAY;
2155
2156 heurdata = SCIPheurGetData(heur);
2157 assert(heurdata != NULL);
2158 assert(heurdata->subscip == NULL);
2159
2160 /* reset solution found counter */
2161 heurdata->nsolfound = 0;
2162
2163 if( heurdata->keepcopy )
2164 {
2165 /* create sub-SCIP for later use */
2166 SCIP_CALL( createSubSCIP(scip, heurdata) );
2167
2168 /* creating sub-SCIP may fail if the NLP solver interfaces did not copy into subscip */
2169 if( heurdata->subscip == NULL )
2170 return SCIP_OKAY;
2171 }
2172
2173 /* if the heuristic is called at the root node, we want to be called directly after the initial root LP solve */
2174 if( SCIPheurGetFreqofs(heur) == 0 )
2175 SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_DURINGLPLOOP | HEUR_TIMING);
2176
2177 return SCIP_OKAY;
2178 }
2179
2180 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
2181 static
SCIP_DECL_HEUREXITSOL(heurExitsolSubNlp)2182 SCIP_DECL_HEUREXITSOL(heurExitsolSubNlp)
2183 {
2184 SCIP_HEURDATA* heurdata;
2185 assert(scip != NULL);
2186 assert(heur != NULL);
2187
2188 /* get heuristic's data */
2189 heurdata = SCIPheurGetData(heur);
2190 assert(heurdata != NULL);
2191
2192 if( heurdata->subscip != NULL )
2193 {
2194 SCIP_CALL( freeSubSCIP(scip, heurdata) );
2195 }
2196
2197 /* free start candidate */
2198 if( heurdata->startcand != NULL )
2199 {
2200 SCIP_CALL( SCIPfreeSol(scip, &heurdata->startcand) );
2201 }
2202
2203 SCIPheurSetTimingmask(heur, HEUR_TIMING);
2204
2205 /* reset some flags and counters */
2206 heurdata->triedsetupsubscip = FALSE;
2207 heurdata->comblinearconsadded = FALSE;
2208 heurdata->contlinearconsadded = FALSE;
2209 heurdata->nseriousnlpierror = 0;
2210 heurdata->iterused = 0;
2211
2212 return SCIP_OKAY;
2213 }
2214
2215
2216 /** execution method of primal heuristic */
2217 static
SCIP_DECL_HEUREXEC(heurExecSubNlp)2218 SCIP_DECL_HEUREXEC(heurExecSubNlp)
2219 { /*lint --e{666,715}*/
2220 SCIP_HEURDATA* heurdata;
2221 SCIP_Longint itercontingent;
2222 SCIP_Real timelimit;
2223 SCIP_Longint iterused;
2224
2225 assert(scip != NULL);
2226 assert(heur != NULL);
2227
2228 /* obviously, we did not do anything yet */
2229 *result = SCIP_DIDNOTRUN;
2230
2231 /* get heuristic's data */
2232 heurdata = SCIPheurGetData(heur);
2233 assert(heurdata != NULL);
2234
2235 /* if keepcopy and subscip == NULL, then InitsolNlp decided that we do not need an NLP solver,
2236 * probably because we do not have nonlinear continuous or implicit integer variables
2237 * if triedsetupsubscip and subscip == NULL, then we run the heuristic already, but gave up due to some serious error
2238 * in both cases, we do not want to run
2239 *
2240 * otherwise, we continue and let SCIPapplyHeurSubNlp try to create subscip
2241 */
2242 if( heurdata->subscip == NULL && (heurdata->keepcopy || heurdata->triedsetupsubscip) )
2243 return SCIP_OKAY;
2244
2245 /* if we recreate the subSCIP in every run, then also check whether we want to run the heuristic at all */
2246 if( !heurdata->keepcopy && !runHeuristic(scip) )
2247 return SCIP_OKAY;
2248
2249 if( heurdata->startcand == NULL )
2250 {
2251 /* if no start candidate is given, we consider the LP solution of the current node */
2252
2253 /* however, if the node was already detected to be infeasible, then there is no point to look at its LP solution */
2254 if( nodeinfeasible )
2255 return SCIP_OKAY;
2256
2257 /* at least if we are not called the first time, we call the heuristic only if an optimal LP solution is available
2258 * if we are called the first time and the LP is unbounded, then we are quite desperate and still give the NLP a try
2259 */
2260 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
2261 {
2262 if( SCIPgetNNodes(scip) > 1 || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
2263 {
2264 *result = SCIP_DELAYED;
2265 SCIPdebugMsg(scip, "NLP heuristic delayed because no start candidate given and no LP solution available; LP status = %d\n", SCIPgetLPSolstat(scip));
2266 return SCIP_OKAY;
2267 }
2268 else
2269 {
2270 SCIPdebugMsg(scip, "LP is unbounded in root node, so we are quite desperate; run NLP heuristic and pray\n");
2271 }
2272 }
2273 else if( SCIPgetNLPBranchCands(scip) > 0 )
2274 {
2275 /* only call heuristic, if there are no fractional variables */
2276 *result = SCIP_DELAYED;
2277 SCIPdebugMsg(scip, "NLP heuristic delayed because no start candidate given and current LP solution is fractional\n");
2278 return SCIP_OKAY;
2279 }
2280 else if( !SCIPisInfinity(scip, SCIPgetPrimalbound(scip)) && SCIPisEQ(scip, SCIPgetLocalDualbound(scip), SCIPgetPrimalbound(scip)) )
2281 {
2282 /* only call heuristic, if there is still room for improvement in the current node */
2283 SCIPdebugMsg(scip, "NLP heuristic delayed because lower and upper bound coincide in current node\n");
2284 return SCIP_OKAY;
2285 }
2286 SCIPdebugMsg(scip, "using current LP solution as startcand\n");
2287 }
2288 else
2289 {
2290 SCIPdebugMsg(scip, "have startcand from heur %s\n", SCIPsolGetHeur(heurdata->startcand) ? SCIPheurGetName(SCIPsolGetHeur(heurdata->startcand)) : "NULL");
2291 }
2292
2293 if( !heurdata->runalways )
2294 {
2295 /* check if enough nodes have been processed so that we want to run the heuristic again */
2296
2297 /* compute the contingent on number of iterations that the NLP solver is allowed to use
2298 * we make it depending on the current number of processed nodes
2299 */
2300 itercontingent = (SCIP_Longint)(heurdata->iterquot * SCIPgetNNodes(scip));
2301
2302 /* weight by previous success of heuristic */
2303 itercontingent = (SCIP_Longint)(itercontingent * 3.0 * (heurdata->nsolfound+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
2304 /* add the fixed offset */
2305 itercontingent += heurdata->iteroffset;
2306 /* subtract the number of iterations used so far */
2307 itercontingent -= heurdata->iterused;
2308
2309 if( itercontingent < heurdata->itermin )
2310 {
2311 /* not enough iterations left to start NLP solver */
2312 SCIPdebugMsg(scip, "skip NLP heuristic; contingent=%" SCIP_LONGINT_FORMAT "; minimal number of iterations=%d; success ratio=%g\n",
2313 itercontingent, heurdata->itermin, (heurdata->nsolfound+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
2314 return SCIP_OKAY;
2315 }
2316
2317 /* enforce user given iteration limit, if given */
2318 if( heurdata->nlpiterlimit > 0 )
2319 itercontingent = MIN(itercontingent, heurdata->nlpiterlimit);
2320 }
2321 else
2322 {
2323 itercontingent = -1;
2324 }
2325
2326 /* check whether there is enough time left */
2327 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
2328 if( !SCIPisInfinity(scip, timelimit) )
2329 {
2330 timelimit -= SCIPgetSolvingTime(scip);
2331 if( timelimit <= 0.0 )
2332 {
2333 SCIPdebugMsg(scip, "skip NLP heuristic; no time left\n");
2334 return SCIP_OKAY;
2335 }
2336 }
2337 /* enforce user given time limit, if given */
2338 if( heurdata->nlptimelimit > 0 )
2339 timelimit = MIN(heurdata->nlptimelimit, timelimit);
2340
2341 /* so far we have not found any solution, but now we are willing to search for one */
2342 *result = SCIP_DIDNOTFIND;
2343
2344 if( heurdata->nlpverblevel >= 1 )
2345 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "calling subnlp heuristic\n");
2346
2347 SCIP_CALL( SCIPapplyHeurSubNlp(scip, heur, result, heurdata->startcand, itercontingent, timelimit,
2348 heurdata->minimprove, &iterused, NULL) );
2349 heurdata->iterused += iterused;
2350
2351 /* SCIP does not like cutoff as return, so we say didnotfind, since we did not find a solution */
2352 if( *result == SCIP_CUTOFF )
2353 *result = SCIP_DIDNOTFIND;
2354
2355 /* forget startcand */
2356 if( heurdata->startcand != NULL )
2357 {
2358 SCIP_CALL( SCIPfreeSol(scip, &heurdata->startcand) );
2359 }
2360
2361 /* reset timing, if it was changed temporary (at the root node) */
2362 if( heurtiming != HEUR_TIMING )
2363 SCIPheurSetTimingmask(heur, HEUR_TIMING);
2364
2365 return SCIP_OKAY;
2366 }
2367
2368
2369 /*
2370 * primal heuristic specific interface methods
2371 */
2372
2373 /** creates the NLP local search primal heuristic and includes it in SCIP */
SCIPincludeHeurSubNlp(SCIP * scip)2374 SCIP_RETCODE SCIPincludeHeurSubNlp(
2375 SCIP* scip /**< SCIP data structure */
2376 )
2377 {
2378 SCIP_HEURDATA* heurdata;
2379 SCIP_HEUR* heur;
2380
2381 /* create Nlp primal heuristic data */
2382 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2383 BMSclearMemory(heurdata);
2384
2385 /* include variable event handler */
2386 heurdata->eventhdlr = NULL;
2387 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &heurdata->eventhdlr, HEUR_NAME, "propagates a global bound change to the sub-SCIP",
2388 processVarEvent, NULL) );
2389 assert(heurdata->eventhdlr != NULL);
2390
2391 /* include primal heuristic */
2392 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
2393 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
2394 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecSubNlp, heurdata) );
2395
2396 assert(heur != NULL);
2397
2398 /* set non-NULL pointers to callback methods */
2399 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopySubNlp) );
2400 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeSubNlp) );
2401 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolSubNlp) );
2402 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolSubNlp) );
2403
2404 /* add Nlp primal heuristic parameters */
2405 SCIP_CALL( SCIPaddIntParam (scip, "heuristics/" HEUR_NAME "/nlpverblevel",
2406 "verbosity level of NLP solver",
2407 &heurdata->nlpverblevel, FALSE, 0, 0, INT_MAX, NULL, NULL) );
2408
2409 SCIP_CALL( SCIPaddIntParam (scip, "heuristics/" HEUR_NAME "/nlpiterlimit",
2410 "iteration limit of NLP solver; 0 to use solver default",
2411 &heurdata->nlpiterlimit, FALSE, 0, 0, INT_MAX, NULL, NULL) );
2412
2413 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nlptimelimit",
2414 "time limit of NLP solver; 0 to use solver default",
2415 &heurdata->nlptimelimit, FALSE, 0.0, 0.0, SCIPinfinity(scip), NULL, NULL) );
2416
2417 SCIP_CALL( SCIPaddStringParam(scip, "heuristics/" HEUR_NAME "/nlpoptfile",
2418 "name of an NLP solver specific options file",
2419 &heurdata->nlpoptfile, TRUE, "", NULL, NULL) );
2420
2421 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/resolvetolfactor",
2422 "if SCIP does not accept a NLP feasible solution, resolve NLP with feas. tolerance reduced by this factor (set to 1.0 to turn off resolve)",
2423 &heurdata->resolvetolfactor, TRUE, 0.001, 0.0, 1.0, NULL, NULL) );
2424
2425 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/resolvefromscratch",
2426 "should the NLP resolve be started from the original starting point or the infeasible solution?",
2427 &heurdata->resolvefromscratch, TRUE, TRUE, NULL, NULL) );
2428
2429 SCIP_CALL( SCIPaddIntParam (scip, "heuristics/" HEUR_NAME "/iteroffset",
2430 "number of iterations added to the contingent of the total number of iterations",
2431 &heurdata->iteroffset, FALSE, 500, 0, INT_MAX, NULL, NULL) );
2432
2433 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/iterquotient",
2434 "contingent of NLP iterations in relation to the number of nodes in SCIP",
2435 &heurdata->iterquot, FALSE, 0.1, 0.0, SCIPinfinity(scip), NULL, NULL) );
2436
2437 SCIP_CALL( SCIPaddIntParam (scip, "heuristics/" HEUR_NAME "/itermin",
2438 "contingent of NLP iterations in relation to the number of nodes in SCIP",
2439 &heurdata->itermin, FALSE, 300, 0, INT_MAX, NULL, NULL) );
2440
2441 SCIP_CALL( SCIPaddBoolParam (scip, "heuristics/" HEUR_NAME "/runalways",
2442 "whether to run NLP heuristic always if starting point available (does not use iteroffset,iterquot,itermin)",
2443 &heurdata->runalways, FALSE, FALSE, NULL, NULL) );
2444
2445 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
2446 "factor by which NLP heuristic should at least improve the incumbent",
2447 &heurdata->minimprove, TRUE, 0.01, 0.0, 1.0, NULL, NULL) );
2448
2449 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxpresolverounds",
2450 "limit on number of presolve rounds in sub-SCIP (-1 for unlimited, 0 for no presolve)",
2451 &heurdata->maxpresolverounds, TRUE, -1, -1, INT_MAX, NULL, NULL) );
2452
2453 SCIP_CALL( SCIPaddBoolParam (scip, "heuristics/" HEUR_NAME "/forbidfixings",
2454 "whether to add constraints that forbid specific fixings that turned out to be infeasible",
2455 &heurdata->forbidfixings, FALSE, TRUE, NULL, NULL) );
2456
2457 SCIP_CALL( SCIPaddBoolParam (scip, "heuristics/" HEUR_NAME "/keepcopy",
2458 "whether to keep SCIP copy or to create new copy each time heuristic is applied",
2459 &heurdata->keepcopy, TRUE, TRUE, NULL, NULL) );
2460
2461 return SCIP_OKAY;
2462 }
2463
2464 /** adds all known linear constraint to the NLP, if initialized and not done already
2465 * This function is temporary and will hopefully become obsolete in the near future.
2466 */
SCIPaddLinearConsToNlpHeurSubNlp(SCIP * scip,SCIP_HEUR * heur,SCIP_Bool addcombconss,SCIP_Bool addcontconss)2467 SCIP_RETCODE SCIPaddLinearConsToNlpHeurSubNlp(
2468 SCIP* scip, /**< original SCIP data structure */
2469 SCIP_HEUR* heur, /**< heuristic data structure */
2470 SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints, i.e., linear constraints that involve only discrete variables */
2471 SCIP_Bool addcontconss /**< whether to add continuous linear constraints, i.e., linear constraints that involve not only discrete variables */
2472 )
2473 {
2474 SCIP_HEURDATA* heurdata;
2475
2476 assert(scip != NULL);
2477 assert(heur != NULL);
2478 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2479
2480 heurdata = SCIPheurGetData(heur);
2481 assert(heurdata != NULL);
2482
2483 /* return, if nothing to do */
2484 if( (!addcombconss || heurdata->comblinearconsadded) && (!addcontconss || heurdata->contlinearconsadded) )
2485 return SCIP_OKAY;
2486
2487 SCIP_CALL( addLinearConstraintsToNlp(scip,
2488 addcombconss && !heurdata->comblinearconsadded,
2489 addcontconss && !heurdata->contlinearconsadded) );
2490
2491 heurdata->comblinearconsadded |= addcombconss;
2492 heurdata->contlinearconsadded |= addcontconss;
2493
2494 return SCIP_OKAY;
2495 }
2496
2497 /** updates the starting point for the NLP heuristic
2498 *
2499 * Is called by a constraint handler that handles nonlinear constraints when a check on feasibility of a solution fails.
2500 */
SCIPupdateStartpointHeurSubNlp(SCIP * scip,SCIP_HEUR * heur,SCIP_SOL * solcand,SCIP_Real violation)2501 SCIP_RETCODE SCIPupdateStartpointHeurSubNlp(
2502 SCIP* scip, /**< SCIP data structure */
2503 SCIP_HEUR* heur, /**< NLP heuristic */
2504 SCIP_SOL* solcand, /**< solution candidate */
2505 SCIP_Real violation /**< constraint violation of solution candidate */
2506 )
2507 {
2508 SCIP_HEURDATA* heurdata;
2509
2510 assert(scip != NULL);
2511 assert(heur != NULL);
2512 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2513 assert(solcand != NULL);
2514 assert(SCIPisPositive(scip, violation));
2515
2516 /* too early or the game is over already: no more interest in starting points */
2517 if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING )
2518 return SCIP_OKAY;
2519
2520 heurdata = SCIPheurGetData(heur);
2521 assert(heurdata != NULL);
2522
2523 /* if we do not have a sub-SCIP, but tried to set one up before or will never create a subSCIP, then do not need a starting point */
2524 if( heurdata->subscip == NULL && (heurdata->triedsetupsubscip || !runHeuristic(scip) || SCIPheurGetFreq(heur) < 0) )
2525 return SCIP_OKAY;
2526
2527 /* if the solution is the one we created (last), then it is useless to use it as starting point again
2528 * (we cannot check SCIPsolGetHeur()==heur, as subnlp may not be registered as author of the solution)
2529 */
2530 if( heurdata->lastsol == solcand )
2531 return SCIP_OKAY;
2532
2533 SCIPdebugMsg(scip, "consider solution candidate with violation %g and objective %g from %s\n",
2534 violation, SCIPgetSolTransObj(scip, solcand), SCIPsolGetHeur(solcand) ? SCIPheurGetName(SCIPsolGetHeur(solcand)) : "tree");
2535
2536 /* if we have no point yet, or the new point has a lower constraint violation, or it has a better objective function value, then take the new point */
2537 if( heurdata->startcand == NULL || violation < heurdata->startcandviol ||
2538 SCIPisRelGT(scip, SCIPgetSolTransObj(scip, heurdata->startcand), SCIPgetSolTransObj(scip, solcand)) )
2539 {
2540 if( heurdata->startcand != NULL )
2541 {
2542 SCIP_CALL( SCIPfreeSol(scip, &heurdata->startcand) );
2543 }
2544 SCIP_CALL( SCIPcreateSolCopy(scip, &heurdata->startcand, solcand) );
2545 SCIP_CALL( SCIPunlinkSol(scip, heurdata->startcand) );
2546 heurdata->startcandviol = violation;
2547
2548 /* remember which heuristic proposed the candidate */
2549 SCIPsolSetHeur(heurdata->startcand, SCIPgetSolHeur(scip, solcand));
2550 }
2551
2552 return SCIP_OKAY;
2553 }
2554
2555 /** gets sub-SCIP used by NLP heuristic, or NULL if none */
SCIPgetSubScipHeurSubNlp(SCIP * scip,SCIP_HEUR * heur)2556 SCIP* SCIPgetSubScipHeurSubNlp(
2557 SCIP* scip, /**< original SCIP data structure */
2558 SCIP_HEUR* heur /**< heuristic data structure */
2559 )
2560 {
2561 SCIP_HEURDATA* heurdata;
2562
2563 assert(scip != NULL);
2564 assert(heur != NULL);
2565 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2566
2567 heurdata = SCIPheurGetData(heur);
2568 assert(heurdata != NULL);
2569
2570 return heurdata->subscip;
2571 }
2572
2573 /** gets mapping of SCIP variables to sub-SCIP variables */
SCIPgetVarMappingScip2SubScipHeurSubNlp(SCIP * scip,SCIP_HEUR * heur)2574 SCIP_VAR** SCIPgetVarMappingScip2SubScipHeurSubNlp(
2575 SCIP* scip, /**< original SCIP data structure */
2576 SCIP_HEUR* heur /**< heuristic data structure */
2577 )
2578 {
2579 SCIP_HEURDATA* heurdata;
2580
2581 assert(scip != NULL);
2582 assert(heur != NULL);
2583 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2584
2585 heurdata = SCIPheurGetData(heur);
2586 assert(heurdata != NULL);
2587
2588 return heurdata->var_scip2subscip;
2589 }
2590
2591 /** gets mapping of sub-SCIP variables to SCIP variables */
SCIPgetVarMappingSubScip2ScipHeurSubNlp(SCIP * scip,SCIP_HEUR * heur)2592 SCIP_VAR** SCIPgetVarMappingSubScip2ScipHeurSubNlp(
2593 SCIP* scip, /**< original SCIP data structure */
2594 SCIP_HEUR* heur /**< heuristic data structure */
2595 )
2596 {
2597 SCIP_HEURDATA* heurdata;
2598
2599 assert(scip != NULL);
2600 assert(heur != NULL);
2601 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2602
2603 heurdata = SCIPheurGetData(heur);
2604 assert(heurdata != NULL);
2605
2606 return heurdata->var_subscip2scip;
2607 }
2608
2609 /** gets startpoint candidate to be used in next call to NLP heuristic, or NULL if none */
SCIPgetStartCandidateHeurSubNlp(SCIP * scip,SCIP_HEUR * heur)2610 SCIP_SOL* SCIPgetStartCandidateHeurSubNlp(
2611 SCIP* scip, /**< original SCIP data structure */
2612 SCIP_HEUR* heur /**< heuristic data structure */
2613 )
2614 {
2615 SCIP_HEURDATA* heurdata;
2616
2617 assert(scip != NULL);
2618 assert(heur != NULL);
2619 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2620
2621 heurdata = SCIPheurGetData(heur);
2622 assert(heurdata != NULL);
2623
2624 return heurdata->startcand;
2625 }
2626