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