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-2017 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  SCIPdebugMsg(scip, "select best leaf\n");
70  *selnode = SCIPgetBestLeaf(scip);
71  }
72 
73  SCIPdebugMsg(scip, "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_NODESEL* nodesel;
124 
125  /* include node selector */
127  nodeselSelectDfs, nodeselCompDfs, NULL) );
128 
129  assert(nodesel != NULL);
130 
131  SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyDfs) );
132 
133  return SCIP_OKAY;
134 }
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip.c:8776
static SCIP_DECL_NODESELSELECT(nodeselSelectDfs)
Definition: nodesel_dfs.c:56
#define NODESEL_STDPRIORITY
Definition: nodesel_dfs.c:31
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7163
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:8740
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7153
#define SCIPdebugMsg
Definition: scip.h:451
static SCIP_DECL_NODESELCOMP(nodeselCompDfs)
Definition: nodesel_dfs.c:82
#define NODESEL_DESC
Definition: nodesel_dfs.c:30
#define NULL
Definition: lpi_spx1.cpp:137
#define SCIP_CALL(x)
Definition: def.h:306
#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:993
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition: scip.c:40666
#define NODESEL_MEMSAVEPRIORITY
Definition: nodesel_dfs.c:32
#define SCIP_Real
Definition: def.h:135
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip.c:40650
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition: scip.c:40714
SCIP_RETCODE SCIPincludeNodeselDfs(SCIP *scip)
Definition: nodesel_dfs.c:119
node selector for depth first search