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