Loading [MathJax]/extensions/TeX/AMSsymbols.js
Scippy

SCIP

Solving Constraint Integer Programs

heur_clique.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-2025 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_clique.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LNS heuristic using a clique partition to restrict the search neighborhood
28 * @brief clique primal heuristic
29 * @author Stefan Heinz
30 * @author Michael Winkler
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/cons_logicor.h"
47#include "scip/heur_clique.h"
48#include "scip/heur_locks.h"
49#include "scip/pub_heur.h"
50#include "scip/pub_implics.h"
51#include "scip/pub_message.h"
52#include "scip/pub_misc.h"
53#include "scip/pub_misc_sort.h"
54#include "scip/pub_var.h"
55#include "scip/scip_branch.h"
56#include "scip/scip_cons.h"
57#include "scip/scip_copy.h"
58#include "scip/scip_general.h"
59#include "scip/scip_heur.h"
60#include "scip/scip_lp.h"
61#include "scip/scip_mem.h"
62#include "scip/scip_message.h"
63#include "scip/scip_numerics.h"
64#include "scip/scip_param.h"
65#include "scip/scip_prob.h"
66#include "scip/scip_probing.h"
67#include "scip/scip_sol.h"
68#include "scip/scip_solve.h"
70#include "scip/scip_timing.h"
71#include "scip/scip_tree.h"
72#include "scip/scip_var.h"
73#include <string.h>
74
75
76#define HEUR_NAME "clique"
77#define HEUR_DESC "LNS heuristic using a clique partition to restrict the search neighborhood"
78#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP
79#define HEUR_PRIORITY 5000
80#define HEUR_FREQ 0
81#define HEUR_FREQOFS 0
82#define HEUR_MAXDEPTH -1
83#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
84#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
85
86#define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
87#define DEFAULT_MININTFIXINGRATE 0.65 /**< minimum percentage of integer variables that have to be fixed */
88#define DEFAULT_MINMIPFIXINGRATE 0.65 /**< minimum percentage of variables that have to be fixed within sub-SCIP
89 * (integer and continuous) */
90#define DEFAULT_MINIMPROVE 0.01 /**< factor by which clique heuristic should at least improve the
91 * incumbent */
92#define DEFAULT_MINNODES 500LL /**< minimum number of nodes to regard in the subproblem */
93#define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */
94#define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
95#define DEFAULT_MAXPROPROUNDS 2 /**< maximum number of propagation rounds during probing */
96#define DEFAULT_MAXBACKTRACKS 10 /**< maximum number of backtracks during the fixing process */
97#define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the
98 * original scip be copied to constraints of the subscip */
99#define DEFAULT_USELOCKFIXINGS FALSE /**< should more variables be fixed based on variable locks if
100 * the fixing rate was not reached? */
101
102
103/*
104 * Data structures
105 */
106
107/** primal heuristic data */
108struct SCIP_HeurData
109{
110 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
111 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
112 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
113 SCIP_Longint usednodes; /**< nodes already used by clique heuristic in earlier calls */
114 SCIP_Real minintfixingrate; /**< minimum percentage of integer variables that have to be fixed */
115 SCIP_Real minmipfixingrate; /**< minimum percentage of variables that have to be fixed within sub-SCIP
116 * (integer and continuous) */
117 SCIP_Real minimprove; /**< factor by which clique heuristic should at least improve the incumbent */
118 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
119 int maxproprounds; /**< maximum number of propagation rounds during probing */
120 int maxbacktracks; /**< maximum number of backtracks during the fixing process */
121 SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in
122 * subproblem?
123 */
124 SCIP_Bool uselockfixings; /**< should more variables be fixed based on variable locks if
125 * the fixing rate was not reached?
126 */
127};
128
129/*
130 * Local methods
131 */
132
133/** comparison method for sorting cliques by their size */
134static
135SCIP_DECL_SORTINDCOMP(compCliquesSize)
136{
137 int* cliquesizes = (int*)dataptr;
138
139 return cliquesizes[ind2] - cliquesizes[ind1];
140}
141
142static
144 SCIP_CLIQUE* clique
145 )
146{
147 SCIP_VAR** cliquevars;
148 SCIP_VAR* var;
149 int ncliquevars;
150 int nunfixed = 0;
151 int v;
152
153 ncliquevars = SCIPcliqueGetNVars(clique);
154 cliquevars = SCIPcliqueGetVars(clique);
155
156 for( v = 0; v < ncliquevars; ++v )
157 {
158 var = cliquevars[v];
159
160 /* is variable unfixed? */
161 if( SCIPvarGetUbLocal(var) > SCIPvarGetLbLocal(var) + 0.5 )
162 ++nunfixed;
163 }
164
165 return nunfixed;
166}
167
168/** apply clique fixing using probing */
169static
171 SCIP* scip, /**< original SCIP data structure */
172 SCIP_HEURDATA* heurdata, /**< structure containing heurdata */
173 SCIP_Bool enabledconflicts, /**< was conflict analysis enabled before the heuristic call? */
174 SCIP_VAR** onefixvars, /**< array to store all variables which are fixed to one in the cliques */
175 SCIP_Shortbool* onefixvals, /**< array to store the values of all variables fixed to one in the cliques */
176 int* nonefixvars, /**< pointer to store the number of variables fixed to one */
177 SCIP_Bool* cutoff /**< pointer to store whether the propagation stopped with infeasibility */
178 )
179{
180 SCIP_CLIQUE** cliques;
181 SCIP_CLIQUE* clique;
182 SCIP_VAR** cliquevars;
183 SCIP_VAR* var;
184 SCIP_Bool* cliquevals;
185 SCIP_Bool* propagated;
186 int* cliquesizes;
187 int* permutation;
188 SCIP_Real bestobj;
189 SCIP_Real obj;
190 SCIP_Bool alreadyone;
191 SCIP_Bool newnode;
192 int probingdepthofonefix;
193 int ncliquevars;
194 int ncliques;
195 int bestpos;
196 int firstclique;
197 int bestclique;
198 int cliquesize;
199 int bestcliquesize;
200 int nbacktracks = 0;
201 int v = 0;
202 int c;
203 int i;
204
205 assert(scip != NULL);
206 assert(heurdata != NULL);
207 assert(onefixvars != NULL);
208 assert(nonefixvars != NULL);
209 assert(cutoff != NULL);
210
211 cliques = SCIPgetCliques(scip);
212 ncliques = SCIPgetNCliques(scip);
213
214 /* allocate memory */
215 SCIP_CALL( SCIPallocBufferArray(scip, &cliquesizes, ncliques) );
216 SCIP_CALL( SCIPallocBufferArray(scip, &permutation, ncliques) );
217 SCIP_CALL( SCIPallocClearBufferArray(scip, &propagated, ncliques) );
218
219 for( c = ncliques - 1; c >= 0; --c )
220 {
221 cliquesizes[c] = SCIPcliqueGetNVars(cliques[c]);
222 }
223
224 SCIPsort(permutation, compCliquesSize, (void*)cliquesizes, ncliques);
225
226#ifndef NDEBUG
227 for( c = ncliques - 1; c >= 1; --c )
228 {
229 assert(cliquesizes[permutation[c]] <= cliquesizes[permutation[c-1]]);
230 }
231#endif
232
233 *cutoff = FALSE;
234 probingdepthofonefix = 0;
235 firstclique = 0;
236
238
239 /* @todo maybe try to fix more than one variable to one in each probing node, to gain faster results */
240 for( c = 0; c < ncliques; ++c )
241 {
242 bestpos = -1;
243 bestobj = SCIPinfinity(scip);
244 alreadyone = FALSE;
245 newnode = FALSE;
246
247 bestclique = firstclique;
248
249 if( bestclique >= ncliques )
250 break;
251
252 bestcliquesize = getCliqueUnfixedVars(cliques[permutation[bestclique]]);
253 assert(!propagated[permutation[bestclique]]);
254
255 for( i = firstclique + 1; i < ncliques; ++i)
256 {
257 if( cliquesizes[permutation[i]] < bestcliquesize )
258 break;
259
260 if( propagated[permutation[i]] )
261 continue;
262
263 cliquesize = getCliqueUnfixedVars(cliques[permutation[i]]);
264
265 if( cliquesize > bestcliquesize )
266 {
267 bestclique = i;
268 bestcliquesize = cliquesize;
269 }
270 else if( cliquesize == 0 )
271 {
272 propagated[permutation[i]] = TRUE;
273 }
274 }
275 clique = cliques[permutation[bestclique]];
276 propagated[permutation[bestclique]] = TRUE;
277
278 while( firstclique < ncliques && propagated[permutation[firstclique]] )
279 ++firstclique;
280
281 ncliquevars = SCIPcliqueGetNVars(clique);
282 cliquevars = SCIPcliqueGetVars(clique);
283 cliquevals = SCIPcliqueGetValues(clique);
284
285 for( v = 0; v < ncliquevars; ++v )
286 {
287 var = cliquevars[v];
288
289 /* variable is already fixed */
290 if( SCIPvarGetUbLocal(var) < SCIPvarGetLbLocal(var) + 0.5 )
291 {
292 SCIPdebugMsg(scip, "<%s> is already fixed to %g\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var));
293
294 /* clique variable is fixed to 1 */
295 if( cliquevals[v] == (SCIPvarGetLbLocal(var) > 0.5) )
296 {
297 assert(!alreadyone);
298 alreadyone = TRUE;
299 break;
300 }
301 continue;
302 }
303
304 obj = cliquevals[v] ? SCIPvarGetObj(var) : -SCIPvarGetObj(var);
305
306 /* @todo use a tiebreaker (locks?) */
307 if( obj < bestobj )
308 {
309 /* variable is not the best one in the clique anymore, fix it to 0 */
310 if( bestpos >= 0 )
311 {
312 assert(bestpos < ncliquevars);
313 if( cliquevals[bestpos] )
314 {
315 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 0.0) );
316 }
317 else
318 {
319 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 1.0) );
320 }
321 SCIPdebugMsg(scip, "fixed <%s> to %g\n", SCIPvarGetName(cliquevars[bestpos]), SCIPvarGetUbLocal(cliquevars[bestpos]));
322 newnode = TRUE;
323 }
324
325 bestobj = obj;
326 bestpos = v;
327 }
328 /* variable is not the best one in the clique, fix it to 0 */
329 else
330 {
331 assert(bestpos >= 0);
332
333 if( cliquevals[v] )
334 {
335 SCIP_CALL( SCIPfixVarProbing(scip, var, 0.0) );
336 }
337 else
338 {
339 SCIP_CALL( SCIPfixVarProbing(scip, var, 1.0) );
340 }
341 SCIPdebugMsg(scip, "fixed <%s> to %g\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var));
342 newnode = TRUE;
343 }
344 }
345 /* we found a variable in the clique which is already fixed to 1 */
346 if( alreadyone )
347 {
348 /* fix (so far) best candidate to 0 */
349 if( bestpos >= 0 )
350 {
351 assert(bestpos < ncliquevars);
352 if( cliquevals[bestpos] )
353 {
354 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 0.0) );
355 }
356 else
357 {
358 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 1.0) );
359 }
360 SCIPdebugMsg(scip, "fixed <%s> to %g\n", SCIPvarGetName(cliquevars[bestpos]), SCIPvarGetUbLocal(cliquevars[bestpos]));
361 newnode = TRUE;
362 }
363
364 /* fix all variables not yet processed to 0 */
365 for( ; v < ncliquevars; ++v )
366 {
367 var = cliquevars[v];
368
369 if( SCIPvarGetUbLocal(var) < SCIPvarGetLbLocal(var) + 0.5 )
370 continue;
371
372 if( cliquevals[v] )
373 {
374 SCIP_CALL( SCIPfixVarProbing(scip, var, 0.0) );
375 }
376 else
377 {
378 SCIP_CALL( SCIPfixVarProbing(scip, var, 1.0) );
379 }
380 SCIPdebugMsg(scip, "fixed <%s> to %g\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var));
381 newnode = TRUE;
382 }
383 }
384 /* fix the best variable to 1 */
385 else if( bestpos >= 0 )
386 {
387 assert(bestpos < ncliquevars);
388 onefixvars[*nonefixvars] = cliquevars[bestpos];
389 probingdepthofonefix = SCIPgetProbingDepth(scip);
390
391 /* @todo should we even fix the best candidate to 1? */
392 if( cliquevals[bestpos] )
393 {
394 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 1.0) );
395 onefixvals[*nonefixvars] = 1;
396 }
397 else
398 {
399 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 0.0) );
400 onefixvals[*nonefixvars] = 0;
401 }
402 SCIPdebugMsg(scip, "fixed <%s> to %g*\n", SCIPvarGetName(cliquevars[bestpos]), SCIPvarGetUbLocal(cliquevars[bestpos]));
403 ++(*nonefixvars);
404 newnode = TRUE;
405 }
406
407 if( newnode )
408 {
409 /* propagate fixings */
410 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, cutoff, NULL) );
411
412 SCIPdebugMsg(scip, "propagate fixings of clique %d: cutoff=%u\n", c, *cutoff);
413
414 if( SCIPisStopped(scip) )
415 break;
416
417 /* stop if we reached the depth limit */
419 break;
420
421 /* probing detected infeasibility: backtrack */
422 if( *cutoff )
423 {
424 if( *nonefixvars > 0 )
425 {
426 if( probingdepthofonefix > 0 )
427 {
428 SCIP_CALL( SCIPbacktrackProbing(scip, probingdepthofonefix - 1) );
429 probingdepthofonefix = 0;
430 ++nbacktracks;
431
432 /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a
433 * valid global fixing for the last fixed variable that conflicts with applying the reverse fixing
434 * after backtracking; in that case, we ran into a deadend and stop
435 */
436 if( SCIPvarGetLbLocal(onefixvars[*nonefixvars - 1]) < 1.5 - onefixvals[*nonefixvars - 1]
437 && SCIPvarGetUbLocal(onefixvars[*nonefixvars - 1]) > 0.5 - onefixvals[*nonefixvars - 1] )
438 {
439 /* fix the last variable, which was fixed to 1 and led to the cutoff, to 0 */
440 SCIP_CALL( SCIPfixVarProbing(scip, onefixvars[*nonefixvars - 1], 1.0 - onefixvals[*nonefixvars - 1]) );
441 --(*nonefixvars);
442
443 /* propagate fixings */
444 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, cutoff, NULL) );
445
446 SCIPdebugMsg(scip, "backtrack %d was %sfeasible\n", nbacktracks, (*cutoff ? "in" : ""));
447 }
448#ifndef NDEBUG
449 else
450 assert(*cutoff == TRUE);
451#endif
452 }
453 if( *cutoff )
454 {
455 SCIPdebugMsg(scip, "probing was infeasible after %d backtracks\n", nbacktracks);
456#ifndef NOCONFLICT
457 if( enabledconflicts )
458 {
459 SCIP_CONS* conflictcons;
460 char consname[SCIP_MAXSTRLEN];
461
462 /* create own conflict */
463 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "conf%" SCIP_LONGINT_FORMAT "", SCIPgetNNodes(scip));
464
465 /* get variables for the conflict */
466 for( i = 0; i < *nonefixvars; ++i )
467 {
468 /* if the variable was fixed to 1 by the heuristic, get its negated variable */
469 if( onefixvals[i] )
470 {
471 SCIP_CALL( SCIPgetNegatedVar(scip, onefixvars[i], &onefixvars[i]) );
472 }
473 }
474
475 /* create conflict constraint */
476 SCIP_CALL( SCIPcreateConsLogicor(scip, &conflictcons, consname, *nonefixvars, onefixvars,
479 SCIPdebugPrintCons(scip, conflictcons, NULL);
480 }
481#endif
482 break;
483 }
484 else if( nbacktracks > heurdata->maxbacktracks )
485 {
486 SCIPdebugMsg(scip, "interrupt probing after %d backtracks\n", nbacktracks);
487 break;
488 }
489 }
490 /* we had a cutoff without a single one-fixing, so the current problem seems to be infeasible already */
491 else
492 break;
493 }
494
496 }
497 }
498 assert((*nonefixvars > 0) || probingdepthofonefix == 0 );
499
500 SCIPfreeBufferArray(scip, &propagated);
501 SCIPfreeBufferArray(scip, &permutation);
502 SCIPfreeBufferArray(scip, &cliquesizes);
503
504 SCIPdebugMsg(scip, "fixed %d of %d variables in probing\n", v, SCIPgetNVars(scip) - SCIPgetNContVars(scip));
505 SCIPdebugMsg(scip, "applied %d of %d cliques in probing\n", c, ncliques);
506 SCIPdebugMsg(scip, "probing was %sfeasible\n", (*cutoff) ? "in" : "");
507
508 return SCIP_OKAY;
509}
510
511/*
512 * Callback methods of primal heuristic
513 */
514
515/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
516static
517SCIP_DECL_HEURCOPY(heurCopyClique)
518{ /*lint --e{715}*/
519 assert(scip != NULL);
520 assert(heur != NULL);
521 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
522
523 /* call inclusion method of primal heuristic */
525
526 return SCIP_OKAY;
527}
528
529/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
530static
531SCIP_DECL_HEURFREE(heurFreeClique)
532{ /*lint --e{715}*/
533 SCIP_HEURDATA* heurdata;
534
535 assert(heur != NULL);
536 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
537 assert(scip != NULL);
538
539 /* free heuristic data */
540 heurdata = SCIPheurGetData(heur);
541 assert(heurdata != NULL);
542
543 SCIPfreeBlockMemory(scip, &heurdata);
544 SCIPheurSetData(heur, NULL);
545
546 return SCIP_OKAY;
547}
548
549
550/** initialization method of primal heuristic (called after problem was transformed) */
551static
552SCIP_DECL_HEURINIT(heurInitClique)
553{ /*lint --e{715}*/
554 SCIP_HEURDATA* heurdata;
555
556 assert(heur != NULL);
557 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
558 assert(scip != NULL);
559
560 /* reset heuristic data */
561 heurdata = SCIPheurGetData(heur);
562 assert(heurdata != NULL);
563
564 heurdata->usednodes = 0;
565
566 return SCIP_OKAY;
567}
568
569/** execution method of primal heuristic */
570static
571SCIP_DECL_HEUREXEC(heurExecClique)
572{ /*lint --e{715}*/
573 SCIP_HEURDATA* heurdata;
574 SCIP_VAR** vars;
575 SCIP_Real lowerbound;
576 int nvars;
577 int nbinvars;
578 int oldnpscands;
579 int npscands;
580 int i;
581 SCIP_Bool cutoff;
582 SCIP_Bool lperror;
583
584 SCIP_VAR** onefixvars;
585 SCIP_Shortbool* onefixvals;
586 int nonefixvars;
587 SCIP_Bool enabledconflicts;
588 SCIP_LPSOLSTAT lpstatus;
589 SCIP_CONS* conflictcons;
590 SCIP_Bool solvelp;
591 char consname[SCIP_MAXSTRLEN];
592
593 SCIP_Longint nstallnodes;
594
595 assert(heur != NULL);
596 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
597 assert(scip != NULL);
598 assert(result != NULL);
599
600 *result = SCIP_DIDNOTRUN;
601
602 /* get heuristic's data */
603 heurdata = SCIPheurGetData(heur);
604 assert(heurdata != NULL);
605
606 nbinvars = SCIPgetNBinVars(scip);
607
608 if( nbinvars < 2 )
609 return SCIP_OKAY;
610
611 /* check for necessary information to apply this heuristic */
612 if( SCIPgetNCliques(scip) == 0 )
613 return SCIP_OKAY;
614
615 lowerbound = SCIPgetLowerbound(scip);
616
617 /* calculate the maximal number of branching nodes until heuristic is aborted */
618 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
619
620 /* reward clique heuristic if it succeeded often */
621 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
622 nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
623 nstallnodes += heurdata->nodesofs;
624
625 /* determine the node limit for the current process */
626 nstallnodes -= heurdata->usednodes;
627 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
628
629 /* check whether we have enough nodes left to call subproblem solving */
630 if( nstallnodes < heurdata->minnodes )
631 {
632 SCIPdebugMsg(scip, "skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
633 return SCIP_OKAY;
634 }
635
636 oldnpscands = SCIPgetNPseudoBranchCands(scip);
637 onefixvars = NULL;
638 onefixvals = NULL;
639
640 /* disable conflict analysis, because we can it better than SCIP itself, cause we have more information */
641 SCIP_CALL( SCIPgetBoolParam(scip, "conflict/enable", &enabledconflicts) );
642
643 if( !SCIPisParamFixed(scip, "conflict/enable") )
644 {
645 SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", FALSE) );
646 }
647
648 solvelp = SCIPhasCurrentNodeLP(scip);
649
650 if( !SCIPisLPConstructed(scip) && solvelp )
651 {
652 SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
653
654 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
655 if( cutoff )
656 {
658 goto TERMINATE;
659 }
660
662 }
663
664 /* get number of possible binary variables */
665 nbinvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
666 assert(nbinvars >= 2);
667
668 *result = SCIP_DIDNOTFIND;
669
670 /* start probing */
672
673#ifdef COLLECTSTATISTICS
675#endif
676
677 /* allocate memory for all variables which will be fixed to one during probing */
678 SCIP_CALL(SCIPallocBufferArray(scip, &onefixvars, nbinvars) );
679 SCIP_CALL(SCIPallocBufferArray(scip, &onefixvals, nbinvars) );
680 nonefixvars = 0;
681
682 /* apply fixings due to clique information */
683 SCIP_CALL( applyCliqueFixings(scip, heurdata, enabledconflicts, onefixvars, onefixvals, &nonefixvars, &cutoff) );
684
685 if( cutoff || SCIPisStopped(scip) )
686 goto TERMINATE;
687
688 /* check that we had enough fixings */
690
691 SCIPdebugMsg(scip, "npscands=%d, oldnpscands=%d, heurdata->minintfixingrate=%g\n", npscands, oldnpscands, heurdata->minintfixingrate);
692
693 if( npscands > oldnpscands * (1.0 - heurdata->minintfixingrate) )
694 {
695 if( heurdata->uselockfixings && npscands <= 2.0 * oldnpscands * (1.0 - heurdata->minintfixingrate) )
696 {
697 SCIP_Bool allrowsfulfilled = FALSE;
698
699 SCIP_CALL( SCIPapplyLockFixings(scip, NULL, &cutoff, &allrowsfulfilled) );
700
701 if( cutoff || SCIPisStopped(scip) )
702 {
703 SCIPdebugMsg(scip, "cutoff or timeout in locks fixing\n");
704 goto TERMINATE;
705 }
706
708
709 SCIPdebugMsg(scip, "after lockfixings: npscands=%d, oldnpscands=%d, allrowsfulfilled=%u, heurdata->minintfixingrate=%g\n",
710 npscands, oldnpscands, allrowsfulfilled, heurdata->minintfixingrate);
711
712 if( !allrowsfulfilled && npscands > oldnpscands * (1 - heurdata->minintfixingrate) )
713 {
714 SCIPdebugMsg(scip, "--> too few fixings\n");
715
716 goto TERMINATE;
717 }
718 }
719 else
720 {
721 SCIPdebugMsg(scip, "--> too few fixings\n");
722
723 goto TERMINATE;
724 }
725 }
726
727 /*************************** Probing LP Solving ***************************/
728
729 lpstatus = SCIP_LPSOLSTAT_ERROR;
730 lperror = FALSE;
731
732 /* solve lp only if the problem is still feasible */
733 if( solvelp )
734 {
735 char strbuf[SCIP_MAXSTRLEN];
736 int ncols;
737
738 /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
739 * which the user sees no output; more detailed probing stats only in debug mode */
740 ncols = SCIPgetNLPCols(scip);
741 if( !SCIPisLPSolBasic(scip) && ncols > 1000 )
742 {
743 int nunfixedcols = SCIPgetNUnfixedLPCols(scip);
744
745 if( nunfixedcols > 0.5 * ncols )
746 {
748 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
749 100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
750 }
751 }
752 SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n",
754
755 /* solve LP; errors in the LP solver should not kill the overall solving process, if the LP is just needed for a
756 * heuristic. hence in optimized mode, the return code is caught and a warning is printed, only in debug mode,
757 * SCIP will stop.
758 */
759 SCIPdebugMsg(scip, "starting solving clique-lp at time %g\n", SCIPgetSolvingTime(scip));
760#ifdef NDEBUG
761 {
762 SCIP_Bool retstat;
763 retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL);
764 if( retstat != SCIP_OKAY )
765 {
766 SCIPwarningMessage(scip, "Error while solving LP in clique heuristic; LP solve terminated with code <%d>\n",
767 retstat);
768 }
769 }
770#else
771 SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) );
772#endif
773 SCIPdebugMsg(scip, "ending solving clique-lp at time %g\n", SCIPgetSolvingTime(scip));
774
775 lpstatus = SCIPgetLPSolstat(scip);
776
777 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
778 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, lpstatus);
779 }
780
781 /* check if this is a feasible solution */
782 if( lpstatus == SCIP_LPSOLSTAT_OPTIMAL && !lperror )
783 {
784 SCIP_SOL* sol;
785 SCIP_Bool stored;
786 SCIP_Bool success;
787
788 assert(!cutoff);
789
790 lowerbound = SCIPgetLPObjval(scip);
791
792 /* create a solution from the current LP solution */
793 SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
795
796 SCIP_CALL( SCIProundSol(scip, sol, &success) );
797
798 if( success )
799 {
800 SCIPdebugMsg(scip, "clique heuristic found roundable primal solution: obj=%g\n",
801 SCIPgetSolOrigObj(scip, sol));
802
803 /* check solution for feasibility, and add it to solution store if possible.
804 * Neither integrality nor feasibility of LP rows have to be checked, because they
805 * are guaranteed by the heuristic at this stage.
806 */
807#ifdef SCIP_DEBUG
808 SCIP_CALL( SCIPtrySol(scip, sol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) );
809#else
810 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, FALSE, &stored) );
811#endif
812
813 if( stored )
814 {
815 SCIPdebugMsg(scip, "found feasible solution:\n");
817 *result = SCIP_FOUNDSOL;
818 }
819
820 SCIP_CALL( SCIPfreeSol(scip, &sol) );
821
822 /* we found a solution, so we are done */
823 goto TERMINATE;
824 }
825
826 SCIP_CALL( SCIPfreeSol(scip, &sol) );
827 }
828 /*************************** END Probing LP Solving ***************************/
829
830 /*************************** Create Conflict ***************************/
831 if( enabledconflicts && SCIPallColsInLP(scip) &&
832 (lpstatus == SCIP_LPSOLSTAT_INFEASIBLE || lpstatus == SCIP_LPSOLSTAT_OBJLIMIT) )
833 {
834#ifndef NOCONFLICT
835 /* create own conflict */
836 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "conf%" SCIP_LONGINT_FORMAT "", SCIPgetNNodes(scip));
837
838 /* get variables for the conflict */
839 for( i = 0; i < nonefixvars; ++i )
840 {
841 /* if the variable was fixed to 1 by the heuristic, get its negated variable */
842 if( onefixvals[i] )
843 {
844 SCIP_CALL( SCIPgetNegatedVar(scip, onefixvars[i], &onefixvars[i]) );
845 }
846 }
847
848 /* create conflict constraint */
849 SCIP_CALL( SCIPcreateConsLogicor(scip, &conflictcons, consname, nonefixvars, onefixvars,
852 SCIPdebugPrintCons(scip, conflictcons, NULL);
853#endif
854 goto TERMINATE;
855 }
856 /*************************** End Conflict ***************************/
857
858 /*************************** Start Subscip Solving ***************************/
859 /* no solution has been found yet and the subproblem is still feasible --> fix all other variables by subscip if
860 * necessary
861 */
862 if( !lperror )
863 {
864 SCIP* subscip;
865 SCIP_VAR** subvars;
866 SCIP_HASHMAP* varmap;
867 SCIP_Bool valid;
868
869 /* check whether there is enough time and memory left */
871
872 if( !valid )
873 goto TERMINATE;
874
875 /* get all variables */
876 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
877
878 /* create subproblem */
879 SCIP_CALL( SCIPcreate(&subscip) );
880
881 /* allocate temporary memory for subscip variables */
882 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
883
884 /* create the variable mapping hash map */
885 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
886
887 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "_clique", NULL, NULL, 0, FALSE, FALSE, FALSE,
888 TRUE, &valid) );
889
890 if( heurdata->copycuts )
891 {
892 /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
893 SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, FALSE, NULL) );
894 }
895
896 for( i = 0; i < nvars; i++ )
897 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
898
899 /* free hash map */
900 SCIPhashmapFree(&varmap);
901
902 /* do not abort subproblem on CTRL-C */
903 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
904
905#ifdef SCIP_DEBUG
906 /* for debugging, enable full output */
907 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
908 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
909#else
910 /* disable statistic timing inside sub SCIP and output to console */
911 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
912 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
913#endif
914
915 /* set limits for the subproblem */
916 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
917 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
918 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
919
920 /* speed up sub-SCIP by not checking dual LP feasibility */
921 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
922
923 /* forbid call of heuristics and separators solving sub-CIPs */
924 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
925
926 /* disable cutting plane separation */
928
929 /* disable expensive presolving */
931
932 /* use inference branching */
933 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
934 {
935 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
936 }
937
938 /* if there is already a solution, add an objective cutoff */
939 if( SCIPgetNSols(scip) > 0 )
940 {
941 SCIP_Real upperbound;
942 SCIP_Real minimprove;
943 SCIP_Real cutoffbound;
944
945 minimprove = heurdata->minimprove;
947
948 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
949
950 if( !SCIPisInfinity(scip, -1.0 * lowerbound) )
951 {
952 cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * lowerbound;
953 }
954 else
955 {
956 if( SCIPgetUpperbound ( scip ) >= 0 )
957 cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip);
958 else
959 cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip);
960 }
961 cutoffbound = MIN(upperbound, cutoffbound);
962 SCIP_CALL( SCIPsetObjlimit(subscip, cutoffbound) );
963 SCIPdebugMsg(scip, "setting objlimit for subscip to %g\n", cutoffbound);
964 }
965
966 SCIPdebugMsg(scip, "starting solving clique-submip at time %g\n", SCIPgetSolvingTime(scip));
967
968 /* solve the subproblem */
969 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
970 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
971 */
972 SCIP_CALL_ABORT( SCIPpresolve(subscip) );
973
974 SCIPdebugMsg(scip, "clique 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));
975
976 /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
977 * to ensure that not only the MIP but also the LP relaxation is easy enough
978 */
979 if( ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars) >= heurdata->minmipfixingrate )
980 {
981 SCIP_Bool success;
982
983 SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
984
985 SCIP_CALL_ABORT( SCIPsolve(subscip) );
987
988 SCIPdebugMsg(scip, "ending solving clique-submip at time %g, status = %d\n", SCIPgetSolvingTime(scip), SCIPgetStatus(subscip));
989
990 /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible ->
991 * try all solutions until one was accepted
992 */
993 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) );
994 if( success )
995 *result = SCIP_FOUNDSOL;
996
997#ifndef NOCONFLICT
998 /* if subscip was infeasible, add a conflict */
999 if( SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE )
1000 {
1001 /* create own conflict */
1002 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "conf%" SCIP_LONGINT_FORMAT "", SCIPgetNNodes(scip));
1003
1004 /* get variables for the conflict */
1005 for( i = 0; i < nonefixvars; ++i )
1006 {
1007 /* if the variable was fixed to 1 by the heuristic, get its negated variable */
1008 if( onefixvals[i] )
1009 {
1010 SCIP_CALL( SCIPgetNegatedVar(scip, onefixvars[i], &onefixvars[i]) );
1011 }
1012 }
1013
1014 /* create conflict constraint */
1015 SCIP_CALL( SCIPcreateConsLogicor(scip, &conflictcons, consname, nonefixvars, onefixvars,
1018 SCIPdebugPrintCons(scip, conflictcons, NULL);
1019 SCIP_CALL( SCIPreleaseCons(scip, &conflictcons) );
1020 }
1021#endif
1022 }
1023
1024#ifdef SCIP_DEBUG
1025 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
1026#endif
1027
1028 /* free subproblem */
1029 SCIPfreeBufferArray(scip, &subvars);
1030 SCIP_CALL( SCIPfree(&subscip) );
1031 }
1032
1033 /*************************** End Subscip Solving ***************************/
1034
1035 TERMINATE:
1036
1037 /* reset the conflict analysis */
1038 if( !SCIPisParamFixed(scip, "conflict/enable") )
1039 {
1040 SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", enabledconflicts) );
1041 }
1042
1043 /* free conflict variables */
1044 SCIPfreeBufferArrayNull(scip, &onefixvals);
1045 SCIPfreeBufferArrayNull(scip, &onefixvars);
1046
1047 /* end probing */
1048 if( SCIPinProbing(scip) )
1049 {
1051 }
1052
1053 return SCIP_OKAY;
1054}
1055
1056/*
1057 * primal heuristic specific interface methods
1058 */
1059
1060/** creates the clique primal heuristic and includes it in SCIP */
1062 SCIP* scip /**< SCIP data structure */
1063 )
1064{
1065 SCIP_HEURDATA* heurdata;
1066 SCIP_HEUR* heur;
1067
1068 /* create clique primal heuristic data */
1069 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1070
1071 /* include primal heuristic */
1074 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecClique, heurdata) );
1075
1076 assert(heur != NULL);
1077
1078 /* set non-NULL pointers to callback methods */
1079 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyClique) );
1080 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeClique) );
1081 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitClique) );
1082
1083 /* add clique primal heuristic parameters */
1084
1085 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minintfixingrate",
1086 "minimum percentage of integer variables that have to be fixable",
1087 &heurdata->minintfixingrate, FALSE, DEFAULT_MININTFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1088
1089 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minmipfixingrate",
1090 "minimum percentage of fixed variables in the sub-MIP",
1091 &heurdata->minmipfixingrate, FALSE, DEFAULT_MINMIPFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1092
1093 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1094 "maximum number of nodes to regard in the subproblem",
1095 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1096
1097 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1098 "number of nodes added to the contingent of the total nodes",
1099 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1100
1101 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1102 "minimum number of nodes required to start the subproblem",
1103 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1104
1105 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1106 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1107 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1108
1109 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1110 "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1111 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1112
1113 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
1114 "maximum number of propagation rounds during probing (-1 infinity)",
1115 &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX/4, NULL, NULL) );
1116
1117 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1118 "should all active cuts from cutpool be copied to constraints in subproblem?",
1119 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1120
1121 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselockfixings",
1122 "should more variables be fixed based on variable locks if the fixing rate was not reached?",
1123 &heurdata->uselockfixings, TRUE, DEFAULT_USELOCKFIXINGS, NULL, NULL) );
1124
1125 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxbacktracks",
1126 "maximum number of backtracks during the fixing process",
1127 &heurdata->maxbacktracks, TRUE, DEFAULT_MAXBACKTRACKS, -1, INT_MAX/4, NULL, NULL) );
1128
1129 return SCIP_OKAY;
1130}
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
#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_Shortbool
Definition: def.h:99
#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 SCIP_LONGINT_MAX
Definition: def.h:158
#define SCIP_CALL(x)
Definition: def.h:373
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
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: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
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
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
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3324
SCIP_RETCODE SCIPaddConflict(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_prob.c:3229
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 SCIPincludeHeurClique(SCIP *scip)
Definition: heur_clique.c:1061
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:304
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:765
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:167
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:122
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:183
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1599
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1579
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:199
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_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:649
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 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_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 SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:878
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1296
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)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
Definition: scip_tree.c:72
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_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18171
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17953
SCIP_CLIQUE ** SCIPgetCliques(SCIP *scip)
Definition: scip_var.c:7752
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17446
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1527
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18161
int SCIPgetNCliques(SCIP *scip)
Definition: scip_var.c:7698
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8852
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5541
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10880
#define DEFAULT_MININTFIXINGRATE
Definition: heur_clique.c:87
#define DEFAULT_NODESQUOT
Definition: heur_clique.c:94
#define DEFAULT_NODESOFS
Definition: heur_clique.c:93
#define DEFAULT_COPYCUTS
Definition: heur_clique.c:97
#define DEFAULT_MAXNODES
Definition: heur_clique.c:86
#define HEUR_TIMING
Definition: heur_clique.c:83
#define DEFAULT_MINNODES
Definition: heur_clique.c:92
static SCIP_DECL_SORTINDCOMP(compCliquesSize)
Definition: heur_clique.c:135
#define HEUR_FREQOFS
Definition: heur_clique.c:81
#define HEUR_DESC
Definition: heur_clique.c:77
static SCIP_DECL_HEURCOPY(heurCopyClique)
Definition: heur_clique.c:517
#define HEUR_DISPCHAR
Definition: heur_clique.c:78
#define HEUR_MAXDEPTH
Definition: heur_clique.c:82
#define HEUR_PRIORITY
Definition: heur_clique.c:79
static SCIP_DECL_HEURINIT(heurInitClique)
Definition: heur_clique.c:552
#define DEFAULT_MINIMPROVE
Definition: heur_clique.c:90
#define HEUR_NAME
Definition: heur_clique.c:76
#define DEFAULT_MINMIPFIXINGRATE
Definition: heur_clique.c:88
#define DEFAULT_MAXBACKTRACKS
Definition: heur_clique.c:96
static SCIP_RETCODE applyCliqueFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool enabledconflicts, SCIP_VAR **onefixvars, SCIP_Shortbool *onefixvals, int *nonefixvars, SCIP_Bool *cutoff)
Definition: heur_clique.c:170
static SCIP_DECL_HEUREXEC(heurExecClique)
Definition: heur_clique.c:571
static int getCliqueUnfixedVars(SCIP_CLIQUE *clique)
Definition: heur_clique.c:143
#define HEUR_FREQ
Definition: heur_clique.c:80
#define HEUR_USESSUBSCIP
Definition: heur_clique.c:84
#define DEFAULT_USELOCKFIXINGS
Definition: heur_clique.c:99
#define DEFAULT_MAXPROPROUNDS
Definition: heur_clique.c:95
static SCIP_DECL_HEURFREE(heurFreeClique)
Definition: heur_clique.c:531
LNS heuristic using a clique partition to restrict the search neighborhood.
SCIP_RETCODE SCIPapplyLockFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *cutoff, SCIP_Bool *allrowsfulfilled)
Definition: heur_locks.c:192
locks primal heuristic
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
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 SCIPdebug(x)
Definition: pub_message.h:93
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:102
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
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
@ SCIP_CONFTYPE_PROPAGATION
Definition: type_conflict.h:60
@ SCIP_CONFTYPE_INFEASLP
Definition: type_conflict.h:61
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_STATUS_INFEASIBLE
Definition: type_stat.h:62