Scippy

SCIP

Solving Constraint Integer Programs

heur_locks.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_locks.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief rounding locks primal heuristic
28 * @author Michael Winkler
29 * @author Gerald Gamrath
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
35#include "scip/heur_locks.h"
36#include "scip/pub_cons.h"
37#include "scip/pub_heur.h"
38#include "scip/pub_lp.h"
39#include "scip/pub_message.h"
40#include "scip/pub_misc.h"
41#include "scip/pub_var.h"
42#include "scip/scip_branch.h"
43#include "scip/scip_cons.h"
44#include "scip/scip_copy.h"
45#include "scip/scip_general.h"
46#include "scip/scip_heur.h"
47#include "scip/scip_lp.h"
48#include "scip/scip_mem.h"
49#include "scip/scip_message.h"
50#include "scip/scip_numerics.h"
51#include "scip/scip_param.h"
52#include "scip/scip_prob.h"
53#include "scip/scip_probing.h"
55#include "scip/scip_sol.h"
56#include "scip/scip_solve.h"
58#include "scip/scip_timing.h"
59#include "scip/scip_tree.h"
60#include <string.h>
61
62#define HEUR_NAME "locks"
63#define HEUR_DESC "heuristic that fixes variables based on their rounding locks"
64#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP
65#define HEUR_PRIORITY 3000
66#define HEUR_FREQ 0
67#define HEUR_FREQOFS 0
68#define HEUR_MAXDEPTH -1
69#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
70#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
71
72#define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
73#define DEFAULT_ROUNDUPPROBABILITY 0.67 /**< probability for rounding a variable up in case of ties */
74#define DEFAULT_MINFIXINGRATE 0.65 /**< minimum percentage of variables that have to be fixed */
75#define DEFAULT_MINIMPROVE 0.01 /**< factor by which locks heuristic should at least improve the
76 * incumbent */
77#define DEFAULT_MINNODES 500LL /**< minimum number of nodes to regard in the subproblem */
78#define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */
79#define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
80#define DEFAULT_MAXPROPROUNDS 2 /**< maximum number of propagation rounds during probing */
81#define DEFAULT_UPDATELOCKS TRUE /**< should the locks be updated based on LP rows? */
82#define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the
83 * original scip be copied to constraints of the subscip? */
84#define DEFAULT_USEFINALSUBMIP TRUE /**< should a final sub-MIP be solved to construct a feasible
85 * solution if the LP was not roundable? */
86#define DEFAULT_RANDSEED 73 /**< initial random seed */
87#define DEFAULT_MINFIXINGRATELP 0.0 /**< minimum fixing rate over all variables (including continuous)
88 * to solve LP */
89
90/** primal heuristic data */
91struct SCIP_HeurData
92{
93 SCIP_RANDNUMGEN* randnumgen; /**< random number generation */
94 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
95 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
96 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
97 SCIP_Longint usednodes; /**< nodes already used by locks heuristic in earlier calls */
98 SCIP_Real roundupprobability; /**< probability for rounding a variable up in case of ties */
99 SCIP_Real minfixingrate; /**< minimum percentage of variables that have to be fixed */
100 SCIP_Real minfixingratelp; /**< minimum fixing rate over all variables (including continuous) to solve LP */
101 SCIP_Real minimprove; /**< factor by which locks heuristic should at least improve the incumbent */
102 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
103 int maxproprounds; /**< maximum number of propagation rounds during probing */
104 SCIP_Bool updatelocks; /**< should the locks be updated based on LP rows? */
105 SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in
106 * the subproblem? */
107 SCIP_Bool usefinalsubmip; /**< should a final sub-MIP be solved to construct a feasible solution if
108 * the LP was not roundable? */
109};
110
111/*
112 * Local methods
113 */
114
115/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
116static
117SCIP_DECL_HEURCOPY(heurCopyLocks)
118{ /*lint --e{715}*/
119 assert(scip != NULL);
120 assert(heur != NULL);
121 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
122
123 /* call inclusion method of primal heuristic */
125
126 return SCIP_OKAY;
127}
128
129/** free method for primal heuristic plugins (called when SCIP is exiting) */
130static
131SCIP_DECL_HEURFREE(heurFreeLocks)
132{ /*lint --e{715}*/
133 SCIP_HEURDATA* heurdata;
134
135 assert(scip != NULL);
136 assert(heur != NULL);
137 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
138
139 heurdata = SCIPheurGetData(heur);
140
141 /* free primal heuristic data */
142 SCIPfreeBlockMemory(scip, &heurdata);
143
144 return SCIP_OKAY;
145}
146
147/** initialization method of primal heuristic (called after problem was transformed) */
148static
149SCIP_DECL_HEURINIT(heurInitLocks) /*lint --e{715}*/
150{ /*lint --e{715}*/
151 SCIP_HEURDATA* heurdata;
152
153 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
154 heurdata = SCIPheurGetData(heur);
155 assert(heurdata != NULL);
156
157 /* initialize data */
158 heurdata->usednodes = 0;
159
160 /* create random number generator */
161 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
163
164 return SCIP_OKAY;
165}
166
167/** deinitialization method of primal heuristic (called before transformed problem is freed) */
168static
169SCIP_DECL_HEUREXIT(heurExitLocks) /*lint --e{715}*/
170{ /*lint --e{715}*/
171 SCIP_HEURDATA* heurdata;
172
173 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
174
175 /* free heuristic data */
176 heurdata = SCIPheurGetData(heur);
177 assert(heurdata != NULL);
178
179 /* free random number generator */
180 SCIPfreeRandom(scip, &heurdata->randnumgen);
181
182 return SCIP_OKAY;
183}
184
185#define heurInitsolLocks NULL
186#define heurExitsolLocks NULL
187
188/** apply fix-and-propagate scheme based on variable locks
189 *
190 * @note probing mode of SCIP needs to be enabled before
191 */
193 SCIP* scip, /**< SCIP data structure */
194 SCIP_HEURDATA* heurdata, /**< primal heuristic data */
195 SCIP_Bool* cutoff, /**< pointer to store if a cutoff was detected */
196 SCIP_Bool* allrowsfulfilled /**< pointer to store if all rows became redundant */
197 )
198{
199 SCIP_ROW** lprows;
200 SCIP_VAR** vars;
201 SCIP_VAR** sortvars;
202 SCIP_Real* minact;
203 SCIP_Real* maxact;
204 SCIP_Bool* fulfilled;
205 SCIP_VAR* var;
206 SCIP_ROW* row;
207 SCIP_COL* col;
208 SCIP_ROW** colrows;
209 SCIP_Real* colvals;
210 int ncolrows;
211 int* ndownlocks;
212 int* nuplocks;
213 int* varpos = NULL;
214 SCIP_Real lastfixval;
215 SCIP_Real randnumber;
216 SCIP_Real roundupprobability;
217 SCIP_Bool propagate;
218 SCIP_Bool propagated;
219 SCIP_Bool haslhs;
220 SCIP_Bool hasrhs;
221 SCIP_Bool updatelocks;
222 int lastfixlocks;
223 int maxproprounds;
224 int nglbfulfilledrows;
225 int rowpos;
226 int nbinvars;
227 int nvars;
228 int nlprows;
229 int nfulfilledrows;
230 int bestpos;
231 int lastbestscore;
232 int bestscore;
233 int score;
234 int v;
235 int r;
236 int i;
237
238 assert(scip != NULL);
239 assert(cutoff != NULL);
240 assert(allrowsfulfilled != NULL);
241 assert(SCIPinProbing(scip));
242
243 if( heurdata == NULL )
244 {
246 heurdata = SCIPheurGetData(heur);
247 }
248 assert(heurdata != NULL);
249
250 *cutoff = FALSE;
251 *allrowsfulfilled = FALSE;
252
253 propagate = (heurdata->maxproprounds != 0);
254
255 if( heurdata->maxproprounds == -2 )
256 maxproprounds = 0;
257 else
258 maxproprounds = heurdata->maxproprounds;
259
260 roundupprobability = heurdata->roundupprobability;
261
262 updatelocks = heurdata->updatelocks && (SCIPgetNCheckConss(scip) == SCIPgetNLPRows(scip));
263
264 SCIPdebugMsg(scip, "%d constraints: %d logicor, updatelocks=%u\n", SCIPgetNConss(scip), SCIPconshdlrGetNCheckConss(SCIPfindConshdlr(scip, "logicor")), updatelocks);
265
266 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
267 assert(vars != NULL);
268
269 /* allocate memory */
270 SCIP_CALL( SCIPduplicateBufferArray(scip, &sortvars, vars, nbinvars) );
271 SCIP_CALL( SCIPallocBufferArray(scip, &nuplocks, nbinvars) );
272 SCIP_CALL( SCIPallocBufferArray(scip, &ndownlocks, nbinvars) );
273
274 /* get LP data */
275 SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) );
276 SCIP_CALL( SCIPallocBufferArray(scip, &minact, nlprows) );
277 SCIP_CALL( SCIPallocBufferArray(scip, &maxact, nlprows) );
278 SCIP_CALL( SCIPallocClearBufferArray(scip, &fulfilled, nlprows) );
279
280 /* @todo add objective value as second sorting criteria */
281
282 nglbfulfilledrows = 0;
283
284 /* get locks of variables */
285 for( v = 0; v < nbinvars; ++v )
286 {
287 var = sortvars[v];
289 ndownlocks[v] = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL);
290 }
291
292 /* get activities of rows */
293 for( r = 0; r < nlprows; ++r )
294 {
295 row = lprows[r];
296 assert(SCIProwGetLPPos(row) == r);
297
298 /* no trivial rows */
300
301 minact[r] = SCIPgetRowMinActivity(scip, row);
302 maxact[r] = SCIPgetRowMaxActivity(scip, row);
303 }
304
305 propagated = TRUE;
306 lastbestscore = INT_MAX;
307
308 /* fix variables */
309 for( v = 0; v < nbinvars; v++ )
310 {
311 if( SCIPisStopped(scip) )
312 break;
313
314 assert(!(*cutoff));
315
316 nfulfilledrows = 0;
317
318 while( v < nbinvars && (SCIPvarGetLbLocal(sortvars[v]) > 0.5 || SCIPvarGetUbLocal(sortvars[v]) < 0.5) )
319 {
320 ++v;
321 }
322 if( v == nbinvars )
323 break;
324
325 bestpos = v;
326 bestscore = nuplocks[v] + ndownlocks[v];
327
328 /* get best variable */
329 if( bestscore < lastbestscore )
330 {
331 for( i = v + 1; i < nbinvars; ++i )
332 {
333 var = sortvars[i];
334
335 /* variable is already fixed; move it to the front and increment v to ignore it */
336 if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
337 {
338 int locks;
339
340 sortvars[i] = sortvars[v];
341 sortvars[v] = var;
342
343 locks = nuplocks[i];
344 nuplocks[i] = nuplocks[v];
345 nuplocks[v] = locks;
346
347 locks = ndownlocks[i];
348 ndownlocks[i] = ndownlocks[v];
349 ndownlocks[v] = locks;
350
351 if( varpos != NULL )
352 {
353 varpos[SCIPvarGetProbindex(sortvars[i])] = i;
354 varpos[SCIPvarGetProbindex(sortvars[v])] = v;
355 }
356
357 if( bestpos == v )
358 bestpos = i;
359
360 ++v;
361
362 continue;
363 }
364
365 score = nuplocks[i] + ndownlocks[i];
366 assert(score <= lastbestscore);
367
368 if( score > bestscore )
369 {
370 bestscore = score;
371 bestpos = i;
372
373 if( bestscore == lastbestscore )
374 break;
375 }
376 }
377 if( v == nbinvars )
378 break;
379 }
380 lastbestscore = bestscore;
381
382 /* move best variable to the front (at position v) */
383 if( bestpos != v )
384 {
385 int locks;
386
387 var = sortvars[bestpos];
388 sortvars[bestpos] = sortvars[v];
389 sortvars[v] = var;
390
391 locks = nuplocks[bestpos];
392 nuplocks[bestpos] = nuplocks[v];
393 nuplocks[v] = locks;
394
395 locks = ndownlocks[bestpos];
396 ndownlocks[bestpos] = ndownlocks[v];
397 ndownlocks[v] = locks;
398
399 if( varpos != NULL )
400 {
401 varpos[SCIPvarGetProbindex(sortvars[bestpos])] = bestpos;
402 varpos[SCIPvarGetProbindex(sortvars[v])] = v;
403 }
404 }
405
406 var = sortvars[v];
407
408 /* all remaining variables are fixed, we can break the fix-and-propagate loop */
409 if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
410 {
411 assert(v == nbinvars);
412
413 break;
414 }
415
416 /* stop if we reached the depth limit */
418 break;
419
420 if( propagated )
421 {
423 propagated = FALSE;
424 }
425
426 /* set variables to the bound with fewer locks, if tie choose an average value */
427 if( ndownlocks[v] > nuplocks[v] )
428 lastfixval = 1.0;
429 else if( ndownlocks[v] < nuplocks[v] )
430 lastfixval = 0.0;
431 else
432 {
433 /* prefer one-fixing if objective value is not positive */
434 if( !SCIPisPositive(scip, SCIPvarGetObj(var)) )
435 lastfixval = 1.0;
436 else
437 {
438 randnumber = SCIPrandomGetReal(heurdata->randnumgen, 0.0, 1.0);
439
440 /* if a tie occurs, we randomly round the variable based on the parameter 'roundupprobability' */
441 if( randnumber < roundupprobability )
442 lastfixval = 1.0;
443 else
444 lastfixval = 0.0;
445 }
446 }
447
448 lastfixlocks = lastfixval > 0.5 ? nuplocks[v] : ndownlocks[v];
449
450 SCIP_CALL( SCIPfixVarProbing(scip, var, lastfixval) );
451
452 SCIPdebugMsg(scip, "iteration %d: fixing variable <%s> to %d with locks (%d, %d)\n", v, SCIPvarGetName(var), lastfixval > 0.5 ? 1 : 0, ndownlocks[v], nuplocks[v]);
453
454 if( propagate && lastfixlocks > 0 )
455 {
456 /* apply propagation */
457 SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, cutoff, NULL) );
458 propagated = TRUE;
459
460 if( *cutoff )
461 {
462 SCIPdebugMsg(scip, "last fixing led to infeasibility trying other bound\n");
463
464 /* fix cutoff variable in other direction */
466 *cutoff = FALSE;
467
468 if( lastfixval < 0.5 )
469 {
470 lastfixval = 1.0;
471
472 if( SCIPvarGetUbLocal(var) > 0.5 )
473 {
474 SCIP_CALL( SCIPfixVarProbing(scip, var, 1.0) );
475 }
476 /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a
477 * valid global fixing for the last fixed variable that conflicts with applying the reverse fixing
478 * after backtracking; in that case, we ran into a deadend and stop
479 */
480 else
481 *cutoff = TRUE;
482 }
483 else
484 {
485 lastfixval = 0.0;
486
487 if( SCIPvarGetLbLocal(var) < 0.5 )
488 {
489 SCIP_CALL( SCIPfixVarProbing(scip, var, 0.0) );
490 }
491 /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a
492 * valid global fixing for the last fixed variable that conflicts with applying the reverse fixing
493 * after backtracking; in that case, we ran into a deadend and stop
494 */
495 else
496 *cutoff = TRUE;
497 }
498
499 if( !(*cutoff) )
500 {
501 SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, cutoff, NULL) );
502 }
503 if( *cutoff )
504 {
505 SCIPdebugMsg(scip, "probing was infeasible\n");
506
507 break;
508 }
509 }
510 /* @todo collect propagated bounds and use them to update row activities as well */
511 }
512
513 if( updatelocks )
514 {
516 continue;
517
518 col = SCIPvarGetCol(var);
519 assert(col != NULL);
520
521 colrows = SCIPcolGetRows(col);
522 colvals = SCIPcolGetVals(col);
523 ncolrows = SCIPcolGetNNonz(col);
524
525 /* update activities */
526 for( r = 0; r < ncolrows; ++r )
527 {
528 row = colrows[r];
529 rowpos = SCIProwGetLPPos(row);
530
531 /* the row is not in the LP */
532 if( rowpos == -1 )
533 continue;
534
535 assert(lprows[rowpos] == row);
536
537 /* we disregard cuts */
538 if( SCIProwGetRank(row) > 0 )
539 continue;
540
541 /* the row is already fulfilled */
542 if( fulfilled[rowpos] )
543 continue;
544
545 haslhs = !SCIPisInfinity(scip, -SCIProwGetLhs(row));
546 hasrhs = !SCIPisInfinity(scip, SCIProwGetRhs(row));
547
548 /* no trivial rows */
549 assert(hasrhs || haslhs);
550
551 if( ((colvals[r] > 0) == (lastfixval < 0.5)) )
552 {
553 maxact[rowpos] -= REALABS(colvals[r]);
554 }
555 if( ((colvals[r] > 0) == (lastfixval > 0.5)) )
556 {
557 minact[rowpos] += REALABS(colvals[r]);
558 }
559
560 /* check if the row cannot be violated anymore */
561 if( (!haslhs || SCIPisFeasGE(scip, minact[rowpos], SCIProwGetLhs(row)))
562 && (!hasrhs || SCIPisFeasLE(scip, maxact[rowpos], SCIProwGetRhs(row))) )
563 {
564 SCIP_COL** cols;
565 SCIP_VAR* colvar;
566 SCIP_Real* vals;
567 int ncols;
568 int pos;
569 int w;
570
571 SCIPdebugMsg(scip, "Row <%s> has activity [%g, %g], lhs=%g, rhs=%g\n", SCIProwGetName(row), minact[rowpos], maxact[rowpos], SCIProwGetLhs(row), SCIProwGetRhs(row));
573
574 if( varpos == NULL )
575 {
576 SCIP_CALL( SCIPallocBufferArray(scip, &varpos, nbinvars) );
577
578 for( pos = 0; pos < nbinvars; ++pos )
579 varpos[SCIPvarGetProbindex(sortvars[pos])] = pos;
580 }
581
582 ++nfulfilledrows;
583 fulfilled[rowpos] = TRUE;
584 cols = SCIProwGetCols(row);
585 vals = SCIProwGetVals(row);
586 ncols = SCIProwGetNNonz(row);
587
588 /* we assume that all rows are locking the variables */
589 for( w = ncols - 1; w >= 0; --w )
590 {
591 colvar = SCIPcolGetVar(cols[w]);
592 if( SCIPvarGetType(colvar) == SCIP_VARTYPE_BINARY && colvar != var )
593 {
594 assert(sortvars[varpos[SCIPvarGetProbindex(colvar)]] == colvar);
595 pos = varpos[SCIPvarGetProbindex(colvar)];
596
597 if( haslhs )
598 {
599 if( vals[w] > 0.0 )
600 --(ndownlocks[pos]);
601 else
602 --(nuplocks[pos]);
603 }
604 if( hasrhs )
605 {
606 if( vals[w] > 0.0 )
607 --(nuplocks[pos]);
608 else
609 --(ndownlocks[pos]);
610 }
611 }
612 }
613
614 continue;
615 }
616 else if( SCIPisFeasLT(scip, maxact[rowpos], SCIProwGetLhs(row)) || SCIPisFeasGT(scip, minact[rowpos], SCIProwGetRhs(row)) )
617 {
618 *cutoff = TRUE;
619 break;
620 }
621 }
622
623 if( *cutoff )
624 {
625 SCIPdebugMsg(scip, "found infeasible row, stopping heur\n");
626 break;
627 }
628
629 nglbfulfilledrows += nfulfilledrows;
630 SCIPdebugMsg(scip, "last fixing led to %d fulfilled rows, now %d of %d rows are fulfilled\n", nfulfilledrows, nglbfulfilledrows, nlprows);
631
632 if( nglbfulfilledrows == nlprows )
633 {
634 *allrowsfulfilled = TRUE;
635 break;
636 }
637 }
638 } /*lint --e{850}*/
639
641 SCIPfreeBufferArray(scip, &fulfilled);
642 SCIPfreeBufferArray(scip, &maxact);
643 SCIPfreeBufferArray(scip, &minact);
644 SCIPfreeBufferArray(scip, &ndownlocks);
645 SCIPfreeBufferArray(scip, &nuplocks);
646 SCIPfreeBufferArray(scip, &sortvars);
647
648 return SCIP_OKAY;
649}
650
651
652
653
654/** execution method of primal heuristic */
655static
656SCIP_DECL_HEUREXEC(heurExecLocks)
657{ /*lint --e{715}*/
658 SCIP_HEURDATA* heurdata;
659 SCIP_VAR** vars;
661 SCIP_Real lowerbound;
662 SCIP_Bool cutoff;
663 SCIP_Bool lperror;
664 SCIP_Bool allrowsfulfilled = FALSE;
665#ifdef NOCONFLICT
666 SCIP_Bool enabledconflicts;
667#endif
668 int oldnpscands;
669 int npscands;
670
671 int nvars;
672 int i;
673
674 *result = SCIP_DIDNOTRUN;
675
676 /* only run once */
677 if( SCIPgetNRuns(scip) > 1 )
678 return SCIP_OKAY;
679
680 if( SCIPgetNBinVars(scip) == 0 )
681 return SCIP_OKAY;
682
683 /* only run if we are allowed to solve an LP at the current node in the tree */
685 return SCIP_OKAY;
686
688 {
689 SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
690
691 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
692 if( cutoff )
693 {
695 return SCIP_OKAY;
696 }
697
699
700 /* we need an LP */
701 if( SCIPgetNLPRows(scip) == 0 )
702 return SCIP_OKAY;
703 }
704
705 *result = SCIP_DIDNOTFIND;
706
707 heurdata = SCIPheurGetData(heur);
708 assert(heurdata != NULL);
709
710#ifdef NOCONFLICT
711 /* disable conflict analysis */
712 SCIP_CALL( SCIPgetBoolParam(scip, "conflict/enable", &enabledconflicts) );
713
714 if( !SCIPisParamFixed(scip, "conflict/enable") )
715 {
716 SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", FALSE) );
717 }
718#endif
719
720 lowerbound = SCIPgetLowerbound(scip);
721 oldnpscands = SCIPgetNPseudoBranchCands(scip);
722
723 /* start probing mode */
725
726#ifdef COLLECTSTATISTICS
728#endif
729
730 cutoff = FALSE;
731 lperror = FALSE;
732
733 SCIP_CALL( SCIPapplyLockFixings(scip, heurdata, &cutoff, &allrowsfulfilled) );
734
735 if( cutoff || SCIPisStopped(scip) )
736 goto TERMINATE;
737
738 /* check that we had enough fixings */
740
741 SCIPdebugMsg(scip, "npscands=%d, oldnpscands=%d, allrowsfulfilled=%u heurdata->minfixingrate=%g\n",
742 npscands, oldnpscands, allrowsfulfilled, heurdata->minfixingrate);
743
744 if( !allrowsfulfilled && npscands > oldnpscands * (1 - heurdata->minfixingrate) )
745 {
746 SCIPdebugMsg(scip, "--> too few fixings\n");
747
748 goto TERMINATE;
749 }
750 else
751 {
752 char strbuf[SCIP_MAXSTRLEN];
753 int ncols;
754
755 if( SCIPgetNContVars(scip) > 0 )
756 {
757 int nminfixings;
758 int nfixedvars = 0;
759
760 nvars = SCIPgetNVars(scip);
761 vars = SCIPgetVars(scip);
762 nminfixings = (int)(SCIPceil(scip, heurdata->minfixingratelp * nvars));
763
764 /* count fixed variables */
765 for( i = 0; i < nvars && nfixedvars < nminfixings; ++i )
766 {
767 if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) )
768 ++nfixedvars;
769 }
770
771 SCIPdebugMsg(scip, "Fixed %d of %d (%.1f %%) variables after probing -> %s\n",
772 nfixedvars, nvars, (100.0 * nfixedvars / (SCIP_Real)nvars),
773 nfixedvars >= nminfixings ? "continue and solve LP for remaining variables" : "terminate without LP");
774
775 if( nfixedvars < nminfixings )
776 goto TERMINATE;
777 }
778
779 /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
780 * which the user sees no output; more detailed probing stats only in debug mode */
781 ncols = SCIPgetNLPCols(scip);
782 if( !SCIPisLPSolBasic(scip) && ncols > 1000 )
783 {
784 int nunfixedcols = SCIPgetNUnfixedLPCols(scip);
785
786 if( nunfixedcols > 0.5 * ncols )
787 {
789 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
790 100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
791 }
792 }
793 SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n",
795
796 /* solve LP;
797 * errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
798 * hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
799 */
800 SCIPdebugMsg(scip, "starting solving locks-lp at time %g\n", SCIPgetSolvingTime(scip));
801#ifdef NDEBUG
802 {
803 SCIP_Bool retstat;
804 retstat = SCIPsolveProbingLP(scip, -1, &lperror, &cutoff);
805 if( retstat != SCIP_OKAY )
806 {
807 SCIPwarningMessage(scip, "Error while solving LP in LOCKS heuristic; LP solve terminated with code <%d>\n",
808 retstat);
809 }
810 }
811#else
812 SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, &cutoff) );
813#endif
814 SCIPdebugMsg(scip, "ending solving locks-lp at time %g\n", SCIPgetSolvingTime(scip));
815
816 lpstatus = SCIPgetLPSolstat(scip);
817
818 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
819 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
820
821 /* check if this is a feasible solution */
822 if( !lperror && lpstatus == SCIP_LPSOLSTAT_OPTIMAL )
823 {
824 SCIP_SOL* sol;
825 SCIP_Bool success;
826
827 lowerbound = SCIPgetLPObjval(scip);
828
829 /* create a copy of the current LP solution */
830 SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
832
833 SCIP_CALL( SCIProundSol(scip, sol, &success) );
834
835 if( success )
836 {
837 SCIP_Bool stored;
838
839 /* check solution for feasibility, and add it to solution store if possible.
840 * Neither integrality nor feasibility of LP rows have to be checked, because they
841 * are guaranteed by the heuristic at this stage.
842 */
843 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, FALSE, &stored) );
844
845 if( stored )
846 {
847#ifdef SCIP_MORE_DEBUG
848 SCIP_Bool feasible;
849 SCIP_CALL( SCIPcheckSol(scip, sol, TRUE, TRUE, TRUE, TRUE, TRUE, &feasible) );
850 assert(feasible);
851#endif
852
853 SCIPdebugMsg(scip, "found feasible solution:\n");
855 *result = SCIP_FOUNDSOL;
856 }
857
858 SCIP_CALL( SCIPfreeSol(scip, &sol) );
859
860 /* we found a solution, so we are done */
861 goto TERMINATE;
862 }
863
864 SCIP_CALL( SCIPfreeSol(scip, &sol) );
865 }
866 }
867
868 if( heurdata->usefinalsubmip && !cutoff && !lperror && lpstatus != SCIP_LPSOLSTAT_INFEASIBLE && lpstatus != SCIP_LPSOLSTAT_OBJLIMIT )
869 {
870 SCIP* subscip;
871 SCIP_VAR** subvars;
872 SCIP_HASHMAP* varmap;
873 SCIP_Longint nstallnodes;
874 SCIP_Bool valid;
875
876 /* calculate the maximal number of branching nodes until heuristic is aborted */
877 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
878
879 /* reward locks heuristic if it succeeded often */
880 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
881 nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
882 nstallnodes += heurdata->nodesofs;
883
884 /* determine the node limit for the current process */
885 nstallnodes -= heurdata->usednodes;
886 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
887
888 /* check whether we have enough nodes left to call subproblem solving */
889 if( nstallnodes < heurdata->minnodes )
890 {
891 SCIPdebugMsg(scip, "skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
892 goto TERMINATE;
893 }
894
895 /* check whether there is enough time and memory left */
897
898 if( !valid )
899 goto TERMINATE;
900
901 /* get all variables */
902 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
903
904 /* create subproblem */
905 SCIP_CALL( SCIPcreate(&subscip) );
906
907 /* allocate temporary memory for subscip variables */
908 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
909
910 /* create the variable mapping hash map */
911 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
912
913 SCIP_CALL( SCIPcopy(scip, subscip, varmap, NULL, "_locks", FALSE, FALSE, FALSE, TRUE, &valid) );
914
915 if( heurdata->copycuts )
916 {
917 /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
918 SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, FALSE, NULL) );
919 }
920
921 for( i = 0; i < nvars; i++ )
922 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
923
924 /* free hash map */
925 SCIPhashmapFree(&varmap);
926
927 /* do not abort subproblem on CTRL-C */
928 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
929
930#ifdef SCIP_DEBUG
931 /* for debugging, enable full output */
932 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
933 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
934#else
935 /* disable statistic timing inside sub SCIP and output to console */
936 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
937 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
938#endif
939
940 /* set limits for the subproblem */
941 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
942 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
943 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
944
945 /* forbid call of heuristics and separators solving sub-CIPs */
946 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
947
948 /* disable cutting plane separation */
950
951 /* disable expensive presolving */
953
954 /* use inference branching */
955 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
956 {
957 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
958 }
959
960 /* speed up sub-SCIP by not checking dual LP feasibility */
961 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
962
963 /* if there is already a solution, add an objective cutoff */
964 if( SCIPgetNSols(scip) > 0 )
965 {
966 SCIP_Real upperbound;
967 SCIP_Real minimprove;
968 SCIP_Real cutoffbound;
969
970 minimprove = heurdata->minimprove;
972
973 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
974
975 if( !SCIPisInfinity(scip, -1.0 * lowerbound) )
976 {
977 cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * lowerbound;
978 }
979 else
980 {
981 if( SCIPgetUpperbound ( scip ) >= 0 )
982 cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip);
983 else
984 cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip);
985 }
986 cutoffbound = MIN(upperbound, cutoffbound);
987 SCIP_CALL( SCIPsetObjlimit(subscip, cutoffbound) );
988 SCIPdebugMsg(scip, "setting objlimit for subscip to %g\n", cutoffbound);
989 }
990
991 SCIPdebugMsg(scip, "starting solving locks-submip at time %g\n", SCIPgetSolvingTime(scip));
992
993 /* solve the subproblem */
994 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
995 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
996 */
997#ifdef NDEBUG
998 {
999 SCIP_RETCODE retstat;
1000 retstat = SCIPpresolve(subscip);
1001 if( retstat != SCIP_OKAY )
1002 {
1003 SCIPwarningMessage(scip, "Error while presolving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n", retstat);
1004
1005 goto FREESCIPANDTERMINATE;
1006 }
1007 }
1008#else
1009 SCIP_CALL_ABORT( SCIPpresolve(subscip) );
1010#endif
1011
1012 SCIPdebugMsg(scip, "locks heuristic presolved subproblem at time %g : %d vars, %d cons; fixing value = %g\n", SCIPgetSolvingTime(scip), SCIPgetNVars(subscip), SCIPgetNConss(subscip), ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars));
1013
1014 /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
1015 * to ensure that not only the MIP but also the LP relaxation is easy enough
1016 */
1017 if( ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars) >= heurdata->minfixingrate )
1018 {
1019 SCIP_Bool success;
1020
1021 SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
1022
1023#ifdef NDEBUG
1024 {
1025 SCIP_RETCODE retstat;
1026 retstat = SCIPsolve(subscip);
1027 if( retstat != SCIP_OKAY )
1028 {
1029 SCIPwarningMessage(scip, "Error while solving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n",retstat);
1030
1031 goto FREESCIPANDTERMINATE;
1032 }
1033 }
1034#else
1035 SCIP_CALL_ABORT( SCIPsolve(subscip) );
1036#endif
1037 SCIPdebugMsg(scip, "ending solving locks-submip at time %g, status = %d\n", SCIPgetSolvingTime(scip), SCIPgetStatus(subscip));
1038
1039 /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible ->
1040 * try all solutions until one was accepted
1041 */
1042 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) );
1043 if( success )
1044 *result = SCIP_FOUNDSOL;
1045 }
1046
1047#ifdef SCIP_DEBUG
1048 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
1049#endif
1050
1051 heurdata->usednodes += SCIPgetNNodes(subscip);
1052#ifdef NDEBUG
1053 FREESCIPANDTERMINATE:
1054#endif
1055 /* free subproblem */
1056 SCIPfreeBufferArray(scip, &subvars);
1057 SCIP_CALL( SCIPfree(&subscip) );
1058 }
1059
1060 TERMINATE:
1061 /* exit probing mode */
1063
1064#ifdef NOCONFLICT
1065 /* reset the conflict analysis */
1066 if( !SCIPisParamFixed(scip, "conflict/enable") )
1067 {
1068 SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", enabledconflicts) );
1069 }
1070#endif
1071
1072 return SCIP_OKAY;
1073}
1074
1075
1076/*
1077 * primal heuristic specific interface methods
1078 */
1079
1080/** creates the locks primal heuristic and includes it in SCIP */
1082 SCIP* scip /**< SCIP data structure */
1083 )
1084{
1085 SCIP_HEURDATA* heurdata;
1086
1087 /* create primal heuristic data */
1088 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1089
1090 /* include primal heuristic */
1093 heurCopyLocks,
1094 heurFreeLocks, heurInitLocks, heurExitLocks,
1095 heurInitsolLocks, heurExitsolLocks, heurExecLocks,
1096 heurdata) );
1097
1098 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
1099 "maximum number of propagation rounds to be performed in each propagation call (-1: no limit, -2: parameter settings)",
1100 &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
1101
1102 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
1103 "minimum percentage of integer variables that have to be fixable",
1104 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1105
1106 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/roundupprobability",
1107 "probability for rounding a variable up in case of ties",
1108 &heurdata->roundupprobability, FALSE, DEFAULT_ROUNDUPPROBABILITY, 0.0, 1.0, NULL, NULL) );
1109
1110 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usefinalsubmip",
1111 "should a final sub-MIP be solved to costruct a feasible solution if the LP was not roundable?",
1112 &heurdata->usefinalsubmip, TRUE, DEFAULT_USEFINALSUBMIP, NULL, NULL) );
1113
1114 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1115 "maximum number of nodes to regard in the subproblem",
1116 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1117
1118 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1119 "number of nodes added to the contingent of the total nodes",
1120 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1121
1122 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1123 "minimum number of nodes required to start the subproblem",
1124 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1125
1126 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1127 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1128 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1129
1130 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1131 "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1132 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1133
1134 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1135 "should all active cuts from cutpool be copied to constraints in subproblem?",
1136 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1137
1138 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/updatelocks",
1139 "should the locks be updated based on LP rows?",
1140 &heurdata->updatelocks, TRUE, DEFAULT_UPDATELOCKS, NULL, NULL) );
1141
1142 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingratelp",
1143 "minimum fixing rate over all variables (including continuous) to solve LP",
1144 &heurdata->minfixingratelp, TRUE, DEFAULT_MINFIXINGRATELP, 0.0, 1.0, NULL, NULL) );
1145
1146 return SCIP_OKAY;
1147}
SCIP_VAR * w
Definition: circlepacking.c:67
SCIP_Real * r
Definition: circlepacking.c:59
#define NULL
Definition: def.h:266
#define SCIP_MAXSTRLEN
Definition: def.h:287
#define SCIP_Longint
Definition: def.h:157
#define SCIP_MAXTREEDEPTH
Definition: def.h:315
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:242
#define SCIP_Real
Definition: def.h:172
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL_ABORT(x)
Definition: def.h:352
#define SCIP_LONGINT_FORMAT
Definition: def.h:164
#define REALABS(x)
Definition: def.h:196
#define SCIP_LONGINT_MAX
Definition: def.h:158
#define SCIP_CALL(x)
Definition: def.h:373
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 SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2875
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:734
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:349
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:317
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:508
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2172
int SCIPgetNCheckConss(SCIP *scip)
Definition: scip_prob.c:3185
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:3043
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:3111
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3264
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3077
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 SCIPincludeHeurLocks(SCIP *scip)
Definition: heur_locks.c:1081
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:758
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17042
int SCIPcolGetNNonz(SCIP_COL *col)
Definition: lp.c:17126
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17161
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17151
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4656
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1364
SCIP_RETCODE SCIPincludeHeur(SCIP *scip, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEURCOPY((*heurcopy)), SCIP_DECL_HEURFREE((*heurfree)), SCIP_DECL_HEURINIT((*heurinit)), SCIP_DECL_HEUREXIT((*heurexit)), SCIP_DECL_HEURINITSOL((*heurinitsol)), SCIP_DECL_HEUREXITSOL((*heurexitsol)), SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:67
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1599
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1579
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:258
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
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_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:626
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 SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:198
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
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_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
SCIP_Real SCIPgetRowMinActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1939
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17213
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17238
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
SCIP_Real SCIPgetRowMaxActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1956
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17501
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17351
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:17381
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17248
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:180
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:837
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1627
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2066
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2307
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:2950
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:3247
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:878
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip_solve.c:2332
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2502
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
int SCIPgetNRuns(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPsumepsilon(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:672
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:436
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17788
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17537
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18143
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17925
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17583
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17767
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17418
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18133
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8864
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10133
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
#define DEFAULT_NODESQUOT
Definition: heur_locks.c:79
static SCIP_DECL_HEUREXEC(heurExecLocks)
Definition: heur_locks.c:656
static SCIP_DECL_HEURFREE(heurFreeLocks)
Definition: heur_locks.c:131
static SCIP_DECL_HEUREXIT(heurExitLocks)
Definition: heur_locks.c:169
#define DEFAULT_NODESOFS
Definition: heur_locks.c:78
#define DEFAULT_MINFIXINGRATELP
Definition: heur_locks.c:87
#define DEFAULT_COPYCUTS
Definition: heur_locks.c:82
#define DEFAULT_MAXNODES
Definition: heur_locks.c:72
#define DEFAULT_ROUNDUPPROBABILITY
Definition: heur_locks.c:73
#define HEUR_TIMING
Definition: heur_locks.c:69
#define DEFAULT_MINNODES
Definition: heur_locks.c:77
static SCIP_DECL_HEURINIT(heurInitLocks)
Definition: heur_locks.c:149
#define heurExitsolLocks
Definition: heur_locks.c:186
static SCIP_DECL_HEURCOPY(heurCopyLocks)
Definition: heur_locks.c:117
#define HEUR_FREQOFS
Definition: heur_locks.c:67
#define HEUR_DESC
Definition: heur_locks.c:63
#define DEFAULT_MINFIXINGRATE
Definition: heur_locks.c:74
SCIP_RETCODE SCIPapplyLockFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *cutoff, SCIP_Bool *allrowsfulfilled)
Definition: heur_locks.c:192
#define HEUR_DISPCHAR
Definition: heur_locks.c:64
#define HEUR_MAXDEPTH
Definition: heur_locks.c:68
#define HEUR_PRIORITY
Definition: heur_locks.c:65
#define DEFAULT_MINIMPROVE
Definition: heur_locks.c:75
#define HEUR_NAME
Definition: heur_locks.c:62
#define DEFAULT_UPDATELOCKS
Definition: heur_locks.c:81
#define DEFAULT_RANDSEED
Definition: heur_locks.c:86
#define DEFAULT_USEFINALSUBMIP
Definition: heur_locks.c:84
#define heurInitsolLocks
Definition: heur_locks.c:185
#define HEUR_FREQ
Definition: heur_locks.c:66
#define HEUR_USESSUBSCIP
Definition: heur_locks.c:70
#define DEFAULT_MAXPROPROUNDS
Definition: heur_locks.c:80
locks primal heuristic
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
public methods for managing constraints
public methods for primal heuristics
public methods for LP management
public methods for message output
#define SCIPdebug(x)
Definition: pub_message.h:93
public data structures and miscellaneous methods
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 random numbers
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
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:51
@ 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
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62
@ SCIP_VARSTATUS_COLUMN
Definition: type_var.h:51
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97