Scippy

SCIP

Solving Constraint Integer Programs

heur_vbounds.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_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
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"
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 */
121struct 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 */
173static
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 */
187static
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 */
416static
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) );
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 */
464static
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);
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 */
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;
530
531 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
532
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 */
552static
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;
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 */
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 }
626 lastvar = var;
627
628 /* fix the variable to its bound */
629 if( fixtolower )
630 {
631 /* we cannot fix to infinite bounds */
633 continue;
634
635 /* only open a new probing node if we will not exceed the maximal tree depth */
637 {
639 }
640
641 /* fix variable to lower bound */
643 SCIPdebugMsg(scip, "fixing %d: variable <%s> (obj=%g) to lower bound <%g> (%d pseudo cands)\n",
645 lastfixedlb = TRUE;
646 lastfixval = SCIPvarGetLbLocal(var);
647 }
648 else
649 {
650 /* we cannot fix to infinite bounds */
652 continue;
653
654 /* only open a new probing node if we will not exceed the maximal tree depth */
656 {
658 }
659
660 /* fix variable to upper bound */
662 SCIPdebugMsg(scip, "fixing %d: variable <%s> (obj=%g) to upper bound <%g> (%d pseudo cands)\n",
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
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 }
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 */
733static
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 */
805
806 /* disable expensive presolving */
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;
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",
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
885#endif
886
887 /* free subproblem */
888 SCIPfreeBufferArray(scip, &subvars);
889
890 return SCIP_OKAY;
891}
892
893/** main procedure of the vbounds heuristic */
894static
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
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 {
988 goto TERMINATE;
989 }
990
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 */
1001
1002#ifdef COLLECTSTATISTICS
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 {
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",
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 */
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
1197
1198 /* exit probing mode */
1199 if( SCIPinProbing(scip) )
1200 {
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) */
1213static
1214SCIP_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 */
1222
1223 return SCIP_OKAY;
1224}
1225
1226/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1227static
1228SCIP_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) */
1243static
1244SCIP_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 */
1269static
1270SCIP_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
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 */
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 */
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/**@} */
static long bound
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:438
internal methods for clocks and timing issues
#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_Shortbool
Definition: def.h:99
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL_ABORT(x)
Definition: def.h:353
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_LONGINT_MAX
Definition: def.h:159
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition: scip_copy.c:1448
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 SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip_copy.c:2130
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
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2127
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1422
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3042
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
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 SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
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 SCIPincludeHeurVbounds(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:758
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:242
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
SCIP_RETCODE SCIPflushLP(SCIP *scip)
Definition: scip_lp.c:148
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_lp.c:124
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition: scip_lp.c:101
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
int SCIPgetNUnfixedLPCols(SCIP *scip)
Definition: scip_lp.c:548
int SCIPgetNLPCols(SCIP *scip)
Definition: scip_lp.c:527
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:667
#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 SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7493
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
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
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_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:165
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:820
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_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2311
SCIP_RETCODE SCIPtrySol(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:2954
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
Definition: scip_sol.c:3251
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:882
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1300
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip_solve.c:2328
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip_timing.c:76
SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:178
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip_timing.c:127
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:161
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:434
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:18270
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:18292
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_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
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
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:18312
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18430
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
int SCIPgetNCliques(SCIP *scip)
Definition: scip_var.c:7575
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:18282
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18441
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:18324
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:18334
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8741
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
SCIP_RETCODE SCIPapplyLockFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *cutoff, SCIP_Bool *allrowsfulfilled)
Definition: heur_locks.c:192
locks primal heuristic
#define getOtherBoundIndex(idx)
Definition: heur_vbounds.c:165
#define DEFAULT_MININTFIXINGRATE
Definition: heur_vbounds.c:93
#define DEFAULT_NODESQUOT
Definition: heur_vbounds.c:100
#define isIndexLowerbound(idx)
Definition: heur_vbounds.c:164
static SCIP_DECL_HEURFREE(heurFreeVbounds)
#define getUbIndex(idx)
Definition: heur_vbounds.c:161
#define DEFAULT_NODESOFS
Definition: heur_vbounds.c:99
#define DEFAULT_COPYCUTS
Definition: heur_vbounds.c:103
#define DEFAULT_MAXNODES
Definition: heur_vbounds.c:92
#define HEUR_TIMING
Definition: heur_vbounds.c:89
#define DEFAULT_MINNODES
Definition: heur_vbounds.c:98
static SCIP_DECL_HEUREXITSOL(heurExitsolVbounds)
static SCIP_RETCODE applyVboundsFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nvbvars, SCIP_Bool tighten, int obj, SCIP_Bool *allobj1, SCIP_Bool *allobj2, SCIP_Bool *backtracked, SCIP_Bool *infeasible)
Definition: heur_vbounds.c:553
static SCIP_RETCODE applyVbounds(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vbvars, int nvbvars, SCIP_Bool tighten, int obj, SCIP_Bool *skipobj1, SCIP_Bool *skipobj2, SCIP_RESULT *result)
Definition: heur_vbounds.c:895
#define VBOUNDVARIANT_WORSTBOUND
Definition: heur_vbounds.c:80
#define HEUR_FREQOFS
Definition: heur_vbounds.c:87
#define HEUR_DESC
Definition: heur_vbounds.c:83
#define DEFAULT_TIGHTENVARIANT
Definition: heur_vbounds.c:113
static SCIP_RETCODE setupAndSolveSubscip(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **vars, int nvars, SCIP_Longint nstallnodes, SCIP_Real lowerbound, int *nprevars, SCIP_Bool *wasfeas, SCIP_RESULT *result)
Definition: heur_vbounds.c:734
static SCIP_RETCODE dfs(SCIP *scip, int startnode, SCIP_Shortbool *visited, int *dfsstack, int *stacknextedge, int *stacknextcliquevar, int *cliqueexit, int *dfsnodes, int *ndfsnodes)
Definition: heur_vbounds.c:188
#define getLbIndex(idx)
Definition: heur_vbounds.c:160
#define HEUR_DISPCHAR
Definition: heur_vbounds.c:84
#define HEUR_MAXDEPTH
Definition: heur_vbounds.c:88
#define HEUR_PRIORITY
Definition: heur_vbounds.c:85
#define DEFAULT_FEASVARIANT
Definition: heur_vbounds.c:110
static SCIP_RETCODE initializeCandsLists(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_vbounds.c:465
static SCIP_DECL_HEURCOPY(heurCopyVbounds)
#define DEFAULT_MINIMPROVE
Definition: heur_vbounds.c:96
#define HEUR_NAME
Definition: heur_vbounds.c:82
#define DEFAULT_MINMIPFIXINGRATE
Definition: heur_vbounds.c:94
static SCIP_RETCODE topologicalSort(SCIP *scip, int *vbvars, int *nvbvars)
Definition: heur_vbounds.c:417
#define DEFAULT_MAXBACKTRACKS
Definition: heur_vbounds.c:102
static void heurdataReset(SCIP_HEURDATA *heurdata)
Definition: heur_vbounds.c:174
#define getBoundtype(idx)
Definition: heur_vbounds.c:163
#define VBOUNDVARIANT_BESTBOUND
Definition: heur_vbounds.c:79
static SCIP_DECL_HEUREXEC(heurExecVbounds)
#define getVarIndex(idx)
Definition: heur_vbounds.c:162
#define HEUR_FREQ
Definition: heur_vbounds.c:86
#define HEUR_USESSUBSCIP
Definition: heur_vbounds.c:90
#define DEFAULT_USELOCKFIXINGS
Definition: heur_vbounds.c:105
#define DEFAULT_MAXPROPROUNDS
Definition: heur_vbounds.c:101
#define VBOUNDVARIANT_NOOBJ
Definition: heur_vbounds.c:78
LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood.
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3380
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3370
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3392
int SCIPcliqueGetIndex(SCIP_CLIQUE *clique)
Definition: implics.c:3416
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
public methods for primal heuristics
public methods for implications, variable bounds, and cliques
public methods for message output
#define SCIPstatisticMessage
Definition: pub_message.h:123
#define SCIPdebugMessage
Definition: pub_message.h:96
#define SCIPstatistic(x)
Definition: pub_message.h:120
public data structures and miscellaneous methods
public methods for branch and bound tree
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
general public methods
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
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_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:51
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
@ SCIP_LPSOLSTAT_ERROR
Definition: type_lp.h:49
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_LPSOLSTAT_INFEASIBLE
Definition: type_lp.h:44
@ SCIP_LPSOLSTAT_OBJLIMIT
Definition: type_lp.h:46
@ 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_DIDNOTRUN
Definition: type_result.h:42
@ 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_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71