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