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_completesol.c
17 * @ingroup DEFPLUGINS_HEUR
18 * @brief COMPLETESOL - primal heuristic trying to complete given partial solutions
19 * @author Jakob Witzig
20 */
21
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23
24 #include "blockmemshell/memory.h"
25 #include "scip/cons_linear.h"
26 #include "scip/heur_completesol.h"
27 #include "scip/pub_event.h"
28 #include "scip/pub_heur.h"
29 #include "scip/pub_message.h"
30 #include "scip/pub_misc.h"
31 #include "scip/pub_sol.h"
32 #include "scip/pub_var.h"
33 #include "scip/scip_branch.h"
34 #include "scip/scip_cons.h"
35 #include "scip/scip_copy.h"
36 #include "scip/scip_event.h"
37 #include "scip/scip_general.h"
38 #include "scip/scip_heur.h"
39 #include "scip/scip_mem.h"
40 #include "scip/scip_message.h"
41 #include "scip/scip_nlp.h"
42 #include "scip/scip_nodesel.h"
43 #include "scip/scip_numerics.h"
44 #include "scip/scip_param.h"
45 #include "scip/scip_prob.h"
46 #include "scip/scip_probing.h"
47 #include "scip/scip_sol.h"
48 #include "scip/scip_solve.h"
49 #include "scip/scip_solvingstats.h"
50 #include "scip/scip_timing.h"
51 #include "scip/scip_tree.h"
52 #include "scip/scip_var.h"
53 #include <string.h>
54
55 #define HEUR_NAME "completesol"
56 #define HEUR_DESC "primal heuristic trying to complete given partial solutions"
57 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
58 #define HEUR_PRIORITY 0
59 #define HEUR_FREQ 0
60 #define HEUR_FREQOFS 0
61 #define HEUR_MAXDEPTH 0
62 #define HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE
63 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
64
65 /* default values for heuristic plugins */
66 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
67 #define DEFAULT_MAXUNKRATE 0.85 /**< maximum percentage of unknown solution values */
68 #define DEFAULT_ADDALLSOLS FALSE /**< should all subproblem solutions be added to the original SCIP? */
69 #define DEFAULT_MINNODES 50LL /**< minimum number of nodes to regard in the subproblem */
70 #define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */
71 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
72 #define DEFAULT_LPLIMFAC 2.0 /**< factor by which the limit on the number of LP depends on the node limit */
73 #define DEFAULT_OBJWEIGHT 1.0 /**< weight of the original objective function (1: only original objective) */
74 #define DEFAULT_BOUNDWIDENING 0.1 /**< bound widening factor applied to continuous variables
75 * (0: round bounds to next integer, 1: relax to global bounds)
76 */
77 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which the incumbent should be improved at least */
78 #define DEFAULT_MINOBJWEIGHT 1e-3 /**< minimal weight for original objective function (zero could lead to infinite solutions) */
79 #define DEFAULT_IGNORECONT FALSE /**< should solution values for continuous variables be ignored? */
80 #define DEFAULT_BESTSOLS 5 /**< heuristic stops, if the given number of improving solutions were found (-1: no limit) */
81 #define DEFAULT_MAXPROPROUNDS 10 /**< maximal number of iterations in propagation (-1: no limit) */
82 #define DEFAULT_MAXLPITER -1LL /**< maximal number of LP iterations (-1: no limit) */
83 #define DEFAULT_MAXCONTVARS -1 /**< maximal number of continuous variables after presolving (-1: no limit) */
84 #define DEFAULT_BEFOREPRESOL TRUE /**< should the heuristic run before presolving? */
85
86 /* event handler properties */
87 #define EVENTHDLR_NAME "Completesol"
88 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
89
90
91 /** primal heuristic data */
92 struct SCIP_HeurData
93 {
94 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
95 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
96 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
97 SCIP_Longint maxlpiter; /**< maximal number of LP iterations (-1: no limit) */
98 SCIP_Real maxunknownrate; /**< maximal rate of changed coefficients in the objective function */
99 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
100 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
101 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
102 SCIP_Real objweight; /**< weight of the original objective function (1: only original obj, 0: try to keep to given solution) */
103 SCIP_Real boundwidening; /**< bound widening factor applied to continuous variables
104 * (0: fix variables to given solution values, 1: relax to global bounds)
105 */
106 SCIP_Real minimprove; /**< factor by which the incumbent should be improved at least */
107 SCIP_Bool addallsols; /**< should all subproblem solutions be added to the original SCIP? */
108 SCIP_Bool ignorecont; /**< should solution values for continuous variables be ignored? */
109 SCIP_Bool beforepresol; /**< should the heuristic run before presolving? */
110 int bestsols; /**< heuristic stops, if the given number of improving solutions were found (-1: no limit) */
111 int maxcontvars; /**< maximal number of continuous variables after presolving (-1: no limit) */
112 int maxproprounds; /**< maximal number of iterations in propagation (-1: no limit) */
113 };
114
115 /* ---------------- Callback methods of event handler ---------------- */
116
117 /* exec the event handler
118 *
119 * we interrupt the solution process
120 */
121 static
SCIP_DECL_EVENTEXEC(eventExecCompletesol)122 SCIP_DECL_EVENTEXEC(eventExecCompletesol)
123 {
124 SCIP_HEURDATA* heurdata;
125
126 assert(eventhdlr != NULL);
127 assert(eventdata != NULL);
128 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
129 assert(event != NULL);
130 assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
131
132 heurdata = (SCIP_HEURDATA*)eventdata;
133 assert(heurdata != NULL);
134
135 /* interrupt solution process of sub-SCIP */
136 if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
137 {
138 SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip));
139 SCIP_CALL( SCIPinterruptSolve(scip) );
140 }
141
142 return SCIP_OKAY;
143 }
144
145 /** creates a subproblem by fixing a number of variables */
146 static
createSubproblem(SCIP * scip,SCIP * subscip,SCIP_HEURDATA * heurdata,SCIP_VAR ** subvars,SCIP_SOL * partialsol,SCIP_Bool * tightened)147 SCIP_RETCODE createSubproblem(
148 SCIP* scip, /**< original SCIP data structure */
149 SCIP* subscip, /**< SCIP data structure for the subproblem */
150 SCIP_HEURDATA* heurdata, /**< heuristic's private data structure */
151 SCIP_VAR** subvars, /**< the variables of the subproblem */
152 SCIP_SOL* partialsol, /**< partial solution */
153 SCIP_Bool* tightened /**< array to store for which variables we have found bound tightenings */
154 )
155 {
156 SCIP_VAR** vars;
157 SCIP_CONS* objcons;
158 SCIP_Real epsobj;
159 SCIP_Real cutoff;
160 SCIP_Real upperbound;
161 char consobjname[SCIP_MAXSTRLEN];
162 int nvars;
163 int i;
164
165 assert(scip != NULL);
166 assert(subscip != NULL);
167 assert(subvars != NULL);
168 assert(heurdata != NULL);
169
170 /* if there is already a solution, add an objective cutoff */
171 if( SCIPgetNSols(scip) > 0 )
172 {
173 assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip)));
174
175 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
176
177 if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
178 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip) + heurdata->minimprove * SCIPgetLowerbound(scip);
179 else
180 {
181 if( SCIPgetUpperbound(scip) >= 0 )
182 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
183 else
184 cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
185 }
186 cutoff = MIN(upperbound, cutoff);
187 SCIPdebugMsg(scip, "set cutoff=%g for sub-SCIP\n", cutoff);
188 }
189 else
190 cutoff = SCIPinfinity(scip);
191
192 /* calculate objective coefficients for all potential epsilons */
193 if( SCIPisEQ(scip, heurdata->objweight, 1.0) )
194 return SCIP_OKAY;
195 else if( !SCIPisInfinity(scip, cutoff) )
196 epsobj = 1.0;
197 else
198 {
199 /* divide by objweight to avoid changing objective coefficient of original problem variables */
200 epsobj = (1.0 - heurdata->objweight)/heurdata->objweight;
201
202 /* scale with -1 if we have a maximization problem */
203 if( SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE )
204 epsobj *= -1.0;
205 }
206
207 /* get active variables */
208 vars = SCIPgetVars(scip);
209 nvars = SCIPgetNVars(scip);
210
211 objcons = NULL;
212
213 /* add constraints to measure the distance to the given partial solution */
214 for( i = 0; i < nvars; i++ )
215 {
216 SCIP_Real solval;
217 int idx;
218
219 assert(SCIPvarIsActive(vars[i]));
220
221 if( subvars[i] == NULL )
222 continue;
223
224 /* add objective function as a constraint, if a primal bound exists */
225 if( SCIPisInfinity(scip, cutoff) )
226 {
227 /* create the constraints */
228 if( objcons == NULL )
229 {
230 SCIP_Real lhs;
231 SCIP_Real rhs;
232
233 if( SCIPgetObjsense(subscip) == SCIP_OBJSENSE_MINIMIZE )
234 {
235 lhs = -SCIPinfinity(subscip);
236 rhs = cutoff;
237 }
238 else
239 {
240 lhs = cutoff;
241 rhs = SCIPinfinity(subscip);
242 }
243
244 (void)SCIPsnprintf(consobjname, SCIP_MAXSTRLEN, "obj");
245 SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &objcons, consobjname, 0, NULL, NULL, lhs, rhs) );
246 }
247
248 /* add the variable to the constraints */
249 SCIP_CALL( SCIPaddCoefLinear(subscip, objcons, subvars[i], SCIPvarGetObj(subvars[i])) );
250
251 /* set objective coefficient to 0.0 */
252 SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) );
253 }
254
255 solval = SCIPgetSolVal(scip, partialsol, vars[i]);
256
257 /* skip variables with unknown solution value */
258 if( solval == SCIP_UNKNOWN ) /*lint !e777*/
259 continue;
260
261 idx = SCIPvarGetProbindex(vars[i]);
262 assert(idx >= 0);
263
264 /* skip variables where we already found some bound tightenings */
265 if( tightened[idx] == FALSE )
266 {
267 /* special case: vars[i] is binary; we do not add an extra variable, but we mimic the behavior we would get with it.
268 * E.g., if the solval is 0.3, setting the variable to 0 would give a cost of 0.3 * epsobj, setting it to 1 gives
269 * 0.7 * epsobj. Thus, 0.3 * epsobj can be treated as a constant in the objective function and the variable gets
270 * an objective coefficient of 0.4 * epsobj.
271 */
272 if( SCIPvarIsBinary(vars[i]) )
273 {
274 SCIP_Real frac = SCIPfeasFrac(scip, solval);
275 SCIP_Real objcoef;
276
277 frac = MIN(frac, 1-frac);
278 objcoef = (1 - 2*frac) * epsobj * (int)SCIPgetObjsense(scip);
279
280 if( solval > 0.5 )
281 {
282 SCIP_CALL( SCIPchgVarObj(scip, vars[i], -objcoef) );
283 }
284 else
285 {
286 SCIP_CALL( SCIPchgVarObj(scip, vars[i], objcoef) );
287 }
288 }
289 else
290 {
291 SCIP_CONS* conspos;
292 SCIP_CONS* consneg;
293 SCIP_VAR* eps;
294 char consnamepos[SCIP_MAXSTRLEN];
295 char consnameneg[SCIP_MAXSTRLEN];
296 char epsname[SCIP_MAXSTRLEN];
297
298 /* create two new variables */
299 (void)SCIPsnprintf(epsname, SCIP_MAXSTRLEN, "eps_%s", SCIPvarGetName(subvars[i]));
300
301 SCIP_CALL( SCIPcreateVarBasic(subscip, &eps, epsname, 0.0, SCIPinfinity(scip), epsobj, SCIP_VARTYPE_CONTINUOUS) );
302 SCIP_CALL( SCIPaddVar(subscip, eps) );
303
304 /* create two constraints */
305 (void)SCIPsnprintf(consnamepos, SCIP_MAXSTRLEN, "cons_%s_pos", SCIPvarGetName(subvars[i]));
306 (void)SCIPsnprintf(consnameneg, SCIP_MAXSTRLEN, "cons_%s_neq", SCIPvarGetName(subvars[i]));
307
308 /* x_{i} - s_{i} <= e_{i} <==> x_{i} - e_{i} <= s_{i} */
309 SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &conspos, consnamepos, 0, NULL, NULL, -SCIPinfinity(scip), solval) );
310 SCIP_CALL( SCIPaddCoefLinear(subscip, conspos, subvars[i], 1.0) );
311 SCIP_CALL( SCIPaddCoefLinear(subscip, conspos, eps, -1.0) );
312 SCIP_CALL( SCIPaddCons(subscip, conspos) );
313 SCIP_CALL( SCIPreleaseCons(subscip, &conspos) );
314
315 /* s_{i} - x_{i} <= e_{i} <==> e_{i} - x_{i} >= s_{i} */
316 SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &consneg, consnameneg, 0, NULL, NULL, solval, SCIPinfinity(scip)) );
317 SCIP_CALL( SCIPaddCoefLinear(subscip, consneg, subvars[i], -1.0) );
318 SCIP_CALL( SCIPaddCoefLinear(subscip, consneg, eps, 1.0) );
319 SCIP_CALL( SCIPaddCons(subscip, consneg) );
320 SCIP_CALL( SCIPreleaseCons(subscip, &consneg) );
321
322 /* release the variables */
323 SCIP_CALL( SCIPreleaseVar(subscip, &eps) );
324 }
325 }
326 }
327
328 /* add and release the constraint representing the original objective function */
329 if( objcons != NULL )
330 {
331 SCIP_CALL( SCIPaddCons(subscip, objcons) );
332 SCIP_CALL( SCIPreleaseCons(subscip, &objcons) );
333 }
334
335 return SCIP_OKAY;
336 }
337
338 /** perform a probing bound change or fixes the variable */
339 static
chgProbingBound(SCIP * scip,SCIP_VAR * var,SCIP_Real newval,SCIP_BRANCHDIR branchdir,SCIP_Bool * success)340 SCIP_RETCODE chgProbingBound(
341 SCIP* scip, /**< original SCIP data structure */
342 SCIP_VAR* var, /**< problem variable */
343 SCIP_Real newval, /**< new bound */
344 SCIP_BRANCHDIR branchdir, /**< bound change direction */
345 SCIP_Bool* success /**< pointer to store whether the bound could be tightened */
346 )
347 {
348 SCIP_Real ub;
349 SCIP_Real lb;
350
351 assert(scip != NULL);
352 assert(var != NULL);
353
354 (*success) = FALSE;
355
356 ub = SCIPvarGetUbLocal(var);
357 lb = SCIPvarGetLbLocal(var);
358
359 switch (branchdir) {
360 case SCIP_BRANCHDIR_DOWNWARDS:
361 if( SCIPisLT(scip, newval, ub) && SCIPisGE(scip, newval, lb) )
362 {
363 SCIP_CALL( SCIPchgVarUbProbing(scip, var, newval) );
364 (*success) = TRUE;
365 }
366 break;
367 case SCIP_BRANCHDIR_UPWARDS:
368 if( SCIPisLE(scip, newval, ub) && SCIPisGT(scip, newval, lb) )
369 {
370 SCIP_CALL( SCIPchgVarLbProbing(scip, var, newval) );
371 (*success) = TRUE;
372 }
373 break;
374 case SCIP_BRANCHDIR_FIXED:
375 if( SCIPisLE(scip, newval, ub) && SCIPisGE(scip, newval, lb) )
376 {
377 SCIP_CALL( SCIPfixVarProbing(scip, var, newval) );
378 (*success) = TRUE;
379 }
380 break;
381 default:
382 return SCIP_INVALIDDATA;
383 }/*lint !e788*/
384
385 return SCIP_OKAY;
386 }
387
388 /** tries variables bound changes guided by the given solution */
389 static
tightenVariables(SCIP * scip,SCIP_HEURDATA * heurdata,SCIP_VAR ** vars,int nvars,SCIP_SOL * sol,SCIP_Bool * tightened,SCIP_Bool * infeasible)390 SCIP_RETCODE tightenVariables(
391 SCIP* scip, /**< original SCIP data structure */
392 SCIP_HEURDATA* heurdata, /**< heuristic's private data structure */
393 SCIP_VAR** vars, /**< problem variables */
394 int nvars, /**< number of problem variables */
395 SCIP_SOL* sol, /**< solution to guide the bound changes */
396 SCIP_Bool* tightened, /**< array to store if variable bound could be tightened */
397 SCIP_Bool* infeasible /**< pointer to store whether subproblem is infeasible */
398 )
399 {
400 #ifndef NDEBUG
401 SCIP_Bool incontsection;
402 #endif
403 SCIP_Bool abortearly;
404 SCIP_Bool cutoff;
405 SCIP_Bool probingsuccess;
406 SCIP_Longint ndomreds;
407 SCIP_Longint ndomredssum;
408 int nbndtightenings;
409 int v;
410
411 assert(scip != NULL);
412 assert(heurdata != NULL);
413 assert(vars != NULL);
414 assert(nvars >= 0);
415 assert(sol != NULL);
416 assert(tightened != NULL);
417
418 assert(SCIPsolGetOrigin(sol) == SCIP_SOLORIGIN_PARTIAL);
419
420 SCIPdebugMsg(scip, "> start probing along the solution values\n");
421
422 *infeasible = FALSE;
423 abortearly = FALSE;
424 nbndtightenings = 0;
425 ndomredssum = 0;
426 #ifndef NDEBUG
427 incontsection = FALSE;
428 #endif
429
430 /* there is at least one integral variable; open one probing node for all non-continuous variables */
431 if( nvars - SCIPgetNContVars(scip) > 0 )
432 {
433 SCIP_CALL( SCIPnewProbingNode(scip) );
434 }
435
436 for( v = 0; v < nvars && !abortearly; v++ )
437 {
438 SCIP_Real solval;
439
440 assert(SCIPvarIsActive(vars[v]));
441
442 cutoff = FALSE;
443 ndomreds = 0;
444
445 #ifndef NDEBUG
446 incontsection |= (!SCIPvarIsIntegral(vars[v])); /*lint !e514*/
447 assert(!incontsection || !SCIPvarIsIntegral(vars[v]));
448 #endif
449
450 /* return if we have found enough domain reductions tightenings */
451 if( ndomredssum > 0.3*nvars )
452 break;
453
454 solval = SCIPgetSolVal(scip, sol, vars[v]);
455
456 /* skip unknown variables */
457 if( solval == SCIP_UNKNOWN ) /*lint !e777*/
458 continue;
459 assert(!SCIPisInfinity(scip, solval) && !SCIPisInfinity(scip, -solval));
460
461 /* variable is binary or integer */
462 if( SCIPvarIsIntegral(vars[v]) )
463 {
464 /* the solution value is integral, try to fix them */
465 if( SCIPisIntegral(scip, solval) )
466 {
467 SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_FIXED, &probingsuccess) );
468 tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
469 ++nbndtightenings;
470
471 #ifdef SCIP_MORE_DEBUG
472 SCIPdebugMsg(scip, "> fix variable <%s> = [%g,%g] to %g \n", SCIPvarGetName(vars[v]),
473 SCIPvarGetLbGlobal(vars[v]), SCIPvarGetUbGlobal(vars[v]), solval);
474 #endif
475 }
476 else
477 {
478 SCIP_Real ub = SCIPceil(scip, solval) + 1.0;
479 SCIP_Real lb = SCIPfloor(scip, solval) - 1.0;
480
481 /* try tightening of upper bound */
482 if( SCIPisLT(scip, ub, SCIPvarGetUbLocal(vars[v])) )
483 {
484 SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_DOWNWARDS, &probingsuccess) );
485 tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
486 ++nbndtightenings;
487
488 #ifdef SCIP_MORE_DEBUG
489 SCIPdebugMsg(scip, "> tighten upper bound of variable <%s>: %g to %g\n", SCIPvarGetName(vars[v]),
490 SCIPvarGetUbGlobal(vars[v]), ub);
491 #endif
492 }
493
494 /* try tightening of lower bound */
495 if( SCIPisGT(scip, lb, SCIPvarGetLbLocal(vars[v])) )
496 {
497 SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_UPWARDS, &probingsuccess) );
498 tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
499 ++nbndtightenings;
500
501 #ifdef SCIP_MORE_DEBUG
502 SCIPdebugMsg(scip, "> tighten lower bound of variable <%s>: %g to %g\n", SCIPvarGetName(vars[v]),
503 SCIPvarGetLbGlobal(vars[v]), ub);
504 #endif
505 }
506 }
507 }
508 /* variable is continuous */
509 else
510 {
511 /* fix to lb or ub */
512 if( SCIPisEQ(scip, solval, SCIPvarGetLbLocal(vars[v])) || SCIPisEQ(scip, solval, SCIPvarGetUbLocal(vars[v])) )
513 {
514 /* open a new probing node */
515 if( SCIPgetProbingDepth(scip) < SCIP_MAXTREEDEPTH-10 )
516 {
517 SCIP_CALL( SCIPnewProbingNode(scip) );
518
519 SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_FIXED, &probingsuccess) );
520
521 /* skip propagation if the bound could not be changed, e.g., already tightened due to previous
522 * domain propagation
523 */
524 if( probingsuccess )
525 {
526 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
527 }
528
529 if( cutoff )
530 {
531 ndomreds = 0;
532 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
533 }
534 else
535 {
536 assert(SCIPvarGetProbindex(vars[v]) >= 0);
537 tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
538 ++nbndtightenings;
539 #ifdef SCIP_MORE_DEBUG
540 SCIPdebugMsg(scip, "> fix variable <%s> = [%g,%g] to %g (ndomreds=%lld)\n", SCIPvarGetName(vars[v]),
541 SCIPvarGetLbGlobal(vars[v]), SCIPvarGetUbGlobal(vars[v]), solval, ndomreds);
542 #endif
543 }
544 }
545 else
546 /* abort probing */
547 abortearly = TRUE;
548 }
549 else
550 {
551 SCIP_Real offset;
552 SCIP_Real newub = SCIPvarGetUbGlobal(vars[v]);
553 SCIP_Real newlb = SCIPvarGetLbGlobal(vars[v]);
554
555 /* both bound are finite */
556 if( !SCIPisInfinity(scip, -newlb) && !SCIPisInfinity(scip, newub) )
557 offset = REALABS(heurdata->boundwidening * (newub-newlb));
558 else
559 {
560 offset = 0.0;
561
562 /* if exactly one bound is finite, widen bound w.r.t. solution value and finite bound */
563 if( !SCIPisInfinity(scip, -newlb) )
564 offset = REALABS(heurdata->boundwidening * (solval-newlb));
565 else if( !SCIPisInfinity(scip, newub) )
566 offset = REALABS(heurdata->boundwidening * (newub-solval));
567 }
568
569 /* update bounds */
570 newub = SCIPceil(scip, solval) + offset;
571 newlb = SCIPfloor(scip, solval) - offset;
572
573 /* try tightening of upper bound */
574 if( SCIPisLT(scip, newub, SCIPvarGetUbLocal(vars[v])) )
575 {
576 /* open a new probing node */
577 if( SCIPgetProbingDepth(scip) < SCIP_MAXTREEDEPTH-10 )
578 {
579 SCIP_CALL( SCIPnewProbingNode(scip) );
580 SCIP_CALL( chgProbingBound(scip, vars[v], newub, SCIP_BRANCHDIR_DOWNWARDS, &probingsuccess) );
581
582 /* skip propagation if the bound could not be changed, e.g., already tightened due to previous
583 * domain propagation
584 */
585 if( probingsuccess )
586 {
587 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
588 }
589
590 if( cutoff )
591 {
592 ndomreds = 0;
593
594 /* backtrack to last feasible probing node */
595 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
596
597 /* we can tighten the lower bound by newub */
598 SCIP_CALL( chgProbingBound(scip, vars[v], newub, SCIP_BRANCHDIR_UPWARDS, &probingsuccess) );
599
600 /* propagate the new bound */
601 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
602
603 /* there is no feasible solution w.r.t. the current bounds */
604 if( cutoff )
605 {
606 SCIPdebugMsg(scip, "> subproblem is infeasible within the local bounds\n");
607 *infeasible = TRUE;
608 return SCIP_OKAY;
609 }
610 #ifdef SCIP_MORE_DEBUG
611 SCIPdebugMsg(scip, "> tighten lower bound of variable <%s>: %g to %g\n",
612 SCIPvarGetName(vars[v]), SCIPvarGetLbGlobal(vars[v]), newub);
613 #endif
614 }
615 else
616 {
617 assert(SCIPvarGetProbindex(vars[v]) >= 0);
618 tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
619 ++nbndtightenings;
620 #ifdef SCIP_MORE_DEBUG
621 SCIPdebugMsg(scip, "> tighten upper bound of variable <%s>: %g to %g (ndomreds=%lld)\n",
622 SCIPvarGetName(vars[v]), SCIPvarGetUbGlobal(vars[v]), newub, ndomreds);
623 #endif
624 }
625 }
626 else
627 /* abort probing */
628 abortearly = TRUE;
629 }
630
631 /* try tightening of lower bound */
632 if( SCIPisGT(scip, newlb, SCIPvarGetLbLocal(vars[v])) )
633 {
634 /* open a new probing node */
635 if( SCIPgetProbingDepth(scip) < SCIP_MAXTREEDEPTH-10 )
636 {
637 SCIP_CALL( SCIPnewProbingNode(scip) );
638 SCIP_CALL( chgProbingBound(scip, vars[v], newlb, SCIP_BRANCHDIR_UPWARDS, &probingsuccess) );
639
640 /* skip propagation if the bound could not be changed, e.g., already tightened due to previous
641 * domain propagation
642 */
643 if( probingsuccess )
644 {
645 SCIP_CALL( SCIPpropagateProbing(scip, -1, &cutoff, &ndomreds) );
646 }
647
648 if( cutoff )
649 {
650 ndomreds = 0;
651
652 /* backtrack to last feasible probing node */
653 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
654
655 /* we can tighten the upper bound by newlb */
656 SCIP_CALL( chgProbingBound(scip, vars[v], newlb, SCIP_BRANCHDIR_DOWNWARDS, &probingsuccess) );
657
658 /* propagate the new bound */
659 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
660
661 /* there is no feasible solution w.r.t. the current bounds */
662 if( cutoff )
663 {
664 SCIPdebugMsg(scip, "> subproblem is infeasible within the local bounds\n");
665 *infeasible = TRUE;
666 return SCIP_OKAY;
667 }
668 #ifdef SCIP_MORE_DEBUG
669 SCIPdebugMsg(scip, "> tighten upper bound of variable <%s>: %g to %g\n",
670 SCIPvarGetName(vars[v]), SCIPvarGetUbGlobal(vars[v]), newlb);
671 #endif
672 }
673 else
674 {
675 assert(SCIPvarGetProbindex(vars[v]) >= 0);
676 tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
677 ++nbndtightenings;
678 #ifdef SCIP_MORE_DEBUG
679 SCIPdebugMsg(scip, "> tighten lower bound of variable <%s>: %g to %g (ndomreds=%lld)\n",
680 SCIPvarGetName(vars[v]), SCIPvarGetLbGlobal(vars[v]), newlb, ndomreds);
681 #endif
682 }
683 }
684 else
685 /* abort probing */
686 abortearly = TRUE;
687 }
688 }
689 }
690
691 ndomredssum += ndomreds;
692 }
693
694 SCIPdebugMsg(scip, "> found %d bound tightenings and %lld induced domain reductions (abort=%u).\n", nbndtightenings,
695 ndomredssum, abortearly);
696
697 return SCIP_OKAY;
698 }
699
700 /* setup and solve the sub-SCIP */
701 static
setupAndSolve(SCIP * scip,SCIP * subscip,SCIP_HEUR * heur,SCIP_HEURDATA * heurdata,SCIP_RESULT * result,SCIP_Longint nstallnodes,SCIP_SOL * partialsol,SCIP_Bool * tightened)702 SCIP_RETCODE setupAndSolve(
703 SCIP* scip, /**< original SCIP data structure */
704 SCIP* subscip, /**< sub-SCIP data structure */
705 SCIP_HEUR* heur, /**< heuristic data structure */
706 SCIP_HEURDATA* heurdata, /**< heuristic's private data structure */
707 SCIP_RESULT* result, /**< result data structure */
708 SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */
709 SCIP_SOL* partialsol, /**< partial solution */
710 SCIP_Bool* tightened /**< array to store whether a variable was already tightened */
711 )
712 {
713 SCIP_HASHMAP* varmapf;
714 SCIP_VAR** vars;
715 SCIP_VAR** subvars = NULL;
716 SCIP_EVENTHDLR* eventhdlr;
717 int nvars;
718 int i;
719
720 SCIP_SOL** subsols;
721 int nsubsols;
722
723 SCIP_Bool valid;
724 SCIP_Bool success;
725 SCIP_RETCODE retcode;
726
727 assert(scip != NULL);
728 assert(subscip != NULL);
729 assert(heur != NULL);
730 assert(heurdata != NULL);
731 assert(result != NULL);
732 assert(partialsol != NULL);
733
734 vars = SCIPgetVars(scip);
735 nvars = SCIPgetNVars(scip);
736
737 /* create the variable mapping hash map */
738 SCIP_CALL( SCIPhashmapCreate(&varmapf, SCIPblkmem(subscip), nvars) );
739
740 eventhdlr = NULL;
741 valid = FALSE;
742
743 /* copy complete SCIP instance */
744 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmapf, NULL, "completesol", NULL, NULL, 0, FALSE, FALSE, FALSE,
745 TRUE, &valid) );
746 SCIPdebugMsg(scip, "Copying the SCIP instance returned with valid=%d.\n", valid);
747
748 /* create event handler for LP events */
749 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecCompletesol, NULL) );
750 if( eventhdlr == NULL )
751 {
752 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
753 return SCIP_PLUGINNOTFOUND;
754 }
755
756 /* allocate memory to align the SCIP and the sub-SCIP variables */
757 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
758
759 /* map all variables */
760 for( i = 0; i < nvars; i++ )
761 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapf, vars[i]);
762
763 /* free hash map */
764 SCIPhashmapFree(&varmapf);
765
766 /* create a new problem, which fixes variables with same value in bestsol and LP relaxation */
767 SCIP_CALL( createSubproblem(scip, subscip, heurdata, subvars, partialsol, tightened) );
768 SCIPdebugMsg(scip, "Completesol subproblem: %d vars, %d cons\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip));
769
770 /* do not abort subproblem on CTRL-C */
771 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
772
773 #ifdef SCIP_DEBUG
774 /* for debugging, enable full output */
775 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", SCIP_VERBLEVEL_FULL) );
776 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", -1) );
777 #else
778 /* disable statistic timing inside sub SCIP and output to console */
779 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", (int) SCIP_VERBLEVEL_NONE) );
780 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
781 #endif
782
783 /* set limits for the subproblem */
784 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
785 heurdata->nodelimit = heurdata->maxnodes;
786 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
787 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
788 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsols) );
789
790 /* limit the number of LP iterations */
791 SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", heurdata->maxlpiter) );
792 SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", heurdata->maxlpiter) );
793
794 /* forbid recursive call of heuristics and separators solving sub-SCIPs */
795 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
796
797 /* disable cutting plane separation */
798 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
799
800 /* disable expensive presolving */
801 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
802
803 /* use best estimate node selection */
804 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
805 {
806 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
807 }
808
809 /* use inference branching */
810 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
811 {
812 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
813 }
814
815 /* disable conflict analysis */
816 if( !SCIPisParamFixed(subscip, "conflict/enable") )
817 {
818 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", FALSE) );
819 }
820
821 /* speed up sub-SCIP by not checking dual LP feasibility */
822 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
823
824 SCIP_CALL( SCIPtransformProb(subscip) );
825 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
826
827 /* solve the subproblem */
828 SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
829
830 /* errors in solving the subproblem should not kill the overall solving process;
831 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
832 */
833
834 retcode = SCIPpresolve(subscip);
835
836 /* errors in presolving the subproblem should not kill the overall solving process;
837 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
838 */
839 if( retcode != SCIP_OKAY )
840 {
841 SCIPwarningMessage(scip, "Error while presolving subproblem in %s heuristic; sub-SCIP terminated with code <%d>\n", HEUR_NAME, retcode);
842
843 SCIPABORT(); /*lint --e{527}*/
844
845 goto TERMINATE;
846 }
847
848 if( SCIPgetStage(subscip) == SCIP_STAGE_PRESOLVED )
849 {
850 SCIPdebugMsg(scip, "presolved instance has bin=%d, int=%d, cont=%d variables\n",
851 SCIPgetNBinVars(subscip), SCIPgetNIntVars(subscip), SCIPgetNContVars(subscip));
852
853 /* check whether the presolved instance is small enough */
854 if( heurdata->maxcontvars >= 0 && SCIPgetNContVars(subscip) > heurdata->maxcontvars )
855 {
856 SCIPdebugMsg(scip, "presolved instance has too many continuous variables (maxcontvars: %d)\n", heurdata->maxcontvars);
857 goto TERMINATE;
858 }
859
860 /* set node limit of 1 if the presolved problem is an LP, otherwise we would start branching if an LP iteration
861 * limit was set by the user.
862 */
863 if( !SCIPisNLPEnabled(subscip) && SCIPgetNContVars(subscip) == SCIPgetNVars(subscip) )
864 {
865 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", 1LL) );
866 }
867
868 retcode = SCIPsolve(subscip);
869
870 /* errors in solving the subproblem should not kill the overall solving process;
871 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
872 */
873 if( retcode != SCIP_OKAY )
874 {
875 SCIPwarningMessage(scip, "Error while solving subproblem in %s heuristic; sub-SCIP terminated with code <%d>\n", HEUR_NAME, retcode);
876
877 SCIPABORT(); /*lint --e{527}*/
878
879 goto TERMINATE;
880 }
881 }
882
883 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
884
885 /* print solving statistics of subproblem if we are in SCIP's debug mode */
886 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
887
888 /* check, whether a solution was found;
889 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
890 */
891 nsubsols = SCIPgetNSols(subscip);
892 subsols = SCIPgetSols(subscip);
893 success = FALSE;
894 for( i = 0; i < nsubsols && (!success || heurdata->addallsols); i++ )
895 {
896 SCIP_SOL* newsol;
897
898 /* create new solution, try to add to SCIP, and free it immediately */
899 SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], heur, subvars, &newsol) );
900 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
901
902 if( success )
903 *result = SCIP_FOUNDSOL;
904 }
905
906 SCIPstatisticPrintf("%s statistic: fixed %6.3f integer variables, needed %6.1f seconds, %" SCIP_LONGINT_FORMAT " nodes, solution %10.4f found at node %" SCIP_LONGINT_FORMAT "\n",
907 HEUR_NAME, 0.0, SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), success ? SCIPgetPrimalbound(scip) : SCIPinfinity(scip),
908 nsubsols > 0 ? SCIPsolGetNodenum(SCIPgetBestSol(subscip)) : -1 );
909
910 /* print message if the completion of a partial solution failed */
911 if( *result != SCIP_FOUNDSOL )
912 {
913 switch( SCIPgetStatus(subscip) )
914 {
915 case SCIP_STATUS_INFEASIBLE:
916 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (subproblem is infeasible)\n");
917 break;
918 case SCIP_STATUS_NODELIMIT:
919 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (node limit exceeded)\n");
920 break;
921 case SCIP_STATUS_TIMELIMIT:
922 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (time limit exceeded)\n");
923 break;
924 case SCIP_STATUS_MEMLIMIT:
925 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (memory limit exceeded)\n");
926 break;
927 default:
928 break;
929 } /*lint !e788*/
930 }
931
932 TERMINATE:
933 SCIPfreeBufferArray(scip, &subvars);
934
935 return SCIP_OKAY;
936 }
937
938 /** main procedure of the completesol heuristic, creates and solves a sub-SCIP */
939 static
applyCompletesol(SCIP * scip,SCIP_HEUR * heur,SCIP_HEURDATA * heurdata,SCIP_RESULT * result,SCIP_Longint nstallnodes,SCIP_SOL * partialsol)940 SCIP_RETCODE applyCompletesol(
941 SCIP* scip, /**< original SCIP data structure */
942 SCIP_HEUR* heur, /**< heuristic data structure */
943 SCIP_HEURDATA* heurdata, /**< heuristic's private data structure */
944 SCIP_RESULT* result, /**< result data structure */
945 SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */
946 SCIP_SOL* partialsol /**< partial solution */
947 )
948 {
949 SCIP* subscip;
950 SCIP_VAR** vars;
951 SCIP_Bool* tightened;
952 SCIP_Bool infeasible;
953 SCIP_Bool success;
954 SCIP_RETCODE retcode;
955 int nvars;
956
957 assert(scip != NULL);
958 assert(heur != NULL);
959 assert(heurdata != NULL);
960 assert(result != NULL);
961 assert(partialsol != NULL);
962
963 *result = SCIP_DIDNOTRUN;
964
965 SCIPdebugMsg(scip, "+---+ Start Completesol heuristic +---+\n");
966
967 /* check whether there is enough time and memory left */
968 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
969
970 if( !success )
971 return SCIP_OKAY;
972
973 *result = SCIP_DIDNOTFIND;
974
975 /* get variable data */
976 vars = SCIPgetVars(scip);
977 nvars = SCIPgetNVars(scip);
978
979 /* get buffer memory and initialize it to FALSE */
980 SCIP_CALL( SCIPallocClearBufferArray(scip, &tightened, nvars) );
981
982 SCIP_CALL( SCIPstartProbing(scip) );
983
984 SCIP_CALL( tightenVariables(scip, heurdata, vars, nvars, partialsol, tightened, &infeasible) );
985
986 if( infeasible )
987 {
988 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (subproblem is infeasible)\n");
989 goto ENDPROBING;
990 }
991
992 /* initialize the subproblem */
993 SCIP_CALL( SCIPcreate(&subscip) );
994
995 retcode = setupAndSolve(scip, subscip, heur, heurdata, result, nstallnodes, partialsol, tightened);
996
997 /* free subproblem */
998 SCIP_CALL( SCIPfree(&subscip) );
999
1000 SCIP_CALL( retcode );
1001
1002 ENDPROBING:
1003 SCIPfreeBufferArray(scip, &tightened);
1004 SCIP_CALL( SCIPendProbing(scip) );
1005
1006 return SCIP_OKAY;
1007 }
1008
1009
1010 /*
1011 * Callback methods of primal heuristic
1012 */
1013
1014 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1015 static
SCIP_DECL_HEURCOPY(heurCopyCompletesol)1016 SCIP_DECL_HEURCOPY(heurCopyCompletesol)
1017 { /*lint --e{715}*/
1018 assert(scip != NULL);
1019 assert(heur != NULL);
1020 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1021
1022 /* call inclusion method of primal heuristic */
1023 SCIP_CALL( SCIPincludeHeurCompletesol(scip) );
1024
1025 return SCIP_OKAY;
1026 }
1027
1028 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1029 static
SCIP_DECL_HEURFREE(heurFreeCompletesol)1030 SCIP_DECL_HEURFREE(heurFreeCompletesol)
1031 { /*lint --e{715}*/
1032 SCIP_HEURDATA* heurdata;
1033
1034 assert(heur != NULL);
1035 assert(scip != NULL);
1036
1037 /* get heuristic data */
1038 heurdata = SCIPheurGetData(heur);
1039 assert(heurdata != NULL);
1040
1041 /* free heuristic data */
1042 SCIPfreeBlockMemory(scip, &heurdata);
1043 SCIPheurSetData(heur, NULL);
1044
1045 return SCIP_OKAY;
1046 }
1047
1048 /** execution method of primal heuristic */
1049 static
SCIP_DECL_HEUREXEC(heurExecCompletesol)1050 SCIP_DECL_HEUREXEC(heurExecCompletesol)
1051 {/*lint --e{715}*/
1052 SCIP_HEURDATA* heurdata;
1053 SCIP_VAR** vars;
1054 SCIP_SOL** partialsols;
1055 SCIP_Longint nstallnodes;
1056 int npartialsols;
1057 int nunknown;
1058 int nfracints;
1059 int nvars;
1060 int s;
1061 int v;
1062
1063 assert( heur != NULL );
1064 assert( scip != NULL );
1065 assert( result != NULL );
1066
1067 *result = SCIP_DELAYED;
1068
1069 /* do not call heuristic of node was already detected to be infeasible */
1070 if( nodeinfeasible )
1071 return SCIP_OKAY;
1072
1073 /* get heuristic data */
1074 heurdata = SCIPheurGetData(heur);
1075 assert( heurdata != NULL );
1076
1077 *result = SCIP_DIDNOTRUN;
1078
1079 if( SCIPisStopped(scip) )
1080 return SCIP_OKAY;
1081
1082 /* do not run after restart */
1083 if( SCIPgetNRuns(scip) > 1 )
1084 return SCIP_OKAY;
1085
1086 /* check whether we want to run before presolving */
1087 if( (heurtiming & SCIP_HEURTIMING_BEFOREPRESOL) && !heurdata->beforepresol )
1088 return SCIP_OKAY;
1089
1090 /* only run before root node */
1091 if( (heurtiming & SCIP_HEURTIMING_BEFORENODE)
1092 && (heurdata->beforepresol || SCIPgetCurrentNode(scip) != SCIPgetRootNode(scip)) )
1093 return SCIP_OKAY;
1094
1095 /* get variable data and return of no variables are left in the problem */
1096 vars = SCIPgetVars(scip);
1097 nvars = SCIPgetNVars(scip);
1098
1099 if( nvars == 0 )
1100 return SCIP_OKAY;
1101
1102 /* calculate the maximal number of branching nodes until heuristic is aborted */
1103 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
1104
1105 /* reward Completesol if it succeeded often */
1106 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
1107 nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-SCIP as 100 nodes */
1108 nstallnodes += heurdata->nodesofs;
1109
1110 /* determine the node limit for the current process */
1111 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
1112
1113 /* check whether we have enough nodes left to call subproblem solving */
1114 if( nstallnodes < heurdata->minnodes )
1115 {
1116 SCIPdebugMsg(scip, "skipping Complete: nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n",
1117 nstallnodes, heurdata->minnodes);
1118 return SCIP_OKAY;
1119 }
1120
1121 /* check the number of variables with unknown value and continuous variables with fractional value */
1122 nfracints = 0;
1123
1124 /* get all partial sols */
1125 npartialsols = SCIPgetNPartialSols(scip);
1126 partialsols = SCIPgetPartialSols(scip);
1127
1128 /* loop over all partial solutions */
1129 for( s = 0; s < npartialsols; s++ )
1130 {
1131 SCIP_SOL* sol;
1132 SCIP_Real solval;
1133 SCIP_Real unknownrate;
1134
1135 sol = partialsols[s];
1136 assert(sol != NULL);
1137 assert(SCIPsolIsPartial(sol));
1138
1139 nunknown = 0;
1140 /* loop over all variables */
1141 for( v = 0; v < nvars; v++ )
1142 {
1143 assert(SCIPvarIsActive(vars[v]));
1144
1145 /* skip continuous variables if they should ignored */
1146 if( !SCIPvarIsIntegral(vars[v]) && heurdata->ignorecont )
1147 continue;
1148
1149 solval = SCIPgetSolVal(scip, sol, vars[v]);
1150
1151 /* we only want to count variables that are unfixed after the presolving */
1152 if( solval == SCIP_UNKNOWN ) /*lint !e777*/
1153 ++nunknown;
1154 else if( SCIPvarIsIntegral(vars[v]) && !SCIPisIntegral(scip, solval) )
1155 ++nfracints;
1156 }
1157
1158 if( heurdata->ignorecont )
1159 unknownrate = nunknown/((SCIP_Real)SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip));
1160 else
1161 unknownrate = nunknown/((SCIP_Real)nvars);
1162 SCIPdebugMsg(scip, "%d (rate %.4f) unknown solution values\n", nunknown, unknownrate);
1163
1164 /* run the heuristic, if not too many unknown variables exist */
1165 if( unknownrate > heurdata->maxunknownrate )
1166 {
1167 SCIPwarningMessage(scip, "ignore partial solution (%d) because unknown rate is too large (%g > %g)\n", s,
1168 unknownrate, heurdata->maxunknownrate);
1169 continue;
1170 }
1171
1172 /* all variables have a finite/known solution value all integer variables have an integral solution value,
1173 * and there are no continuous variables
1174 * in the sub-SCIP, all variables would be fixed, so create a new solution without solving a sub-SCIP
1175 */
1176 if( nunknown == 0 && nfracints == 0 && SCIPgetNContVars(scip) == 0 && SCIPgetNImplVars(scip) == 0 )
1177 {
1178 SCIP_SOL* newsol;
1179 SCIP_Bool stored;
1180
1181 assert(vars != NULL);
1182 assert(nvars >= 0);
1183
1184 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
1185
1186 for( v = 0; v < nvars; v++ )
1187 {
1188 solval = SCIPgetSolVal(scip, sol, vars[v]);
1189 assert(solval != SCIP_UNKNOWN); /*lint !e777*/
1190
1191 SCIP_CALL( SCIPsetSolVal(scip, newsol, vars[v], solval) );
1192 }
1193
1194 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
1195 if( stored )
1196 *result = SCIP_FOUNDSOL;
1197 }
1198 else
1199 {
1200 /* run the heuristic */
1201 SCIP_CALL( applyCompletesol(scip, heur, heurdata, result, nstallnodes, sol) );
1202 }
1203 }
1204
1205 return SCIP_OKAY;
1206 }
1207
1208
1209 /*
1210 * primal heuristic specific interface methods
1211 */
1212
1213 /** creates the completesol primal heuristic and includes it in SCIP */
SCIPincludeHeurCompletesol(SCIP * scip)1214 SCIP_RETCODE SCIPincludeHeurCompletesol(
1215 SCIP* scip /**< SCIP data structure */
1216 )
1217 {
1218 SCIP_HEURDATA* heurdata;
1219 SCIP_HEUR* heur;
1220
1221 /* create completesol primal heuristic data */
1222 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1223 assert(heurdata != NULL);
1224
1225 /* include primal heuristic */
1226 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1227 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
1228 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecCompletesol, heurdata) );
1229
1230 assert(heur != NULL);
1231
1232 /* set non fundamental callbacks via setter functions */
1233 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyCompletesol) );
1234 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeCompletesol) );
1235
1236 /* add completesol primal heuristic parameters */
1237
1238 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1239 "maximum number of nodes to regard in the subproblem",
1240 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1241
1242 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1243 "minimum number of nodes required to start the subproblem",
1244 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1245
1246 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxunknownrate",
1247 "maximal rate of unknown solution values",
1248 &heurdata->maxunknownrate, FALSE, DEFAULT_MAXUNKRATE, 0.0, 1.0, NULL, NULL) );
1249
1250 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/addallsols",
1251 "should all subproblem solutions be added to the original SCIP?",
1252 &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) );
1253
1254 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1255 "number of nodes added to the contingent of the total nodes",
1256 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1257
1258 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1259 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1260 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1261
1262 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
1263 "factor by which the limit on the number of LP depends on the node limit",
1264 &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
1265
1266 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/objweight",
1267 "weight of the original objective function (1: only original objective)",
1268 &heurdata->objweight, TRUE, DEFAULT_OBJWEIGHT, DEFAULT_MINOBJWEIGHT, 1.0, NULL, NULL) );
1269
1270 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/boundwidening",
1271 "bound widening factor applied to continuous variables (0: fix variables to given solution values, 1: relax to global bounds)",
1272 &heurdata->boundwidening, TRUE, DEFAULT_BOUNDWIDENING, 0.0, 1.0, NULL, NULL) );
1273
1274 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1275 "factor by which the incumbent should be improved at least",
1276 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1277
1278 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/ignorecont",
1279 "should number of continuous variables be ignored?",
1280 &heurdata->ignorecont, FALSE, DEFAULT_IGNORECONT, NULL, NULL) );
1281
1282 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/solutions",
1283 "heuristic stops, if the given number of improving solutions were found (-1: no limit)",
1284 &heurdata->bestsols, FALSE, DEFAULT_BESTSOLS, -1, INT_MAX, NULL, NULL) );
1285
1286 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
1287 "maximal number of iterations in propagation (-1: no limit)",
1288 &heurdata->maxproprounds, FALSE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX, NULL, NULL) );
1289
1290 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/beforepresol",
1291 "should the heuristic run before presolving?",
1292 &heurdata->beforepresol, FALSE, DEFAULT_BEFOREPRESOL, NULL, NULL) );
1293
1294 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiter",
1295 "maximal number of LP iterations (-1: no limit)",
1296 &heurdata->maxlpiter, FALSE, DEFAULT_MAXLPITER, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
1297
1298 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxcontvars",
1299 "maximal number of continuous variables after presolving",
1300 &heurdata->maxcontvars, FALSE, DEFAULT_MAXCONTVARS, -1, INT_MAX, NULL, NULL) );
1301
1302 return SCIP_OKAY;
1303 }
1304