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-2024 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
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 */
57static
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 */
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 */
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 */
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
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;
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);
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;
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);
176 }
177 }
178
179 /* possibly init hashmap for nodes */
180 if ( visual->vbcfile != NULL || visual->bakfile != NULL )
181 {
183 }
184
185 return SCIP_OKAY;
186}
187
188/** closes the visualization output file */
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 */
219static
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 */
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 */
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 */
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 */
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 {
418 /* the child is a new candidate */
419 nodeinfo = "candidate";
420 break;
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 */
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 */
448static
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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);
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 */
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);
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}
static long bound
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:438
internal methods for clocks and timing issues
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define SCIP_ALLOC(x)
Definition: def.h:385
#define SCIP_Real
Definition: def.h:173
#define SCIP_HASHSIZE_VBC
Definition: def.h:305
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_OBJSENSE SCIPgetObjsense(SCIP *scip)
Definition: scip_prob.c:1225
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3357
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7483
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7513
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7493
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7773
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7503
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2804
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1300
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1347
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1432
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
void SCIPprintSysError(const char *message)
Definition: misc.c:10769
memory allocation routines
#define BMSfreeMemory(ptr)
Definition: memory.h:145
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
#define BMSallocMemory(ptr)
Definition: memory.h:118
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
Definition: message.c:618
void SCIPmessagePrintVerbInfo(SCIP_MESSAGEHDLR *messagehdlr, SCIP_VERBLEVEL verblevel, SCIP_VERBLEVEL msgverblevel, const char *formatstr,...)
Definition: message.c:678
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP callable library.
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:6064
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6199
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6275
internal methods for global SCIP settings
internal methods for problem statistics
SCIP_Real newbound
Definition: struct_var.h:93
unsigned int boundtype
Definition: struct_var.h:101
SCIP_VAR * var
Definition: struct_var.h:99
SCIP_BOUNDCHG * boundchgs
Definition: struct_var.h:134
unsigned int nboundchgs
Definition: struct_var.h:132
SCIP_DOMCHG * domchg
Definition: struct_tree.h:159
SCIP_NODE * parent
Definition: struct_tree.h:157
SCIP_Longint nnodes
Definition: struct_stat.h:82
SCIP_Longint ncreatednodesrun
Definition: struct_stat.h:91
SCIP_CLOCK * solvingtime
Definition: struct_stat.h:160
FILE * vbcfile
Definition: struct_visual.h:51
SCIP_HASHMAP * nodenum
Definition: struct_visual.h:54
SCIP_MESSAGEHDLR * messagehdlr
Definition: struct_visual.h:53
SCIP_VBCCOLOR lastcolor
Definition: struct_visual.h:57
SCIP_Real lastlowerbound
Definition: struct_visual.h:59
SCIP_Bool userealtime
Definition: struct_visual.h:58
SCIP_Longint timestep
Definition: struct_visual.h:55
FILE * bakfile
Definition: struct_visual.h:52
SCIP_NODE * lastnode
Definition: struct_visual.h:56
data structures for output for visualization tools (VBC, BAK)
Definition: heur_padm.c:135
internal methods for branch and bound tree
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_VERBLEVEL_NORMAL
Definition: type_message.h:55
@ SCIP_VERBLEVEL_FULL
Definition: type_message.h:57
@ SCIP_OBJSENSE_MINIMIZE
Definition: type_prob.h:48
@ SCIP_FILECREATEERROR
Definition: type_retcode.h:48
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_NODETYPE_CHILD
Definition: type_tree.h:44
@ SCIP_NODETYPE_PROBINGNODE
Definition: type_tree.h:42
@ SCIP_NODETYPE_FOCUSNODE
Definition: type_tree.h:41
enum SCIP_VBCColor SCIP_VBCCOLOR
Definition: type_visual.h:73
@ SCIP_VBCCOLOR_UNSOLVED
Definition: type_visual.h:64
@ SCIP_VBCCOLOR_MARKREPROP
Definition: type_visual.h:68
@ SCIP_VBCCOLOR_REPROP
Definition: type_visual.h:69
@ SCIP_VBCCOLOR_SOLUTION
Definition: type_visual.h:70
@ SCIP_VBCCOLOR_SOLVED
Definition: type_visual.h:65
@ SCIP_VBCCOLOR_NONE
Definition: type_visual.h:71
@ SCIP_VBCCOLOR_CUTOFF
Definition: type_visual.h:66
@ SCIP_VBCCOLOR_CONFLICT
Definition: type_visual.h:67
SCIP_DOMCHGBOUND domchgbound
Definition: struct_var.h:162
internal methods for problem variables
SCIP_RETCODE SCIPvisualUpdateChild(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:341
void SCIPvisualUpperbound(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_Real upperbound)
Definition: visual.c:805
void SCIPvisualLowerbound(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_Real lowerbound)
Definition: visual.c:768
void SCIPvisualMarkedRepropagateNode(SCIP_VISUAL *visual, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:630
void SCIPvisualFoundSolution(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node, SCIP_Bool bettersol, SCIP_SOL *sol)
Definition: visual.c:669
static void vbcSetColor(SCIP_VISUAL *visual, SCIP_STAT *stat, SCIP_NODE *node, SCIP_VBCCOLOR color)
Definition: visual.c:449
static void getBranchInfo(SCIP_NODE *node, SCIP_VAR **var, SCIP_BOUNDTYPE *boundtype, SCIP_Real *bound)
Definition: visual.c:58
SCIP_RETCODE SCIPvisualNewChild(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:266
void SCIPvisualSolvedNode(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:473
static void printTime(SCIP_VISUAL *visual, SCIP_STAT *stat, SCIP_Bool vbc)
Definition: visual.c:220
void SCIPvisualFree(SCIP_VISUAL **visual)
Definition: visual.c:106
SCIP_RETCODE SCIPvisualInit(SCIP_VISUAL *visual, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr)
Definition: visual.c:120
SCIP_RETCODE SCIPvisualCreate(SCIP_VISUAL **visual, SCIP_MESSAGEHDLR *messagehdlr)
Definition: visual.c:85
void SCIPvisualFoundConflict(SCIP_VISUAL *visual, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:612
void SCIPvisualCutoffNode(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_STAT *stat, SCIP_NODE *node, SCIP_Bool infeasible)
Definition: visual.c:533
void SCIPvisualExit(SCIP_VISUAL *visual, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr)
Definition: visual.c:189
void SCIPvisualRepropagatedNode(SCIP_VISUAL *visual, SCIP_STAT *stat, SCIP_NODE *node)
Definition: visual.c:651
methods for creating output for visualization tools (VBC, BAK)