1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2023 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_vbounds.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood
28 * @author Timo Berthold
29 * @author Stefan Heinz
30 * @author Jens Schulz
31 * @author Gerald Gamrath
32 *
33 * @todo allow smaller fixing rate for probing LP?
34 * @todo allow smaller fixing rate after presolve if total number of variables is small (<= 1000)?
35 *
36 * More details about the heuristic can be found in@n
37 * Structure-Based Primal Heuristics for Mixed Integer Programming@n
38 * Gerald Gamrath, Timo Berthold, Stefan Heinz, and Michael Winkler@n
39 * Optimization in the Real World, Volume 13 of the series Mathematics for Industry, pp 37-53@n
40 * Preliminary version available as <a href="https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/5551">ZIB-Report 15-26</a>.
41 */
42
43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44
45 #include "blockmemshell/memory.h"
46 #include "scip/heur_locks.h"
47 #include "scip/heur_vbounds.h"
48 #include "scip/pub_heur.h"
49 #include "scip/pub_implics.h"
50 #include "scip/pub_message.h"
51 #include "scip/pub_misc.h"
52 #include "scip/pub_tree.h"
53 #include "scip/pub_var.h"
54 #include "scip/scip_branch.h"
55 #include "scip/scip_cons.h"
56 #include "scip/scip_copy.h"
57 #include "scip/scip_general.h"
58 #include "scip/scip_heur.h"
59 #include "scip/scip_lp.h"
60 #include "scip/scip_mem.h"
61 #include "scip/scip_message.h"
62 #include "scip/scip_numerics.h"
63 #include "scip/scip_param.h"
64 #include "scip/scip_prob.h"
65 #include "scip/scip_probing.h"
66 #include "scip/scip_sol.h"
67 #include "scip/scip_solve.h"
68 #include "scip/scip_solvingstats.h"
69 #include "scip/scip_timing.h"
70 #include "scip/scip_tree.h"
71 #include "scip/scip_var.h"
72 #include <string.h>
73
74 #ifdef SCIP_STATISTIC
75 #include "scip/clock.h"
76 #endif
77
78 #define VBOUNDVARIANT_NOOBJ 0x001u
79 #define VBOUNDVARIANT_BESTBOUND 0x002u
80 #define VBOUNDVARIANT_WORSTBOUND 0x004u
81
82 #define HEUR_NAME "vbounds"
83 #define HEUR_DESC "LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood"
84 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP
85 #define HEUR_PRIORITY 2500
86 #define HEUR_FREQ 0
87 #define HEUR_FREQOFS 0
88 #define HEUR_MAXDEPTH -1
89 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
90 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
91
92 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
93 #define DEFAULT_MININTFIXINGRATE 0.65 /**< minimum percentage of integer variables that have to be fixed */
94 #define DEFAULT_MINMIPFIXINGRATE 0.65 /**< minimuskipobjm percentage of variables that have to be fixed within sub-SCIP
95 * (integer and continuous) */
96 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which vbounds heuristic should at least improve the
97 * incumbent */
98 #define DEFAULT_MINNODES 500LL /**< minimum number of nodes to regard in the subproblem */
99 #define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */
100 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
101 #define DEFAULT_MAXPROPROUNDS 2 /**< maximum number of propagation rounds during probing */
102 #define DEFAULT_MAXBACKTRACKS 10 /**< maximum number of backtracks during the fixing process */
103 #define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the original scip be copied to
104 * constraints of the subscip? */
105 #define DEFAULT_USELOCKFIXINGS FALSE /**< should more variables be fixed based on variable locks if
106 * the fixing rate was not reached?
107 */
108
109 /** which variants of the vbounds heuristic that try to stay feasible should be called? */
110 #define DEFAULT_FEASVARIANT (VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND)
111
112 /** which tightening variants of the vbounds heuristic should be called? */
113 #define DEFAULT_TIGHTENVARIANT (VBOUNDVARIANT_NOOBJ | VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND)
114
115
116 /*
117 * Data structures
118 */
119
120 /** primal heuristic data */
121 struct SCIP_HeurData
122 {
123 SCIP_VAR** vbvars; /**< topological sorted variables with respect to the variable bounds */
124 SCIP_BOUNDTYPE* vbbounds; /**< topological sorted variables with respect to the variable bounds */
125 int nvbvars; /**< number of variables in variable lower bound array */
126 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
127 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
128 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
129 SCIP_Longint usednodes; /**< nodes already used by vbounds heuristic in earlier calls */
130 SCIP_Real minintfixingrate; /**< minimum percentage of integer variables that have to be fixed */
131 SCIP_Real minmipfixingrate; /**< minimum percentage of variables that have to be fixed within sub-SCIP
132 * (integer and continuous) */
133 SCIP_Real minimprove; /**< factor by which vbounds heuristic should at least improve the incumbent */
134 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
135 SCIP_Real cutoffbound;
136 int maxproprounds; /**< maximum number of propagation rounds during probing */
137 int maxbacktracks; /**< maximum number of backtracks during the fixing process */
138 int feasvariant; /**< which variants of the vbounds heuristic that try to stay feasible
139 * should be called? */
140 int tightenvariant; /**< which tightening variants of the vbounds heuristic should be called? */
141 SCIP_Bool initialized; /**< is the candidate list initialized? */
142 SCIP_Bool applicable; /**< is the heuristic applicable? */
143 SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in
144 * subproblem? */
145 SCIP_Bool uselockfixings; /**< should more variables be fixed based on variable locks if
146 * the fixing rate was not reached? */
147 };
148
149 /**@name Heuristic defines
150 *
151 * @{
152 *
153 * The heuristic works on indices representing a bound of a variable. This index will be called bound index in the
154 * following. For a given active variable with problem index i (note that active variables have problem indices
155 * between 0 and nactivevariable - 1), the bound index of its lower bound is 2*i, the bound index of its upper
156 * bound is 2*i + 1. The other way around, a given bound index i corresponds to the variable with problem index
157 * i/2 (rounded down), and to the lower bound, if i is even, to the upper bound if i is odd.
158 * The following macros can be used to convert bound index into variable problem index and boundtype and vice versa.
159 */
160 #define getLbIndex(idx) (2*(idx))
161 #define getUbIndex(idx) (2*(idx)+1)
162 #define getVarIndex(idx) ((idx)/2)
163 #define getBoundtype(idx) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)
164 #define isIndexLowerbound(idx) ((idx) % 2 == 0)
165 #define getOtherBoundIndex(idx) (((idx) % 2 == 0) ? (idx) + 1 : (idx) - 1)
166
167
168 /*
169 * Local methods
170 */
171
172 /** reset heuristic data structure */
173 static
174 void heurdataReset(
175 SCIP_HEURDATA* heurdata /**< structure containing heurdata */
176 )
177 {
178 heurdata->vbvars = NULL;
179 heurdata->vbbounds = NULL;
180 heurdata->nvbvars = 0;
181 heurdata->initialized = FALSE;
182 heurdata->applicable = FALSE;
183 }
184
185
186 /** performs depth-first-search in the implicitly given directed graph from the given start index */
187 static
188 SCIP_RETCODE dfs(
189 SCIP* scip, /**< SCIP data structure */
190 int startnode, /**< node to start the depth-first-search */
191 SCIP_Shortbool* visited, /**< array to store for each node, whether it was already visited */
192 int* dfsstack, /**< array of size number of nodes to store the stack;
193 * only needed for performance reasons */
194 int* stacknextedge, /**< array of size number of nodes to store the number of adjacent nodes
195 * already visited for each node on the stack; only needed for
196 * performance reasons */
197 int* stacknextcliquevar, /**< array of size number of nodes to store the number of variables
198 * already evaluated for the clique currently being evaluated */
199 int* cliqueexit, /**< exit node when entering a clique */
200 int* dfsnodes, /**< array of nodes that can be reached starting at startnode, in reverse
201 * dfs order */
202 int* ndfsnodes /**< pointer to store number of nodes that can be reached starting at
203 * startnode */
204 )
205 {
206 SCIP_VAR** vars;
207 SCIP_VAR* startvar;
208 SCIP_VAR** vbvars;
209 SCIP_Real* coefs;
210 SCIP_Bool lower;
211 SCIP_Bool found;
212 int maxstacksize;
213 int stacksize;
214 int curridx;
215 int idx;
216 int nvbvars;
217 int i;
218
219 assert(startnode >= 0);
220 assert(startnode < 2 * SCIPgetNVars(scip));
221 assert(visited != NULL);
222 assert(visited[startnode] == FALSE);
223 assert(dfsstack != NULL);
224 assert(dfsnodes != NULL);
225 assert(ndfsnodes != NULL);
226
227 vars = SCIPgetVars(scip);
228
229 /* put start node on the stack */
230 dfsstack[0] = startnode;
231 stacknextcliquevar[0] = 0;
232 stacknextedge[0] = 0;
233 maxstacksize = 1;
234 stacksize = 1;
235 idx = -1;
236
237 /* we run until no more bounds indices are on the stack */
238 while( stacksize > 0 )
239 {
240 /* get next node from stack */
241 curridx = dfsstack[stacksize - 1];
242
243 /* mark current node as visited */
244 assert(visited[curridx] == (stacknextedge[stacksize - 1] != 0));
245 visited[curridx] = TRUE;
246 found = FALSE;
247
248 startvar = vars[getVarIndex(curridx)];
249 lower = isIndexLowerbound(curridx);
250
251 if( stacknextedge[stacksize - 1] >= 0 )
252 {
253 /* go over edges corresponding to varbounds */
254 if( lower )
255 {
256 vbvars = SCIPvarGetVlbVars(startvar);
257 coefs = SCIPvarGetVlbCoefs(startvar);
258 nvbvars = SCIPvarGetNVlbs(startvar);
259 }
260 else
261 {
262 vbvars = SCIPvarGetVubVars(startvar);
263 coefs = SCIPvarGetVubCoefs(startvar);
264 nvbvars = SCIPvarGetNVubs(startvar);
265 }
266
267 /* iterate over all vbounds for the given bound */
268 for( i = stacknextedge[stacksize - 1]; i < nvbvars; ++i )
269 {
270 if( !SCIPvarIsActive(vbvars[i]) )
271 continue;
272
273 idx = (SCIPisPositive(scip, coefs[i]) == lower) ? getLbIndex(SCIPvarGetProbindex(vbvars[i])) : getUbIndex(SCIPvarGetProbindex(vbvars[i]));
274 assert(idx >= 0);
275
276 /* break when the first unvisited node is reached */
277 if( !visited[idx] )
278 break;
279 }
280
281 /* we stopped because we found an unhandled node and not because we reached the end of the list */
282 if( i < nvbvars )
283 {
284 assert(!visited[idx]);
285
286 /* put the adjacent node onto the stack */
287 dfsstack[stacksize] = idx;
288 stacknextedge[stacksize] = 0;
289 stacknextcliquevar[stacksize] = 0;
290 stacknextedge[stacksize - 1] = i + 1;
291 stacksize++;
292 assert(stacksize <= 2* SCIPgetNVars(scip));
293
294 /* restart while loop, get next index from stack */
295 continue;
296 }
297 }
298
299 stacknextedge[stacksize - 1] = -1;
300
301 /* treat cliques */
302 if( SCIPvarIsBinary(startvar) )
303 {
304 SCIP_CLIQUE** cliques = SCIPvarGetCliques(startvar, !lower);
305 int ncliques = SCIPvarGetNCliques(startvar, !lower);
306 int j;
307
308 /* iterate over all not yet handled cliques and search for an unvisited node */
309 for( j = -stacknextedge[stacksize - 1] - 1; j < ncliques; ++j )
310 {
311 SCIP_VAR** cliquevars;
312 SCIP_Bool* cliquevals;
313 int ncliquevars;
314
315 /* the first time we evaluate this clique for the current node */
316 if( stacknextcliquevar[stacksize - 1] == 0 )
317 {
318 if( cliqueexit[SCIPcliqueGetIndex(cliques[j])] > 0 )
319 {
320 if( !visited[cliqueexit[SCIPcliqueGetIndex(cliques[j])] - 1] &&
321 cliqueexit[SCIPcliqueGetIndex(cliques[j])] - 1 != curridx )
322 {
323 stacknextedge[stacksize - 1] = -j - 2;
324 stacknextcliquevar[stacksize - 1] = 0;
325 idx = cliqueexit[SCIPcliqueGetIndex(cliques[j])] - 1;
326 cliqueexit[SCIPcliqueGetIndex(cliques[j])] = -1;
327 found = TRUE;
328 }
329 else
330 continue;
331 }
332 else if( cliqueexit[SCIPcliqueGetIndex(cliques[j])] == 0 )
333 {
334 cliqueexit[SCIPcliqueGetIndex(cliques[j])] = getOtherBoundIndex(curridx) + 1;
335 }
336 else
337 continue;
338 }
339 if( !found )
340 {
341 cliquevars = SCIPcliqueGetVars(cliques[j]);
342 cliquevals = SCIPcliqueGetValues(cliques[j]);
343 ncliquevars = SCIPcliqueGetNVars(cliques[j]);
344
345 for( i = 0; i < ncliquevars; ++i )
346 {
347 assert(SCIPvarIsActive(cliquevars[i]));
348
349 if( cliquevars[i] == startvar )
350 continue;
351
352 if( cliquevals[i] )
353 idx = getLbIndex(SCIPvarGetProbindex(cliquevars[i]));
354 else
355 idx = getUbIndex(SCIPvarGetProbindex(cliquevars[i]));
356
357 assert(idx >= 0 && idx < 2 * SCIPgetNVars(scip));
358
359 /* break when the first unvisited node is reached */
360 if( idx >= 0 && !visited[idx] )
361 {
362 if( i < ncliquevars - 1 )
363 {
364 stacknextedge[stacksize - 1] = -j - 1;
365 stacknextcliquevar[stacksize - 1] = i + 1;
366 }
367 else
368 {
369 stacknextedge[stacksize - 1] = -j - 2;
370 stacknextcliquevar[stacksize - 1] = 0;
371 }
372 found = TRUE;
373 break;
374 }
375 }
376 }
377 if( found )
378 {
379 assert(!visited[idx]);
380
381 /* put the adjacent node onto the stack */
382 dfsstack[stacksize] = idx;
383 stacknextedge[stacksize] = 0;
384 stacknextcliquevar[stacksize] = 0;
385 stacksize++;
386 assert(stacksize <= 2* SCIPgetNVars(scip));
387
388 break;
389 }
390 }
391 /* restart while loop, get next index from stack */
392 if( found )
393 continue;
394 }
395
396 maxstacksize = MAX(maxstacksize, stacksize);
397
398 /* the current node was completely handled, remove it from the stack */
399 stacksize--;
400
401 if( (maxstacksize > 1) && SCIPvarGetType(startvar) != SCIP_VARTYPE_CONTINUOUS )
402 {
403 /* store node in the sorted nodes array */
404 dfsnodes[(*ndfsnodes)] = curridx;
405 (*ndfsnodes)++;
406 }
407 else
408 visited[curridx] = FALSE;
409 }
410
411 return SCIP_OKAY;
412 }
413
414
415 /** sort the bounds of variables topologically */
416 static
417 SCIP_RETCODE topologicalSort(
418 SCIP* scip, /**< SCIP data structure */
419 int* vbvars, /**< array to store variable bounds in topological order */
420 int* nvbvars /**< pointer to store number of variable bounds in the graph */
421 )
422 {
423 int* dfsstack;
424 int* stacknextedge;
425 int* stacknextcliquevar;
426 int* cliqueexit;
427 SCIP_Shortbool* visited;
428 int nbounds;
429 int i;
430
431 assert(scip != NULL);
432
433 nbounds = 2 * SCIPgetNVars(scip);
434
435 SCIP_CALL( SCIPallocBufferArray(scip, &dfsstack, nbounds) );
436 SCIP_CALL( SCIPallocBufferArray(scip, &stacknextedge, nbounds) );
437 SCIP_CALL( SCIPallocBufferArray(scip, &stacknextcliquevar, nbounds) );
438 SCIP_CALL( SCIPallocClearBufferArray(scip, &cliqueexit, SCIPgetNCliques(scip)) );
439 SCIP_CALL( SCIPallocClearBufferArray(scip, &visited, nbounds) );
440
441 /* while there are unvisited nodes, run dfs on the inverse graph starting from one of these nodes; the dfs orders are
442 * stored in the topoorder array, later dfs calls are just appended after the stacks of previous dfs calls, which
443 * gives us a topological order
444 */
445 for( i = 0; i < nbounds; ++i )
446 {
447 if( !visited[i] )
448 {
449 SCIP_CALL( dfs(scip, i, visited, dfsstack, stacknextedge, stacknextcliquevar, cliqueexit, vbvars, nvbvars) );
450 }
451 }
452 assert(*nvbvars <= nbounds);
453
454 SCIPfreeBufferArray(scip, &visited);
455 SCIPfreeBufferArray(scip, &cliqueexit);
456 SCIPfreeBufferArray(scip, &stacknextcliquevar);
457 SCIPfreeBufferArray(scip, &stacknextedge);
458 SCIPfreeBufferArray(scip, &dfsstack);
459
460 return SCIP_OKAY;
461 }
462
463 /** initialize candidate lists */
464 static
465 SCIP_RETCODE initializeCandsLists(
466 SCIP* scip, /**< original SCIP data structure */
467 SCIP_HEURDATA* heurdata /**< structure containing heurdata */
468 )
469 {
470 SCIP_VAR** vars;
471 int* vbs;
472 int nvars;
473 int nvbs;
474 int v;
475
476 SCIPdebugMsg(scip, "initialize variable bound heuristic (%s)\n", SCIPgetProbName(scip));
477
478 vars = SCIPgetVars(scip);
479 nvars = SCIPgetNIntVars(scip) + SCIPgetNBinVars(scip) + SCIPgetNImplVars(scip);
480 nvbs = 0;
481
482 /* initialize data */
483 heurdata->usednodes = 0;
484 heurdata->initialized = TRUE;
485
486 if( nvars == 0 )
487 return SCIP_OKAY;
488
489 /* allocate memory for the arrays of the heurdata */
490 SCIP_CALL( SCIPallocBufferArray(scip, &vbs, 2 * nvars) );
491
492 /* create the topological sorted variable array with respect to the variable bounds */
493 SCIP_CALL( topologicalSort(scip, vbs, &nvbs) );
494
495 /* check if the candidate list contains enough candidates */
496 if( nvbs > 0 && nvbs >= 0.1 * heurdata->minintfixingrate * nvars )
497 {
498 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->vbvars, nvbs) );
499 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->vbbounds, nvbs) );
500
501 /* capture variable candidate list */
502 for( v = 0; v < nvbs; ++v )
503 {
504 heurdata->vbvars[v] = vars[getVarIndex(vbs[v])];
505 heurdata->vbbounds[v] = getBoundtype(vbs[v]);
506 assert(SCIPvarIsIntegral(heurdata->vbvars[v]));
507
508 SCIP_CALL( SCIPcaptureVar(scip, heurdata->vbvars[v]) );
509 }
510
511 heurdata->nvbvars = nvbs;
512 heurdata->applicable = TRUE;
513 }
514
515 /* free buffer arrays */
516 SCIPfreeBufferArray(scip, &vbs);
517
518 SCIPstatisticMessage("vbvars %.3g (%s)\n",
519 (nvbs * 100.0) / nvars, SCIPgetProbName(scip));
520
521 /* if there is already a solution, add an objective cutoff */
522 if( SCIPgetNSols(scip) > 0 )
523 {
524 SCIP_Real upperbound;
525 SCIP_Real minimprove;
526 SCIP_Real cutoffbound;
527
528 minimprove = heurdata->minimprove;
529 assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
530
531 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
532
533 if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
534 {
535 cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * SCIPgetLowerbound(scip);
536 }
537 else
538 {
539 if( SCIPgetUpperbound ( scip ) >= 0 )
540 cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip);
541 else
542 cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip);
543 }
544 heurdata->cutoffbound = MIN(upperbound, cutoffbound);
545 }
546 else
547 heurdata->cutoffbound = SCIPinfinity(scip);
548 return SCIP_OKAY;
549 }
550
551 /** apply variable bound fixing during probing */
552 static
553 SCIP_RETCODE applyVboundsFixings(
554 SCIP* scip, /**< original SCIP data structure */
555 SCIP_HEURDATA* heurdata, /**< structure containing heurdata */
556 SCIP_VAR** vars, /**< variables to fix during probing */
557 int nvbvars, /**< number of variables in the variable bound graph */
558 SCIP_Bool tighten, /**< should variables be fixed to cause other fixings? */
559 int obj, /**< should the objective be taken into account? */
560 SCIP_Bool* allobj1, /**< pointer to store whether all variables were fixed according to obj=1 scheme */
561 SCIP_Bool* allobj2, /**< pointer to store whether all variables were fixed according to obj=2 scheme */
562 SCIP_Bool* backtracked, /**< was backtracking performed at least once? */
563 SCIP_Bool* infeasible /**< pointer to store whether propagation detected infeasibility */
564 )
565 {
566 SCIP_VAR* lastvar;
567 SCIP_VAR* var;
568 SCIP_Real lastfixval;
569 SCIP_Bool lastfixedlb;
570 SCIP_Bool fixtolower;
571 SCIP_BOUNDTYPE bound;
572 int nbacktracks = 0;
573 int v;
574
575 /* loop over variables in topological order */
576 for( v = 0; v < nvbvars && !(*infeasible); ++v )
577 {
578 var = vars[v];
579 bound = heurdata->vbbounds[v];
580
581 /*SCIPdebugMsg(scip, "topoorder[%d]: %s(%s) (%s) [%g,%g] (obj=%g)\n", v,
582 bound == SCIP_BOUNDTYPE_UPPER ? "ub" : "lb", SCIPvarGetName(var),
583 SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ? "c" : "d",
584 SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetObj(var));*/
585
586 /* only check integer or binary variables */
587 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
588 continue;
589
590 /* skip variables which are already fixed */
591 if( SCIPvarGetLbLocal(var) + 0.5 > SCIPvarGetUbLocal(var) )
592 continue;
593
594 /* there are two cases for tighten:
595 * 1) tighten == TRUE: we go through the list of variables and fix variables to force propagation;
596 * this is be obtained by fixing the variable to the other bound (which means
597 * that the current bound is changed and so, much propagation is triggered
598 * since we are starting with the bounds which are most influential).
599 * 2) tighten == FALSE: we fix variables to avoid too much propagation in order to avoid reaching
600 * infeasibility. Therefore, we fix the variable to the current bound, so that
601 * this bound is not changed and does not propagate. The other bound is changed
602 * and propagates, but is later in the order, so less influential.
603 */
604 fixtolower = (tighten == (bound == SCIP_BOUNDTYPE_UPPER));
605
606 /* if we want to take into account the objective function coefficients, we only perform a fixing if the variable
607 * would be fixed to its best bound; otherwise, we just continue
608 */
609 if( ((SCIPvarGetObj(var) >= 0) != fixtolower) )
610 {
611 if( obj == 1 )
612 continue;
613 else
614 *allobj1 = FALSE;
615 }
616 /* if we want to take into account the objective function coefficients but reverted, we only perform a fixing if the variable
617 * would be fixed to its worst bound; otherwise, we just continue
618 */
619 if( ((SCIPvarGetObj(var) >= 0) == fixtolower) )
620 {
621 if( obj == 2 )
622 continue;
623 else
624 *allobj2 = FALSE;
625 }
(1) Event value_overwrite: |
Overwriting previous write to "lastvar" with value from "var". |
Also see events: |
[assigned_pointer] |
626 lastvar = var;
627
628 /* fix the variable to its bound */
629 if( fixtolower )
630 {
631 /* we cannot fix to infinite bounds */
632 if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)) )
633 continue;
634
635 /* only open a new probing node if we will not exceed the maximal tree depth */
636 if( SCIP_MAXTREEDEPTH > SCIPgetDepth(scip) )
637 {
638 SCIP_CALL( SCIPnewProbingNode(scip) );
639 }
640
641 /* fix variable to lower bound */
642 SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetLbLocal(var)) );
643 SCIPdebugMsg(scip, "fixing %d: variable <%s> (obj=%g) to lower bound <%g> (%d pseudo cands)\n",
644 v, SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetLbLocal(var), SCIPgetNPseudoBranchCands(scip));
645 lastfixedlb = TRUE;
646 lastfixval = SCIPvarGetLbLocal(var);
647 }
648 else
649 {
650 /* we cannot fix to infinite bounds */
651 if( SCIPisInfinity(scip, SCIPvarGetUbLocal(var)) )
652 continue;
653
654 /* only open a new probing node if we will not exceed the maximal tree depth */
655 if( SCIP_MAXTREEDEPTH > SCIPgetDepth(scip) )
656 {
657 SCIP_CALL( SCIPnewProbingNode(scip) );
658 }
659
660 /* fix variable to upper bound */
661 SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetUbLocal(var)) );
662 SCIPdebugMsg(scip, "fixing %d: variable <%s> (obj=%g) to upper bound <%g> (%d pseudo cands)\n",
663 v, SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetUbLocal(var), SCIPgetNPseudoBranchCands(scip));
664 lastfixedlb = FALSE;
665 lastfixval = SCIPvarGetUbLocal(var);
666 }
667
668 /* check if problem is already infeasible */
669 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, infeasible, NULL) );
670
671 /* probing detected infeasibility: backtrack */
672 if( *infeasible )
673 {
674 assert(lastvar != NULL);
675
676 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip) - 1) );
677 ++nbacktracks;
678 *infeasible = FALSE;
679
680 /* increase the lower bound of the variable which caused the infeasibility */
681 if( lastfixedlb && lastfixval + 0.5 < SCIPvarGetUbLocal(lastvar) )
682 {
683 if( lastfixval + 0.5 > SCIPvarGetLbLocal(lastvar) )
684 {
685 SCIP_CALL( SCIPchgVarLbProbing(scip, lastvar, lastfixval + 1.0) );
686 }
687 }
688 else if( !lastfixedlb && lastfixval - 0.5 > SCIPvarGetLbLocal(lastvar) )
689 {
690 if( lastfixval - 0.5 < SCIPvarGetUbLocal(lastvar) )
691 {
692 SCIP_CALL( SCIPchgVarUbProbing(scip, lastvar, lastfixval - 1.0) );
693 }
694 }
695 /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a valid
696 * global bound for the last fixed variable that conflicts with applying the reverse bound change after backtracking;
697 * in that case, we ran into a deadend and stop
698 */
699 else
700 {
701 *infeasible = TRUE;
702 }
(2) Event assigned_pointer: |
Assigning value "NULL" to "lastvar" here, but that stored value is overwritten before it can be used. |
Also see events: |
[value_overwrite] |
703 lastvar = NULL;
704
705 if( !(*infeasible) )
706 {
707 /* propagate fixings */
708 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, infeasible, NULL) );
709
710 SCIPdebugMessage("backtrack %d was %sfeasible\n", nbacktracks, (*infeasible ? "in" : ""));
711 }
712
713 if( *infeasible )
714 {
715 SCIPdebugMsg(scip, "probing was infeasible after %d backtracks\n", nbacktracks);
716
717 break;
718 }
719 else if( nbacktracks > heurdata->maxbacktracks )
720 {
721 SCIPdebugMsg(scip, "interrupt probing after %d backtracks\n", nbacktracks);
722 break;
723 }
724 }
725 }
726
727 *backtracked = (nbacktracks > 0);
728
729 return SCIP_OKAY;
730 }
731
732 /** copy problem to sub-SCIP, solve it, and add solutions */
733 static
734 SCIP_RETCODE setupAndSolveSubscip(
735 SCIP* scip, /**< original SCIP data structure */
736 SCIP* subscip, /**< SCIP structure of the subproblem */
737 SCIP_HEUR* heur, /**< heuristic */
738 SCIP_VAR** vars, /**< variables of the main SCIP */
739 int nvars, /**< number of variables of the main SCIP */
740 SCIP_Longint nstallnodes, /**< stalling node limit for the sub-SCIP */
741 SCIP_Real lowerbound, /**< lower bound of the main SCIP / current subproblem */
742 int* nprevars, /**< pointer to store the number of presolved variables */
743 SCIP_Bool* wasfeas, /**< pointer to store if a feasible solution was found */
744 SCIP_RESULT* result /**< pointer to store the result */
745 )
746 {
747 SCIP_HEURDATA* heurdata;
748 SCIP_VAR** subvars;
749 SCIP_HASHMAP* varmap;
750 int i;
751
752 assert(scip != NULL);
753 assert(subscip != NULL);
754 assert(heur != NULL);
755
756 heurdata = SCIPheurGetData(heur);
757 assert(heurdata != NULL);
758
759 /* create the variable mapping hash map */
760 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
761
762 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "_vbounds", NULL, NULL, 0, FALSE, FALSE, FALSE,
763 TRUE, NULL) );
764
765 if( heurdata->copycuts )
766 {
767 /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
768 SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, FALSE, NULL) );
769 }
770
771 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
772
773 for( i = 0; i < nvars; i++ )
774 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
775
776 /* free hash map */
777 SCIPhashmapFree(&varmap);
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", 5) );
785 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
786 #else
787 /* disable statistic timing inside sub SCIP and output to console */
788 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
789 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
790 #endif
791
792 /* set limits for the subproblem */
793 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
794 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
795 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
796
797 /* speed up sub-SCIP by not checking dual LP feasibility */
798 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
799
800 /* forbid call of heuristics and separators solving sub-CIPs */
801 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
802
803 /* disable cutting plane separation */
804 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
805
806 /* disable expensive presolving */
807 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
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 /* set a cutoff bound */
816 if( SCIPgetNSols(scip) > 0 )
817 {
818 SCIP_Real upperbound;
819 SCIP_Real minimprove;
820 SCIP_Real cutoffbound;
821
822 minimprove = heurdata->minimprove;
823 assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
824
825 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
826
827 if( !SCIPisInfinity(scip, -1.0 * lowerbound) )
828 {
829 cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * lowerbound;
830 }
831 else
832 {
833 if( SCIPgetUpperbound ( scip ) >= 0 )
834 cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip);
835 else
836 cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip);
837 }
838 heurdata->cutoffbound = MIN(upperbound, cutoffbound);
839 }
840
841 if( !SCIPisInfinity(scip, heurdata->cutoffbound) )
842 {
843 SCIP_CALL( SCIPsetObjlimit(subscip, heurdata->cutoffbound) );
844 SCIPdebugMsg(scip, "setting objlimit for subscip to %g\n", heurdata->cutoffbound);
845 }
846
847 SCIPdebugMsg(scip, "starting solving vbound-submip at time %g\n", SCIPgetSolvingTime(scip));
848
849 /* solve the subproblem */
850 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
851 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
852 */
853 SCIP_CALL_ABORT( SCIPpresolve(subscip) );
854
855 SCIPdebugMsg(scip, "vbounds heuristic presolved subproblem at time %g : %d vars, %d cons; fixing value = %g\n",
856 SCIPgetSolvingTime(scip), SCIPgetNVars(subscip), SCIPgetNConss(subscip),
857 ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars));
858
859 *nprevars = SCIPgetNVars(subscip);
860
861 /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
862 * to ensure that not only the MIP but also the LP relaxation is easy enough
863 */
864 if( ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars) >= heurdata->minmipfixingrate )
865 {
866 SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
867
868 SCIP_CALL_ABORT( SCIPsolve(subscip) );
869
870 SCIPdebugMsg(scip, "ending solving vbounds-submip at time %g, status = %d\n", SCIPgetSolvingTime(scip), SCIPgetStatus(subscip));
871
872 /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible ->
873 * try all solutions until one was accepted
874 */
875 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, wasfeas, NULL) );
876 if( (*wasfeas) )
877 {
878 SCIPdebugMsg(scip, "found feasible solution in sub-MIP\n");
879 *result = SCIP_FOUNDSOL;
880 }
881 }
882
883 #ifdef SCIP_DEBUG
884 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
885 #endif
886
887 /* free subproblem */
888 SCIPfreeBufferArray(scip, &subvars);
889
890 return SCIP_OKAY;
891 }
892
893 /** main procedure of the vbounds heuristic */
894 static
895 SCIP_RETCODE applyVbounds(
896 SCIP* scip, /**< original SCIP data structure */
897 SCIP_HEUR* heur, /**< heuristic */
898 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
899 SCIP_VAR** vbvars, /**< variables to fix during probing */
900 int nvbvars, /**< number of variables to fix */
901 SCIP_Bool tighten, /**< should variables be fixed to cause other fixings? */
902 int obj, /**< should the objective be taken into account? */
903 SCIP_Bool* skipobj1, /**< pointer to store whether the run with obj=1 can be skipped, or NULL */
904 SCIP_Bool* skipobj2, /**< pointer to store whether the run with obj=2 can be skipped, or NULL */
905 SCIP_RESULT* result /**< pointer to store the result */
906 )
907 {
908 SCIPstatistic( SCIP_CLOCK* clock; )
909 SCIP_VAR** vars;
910 SCIP_Longint nstallnodes;
911 SCIP_LPSOLSTAT lpstatus;
912 SCIP_Real lowerbound;
913 SCIP_Bool wasfeas = FALSE;
914 SCIP_Bool cutoff;
915 SCIP_Bool lperror;
916 SCIP_Bool solvelp;
917 SCIP_Bool allobj1 = TRUE;
918 SCIP_Bool allobj2 = TRUE;
919 SCIP_Bool backtracked = TRUE;
920 int oldnpscands;
921 int npscands;
922 int nvars;
923 int nprevars;
924
925 assert(heur != NULL);
926 assert(heurdata != NULL);
927 assert(nvbvars > 0);
928
929 /* initialize default values */
930 cutoff = FALSE;
931
932 if( skipobj1 != NULL )
933 *skipobj1 = FALSE;
934 if( skipobj2 != NULL )
935 *skipobj2 = FALSE;
936
937 if( nvbvars < SCIPgetNVars(scip) * heurdata->minintfixingrate )
938 return SCIP_OKAY;
939
940 if( *result == SCIP_DIDNOTRUN )
941 *result = SCIP_DIDNOTFIND;
942
943 lowerbound = SCIPgetLowerbound(scip);
944
945 oldnpscands = SCIPgetNPseudoBranchCands(scip);
946
947 /* calculate the maximal number of branching nodes until heuristic is aborted */
948 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
949
950 /* reward variable bounds heuristic if it succeeded often */
951 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
952 nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
953 nstallnodes += heurdata->nodesofs;
954
955 /* determine the node limit for the current process */
956 nstallnodes -= heurdata->usednodes;
957 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
958
959 SCIPdebugMsg(scip, "apply variable bounds heuristic at node %lld on %d variable bounds, tighten: %u obj: %d\n",
960 SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), nvbvars, tighten, obj);
961
962 /* check whether we have enough nodes left to call subproblem solving */
963 if( nstallnodes < heurdata->minnodes )
964 {
965 SCIPdebugMsg(scip, "skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
966 return SCIP_OKAY;
967 }
968
969 if( SCIPisStopped(scip) )
970 return SCIP_OKAY;
971
972 SCIPstatistic( SCIP_CALL( SCIPcreateClock(scip, &clock) ) );
973 SCIPstatistic( SCIP_CALL( SCIPstartClock(scip, clock) ) );
974
975 /* check whether the LP should be solved at the current node in the tree to determine whether the heuristic
976 * is allowed to solve an LP
977 */
978 solvelp = SCIPhasCurrentNodeLP(scip);
979
980 if( !SCIPisLPConstructed(scip) && solvelp )
981 {
982 SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
983
984 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
985 if( cutoff )
986 {
987 SCIP_CALL( SCIPcutoffNode(scip, SCIPgetCurrentNode(scip)) );
988 goto TERMINATE;
989 }
990
991 SCIP_CALL( SCIPflushLP(scip) );
992 }
993
994 /* get variable data of original problem */
995 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
996
997 SCIPstatistic( nprevars = nvars; )
998
999 /* start probing */
1000 SCIP_CALL( SCIPstartProbing(scip) );
1001
1002 #ifdef COLLECTSTATISTICS
1003 SCIPenableVarHistory(scip);
1004 #endif
1005
1006 /* apply the variable fixings */
1007 SCIP_CALL( applyVboundsFixings(scip, heurdata, vbvars, nvbvars, tighten, obj, &allobj1, &allobj2, &backtracked, &cutoff) );
1008
1009 if( skipobj1 != NULL )
1010 *skipobj1 = allobj1;
1011
1012 if( skipobj2 != NULL )
1013 *skipobj2 = allobj2;
1014
1015 if( cutoff || SCIPisStopped(scip) )
1016 goto TERMINATE;
1017
1018 /* check that we had enough fixings */
1019 npscands = SCIPgetNPseudoBranchCands(scip);
1020
1021 SCIPdebugMsg(scip, "npscands=%d, oldnpscands=%d, heurdata->minintfixingrate=%g\n", npscands, oldnpscands, heurdata->minintfixingrate);
1022
1023 /* check fixing rate */
1024 if( npscands > oldnpscands * (1.0 - heurdata->minintfixingrate) )
1025 {
1026 if( heurdata->uselockfixings && npscands <= 2.0 * oldnpscands * (1.0 - heurdata->minintfixingrate) )
1027 {
1028 SCIP_Bool allrowsfulfilled = FALSE;
1029
1030 SCIP_CALL( SCIPapplyLockFixings(scip, NULL, &cutoff, &allrowsfulfilled) );
1031
1032 if( cutoff || SCIPisStopped(scip) )
1033 {
1034 SCIPdebugMsg(scip, "cutoff or timeout in locks fixing\n");
1035 goto TERMINATE;
1036 }
1037
1038 npscands = SCIPgetNPseudoBranchCands(scip);
1039
1040 SCIPdebugMsg(scip, "after lockfixings: npscands=%d, oldnpscands=%d, allrowsfulfilled=%u, heurdata->minintfixingrate=%g\n",
1041 npscands, oldnpscands, allrowsfulfilled, heurdata->minintfixingrate);
1042
1043 if( !allrowsfulfilled && npscands > oldnpscands * (1 - heurdata->minintfixingrate) )
1044 {
1045 SCIPdebugMsg(scip, "--> too few fixings\n");
1046
1047 goto TERMINATE;
1048 }
1049 }
1050 else
1051 {
1052 SCIPdebugMsg(scip, "--> too few fixings\n");
1053
1054 goto TERMINATE;
1055 }
1056 }
1057
1058 assert(!cutoff);
1059
1060 /*************************** Probing LP Solving ***************************/
1061 lpstatus = SCIP_LPSOLSTAT_ERROR;
1062 lperror = FALSE;
1063 /* solve lp only if the problem is still feasible */
1064 if( solvelp )
1065 {
1066 char strbuf[SCIP_MAXSTRLEN];
1067 int ncols;
1068
1069 /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
1070 * which the user sees no output; more detailed probing stats only in debug mode */
1071 ncols = SCIPgetNLPCols(scip);
1072 if( !SCIPisLPSolBasic(scip) && ncols > 1000 )
1073 {
1074 int nunfixedcols = SCIPgetNUnfixedLPCols(scip);
1075
1076 if( nunfixedcols > 0.5 * ncols )
1077 {
1078 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1079 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
1080 100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
1081 }
1082 }
1083 SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n",
1084 SCIPsnprintfProbingStats(scip, strbuf, SCIP_MAXSTRLEN));
1085
1086 /* solve LP; errors in the LP solver should not kill the overall solving process, if the LP is just needed for a
1087 * heuristic. hence in optimized mode, the return code is caught and a warning is printed, only in debug mode,
1088 * SCIP will stop.
1089 */
1090 SCIPdebugMsg(scip, "starting solving vbound-lp at time %g\n", SCIPgetSolvingTime(scip));
1091 #ifdef NDEBUG
1092 {
1093 SCIP_Bool retstat;
1094 retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL);
1095 if( retstat != SCIP_OKAY )
1096 {
1097 SCIPwarningMessage(scip, "Error while solving LP in vbound heuristic; LP solve terminated with code <%d>\n",
1098 retstat);
1099 }
1100 }
1101 #else
1102 SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) );
1103 #endif
1104 SCIPdebugMsg(scip, "ending solving vbound-lp at time %g\n", SCIPgetSolvingTime(scip));
1105
1106 lpstatus = SCIPgetLPSolstat(scip);
1107
1108 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
1109 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, lpstatus);
1110 }
1111
1112 /* check if this is a feasible solution */
1113 if( lpstatus == SCIP_LPSOLSTAT_OPTIMAL && !lperror )
1114 {
1115 SCIP_Bool stored;
1116 SCIP_Bool success;
1117 SCIP_SOL* sol;
1118
1119 lowerbound = SCIPgetLPObjval(scip);
1120
1121 /* copy the current LP solution to the working solution */
1122 SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
1123 SCIP_CALL( SCIPlinkLPSol(scip, sol) );
1124
1125 SCIP_CALL( SCIProundSol(scip, sol, &success) );
1126
1127 if( success )
1128 {
1129 SCIPdebugMsg(scip, "vbound heuristic found roundable primal solution: obj=%g\n",
1130 SCIPgetSolOrigObj(scip, sol));
1131
1132 /* check solution for feasibility, and add it to solution store if possible.
1133 * Neither integrality nor feasibility of LP rows have to be checked, because they
1134 * are guaranteed by the heuristic at this stage.
1135 */
1136 #ifdef SCIP_DEBUG
1137 SCIP_CALL( SCIPtrySol(scip, sol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) );
1138 #else
1139 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, FALSE, &stored) );
1140 #endif
1141
1142 #ifdef SCIP_DEBUG
1143 SCIP_CALL( SCIPcheckSol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, &wasfeas) );
1144 assert(wasfeas);
1145 SCIPdebugMsg(scip, "found feasible solution by LP rounding: %16.9g\n", SCIPgetSolOrigObj(scip, sol));
1146 #endif
1147
1148 if( stored )
1149 *result = SCIP_FOUNDSOL;
1150
1151 SCIP_CALL( SCIPfreeSol(scip, &sol) );
1152
1153 /* we found a solution, so we are done */
1154 goto TERMINATE;
1155 }
1156
1157 SCIP_CALL( SCIPfreeSol(scip, &sol) );
1158 }
1159 /*************************** END Probing LP Solving ***************************/
1160
1161 /*************************** Start Subscip Solving ***************************/
1162 /* if no solution has been found --> fix all other variables by subscip if necessary */
1163 if( !lperror && lpstatus != SCIP_LPSOLSTAT_INFEASIBLE && lpstatus != SCIP_LPSOLSTAT_OBJLIMIT )
1164 {
1165 SCIP* subscip;
1166 SCIP_RETCODE retcode;
1167 SCIP_Bool valid;
1168
1169 /* check whether there is enough time and memory left */
1170 SCIP_CALL( SCIPcheckCopyLimits(scip, &valid) );
1171
1172 if( !valid )
1173 goto TERMINATE;
1174
1175 /* create subproblem */
1176 SCIP_CALL( SCIPcreate(&subscip) );
1177
1178 retcode = setupAndSolveSubscip(scip, subscip, heur, vars, nvars, nstallnodes, lowerbound,
1179 &nprevars, &wasfeas, result);
1180
1181 SCIP_CALL( SCIPfree(&subscip) );
1182
1183 SCIP_CALL( retcode );
1184 }
1185
1186 /*************************** End Subscip Solving ***************************/
1187
1188 TERMINATE:
1189 #ifdef SCIP_STATISTIC
1190 SCIP_CALL( SCIPstopClock(scip, clock) );
1191 SCIPstatisticMessage("vbound: tighten=%u obj=%d nvars=%d presolnvars=%d ratio=%.2f infeas=%u found=%d time=%.4f\n",
1192 tighten, obj, nvars, nprevars, (nvars - nprevars) / (SCIP_Real)nvars, cutoff,
1193 wasfeas ? 1 : 0, SCIPclockGetTime(clock) );
1194 #endif
1195
1196 SCIPstatistic( SCIP_CALL( SCIPfreeClock(scip, &clock) ) );
1197
1198 /* exit probing mode */
1199 if( SCIPinProbing(scip) )
1200 {
1201 SCIP_CALL( SCIPendProbing(scip) );
1202 }
1203
1204 return SCIP_OKAY; /*lint !e438*/
1205 }
1206
1207
1208 /*
1209 * Callback methods of primal heuristic
1210 */
1211
1212 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1213 static
1214 SCIP_DECL_HEURCOPY(heurCopyVbounds)
1215 { /*lint --e{715}*/
1216 assert(scip != NULL);
1217 assert(heur != NULL);
1218 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1219
1220 /* call inclusion method of heuristic */
1221 SCIP_CALL( SCIPincludeHeurVbounds(scip) );
1222
1223 return SCIP_OKAY;
1224 }
1225
1226 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1227 static
1228 SCIP_DECL_HEURFREE(heurFreeVbounds)
1229 { /*lint --e{715}*/
1230 SCIP_HEURDATA* heurdata;
1231
1232 /* free heuristic data */
1233 heurdata = SCIPheurGetData(heur);
1234
1235 SCIPfreeBlockMemory(scip, &heurdata);
1236 SCIPheurSetData(heur, NULL);
1237
1238 return SCIP_OKAY;
1239 }
1240
1241
1242 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
1243 static
1244 SCIP_DECL_HEUREXITSOL(heurExitsolVbounds)
1245 { /*lint --e{715}*/
1246 SCIP_HEURDATA* heurdata;
1247 int v;
1248
1249 heurdata = SCIPheurGetData(heur);
1250 assert(heurdata != NULL);
1251
1252 /* release all variables */
1253 for( v = 0; v < heurdata->nvbvars; ++v )
1254 {
1255 SCIP_CALL( SCIPreleaseVar(scip, &heurdata->vbvars[v]) );
1256 }
1257
1258 /* free varbounds array */
1259 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->vbbounds, heurdata->nvbvars);
1260 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->vbvars, heurdata->nvbvars);
1261
1262 /* reset heuristic data structure */
1263 heurdataReset(heurdata);
1264
1265 return SCIP_OKAY;
1266 }
1267
1268 /** execution method of primal heuristic */
1269 static
1270 SCIP_DECL_HEUREXEC(heurExecVbounds)
1271 { /*lint --e{715}*/
1272 SCIP_HEURDATA* heurdata;
1273 SCIP_Bool skipobj1;
1274 SCIP_Bool skipobj2;
1275 #ifdef NOCONFLICT
1276 SCIP_Bool enabledconflicts;
1277 #endif
1278
1279 assert( heur != NULL );
1280 assert( scip != NULL );
1281 assert( result != NULL );
1282
1283 *result = SCIP_DIDNOTRUN;
1284
1285 if( SCIPgetNPseudoBranchCands(scip) == 0 )
1286 return SCIP_OKAY;
1287
1288 heurdata = SCIPheurGetData(heur);
1289 assert(heurdata != NULL);
1290
1291 if( !heurdata->initialized )
1292 {
1293 SCIP_CALL( initializeCandsLists(scip, heurdata) );
1294 }
1295
1296 if( !heurdata->applicable )
1297 return SCIP_OKAY;
1298
1299 #ifdef NOCONFLICT
1300 /* disable conflict analysis */
1301 SCIP_CALL( SCIPgetBoolParam(scip, "conflict/enable", &enabledconflicts) );
1302
1303 if( !SCIPisParamFixed(scip, "conflict/enable") )
1304 {
1305 SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", FALSE) );
1306 }
1307 #endif
1308
1309 /* try variable bounds */
1310 skipobj1 = FALSE;
1311 skipobj2 = FALSE;
1312 if( ((unsigned)heurdata->feasvariant & VBOUNDVARIANT_NOOBJ) != 0 )
1313 {
1314 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 0,
1315 &skipobj1, &skipobj2, result) );
1316 }
1317 if( !skipobj1 && ((unsigned) heurdata->feasvariant & VBOUNDVARIANT_BESTBOUND) != 0)
1318 {
1319 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 1, NULL, NULL, result) );
1320 }
1321 if( !skipobj2 && ((unsigned) heurdata->feasvariant & VBOUNDVARIANT_WORSTBOUND) != 0)
1322 {
1323 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 2, NULL, NULL, result) );
1324 }
1325
1326 skipobj1 = FALSE;
1327 skipobj2 = FALSE;
1328 if( ((unsigned) heurdata->tightenvariant & VBOUNDVARIANT_NOOBJ) != 0 )
1329 {
1330 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 0,
1331 &skipobj1, &skipobj2, result) );
1332 }
1333 if( !skipobj1 && ((unsigned) heurdata->tightenvariant & VBOUNDVARIANT_BESTBOUND) != 0)
1334 {
1335 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 1, NULL, NULL, result) );
1336 }
1337 if( !skipobj2 && ((unsigned) heurdata->tightenvariant & VBOUNDVARIANT_WORSTBOUND) != 0)
1338 {
1339 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 2, NULL, NULL, result) );
1340 }
1341
1342 #ifdef NOCONFLICT
1343 /* reset the conflict analysis */
1344 if( !SCIPisParamFixed(scip, "conflict/enable") )
1345 {
1346 SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", enabledconflicts) );
1347 }
1348 #endif
1349
1350 return SCIP_OKAY;
1351 }
1352
1353 /*
1354 * primal heuristic specific interface methods
1355 */
1356
1357 /** creates the vbounds primal heuristic and includes it in SCIP */
1358 SCIP_RETCODE SCIPincludeHeurVbounds(
1359 SCIP* scip /**< SCIP data structure */
1360 )
1361 {
1362 SCIP_HEURDATA* heurdata;
1363 SCIP_HEUR* heur;
1364
1365 /* create vbounds primal heuristic data */
1366 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1367 heurdataReset(heurdata);
1368
1369 /* include primal heuristic */
1370 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1371 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
1372 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecVbounds, heurdata) );
1373
1374 assert(heur != NULL);
1375
1376 /* set non-NULL pointers to callback methods */
1377 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyVbounds) );
1378 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeVbounds) );
1379 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolVbounds) );
1380
1381 /* add variable bounds primal heuristic parameters */
1382 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minintfixingrate",
1383 "minimum percentage of integer variables that have to be fixed",
1384 &heurdata->minintfixingrate, FALSE, DEFAULT_MININTFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1385
1386 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minmipfixingrate",
1387 "minimum percentage of variables that have to be fixed within sub-SCIP (integer and continuous)",
1388 &heurdata->minmipfixingrate, FALSE, DEFAULT_MINMIPFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1389
1390 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1391 "maximum number of nodes to regard in the subproblem",
1392 &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1393
1394 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1395 "number of nodes added to the contingent of the total nodes",
1396 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1397
1398 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1399 "minimum number of nodes required to start the subproblem",
1400 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1401
1402 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1403 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1404 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1405
1406 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1407 "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1408 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1409
1410 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
1411 "maximum number of propagation rounds during probing (-1 infinity)",
1412 &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX/4, NULL, NULL) );
1413
1414 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1415 "should all active cuts from cutpool be copied to constraints in subproblem?",
1416 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1417
1418 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselockfixings",
1419 "should more variables be fixed based on variable locks if the fixing rate was not reached?",
1420 &heurdata->uselockfixings, TRUE, DEFAULT_USELOCKFIXINGS, NULL, NULL) );
1421
1422 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxbacktracks",
1423 "maximum number of backtracks during the fixing process",
1424 &heurdata->maxbacktracks, TRUE, DEFAULT_MAXBACKTRACKS, -1, INT_MAX/4, NULL, NULL) );
1425
1426 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/feasvariant",
1427 "which variants of the vbounds heuristic that try to stay feasible should be called? (0: off, 1: w/o looking at obj, 2: only fix to best bound, 4: only fix to worst bound",
1428 &heurdata->feasvariant, TRUE, (int) DEFAULT_FEASVARIANT, 0, 7, NULL, NULL) );
1429
1430 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/tightenvariant",
1431 "which tightening variants of the vbounds heuristic should be called? (0: off, 1: w/o looking at obj, 2: only fix to best bound, 4: only fix to worst bound",
1432 &heurdata->tightenvariant, TRUE, (int) DEFAULT_TIGHTENVARIANT, 0, 7, NULL, NULL) );
1433
1434 return SCIP_OKAY;
1435 }
1436
1437 /**@} */
1438