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-2016 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 email to 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 <assert.h>
24 #include <string.h>
25 
26 #include "scip/nodesel_dfs.h"
27 
28 
29 #define NODESEL_NAME "dfs"
30 #define NODESEL_DESC "depth first search"
31 #define NODESEL_STDPRIORITY 0
32 #define NODESEL_MEMSAVEPRIORITY 100000
33 
34 
35 /*
36  * Callback methods
37  */
38 
39 /** copy method for node selector plugins (called when SCIP copies plugins) */
40 static
41 SCIP_DECL_NODESELCOPY(nodeselCopyDfs)
42 { /*lint --e{715}*/
43  assert(scip != NULL);
44  assert(nodesel != NULL);
45  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
46 
47  /* call inclusion method of node selector */
49 
50  return SCIP_OKAY;
51 }
52 
53 
54 /** node selection method of node selector */
55 static
56 SCIP_DECL_NODESELSELECT(nodeselSelectDfs)
57 { /*lint --e{715}*/
58  assert(nodesel != NULL);
59  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
60  assert(scip != NULL);
61  assert(selnode != NULL);
62 
63  *selnode = SCIPgetPrioChild(scip);
64  if( *selnode == NULL )
65  {
66  *selnode = SCIPgetPrioSibling(scip);
67  if( *selnode == NULL )
68  {
69  SCIPdebugMessage("select best leaf\n");
70  *selnode = SCIPgetBestLeaf(scip);
71  }
72 
73  SCIPdebugMessage("select best sibling leaf\n");
74  }
75 
76  return SCIP_OKAY;
77 }
78 
79 
80 /** node comparison method of node selector */
81 static
82 SCIP_DECL_NODESELCOMP(nodeselCompDfs)
83 { /*lint --e{715}*/
84  int depth1;
85  int depth2;
86 
87  assert(nodesel != NULL);
88  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
89  assert(scip != NULL);
90 
91  depth1 = SCIPnodeGetDepth(node1);
92  depth2 = SCIPnodeGetDepth(node2);
93  if( depth1 > depth2 )
94  return -1;
95  else if( depth1 < depth2 )
96  return +1;
97  else
98  {
99  SCIP_Real lowerbound1;
100  SCIP_Real lowerbound2;
101 
102  lowerbound1 = SCIPnodeGetLowerbound(node1);
103  lowerbound2 = SCIPnodeGetLowerbound(node2);
104  if( lowerbound1 < lowerbound2 )
105  return -1;
106  else if( lowerbound1 > lowerbound2 )
107  return +1;
108  else
109  return 0;
110  }
111 }
112 
113 
114 /*
115  * dfs specific interface methods
116  */
117 
118 /** creates the node selector for depth first search and includes it in SCIP */
120  SCIP* scip /**< SCIP data structure */
121  )
122 {
123  SCIP_NODESELDATA* nodeseldata;
124  SCIP_NODESEL* nodesel;
125 
126  /* create dfs node selector data */
127  nodeseldata = NULL;
128 
129  /* include node selector */
131  nodeselSelectDfs, nodeselCompDfs, nodeseldata) );
132 
133  assert(nodesel != NULL);
134 
135  SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyDfs) );
136 
137  return SCIP_OKAY;
138 }
139 
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition: scip.c:36986
static SCIP_DECL_NODESELSELECT(nodeselSelectDfs)
Definition: nodesel_dfs.c:56
#define NODESEL_STDPRIORITY
Definition: nodesel_dfs.c:31
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip.c:8028
#define NULL
Definition: lpi_spx.cpp:130
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7026
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIP_CALL(x)
Definition: def.h:266
#define SCIPdebugMessage
Definition: pub_message.h:77
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.c:7992
SCIP_RETCODE SCIPincludeNodeselDfs(SCIP *scip)
Definition: nodesel_dfs.c:119
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip.c:37034
struct SCIP_NodeselData SCIP_NODESELDATA
Definition: type_nodesel.h:38
static SCIP_DECL_NODESELCOMP(nodeselCompDfs)
Definition: nodesel_dfs.c:82
#define NODESEL_DESC
Definition: nodesel_dfs.c:30
#define NODESEL_NAME
Definition: nodesel_dfs.c:29
static SCIP_DECL_NODESELCOPY(nodeselCopyDfs)
Definition: nodesel_dfs.c:41
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:992
#define NODESEL_MEMSAVEPRIORITY
Definition: nodesel_dfs.c:32
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip.c:36970
#define SCIP_Real
Definition: def.h:127
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7036
node selector for depth first search