Scippy

SCIP

Solving Constraint Integer Programs

dptermsinterns.h
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-2022 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file dptermsinterns.h
17  * @brief Dynamic programming internals for Steiner tree (sub-) problems with small number of terminals
18  * @author Daniel Rehfeldt
19  *
20  * Internal methods and data structures for DP.
21  *
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 
27 #ifndef APPLICATIONS_STP_SRC_DPTERMSINTERNS_H_
28 #define APPLICATIONS_STP_SRC_DPTERMSINTERNS_H_
29 
30 #include "scip/scip.h"
31 #include "scip/rbtree.h"
32 #include "graph.h"
33 #include "stpvector.h"
34 #include "stpbitset.h"
35 #include "stpprioqueue.h"
36 
37 //#define STP_DPTERM_USEDA
38 
39 /** dynamic programming search tree */
41 
42 
43 
44 /*
45  * Data structures
46  */
47 
48 
49 /** trace for reconstructing a sub-solution */
50 typedef struct solution_trace
51 {
52  int prevs[2]; /**< marker to get ancestor solutions (0,1,2 ancestors possible) */
53  SCIP_Real cost; /**< solution cost */
54 #ifdef STP_DPTERM_USEDA
55  SCIP_Real redcost; /**< reduced solution cost */
56 #endif
57  int root; /**< solution root */
58 } SOLTRACE;
59 
60 
61 /** sub-solution with extension */
63 {
64  SCIP_RBTREE_HOOKS; /**< for red-black tree */
65  STP_Bitset bitkey; /**< key marking the terminals in sub-solution */
66  STP_Vectype(SOLTRACE) traces; /**< traces of solution */
67 } DPSUBSOL;
68 
69 
70 /** compressed graph with less information */
72 {
73  int* terminals; /**< array of terminals; in {0,1,...,nnodes - 1} */
74  int* nodes_termId; /**< per node: terminal (0,1,..), or -1 if non-terminal */
75  int nnodes; /**< number of nodes */
76  int nedges; /**< number of edges */
77  int nterms; /**< number of terminals */
78 } DPGRAPH;
79 
80 
81 /** additional data */
83 {
84  STP_Vectype(SOLTRACE) global_traces;
85  STP_Vectype(STP_Bitset) global_termbits;
86  STP_Vectype(int) global_termbitscount;
87  STP_Vectype(int) global_starts;
88  int opt_prev[2];
90  int opt_root;
92 } DPMISC;
93 
94 
95 
96 /** reduced cost data */
98 {
103 } DPREDCOST;
104 
105 
106 
107 /** solver */
109 {
110  STP_Vectype(int) solnodes; /**< (final) solution nodes */
111  DPGRAPH* dpgraph; /**< graph */
112  DPSUBSOL* soltree_root; /**< root of solution tree */
113  DPSTREE* dpstree; /**< tree for finding solution combinations */
114  DPMISC* dpmisc; /**< this and that */
115  STP_PQ* solpqueue; /**< sub-solutions */
116  DHEAP* dheap; /**< heap of size nnodes */
117 #ifdef STP_DPTERM_USEDA
118  DPREDCOST* dpredcosts;
119 #endif
120 } DPSOLVER;
121 
122 
123 /*
124  * Macro hacks
125  */
126 
127 
128 /* NOTE: needed to find element in a red-black tree */
129 #define SUBSOL_LT(key,subsol) stpbitset_GT(key, subsol->bitkey)
130 #define SUBSOL_GT(key,subsol) stpbitset_LT(key, subsol->bitkey)
131 
132 static inline
133 SCIP_DEF_RBTREE_FIND(findSubsol, STP_Bitset, DPSUBSOL, SUBSOL_LT, SUBSOL_GT) /*lint !e123*/
134 
135 
136 
137 /*
138  * Inline methods
139  */
140 
141 
142 /** initializes */
143 static inline
144 SCIP_RETCODE dpterms_dpsubsolInit(
145  SCIP* scip, /**< SCIP data structure */
146  DPSUBSOL** subsol /**< solution */
147 )
148 {
149  DPSUBSOL* sub;
150  SCIP_CALL( SCIPallocBlockMemory(scip, subsol) );
151  sub = *subsol;
152  sub->bitkey = NULL;
153  sub->traces = NULL;
154 
155  return SCIP_OKAY;
156 }
157 
158 
159 /** frees */
160 static inline
162  SCIP* scip, /**< SCIP data structure */
163  DPSUBSOL** subsol /**< solution */
164 )
165 {
166  DPSUBSOL* sub = *subsol;
167 
168  if( sub->bitkey )
169  stpbitset_free(scip, &(sub->bitkey));
170 
171  if( sub->traces )
172  {
173  StpVecFree(scip, sub->traces);
174  }
175 
176  SCIPfreeBlockMemory(scip, subsol);
177 }
178 
179 
180 
181 /*
182  *
183  */
184 
185 
186 /* dpterms_util.c
187  */
189 extern STP_Vectype(int) dpterms_collectIntersectsNaive(SCIP*, STP_Bitset, STP_Bitset, DPMISC*);
190 extern SCIP_RETCODE dpterms_streeInit(SCIP*, int, int, DPSTREE**);
191 extern void dpterms_streeFree(SCIP*, DPSTREE**);
193 extern STP_Vectype(int) dpterms_streeCollectIntersects(SCIP*, STP_Bitset, STP_Bitset, DPSTREE*);
194 
195 
196 /* dpterms_core.c
197  */
199 
200 
201 
202 #endif /* APPLICATIONS_STP_SRC_DPTERMSINTERNS_H_ */
SCIP_Bool dpterms_intersectsEqualNaive(SCIP *, STP_Bitset, STP_Bitset, STP_Vectype(int), DPMISC *)
Definition: dpterms_util.c:340
struct solution_trace SOLTRACE
SCIP_Real cost
struct dynamic_programming_subsolution DPSUBSOL
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
struct dynamic_programming_misc DPMISC
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
struct dynamic_programming_solver DPSOLVER
header only, simple implementation of an STL like vector
return SCIP_OKAY
STP_Bitset
priority queue with integer keys
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
#define SUBSOL_LT(key, subsol)
header only, simple implementation of a bitset
#define SCIP_Bool
Definition: def.h:84
static void dpterms_dpsubsolFree(SCIP *scip, DPSUBSOL **subsol)
struct dynamic_programming_graph DPGRAPH
#define SUBSOL_GT(key, subsol)
struct dynamic_programming_reduced_costs DPREDCOST
static void stpbitset_free(SCIP *scip, STP_Bitset *bitset)
Definition: stpbitset.h:100
sub traces
static SCIP_DEF_RBTREE_FIND(findSubsol, STP_Bitset, DPSUBSOL, SUBSOL_LT, SUBSOL_GT) static inline SCIP_RETCODE dpterms_dpsubsolInit(SCIP *scip
DPSTREE *SCIP_RETCODE dpterms_coreSolve(SCIP *, GRAPH *, DPSOLVER *, SCIP_Bool *)
SCIP_RETCODE dpterms_streeInsert(SCIP *, STP_Bitset, STP_Bitset, int64_t, DPSTREE *)
Definition: dpterms_util.c:449
#define SCIP_Real
Definition: def.h:177
#define StpVecFree(scip, vec)
Definition: stpvector.h:149
static DPSUBSOL ** subsol
intrusive red black tree datastructure
DPMISC *SCIP_RETCODE dpterms_streeInit(SCIP *, int, int, DPSTREE **)
Definition: dpterms_util.c:533
void dpterms_streeFree(SCIP *, DPSTREE **)
Definition: dpterms_util.c:560
SCIPallocBlockMemory(scip, subsol))
STP_Vectype(int) dpterms_collectIntersectsNaive(SCIP *
SCIP callable library.