Scippy

SCIP

Solving Constraint Integer Programs

reducedefs.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 reducedefs.h
17  * @brief includes reductions definitions and inline methods used for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  *
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 
26 
27 #ifndef APPLICATIONS_STP_SRC_REDUCEDEFS_H_
28 #define APPLICATIONS_STP_SRC_REDUCEDEFS_H_
29 
30 #include "scip/scip.h"
31 #include "portab.h"
32 
33 
34 #ifdef __cplusplus
35 extern "C" {
36 #endif
37 
38 
39 #define STP_REDUCTION_NONE 0
40 #define STP_REDUCTION_BASIC 1
41 #define STP_REDUCTION_ADVANCED 2
42 
43 #define STP_DAMODE_HOPS -9991
44 #define STP_DAMODE_FAST 0
45 #define STP_DAMODE_MEDIUM 1
46 #define STP_DAMODE_EXTENSIVE 2
47 
48 
49 /** lightweight minimum spanning tree structure that allows to add vertices to given MST on complete graph (in CSR format) */
51 
52 /** auxiliary data structure for ruling out all 1-hop stars of a given node */
53 typedef struct node_one_hop_star STAR;
54 
55 /** SD distance graph data */
57 
58 /** SD neighbors */
60 
61 /** link-cut tree for bottleneck operations */
63 
64 /** primal solution data retained during reduction process */
66 
67 /** INTERNAL primal solution data retained during reduction loop */
69 
70 
72 
73 
74 /** reduction parameters */
75 typedef struct reduction_parameters
76 {
77  SCIP_Bool dualascent; /**< do dual-ascent reduction? */
78  SCIP_Bool boundreduce; /**< do bound-based reduction? */
79  SCIP_Bool nodereplacing; /**< should node replacement (by edges) be performed? */
80  int reductbound; /**< minimal number of edges to be eliminated in order to reiterate reductions */
81  int reductbound_min; /**< absolute minimum */
82  SCIP_Bool userec; /**< use recombination heuristic? */
83  SCIP_Bool fullreduce; /**< use full reductions? (including extended techniques) */
84  SCIP_Bool usestrongreds; /**< allow strong reductions? */
85 } RPARAMS;
86 
87 
88 // todo: parameter so that after restart only standard SD is performed...
89 // todo: need to adapt reductbound?? make smaller... */
90 /** bi-decomposition reduction parameters */
92 {
93  int depth; /**< current depth */
94  int maxdepth; /**< maximum recursive depth of decomposition */
95  SCIP_Bool newLevelStarted; /**< no level? */
96 } BIDECPARAMS;
97 
98 
99 /** reduction information and some buffers */
100 typedef struct reduction_base
101 {
102  RPARAMS* redparameters; /**< parameters */
103  BIDECPARAMS* bidecompparams; /**< bidecomposition parameters or NULL */
104  int* solnode; /**< solution nodes array (or NULL) */
105  REDSOL* redsol; /**< primal solution container */
106  /* buffer: */
110  int* heap;
111  int* state;
112  int* vbase;
117 } REDBASE;
118 
119 
120 
121 /** Stores data for computation of special distance/bottleneck distance computations */
123 {
124  SDPROFIT* sdprofit; /**< SD bias for nodes (or NULL) */
125  SDGRAPH* sdgraph; /**< special distance graph on terminals */
126  TPATHS* terminalpaths; /**< terminal paths */
127  SDN* sdneighbors; /**< neighbors */
128  BLCTREE* blctree; /**< bottleneck tree (or NULL) */
129  SCIP_Bool isBiased; /**< are the SDs biased? */
130  SCIP_Bool hasNeigborUpdate; /**< with neighbor update? NOTE: does not allow certain methods */
131 } SD;
132 
133 
134 /** lightweight store for implied profit */
136 {
137  SCIP_Real* RESTRICT nodes_bias; /**< bias per node */
138  SCIP_Real* RESTRICT nodes_bias2; /**< second best bias per node */
139  int* RESTRICT nodes_biassource; /**< source terminal per node */
140  int* RESTRICT nodes_biassource2; /**< second source terminal per node */
141 };
142 
143 
144 /** reduced cost reduction parameters */
146 {
147  int damode; /**< mode */
148  enum EXTRED_MODE extredMode; /**< mode of extended reductions */
149  SCIP_Bool useRec; /**< use recombination heuristic? */
150  SCIP_Bool useSlackPrune; /**< use slack-prune heuristic? */
151  SCIP_Bool nodereplacing; /**< should node replacement (by edges) be performed? */
152  /* PC/MW only values: */
153  SCIP_Bool pcmw_solbasedda; /**< rerun Da based on best primal solution */
154  SCIP_Bool pcmw_useMultRoots; /**< vary root for DA? (if possible) */
155  SCIP_Bool pcmw_markroots; /**< should terminals proven to be part of an opt. sol. be marked as such? */
156  SCIP_Bool pcmw_fastDa; /**< run dual ascent heuristic in fast mode? */
157 } RPDA;
158 
159 
160 /** single special distance for PC */
162 {
165  int* heap;
166  int* statetail;
167  int* statehead;
172 } SD1PC;
173 
174 
175 
176 /** gets profit for given node */
177 inline static
179  const SDPROFIT* sdprofit, /**< the SD profit */
180  int node, /**< node to get profit for */
181  int nonsource1, /**< node that should not be a source */
182  int nonsource2 /**< node that should not be a source */
183 )
184 {
185  const int source1 = sdprofit->nodes_biassource[node];
186 
187  assert(nonsource1 != nonsource2 || nonsource1 == -1);
188  assert(GE(sdprofit->nodes_bias[node], 0.0));
189  assert(LE(sdprofit->nodes_bias[node], FARAWAY));
190  assert(GE(sdprofit->nodes_bias2[node], 0.0));
191  assert(LE(sdprofit->nodes_bias2[node], FARAWAY));
192  assert(GE(sdprofit->nodes_bias[node], sdprofit->nodes_bias2[node]));
193 
194  if( source1 != nonsource1 && source1 != nonsource2 )
195  {
196  return sdprofit->nodes_bias[node];
197  }
198  else
199  {
200  const int source2 = sdprofit->nodes_biassource2[node];
201 
202  if( source2 != nonsource1 && source2 != nonsource2 )
203  {
204  return sdprofit->nodes_bias2[node];
205  }
206  }
207 
208  return 0.0;
209 }
210 
211 
212 /** gets biased distance */
213 inline static
215  const SDPROFIT* sdprofit, /**< the SD profit */
216  int node, /**< node along which to get biased distance */
217  SCIP_Real edgecost, /**< edge cost */
218  SCIP_Real nodedist, /**< node distance */
219  int nonsource1, /**< node that should not be a source */
220  int nonsource2 /**< node that should not be a source */
221 )
222 {
223  SCIP_Real distnew = nodedist + edgecost;
224  const SCIP_Real profit = reduce_sdprofitGetProfit(sdprofit, node, nonsource1, nonsource2);
225  SCIP_Real bias = MIN(edgecost, profit);
226  if( nodedist < bias )
227  bias = nodedist;
228 
229  distnew -= bias;
230 
231  assert(GE(profit, 0.0));
232  assert(GE(bias, 0.0));
233  assert(GE(edgecost, 0.0));
234  assert(GE(nodedist, 0.0));
235  assert(GE(distnew, 0.0));
236 
237  return distnew;
238 }
239 
240 
241 
242 #ifdef __cplusplus
243 }
244 #endif
245 
246 
247 #endif /* APPLICATIONS_STP_SRC_REDUCEDEFS_H_ */
int * edgearrint
Definition: reducedefs.h:114
SCIP_Real * nodearrreal
Definition: reducedefs.h:109
SCIP_Bool fullreduce
Definition: reducedefs.h:83
int * nodearrint
Definition: reducedefs.h:113
int * nodearrint2
Definition: reducedefs.h:115
struct reduce_costs_reduction_parameters RPDA
struct bidecomposition_reduction_parameters BIDECPARAMS
#define FARAWAY
Definition: graphdefs.h:89
struct reduction_parameters RPARAMS
#define LE(a, b)
Definition: portab.h:83
#define GE(a, b)
Definition: portab.h:85
SCIP_Bool usestrongreds
Definition: reducedefs.h:84
SCIP_Bool boundreduce
Definition: reducedefs.h:78
SCIP_Bool dualascent
Definition: reducedefs.h:77
struct single_special_distance_pc SD1PC
unsigned char STP_Bool
Definition: portab.h:34
struct special_distance_storage SD
static SCIP_Real reduce_sdprofitGetProfit(const SDPROFIT *sdprofit, int node, int nonsource1, int nonsource2)
Definition: reducedefs.h:178
#define SCIP_Bool
Definition: def.h:84
STP_Bool * nodearrchar
Definition: reducedefs.h:116
REDSOL * redsol
Definition: reducedefs.h:105
struct reduction_base REDBASE
SCIP_Real *RESTRICT nodes_bias2
Definition: reducedefs.h:138
Portable definitions.
SCIP_Real *RESTRICT nodes_bias
Definition: reducedefs.h:137
EXTRED_MODE
Definition: reducedefs.h:71
#define SCIP_Real
Definition: def.h:177
static SCIP_Real reduce_sdprofitGetBiasedDist(const SDPROFIT *sdprofit, int node, SCIP_Real edgecost, SCIP_Real nodedist, int nonsource1, int nonsource2)
Definition: reducedefs.h:214
BIDECPARAMS * bidecompparams
Definition: reducedefs.h:103
RPARAMS * redparameters
Definition: reducedefs.h:102
SCIP_Bool nodereplacing
Definition: reducedefs.h:79
SCIP callable library.