Scippy

SCIP

Solving Constraint Integer Programs

nodesel_dfs.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file nodesel_dfs.c
17  * @brief node selector for depth first search
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include "scip/nodesel_dfs.h"
24 #include "scip/pub_message.h"
25 #include "scip/pub_nodesel.h"
26 #include "scip/pub_tree.h"
27 #include "scip/scip_message.h"
28 #include "scip/scip_nodesel.h"
29 #include "scip/scip_tree.h"
30 #include <string.h>
31 
32 #define NODESEL_NAME "dfs"
33 #define NODESEL_DESC "depth first search"
34 #define NODESEL_STDPRIORITY 0
35 #define NODESEL_MEMSAVEPRIORITY 100000
36 
37 
38 /*
39  * Callback methods
40  */
41 
42 /** copy method for node selector plugins (called when SCIP copies plugins) */
43 static
44 SCIP_DECL_NODESELCOPY(nodeselCopyDfs)
45 { /*lint --e{715}*/
46  assert(scip != NULL);
47  assert(nodesel != NULL);
48  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
49 
50  /* call inclusion method of node selector */
52 
53  return SCIP_OKAY;
54 }
55 
56 
57 /** node selection method of node selector */
58 static
59 SCIP_DECL_NODESELSELECT(nodeselSelectDfs)
60 { /*lint --e{715}*/
61  assert(nodesel != NULL);
62  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
63  assert(scip != NULL);
64  assert(selnode != NULL);
65 
66  *selnode = SCIPgetPrioChild(scip);
67  if( *selnode == NULL )
68  {
69  *selnode = SCIPgetPrioSibling(scip);
70  if( *selnode == NULL )
71  {
72  SCIPdebugMsg(scip, "select best leaf\n");
73  *selnode = SCIPgetBestLeaf(scip);
74  }
75 
76  SCIPdebugMsg(scip, "select best sibling leaf\n");
77  }
78 
79  return SCIP_OKAY;
80 }
81 
82 
83 /** node comparison method of node selector */
84 static
85 SCIP_DECL_NODESELCOMP(nodeselCompDfs)
86 { /*lint --e{715}*/
87  int depth1;
88  int depth2;
89 
90  assert(nodesel != NULL);
91  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
92  assert(scip != NULL);
93 
94  depth1 = SCIPnodeGetDepth(node1);
95  depth2 = SCIPnodeGetDepth(node2);
96  if( depth1 > depth2 )
97  return -1;
98  else if( depth1 < depth2 )
99  return +1;
100  else
101  {
102  SCIP_Real lowerbound1;
103  SCIP_Real lowerbound2;
104 
105  lowerbound1 = SCIPnodeGetLowerbound(node1);
106  lowerbound2 = SCIPnodeGetLowerbound(node2);
107  if( lowerbound1 < lowerbound2 )
108  return -1;
109  else if( lowerbound1 > lowerbound2 )
110  return +1;
111  else
112  return 0;
113  }
114 }
115 
116 
117 /*
118  * dfs specific interface methods
119  */
120 
121 /** creates the node selector for depth first search and includes it in SCIP */
123  SCIP* scip /**< SCIP data structure */
124  )
125 {
126  SCIP_NODESEL* nodesel;
127 
128  /* include node selector */
130  nodeselSelectDfs, nodeselCompDfs, NULL) );
131 
132  assert(nodesel != NULL);
133 
134  SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyDfs) );
135 
136  return SCIP_OKAY;
137 }
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:208
#define NULL
Definition: def.h:239
static SCIP_DECL_NODESELSELECT(nodeselSelectDfs)
Definition: nodesel_dfs.c:59
public methods for branch and bound tree
#define NODESEL_STDPRIORITY
Definition: nodesel_dfs.c:34
public methods for node selector plugins
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7364
SCIP_RETCODE SCIPincludeNodeselBasic(SCIP *scip, SCIP_NODESEL **nodesel, const char *name, const char *desc, int stdpriority, int memsavepriority, SCIP_DECL_NODESELSELECT((*nodeselselect)), SCIP_DECL_NODESELCOMP((*nodeselcomp)), SCIP_NODESELDATA *nodeseldata)
Definition: scip_nodesel.c:173
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7354
#define SCIPdebugMsg
Definition: scip_message.h:88
public methods for the branch-and-bound tree
static SCIP_DECL_NODESELCOMP(nodeselCompDfs)
Definition: nodesel_dfs.c:85
#define NODESEL_DESC
Definition: nodesel_dfs.c:33
#define SCIP_CALL(x)
Definition: def.h:351
#define NODESEL_NAME
Definition: nodesel_dfs.c:32
static SCIP_DECL_NODESELCOPY(nodeselCopyDfs)
Definition: nodesel_dfs.c:44
public methods for node selectors
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1038
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition: scip_tree.c:371
#define NODESEL_MEMSAVEPRIORITY
Definition: nodesel_dfs.c:35
public methods for message output
#define SCIP_Real
Definition: def.h:150
public methods for message handling
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip_tree.c:355
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip_tree.c:419
SCIP_RETCODE SCIPincludeNodeselDfs(SCIP *scip)
Definition: nodesel_dfs.c:122
node selector for depth first search