Scippy

SCIP

Solving Constraint Integer Programs

visual.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-2018 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 visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file visual.c
17  * @brief methods for creating output for visualization tools (VBC, BAK)
18  * @author Tobias Achterberg
19  * @author Marc Pfetsch
20  *
21  * Output can be generated for the following visualization tools:
22  *
23  * - VBCTOOL - a graphical interface for Visualization of Branch Cut algorithms @n
24  * See <a href="http://www.informatik.uni-koeln.de/ls_juenger/research/vbctool">VBCTOOL</a>.
25  * - BAK: Branch-and-bound Analysis Kit @n
26  * BAK is available through COIN-OR, see <a href="https://projects.coin-or.org/CoinBazaar/wiki/Projects/BAK">BAK</a>.
27  * A description is <a href="http://www.optimization-online.org/DB_HTML/2007/09/1785.html">available</a> as well.
28  */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 #include <stdio.h>
33 #include <assert.h>
34 
35 #include "blockmemshell/memory.h"
36 #include "scip/scip.h"
37 #include "scip/set.h"
38 #include "scip/stat.h"
39 #include "scip/clock.h"
40 #include "scip/var.h"
41 #include "scip/tree.h"
42 #include "scip/visual.h"
43 #include "scip/struct_visual.h"
44 
45 
46 /** returns the branching variable of the node, or NULL */
47 static
49  SCIP_NODE* node, /**< node */
50  SCIP_VAR** var, /**< pointer to store the branching variable */
51  SCIP_BOUNDTYPE* boundtype, /**< pointer to store the branching type: lower or upper bound */
52  SCIP_Real* bound /**< pointer to store the new bound of the branching variable */
53  )
54 {
55  SCIP_DOMCHGBOUND* domchgbound;
56 
57  (*var) = NULL;
58  (*bound) = 0.0;
59  (*boundtype) = SCIP_BOUNDTYPE_LOWER;
60 
61  assert(node != NULL);
62  if( node->domchg == NULL )
63  return;
64 
65  domchgbound = &node->domchg->domchgbound;
66  if( domchgbound->nboundchgs == 0 )
67  return;
68 
69  (*var) = domchgbound->boundchgs[0].var;
70  (*bound) = domchgbound->boundchgs[0].newbound;
71  (*boundtype) = (SCIP_BOUNDTYPE) domchgbound->boundchgs[0].boundtype;
72 }
73 
74 /** creates visualization data structure */
76  SCIP_VISUAL** visual, /**< pointer to store visualization information */
77  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
78  )
79 {
80  SCIP_ALLOC( BMSallocMemory(visual) );
81 
82  (*visual)->vbcfile = NULL;
83  (*visual)->bakfile = NULL;
84  (*visual)->messagehdlr = messagehdlr;
85  (*visual)->nodenum = NULL;
86  (*visual)->timestep = 0;
87  (*visual)->lastnode = NULL;
88  (*visual)->lastcolor = SCIP_VBCCOLOR_NONE;
89  (*visual)->userealtime = FALSE;
90  (*visual)->lastlowerbound = SCIP_INVALID;
91 
92  return SCIP_OKAY;
93 }
94 
95 /** frees visualization data structure */
97  SCIP_VISUAL** visual /**< pointer to store visualization information */
98  )
99 {
100  assert( visual != NULL );
101  assert( *visual != NULL );
102  assert( (*visual)->vbcfile == NULL );
103  assert( (*visual)->bakfile == NULL );
104  assert( (*visual)->nodenum == NULL );
105 
106  BMSfreeMemory(visual);
107 }
108 
109 /** initializes visualization information and creates a file for visualization output */
111  SCIP_VISUAL* visual, /**< visualization information */
112  BMS_BLKMEM* blkmem, /**< block memory */
113  SCIP_SET* set, /**< global SCIP settings */
114  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
115  )
116 {
117  assert( visual != NULL );
118  assert( set != NULL );
119  assert( set->visual_vbcfilename != NULL );
120  assert( set->visual_bakfilename != NULL );
121  assert( visual->nodenum == NULL );
122 
123  visual->lastlowerbound = -SCIPsetInfinity(set);
124 
125  /* check whether we should initialize VBC output */
126  if ( set->visual_vbcfilename[0] != '-' || set->visual_vbcfilename[1] != '\0' )
127  {
128  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
129  "storing VBC information in file <%s>\n", set->visual_vbcfilename);
130  visual->vbcfile = fopen(set->visual_vbcfilename, "w");
131  visual->timestep = 0;
132  visual->lastnode = NULL;
133  visual->lastcolor = SCIP_VBCCOLOR_NONE;
134  visual->userealtime = set->visual_realtime;
135 
136  if( visual->vbcfile == NULL )
137  {
138  SCIPerrorMessage("error creating file <%s>\n", set->visual_vbcfilename);
139  SCIPprintSysError(set->visual_vbcfilename);
140  return SCIP_FILECREATEERROR;
141  }
142 
143  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "#TYPE: COMPLETE TREE\n");
144  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "#TIME: SET\n");
145  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "#BOUNDS: SET\n");
146  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "#INFORMATION: STANDARD\n");
147  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "#NODE_NUMBER: NONE\n");
148  }
149 
150  /* check whether we should initialize BAK output */
151  if ( set->visual_bakfilename[0] != '-' || set->visual_bakfilename[1] != '\0' )
152  {
153  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_NORMAL,
154  "storing BAK information in file <%s>\n", set->visual_bakfilename);
155  visual->bakfile = fopen(set->visual_bakfilename, "w");
156  visual->timestep = 0;
157  visual->lastnode = NULL;
158  visual->lastcolor = SCIP_VBCCOLOR_NONE;
159  visual->userealtime = set->visual_realtime;
160 
161  if ( visual->bakfile == NULL )
162  {
163  SCIPerrorMessage("error creating file <%s>\n", set->visual_bakfilename);
164  SCIPprintSysError(set->visual_bakfilename);
165  return SCIP_FILECREATEERROR;
166  }
167  }
168 
169  /* possibly init hashmap for nodes */
170  if ( visual->vbcfile != NULL || visual->bakfile != NULL )
171  {
173  }
174 
175  return SCIP_OKAY;
176 }
177 
178 /** closes the visualization output file */
180  SCIP_VISUAL* visual, /**< visualization information */
181  SCIP_SET* set, /**< global SCIP settings */
182  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
183  )
184 {
185  assert( visual != NULL );
186  assert( set != NULL );
187 
188  if ( visual->vbcfile != NULL )
189  {
190  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL, "closing VBC information file\n");
191 
192  fclose(visual->vbcfile);
193  visual->vbcfile = NULL;
194  }
195 
196  if ( visual->bakfile != NULL )
197  {
198  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL, "closing BAK information file\n");
199 
200  fclose(visual->bakfile);
201  visual->bakfile = NULL;
202  }
203 
204  if ( visual->nodenum )
205  SCIPhashmapFree(&visual->nodenum);
206 }
207 
208 /** prints current solution time to visualization output file */
209 static
211  SCIP_VISUAL* visual, /**< visualization information */
212  SCIP_STAT* stat, /**< problem statistics */
213  SCIP_Bool vbc /**< whether we use vbc output (bak otherwise) */
214  )
215 {
216  SCIP_Longint step;
217  int hours;
218  int mins;
219  int secs;
220  int hunds;
221 
222  assert( visual != NULL );
223  assert( stat != NULL );
224 
225  if( visual->userealtime )
226  {
227  double time;
228  time = SCIPclockGetTime(stat->solvingtime);
229  step = (SCIP_Longint)(time * 100.0);
230  }
231  else
232  {
233  step = visual->timestep;
234  visual->timestep++;
235  }
236 
237  if ( vbc )
238  {
239  hours = (int)(step / (60*60*100));
240  step %= 60*60*100;
241  mins = (int)(step / (60*100));
242  step %= 60*100;
243  secs = (int)(step / 100);
244  step %= 100;
245  hunds = (int)step;
246 
247  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "%02d:%02d:%02d.%02d ", hours, mins, secs, hunds);
248  }
249  else
250  {
251  SCIPmessageFPrintInfo(visual->messagehdlr, visual->bakfile, "%f ", (SCIP_Real) step/100.0);
252  }
253 }
254 
255 /** creates a new node entry in the visualization output file */
257  SCIP_VISUAL* visual, /**< visualization information */
258  SCIP_SET* set, /**< global SCIP settings */
259  SCIP_STAT* stat, /**< problem statistics */
260  SCIP_NODE* node /**< new node, that was created */
261  )
262 {
263  SCIP_VAR* branchvar;
264  SCIP_BOUNDTYPE branchtype;
265  SCIP_Real branchbound;
266  SCIP_Real lowerbound;
267  size_t parentnodenum;
268  size_t nodenum;
269 
270  assert( visual != NULL );
271  assert( stat != NULL );
272  assert( node != NULL );
273 
274  /* visualization is disabled on probing nodes */
276  return SCIP_OKAY;
277 
278  /* check whether output should be created */
279  if ( visual->vbcfile == NULL && visual->bakfile == NULL )
280  return SCIP_OKAY;
281 
282  /* insert mapping node -> nodenum into hash map */
283  if( stat->ncreatednodesrun >= (SCIP_Longint)INT_MAX )
284  {
285  SCIPerrorMessage("too many nodes to store in the visualization file\n");
286  return SCIP_INVALIDDATA;
287  }
288 
289  nodenum = (size_t)stat->ncreatednodesrun;
290  assert(nodenum > 0);
291  SCIP_CALL( SCIPhashmapSetImage(visual->nodenum, node, (void*)nodenum) );
292 
293  /* get nodenum of parent node from hash map */
294  parentnodenum = (node->parent != NULL ? (size_t)SCIPhashmapGetImage(visual->nodenum, node->parent) : 0);
295  assert(node->parent == NULL || parentnodenum > 0);
296 
297  /* get branching information */
298  getBranchInfo(node, &branchvar, &branchtype, &branchbound);
299 
300  /* determine lower bound */
301  if ( set->visual_objextern )
302  lowerbound = SCIPretransformObj(set->scip, SCIPnodeGetLowerbound(node));
303  else
304  lowerbound = SCIPnodeGetLowerbound(node);
305 
306  if ( visual->vbcfile != NULL )
307  {
308  printTime(visual, stat, TRUE);
309  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "N %d %d %d\n", (int)parentnodenum, (int)nodenum, SCIP_VBCCOLOR_UNSOLVED);
310  printTime(visual, stat, TRUE);
311  if( branchvar != NULL )
312  {
313  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "I %d \\inode:\\t%d (%p)\\idepth:\\t%d\\nvar:\\t%s [%g,%g] %s %f\\nbound:\\t%f\n",
314  (int)nodenum, (int)nodenum, node, SCIPnodeGetDepth(node),
315  SCIPvarGetName(branchvar), SCIPvarGetLbLocal(branchvar), SCIPvarGetUbLocal(branchvar),
316  branchtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", branchbound, lowerbound);
317  }
318  else
319  {
320  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "I %d \\inode:\\t%d (%p)\\idepth:\\t%d\\nvar:\\t-\\nbound:\\t%f\n",
321  (int)nodenum, (int)nodenum, node, SCIPnodeGetDepth(node), lowerbound);
322  }
323  }
324 
325  /* For BAK, not all available information is available here. Use SCIPvisualUpdateChild() instead */
326 
327  return SCIP_OKAY;
328 }
329 
330 /** updates a node entry in the visualization output file */
332  SCIP_VISUAL* visual, /**< visualization information */
333  SCIP_SET* set, /**< global SCIP settings */
334  SCIP_STAT* stat, /**< problem statistics */
335  SCIP_NODE* node /**< new node, that was created */
336  )
337 {
338  SCIP_VAR* branchvar;
339  SCIP_BOUNDTYPE branchtype;
340  SCIP_Real branchbound;
341  SCIP_Real lowerbound;
342  size_t nodenum;
343 
344  assert( visual != NULL );
345  assert( stat != NULL );
346  assert( node != NULL );
347 
348  /* check whether output should be created */
349  if ( visual->vbcfile == NULL && visual->bakfile == NULL )
350  return SCIP_OKAY;
351 
352  /* visualization is disabled on probing nodes */
354  return SCIP_OKAY;
355 
356  /* get node num from hash map */
357  nodenum = (size_t)SCIPhashmapGetImage(visual->nodenum, node);
358  assert(nodenum > 0);
359 
360  /* get branching information */
361  getBranchInfo(node, &branchvar, &branchtype, &branchbound);
362 
363  /* determine lower bound */
364  if ( set->visual_objextern )
365  lowerbound = SCIPretransformObj(set->scip, SCIPnodeGetLowerbound(node));
366  else
367  lowerbound = SCIPnodeGetLowerbound(node);
368 
369  if ( visual->vbcfile != NULL )
370  {
371  printTime(visual, stat, TRUE);
372  if( branchvar != NULL )
373  {
374  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "I %d \\inode:\\t%d (%p)\\idepth:\\t%d\\nvar:\\t%s [%g,%g] %s %f\\nbound:\\t%f\n",
375  (int)nodenum, (int)nodenum, node, SCIPnodeGetDepth(node),
376  SCIPvarGetName(branchvar), SCIPvarGetLbLocal(branchvar), SCIPvarGetUbLocal(branchvar),
377  branchtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", branchbound, lowerbound);
378  }
379  else
380  {
381  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "I %d \\inode:\\t%d (%p)\\idepth:\\t%d\\nvar:\\t-\\nbound:\\t%f\n",
382  (int)nodenum, (int)nodenum, node, SCIPnodeGetDepth(node), lowerbound);
383  }
384  }
385 
386  if ( visual->bakfile != NULL )
387  {
388  size_t parentnodenum;
389  SCIP_Real* lpcandsfrac;
390  SCIP_Real sum = 0.0;
391  int nlpcands = 0;
392  char t = 'M';
393  const char* nodeinfo;
394  int j;
395 
396  /* determine branching type */
397  if ( branchvar != NULL )
398  t = (branchtype == SCIP_BOUNDTYPE_LOWER ? 'R' : 'L');
399 
400  /* get nodenum of parent node from hash map */
401  parentnodenum = (node->parent != NULL ? (size_t)SCIPhashmapGetImage(visual->nodenum, node->parent) : 0);
402  assert(node->parent == NULL || parentnodenum > 0);
403 
404  /* update info depending on the node type */
405  switch( SCIPnodeGetType(node) )
406  {
407  case SCIP_NODETYPE_CHILD:
408  /* the child is a new candidate */
409  nodeinfo = "candidate";
410  break;
412  /* the focus node is updated to a branch node */
413  nodeinfo = "branched";
414 
415  /* calculate infeasibility information only if the LP was solved to optimality */
416  if( SCIPgetLPSolstat(set->scip) == SCIP_LPSOLSTAT_OPTIMAL )
417  {
418  SCIP_CALL( SCIPgetLPBranchCands(set->scip, NULL, NULL, &lpcandsfrac, &nlpcands, NULL, NULL) );
419  for( j = 0; j < nlpcands; ++j )
420  sum += lpcandsfrac[j];
421  }
422 
423  break;
424  default:
425  SCIPerrorMessage("Error: Unexpected node type <%d> in Update Child Method", SCIPnodeGetType(node));
426  return SCIP_INVALIDDATA;
427  } /*lint !e788*/
428  /* append new status line with updated node information to the bakfile */
429  printTime(visual, stat, FALSE);
430  SCIPmessageFPrintInfo(visual->messagehdlr, visual->bakfile, "%s %d %d %c %f %f %d\n", nodeinfo, (int)nodenum, (int)parentnodenum, t,
431  lowerbound, sum, nlpcands);
432  }
433 
434  return SCIP_OKAY;
435 }
436 
437 /** changes the color of the node to the given color */
438 static
440  SCIP_VISUAL* visual, /**< visualization information */
441  SCIP_STAT* stat, /**< problem statistics */
442  SCIP_NODE* node, /**< node to change color for */
443  SCIP_VBCCOLOR color /**< new color of node, or SCIP_VBCCOLOR_NONE */
444  )
445 {
446  assert( visual != NULL );
447  assert( node != NULL );
448 
449  if( visual->vbcfile != NULL && color != SCIP_VBCCOLOR_NONE && (node != visual->lastnode || color != visual->lastcolor) )
450  {
451  size_t nodenum;
452 
453  nodenum = (size_t)SCIPhashmapGetImage(visual->nodenum, node);
454  assert(nodenum > 0);
455  printTime(visual, stat, TRUE);
456  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "P %d %d\n", (int)nodenum, color);
457  visual->lastnode = node;
458  visual->lastcolor = color;
459  }
460 }
461 
462 /** marks node as solved in visualization output file */
464  SCIP_VISUAL* visual, /**< visualization information */
465  SCIP_SET* set, /**< global SCIP settings */
466  SCIP_STAT* stat, /**< problem statistics */
467  SCIP_NODE* node /**< node, that was solved */
468  )
469 {
470  SCIP_VAR* branchvar;
471  SCIP_BOUNDTYPE branchtype;
472  SCIP_Real branchbound;
473  SCIP_Real lowerbound;
474  size_t nodenum;
475 
476  assert( visual != NULL );
477  assert( stat != NULL );
478  assert( node != NULL );
479 
480  /* check whether output should be created */
481  if ( visual->vbcfile == NULL && visual->bakfile == NULL )
482  return;
483 
484  /* visualization is disabled on probing nodes */
486  return;
487 
488  /* get node num from hash map */
489  nodenum = (size_t)SCIPhashmapGetImage(visual->nodenum, node);
490  assert(nodenum > 0);
491 
492  /* get branching information */
493  getBranchInfo(node, &branchvar, &branchtype, &branchbound);
494 
495  /* determine lower bound */
496  if ( set->visual_objextern )
497  lowerbound = SCIPretransformObj(set->scip, SCIPnodeGetLowerbound(node));
498  else
499  lowerbound = SCIPnodeGetLowerbound(node);
500 
501  if ( visual->vbcfile != NULL )
502  {
503  printTime(visual, stat, TRUE);
504  if( branchvar != NULL )
505  {
506  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "I %d \\inode:\\t%d (%p)\\idepth:\\t%d\\nvar:\\t%s [%g,%g] %s %f\\nbound:\\t%f\\nnr:\\t%" SCIP_LONGINT_FORMAT "\n",
507  (int)nodenum, (int)nodenum, node, SCIPnodeGetDepth(node),
508  SCIPvarGetName(branchvar), SCIPvarGetLbLocal(branchvar), SCIPvarGetUbLocal(branchvar),
509  branchtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", branchbound, lowerbound, stat->nnodes);
510  }
511  else
512  {
513  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "I %d \\inode:\\t%d (%p)\\idepth:\\t%d\\nvar:\\t-\\nbound:\\t%f\\nnr:\\t%" SCIP_LONGINT_FORMAT "\n",
514  (int)nodenum, (int)nodenum, node, SCIPnodeGetDepth(node), lowerbound, stat->nnodes);
515  }
516  vbcSetColor(visual, stat, node, SCIP_VBCCOLOR_SOLVED);
517  }
518 
519  /* do nothing for BAK */
520 }
521 
522 /** changes the color of the node to the color of cutoff nodes */
524  SCIP_VISUAL* visual, /**< visualization information */
525  SCIP_SET* set, /**< global SCIP settings */
526  SCIP_STAT* stat, /**< problem statistics */
527  SCIP_NODE* node, /**< node, that was cut off */
528  SCIP_Bool infeasible /**< whether the node is infeasible (otherwise exceeded the cutoff bound) */
529  )
530 {
531  SCIP_VAR* branchvar;
532  SCIP_BOUNDTYPE branchtype;
533  SCIP_Real branchbound;
534  SCIP_Real lowerbound;
535  size_t nodenum;
536 
537  assert( visual != NULL );
538  assert( stat != NULL );
539  assert( node != NULL );
540 
541  /* check whether output should be created */
542  if ( visual->vbcfile == NULL && visual->bakfile == NULL )
543  return;
544 
545  /* visualization is disabled on probing nodes */
547  return;
548 
549  /* get node num from hash map */
550  nodenum = (size_t)SCIPhashmapGetImage(visual->nodenum, node);
551  assert(nodenum > 0);
552 
553  /* get branching information */
554  getBranchInfo(node, &branchvar, &branchtype, &branchbound);
555 
556  /* determine lower bound */
557  if ( set->visual_objextern )
558  lowerbound = SCIPretransformObj(set->scip, SCIPnodeGetLowerbound(node));
559  else
560  lowerbound = SCIPnodeGetLowerbound(node);
561 
562  if ( visual->vbcfile != NULL )
563  {
564  printTime(visual, stat, TRUE);
565  if( branchvar != NULL )
566  {
567  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "I %d \\inode:\\t%d (%p)\\idepth:\\t%d\\nvar:\\t%s [%g,%g] %s %f\\nbound:\\t%f\\nnr:\\t%" SCIP_LONGINT_FORMAT "\n",
568  (int)nodenum, (int)nodenum, node, SCIPnodeGetDepth(node),
569  SCIPvarGetName(branchvar), SCIPvarGetLbLocal(branchvar), SCIPvarGetUbLocal(branchvar),
570  branchtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", branchbound, lowerbound, stat->nnodes);
571  }
572  else
573  {
574  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "I %d \\inode:\\t%d (%p)\\idepth:\\t%d\\nvar:\\t-\\nbound:\\t%f\\nnr:\\t%" SCIP_LONGINT_FORMAT "\n",
575  (int)nodenum, (int)nodenum, node, SCIPnodeGetDepth(node), lowerbound, stat->nnodes);
576  }
577  vbcSetColor(visual, stat, node, SCIP_VBCCOLOR_CUTOFF);
578  }
579 
580  if ( visual->bakfile != NULL )
581  {
582  size_t parentnodenum;
583  char t = 'M';
584 
585  /* determine branching type */
586  if ( branchvar != NULL )
587  t = (branchtype == SCIP_BOUNDTYPE_LOWER ? 'R' : 'L');
588 
589  /* get nodenum of parent node from hash map */
590  parentnodenum = (node->parent != NULL ? (size_t)SCIPhashmapGetImage(visual->nodenum, node->parent) : 0);
591  assert(node->parent == NULL || parentnodenum > 0);
592 
593  printTime(visual, stat, FALSE);
594  if ( infeasible )
595  SCIPmessageFPrintInfo(visual->messagehdlr, visual->bakfile, "infeasible %d %d %c\n", (int)nodenum, (int)parentnodenum, t);
596  else
597  SCIPmessageFPrintInfo(visual->messagehdlr, visual->bakfile, "fathomed %d %d %c\n", (int)nodenum, (int)parentnodenum, t);
598  }
599 }
600 
601 /** changes the color of the node to the color of nodes where a conflict constraint was found */
603  SCIP_VISUAL* visual, /**< visualization information */
604  SCIP_STAT* stat, /**< problem statistics */
605  SCIP_NODE* node /**< node, where the conflict was found */
606  )
607 {
608  assert(node != NULL);
609 
610  /* visualization is disabled on probing nodes */
612  return;
613 
614  vbcSetColor(visual, stat, node, SCIP_VBCCOLOR_CONFLICT);
615 
616  /* do nothing for BAK */
617 }
618 
619 /** changes the color of the node to the color of nodes that were marked to be repropagated */
621  SCIP_VISUAL* visual, /**< visualization information */
622  SCIP_STAT* stat, /**< problem statistics */
623  SCIP_NODE* node /**< node, that was marked to be repropagated */
624  )
625 {
626  assert(node != NULL);
627 
628  /* visualization is disabled on probing nodes */
630  return;
631 
632  /* if the node number is zero, then SCIP is currently in probing and wants to mark a probing node; however this node
633  * is not part of the search tree */
634  if( SCIPnodeGetNumber(node) > 0 )
635  vbcSetColor(visual, stat, node, SCIP_VBCCOLOR_MARKREPROP);
636 
637  /* do nothing for BAK */
638 }
639 
640 /** changes the color of the node to the color of repropagated nodes */
642  SCIP_VISUAL* visual, /**< visualization information */
643  SCIP_STAT* stat, /**< problem statistics */
644  SCIP_NODE* node /**< node, that was repropagated */
645  )
646 {
647  assert(node != NULL);
648 
649  /* visualization is disabled on probing nodes */
651  return;
652 
653  vbcSetColor(visual, stat, node, SCIP_VBCCOLOR_REPROP);
654 
655  /* do nothing for BAK */
656 }
657 
658 /** changes the color of the node to the color of nodes with a primal solution */
660  SCIP_VISUAL* visual, /**< visualization information */
661  SCIP_SET* set, /**< global SCIP settings */
662  SCIP_STAT* stat, /**< problem statistics */
663  SCIP_NODE* node, /**< node where the solution was found, or NULL */
664  SCIP_Bool bettersol, /**< the solution was better than the previous ones */
665  SCIP_SOL* sol /**< solution that has been found */
666  )
667 {
668  if( node == NULL || ! set->visual_dispsols )
669  return;
670 
671  if( visual->vbcfile != NULL )
672  {
673  SCIP_Real obj;
674  size_t nodenum;
675 
676  /* if we are in probing, determine original parent node */
677  while ( SCIPnodeGetType(node) == SCIP_NODETYPE_PROBINGNODE )
678  node = SCIPnodeGetParent(node);
679 
680  /* get node num from hash map */
681  assert(node != NULL);
682  nodenum = (size_t)SCIPhashmapGetImage(visual->nodenum, node);
683  assert(nodenum > 0);
684 
685  /* get objective of solution */
686  if( set->visual_objextern )
687  obj = SCIPgetSolOrigObj(set->scip, sol);
688  else
689  obj = SCIPgetSolTransObj(set->scip, sol);
690 
691  printTime(visual, stat, TRUE);
692  if( bettersol )
693  {
694  /* note that this output is in addition to the one by SCIPvisualUpperbound() */
695  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "A %d \\nfound better solution: %f\n", (int)nodenum, obj);
696  }
697  else
698  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "A %d \\nfound solution: %f\n", (int)nodenum, obj);
699 
700  vbcSetColor(visual, stat, node, SCIP_VBCCOLOR_SOLUTION);
701  }
702 
703  if( visual->bakfile != NULL && bettersol )
704  {
705  SCIP_Real obj;
706 
707  if( set->visual_objextern )
708  obj = SCIPgetSolOrigObj(set->scip, sol);
709  else
710  obj = SCIPgetSolTransObj(set->scip, sol);
711 
712  if( SCIPsolGetHeur(sol) == NULL )
713  {
714  /* if LP solution was feasible ... */
715  SCIP_VAR* branchvar;
716  SCIP_BOUNDTYPE branchtype;
717  SCIP_Real branchbound;
718  SCIP_NODE *pnode;
719  size_t parentnodenum;
720  size_t nodenum;
721  char t = 'M';
722 
723  /* find first parent that is not a probing node */
724  assert(node != NULL);
725  pnode = node;
726  while( pnode != NULL && SCIPnodeGetType(pnode) == SCIP_NODETYPE_PROBINGNODE )
727  pnode = pnode->parent;
728 
729  if( pnode != NULL )
730  {
731  /* get node num from hash map */
732  nodenum = (size_t)SCIPhashmapGetImage(visual->nodenum, pnode);
733 
734  /* get nodenum of parent node from hash map */
735  parentnodenum = (pnode->parent != NULL ? (size_t)SCIPhashmapGetImage(visual->nodenum, pnode->parent) : 0);
736  assert(pnode->parent == NULL || parentnodenum > 0);
737 
738  /* get branching information */
739  getBranchInfo(pnode, &branchvar, &branchtype, &branchbound);
740 
741  /* determine branching type */
742  if( branchvar != NULL )
743  t = (branchtype == SCIP_BOUNDTYPE_LOWER ? 'R' : 'L');
744 
745  printTime(visual, stat, FALSE);
746  SCIPmessageFPrintInfo(visual->messagehdlr, visual->bakfile, "integer %d %d %c %f\n", (int)nodenum, (int)parentnodenum, t, obj);
747  }
748  }
749  else
750  {
751  printTime(visual, stat, FALSE);
752  SCIPmessageFPrintInfo(visual->messagehdlr, visual->bakfile, "heuristic %f\n", obj);
753  }
754  }
755 }
756 
757 /** outputs a new global lower bound to the visualization output file */
759  SCIP_VISUAL* visual, /**< visualization information */
760  SCIP_SET* set, /**< global SCIP settings */
761  SCIP_STAT* stat, /**< problem statistics */
762  SCIP_Real lowerbound /**< new lower bound */
763  )
764 {
765  assert(visual != NULL);
766 
767  /* do not output if not required */
768  if ( ! set->visual_displb )
769  return;
770 
771  /* check, if VBC output should be created */
772  if( visual->vbcfile == NULL )
773  return;
774 
775  /* only output if lowerbound has improved and is finite */
776  if ( ! SCIPsetIsInfinity(set, lowerbound) && SCIPsetIsGT(set, lowerbound, visual->lastlowerbound) )
777  {
778  visual->lastlowerbound = lowerbound;
779 
780  /* determine external lower bound */
781  if( set->visual_objextern )
782  lowerbound = SCIPretransformObj(set->scip, lowerbound);
783 
784  printTime(visual, stat, TRUE);
785  if( SCIPgetObjsense(set->scip) == SCIP_OBJSENSE_MINIMIZE )
786  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "L %f\n", lowerbound);
787  else
788  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "U %f\n", lowerbound);
789  }
790 
791  /* do nothing for BAK */
792 }
793 
794 /** outputs a new global upper bound to the visualization output file */
796  SCIP_VISUAL* visual, /**< visualization information */
797  SCIP_SET* set, /**< global SCIP settings */
798  SCIP_STAT* stat, /**< problem statistics */
799  SCIP_Real upperbound /**< new upper bound */
800  )
801 {
802  assert(visual != NULL);
803 
804  /* check, if VBC output should be created */
805  if( visual->vbcfile == NULL )
806  return;
807 
808  /* determine external upper bound */
809  if( set->visual_objextern )
810  upperbound = SCIPretransformObj(set->scip, upperbound);
811 
812  printTime(visual, stat, TRUE);
813  if( SCIPgetObjsense(set->scip) == SCIP_OBJSENSE_MINIMIZE )
814  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "U %f\n", upperbound);
815  else
816  SCIPmessageFPrintInfo(visual->messagehdlr, visual->vbcfile, "L %f\n", upperbound);
817 
818  /* do nothing for BAK */
819 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:384
data structures for output for visualization tools (VBC, BAK)
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_RETCODE SCIPvisualCreate(SCIP_VISUAL **visual, SCIP_MESSAGEHDLR *messagehdlr)
Definition: visual.c:75
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:5953
#define NULL
Definition: def.h:239
enum SCIP_VBCColor SCIP_VBCCOLOR
Definition: type_visual.h:64
void SCIPvisualRepropagatedNode(SCIP_VISUAL *visual, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:641
internal methods for branch and bound tree
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7364
internal methods for clocks and timing issues
SCIP_BOUNDCHG * boundchgs
Definition: struct_var.h:125
static long bound
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17399
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7624
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:5813
unsigned int nboundchgs
Definition: struct_var.h:123
void SCIPvisualFree(SCIP_VISUAL **visual)
Definition: visual.c:96
#define FALSE
Definition: def.h:65
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
void SCIPvisualSolvedNode(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:463
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7354
methods for creating output for visualization tools (VBC, BAK)
static void getBranchInfo(SCIP_NODE *node, SCIP_VAR **var, SCIP_BOUNDTYPE *boundtype, SCIP_Real *bound)
Definition: visual.c:48
#define BMSfreeMemory(ptr)
Definition: memory.h:127
void SCIPvisualExit(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr)
Definition: visual.c:179
void SCIPvisualLowerbound(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_Real lowerbound)
Definition: visual.c:758
FILE * vbcfile
Definition: struct_visual.h:42
static void vbcSetColor(SCIP_VISUAL *visual, SCIP_STAT *stat, SCIP_NODE *node, SCIP_VBCCOLOR color)
Definition: visual.c:439
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7344
SCIP_DOMCHG * domchg
Definition: struct_tree.h:151
SCIP_RETCODE SCIPvisualNewChild(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:256
#define SCIPerrorMessage
Definition: pub_message.h:45
void SCIPmessagePrintVerbInfo(SCIP_MESSAGEHDLR *messagehdlr, SCIP_VERBLEVEL verblevel, SCIP_VERBLEVEL msgverblevel, const char *formatstr,...)
Definition: message.c:668
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:428
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2553
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1540
SCIP_VBCCOLOR lastcolor
Definition: struct_visual.h:48
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:351
SCIP_HASHMAP * nodenum
Definition: struct_visual.h:45
SCIP_Longint ncreatednodesrun
Definition: struct_stat.h:82
SCIP_Real lastlowerbound
Definition: struct_visual.h:50
internal methods for problem variables
SCIP_NODE * lastnode
Definition: struct_visual.h:47
FILE * bakfile
Definition: struct_visual.h:43
SCIP_VAR * var
Definition: struct_var.h:90
#define SCIP_Bool
Definition: def.h:62
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:226
unsigned int boundtype
Definition: struct_var.h:92
#define SCIP_HASHSIZE_VBC
Definition: def.h:276
void SCIPprintSysError(const char *message)
Definition: misc.c:9926
SCIP_RETCODE SCIPvisualUpdateChild(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:331
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1493
SCIP_Bool userealtime
Definition: struct_visual.h:49
SCIP_Real newbound
Definition: struct_var.h:84
#define SCIP_LONGINT_FORMAT
Definition: def.h:142
SCIP_DOMCHGBOUND domchgbound
Definition: struct_var.h:153
void SCIPvisualFoundConflict(SCIP_VISUAL *visual, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:602
SCIP_NODE * parent
Definition: struct_tree.h:149
SCIP_Longint timestep
Definition: struct_visual.h:46
SCIP_MESSAGEHDLR * messagehdlr
Definition: struct_visual.h:44
SCIP_CLOCK * solvingtime
Definition: struct_stat.h:144
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1625
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
Definition: message.c:608
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6029
SCIP_RETCODE SCIPhashmapSetImage(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2971
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7334
#define SCIP_Real
Definition: def.h:150
void SCIPvisualCutoffNode(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node, SCIP_Bool infeasible)
Definition: visual.c:523
internal methods for problem statistics
#define BMSallocMemory(ptr)
Definition: memory.h:101
#define SCIP_INVALID
Definition: def.h:170
#define SCIP_Longint
Definition: def.h:135
SCIP_OBJSENSE SCIPgetObjsense(SCIP *scip)
Definition: scip_prob.c:1281
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17409
SCIP_Longint nnodes
Definition: struct_stat.h:73
void SCIPvisualMarkedRepropagateNode(SCIP_VISUAL *visual, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:620
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:419
#define SCIP_ALLOC(x)
Definition: def.h:362
void SCIPvisualUpperbound(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_Real upperbound)
Definition: visual.c:795
void SCIPvisualFoundSolution(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node, SCIP_Bool bettersol, SCIP_SOL *sol)
Definition: visual.c:659
SCIP_RETCODE SCIPvisualInit(SCIP_VISUAL *visual, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr)
Definition: visual.c:110
SCIP callable library.
static void printTime(SCIP_VISUAL *visual, SCIP_STAT *stat, SCIP_Bool vbc)
Definition: visual.c:210
memory allocation routines