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