Scippy

SCIP

Solving Constraint Integer Programs

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