Scippy

SCIP

Solving Constraint Integer Programs

sepa_rapidlearning.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 sepa_rapidlearning.c
26 * @ingroup DEFPLUGINS_SEPA
27 * @brief rapidlearning separator
28 * @author Timo Berthold
29 * @author Jakob Witzig
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
34#include <assert.h>
35#ifndef NDEBUG
36#include <string.h>
37#endif
38
40#include "scip/scipdefplugins.h"
41#include "scip/heuristics.h"
42#include "scip/pub_var.h"
43
44#define SEPA_NAME "rapidlearning"
45#define SEPA_DESC "rapid learning heuristic and separator"
46#define SEPA_PRIORITY -1200000
47#define SEPA_FREQ 5
48#define SEPA_MAXBOUNDDIST 1.0
49#define SEPA_USESSUBSCIP TRUE /**< does the separator use a secondary SCIP instance? */
50#define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
51
52#define DEFAULT_APPLYCONFLICTS TRUE /**< should the found conflicts be applied in the original SCIP? */
53#define DEFAULT_APPLYBDCHGS TRUE /**< should the found global bound deductions be applied in the original SCIP?
54 * apply only if conflicts and incumbent solution will be copied too
55 */
56#define DEFAULT_APPLYINFERVALS TRUE /**< should the inference values be used as initialization in the original SCIP? */
57#define DEFAULT_REDUCEDINFER FALSE /**< should the inference values only be used when rapid learning found other reductions? */
58#define DEFAULT_APPLYPRIMALSOL TRUE /**< should the incumbent solution be copied to the original SCIP? */
59#define DEFAULT_APPLYSOLVED TRUE /**< should a solved status be copied to the original SCIP? */
60
61#define DEFAULT_CHECKEXEC TRUE /**< check whether rapid learning should be executed */
62#define DEFAULT_CHECKDEGANERACY TRUE /**< should local LP degeneracy be checked? */
63#define DEFAULT_CHECKDUALBOUND FALSE /**< should the progress on the dual bound be checked? */
64#define DEFAULT_CHECKLEAVES FALSE /**< should the ratio of leaves proven to be infeasible and exceeding the
65 * cutoff bound be checked? */
66#define DEFAULT_CHECKOBJ FALSE /**< should the local objection function be checked? */
67#define DEFAULT_CHECKNSOLS TRUE /**< should the number of solutions found so far be checked? */
68#define DEFAULT_MINDEGENERACY 0.7 /**< minimal degeneracy threshold to allow local rapid learning */
69#define DEFAULT_MININFLPRATIO 10.0 /**< minimal threshold of inf/obj leaves to allow local rapid learning */
70#define DEFAULT_MINVARCONSRATIO 2.0 /**< minimal ratio of unfixed variables in relation to basis size to
71 * allow local rapid learning */
72#define DEFAULT_NWAITINGNODES 100L /**< number of nodes that should be processed before rapid learning is
73 * executed locally based on the progress of the dualbound */
74
75#define DEFAULT_MAXNVARS 10000 /**< maximum problem size (variables) for which rapid learning will be called */
76#define DEFAULT_MAXNCONSS 10000 /**< maximum problem size (constraints) for which rapid learning will be called */
77#define DEFAULT_MAXCALLS 100 /**< maximum number of overall calls */
78
79#define DEFAULT_MINNODES 500 /**< minimum number of nodes considered in rapid learning run */
80#define DEFAULT_MAXNODES 5000 /**< maximum number of nodes considered in rapid learning run */
81
82#define DEFAULT_CONTVARS FALSE /**< should rapid learning be applied when there are continuous variables? */
83#define DEFAULT_CONTVARSQUOT 0.3 /**< maximal portion of continuous variables to apply rapid learning */
84#define DEFAULT_LPITERQUOT 0.2 /**< maximal fraction of LP iterations compared to node LP iterations */
85#define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the
86 * original scip be copied to constraints of the subscip */
87
88
89/*
90 * Data structures
91 */
92
93/** separator data */
94struct SCIP_SepaData
95{
96 SCIP_Real lpiterquot; /**< maximal fraction of LP iterations compared to node LP iterations */
97 SCIP_Real mindegeneracy; /**< minimal degeneracy threshold to allow local rapid learning */
98 SCIP_Real mininflpratio; /**< minimal threshold of inf/obj leaves to allow local rapid learning */
99 SCIP_Real minvarconsratio; /**< minimal ratio of unfixed variables in relation to basis size to
100 * allow local rapid learning */
101 int maxnvars; /**< maximum problem size (variables) for which rapid learning will be called */
102 int maxnconss; /**< maximum problem size (constraints) for which rapid learning will be called */
103 int maxcalls; /**< maximum number of overall calls */
104 int minnodes; /**< minimum number of nodes considered in rapid learning run */
105 int maxnodes; /**< maximum number of nodes considered in rapid learning run */
106 SCIP_Longint nwaitingnodes; /**< number of nodes that should be processed before rapid learning is executed locally
107 * based on the progress of the dualbound */
108 SCIP_Bool applybdchgs; /**< should the found global bound deductions be applied in the original SCIP? */
109 SCIP_Bool applyconflicts; /**< should the found conflicts be applied in the original SCIP? */
110 SCIP_Bool applyinfervals; /**< should the inference values be used as initialization in the original SCIP? */
111 SCIP_Bool applyprimalsol; /**< should the incumbent solution be copied to the original SCIP? */
112 SCIP_Bool applysolved; /**< should a solved status ba copied to the original SCIP? */
113 SCIP_Bool checkdegeneracy; /**< should local LP degeneracy be checked? */
114 SCIP_Bool checkdualbound; /**< should the progress on the dual bound be checked? */
115 SCIP_Bool checkleaves; /**< should the ratio of leaves proven to be infeasible and exceeding the
116 * cutoff bound be checked? */
117 SCIP_Bool checkexec; /**< check whether rapid learning should be executed */
118 SCIP_Bool checkobj; /**< should the (local) objective function be checked? */
119 SCIP_Bool checknsols; /**< should number if solutions found so far be checked? */
120 SCIP_Bool contvars; /**< should rapid learning be applied when there are continuous variables? */
121 SCIP_Real contvarsquot; /**< maximal portion of continuous variables to apply rapid learning */
122 SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in
123 * subproblem? */
124 SCIP_Bool reducedinfer; /**< should the inference values only be used when rapid learning found other reductions? */
125};
126
127/*
128 * Callback methods of separator
129 */
130
131/** copy method for separator plugins (called when SCIP copies plugins) */
132static
133SCIP_DECL_SEPACOPY(sepaCopyRapidlearning)
134{ /*lint --e{715}*/
135 assert(scip != NULL);
136 assert(sepa != NULL);
137 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
138
139 /* call inclusion method of constraint handler */
141
142 return SCIP_OKAY;
143}
144
145/** destructor of separator to free user data (called when SCIP is exiting) */
146static
147SCIP_DECL_SEPAFREE(sepaFreeRapidlearning)
148{ /*lint --e{715}*/
149 SCIP_SEPADATA* sepadata;
150
151 assert(sepa != NULL);
152 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
153 assert(scip != NULL);
154
155 /* free separator data */
156 sepadata = SCIPsepaGetData(sepa);
157 assert(sepadata != NULL);
158 SCIPfreeBlockMemory(scip, &sepadata);
159 SCIPsepaSetData(sepa, NULL);
160
161 return SCIP_OKAY;
162}
163
164
165/** setup and solve sub-SCIP */
166static
168 SCIP* scip, /**< SCIP data structure */
169 SCIP* subscip, /**< subSCIP data structure */
170 SCIP_SEPADATA* sepadata, /**< separator data */
171 int randseed, /**< global seed shift used in the sub-SCIP */
172 SCIP_Bool global, /**< should rapid learning run on the global problem? */
173 SCIP_RESULT* result /**< result pointer */
174 )
175{
176 SCIP_VAR** vars; /* original problem's variables */
177 SCIP_VAR** subvars; /* subproblem's variables */
178 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
179 SCIP_HASHMAP* varmapbw = NULL; /* mapping of sub-SCIP variables to SCIP variables */
180
181 SCIP_CONSHDLR** conshdlrs = NULL; /* array of constraint handler's that might that might obtain conflicts */
182 int* oldnconss = NULL; /* number of constraints without rapid learning conflicts */
183
184 SCIP_Longint nodelimit; /* node limit for the subproblem */
185
186 int nconshdlrs; /* size of conshdlr and oldnconss array */
187 int nvars; /* number of variables */
188 int nbinvars;
189 int nintvars;
190 int nimplvars;
191 int implstart;
192 int implend;
193 int restartnum; /* maximal number of conflicts that should be created */
194 int i; /* counter */
195
196 SCIP_Bool success; /* was problem creation / copying constraint successful? */
197
198 SCIP_Bool cutoff; /* detected infeasibility */
199 int nconflicts; /* statistic: number of conflicts applied */
200 int nbdchgs; /* statistic: number of bound changes applied */
201
202 SCIP_Bool soladded = FALSE; /* statistic: was a new incumbent found? */
203 SCIP_Bool dualboundchg; /* statistic: was a new dual bound found? */
204 SCIP_Bool disabledualreductions; /* TRUE, if dual reductions in sub-SCIP are not valid for original SCIP,
205 * e.g., because a constraint could not be copied or a primal solution
206 * could not be copied back */
207 int initseed;
208 int seedshift;
209 SCIP_Bool valid;
210
211#ifdef SCIP_DEBUG
212 int n1startinfers = 0; /* statistic: number of one side infer values */
213 int n2startinfers = 0; /* statistic: number of both side infer values */
214#endif
215
216 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, &nimplvars, NULL) );
217
218 /* initializing the subproblem */
219 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
220 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
221 valid = FALSE;
222
223 /* copy the subproblem */
224 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmapfw, NULL, "rapid", NULL, NULL, 0, global, FALSE, FALSE, TRUE, &valid) );
225
226 if( sepadata->copycuts )
227 {
228 /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
229 SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, global, NULL) );
230 }
231
232 /* fill subvars array in the order of the variables of the main SCIP */
233 for( i = 0; i < nvars; i++ )
234 {
235 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
236 }
237 SCIPhashmapFree(&varmapfw);
238
239 /* change implicit integer variables to integer type */
240 implstart = nbinvars + nintvars;
241 implend = nbinvars + nintvars + nimplvars;
242 for( i = implstart; i < implend; i++ )
243 {
244 SCIP_Bool infeasible;
245
246 if( subvars[i] == NULL )
247 continue;
248
249 assert(SCIPvarGetType(subvars[i]) == SCIP_VARTYPE_IMPLINT);
250 SCIP_CALL( SCIPchgVarType(subscip, subvars[i], SCIP_VARTYPE_INTEGER, &infeasible) );
251 assert(!infeasible);
252 }
253
254 /* This avoids dual presolving.
255 *
256 * If the copy is not valid, it should be a relaxation of the problem (constraints might have failed to be copied,
257 * but no variables should be missing because we stop earlier anyway if pricers are present).
258 * By disabling dual presolving, conflicts and bound changes found in a relaxation are still valid for the original problem.
259 */
260 if( ! valid )
261 {
262 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/allowweakdualreds", FALSE) );
263 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/allowstrongdualreds", FALSE) );
264 }
265
266 SCIPdebugMsg(scip, "Copying SCIP was%s valid.\n", valid ? "" : " not");
267
268 /* mimic an FD solver: DFS, no LP solving, 1-FUIP instead of all-FUIP, ... */
269 if( SCIPisParamFixed(subscip, "lp/solvefreq") )
270 {
271 SCIPwarningMessage(scip, "unfixing parameter lp/solvefreq in subscip of rapidlearning\n");
272 SCIP_CALL( SCIPunfixParam(subscip, "lp/solvefreq") );
273 }
274 if( SCIPisParamFixed(subscip, "nodeselection/dfs/stdpriority") )
275 {
276 SCIPwarningMessage(scip, "unfixing parameter nodeselection/dfs/stdpriority in subscip of rapidlearning\n");
277 SCIP_CALL( SCIPunfixParam(subscip, "nodeselection/dfs/stdpriority") );
278 }
280
281 /* turn off pseudo objective propagation */
282 if( !SCIPisParamFixed(subscip, "propagating/pseudoobj/freq") )
283 {
284 SCIP_CALL( SCIPsetIntParam(subscip, "propagating/pseudoobj/freq", -1) );
285 }
286
287 /* use classic inference branching */
288 if( !SCIPisParamFixed(subscip, "branching/inference/useweightedsum") )
289 {
290 SCIP_CALL( SCIPsetBoolParam(subscip, "branching/inference/useweightedsum", FALSE) );
291 }
292
293 /* only create short conflicts */
294 if( !SCIPisParamFixed(subscip, "conflict/maxvarsfac") )
295 {
296 SCIP_CALL( SCIPsetRealParam(subscip, "conflict/maxvarsfac", 0.05) );
297 }
298
299 /* set node limit for the subproblem based on the number of LP iterations per node,
300 * which are a determistic measure for the node processing time.
301 *
302 * Note: We scale by number of LPs + 1 because the counter is increased after solving the LP.
303 */
304 nodelimit = SCIPgetNLPIterations(scip) / (SCIPgetNLPs(scip) + 1);
305 nodelimit = MAX(sepadata->minnodes, nodelimit);
306 nodelimit = MIN(sepadata->maxnodes, nodelimit);
307
308 /* change global random seed */
309 assert(randseed >= 0);
310 SCIP_CALL( SCIPgetIntParam(scip, "randomization/randomseedshift", &seedshift) );
311
312 initseed = ((randseed + seedshift) % INT_MAX);
313 SCIP_CALL( SCIPsetIntParam(subscip, "randomization/randomseedshift", initseed) );
314
315 restartnum = 1000;
316
317 #ifdef SCIP_DEBUG
318 /* for debugging, enable full output */
319 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
320 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", -1) );
321 #else
322 /* disable statistic timing inside sub SCIP and output to console */
323 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
324 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
325 #endif
326
327 /* set limits for the subproblem */
328 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
329 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit/5) );
330 SCIP_CALL( SCIPsetIntParam(subscip, "limits/restarts", 0) );
331 SCIP_CALL( SCIPsetIntParam(subscip, "conflict/restartnum", restartnum) );
332
333 /* forbid recursive call of heuristics and separators solving subMIPs */
334 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
335
336 /* disable cutting plane separation */
338
339 /* disable expensive presolving */
341
342 /* do not abort subproblem on CTRL-C */
343 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
344
345 /* add an objective cutoff */
347
348 /* create the variable mapping hash map */
349 SCIP_CALL( SCIPhashmapCreate(&varmapbw, SCIPblkmem(scip), nvars) );
350
351 /* store reversing mapping of variables */
352 SCIP_CALL( SCIPtransformProb(subscip) );
353 for( i = 0; i < nvars; ++i)
354 {
355 if( subvars[i] != NULL )
356 {
357 SCIP_CALL( SCIPhashmapInsert(varmapbw, SCIPvarGetTransVar(subvars[i]), vars[i]) );
358 }
359 }
360
361 /* allocate memory for constraints storage. Each constraint that will be created from now on will be a conflict.
362 * Therefore, we need to remember oldnconss to get the conflicts from the FD search.
363 */
364 nconshdlrs = 4;
365 SCIP_CALL( SCIPallocBufferArray(scip, &conshdlrs, nconshdlrs) );
366 SCIP_CALL( SCIPallocBufferArray(scip, &oldnconss, nconshdlrs) );
367
368 /* store number of constraints before rapid learning search */
369 conshdlrs[0] = SCIPfindConshdlr(subscip, "setppc");
370 conshdlrs[1] = SCIPfindConshdlr(subscip, "logicor");
371 conshdlrs[2] = SCIPfindConshdlr(subscip, "linear");
372 conshdlrs[3] = SCIPfindConshdlr(subscip, "bounddisjunction");
373
374 /* redundant constraints might be eliminated in presolving */
375 SCIP_CALL( SCIPpresolve(subscip) );
376
377 for( i = 0; i < nconshdlrs; ++i)
378 {
379 if( conshdlrs[i] != NULL )
380 oldnconss[i] = SCIPconshdlrGetNConss(conshdlrs[i]);
381 }
382
383 /* solve the subproblem, abort after errors in debug mode */
384 SCIP_CALL_ABORT( SCIPsolve(subscip) );
385
386 /* if problem was already solved do not increase limits to run again */
387 if( SCIPgetStage(subscip) == SCIP_STAGE_SOLVED )
388 {
389 SCIPdebugMsg(scip, "Subscip was completely solved, status %d.\n", SCIPgetStatus(subscip));
390 }
391 /* abort solving, if limit of applied conflicts is reached */
392 else if( SCIPgetNConflictConssApplied(subscip) >= restartnum )
393 {
394 SCIPdebugMsg(scip, "finish after %" SCIP_LONGINT_FORMAT " successful conflict calls.\n", SCIPgetNConflictConssApplied(subscip));
395 }
396 /* if the first 20% of the solution process were successful, proceed */
397 else if( (sepadata->applyprimalsol && SCIPgetNSols(subscip) > 0 && SCIPisFeasLT(scip, SCIPgetUpperbound(subscip), SCIPgetUpperbound(scip) ) )
398 || (sepadata->applybdchgs && SCIPgetNRootboundChgs(subscip) > 0 )
399 || (sepadata->applyconflicts && SCIPgetNConflictConssApplied(subscip) > 0) )
400 {
401 SCIPdebugMsg(scip, "proceed solving after the first 20%% of the solution process, since:\n");
402
403 if( SCIPgetNSols(subscip) > 0 && SCIPisFeasLE(scip, SCIPgetUpperbound(subscip), SCIPgetUpperbound(scip) ) )
404 {
405 SCIPdebugMsg(scip, " - there was a better solution (%f < %f)\n",SCIPgetUpperbound(subscip), SCIPgetUpperbound(scip));
406 }
407 if( SCIPgetNRootboundChgs(subscip) > 0 )
408 {
409 SCIPdebugMsg(scip, " - there were %d changed variables bounds\n", SCIPgetNRootboundChgs(subscip) );
410 }
411 if( SCIPgetNConflictConssFound(subscip) > 0 )
412 {
413 SCIPdebugMsg(scip, " - there were %" SCIP_LONGINT_FORMAT " conflict constraints created\n", SCIPgetNConflictConssApplied(subscip));
414 }
415
416 /* set node limit to 100% */
417 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
418
419 /* solve the subproblem, abort after errors in debug mode */
420 SCIP_CALL_ABORT( SCIPsolve(subscip) );
421 }
422 else
423 {
424 SCIPdebugMsg(scip, "do not proceed solving after the first 20%% of the solution process.\n");
425 }
426
427 #ifdef SCIP_DEBUG
429 #endif
430
432 disabledualreductions = FALSE;
433 else
434 disabledualreductions = TRUE;
435
436 /* check, whether a solution was found */
437 if( sepadata->applyprimalsol && SCIPgetNSols(subscip) > 0 )
438 {
439 SCIP_SOL** subsols;
440 int nsubsols;
441
442 /* check, whether a solution was found;
443 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until was declared to be feasible
444 */
445 nsubsols = SCIPgetNSols(subscip);
446 subsols = SCIPgetSols(subscip);
447 soladded = FALSE;
448
449 /* try adding solution from subSCIP to SCIP, until finding one that is accepted */
450 for( i = 0; i < nsubsols && !soladded; ++i )
451 {
452 SCIP_SOL* newsol;
453
454 SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], NULL, subvars, &newsol) );
455 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &soladded) );
456 }
457 if( !soladded || !SCIPisEQ(scip, SCIPgetSolOrigObj(subscip, subsols[i-1]), SCIPgetSolOrigObj(subscip, subsols[0])) )
458 disabledualreductions = TRUE;
459 }
460
461 /* if the sub problem was solved completely, we update the dual bound */
462 dualboundchg = FALSE;
463 if( sepadata->applysolved && !disabledualreductions
465 {
466 /* we need to multiply the dualbound with the scaling factor and add the offset,
467 * because this information has been disregarded in the sub-SCIP
468 */
469 SCIPdebugMsg(scip, "Update old dualbound %g to new dualbound %g.\n",
471
473 dualboundchg = TRUE;
474 }
475
476 /* check, whether conflicts were created */
477 nconflicts = 0;
478 if( sepadata->applyconflicts && !disabledualreductions && SCIPgetNConflictConssApplied(subscip) > 0 )
479 {
480 SCIP_HASHMAP* consmap;
481 int hashtablesize;
482 int nmaxconfs;
483
484 assert(SCIPgetNConflictConssApplied(subscip) < (SCIP_Longint) INT_MAX);
485 hashtablesize = (int) SCIPgetNConflictConssApplied(subscip);
486 assert(hashtablesize < INT_MAX/5);
487
488 /* create the variable mapping hash map */
489 SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), hashtablesize) );
490
491 SCIP_CALL( SCIPgetIntParam(scip, "conflict/maxconss", &nmaxconfs) );
492 if( global )
493 nmaxconfs *= 20;
494
495 /* loop over all constraint handlers that might contain conflict constraints
496 * @todo select promising constraints and not greedy
497 */
498 for( i = 0; i < nconshdlrs && nconflicts < nmaxconfs; ++i)
499 {
500 /* copy constraints that have been created in FD run */
501 if( conshdlrs[i] != NULL && SCIPconshdlrGetNConss(conshdlrs[i]) > oldnconss[i] )
502 {
503 SCIP_CONS** conss;
504 int c;
505 int nconss;
506
507 nconss = SCIPconshdlrGetNConss(conshdlrs[i]);
508 conss = SCIPconshdlrGetConss(conshdlrs[i]);
509
510 /* loop over all constraints that have been added in sub-SCIP run, these are the conflicts */
511 for( c = oldnconss[i]; c < nconss && nconflicts < nmaxconfs; ++c)
512 {
513 SCIP_CONS* cons;
514 SCIP_CONS* conscopy;
515
516 cons = conss[c];
517 assert(cons != NULL);
518
519 success = FALSE;
520
521 /* @todo assert that flags are as they should be for conflicts */
522 SCIP_CALL( SCIPgetConsCopy(subscip, scip, cons, &conscopy, conshdlrs[i], varmapbw, consmap, NULL,
524 SCIPconsIsPropagated(cons), !global, FALSE, SCIPconsIsDynamic(cons),
525 SCIPconsIsRemovable(cons), FALSE, TRUE, &success) );
526
527 if( success )
528 {
529 nconflicts++;
530
533 }
534 else
535 {
536 SCIPdebugMsg(scip, "failed to copy conflict constraint %s back to original SCIP\n", SCIPconsGetName(cons));
537 }
538 }
539 }
540 }
541 SCIPhashmapFree(&consmap);
542 }
543
544 /* check, whether tighter (global) bounds were detected */
545 cutoff = FALSE;
546 nbdchgs = 0;
547 if( sepadata->applybdchgs && !disabledualreductions )
548 {
549 for( i = 0; i < nvars; ++i )
550 {
551 SCIP_Bool tightened;
552
553 if( subvars[i] == NULL )
554 continue;
555
556 assert(SCIPisLE(scip, SCIPvarGetLbGlobal(vars[i]), SCIPvarGetLbGlobal(subvars[i])));
557 assert(SCIPisLE(scip, SCIPvarGetLbGlobal(subvars[i]), SCIPvarGetUbGlobal(subvars[i])));
558 assert(SCIPisLE(scip, SCIPvarGetUbGlobal(subvars[i]), SCIPvarGetUbGlobal(vars[i])));
559
560 /* update the bounds of the original SCIP, if a better bound was proven in the sub-SCIP */
561 if( global )
562 {
563#ifndef NDEBUG
565#else
567 return SCIP_INVALIDCALL;
568#endif
569 tightened = FALSE;
570
571 SCIP_CALL( SCIPtightenVarUbGlobal(scip, vars[i], SCIPvarGetUbGlobal(subvars[i]), FALSE, &cutoff, &tightened) );
572
573 if( cutoff )
574 break;
575
576 if( tightened )
577 nbdchgs++;
578
579 tightened = FALSE;
580
581 SCIP_CALL( SCIPtightenVarLbGlobal(scip, vars[i], SCIPvarGetLbGlobal(subvars[i]), FALSE, &cutoff, &tightened) );
582
583 if( cutoff )
584 break;
585
586 if( tightened )
587 nbdchgs++;
588 }
589 else
590 {
591 tightened = FALSE;
592
593 SCIP_CALL( SCIPtightenVarUb(scip, vars[i], SCIPvarGetUbGlobal(subvars[i]), FALSE, &cutoff, &tightened) );
594
595 if( cutoff )
596 break;
597
598 if( tightened )
599 nbdchgs++;
600
601 tightened = FALSE;
602
603 SCIP_CALL( SCIPtightenVarLb(scip, vars[i], SCIPvarGetLbGlobal(subvars[i]), FALSE, &cutoff, &tightened) );
604
605 if( cutoff )
606 break;
607
608 if( tightened )
609 nbdchgs++;
610 }
611 }
612 }
613
614 /* install start values for inference branching */
615 /* @todo use different nbranching counters for pseudo cost and inference values and update inference values in the tree */
616 if( sepadata->applyinfervals && global && (!sepadata->reducedinfer || soladded || nbdchgs + nconflicts > 0) )
617 {
618 for( i = 0; i < nvars; ++i )
619 {
620 SCIP_Real downinfer;
621 SCIP_Real upinfer;
622 SCIP_Real downvsids;
623 SCIP_Real upvsids;
624 SCIP_Real downconflen;
625 SCIP_Real upconflen;
626
627 if( subvars[i] == NULL )
628 continue;
629
630 /* copy downwards branching statistics */
631 downvsids = SCIPgetVarVSIDS(subscip, subvars[i], SCIP_BRANCHDIR_DOWNWARDS);
632 downconflen = SCIPgetVarAvgConflictlength(subscip, subvars[i], SCIP_BRANCHDIR_DOWNWARDS);
633 downinfer = SCIPgetVarAvgInferences(subscip, subvars[i], SCIP_BRANCHDIR_DOWNWARDS);
634
635 /* copy upwards branching statistics */
636 upvsids = SCIPgetVarVSIDS(subscip, subvars[i], SCIP_BRANCHDIR_UPWARDS);
637 upconflen = SCIPgetVarAvgConflictlength(subscip, subvars[i], SCIP_BRANCHDIR_UPWARDS);
638 upinfer = SCIPgetVarAvgInferences(subscip, subvars[i], SCIP_BRANCHDIR_UPWARDS);
639
640#ifdef SCIP_DEBUG
641 /* memorize statistics */
642 if( downinfer+downconflen+downvsids > 0.0 || upinfer+upconflen+upvsids != 0 )
643 n1startinfers++;
644
645 if( downinfer+downconflen+downvsids > 0.0 && upinfer+upconflen+upvsids != 0 )
646 n2startinfers++;
647#endif
648
649 SCIP_CALL( SCIPinitVarBranchStats(scip, vars[i], 0.0, 0.0, downvsids, upvsids, downconflen, upconflen, downinfer, upinfer, 0.0, 0.0) );
650 }
651 }
652
653#ifdef SCIP_DEBUG
654 if( cutoff )
655 {
656 SCIPdebugMsg(scip, "Rapidlearning detected %s infeasibility.\n", global ? "global" : "local");
657 }
658
659 SCIPdebugMsg(scip, "Rapidlearning added %d %s conflicts, changed %d bounds, %s primal solution, %s dual bound improvement.\n",
660 nconflicts, global ? "global" : "local", nbdchgs, soladded ? "found" : "no", dualboundchg ? "found" : "no");
661
662 SCIPdebugMsg(scip, "YYY Infervalues initialized on one side: %5.2f %% of variables, %5.2f %% on both sides\n",
663 100.0 * n1startinfers/(SCIP_Real)nvars, 100.0 * n2startinfers/(SCIP_Real)nvars);
664#endif
665
666 /* change result pointer */
667 if( cutoff )
668 *result = SCIP_CUTOFF;
669 else if( nconflicts > 0 || dualboundchg )
670 *result = SCIP_CONSADDED;
671 else if( nbdchgs > 0 )
672 *result = SCIP_REDUCEDDOM;
673
674 /* free local data */
675 assert(oldnconss != NULL);
676 assert(conshdlrs != NULL);
677 assert(varmapbw != NULL);
678 SCIPfreeBufferArray(scip, &oldnconss);
679 SCIPfreeBufferArray(scip, &conshdlrs);
680 SCIPhashmapFree(&varmapbw);
681
682 /* free subproblem */
683 SCIPfreeBufferArray(scip, &subvars);
684
685 return SCIP_OKAY;
686}
687
688/** returns whether rapid learning is allowed to run locally */
689static
691 SCIP* scip, /**< SCIP data structure */
692 SCIP_SEPADATA* sepadata, /**< separator's private data */
693 SCIP_Bool* run /**< pointer to store whether rapid learning is allowed to run */
694 )
695{
696 assert(scip != NULL);
697 assert(sepadata != NULL);
698
699 *run = FALSE;
700
701 /* return TRUE if local exec should not be checked */
702 if( !sepadata->checkexec )
703 {
704 *run = TRUE;
705 }
706
707 /* problem has zero objective function, i.e., it is a pure feasibility problem */
708 if( !(*run) && sepadata->checkobj && SCIPgetNObjVars(scip) == 0 )
709 {
710 SCIPdebugMsg(scip, "-> allow local rapid learning due to global zero objective\n");
711
712 *run = TRUE;
713 }
714
715 /* check whether a solution was found */
716 if( !(*run) && sepadata->checknsols && SCIPgetNSolsFound(scip) == 0 )
717 {
718 SCIPdebugMsg(scip, "-> allow local rapid learning due to no solution found so far\n");
719
720 *run = TRUE;
721 }
722
723 /* check whether the dual bound has not changed since the root node */
724 if( !(*run) && sepadata->checkdualbound && sepadata->nwaitingnodes < SCIPgetNNodes(scip) )
725 {
726 SCIP_Real rootdualbound;
727 SCIP_Real locdualbound;
728
729 rootdualbound = SCIPgetLowerboundRoot(scip);
730 locdualbound = SCIPgetLocalLowerbound(scip);
731
732 if( SCIPisEQ(scip, rootdualbound, locdualbound) )
733 {
734 SCIPdebugMsg(scip, "-> allow local rapid learning due to equal dualbound\n");
735
736 *run = TRUE;
737 }
738 }
739
740 /* check leaf nodes */
741 if( !(*run) && sepadata->checkleaves )
742 {
744
745 if( SCIPisLE(scip, sepadata->mininflpratio, ratio) )
746 {
747 SCIPdebugMsg(scip, "-> allow local rapid learning due to inf/obj leaves ratio\n");
748
749 *run = TRUE;
750 }
751 }
752
753 /* check whether all undecided integer variables have zero objective coefficient */
754 if( !(*run) && sepadata->checkobj )
755 {
756 SCIP_Bool allzero;
757 SCIP_VAR** vars;
758 int ndiscvars;
759 int i;
760
761 allzero = TRUE;
762 vars = SCIPgetVars(scip);
764
765 for( i = 0; i < ndiscvars; i++ )
766 {
767 assert(SCIPvarIsIntegral(vars[i]));
768
769 /* skip locally fixed variables */
770 if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) )
771 continue;
772
773 if( !SCIPisZero(scip, SCIPvarGetObj(vars[i])) )
774 {
775 allzero = FALSE;
776 break;
777 }
778 }
779
780 if( allzero )
781 {
782 SCIPdebugMsg(scip, "-> allow local rapid learning due to local zero objective\n");
783
784 *run = TRUE;
785 }
786 }
787
788 /* check degeneracy */
789 if( !(*run) && sepadata->checkdegeneracy )
790 {
791 SCIP_Real degeneracy;
792 SCIP_Real varconsratio;
793
794 SCIP_CALL( SCIPgetLPDualDegeneracy(scip, &degeneracy, &varconsratio) );
795
796 SCIPdebugMsg(scip, "degeneracy: %.2f ratio: %.2f\n", degeneracy, varconsratio);
797
798 if( degeneracy >= sepadata->mindegeneracy || varconsratio >= sepadata->minvarconsratio )
799 {
800 SCIPdebugMsg(scip, "-> allow local rapid learning due to degeneracy\n");
801
802 *run = TRUE;
803 }
804 }
805
806 return SCIP_OKAY;
807}
808
809/** LP solution separation method of separator */
810static
811SCIP_DECL_SEPAEXECLP(sepaExeclpRapidlearning)
812{/*lint --e{715}*/
813 SCIP_VAR** vars;
814 SCIP* subscip;
815 SCIP_SEPADATA* sepadata;
816 SCIP_Bool global;
817 SCIP_Bool run;
818 SCIP_Bool success;
819 SCIP_RETCODE retcode;
820 int ndiscvars;
821 int i;
822
823 assert(sepa != NULL);
824 assert(scip != NULL);
825 assert(result != NULL);
826
827 *result = SCIP_DIDNOTRUN;
828
830
831 /* only run when still not fixed binary variables exists */
832 if( ndiscvars == 0 )
833 return SCIP_OKAY;
834
835 /* get separator's data */
836 sepadata = SCIPsepaGetData(sepa);
837 assert(sepadata != NULL);
838
839 /* call separator at most maxcalls times */
840 if( SCIPsepaGetNCalls(sepa) >= sepadata->maxcalls )
841 return SCIP_OKAY;
842
843 /* only run for integer programs */
844 if( !sepadata->contvars && ndiscvars != SCIPgetNVars(scip) )
845 return SCIP_OKAY;
846
847 /* only run if there are few enough continuous variables */
848 if( sepadata->contvars && SCIPgetNContVars(scip) > sepadata->contvarsquot * SCIPgetNVars(scip) )
849 return SCIP_OKAY;
850
851 /* do not run if pricers are present */
852 if( SCIPgetNActivePricers(scip) > 0 )
853 return SCIP_OKAY;
854
855 /* if the separator should be exclusive to the root node, this prevents multiple calls due to restarts */
856 if( SCIPsepaGetFreq(sepa) == 0 && SCIPsepaGetNCalls(sepa) > 0 )
857 return SCIP_OKAY;
858
859 /* call separator at most once per node */
860 if( SCIPsepaGetNCallsAtNode(sepa) > 0 )
861 return SCIP_OKAY;
862
863 /* the information deduced from rapid learning is globally valid only if we are at the root node; thus we can't use
864 * the depth argument of the callback
865 */
867
868 /* check if rapid learning should be applied locally */
869 SCIP_CALL( checkExec(scip, sepadata, &run) );
870
871 /* @todo check whether we want to run at the root node again, e.g., inf/obj ratio is large enough */
872 if( !run )
873 return SCIP_OKAY;
874
875 /* do not call rapid learning, if the problem is too big */
876 if( SCIPgetNVars(scip) > sepadata->maxnvars || SCIPgetNConss(scip) > sepadata->maxnconss )
877 return SCIP_OKAY;
878
879 if( SCIPisStopped(scip) )
880 return SCIP_OKAY;
881
882 /* check whether there is enough time and memory left */
883 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
884
885 if( !success)
886 return SCIP_OKAY;
887
888 /* skip rapid learning when the sub-SCIP would contain an integer variable with an infinite bound in direction of the
889 * objective function; this might lead to very bad branching decisions when enforcing a pseudo solution (#1439)
890 */
891 vars = SCIPgetVars(scip);
892 for( i = SCIPgetNBinVars(scip); i < ndiscvars; i++ )
893 {
894 SCIP_Real lb = SCIPvarGetLbLocal(vars[i]);
895 SCIP_Real ub = SCIPvarGetUbLocal(vars[i]);
896 SCIP_Real obj = SCIPvarGetObj(vars[i]);
897
898 if( (SCIPisNegative(scip, obj) && SCIPisInfinity(scip, ub))
899 || (SCIPisPositive(scip, obj) && SCIPisInfinity(scip, -lb)) )
900 {
901 SCIPdebugMsg(scip, "unbounded integer variable %s (in [%g,%g]) with objective %g -> skip rapid learning\n",
902 SCIPvarGetName(vars[i]), lb, ub, obj);
903 return SCIP_OKAY;
904 }
905 }
906
907 *result = SCIP_DIDNOTFIND;
908
909 SCIP_CALL( SCIPcreate(&subscip) );
910
911 retcode = setupAndSolveSubscipRapidlearning(scip, subscip, sepadata, (int)SCIPsepaGetNCalls(sepa)+1, global, result);
912
913 SCIP_CALL( SCIPfree(&subscip) );
914
915 return retcode;
916}
917
918
919/*
920 * separator specific interface methods
921 */
922
923/** creates the rapidlearning separator and includes it in SCIP */
925 SCIP* scip /**< SCIP data structure */
926 )
927{
928 SCIP_SEPADATA* sepadata;
929 SCIP_SEPA* sepa;
930
931 /* create rapidlearning separator data */
932 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
933
934 /* include separator */
937 sepaExeclpRapidlearning, NULL,
938 sepadata) );
939
940 assert(sepa != NULL);
941
942 /* set non-NULL pointers to callback methods */
943 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyRapidlearning) );
944 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeRapidlearning) );
945
946 /* add rapidlearning separator parameters */
947 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/applyconflicts",
948 "should the found conflicts be applied in the original SCIP?",
949 &sepadata->applyconflicts, TRUE, DEFAULT_APPLYCONFLICTS, NULL, NULL) );
950
951 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/applybdchgs",
952 "should the found global bound deductions be applied in the original SCIP?",
953 &sepadata->applybdchgs, TRUE, DEFAULT_APPLYBDCHGS, NULL, NULL) );
954
955 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/applyinfervals",
956 "should the inference values be used as initialization in the original SCIP?",
957 &sepadata->applyinfervals, TRUE, DEFAULT_APPLYINFERVALS, NULL, NULL) );
958
959 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/reducedinfer",
960 "should the inference values only be used when " SEPA_NAME " found other reductions?",
961 &sepadata->reducedinfer, TRUE, DEFAULT_REDUCEDINFER, NULL, NULL) );
962
963 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/applyprimalsol",
964 "should the incumbent solution be copied to the original SCIP?",
965 &sepadata->applyprimalsol, TRUE, DEFAULT_APPLYPRIMALSOL, NULL, NULL) );
966
967 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/applysolved",
968 "should a solved status be copied to the original SCIP?",
969 &sepadata->applysolved, TRUE, DEFAULT_APPLYSOLVED, NULL, NULL) );
970
971 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/checkdegeneracy",
972 "should local LP degeneracy be checked?",
973 &sepadata->checkdegeneracy, TRUE, DEFAULT_CHECKDEGANERACY, NULL, NULL) );
974
975 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/checkdualbound",
976 "should the progress on the dual bound be checked?",
977 &sepadata->checkdualbound, TRUE, DEFAULT_CHECKDUALBOUND, NULL, NULL) );
978
979 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/checkleaves",
980 "should the ratio of leaves proven to be infeasible and exceeding the cutoff bound be checked?",
981 &sepadata->checkleaves, TRUE, DEFAULT_CHECKLEAVES, NULL, NULL) );
982
983 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/checkexec",
984 "check whether rapid learning should be executed",
985 &sepadata->checkexec, TRUE, DEFAULT_CHECKEXEC, NULL, NULL) );
986
987 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/checkobj",
988 "should the (local) objective function be checked?",
989 &sepadata->checkobj, TRUE, DEFAULT_CHECKOBJ, NULL, NULL) );
990
991 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/checknsols",
992 "should the number of solutions found so far be checked?",
993 &sepadata->checknsols, TRUE, DEFAULT_CHECKNSOLS, NULL, NULL) );
994
995 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/contvars",
996 "should rapid learning be applied when there are continuous variables?",
997 &sepadata->contvars, TRUE, DEFAULT_CONTVARS, NULL, NULL) );
998
999 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/contvarsquot",
1000 "maximal portion of continuous variables to apply rapid learning",
1001 &sepadata->contvarsquot, TRUE, DEFAULT_CONTVARSQUOT, 0.0, 1.0, NULL, NULL) );
1002
1003 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/lpiterquot",
1004 "maximal fraction of LP iterations compared to node LP iterations",
1005 &sepadata->lpiterquot, TRUE, DEFAULT_LPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1006
1007 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/mindegeneracy",
1008 "minimal degeneracy threshold to allow local rapid learning",
1009 &sepadata->mindegeneracy, TRUE, DEFAULT_MINDEGENERACY, 0.0, 1.0, NULL, NULL) );
1010
1011 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/mininflpratio",
1012 "minimal threshold of inf/obj leaves to allow local rapid learning",
1013 &sepadata->mininflpratio, TRUE, DEFAULT_MININFLPRATIO, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1014
1015 SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/minvarconsratio",
1016 "minimal ratio of unfixed variables in relation to basis size to allow local rapid learning",
1017 &sepadata->minvarconsratio, TRUE, DEFAULT_MINVARCONSRATIO, 1.0, SCIP_REAL_MAX, NULL, NULL) );
1018
1019 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxnvars",
1020 "maximum problem size (variables) for which rapid learning will be called",
1021 &sepadata->maxnvars, TRUE, DEFAULT_MAXNVARS, 0, INT_MAX, NULL, NULL) );
1022
1023 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxnconss",
1024 "maximum problem size (constraints) for which rapid learning will be called",
1025 &sepadata->maxnconss, TRUE, DEFAULT_MAXNCONSS, 0, INT_MAX, NULL, NULL) );
1026
1027 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxcalls",
1028 "maximum number of overall calls",
1029 &sepadata->maxcalls, TRUE, DEFAULT_MAXCALLS, 0, INT_MAX, NULL, NULL) );
1030
1031 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxnodes",
1032 "maximum number of nodes considered in rapid learning run",
1033 &sepadata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
1034
1035 SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/minnodes",
1036 "minimum number of nodes considered in rapid learning run",
1037 &sepadata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
1038
1039 SCIP_CALL( SCIPaddLongintParam(scip, "separating/" SEPA_NAME "/nwaitingnodes",
1040 "number of nodes that should be processed before rapid learning is executed locally based on the progress of the dualbound",
1041 &sepadata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0L, SCIP_LONGINT_MAX, NULL, NULL) );
1042
1043 SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/copycuts",
1044 "should all active cuts from cutpool be copied to constraints in subproblem?",
1045 &sepadata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1046
1047 return SCIP_OKAY;
1048}
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL_ABORT(x)
Definition: def.h:353
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_LONGINT_MAX
Definition: def.h:159
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE 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 SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, 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_Bool global, SCIP_Bool *valid)
Definition: scip_copy.c:1591
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 SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
Definition: scip_copy.c:1408
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3296
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:339
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:307
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:498
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
int SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2220
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2127
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2172
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1422
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3042
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Real SCIPgetLocalLowerbound(SCIP *scip)
Definition: scip_prob.c:3585
SCIP_RETCODE SCIPupdateLocalDualbound(SCIP *scip, SCIP_Real newbound)
Definition: scip_prob.c:3646
SCIP_RETCODE SCIPaddConflict(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_prob.c:3228
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:111
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:904
SCIP_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
Definition: scip_param.c:385
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:953
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
Definition: scip_param.c:882
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 SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:979
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4636
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4593
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8473
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8383
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8413
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8403
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8433
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8214
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8393
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8483
SCIP_RETCODE SCIPgetLPDualDegeneracy(SCIP *scip, SCIP_Real *degeneracy, SCIP_Real *varconsratio)
Definition: scip_lp.c:2792
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:348
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip_sepa.c:109
int SCIPsepaGetFreq(SCIP_SEPA *sepa)
Definition: sepa.c:787
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:743
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:880
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:167
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:633
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:643
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
SCIP_Longint SCIPsepaGetNCalls(SCIP_SEPA *sepa)
Definition: sepa.c:860
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2119
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3050
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1300
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1432
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:222
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip_solve.c:2328
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Real SCIPgetLowerboundRoot(SCIP *scip)
SCIP_Longint SCIPgetNInfeasibleLeaves(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetDualbound(SCIP *scip)
int SCIPgetNRootboundChgs(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Longint SCIPgetNConflictConssApplied(SCIP *scip)
SCIP_Longint SCIPgetNObjlimLeaves(SCIP *scip)
SCIP_Longint SCIPgetNConflictConssFound(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int SCIPgetEffectiveRootDepth(SCIP *scip)
Definition: scip_tree.c:127
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_RETCODE SCIPinitVarBranchStats(SCIP *scip, SCIP_VAR *var, SCIP_Real downpscost, SCIP_Real uppscost, SCIP_Real downvsids, SCIP_Real upvsids, SCIP_Real downconflen, SCIP_Real upconflen, SCIP_Real downinfer, SCIP_Real upinfer, SCIP_Real downcutoff, SCIP_Real upcutoff)
Definition: scip_var.c:9537
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5203
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6348
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_Real SCIPgetVarAvgConflictlength(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: scip_var.c:9365
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5320
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition: scip_var.c:8176
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_VAR * SCIPvarGetTransVar(SCIP_VAR *var)
Definition: var.c:17778
SCIP_Real SCIPgetVarVSIDS(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: scip_var.c:9177
SCIP_Real SCIPgetVarAvgInferences(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: scip_var.c:9419
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition: scip_var.c:8629
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6228
SCIP_RETCODE SCIPincludeSepaRapidlearning(SCIP *scip)
methods commonly used by primal heuristics
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
public methods for problem variables
default SCIP plugins
#define DEFAULT_CHECKDUALBOUND
#define SEPA_PRIORITY
#define DEFAULT_CHECKOBJ
#define DEFAULT_MAXNCONSS
#define DEFAULT_CHECKLEAVES
#define DEFAULT_MINVARCONSRATIO
#define SEPA_DELAY
#define DEFAULT_NWAITINGNODES
#define DEFAULT_CHECKEXEC
#define DEFAULT_COPYCUTS
#define DEFAULT_MAXNODES
#define DEFAULT_MINNODES
#define DEFAULT_CHECKNSOLS
#define DEFAULT_APPLYSOLVED
#define SEPA_DESC
static SCIP_DECL_SEPACOPY(sepaCopyRapidlearning)
#define SEPA_USESSUBSCIP
#define DEFAULT_CONTVARS
#define DEFAULT_CHECKDEGANERACY
#define DEFAULT_LPITERQUOT
#define DEFAULT_REDUCEDINFER
#define DEFAULT_CONTVARSQUOT
static SCIP_RETCODE setupAndSolveSubscipRapidlearning(SCIP *scip, SCIP *subscip, SCIP_SEPADATA *sepadata, int randseed, SCIP_Bool global, SCIP_RESULT *result)
#define DEFAULT_MAXNVARS
static SCIP_DECL_SEPAFREE(sepaFreeRapidlearning)
static SCIP_DECL_SEPAEXECLP(sepaExeclpRapidlearning)
#define DEFAULT_MAXCALLS
#define DEFAULT_MININFLPRATIO
#define SEPA_MAXBOUNDDIST
#define SEPA_FREQ
#define DEFAULT_APPLYCONFLICTS
#define SEPA_NAME
static SCIP_RETCODE checkExec(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Bool *run)
#define DEFAULT_APPLYBDCHGS
#define DEFAULT_APPLYPRIMALSOL
#define DEFAULT_MINDEGENERACY
#define DEFAULT_APPLYINFERVALS
rapidlearning separator
@ SCIP_CONFTYPE_UNKNOWN
Definition: type_conflict.h:59
@ SCIP_BRANCHDIR_DOWNWARDS
Definition: type_history.h:43
@ SCIP_BRANCHDIR_UPWARDS
Definition: type_history.h:44
@ SCIP_PARAMSETTING_OFF
Definition: type_paramset.h:63
@ SCIP_PARAMSETTING_FAST
Definition: type_paramset.h:62
@ SCIP_PARAMEMPHASIS_CPSOLVER
Definition: type_paramset.h:72
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_CONSADDED
Definition: type_result.h:52
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_INVALIDCALL
Definition: type_retcode.h:51
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:52
@ SCIP_STAGE_SOLVED
Definition: type_set.h:54
@ SCIP_STATUS_OPTIMAL
Definition: type_stat.h:61
@ SCIP_STATUS_INFEASIBLE
Definition: type_stat.h:62
@ SCIP_VARTYPE_INTEGER
Definition: type_var.h:63
@ SCIP_VARTYPE_IMPLINT
Definition: type_var.h:64