Scippy

SCIP

Solving Constraint Integer Programs

dualascent.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 dualascent.h
17  * @brief Includes dual-ascent for classic Steiner tree and some variants.
18  * @author Daniel Rehfeldt
19  *
20  *
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #ifndef APPLICATIONS_STP_SRC_DUALASCENT_H_
26 #define APPLICATIONS_STP_SRC_DUALASCENT_H_
27 
28 #include "scip/scip.h"
29 #include "graph.h"
30 
31 
32 #ifdef __cplusplus
33 extern "C" {
34 #endif
35 
36 
37 
38 /** reduced cost parameters */
39 typedef struct reduce_cost_parameters
40 {
41  SCIP_Bool addcuts; /**< should dual ascent add Steiner cuts? */
42  SCIP_Bool ascendandprune; /**< should the ascent-and-prune heuristic be executed? */
43  int root; /**< the root */
44  SCIP_Bool is_pseudoroot; /**< is the root a pseudo root? */
45  SCIP_Real damaxdeviation; /**< maximum deviation for dual-ascent ( -1.0 for default) */
46 } DAPARAMS;
47 
48 
49 /** dual ascent heuristic */
51  SCIP* scip, /**< SCIP data structure */
52  const GRAPH* g, /**< graph data structure */
53  const int* result, /**< solution array or NULL */
54  const DAPARAMS* daparams, /**< parameter */
55  SCIP_Real* RESTRICT redcost, /**< array to store reduced costs or NULL */
56  SCIP_Real* objval /**< pointer to store objective value */
57  );
58 
59 
60 /** dual-ascent for reduced costs */
62  SCIP* scip, /**< SCIP data structure */
63  const GRAPH* g, /**< graph data structure */
64  const int* result, /**< solution array or NULL */
65  const DAPARAMS* daparams, /**< parameter */
66  SCIP_Real* RESTRICT redcost, /**< array to store reduced costs or NULL */
67  SCIP_Real* objval
68  );
69 
70 
71 /** updates reduced costs with dual ascent heuristic */
73  SCIP* scip, /**< SCIP data structure */
74  const GRAPH* g, /**< graph data structure */
75  const int* result, /**< solution array or NULL */
76  const DAPARAMS* daparams, /**< parameter */
77  SCIP_Real* RESTRICT redcost, /**< array to store reduced costs */
78  SCIP_Real* objval /**< pointer to store objective value */
79 );
80 
81 
82 /** dual ascent heuristic for the PCSPG and the MWCSP */
84  SCIP* scip, /**< SCIP data structure */
85  GRAPH* g, /**< graph data structure */
86  SCIP_Real* redcost, /**< array to store reduced costs or NULL */
87  SCIP_Real* objval, /**< pointer to store objective value */
88  SCIP_Bool addcuts, /**< should dual ascent add Steiner cuts? */
89  SCIP_Bool ascendandprune, /**< perform ascend-and-prune and add solution? */
90  int nruns /**< number of dual ascent runs */
91  );
92 
93 
94 /** path based dual ascent heuristic */
96  SCIP* scip, /**< SCIP data structure */
97  const GRAPH* transgraph, /**< transformed SAP graph */
98  SCIP_Real* RESTRICT redcost, /**< array to store reduced costs */
99  SCIP_Real* objval, /**< pointer to store (dual) objective value */
100  const int* result /**< solution array or NULL */
101  );
102 
103 
104 /** path based dual ascent heuristic */
106  SCIP* scip, /**< SCIP data structure */
107  GRAPH* graph, /**< graph */
108  SCIP_Real* RESTRICT redcost, /**< array to store reduced costs */
109  SCIP_Real* objval, /**< pointer to store (dual) objective value */
110  const int* result /**< solution array or NULL */
111  );
112 
113 
114 /** can all terminal be reached via reduced costs from given root? */
116  SCIP* scip, /**< SCIP */
117  const GRAPH* g, /**< graph */
118  int root, /**< root for reduced costs */
119  const SCIP_Real* redcost /**< reduced costs */
120 );
121 
122 
123 
124 #ifdef __cplusplus
125 }
126 #endif
127 
128 
129 #endif /* APPLICATIONS_STP_SRC_DUALASCENT_H_ */
struct reduce_cost_parameters DAPARAMS
SCIP_RETCODE dualascent_execDegCons(SCIP *scip, const GRAPH *g, const int *result, const DAPARAMS *daparams, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:1256
SCIP_Real damaxdeviation
Definition: dualascent.h:45
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE dualascent_paths(SCIP *scip, GRAPH *graph, SCIP_Real *RESTRICT redcost, SCIP_Real *objval, const int *result)
Definition: dualascent.c:1803
SCIP_RETCODE dualascent_execPcMw(SCIP *scip, GRAPH *g, SCIP_Real *redcost, SCIP_Real *objval, SCIP_Bool addcuts, SCIP_Bool ascendandprune, int nruns)
Definition: dualascent.c:1319
SCIP_Bool is_pseudoroot
Definition: dualascent.h:44
SCIP_Bool dualascent_allTermsReachable(SCIP *scip, const GRAPH *g, int root, const SCIP_Real *redcost)
Definition: dualascent.c:1835
SCIP_RETCODE dualascent_pathsPcMw(SCIP *scip, const GRAPH *transgraph, SCIP_Real *RESTRICT redcost, SCIP_Real *objval, const int *result)
Definition: dualascent.c:1780
#define SCIP_Bool
Definition: def.h:84
SCIP_Bool ascendandprune
Definition: dualascent.h:42
SCIP_RETCODE dualascent_update(SCIP *scip, const GRAPH *g, const int *result, const DAPARAMS *daparams, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:1225
#define SCIP_Real
Definition: def.h:177
SCIP_RETCODE dualascent_exec(SCIP *scip, const GRAPH *g, const int *result, const DAPARAMS *daparams, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:1191
SCIP callable library.