SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-2024 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) */
53static
55{ /*lint --e{715}*/
56 assert(scip != NULL);
57 assert(nodesel != NULL);
59
60 /* call inclusion method of node selector */
62
63 return SCIP_OKAY;
64}
65
66
67/** node selection method of node selector */
68static
70{ /*lint --e{715}*/
71 assert(nodesel != NULL);
73 assert(scip != NULL);
75
77 if( *selnode == NULL )
78 {
80 if( *selnode == NULL )
81 {
82 SCIPdebugMsg(scip, "select best leaf\n");
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 */
94static
96{ /*lint --e{715}*/
97 int depth1;
98 int depth2;
99
100 assert(nodesel != NULL);
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
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 */
141
142 assert(nodesel != NULL);
143
145
146 return SCIP_OKAY;
147}
#define NULL
Definition def.h:267
#define SCIP_CALL(x)
Definition def.h:374
#define SCIPdebugMsg
SCIP_RETCODE SCIPincludeNodeselDfs(SCIP *scip)
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition tree.c:7510
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition tree.c:7500
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)
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel,)
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition nodesel.c:1052
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition scip_tree.c:304
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition scip_tree.c:288
SCIP_NODE * SCIPgetBestLeaf(SCIP *scip)
Definition scip_tree.c:352
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
#define NODESEL_NAME
Definition nodesel_dfs.c:42
#define NODESEL_MEMSAVEPRIORITY
Definition nodesel_dfs.c:45
#define NODESEL_STDPRIORITY
Definition nodesel_dfs.c:44
#define NODESEL_DESC
Definition nodesel_dfs.c:43
node selector for depth first search
public methods for message output
public methods for node selectors
public methods for branch and bound tree
public methods for message handling
public methods for node selector plugins
public methods for the branch-and-bound tree
#define SCIP_DECL_NODESELCOMP(x)
#define SCIP_DECL_NODESELCOPY(x)
#define SCIP_DECL_NODESELSELECT(x)
enum SCIP_Retcode SCIP_RETCODE