Scippy

SCIP

Solving Constraint Integer Programs

debug.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 debug.c
17  * @brief methods for debugging
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <stdio.h>
24 #include <string.h>
25 #include <assert.h>
26 
27 #include "scip/def.h"
28 #include "blockmemshell/memory.h"
29 #include "scip/set.h"
30 #include "scip/lp.h"
31 #include "scip/var.h"
32 #include "scip/prob.h"
33 #include "scip/tree.h"
34 #include "scip/scip.h"
35 #include "scip/debug.h"
36 #include "scip/pub_message.h"
37 #include "scip/pub_misc.h"
38 #include "scip/struct_scip.h"
39 
40 #ifdef SCIP_DEBUG_SOLUTION
41 
42 #define SCIP_HASHSIZE_DEBUG 131101 /**< minimum size of hash map for storing whether a solution is valid for the node */
43 
44 static char** solnames = NULL;
45 static SCIP_Real* solvals = NULL;
46 static int nsolvals = 0;
47 static int solsize = 0;
48 static SCIP_SET* mainscipset = NULL;
49 static SCIP_SOL* debugsol = NULL;
50 static SCIP_STAGE debugsolstage = SCIP_STAGE_INIT;
51 static SCIP_HASHMAP* solinnode = NULL; /**< maps nodes to bools, storing whether the solution is valid for the node */
52 static SCIP_Bool falseptr = FALSE;
53 static SCIP_Bool trueptr = TRUE;
54 static SCIP_Bool solisachieved = FALSE; /**< means if current best solution is better than the given debug solution */
55 static SCIP_Real debugsolval = 0.0; /**< objective value for debug solution */
56 static SCIP_Bool debugsoldisabled = FALSE; /**< flag indicating if debugging of solution was disabled or not */
57 
58 
59 #ifdef SCIP_MORE_DEBUG
60 /** comparison method for sorting variables w.r.t. to their name */
61 static
62 SCIP_DECL_SORTPTRCOMP(sortVarsAfterNames)
63 {
64  return strcmp(SCIPvarGetName((SCIP_VAR*)elem1), SCIPvarGetName((SCIP_VAR*)elem2));
65 }
66 #endif
67 
68 /** returns whether the settings are the one of the SCIP instance that is debugged */
69 static
70 SCIP_Bool isMainscipset(
71  SCIP_SET* set /**< global SCIP settings */
72  )
73 {
74  return (mainscipset == NULL || mainscipset == set);
75 }
76 
77 /** reads solution from given file into given arrays */
78 static
79 SCIP_RETCODE readSolfile(
80  SCIP_SET* set, /**< global SCIP settings */
81  const char* solfilename, /**< solution filename to read */
82  char*** names, /**< pointer to store the array of variable names */
83  SCIP_Real** vals, /**< pointer to store the array of solution values */
84  int* nvals, /**< pointer to store the number of non-zero elements */
85  int* valssize /**< pointer to store the length of the variable names and solution values arrays */
86  )
87 {
88  SCIP_VAR** vars;
89  SCIP_Real* solvalues;
90  FILE* file;
91  int nonvalues;
92  int nfound;
93  int i;
94 
95  assert(set != NULL);
96  assert(solfilename != NULL);
97  assert(names != NULL);
98  assert(*names == NULL);
99  assert(vals != NULL);
100  assert(*vals == NULL);
101  assert(nvals != NULL);
102  assert(valssize != NULL);
103 
104  printf("***** debug: reading solution file <%s>\n", solfilename);
105 
106  /* open solution file */
107  file = fopen(solfilename, "r");
108  if( file == NULL )
109  {
110  SCIPerrorMessage("cannot open solution file <%s> specified in scip/debug.h\n", solfilename);
111  SCIPprintSysError(solfilename);
112  return SCIP_NOFILE;
113  }
114 
115  /* read data */
116  nonvalues = 0;
117  *valssize = 0;
118 
119  while( !feof(file) )
120  {
121  char buf[SCIP_MAXSTRLEN];
122  char name[SCIP_MAXSTRLEN];
123  char objstring[SCIP_MAXSTRLEN];
124  SCIP_Real val;
125  int nread;
126 
127  if( fgets(buf, SCIP_MAXSTRLEN, file) == NULL )
128  {
129  if( feof(file) )
130  break;
131  else
132  return SCIP_READERROR;
133  }
134 
135  /* the lines "solution status: ..." and "objective value: ..." may preceed the solution information */
136  if( strncmp(buf, "solution", 8) == 0 || strncmp(buf, "objective", 9) == 0 )
137  {
138  nonvalues++;
139  continue;
140  }
141 
142  /* skip empty lines */
143  if( strlen(buf) == 1 )
144  {
145  nonvalues++;
146  continue;
147  }
148 
149 
150  nread = sscanf(buf, "%s %lf %s\n", name, &val, objstring);
151  if( nread < 2 )
152  {
153  printf("invalid input line %d in solution file <%s>: <%s>\n", *nvals + nonvalues, SCIP_DEBUG_SOLUTION, name);
154  fclose(file);
155  return SCIP_READERROR;
156  }
157 
158  /* allocate memory */
159  if( *nvals >= *valssize )
160  {
161  *valssize = MAX(2 * *valssize, (*nvals)+1);
162  SCIP_ALLOC( BMSreallocMemoryArray(names, *valssize) );
163  SCIP_ALLOC( BMSreallocMemoryArray(vals, *valssize) );
164  }
165  assert(*nvals < *valssize);
166 
167  /* store solution value in sorted list */
168  for( i = *nvals; i > 0 && strcmp(name, (*names)[i-1]) < 0; --i )
169  {
170  (*names)[i] = (*names)[i-1];
171  (*vals)[i] = (*vals)[i-1];
172  }
173  SCIP_ALLOC( BMSduplicateMemoryArray(&(*names)[i], name, strlen(name)+1) );
174  SCIPdebugMessage("found variable <%s>: value <%g>\n", (*names)[i], val);
175  (*vals)[i] = val;
176  (*nvals)++;
177  }
178 
179  /* get memory for SCIP solution */
180  SCIP_ALLOC( BMSallocMemoryArray(&vars, *valssize) );
181  SCIP_ALLOC( BMSallocMemoryArray(&solvalues, *valssize) );
182 
183  debugsolval = 0.0;
184  nfound = 0;
185 
186  /* get solution value */
187  for( i = 0; i < *nvals; ++i)
188  {
189  SCIP_VAR* var;
190  var = SCIPfindVar(set->scip, (*names)[i]);
191  if( var != NULL )
192  {
193  vars[nfound] = var;
194  solvalues[nfound] = (*vals)[i];
195  ++nfound;
196  debugsolval += (*vals)[i] * SCIPvarGetObj(var);
197  }
198  }
199  SCIPdebugMessage("Debug Solution value is %g.\n", debugsolval);
200 
201 #ifdef SCIP_MORE_DEBUG
202  SCIPsortPtrReal((void**)vars, solvalues, sortVarsAfterNames, nfound);
203 
204  for( i = 0; i < nfound - 1; ++i)
205  {
206  assert(strcmp(SCIPvarGetName(vars[i]), SCIPvarGetName(vars[i + 1])) != 0);
207  }
208 #endif
209 
210  assert(debugsol == NULL);
211 
212  /* create SCIP solution */
213  SCIP_CALL( SCIPcreateOrigSol(set->scip, &debugsol, NULL) );
214  debugsolstage = SCIPgetStage(set->scip);
215 
216  /* set SCIP solution values */
217  SCIP_CALL( SCIPsetSolVals(set->scip, debugsol, nfound, vars, solvalues ) );
218 
219  BMSfreeMemoryArray(&vars);
220  BMSfreeMemoryArray(&solvalues);
221 
222  /* close file */
223  fclose(file);
224 
225  printf("***** debug: read %d non-zero entries (%d variables found)\n", *nvals, nfound);
226 
227  return SCIP_OKAY;
228 }
229 
230 /** reads feasible solution to check from file */
231 static
232 SCIP_RETCODE readSolution(
233  SCIP_SET* set /**< global SCIP settings */
234  )
235 {
236  assert(set != NULL);
237 
238  if( !isMainscipset(set) || nsolvals > 0 )
239  return SCIP_OKAY;
240 
241  SCIP_CALL( readSolfile(set, SCIP_DEBUG_SOLUTION, &solnames, &solvals, &nsolvals, &solsize) );
242 
243  return SCIP_OKAY;
244 }
245 
246 /** gets value of given variable in debugging solution */
247 static
248 SCIP_RETCODE getSolutionValue(
249  SCIP_SET* set, /**< global SCIP settings */
250  SCIP_VAR* var, /**< variable to get solution value for */
251  SCIP_Real* val /**< pointer to store solution value */
252  )
253 {
254  SCIP_VAR* solvar;
255  SCIP_Real scalar;
256  SCIP_Real constant;
257  const char* name;
258  int left;
259  int right;
260  int middle;
261  int cmp;
262 
263  assert(set != NULL);
264  assert(var != NULL);
265  assert(val != NULL);
266 
267  /* allow retrieving solution values only if referring to the SCIP instance that is debugged */
268  assert(isMainscipset(set));
269 
270  SCIP_CALL( readSolution(set) );
271  SCIPdebugMessage("Now handling variable <%s>, which has status %d, is of type %d, and was deleted: %d, negated: %d, transformed: %d\n",
272  SCIPvarGetName(var), SCIPvarGetStatus(var), SCIPvarGetType(var), SCIPvarIsDeleted(var), SCIPvarIsNegated(var),SCIPvarIsTransformedOrigvar(var));
273  /* ignore deleted variables */
274  if( SCIPvarIsDeleted(var) )
275  {
276  SCIPdebugMessage("**** unknown solution value for deleted variable <%s>\n", SCIPvarGetName(var));
277  *val = SCIP_UNKNOWN;
278  return SCIP_OKAY;
279  }
280  /* retransform variable onto original variable space */
281  solvar = var;
282  scalar = 1.0;
283  constant = 0.0;
284  if( SCIPvarIsNegated(solvar) )
285  {
286  scalar = -1.0;
287  constant = SCIPvarGetNegationConstant(solvar);
288  solvar = SCIPvarGetNegationVar(solvar);
289  }
290  if( SCIPvarIsTransformed(solvar) )
291  {
292  SCIP_CALL( SCIPvarGetOrigvarSum(&solvar, &scalar, &constant) );
293  if( solvar == NULL )
294  {
295  /* if no original counterpart, then maybe someone added a value for the transformed variable, so search for var (or its negation) */
296  SCIPdebugMessage("variable <%s> has no original counterpart\n", SCIPvarGetName(var));
297  solvar = var;
298  scalar = 1.0;
299  constant = 0.0;
300  if( SCIPvarIsNegated(solvar) )
301  {
302  scalar = -1.0;
303  constant = SCIPvarGetNegationConstant(solvar);
304  solvar = SCIPvarGetNegationVar(solvar);
305  }
306  }
307  }
308  /* perform a binary search for the variable */
309  name = SCIPvarGetName(solvar);
310  left = 0;
311  right = nsolvals-1;
312  while( left <= right )
313  {
314  middle = (left+right)/2;
315  cmp = strcmp(name, solnames[middle]);
316  if( cmp < 0 )
317  right = middle-1;
318  else if( cmp > 0 )
319  left = middle+1;
320  else
321  {
322  *val = scalar * solvals[middle] + constant;
323  return SCIP_OKAY;
324  }
325  }
326  *val = constant;
327 
328  if( *val < SCIPvarGetLbGlobal(var) - 1e-06 || *val > SCIPvarGetUbGlobal(var) + 1e-06 )
329  {
330  SCIPmessagePrintWarning(SCIPgetMessagehdlr(set->scip), "invalid solution value %.15g for variable <%s>[%.15g,%.15g]\n",
331  *val, SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var));
332  }
333 
334  return SCIP_OKAY;
335 }
336 
337 /** gets pointer to the debug solution */
338 SCIP_RETCODE SCIPdebugGetSol(
339  SCIP* scip, /**< SCIP data structure */
340  SCIP_SOL** sol /**< buffer to store pointer to the debug solution */
341  )
342 {
343  assert(scip != NULL);
344  assert(sol != NULL);
345 
346  SCIP_CALL( readSolution(scip->set) );
347  if( debugsol == NULL )
348  {
349  *sol = NULL;
350  return SCIP_ERROR;
351  }
352 
353  *sol = debugsol;
354  return SCIP_OKAY;
355 }
356 
357 /** gets value for a variable in the debug solution
358  *
359  * if no value is stored for the variable, gives 0.0
360  */
361 SCIP_RETCODE SCIPdebugGetSolVal(
362  SCIP* scip, /**< SCIP data structure */
363  SCIP_VAR* var, /**< variable for which to get the value */
364  SCIP_Real* val /**< buffer to store solution value */
365  )
366 {
367  SCIP_CALL( getSolutionValue(scip->set, var, val) );
368 
369  return SCIP_OKAY;
370 }
371 
372 /** returns whether the debug solution is worse as the best known solution or if the debug solution was found */
373 static
374 SCIP_Bool debugSolIsAchieved(
375  SCIP_SET* set /**< global SCIP settings */
376  )
377 {
378  SCIP_SOL* bestsol;
379  SCIP* scip;
380 
381  if( solisachieved )
382  return TRUE;
383 
384  assert(set != NULL);
385 
386  scip = set->scip;
387  assert(scip != NULL);
388 
389  bestsol = SCIPgetBestSol(scip);
390 
391  if( bestsol != NULL )
392  {
393  SCIP_Real solvalue;
394 
395  /* don't check solution while in problem creation stage */
396  if( SCIPsetGetStage(set) == SCIP_STAGE_PROBLEM )
397  return TRUE;
398 
399  solvalue = SCIPgetSolOrigObj(scip, bestsol);
400 
401  /* make sure a debug solution has been read, so we do not compare against the initial debugsolval == 0 */
402  SCIP_CALL( readSolution(set) );
403 
404  if( (SCIPgetObjsense(scip) == SCIP_OBJSENSE_MINIMIZE && SCIPsetIsLE(set, solvalue, debugsolval)) || (SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE && SCIPsetIsGE(set, solvalue, debugsolval)) )
405  solisachieved = TRUE;
406  }
407 
408  return solisachieved;
409 }
410 
411 /** returns whether the solution is contained in node's subproblem */
412 static
413 SCIP_RETCODE isSolutionInNode(
414  BMS_BLKMEM* blkmem, /**< block memory */
415  SCIP_SET* set, /**< global SCIP settings */
416  SCIP_NODE* node, /**< local node where this bound change was applied */
417  SCIP_Bool* solcontained /**< pointer to store whether the solution is contained in node's subproblem */
418  )
419 {
420  SCIP_Bool* boolptr;
421 
422  assert(set != NULL);
423  assert(blkmem != NULL);
424  assert(node != NULL);
425  assert(solcontained != NULL);
426 
427  /* check if we are in the original problem and not in a sub MIP */
428  if( !isMainscipset(set) )
429  {
430  *solcontained = FALSE;
431  return SCIP_OKAY;
432  }
433 
434  /* generate the hashmap */
435  if( solinnode == NULL )
436  {
437  SCIP_CALL( SCIPhashmapCreate(&solinnode, blkmem, SCIPcalcHashtableSize(SCIP_HASHSIZE_DEBUG)) );
438  }
439 
440  /* check, whether we know already whether the solution is contained in the given node */
441  boolptr = (SCIP_Bool*)SCIPhashmapGetImage(solinnode, (void*)node);
442  if( boolptr != NULL )
443  {
444  if( boolptr != &falseptr && boolptr != &trueptr )
445  {
446  SCIPerrorMessage("wrong value in node hashmap\n");
447  SCIPABORT();
448  return SCIP_ERROR;
449  }
450  *solcontained = *boolptr;
451  return SCIP_OKAY;
452  }
453 
454  /* if the solution is not contained in the parent of the node, it cannot be contained in the current node */
455  *solcontained = TRUE;
456  if( node->parent != NULL )
457  {
458  SCIP_CALL( isSolutionInNode(blkmem, set, node->parent, solcontained) );
459  }
460 
461  if( *solcontained )
462  {
463  /* check whether the bound changes at the current node remove the debugging solution from the subproblem */
464  if( node->domchg != NULL )
465  {
466  SCIP_DOMCHGBOUND* domchgbound;
467  SCIP_BOUNDCHG* boundchgs;
468  int i;
469 
470  domchgbound = &node->domchg->domchgbound;
471  boundchgs = domchgbound->boundchgs;
472  for( i = 0; i < (int)domchgbound->nboundchgs && *solcontained; ++i )
473  {
474  SCIP_Real varsol;
475 
476  /* get solution value of variable */
477  SCIP_CALL( getSolutionValue(set, boundchgs[i].var, &varsol) );
478 
479  if( varsol != SCIP_UNKNOWN ) /*lint !e777*/
480  {
481  /* compare the bound change with the solution value */
482  if( SCIPboundchgGetBoundtype(&boundchgs[i]) == SCIP_BOUNDTYPE_LOWER )
483  *solcontained = SCIPsetIsFeasGE(set, varsol, boundchgs[i].newbound);
484  else
485  *solcontained = SCIPsetIsFeasLE(set, varsol, boundchgs[i].newbound);
486 
487  if( !(*solcontained) && SCIPboundchgGetBoundchgtype(&boundchgs[i]) != SCIP_BOUNDCHGTYPE_BRANCHING )
488  {
489  SCIPerrorMessage("debugging solution was cut off in local node %p at depth %d by inference <%s>[%.15g] %s %.15g\n",
490  node, SCIPnodeGetDepth(node), SCIPvarGetName(boundchgs[i].var), varsol,
491  SCIPboundchgGetBoundtype(&boundchgs[i]) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", boundchgs[i].newbound);
492  SCIPABORT();
493  }
494  }
495  else if( SCIPboundchgGetBoundchgtype(&boundchgs[i]) == SCIP_BOUNDCHGTYPE_BRANCHING )
496  {
497  /* we branched on a variable were we don't know the solution: no debugging can be applied in this subtree */
498  *solcontained = FALSE;
499  }
500  }
501  }
502  }
503 
504  /* remember the status of the current node */
505  SCIP_CALL( SCIPhashmapSetImage(solinnode, (void*)node, *solcontained ? (void*)(&trueptr) : (void*)(&falseptr)) );
506 
507  return SCIP_OKAY;
508 }
509 
510 /** frees all debugging solution data*/
511 SCIP_RETCODE SCIPdebugFreeDebugData(
512  SCIP_SET* set /**< global SCIP settings */
513  )
514 {
515  int s;
516 
517  assert(set != NULL);
518 
519  /* check if we are in the original problem and not in a sub MIP */
520  if( !isMainscipset(set) )
521  return SCIP_OKAY;
522 
523  for( s = nsolvals - 1; s >= 0; --s )
524  BMSfreeMemoryArrayNull(&solnames[s]);
525 
526  BMSfreeMemoryArrayNull(&solnames);
527  BMSfreeMemoryArrayNull(&solvals);
528 
529  nsolvals = 0;
530  debugsolval = 0.0;
531  mainscipset = NULL;
532  solisachieved = FALSE;
533 
534  if( solinnode != NULL)
535  SCIPhashmapFree(&solinnode);
536 
537  if( debugsol != NULL && SCIPgetStage(set->scip) == debugsolstage )
538  {
539  SCIP_CALL( SCIPfreeSol(set->scip, &debugsol) );
540  }
541 
542  return SCIP_OKAY;
543 }
544 
545 /** checks for validity of the debugging solution in given constraints */
546 SCIP_RETCODE SCIPdebugCheckConss(
547  SCIP* scip, /**< SCIP data structure */
548  SCIP_CONS** conss, /**< constraints to check for validity */
549  int nconss /**< number of given constraints */
550  )
551 {
552  SCIP_RESULT result;
553  int c;
554 
555  assert(conss != NULL || nconss == 0);
556  assert(debugsol != NULL);
557 
558  /* when debugging was disabled the solution is not defined to be not valid in the current subtree */
559  if( debugsoldisabled )
560  return SCIP_OKAY;
561 
562  /* check if we are in the original problem and not in a sub MIP */
563  if( !isMainscipset(scip->set) )
564  return SCIP_OKAY;
565 
566  /* check if the incumbent solution is at least as good as the debug solution, so we can stop to check the debug
567  * solution
568  */
569  if( debugSolIsAchieved(scip->set) )
570  return SCIP_OKAY;
571 
572  assert(scip->set == mainscipset);
573 
574  result = SCIP_FEASIBLE;
575 
576  /* checking each given constraint against the debugging solution */
577  for( c = nconss - 1; c >= 0; --c )
578  {
579  assert(conss[c] != NULL);
580 
581  if( !SCIPconsIsActive(conss[c]) )
582  continue;
583 
584  assert(SCIPconsGetActiveDepth(conss[c]) <= SCIPgetDepth(scip));
585 
586  /* if the cons is only locally valid, check whether the debugging solution is contained in the local subproblem */
587  if( SCIPconsIsLocal(conss[c]) )
588  {
589  SCIP_Bool solcontained;
590 
591  SCIP_CALL( isSolutionInNode(SCIPblkmem(scip), scip->set, SCIPgetCurrentNode(scip), &solcontained) );
592  if( !solcontained )
593  return SCIP_OKAY;
594  }
595 
596  SCIP_CALL( SCIPcheckCons(scip, conss[c], debugsol, TRUE, TRUE, TRUE, &result) );
597 
598  SCIPdebugMessage(" -> checking of constraint %s returned result <%d>\n", SCIPconsGetName(conss[c]), result);
599 
600  if( result != SCIP_FEASIBLE )
601  {
602  SCIPerrorMessage("constraint %s violates the debugging solution\n", SCIPconsGetName(conss[c]));
603  SCIPABORT();
604  }
605  }
606 
607  return SCIP_OKAY;
608 }
609 
610 /** checks whether given row is valid for the debugging solution */
611 SCIP_RETCODE SCIPdebugCheckRow(
612  SCIP_SET* set, /**< global SCIP settings */
613  SCIP_ROW* row /**< row to check for validity */
614  )
615 {
616  SCIP_COL** cols;
617  SCIP_Real* vals;
618  SCIP_Real lhs;
619  SCIP_Real rhs;
620  int nnonz;
621  int i;
622  SCIP_Real minactivity;
623  SCIP_Real maxactivity;
624  SCIP_Real solval;
625 
626  assert(set != NULL);
627  assert(row != NULL);
628 
629  /* when debugging was disabled the solution is not defined to be not valid in the current subtree */
630  if( debugsoldisabled )
631  return SCIP_OKAY;
632 
633  /* check if we are in the original problem and not in a sub MIP */
634  if( !isMainscipset(set) )
635  return SCIP_OKAY;
636 
637  /* check if the incumbent solution is at least as good as the debug solution, so we can stop to check the debug solution */
638  if( debugSolIsAchieved(set) )
639  return SCIP_OKAY;
640 
641  /* if the row is only locally valid, check whether the debugging solution is contained in the local subproblem */
642  if( SCIProwIsLocal(row) )
643  {
644  SCIP_Bool solcontained;
645 
646  SCIP_CALL( isSolutionInNode(SCIPblkmem(set->scip), set, SCIPgetCurrentNode(set->scip), &solcontained) );
647  if( !solcontained )
648  return SCIP_OKAY;
649  }
650 
651  cols = SCIProwGetCols(row);
652  vals = SCIProwGetVals(row);
653  nnonz = SCIProwGetNNonz(row);
654  lhs = SCIProwGetLhs(row);
655  rhs = SCIProwGetRhs(row);
656 
657  /* calculate row's activity on debugging solution */
658  minactivity = SCIProwGetConstant(row);
659  maxactivity = minactivity;
660  for( i = 0; i < nnonz; ++i )
661  {
662  SCIP_VAR* var;
663 
664  /* get solution value of variable in debugging solution */
665  var = SCIPcolGetVar(cols[i]);
666  SCIP_CALL( getSolutionValue(set, var, &solval) );
667 
668  if( solval != SCIP_UNKNOWN ) /*lint !e777*/
669  {
670  minactivity += vals[i] * solval;
671  maxactivity += vals[i] * solval;
672  }
673  else if( vals[i] > 0.0 )
674  {
675  minactivity += vals[i] * SCIPvarGetLbGlobal(var);
676  maxactivity += vals[i] * SCIPvarGetUbGlobal(var);
677  }
678  else if( vals[i] < 0.0 )
679  {
680  minactivity += vals[i] * SCIPvarGetUbGlobal(var);
681  maxactivity += vals[i] * SCIPvarGetLbGlobal(var);
682  }
683  }
684  SCIPdebugMessage("debugging solution on row <%s>: %g <= [%g,%g] <= %g\n",
685  SCIProwGetName(row), lhs, minactivity, maxactivity, rhs);
686 
687  /* check row for violation */
688  if( SCIPsetIsFeasLT(set, maxactivity, lhs) || SCIPsetIsFeasGT(set, minactivity, rhs) )
689  {
690  printf("***** debug: row <%s> violates debugging solution (lhs=%.15g, rhs=%.15g, activity=[%.15g,%.15g], local=%d)\n",
691  SCIProwGetName(row), lhs, rhs, minactivity, maxactivity, SCIProwIsLocal(row));
692  SCIProwPrint(row, SCIPgetMessagehdlr(set->scip), NULL);
693 
694  /* output row with solution values */
695  printf("\n\n");
696  printf("***** debug: violated row <%s>:\n", SCIProwGetName(row));
697  printf(" %.15g <= %.15g", lhs, SCIProwGetConstant(row));
698  for( i = 0; i < nnonz; ++i )
699  {
700  /* get solution value of variable in debugging solution */
701  SCIP_CALL( getSolutionValue(set, SCIPcolGetVar(cols[i]), &solval) );
702  printf(" %+.15g<%s>[%.15g]", vals[i], SCIPvarGetName(SCIPcolGetVar(cols[i])), solval);
703  }
704  printf(" <= %.15g\n", rhs);
705 
706  SCIPABORT();
707  }
708 
709  return SCIP_OKAY;
710 }
711 
712 /** checks whether given global lower bound is valid for the debugging solution */
713 SCIP_RETCODE SCIPdebugCheckLbGlobal(
714  SCIP* scip, /**< SCIP data structure */
715  SCIP_VAR* var, /**< problem variable */
716  SCIP_Real lb /**< lower bound */
717  )
718 {
719  SCIP_Real varsol;
720 
721  assert(scip != NULL);
722  assert(var != NULL);
723 
724  /* when debugging was disabled the solution is not defined to be not valid in the current subtree */
725  if( debugsoldisabled )
726  return SCIP_OKAY;
727 
728  /* check if we are in the original problem and not in a sub MIP */
729  if( !isMainscipset(scip->set) )
730  return SCIP_OKAY;
731 
732  /* check if the incumbent solution is at least as good as the debug solution, so we can stop to check the debug solution */
733  if( debugSolIsAchieved(scip->set) )
734  return SCIP_OKAY;
735 
736  /* get solution value of variable */
737  SCIP_CALL( getSolutionValue(scip->set, var, &varsol) );
738  SCIPdebugMessage("debugging solution on lower bound of <%s>[%g] >= %g\n", SCIPvarGetName(var), varsol, lb);
739 
740  /* check validity of debugging solution */
741  if( varsol != SCIP_UNKNOWN && SCIPisFeasLT(scip, varsol, lb) ) /*lint !e777*/
742  {
743  SCIPerrorMessage("invalid global lower bound: <%s>[%.15g] >= %.15g\n", SCIPvarGetName(var), varsol, lb);
744  SCIPABORT();
745  }
746 
747  return SCIP_OKAY;
748 }
749 
750 /** checks whether given global upper bound is valid for the debugging solution */
751 SCIP_RETCODE SCIPdebugCheckUbGlobal(
752  SCIP* scip, /**< SCIP data structure */
753  SCIP_VAR* var, /**< problem variable */
754  SCIP_Real ub /**< upper bound */
755  )
756 {
757  SCIP_Real varsol;
758 
759  assert(scip != NULL);
760  assert(var != NULL);
761 
762  /* when debugging was disabled the solution is not defined to be not valid in the current subtree */
763  if( debugsoldisabled )
764  return SCIP_OKAY;
765 
766  /* check if we are in the original problem and not in a sub MIP */
767  if( !isMainscipset(scip->set) )
768  return SCIP_OKAY;
769 
770  /* check if the incumbent solution is at least as good as the debug solution, so we can stop to check the debug solution */
771  if( debugSolIsAchieved(scip->set) )
772  return SCIP_OKAY;
773 
774  /* get solution value of variable */
775  SCIP_CALL( getSolutionValue(scip->set, var, &varsol) );
776  SCIPdebugMessage("debugging solution on upper bound of <%s>[%g] <= %g\n", SCIPvarGetName(var), varsol, ub);
777 
778  /* check validity of debugging solution */
779  if( varsol != SCIP_UNKNOWN && SCIPisFeasGT(scip, varsol, ub) ) /*lint !e777*/
780  {
781  SCIPerrorMessage("invalid global upper bound: <%s>[%.15g] <= %.15g\n", SCIPvarGetName(var), varsol, ub);
782  SCIPABORT();
783  }
784 
785  return SCIP_OKAY;
786 }
787 
788 /** checks whether given local bound implication is valid for the debugging solution */
789 SCIP_RETCODE SCIPdebugCheckInference(
790  BMS_BLKMEM* blkmem, /**< block memory */
791  SCIP_SET* set, /**< global SCIP settings */
792  SCIP_NODE* node, /**< local node where this bound change was applied */
793  SCIP_VAR* var, /**< problem variable */
794  SCIP_Real newbound, /**< new value for bound */
795  SCIP_BOUNDTYPE boundtype /**< type of bound: lower or upper bound */
796  )
797 {
798  SCIP_Real varsol;
799  SCIP_Bool solcontained;
800 
801  assert(set != NULL);
802  assert(blkmem != NULL);
803  assert(node != NULL);
804  assert(var != NULL);
805 
806  /* when debugging was disabled the solution is not defined to be not valid in the current subtree */
807  if( debugsoldisabled )
808  return SCIP_OKAY;
809 
810  /* in case we are in probing or diving we have to avoid checking the solution */
811  if( SCIPlpDiving(set->scip->lp) || SCIPtreeProbing(set->scip->tree) )
812  return SCIP_OKAY;
813 
814  /* check if we are in the original problem and not in a sub MIP */
815  if( !isMainscipset(set) )
816  return SCIP_OKAY;
817 
818  /* check if the incumbent solution is at least as good as the debug solution, so we can stop to check the debug solution */
819  if( debugSolIsAchieved(set) )
820  return SCIP_OKAY;
821 
822  /* check whether the debugging solution is contained in the local subproblem */
823  SCIP_CALL( isSolutionInNode(blkmem, set, node, &solcontained) );
824  if( !solcontained )
825  return SCIP_OKAY;
826 
827  /* get solution value of variable */
828  SCIP_CALL( getSolutionValue(set, var, &varsol) );
829 
830  /* check validity of debugging solution */
831  if( varsol != SCIP_UNKNOWN ) /*lint !e777*/
832  {
833  if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasLT(set, varsol, newbound) )
834  {
835  SCIPerrorMessage("invalid local lower bound implication: <%s>[%.15g] >= %.15g\n", SCIPvarGetName(var), varsol, newbound);
836  SCIPABORT();
837  }
838  if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasGT(set, varsol, newbound) )
839  {
840  SCIPerrorMessage("invalid local upper bound implication: <%s>[%.15g] <= %.15g\n", SCIPvarGetName(var), varsol, newbound);
841  SCIPABORT();
842  }
843  }
844 
845  return SCIP_OKAY;
846 }
847 
848 /** informs solution debugger, that the given node will be freed */
849 SCIP_RETCODE SCIPdebugRemoveNode(
850  BMS_BLKMEM* blkmem, /**< block memory */
851  SCIP_SET* set, /**< global SCIP settings */
852  SCIP_NODE* node /**< node that will be freed */
853  )
854 {
855  assert(set != NULL);
856  assert(blkmem != NULL);
857  assert(node != NULL);
858 
859  /* when debugging was disabled the solution is not defined to be not valid in the current subtree */
860  if( debugsoldisabled )
861  return SCIP_OKAY;
862 
863  /* check if we are in the original problem and not in a sub MIP */
864  if( !isMainscipset(set) )
865  return SCIP_OKAY;
866 
867  /* check if the incumbent solution is at least as good as the debug solution, so we can stop to check the debug solution */
868  if( debugSolIsAchieved(set) )
869  return SCIP_OKAY;
870 
871  /* check if a solution will be cutoff in tree */
872  if( SCIPgetStage(set->scip) != SCIP_STAGE_EXITSOLVE && SCIPgetStage(set->scip) != SCIP_STAGE_EXITPRESOLVE && SCIPnodeGetType(node) != SCIP_NODETYPE_PROBINGNODE )
873  {
874  SCIP_Bool solisinnode;
875 
876  solisinnode = FALSE;
877 
878  SCIP_CALL( isSolutionInNode(blkmem, set, node, &solisinnode) );
879  /* wrong node will be cutoff */
880  if( solisinnode )
881  {
882  SCIPerrorMessage("debugging solution was cut off in local node #%"SCIP_LONGINT_FORMAT" (%p) at depth %d\n",
883  node->number, node, SCIPnodeGetDepth(node));
884  SCIPABORT();
885  }
886  }
887 
888  /* remove node from the hash map */
889  if( solinnode != NULL )
890  {
891  SCIP_CALL( SCIPhashmapRemove(solinnode, (void*)node) );
892  }
893 
894  return SCIP_OKAY;
895 }
896 
897 /** checks whether given variable bound is valid for the debugging solution */
898 SCIP_RETCODE SCIPdebugCheckVbound(
899  SCIP_SET* set, /**< global SCIP settings */
900  SCIP_VAR* var, /**< problem variable x in x <= b*z + d or x >= b*z + d */
901  SCIP_BOUNDTYPE vbtype, /**< type of variable bound (LOWER or UPPER) */
902  SCIP_VAR* vbvar, /**< variable z in x <= b*z + d or x >= b*z + d */
903  SCIP_Real vbcoef, /**< coefficient b in x <= b*z + d or x >= b*z + d */
904  SCIP_Real vbconstant /**< constant d in x <= b*z + d or x >= b*z + d */
905  )
906 {
907  SCIP_Real varsol;
908  SCIP_Real vbvarsol;
909  SCIP_Real vb;
910 
911  assert(set != NULL);
912  assert(var != NULL);
913 
914  /* when debugging was disabled the solution is not defined to be not valid in the current subtree */
915  if( debugsoldisabled )
916  return SCIP_OKAY;
917 
918  /* check if we are in the original problem and not in a sub MIP */
919  if( !isMainscipset(set) )
920  return SCIP_OKAY;
921 
922  /* check if the incumbent solution is at least as good as the debug solution, so we can stop to check the debug solution */
923  if( debugSolIsAchieved(set) )
924  return SCIP_OKAY;
925 
926  /* get solution value of variables */
927  SCIP_CALL( getSolutionValue(set, var, &varsol) );
928  SCIP_CALL( getSolutionValue(set, vbvar, &vbvarsol) );
929 
930  /* check validity of debugging solution */
931  if( varsol != SCIP_UNKNOWN && vbvarsol != SCIP_UNKNOWN ) /*lint !e777*/
932  {
933  vb = vbcoef * vbvarsol + vbconstant;
934  if( (vbtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasLT(set, varsol, vb))
935  || (vbtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasGT(set, varsol, vb)) )
936  {
937  SCIPerrorMessage("invalid variable bound: <%s>[%.15g] %s %.15g<%s>[%.15g] %+.15g\n",
938  SCIPvarGetName(var), varsol, vbtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", vbcoef,
939  SCIPvarGetName(vbvar), vbvarsol, vbconstant);
940  SCIPABORT();
941  }
942  }
943 
944  return SCIP_OKAY;
945 }
946 
947 /** checks whether given implication is valid for the debugging solution */
948 SCIP_RETCODE SCIPdebugCheckImplic(
949  SCIP_SET* set, /**< global SCIP settings */
950  SCIP_VAR* var, /**< problem variable */
951  SCIP_Bool varfixing, /**< FALSE if y should be added in implications for x == 0, TRUE for x == 1 */
952  SCIP_VAR* implvar, /**< variable y in implication y <= b or y >= b */
953  SCIP_BOUNDTYPE impltype, /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */
954  SCIP_Real implbound /**< bound b in implication y <= b or y >= b */
955  )
956 {
957  SCIP_Real solval;
958 
959  assert(set != NULL);
960  assert(var != NULL);
961  assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY);
962 
963  /* when debugging was disabled the solution is not defined to be not valid in the current subtree */
964  if( debugsoldisabled )
965  return SCIP_OKAY;
966 
967  /* check if we are in the original problem and not in a sub MIP */
968  if( !isMainscipset(set) )
969  return SCIP_OKAY;
970 
971  /* check if the incumbent solution is at least as good as the debug solution, so we can stop to check the debug solution */
972  if( debugSolIsAchieved(set) )
973  return SCIP_OKAY;
974 
975  /* get solution value of variable */
976  SCIP_CALL( getSolutionValue(set, var, &solval) );
977  if( solval == SCIP_UNKNOWN ) /*lint !e777*/
978  return SCIP_OKAY;
979  assert(SCIPsetIsFeasZero(set, solval) || SCIPsetIsFeasEQ(set, solval, 1.0));
980 
981  /* check, whether the implication applies for the debugging solution */
982  if( (solval > 0.5) != varfixing )
983  return SCIP_OKAY;
984 
985  /* get solution value of implied variable */
986  SCIP_CALL( getSolutionValue(set, implvar, &solval) );
987  if( solval == SCIP_UNKNOWN ) /*lint !e777*/
988  return SCIP_OKAY;
989 
990  if( impltype == SCIP_BOUNDTYPE_LOWER )
991  {
992  if( SCIPsetIsFeasLT(set, solval, implbound) )
993  {
994  SCIPerrorMessage("invalid implication <%s> == %d -> <%s> >= %.15g (variable has value %.15g in solution)\n",
995  SCIPvarGetName(var), varfixing, SCIPvarGetName(implvar), implbound, solval);
996  SCIPABORT();
997  }
998  }
999  else
1000  {
1001  if( SCIPsetIsFeasGT(set, solval, implbound) )
1002  {
1003  SCIPerrorMessage("invalid implication <%s> == %d -> <%s> <= %.15g (variable has value %.15g in solution)\n",
1004  SCIPvarGetName(var), varfixing, SCIPvarGetName(implvar), implbound, solval);
1005  SCIPABORT();
1006  }
1007  }
1008 
1009  return SCIP_OKAY;
1010 }
1011 
1012 /** check whether given clique is valid for the debugging solution */
1013 SCIP_RETCODE SCIPdebugCheckClique(
1014  SCIP_SET* set, /**< global SCIP settings */
1015  SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given value */
1016  SCIP_Bool* values, /**< values of the variables in the clique; NULL to use TRUE for all vars */
1017  int nvars /**< number of variables in the clique */
1018  )
1019 {
1020  SCIP_Real solval;
1021  int pos1;
1022  int pos2;
1023  int v;
1024 
1025  assert(set != NULL);
1026  assert(vars != NULL);
1027 
1028  /* when debugging was disabled the solution is not defined to be not valid in the current subtree */
1029  if( debugsoldisabled )
1030  return SCIP_OKAY;
1031 
1032  /* check if we are in the original problem and not in a sub MIP */
1033  if( !isMainscipset(set) )
1034  return SCIP_OKAY;
1035 
1036  /* check if the incumbent solution is at least as good as the debug solution, so we can stop to check the debug solution */
1037  if( debugSolIsAchieved(set) )
1038  return SCIP_OKAY;
1039 
1040  pos1 = -1;
1041  pos2 = -1;
1042 
1043  for( v = 0; v < nvars; ++v )
1044  {
1045  assert(vars[v] != NULL);
1046  assert(SCIPvarIsBinary(vars[v]));
1047 
1048  /* get solution value of variable */
1049  SCIP_CALL( getSolutionValue(set, vars[v], &solval) );
1050 
1051  if( solval == SCIP_UNKNOWN ) /*lint !e777*/
1052  continue;
1053 
1054  assert(SCIPsetIsFeasZero(set, solval) || SCIPsetIsFeasEQ(set, solval, 1.0));
1055 
1056  /* negated solution value if negated variable is in clique */
1057  if( values != NULL && values[v] == 0 )
1058  solval = 1.0 - solval;
1059 
1060  if( SCIPsetIsFeasEQ(set, solval, 1.0) )
1061  {
1062  if( pos1 == -1 )
1063  pos1 = v;
1064  else
1065  {
1066  assert(pos2 == -1);
1067  pos2 = v;
1068  break;
1069  }
1070  }
1071  }
1072 
1073  /* print debug message if the clique violates the debugging solution */
1074  if( pos2 != -1 )
1075  {
1076  assert(pos1 != -1);
1077  SCIPerrorMessage("clique violates debugging solution, (at least) variable <%s%s> and variable <%s%s> are both one in the debugging solution\n",
1078  (values == NULL || values[pos1]) ? "" : "~", SCIPvarGetName(vars[pos1]), (values == NULL || values[pos2]) ? "" : "~", SCIPvarGetName(vars[pos2]));
1079  SCIPABORT();
1080  }
1081 
1082  return SCIP_OKAY;
1083 }
1084 
1085 /** check, whether at least one literals is TRUE in the debugging solution */
1086 static
1087 SCIP_Bool debugCheckBdchginfos(
1088  SCIP_SET* set, /**< global SCIP settings */
1089  SCIP_BDCHGINFO** bdchginfos, /**< bound change informations of the conflict set */
1090  SCIP_Real* relaxedbds, /**< array with relaxed bounds which are efficient to create a valid conflict, or NULL */
1091  int nbdchginfos /**< number of bound changes in the conflict set */
1092  )
1093 {
1094  SCIP_Real solval;
1095  int i;
1096 
1097  /* check, whether at least one literals is TRUE in the debugging solution */
1098  for( i = 0; i < nbdchginfos; ++i )
1099  {
1100  SCIP_BDCHGINFO* bdchginfo;
1101  SCIP_VAR* var;
1102  SCIP_Real newbound;
1103 
1104  bdchginfo = bdchginfos[i];
1105  assert(bdchginfo != NULL);
1106 
1107  var = SCIPbdchginfoGetVar(bdchginfo);
1108  assert(var != NULL);
1109 
1110  if( relaxedbds != NULL )
1111  newbound = relaxedbds[i];
1112  else
1113  newbound = SCIPbdchginfoGetNewbound(bdchginfo);
1114 
1115  SCIP_CALL( getSolutionValue(set, var, &solval) );
1116 
1117  if( solval == SCIP_UNKNOWN ) /*lint !e777*/
1118  return TRUE;
1119 
1120  if( SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER )
1121  {
1122  assert(SCIPsetIsLE(set, newbound, SCIPbdchginfoGetNewbound(bdchginfo)));
1123 
1124  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
1125  {
1126  if( SCIPsetIsLE(set, solval, newbound) )
1127  return TRUE;
1128  }
1129  else
1130  {
1131  if( SCIPsetIsLT(set, solval, newbound) )
1132  return TRUE;
1133  }
1134  }
1135  else
1136  {
1137  assert(SCIPsetIsGE(set, newbound, SCIPbdchginfoGetNewbound(bdchginfo)));
1138 
1139  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
1140  {
1141  if( SCIPsetIsGE(set, solval, newbound) )
1142  return TRUE;
1143  }
1144  else
1145  {
1146  if( SCIPsetIsGT(set, solval, newbound) )
1147  return TRUE;
1148  }
1149  }
1150  }
1151 
1152  return FALSE;
1153 }
1154 
1155 /** print bound change information */
1156 static
1157 SCIP_RETCODE printBdchginfo(
1158  SCIP_SET* set, /**< global SCIP settings */
1159  SCIP_BDCHGINFO * bdchginfo, /**< bound change information */
1160  SCIP_Real relaxedbd /**< array with relaxed bounds which are efficient to create a valid conflict, or NULL */
1161  )
1162 {
1163  SCIP_Real solval;
1164 
1165  /* get solution value within the debug solution */
1166  SCIP_CALL( getSolutionValue(set, SCIPbdchginfoGetVar(bdchginfo), &solval) );
1167 
1168  printf(" <%s>[%.15g] %s %g(%g)", SCIPvarGetName(SCIPbdchginfoGetVar(bdchginfo)), solval,
1169  SCIPbdchginfoGetBoundtype(bdchginfo) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
1170  SCIPbdchginfoGetNewbound(bdchginfo), relaxedbd);
1171 
1172  return SCIP_OKAY;
1173 }
1174 
1175 
1176 /** print bound change information */
1177 static
1178 SCIP_RETCODE printBdchginfos(
1179  SCIP_SET* set, /**< global SCIP settings */
1180  SCIP_BDCHGINFO** bdchginfos, /**< bound change information array */
1181  SCIP_Real* relaxedbds, /**< array with relaxed bounds which are efficient to create a valid conflict, or NULL */
1182  int nbdchginfos /**< number of bound changes in the conflict set */
1183  )
1184 {
1185  int i;
1186 
1187  for( i = 0; i < nbdchginfos; ++i )
1188  {
1189  SCIP_BDCHGINFO* bdchginfo;
1190 
1191  bdchginfo = bdchginfos[i];
1192  assert(bdchginfo != NULL);
1193 
1194  printBdchginfo(set, bdchginfo, relaxedbds != NULL ? relaxedbds[i] : SCIPbdchginfoGetNewbound(bdchginfo));
1195  }
1196 
1197  return SCIP_OKAY;
1198 }
1199 
1200 /** checks whether given conflict is valid for the debugging solution */
1201 SCIP_RETCODE SCIPdebugCheckConflict(
1202  BMS_BLKMEM* blkmem, /**< block memory */
1203  SCIP_SET* set, /**< global SCIP settings */
1204  SCIP_NODE* node, /**< node where the conflict clause is added */
1205  SCIP_BDCHGINFO** bdchginfos, /**< bound change informations of the conflict set */
1206  SCIP_Real* relaxedbds, /**< array with relaxed bounds which are efficient to create a valid conflict */
1207  int nbdchginfos /**< number of bound changes in the conflict set */
1208  )
1209 {
1210  SCIP_Bool solcontained;
1211 
1212  assert(set != NULL);
1213  assert(blkmem != NULL);
1214  assert(node != NULL);
1215  assert(nbdchginfos == 0 || bdchginfos != NULL);
1216 
1217  /* when debugging was disabled the solution is not defined to be not valid in the current subtree */
1218  if( debugsoldisabled )
1219  return SCIP_OKAY;
1220 
1221  /* check if we are in the original problem and not in a sub MIP */
1222  if( !isMainscipset(set) )
1223  return SCIP_OKAY;
1224 
1225  /* check if the incumbent solution is at least as good as the debug solution, so we can stop to check the debug solution */
1226  if( debugSolIsAchieved(set) )
1227  return SCIP_OKAY;
1228 
1229  /* check whether the debugging solution is contained in the local subproblem */
1230  SCIP_CALL( isSolutionInNode(blkmem, set, node, &solcontained) );
1231  if( !solcontained )
1232  return SCIP_OKAY;
1233 
1234  /* check, whether at least one literals is TRUE in the debugging solution */
1235  if( debugCheckBdchginfos(set, bdchginfos, relaxedbds, nbdchginfos) )
1236  return SCIP_OKAY;
1237 
1238  SCIPerrorMessage("invalid conflict set:");
1239 
1240  /* print bound changes which are already part of the conflict set */
1241  SCIP_CALL( printBdchginfos(set, bdchginfos, relaxedbds, nbdchginfos) );
1242 
1243  printf("\n");
1244  SCIPABORT();
1245 
1246  return SCIP_OKAY; /*lint !e527*/
1247 }
1248 
1249 /** checks whether given conflict graph frontier is valid for the debugging solution */
1250 SCIP_RETCODE SCIPdebugCheckConflictFrontier(
1251  BMS_BLKMEM* blkmem, /**< block memory */
1252  SCIP_SET* set, /**< global SCIP settings */
1253  SCIP_NODE* node, /**< node where the conflict clause is added */
1254  SCIP_BDCHGINFO* bdchginfo, /**< bound change info which got resolved, or NULL */
1255  SCIP_BDCHGINFO** bdchginfos, /**< bound change informations of the conflict set */
1256  SCIP_Real* relaxedbds, /**< array with relaxed bounds which are efficient to create a valid conflict */
1257  int nbdchginfos, /**< number of bound changes in the conflict set */
1258  SCIP_PQUEUE* bdchgqueue, /**< unprocessed conflict bound changes */
1259  SCIP_PQUEUE* forcedbdchgqueue /**< unprocessed conflict bound changes that must be resolved */
1260  )
1261 {
1262  SCIP_BDCHGINFO** bdchgqueued;
1263  SCIP_BDCHGINFO** forcedbdchgqueued;
1264  SCIP_Bool solcontained;
1265  int nbdchgqueued;
1266  int nforcedbdchgqueued;
1267 
1268  assert(set != NULL);
1269  assert(blkmem != NULL);
1270  assert(node != NULL);
1271  assert(nbdchginfos == 0 || bdchginfos != NULL);
1272 
1273  /* when debugging was disabled the solution is not defined to be not valid in the current subtree */
1274  if( debugsoldisabled )
1275  return SCIP_OKAY;
1276 
1277  /* check if we are in the original problem and not in a sub MIP */
1278  if( !isMainscipset(set) )
1279  return SCIP_OKAY;
1280 
1281  /* check if the incumbent solution is at least as good as the debug solution, so we can stop to check the debug solution */
1282  if( debugSolIsAchieved(set) )
1283  return SCIP_OKAY;
1284 
1285  /* check whether the debugging solution is contained in the local subproblem */
1286  SCIP_CALL( isSolutionInNode(blkmem, set, node, &solcontained) );
1287  if( !solcontained )
1288  return SCIP_OKAY;
1289 
1290  /* check, whether one literals is TRUE in the debugging solution */
1291  if( debugCheckBdchginfos(set, bdchginfos, relaxedbds, nbdchginfos) )
1292  return SCIP_OKAY;
1293 
1294  /* get the elements of the bound change queue */
1295  bdchgqueued = (SCIP_BDCHGINFO**)SCIPpqueueElems(bdchgqueue);
1296  nbdchgqueued = SCIPpqueueNElems(bdchgqueue);
1297 
1298  /* check, whether one literals is TRUE in the debugging solution */
1299  if( debugCheckBdchginfos(set, bdchgqueued, NULL, nbdchgqueued) )
1300  return SCIP_OKAY;
1301 
1302  /* get the elements of the bound change queue */
1303  forcedbdchgqueued = (SCIP_BDCHGINFO**)SCIPpqueueElems(forcedbdchgqueue);
1304  nforcedbdchgqueued = SCIPpqueueNElems(forcedbdchgqueue);
1305 
1306  /* check, whether one literals is TRUE in the debugging solution */
1307  if( debugCheckBdchginfos(set, forcedbdchgqueued, NULL, nforcedbdchgqueued) )
1308  return SCIP_OKAY;
1309 
1310  SCIPerrorMessage("invalid conflict frontier:");
1311 
1312  if( bdchginfo != NULL )
1313  {
1314  printBdchginfo(set, bdchginfo, SCIPbdchginfoGetNewbound(bdchginfo));
1315  printf(" ");
1316  }
1317 
1318  /* print bound changes which are already part of the conflict set */
1319  SCIP_CALL( printBdchginfos(set, bdchginfos, relaxedbds, nbdchginfos) );
1320 
1321  /* print bound changes which are queued */
1322  SCIP_CALL( printBdchginfos(set, bdchgqueued, NULL, nbdchgqueued) );
1323 
1324  /* print bound changes which are queued in the force queue */
1325  SCIP_CALL( printBdchginfos(set, forcedbdchgqueued, NULL, nforcedbdchgqueued) );
1326 
1327  printf("\n");
1328  SCIPABORT();
1329 
1330  return SCIP_OKAY; /*lint !e527*/
1331 }
1332 
1333 /** check whether the debugging solution is valid in the current node */
1334 SCIP_RETCODE SCIPdebugSolIsValidInSubtree(
1335  SCIP* scip, /**< SCIP data structure */
1336  SCIP_Bool* isvalidinsubtree /**< pointer to store whether the solution is valid in the current
1337  * subtree
1338  */
1339  )
1340 {
1341  SCIP_Bool solcontained;
1342 
1343  *isvalidinsubtree = FALSE;
1344 
1345  /* when debugging was disabled the solution is not defined to be not valid in the current subtree */
1346  if( debugsoldisabled )
1347  return SCIP_OKAY;
1348 
1349  /* check if we are in the original problem and not in a sub MIP */
1350  if( !isMainscipset(scip->set) )
1351  return SCIP_OKAY;
1352 
1353  /* check if the incumbent solution is at least as good as the debug solution, so we can stop to check the debug solution */
1354  if( debugSolIsAchieved(scip->set) )
1355  return SCIP_OKAY;
1356 
1357  /* check whether the debugging solution is contained in the local subproblem */
1358  SCIP_CALL( isSolutionInNode(SCIPblkmem(scip), scip->set, SCIPgetCurrentNode(scip), &solcontained) );
1359 
1360  if( solcontained )
1361  *isvalidinsubtree = TRUE;
1362 
1363  return SCIP_OKAY;
1364 }
1365 
1366 /** set the main SCIP settings pointer */
1367 void SCIPdebugSetMainscipset(
1368  SCIP_SET* set /**< settings of SCIP instance */
1369  )
1370 {
1371  assert(set != NULL);
1372 
1373  if( mainscipset == NULL )
1374  mainscipset = set;
1375 }
1376 
1377 /** checks whether SCIP data structure is the main SCIP (the one for which debugging is enabled) */
1378 SCIP_Bool SCIPdebugIsMainscip(
1379  SCIP* scip /**< SCIP data structure */
1380  )
1381 {
1382  assert(scip != NULL);
1383 
1384  return isMainscipset(scip->set);
1385 }
1386 
1387 /** enabling solution debugging mechanism */
1388 void SCIPdebugSolEnable(
1389  SCIP* scip /**< SCIP data structure */
1390  )
1391 {
1392  debugsoldisabled = FALSE;
1393 }
1394 
1395 /** disabling solution debugging mechanism */
1396 void SCIPdebugSolDisable(
1397  SCIP* scip /**< SCIP data structure */
1398  )
1399 {
1400  debugsoldisabled = TRUE;
1401 }
1402 
1403 /** check if solution debugging mechanism is enabled */
1404 SCIP_Bool SCIPdebugSolIsEnabled(
1405  SCIP* scip /**< SCIP data structure */
1406  )
1407 {
1408  return (!debugsoldisabled);
1409 }
1410 
1411 /** propagator to force finding the debugging solution */
1412 static
1413 SCIP_DECL_PROPEXEC(propExecDebug)
1414 { /*lint --e{715}*/
1415  SCIP_VAR** vars;
1416  int nvars;
1417  int i;
1418 
1419  assert(scip != NULL);
1420  assert(result != NULL);
1421 
1422  *result = SCIP_DIDNOTFIND;
1423 
1424  /* check if we are in the original problem and not in a sub MIP */
1425  if( !isMainscipset(scip->set) )
1426  return SCIP_OKAY;
1427 
1428  if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING )
1429  return SCIP_OKAY;
1430 
1431  /* check if the incumbent solution is at least as good as the debug solution, so we can stop to check the debug solution */
1432  if( debugSolIsAchieved(scip->set) )
1433  return SCIP_OKAY;
1434 
1435 #if 1
1436  /* solve at least one LP */
1437  if( SCIPgetNLPIterations(scip) == 0 )
1438  return SCIP_OKAY;
1439 #endif
1440 
1441  vars = SCIPgetOrigVars(scip);
1442  nvars = SCIPgetNOrigVars(scip);
1443  for( i = 0; i < nvars; ++i )
1444  {
1445  SCIP_Real solval;
1446  SCIP_Real lb;
1447  SCIP_Real ub;
1448  SCIP_Bool infeasible;
1449  SCIP_Bool fixed;
1450 
1451  SCIP_CALL( getSolutionValue(scip->set, vars[i], &solval) );
1452  if( solval == SCIP_UNKNOWN ) /*lint !e777*/
1453  {
1454  SCIPerrorMessage("original variable without debugging solution value\n");
1455  SCIPABORT();
1456  }
1457 
1458  lb = SCIPvarGetLbGlobal(vars[i]);
1459  ub = SCIPvarGetUbGlobal(vars[i]);
1460  if( SCIPisLT(scip, solval, lb) || SCIPisGT(scip, solval, ub) )
1461  {
1462  SCIPerrorMessage("solution value %.15g of <%s> outside bounds loc=[%.15g,%.15g], glb=[%.15g,%.15g]\n",
1463  solval, SCIPvarGetName(vars[i]), lb, ub, SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i]));
1464  SCIPABORT();
1465  }
1466 
1467  SCIP_CALL( SCIPfixVar(scip, vars[i], solval, &infeasible, &fixed) );
1468  if( infeasible )
1469  *result = SCIP_CUTOFF;
1470  else if( fixed )
1471  *result = SCIP_REDUCEDDOM;
1472  }
1473 
1474  return SCIP_OKAY;
1475 }
1476 
1477 /** creates the debugging propagator and includes it in SCIP */
1478 SCIP_RETCODE SCIPdebugIncludeProp(
1479  SCIP* scip /**< SCIP data structure */
1480  )
1481 {
1482  assert(scip != NULL);
1483 
1484  /* include propagator */
1485  SCIP_CALL( SCIPincludeProp(scip, "debug", "debugging propagator", 99999999, -1, FALSE,
1486  SCIP_PROPTIMING_ALWAYS, 99999999, 0, FALSE, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
1487  NULL, propExecDebug, NULL, NULL) );
1488 
1489  return SCIP_OKAY;
1490 }
1491 
1492 /** adds a solution value for a new variable in the transformed problem that has no original counterpart
1493  * a value can only be set if no value has been set for this variable before
1494  */
1495 SCIP_RETCODE SCIPdebugAddSolVal(
1496  SCIP* scip, /**< SCIP data structure */
1497  SCIP_VAR* var, /**< variable for which to add a value */
1498  SCIP_Real val /**< solution value for variable */
1499  )
1500 {
1501  const char* varname;
1502  int i;
1503 
1504  assert(var != NULL);
1505 
1506  /* assert that we are in the SCIP instance that we are debugging and not some different (subSCIP, auxiliary CIP, ...) */
1507  assert(isMainscipset(scip->set));
1508 
1509  if( SCIPvarIsOriginal(var) )
1510  {
1511  SCIPerrorMessage("adding solution values for original variables is forbidden\n");
1512  return SCIP_ERROR;
1513  }
1514 
1515  if( SCIPvarIsTransformedOrigvar(var) )
1516  {
1517  SCIPerrorMessage("adding solution values for variable that are direct counterparts of original variables is forbidden\n");
1518  return SCIP_ERROR;
1519  }
1520 
1521  /* allocate memory */
1522  if( nsolvals >= solsize )
1523  {
1524  solsize = MAX(2*solsize, nsolvals+1);
1525  SCIP_ALLOC( BMSreallocMemoryArray(&solnames, solsize) );
1526  SCIP_ALLOC( BMSreallocMemoryArray(&solvals, solsize) );
1527  }
1528  assert(nsolvals < solsize);
1529 
1530  /* store solution value in sorted list */
1531  varname = SCIPvarGetName(var);
1532  for( i = nsolvals; i > 0 && strcmp(varname, solnames[i-1]) < 0; --i )
1533  {
1534  solnames[i] = solnames[i-1];
1535  solvals[i] = solvals[i-1];
1536  }
1537  if( i > 0 && strcmp(varname, solnames[i-1]) == 0 )
1538  {
1539  if( REALABS(solvals[i-1] - val) > 1e-9 )
1540  {
1541  SCIPerrorMessage("already have stored different debugging solution value (%g) for variable <%s>, cannot store %g\n", solvals[i-1], varname, val);
1542  return SCIP_ERROR;
1543  }
1544  else
1545  {
1546  SCIPdebugMessage("already have stored debugging solution value %g for variable <%s>, do not store same value again\n", val, varname);
1547  for( ; i < nsolvals; ++i )
1548  {
1549  solnames[i] = solnames[i+1];
1550  solvals[i] = solvals[i+1];
1551  }
1552  return SCIP_OKAY;
1553  }
1554  }
1555 
1556  /* insert new solution value */
1557  SCIP_ALLOC( BMSduplicateMemoryArray(&solnames[i], varname, strlen(varname)+1) );
1558  SCIPdebugMessage("add variable <%s>: value <%g>\n", solnames[i], val);
1559  solvals[i] = val;
1560  nsolvals++;
1561 
1562  /* update objective function value of debug solution */
1563  debugsolval += solvals[i] * SCIPvarGetObj(var);
1564  SCIPdebugMessage("Debug Solution value is now %g.\n", debugsolval);
1565 
1566  assert(debugsol != NULL);
1567 
1568  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_ORIGINAL )
1569  {
1570  /* add values to SCIP debug solution */
1571  SCIP_CALL( SCIPsetSolVal(scip, debugsol, var, solvals[i] ) );
1572  }
1573 
1574  return SCIP_OKAY;
1575 }
1576 
1577 #else
1578 
1579 /** this is a dummy method to make the SunOS gcc linker happy */
1580 extern void SCIPdummyDebugMethodForSun(void);
1581 void SCIPdummyDebugMethodForSun(void)
1582 {
1583  return;
1584 }
1585 
1586 #endif
1587 
1588 
1589 /*
1590  * debug method for LP interface, to check if the LP interface works correct
1591  */
1592 #ifdef SCIP_DEBUG_LP_INTERFACE
1593 
1594 /* check whether coef is the r-th row of the inverse basis matrix B^-1; this is
1595  * the case if( coef * B ) is the r-th unit vector */
1596 SCIP_RETCODE SCIPdebugCheckBInvRow(
1597  SCIP* scip, /**< SCIP data structure */
1598  int r, /**< row number */
1599  SCIP_Real* coef /**< r-th row of the inverse basis matrix */
1600  )
1601 {
1602  SCIP_Real vecval;
1603  SCIP_Real matrixval;
1604  int* basisind;
1605  int nrows;
1606  int idx;
1607  int i;
1608  int k;
1609 
1610  assert(scip != NULL);
1611 
1612  nrows = SCIPgetNLPRows(scip);
1613 
1614  /* get basic indices for the basic matrix B */
1615  SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
1616  SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
1617 
1618 
1619  /* loop over the columns of B */
1620  for( k = 0; k < nrows; ++k )
1621  {
1622  vecval = 0.0;
1623 
1624  /* indices of basic columns and rows:
1625  * - index i >= 0 corresponds to column i,
1626  * - index i < 0 to row -i-1
1627  */
1628  idx = basisind[k];
1629 
1630  /* check if we have a slack variable; this is the case if idx < 0 */
1631  if( idx >= 0 )
1632  {
1633  /* loop over the rows to compute the corresponding value in the unit vector */
1634  for( i = 0; i < nrows; ++i )
1635  {
1636  SCIP_CALL( SCIPlpiGetCoef(scip->lp->lpi, i, idx, &matrixval) );
1637  vecval += coef[i] * matrixval;
1638  }
1639  }
1640  else
1641  {
1642  assert( idx < 0 );
1643 
1644  /* retransform idx
1645  * - index i >= 0 corresponds to column i,
1646  * - index i < 0 to row -i-1
1647  */
1648  idx = -idx - 1;
1649  assert( idx >= 0 && idx < nrows );
1650 
1651  /* since idx < 0 we are in the case of a slack variable, i.e., the corresponding column
1652  is the idx-unit vector; note that some LP solver return a -idx-unit vector */
1653  /* vecval = REALABS(coef[idx]);*/
1654  vecval = coef[idx];
1655  }
1656 
1657  /* check if vecval fits to the r-th unit vector */
1658  if( k == r && !SCIPisFeasEQ(scip, vecval, 1.0) )
1659  {
1660  /* we expected a 1.0 and found something different */
1661  SCIPmessagePrintWarning(SCIPgetMessagehdlr(scip), "checked SCIPgetLPBInvRow() found value <%g> expected 1.0\n", vecval);
1662  }
1663  else if( k != r && !SCIPisFeasZero(scip, vecval) )
1664  {
1665  /* we expected a 0.0 and found something different */
1666  SCIPmessagePrintWarning(SCIPgetMessagehdlr(scip), "checked SCIPgetLPBInvRow() found value <%g> expected 0.0\n", vecval);
1667  }
1668  }
1669 
1670  SCIPfreeBufferArray(scip, &basisind);
1671 
1672  return SCIP_OKAY;
1673 }
1674 
1675 #endif
1676