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-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 nodesel_dfs.c
17  * @ingroup DEFPLUGINS_NODESEL
18  * @brief node selector for depth first search
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "scip/nodesel_dfs.h"
25 #include "scip/pub_message.h"
26 #include "scip/pub_nodesel.h"
27 #include "scip/pub_tree.h"
28 #include "scip/scip_message.h"
29 #include "scip/scip_nodesel.h"
30 #include "scip/scip_tree.h"
31 #include <string.h>
32 
33 #define NODESEL_NAME "dfs"
34 #define NODESEL_DESC "depth first search"
35 #define NODESEL_STDPRIORITY 0
36 #define NODESEL_MEMSAVEPRIORITY 100000
37 
38 
39 /*
40  * Callback methods
41  */
42 
43 /** copy method for node selector plugins (called when SCIP copies plugins) */
44 static
45 SCIP_DECL_NODESELCOPY(nodeselCopyDfs)
46 { /*lint --e{715}*/
47  assert(scip != NULL);
48  assert(nodesel != NULL);
49  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
50 
51  /* call inclusion method of node selector */
53 
54  return SCIP_OKAY;
55 }
56 
57 
58 /** node selection method of node selector */
59 static
60 SCIP_DECL_NODESELSELECT(nodeselSelectDfs)
61 { /*lint --e{715}*/
62  assert(nodesel != NULL);
63  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
64  assert(scip != NULL);
65  assert(selnode != NULL);
66 
67  *selnode = SCIPgetPrioChild(scip);
68  if( *selnode == NULL )
69  {
70  *selnode = SCIPgetPrioSibling(scip);
71  if( *selnode == NULL )
72  {
73  SCIPdebugMsg(scip, "select best leaf\n");
74  *selnode = SCIPgetBestLeaf(scip);
75  }
76 
77  SCIPdebugMsg(scip, "select best sibling leaf\n");
78  }
79 
80  return SCIP_OKAY;
81 }
82 
83 
84 /** node comparison method of node selector */
85 static
86 SCIP_DECL_NODESELCOMP(nodeselCompDfs)
87 { /*lint --e{715}*/
88  int depth1;
89  int depth2;
90 
91  assert(nodesel != NULL);
92  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
93  assert(scip != NULL);
94 
95  depth1 = SCIPnodeGetDepth(node1);
96  depth2 = SCIPnodeGetDepth(node2);
97  if( depth1 > depth2 )
98  return -1;
99  else if( depth1 < depth2 )
100  return +1;
101  else
102  {
103  SCIP_Real lowerbound1;
104  SCIP_Real lowerbound2;
105 
106  lowerbound1 = SCIPnodeGetLowerbound(node1);
107  lowerbound2 = SCIPnodeGetLowerbound(node2);
108  if( lowerbound1 < lowerbound2 )
109  return -1;
110  else if( lowerbound1 > lowerbound2 )
111  return +1;
112  else
113  return 0;
114  }
115 }
116 
117 
118 /*
119  * dfs specific interface methods
120  */
121 
122 /** creates the node selector for depth first search and includes it in SCIP */
124  SCIP* scip /**< SCIP data structure */
125  )
126 {
127  SCIP_NODESEL* nodesel;
128 
129  /* include node selector */
131  nodeselSelectDfs, nodeselCompDfs, NULL) );
132 
133  assert(nodesel != NULL);
134 
135  SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyDfs) );
136 
137  return SCIP_OKAY;
138 }
static SCIP_DECL_NODESELSELECT(nodeselSelectDfs)
Definition: nodesel_dfs.c:60
public methods for branch and bound tree
#define NODESEL_STDPRIORITY
Definition: nodesel_dfs.c:35
public methods for node selector plugins
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip_tree.c:342
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:129
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition: scip_tree.c:294
SCIP_EXPORT int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7430
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_EXPORT SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7440
#define SCIPdebugMsg
Definition: scip_message.h:69
public methods for the branch-and-bound tree
static SCIP_DECL_NODESELCOMP(nodeselCompDfs)
Definition: nodesel_dfs.c:86
#define NODESEL_DESC
Definition: nodesel_dfs.c:34
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip_tree.c:278
#define NODESEL_NAME
Definition: nodesel_dfs.c:33
static SCIP_DECL_NODESELCOPY(nodeselCopyDfs)
Definition: nodesel_dfs.c:45
public methods for node selectors
SCIP_RETCODE SCIPincludeNodeselDfs(SCIP *scip)
Definition: nodesel_dfs.c:123
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:94
#define NODESEL_MEMSAVEPRIORITY
Definition: nodesel_dfs.c:36
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1043
public methods for message output
#define SCIP_Real
Definition: def.h:163
public methods for message handling
node selector for depth first search