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-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file sepa_rapidlearning.c
17  * @brief rapidlearning separator
18  * @author Timo Berthold
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #ifndef NDEBUG
25 #include <string.h>
26 #endif
27 
28 #include "scip/sepa_rapidlearning.h"
29 #include "scip/scipdefplugins.h"
30 #include "scip/pub_var.h"
31 
32 #define SEPA_NAME "rapidlearning"
33 #define SEPA_DESC "rapid learning heuristic and separator"
34 #define SEPA_PRIORITY -1200000
35 #define SEPA_FREQ -1
36 #define SEPA_MAXBOUNDDIST 1.0
37 #define SEPA_USESSUBSCIP TRUE /**< does the separator use a secondary SCIP instance? */
38 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
39 
40 #define DEFAULT_APPLYCONFLICTS TRUE /**< should the found conflicts be applied in the original SCIP? */
41 #define DEFAULT_APPLYBDCHGS TRUE /**< should the found global bound deductions be applied in the original SCIP?
42  * apply only if conflicts and incumbent solution will be copied too
43  */
44 #define DEFAULT_APPLYINFERVALS TRUE /**< should the inference values be used as initialization in the original SCIP? */
45 #define DEFAULT_REDUCEDINFER FALSE /**< should the inference values only be used when rapid learning found other reductions? */
46 #define DEFAULT_APPLYPRIMALSOL TRUE /**< should the incumbent solution be copied to the original SCIP? */
47 #define DEFAULT_APPLYSOLVED TRUE /**< should a solved status be copied to the original SCIP? */
48 
49 #define DEFAULT_MAXNVARS 10000 /**< maximum problem size (variables) for which rapid learning will be called */
50 #define DEFAULT_MAXNCONSS 10000 /**< maximum problem size (constraints) for which rapid learning will be called */
51 
52 #define DEFAULT_MINNODES 500 /**< minimum number of nodes considered in rapid learning run */
53 #define DEFAULT_MAXNODES 5000 /**< maximum number of nodes considered in rapid learning run */
54 
55 #define DEFAULT_CONTVARS FALSE /**< should rapid learning be applied when there are continuous variables? */
56 #define DEFAULT_CONTVARSQUOT 0.3 /**< maximal portion of continuous variables to apply rapid learning */
57 #define DEFAULT_LPITERQUOT 0.2 /**< maximal fraction of LP iterations compared to node LP iterations */
58 #define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the
59  * original scip be copied to constraints of the subscip
60  */
61 
62 
63 /*
64  * Data structures
65  */
66 
67 /** separator data */
68 struct SCIP_SepaData
69 {
70  SCIP_Bool applyconflicts; /**< should the found conflicts be applied in the original SCIP? */
71  SCIP_Bool applybdchgs; /**< should the found global bound deductions be applied in the original SCIP? */
72  SCIP_Bool applyinfervals; /**< should the inference values be used as initialization in the original SCIP? */
73  SCIP_Bool reducedinfer; /**< should the inference values only be used when rapid learning found other reductions? */
74  SCIP_Bool applyprimalsol; /**< should the incumbent solution be copied to the original SCIP? */
75  SCIP_Bool applysolved; /**< should a solved status ba copied to the original SCIP? */
76  int maxnvars; /**< maximum problem size (variables) for which rapid learning will be called */
77  int maxnconss; /**< maximum problem size (constraints) for which rapid learning will be called */
78  int minnodes; /**< minimum number of nodes considered in rapid learning run */
79  int maxnodes; /**< maximum number of nodes considered in rapid learning run */
80  SCIP_Bool contvars; /**< should rapid learning be applied when there are continuous variables? */
81  SCIP_Real contvarsquot; /**< maximal portion of continuous variables to apply rapid learning */
82  SCIP_Real lpiterquot; /**< maximal fraction of LP iterations compared to node LP iterations */
83  SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in
84  * subproblem?
85  */
86 };
87 
88 /** creates a new solution for the original problem by copying the solution of the subproblem */
89 static
90 SCIP_RETCODE createNewSol(
91  SCIP* scip, /**< original SCIP data structure */
92  SCIP* subscip, /**< SCIP structure of the subproblem */
93  SCIP_VAR** subvars, /**< the variables of the subproblem */
94  SCIP_HEUR* heur, /**< trysol heuristic structure */
95  SCIP_SOL* subsol, /**< solution of the subproblem */
96  SCIP_Bool* success /**< used to store whether new solution was found or not */
97  )
98 {
99  SCIP_VAR** vars; /* the original problem's variables */
100  int nvars;
101  SCIP_Real* subsolvals; /* solution values of the subproblem */
102  SCIP_SOL* newsol; /* solution to be created for the original problem */
103 
104  assert( scip != NULL );
105  assert( subscip != NULL );
106  assert( subvars != NULL );
107  assert( heur != NULL );
108  assert( subsol != NULL );
109  assert( success != NULL );
110 
111  /* get variables' data */
112  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
113  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
114  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
115  */
116  assert(nvars <= SCIPgetNOrigVars(subscip));
117 
118  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
119 
120  /* copy the solution */
121  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
122 
123  /* create new solution for the original problem */
124  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
125  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
126 
127  /* check feasibility of new solution and pass it to trysol heuristic */
128  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, TRUE, TRUE, TRUE, success) );
129 
130  SCIPfreeBufferArray(scip, &subsolvals);
131 
132  return SCIP_OKAY;
133 }
134 
135 /*
136  * Callback methods of separator
137  */
138 
139 /** copy method for separator plugins (called when SCIP copies plugins) */
140 static
141 SCIP_DECL_SEPACOPY(sepaCopyRapidlearning)
142 { /*lint --e{715}*/
143  assert(scip != NULL);
144  assert(sepa != NULL);
145  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
146 
147  /* call inclusion method of constraint handler */
148  SCIP_CALL( SCIPincludeSepaRapidlearning(scip) );
149 
150  return SCIP_OKAY;
151 }
152 
153 /** destructor of separator to free user data (called when SCIP is exiting) */
154 static
155 SCIP_DECL_SEPAFREE(sepaFreeRapidlearning)
156 { /*lint --e{715}*/
157  SCIP_SEPADATA* sepadata;
158 
159  assert(sepa != NULL);
160  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
161  assert(scip != NULL);
162 
163  /* free separator data */
164  sepadata = SCIPsepaGetData(sepa);
165  assert(sepadata != NULL);
166  SCIPfreeMemory(scip, &sepadata);
167  SCIPsepaSetData(sepa, NULL);
168 
169  return SCIP_OKAY;
170 }
171 
172 
173 /** LP solution separation method of separator */
174 static
175 SCIP_DECL_SEPAEXECLP(sepaExeclpRapidlearning)
176 {/*lint --e{715}*/
177  SCIP* subscip; /* the subproblem created by rapid learning */
178  SCIP_SEPADATA* sepadata; /* separator's private data */
179 
180  SCIP_VAR** vars; /* original problem's variables */
181  SCIP_VAR** subvars; /* subproblem's variables */
182  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
183  SCIP_HASHMAP* varmapbw; /* mapping of sub-SCIP variables to SCIP variables */
184 
185  SCIP_CONSHDLR** conshdlrs; /* array of constraint handler's that might that might obtain conflicts */
186  int* oldnconss; /* number of constraints without rapid learning conflicts */
187 
188  SCIP_Longint nodelimit; /* node limit for the subproblem */
189  SCIP_Real timelimit; /* time limit for the subproblem */
190  SCIP_Real memorylimit; /* memory limit for the subproblem */
191 
192  int nconshdlrs; /* size of conshdlr and oldnconss array */
193  int nfixedvars; /* number of variables that could be fixed by rapid learning */
194  int nvars; /* number of variables */
195  int restartnum; /* maximal number of conflicts that should be created */
196  int i; /* counter */
197 
198  SCIP_Bool success; /* was problem creation / copying constraint successful? */
199  SCIP_RETCODE retcode; /* used for catching sub-SCIP errors in debug mode */
200 
201  int nconflicts; /* statistic: number of conflicts applied */
202  int nbdchgs; /* statistic: number of bound changes applied */
203  int n1startinfers; /* statistic: number of one side infer values */
204  int n2startinfers; /* statistic: number of both side infer values */
205 
206  SCIP_Bool soladded; /* statistic: was a new incumbent found? */
207  SCIP_Bool dualboundchg; /* statistic: was a new dual bound found? */
208  SCIP_Bool disabledualreductions; /* TRUE, if dual reductions in sub-SCIP are not valid for original SCIP,
209  * e.g., because a constraint could not be copied or a primal solution
210  * could not be copied back
211  */
212 
213  int ndiscvars;
214 
215  soladded = FALSE;
216 
217  assert(sepa != NULL);
218  assert(scip != NULL);
219  assert(result != NULL);
220 
221  *result = SCIP_DIDNOTRUN;
222 
223  ndiscvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip);
224 
225  /* only run when still not fixed binary variables exists */
226  if( ndiscvars == 0 )
227  return SCIP_OKAY;
228 
229  /* get separator's data */
230  sepadata = SCIPsepaGetData(sepa);
231  assert(sepadata != NULL);
232 
233  /* only run for integer programs */
234  if( !sepadata->contvars && ndiscvars != SCIPgetNVars(scip) )
235  return SCIP_OKAY;
236 
237  /* only run if there are few enough continuous variables */
238  if( sepadata->contvars && SCIPgetNContVars(scip) > sepadata->contvarsquot * SCIPgetNVars(scip) )
239  return SCIP_OKAY;
240 
241  /* do not run if pricers are present */
242  if( SCIPgetNActivePricers(scip) > 0 )
243  return SCIP_OKAY;
244 
245  /* if the separator should be exclusive to the root node, this prevents multiple calls due to restarts */
246  if( SCIPsepaGetFreq(sepa) == 0 && SCIPsepaGetNCalls(sepa) > 0 )
247  return SCIP_OKAY;
248 
249  /* call separator at most once per node */
250  if( SCIPsepaGetNCallsAtNode(sepa) > 0 )
251  return SCIP_OKAY;
252 
253  /* do not call rapid learning, if the problem is too big */
254  if( SCIPgetNVars(scip) > sepadata->maxnvars || SCIPgetNConss(scip) > sepadata->maxnconss )
255  return SCIP_OKAY;
256 
257  if( SCIPisStopped(scip) )
258  return SCIP_OKAY;
259 
260  *result = SCIP_DIDNOTFIND;
261 
262  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
263 
264  /* initializing the subproblem */
265  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
266  SCIP_CALL( SCIPcreate(&subscip) );
267  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), SCIPcalcHashtableSize(5 * nvars)) );
268  success = FALSE;
269 
270  /* copy the subproblem */
271  SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "rapid", FALSE, FALSE, TRUE, &success) );
272 
273  if( sepadata->copycuts )
274  {
275  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
276  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, FALSE, NULL) );
277  }
278 
279  for( i = 0; i < nvars; i++ )
280  {
281  subvars[i] = (SCIP_VAR*) (size_t) SCIPhashmapGetImage(varmapfw, vars[i]);
282 
283  /* change implicit integer variables to integer type */
284  if( SCIPvarGetType(subvars[i]) == SCIP_VARTYPE_IMPLINT )
285  {
286  SCIP_Bool infeasible;
287 
288  SCIP_CALL( SCIPchgVarType(subscip, subvars[i], SCIP_VARTYPE_INTEGER, &infeasible) );
289  assert(!infeasible);
290  }
291  }
292 
293  SCIPhashmapFree(&varmapfw);
294 
295  /* This avoids dual presolving.
296  *
297  * If the copy is not valid, it should be a relaxation of the problem (constraints might have failed to be copied,
298  * but no variables should be missing because we stop earlier anyway if pricers are present).
299  * By disabling dual presolving, conflicts found in a relaxation are still valid for the original problem.
300  */
301  if( !success )
302  {
303  for( i = 0; i < nvars; i++ )
304  {
305  SCIP_CALL( SCIPaddVarLocks(subscip, subvars[i], 1, 1 ) );
306  }
307  }
308 
309  SCIPdebugMessage("Copying SCIP was%s successful.\n", success ? "" : " not");
310 
311  /* mimic an FD solver: DFS, no LP solving, 1-FUIP instead of all-FUIP */
312  if( SCIPisParamFixed(subscip, "lp/solvefreq") )
313  {
314  SCIPwarningMessage(scip, "unfixing parameter lp/solvefreq in subscip of rapidlearning\n");
315  SCIP_CALL( SCIPunfixParam(subscip, "lp/solvefreq") );
316  }
317  SCIP_CALL( SCIPsetIntParam(subscip, "lp/solvefreq", -1) );
318  if( !SCIPisParamFixed(subscip, "conflict/fuiplevels") )
319  {
320  SCIP_CALL( SCIPsetIntParam(subscip, "conflict/fuiplevels", 1) );
321  }
322  if( SCIPisParamFixed(subscip, "nodeselection/dfs/stdpriority") )
323  {
324  SCIPwarningMessage(scip, "unfixing parameter nodeselection/dfs/stdpriority in subscip of rapidlearning\n");
325  SCIP_CALL( SCIPunfixParam(subscip, "nodeselection/dfs/stdpriority") );
326  }
327  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/dfs/stdpriority", INT_MAX/4) );
328 
329  if( !SCIPisParamFixed(subscip, "propagating/pseudoobj/freq") )
330  {
331  SCIP_CALL( SCIPsetIntParam(subscip, "propagating/pseudoobj/freq", -1) );
332  }
333  if( !SCIPisParamFixed(subscip, "constraints/disableenfops") )
334  {
335  SCIP_CALL( SCIPsetBoolParam(subscip, "constraints/disableenfops", TRUE) );
336  }
337 
338  /* use inference branching */
339  if( !SCIPisParamFixed(subscip, "branching/inference/useweightedsum") )
340  {
341  SCIP_CALL( SCIPsetBoolParam(subscip, "branching/inference/useweightedsum", FALSE) );
342  }
343 
344  /* only create short conflicts */
345  if( !SCIPisParamFixed(subscip, "conflict/maxvarsfac") )
346  {
347  SCIP_CALL( SCIPsetRealParam(subscip, "conflict/maxvarsfac", 0.05) );
348  }
349 
350  /* set limits for the subproblem */
351  nodelimit = SCIPgetNLPIterations(scip);
352  nodelimit = MAX(sepadata->minnodes, nodelimit);
353  nodelimit = MIN(sepadata->maxnodes, nodelimit);
354 
355  restartnum = 1000;
356 
357  /* check whether there is enough time and memory left */
358  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
359  if( !SCIPisInfinity(scip, timelimit) )
360  timelimit -= SCIPgetSolvingTime(scip);
361  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
362 
363  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
364  if( !SCIPisInfinity(scip, memorylimit) )
365  {
366  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
367  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
368  }
369 
370  /* abort if no time is left or not enough memory to create a copy of SCIP
371  * for rapid learning, this does not include external memory usage, because no LPs are solved
372  */
373  if( timelimit <= 0.0 || memorylimit <= SCIPgetMemExternEstim(scip)/1048576.0 )
374  goto TERMINATE;
375 
376  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit/5) );
377  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
378  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
379  SCIP_CALL( SCIPsetIntParam(subscip, "limits/restarts", 0) );
380  SCIP_CALL( SCIPsetIntParam(subscip, "conflict/restartnum", restartnum) );
381 
382  /* forbid recursive call of heuristics and separators solving subMIPs */
383  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
384 
385  /* disable cutting plane separation */
386  SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
387 
388  /* disable expensive presolving */
389  SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
390 
391  /* do not abort subproblem on CTRL-C */
392  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
393 
394 #ifndef SCIP_DEBUG
395  /* disable output to console */
396  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
397 #endif
398 
399  /* add an objective cutoff */
400  SCIP_CALL( SCIPsetObjlimit(subscip, SCIPgetUpperbound(scip)) );
401 
402  /* create the variable mapping hash map */
403  SCIP_CALL( SCIPhashmapCreate(&varmapbw, SCIPblkmem(scip), SCIPcalcHashtableSize(5 * nvars)) );
404 
405  /* store reversing mapping of variables */
406  SCIP_CALL( SCIPtransformProb(subscip) );
407  for( i = 0; i < nvars; ++i)
408  {
409  SCIP_CALL( SCIPhashmapInsert(varmapbw, SCIPvarGetTransVar(subvars[i]), vars[i]) );
410  }
411 
412  /* allocate memory for constraints storage. Each constraint that will be created from now on will be a conflict.
413  * Therefore, we need to remember oldnconss to get the conflicts from the FD search.
414  */
415  nconshdlrs = 4;
416  SCIP_CALL( SCIPallocBufferArray(scip, &conshdlrs, nconshdlrs) );
417  SCIP_CALL( SCIPallocBufferArray(scip, &oldnconss, nconshdlrs) );
418 
419  /* store number of constraints before rapid learning search */
420  conshdlrs[0] = SCIPfindConshdlr(subscip, "bounddisjunction");
421  conshdlrs[1] = SCIPfindConshdlr(subscip, "setppc");
422  conshdlrs[2] = SCIPfindConshdlr(subscip, "linear");
423  conshdlrs[3] = SCIPfindConshdlr(subscip, "logicor");
424 
425  /* redundant constraints might be eliminated in presolving */
426  SCIP_CALL( SCIPpresolve(subscip));
427 
428  for( i = 0; i < nconshdlrs; ++i)
429  {
430  if( conshdlrs[i] != NULL )
431  oldnconss[i] = SCIPconshdlrGetNConss(conshdlrs[i]);
432  }
433 
434  nfixedvars = SCIPgetNFixedVars(scip);
435 
436  /* solve the subproblem */
437  retcode = SCIPsolve(subscip);
438 
439  /* Errors in solving the subproblem should not kill the overall solving process
440  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
441  */
442  if( retcode != SCIP_OKAY )
443  {
444 #ifndef NDEBUG
445  SCIP_CALL( retcode );
446 #endif
447  SCIPwarningMessage(scip, "Error while solving subproblem in rapid learning separator; sub-SCIP terminated with code <%d>\n",retcode);
448  }
449 
450  /* if problem was already solved do not increase limits to run again */
451  if( SCIPgetStage(subscip) == SCIP_STAGE_SOLVED )
452  {
453  SCIPdebugMessage("Subscip was completely solved, status %d.\n", SCIPgetStatus(subscip));
454  }
455  /* abort solving, if limit of applied conflicts is reached */
456  else if( SCIPgetNConflictConssApplied(subscip) >= restartnum )
457  {
458  SCIPdebugMessage("finish after %lld successful conflict calls.\n", SCIPgetNConflictConssApplied(subscip));
459  }
460  /* if the first 20% of the solution process were successful, proceed */
461  else if( (sepadata->applyprimalsol && SCIPgetNSols(subscip) > 0 && SCIPisFeasLT(scip, SCIPgetUpperbound(subscip), SCIPgetUpperbound(scip) ) )
462  || (sepadata->applybdchgs && SCIPgetNFixedVars(subscip) > nfixedvars)
463  || (sepadata->applyconflicts && SCIPgetNConflictConssApplied(subscip) > 0) )
464  {
465  SCIPdebugMessage("proceed solving after the first 20%% of the solution process, since:\n");
466 
467  if( SCIPgetNSols(subscip) > 0 && SCIPisFeasLE(scip, SCIPgetUpperbound(subscip), SCIPgetUpperbound(scip) ) )
468  {
469  SCIPdebugMessage(" - there was a better solution (%f < %f)\n",SCIPgetUpperbound(subscip), SCIPgetUpperbound(scip));
470  }
471  if( SCIPgetNFixedVars(subscip) > nfixedvars )
472  {
473  SCIPdebugMessage(" - there were %d variables fixed\n", SCIPgetNFixedVars(scip)-nfixedvars );
474  }
475  if( SCIPgetNConflictConssFound(subscip) > 0 )
476  {
477  SCIPdebugMessage(" - there were %lld conflict constraints created\n", SCIPgetNConflictConssApplied(subscip));
478  }
479 
480  /* set node limit to 100% */
481  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
482 
483  /* solve the subproblem */
484  retcode = SCIPsolve(subscip);
485 
486  /* Errors in solving the subproblem should not kill the overall solving process
487  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
488  */
489  if( retcode != SCIP_OKAY )
490  {
491 #ifndef NDEBUG
492  SCIP_CALL( retcode );
493 #endif
494  SCIPwarningMessage(scip, "Error while solving subproblem in rapid learning separator; sub-SCIP terminated with code <%d>\n",retcode);
495  }
496  }
497  else
498  {
499  SCIPdebugMessage("do not proceed solving after the first 20%% of the solution process.\n");
500  }
501 
502 #ifdef SCIP_DEBUG
503  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
504 #endif
505 
506  disabledualreductions = FALSE;
507 
508  /* check, whether a solution was found */
509  if( sepadata->applyprimalsol && SCIPgetNSols(subscip) > 0 && SCIPfindHeur(scip, "trysol") != NULL )
510  {
511  SCIP_HEUR* heurtrysol;
512  SCIP_SOL** subsols;
513  int nsubsols;
514 
515  /* check, whether a solution was found;
516  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until was declared to be feasible
517  */
518  nsubsols = SCIPgetNSols(subscip);
519  subsols = SCIPgetSols(subscip);
520  soladded = FALSE;
521  heurtrysol = SCIPfindHeur(scip, "trysol");
522 
523  /* sequentially add solutions to trysol heuristic */
524  for( i = 0; i < nsubsols && !soladded; ++i )
525  {
526  SCIPdebugMessage("Try to create new solution by copying subscip solution.\n");
527  SCIP_CALL( createNewSol(scip, subscip, subvars, heurtrysol, subsols[i], &soladded) );
528  }
529  if( !soladded || !SCIPisEQ(scip, SCIPgetSolOrigObj(subscip, subsols[i-1]), SCIPgetSolOrigObj(subscip, subsols[0])) )
530  disabledualreductions = TRUE;
531  }
532 
533  /* if the sub problem was solved completely, we update the dual bound */
534  dualboundchg = FALSE;
535  if( sepadata->applysolved && !disabledualreductions
536  && (SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL || SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE) )
537  {
538  /* we need to multiply the dualbound with the scaling factor and add the offset,
539  * because this information has been disregarded in the sub-SCIP
540  */
541  SCIPdebugMessage("Update old dualbound %g to new dualbound %g.\n", SCIPgetDualbound(scip), SCIPretransformObj(scip, SCIPgetDualbound(subscip)));
542 
543  SCIP_CALL( SCIPupdateLocalDualbound(scip, SCIPretransformObj(scip, SCIPgetDualbound(subscip))) );
544  dualboundchg = TRUE;
545  }
546 
547  /* check, whether conflicts were created */
548  nconflicts = 0;
549  if( sepadata->applyconflicts && !disabledualreductions && SCIPgetNConflictConssApplied(subscip) > 0 )
550  {
551  SCIP_HASHMAP* consmap;
552  int hashtablesize;
553 
554  assert(SCIPgetNConflictConssApplied(subscip) < (SCIP_Longint) INT_MAX);
555  hashtablesize = (int) SCIPgetNConflictConssApplied(subscip);
556  assert(hashtablesize < INT_MAX/5);
557  hashtablesize *= 5;
558 
559  /* create the variable mapping hash map */
560  SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), SCIPcalcHashtableSize(hashtablesize)) );
561 
562  /* loop over all constraint handlers that might contain conflict constraints */
563  for( i = 0; i < nconshdlrs; ++i)
564  {
565  /* copy constraints that have been created in FD run */
566  if( conshdlrs[i] != NULL && SCIPconshdlrGetNConss(conshdlrs[i]) > oldnconss[i] )
567  {
568  SCIP_CONS** conss;
569  int c;
570  int nconss;
571 
572  nconss = SCIPconshdlrGetNConss(conshdlrs[i]);
573  conss = SCIPconshdlrGetConss(conshdlrs[i]);
574 
575  /* loop over all constraints that have been added in sub-SCIP run, these are the conflicts */
576  for( c = oldnconss[i]; c < nconss; ++c)
577  {
578  SCIP_CONS* cons;
579  SCIP_CONS* conscopy;
580 
581  cons = conss[c];
582  assert(cons != NULL);
583 
584  success = FALSE;
585 
586  /* @todo assert that flags are as they should be for conflicts */
587  SCIP_CALL( SCIPgetConsCopy(subscip, scip, cons, &conscopy, conshdlrs[i], varmapbw, consmap, NULL,
588  SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons),
589  SCIPconsIsPropagated(cons), TRUE, FALSE, SCIPconsIsDynamic(cons),
590  SCIPconsIsRemovable(cons), FALSE, TRUE, &success) );
591 
592  if( success )
593  {
594  nconflicts++;
595  SCIP_CALL( SCIPaddCons(scip, conscopy) );
596  SCIP_CALL( SCIPreleaseCons(scip, &conscopy) );
597  }
598  else
599  {
600  SCIPdebugMessage("failed to copy conflict constraint %s back to original SCIP\n", SCIPconsGetName(cons));
601  }
602  }
603  }
604  }
605  SCIPhashmapFree(&consmap);
606  }
607 
608  /* check, whether tighter global bounds were detected */
609  nbdchgs = 0;
610  if( sepadata->applybdchgs && !disabledualreductions )
611  for( i = 0; i < nvars; ++i )
612  {
613  SCIP_Bool infeasible;
614  SCIP_Bool tightened;
615 
616  assert(SCIPisLE(scip, SCIPvarGetLbGlobal(vars[i]), SCIPvarGetLbGlobal(subvars[i])));
617  assert(SCIPisLE(scip, SCIPvarGetLbGlobal(subvars[i]), SCIPvarGetUbGlobal(subvars[i])));
618  assert(SCIPisLE(scip, SCIPvarGetUbGlobal(subvars[i]), SCIPvarGetUbGlobal(vars[i])));
619 
620  /* update the bounds of the original SCIP, if a better bound was proven in the sub-SCIP */
621  /* @todo handle infeasible pointer? can it be set to TRUE? */
622  SCIP_CALL( SCIPtightenVarUb(scip, vars[i], SCIPvarGetUbGlobal(subvars[i]), FALSE, &infeasible, &tightened) );
623  if( tightened )
624  nbdchgs++;
625 
626  SCIP_CALL( SCIPtightenVarLb(scip, vars[i], SCIPvarGetLbGlobal(subvars[i]), FALSE, &infeasible, &tightened) );
627  if( tightened )
628  nbdchgs++;
629  }
630 
631  n1startinfers = 0;
632  n2startinfers = 0;
633 
634  /* install start values for inference branching */
635  /* @todo use different nbranching counters for pseudo cost and inference values and update inference values in the tree */
636  if( sepadata->applyinfervals && SCIPgetDepth(scip) == 0 && (!sepadata->reducedinfer || soladded || nbdchgs+nconflicts > 0) )
637  {
638  for( i = 0; i < nvars; ++i )
639  {
640  SCIP_Real downinfer;
641  SCIP_Real upinfer;
642  SCIP_Real downvsids;
643  SCIP_Real upvsids;
644  SCIP_Real downconflen;
645  SCIP_Real upconflen;
646 
647  /* copy downwards branching statistics */
648  downvsids = SCIPgetVarVSIDS(subscip, subvars[i], SCIP_BRANCHDIR_DOWNWARDS);
649  downconflen = SCIPgetVarAvgConflictlength(subscip, subvars[i], SCIP_BRANCHDIR_DOWNWARDS);
650  downinfer = SCIPgetVarAvgInferences(subscip, subvars[i], SCIP_BRANCHDIR_DOWNWARDS);
651 
652  /* copy upwards branching statistics */
653  upvsids = SCIPgetVarVSIDS(subscip, subvars[i], SCIP_BRANCHDIR_UPWARDS);
654  upconflen = SCIPgetVarAvgConflictlength(subscip, subvars[i], SCIP_BRANCHDIR_UPWARDS);
655  upinfer = SCIPgetVarAvgInferences(subscip, subvars[i], SCIP_BRANCHDIR_UPWARDS);
656 
657  /* memorize statistics */
658  if( downinfer+downconflen+downvsids > 0.0 || upinfer+upconflen+upvsids != 0 )
659  n1startinfers++;
660 
661  if( downinfer+downconflen+downvsids > 0.0 && upinfer+upconflen+upvsids != 0 )
662  n2startinfers++;
663 
664  SCIP_CALL( SCIPinitVarBranchStats(scip, vars[i], 0.0, 0.0, downvsids, upvsids, downconflen, upconflen, downinfer, upinfer, 0.0, 0.0) );
665  }
666  }
667 
668  SCIPdebugPrintf("XXX Rapidlearning added %d conflicts, changed %d bounds, %s primal solution, %s dual bound improvement.\n", nconflicts, nbdchgs, soladded ? "found" : "no",
669  dualboundchg ? "found" : "no");
670 
671  SCIPdebugPrintf("YYY Infervalues initialized on one side: %5.2f %% of variables, %5.2f %% on both sides\n",
672  100.0 * n1startinfers/(SCIP_Real)nvars, 100.0 * n2startinfers/(SCIP_Real)nvars);
673 
674  /* change result pointer */
675  if( nconflicts > 0 || dualboundchg )
676  *result = SCIP_CONSADDED;
677  else if( nbdchgs > 0 )
678  *result = SCIP_REDUCEDDOM;
679 
680  /* free local data */
681  SCIPfreeBufferArray(scip, &oldnconss);
682  SCIPfreeBufferArray(scip, &conshdlrs);
683 
684  SCIPhashmapFree(&varmapbw);
685 
686  TERMINATE:
687  /* free subproblem */
688  SCIPfreeBufferArray(scip, &subvars);
689  SCIP_CALL( SCIPfree(&subscip) );
690 
691  return SCIP_OKAY;
692 }
693 
694 
695 /*
696  * separator specific interface methods
697  */
698 
699 /** creates the rapidlearning separator and includes it in SCIP */
700 SCIP_RETCODE SCIPincludeSepaRapidlearning(
701  SCIP* scip /**< SCIP data structure */
702  )
703 {
704  SCIP_SEPADATA* sepadata;
705  SCIP_SEPA* sepa;
706 
707  /* create rapidlearning separator data */
708  SCIP_CALL( SCIPallocMemory(scip, &sepadata) );
709 
710  /* include separator */
711  SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
712  SEPA_USESSUBSCIP, SEPA_DELAY,
713  sepaExeclpRapidlearning, NULL,
714  sepadata) );
715 
716  assert(sepa != NULL);
717 
718  /* set non-NULL pointers to callback methods */
719  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyRapidlearning) );
720  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeRapidlearning) );
721 
722  /* add rapidlearning separator parameters */
723  SCIP_CALL( SCIPaddBoolParam(scip, "separating/"SEPA_NAME"/applyconflicts",
724  "should the found conflicts be applied in the original SCIP?",
725  &sepadata->applyconflicts, TRUE, DEFAULT_APPLYCONFLICTS, NULL, NULL) );
726 
727  SCIP_CALL( SCIPaddBoolParam(scip, "separating/"SEPA_NAME"/applybdchgs",
728  "should the found global bound deductions be applied in the original SCIP?",
729  &sepadata->applybdchgs, TRUE, DEFAULT_APPLYBDCHGS, NULL, NULL) );
730 
731  SCIP_CALL( SCIPaddBoolParam(scip, "separating/"SEPA_NAME"/applyinfervals",
732  "should the inference values be used as initialization in the original SCIP?",
733  &sepadata->applyinfervals, TRUE, DEFAULT_APPLYINFERVALS, NULL, NULL) );
734 
735  SCIP_CALL( SCIPaddBoolParam(scip, "separating/"SEPA_NAME"/reducedinfer",
736  "should the inference values only be used when "SEPA_NAME" found other reductions?",
737  &sepadata->reducedinfer, TRUE, DEFAULT_REDUCEDINFER, NULL, NULL) );
738 
739  SCIP_CALL( SCIPaddBoolParam(scip, "separating/"SEPA_NAME"/applyprimalsol",
740  "should the incumbent solution be copied to the original SCIP?",
741  &sepadata->applyprimalsol, TRUE, DEFAULT_APPLYPRIMALSOL, NULL, NULL) );
742 
743  SCIP_CALL( SCIPaddBoolParam(scip, "separating/"SEPA_NAME"/applysolved",
744  "should a solved status be copied to the original SCIP?",
745  &sepadata->applysolved, TRUE, DEFAULT_APPLYSOLVED, NULL, NULL) );
746 
747  SCIP_CALL( SCIPaddBoolParam(scip, "separating/"SEPA_NAME"/contvars",
748  "should rapid learning be applied when there are continuous variables?",
749  &sepadata->contvars, TRUE, DEFAULT_CONTVARS, NULL, NULL) );
750 
751  SCIP_CALL( SCIPaddRealParam(scip, "separating/"SEPA_NAME"/contvarsquot",
752  "maximal portion of continuous variables to apply rapid learning",
753  &sepadata->contvarsquot, TRUE, DEFAULT_CONTVARSQUOT, 0.0, 1.0, NULL, NULL) );
754 
755  SCIP_CALL( SCIPaddRealParam(scip, "separating/"SEPA_NAME"/lpiterquot",
756  "maximal fraction of LP iterations compared to node LP iterations",
757  &sepadata->lpiterquot, TRUE, DEFAULT_LPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
758 
759  SCIP_CALL( SCIPaddIntParam(scip, "separating/"SEPA_NAME"/maxnvars",
760  "maximum problem size (variables) for which rapid learning will be called",
761  &sepadata->maxnvars, TRUE, DEFAULT_MAXNVARS, 0, INT_MAX, NULL, NULL) );
762 
763  SCIP_CALL( SCIPaddIntParam(scip, "separating/"SEPA_NAME"/maxnconss",
764  "maximum problem size (constraints) for which rapid learning will be called",
765  &sepadata->maxnconss, TRUE, DEFAULT_MAXNCONSS, 0, INT_MAX, NULL, NULL) );
766 
767  SCIP_CALL( SCIPaddIntParam(scip, "separating/"SEPA_NAME"/maxnodes",
768  "maximum number of nodes considered in rapid learning run",
769  &sepadata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
770 
771  SCIP_CALL( SCIPaddIntParam(scip, "separating/"SEPA_NAME"/minnodes",
772  "minimum number of nodes considered in rapid learning run",
773  &sepadata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
774 
775  SCIP_CALL( SCIPaddBoolParam(scip, "separating/"SEPA_NAME"/copycuts",
776  "should all active cuts from cutpool be copied to constraints in subproblem?",
777  &sepadata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
778 
779  return SCIP_OKAY;
780 }
781