Scippy

SCIP

Solving Constraint Integer Programs

relax_stpdp.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-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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file relax_stpdp.c
17  * @brief Steiner tree relaxator
18  * @author Daniel Rehfeldt
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 #include "relax_stpdp.h"
26 #include "probdata_stp.h"
27 #include "solstp.h"
28 #include "dpterms.h"
29 #include "dpborder.h"
30 #ifndef NDEBUG
31 #include "substpsolver.h"
32 #endif
33 
34 #define RELAX_NAME "stpdp"
35 #define RELAX_DESC "DP relaxator for STP"
36 #define RELAX_PRIORITY 100000000
37 #define RELAX_FREQ 1
38 
40 
41 
42 /*
43  * Data structures
44  */
45 
46 /** relaxator data */
47 struct SCIP_RelaxData
48 {
49  DPBORDER* dpborder; /**< DP border */
50  enum DP_TYPE mode; /**< DP algo to be used */
51  SCIP_Bool isActive; /**< is the relaxator being used? */
52 };
53 
54 
55 /*
56  * Local methods
57  */
58 
59 
60 /** solves problem with border-FPT DP */
61 static
63  SCIP* scip, /**< SCIP data structure */
64  GRAPH* graph, /**< the graph */
65  DPBORDER* dpborder, /**< DP border algorithm data structure */
66  SCIP_Real* obj, /**< pointer to the objective value (OUT) */
67  SCIP_Bool* wasSolved /**< pointer to mark whether problem was solved (OUT) */
68  )
69 {
70  int* soledges;
71  SCIP_Bool success;
72 
73  SCIP_CALL( SCIPallocMemoryArray(scip, &soledges, graph->edges) );
74 
75  printf("solving problem with DPB... ");
76  graph_printInfo(graph);
77 
78  SCIP_CALL( dpborder_solve(scip, graph, dpborder, soledges, wasSolved) );
79 
80  if( !(*wasSolved) )
81  {
82  printf("...aborted \n");
83 
84  SCIPfreeMemoryArray(scip, &soledges);
85 
86  return SCIP_OKAY;
87  }
88 
89  SCIP_CALL( solstp_addSolToProb(scip, graph, soledges, NULL, &success) );
90 
91  printf("...finished \n");
92 
93  *obj = solstp_getObj(graph, soledges, 0.0);
94 
95  SCIPfreeMemoryArray(scip, &soledges);
96 
97  return SCIP_OKAY;
98 }
99 
100 
101 /** solves problem with terminals-FPT DP */
102 static
104  SCIP* scip, /**< SCIP data structure */
105  GRAPH* graph, /**< the graph */
106  SCIP_Real* obj, /**< pointer to the objective value (OUT) */
107  SCIP_Bool* wasSolved /**< pointer to mark whether problem was solved (OUT) */
108  )
109 {
110  int* soledges;
111  SCIP_Bool success;
112 
113  SCIP_CALL( SCIPallocMemoryArray(scip, &soledges, graph->edges) );
114 
115  printf("solving problem with DP... \n");
116 
117  SCIP_CALL( dpterms_solve(scip, graph, soledges, wasSolved) );
118 
119  if( !(*wasSolved) )
120  {
121  printf("...aborted \n");
122 
123  SCIPfreeMemoryArray(scip, &soledges);
124 
125  return SCIP_OKAY;
126  }
127 
128  SCIP_CALL( solstp_addSolToProb(scip, graph, soledges, NULL, &success) );
129 
130  printf("...finished \n");
131 
132  *obj = solstp_getObj(graph, soledges, 0.0);
133 
134  SCIPfreeMemoryArray(scip, &soledges);
135 
136 #ifndef NDEBUG
137  {
138  SCIP_Real obj_bc;
139  SCIP_CALL( substpsolver_getObjFromGraph(scip, graph, &obj_bc) );
140  assert(EQ(obj_bc, *obj));
141  }
142 #endif
143 
144  return SCIP_OKAY;
145 }
146 
147 
148 /*
149  * Callback methods of relaxator
150  */
151 
152 
153 /** destructor of relaxator to free user data (called when SCIP is exiting) */
154 static
155 SCIP_DECL_RELAXFREE(relaxFreeStpdp)
156 { /*lint --e{715}*/
157  SCIP_RELAXDATA* relaxdata = SCIPrelaxGetData(relax);
158  assert(relaxdata);
159 
160  if( relaxdata->dpborder )
161  dpborder_free(scip, &(relaxdata->dpborder));
162 
163  SCIPfreeMemory(scip, &relaxdata);
164  SCIPrelaxSetData(relax, NULL);
165 
166  return SCIP_OKAY;
167 }
168 
169 
170 /** solving process initialization method of relaxator (called when branch and bound process is about to begin) */
171 static
172 SCIP_DECL_RELAXINITSOL(relaxInitsolStpdp)
173 { /*lint --e{715}*/
174 
175  //SCIP_RELAXDATA* relaxdata = SCIPrelaxGetData(relax);
176  //assert(relaxdata);
177 
178  return SCIP_OKAY;
179 }
180 
181 
182 
183 /** solving process deinitialization method of relaxator (called before branch and bound process data is freed) */
184 static
185 SCIP_DECL_RELAXEXITSOL(relaxExitsolStpdp)
186 { /*lint --e{715}*/
187 
188  return SCIP_OKAY;
189 }
190 
191 
192 /** execution method of relaxator */
193 static
194 SCIP_DECL_RELAXEXEC(relaxExecStpdp)
195 { /*lint --e{715}*/
196  GRAPH* graph;
197  SCIP_RELAXDATA* const relaxdata = SCIPrelaxGetData(relax);
198  SCIP_Bool success;
199 
200  *lowerbound = -SCIPinfinity(scip);
201  *result = SCIP_DIDNOTRUN;
202 
203  if( !relaxdata->isActive )
204  return SCIP_OKAY;
205 
206  graph = SCIPprobdataGetGraph2(scip);
207  assert(graph);
208 
209  if( relaxdata->mode == dp_terms )
210  {
211  SCIP_CALL( solveWithDpTerms(scip, graph, lowerbound, &success) );
212  }
213  else
214  {
215  assert(relaxdata->mode == dp_border);
216  assert(relaxdata->dpborder);
217 
218  SCIP_CALL( solveWithDpBorder(scip, graph, relaxdata->dpborder, lowerbound, &success) );
219  }
220 
221  if( !success )
222  {
223  assert(SCIPisStopped(scip));
224  return SCIP_OKAY;
225  }
226 
227  *result = SCIP_SUCCESS;
228 
229  return SCIP_OKAY;
230 }
231 
232 
233 /*
234  * Interface methods
235  */
236 
237 
238 /** is using the relaxator promising? */
240  SCIP* scip, /**< SCIP data structure */
241  GRAPH* graph /**< graph */
242  )
243 {
244  SCIP_Bool dpbHasPotential;
245  SCIP_RELAX* relax = SCIPfindRelax(scip, "stpdp");
246  SCIP_RELAXDATA* relaxdata = SCIPrelaxGetData(relax);
247 
248  assert(graph);
249  assert(relaxdata);
250  assert(!relaxdata->dpborder);
251 
252  if( dpterms_isPromisingPartly(graph) )
253  {
254  relaxdata->mode = dp_terms;
255  return TRUE;
256  }
257 
258  SCIP_CALL( dpborder_init(scip, graph, &(relaxdata->dpborder)) );
259  SCIP_CALL( dpborder_probePotential(scip, graph, relaxdata->dpborder, &dpbHasPotential) );
260 
261  if( dpbHasPotential )
262  {
263  relaxdata->mode = dp_border;
264  return TRUE;
265  }
266 
267  return FALSE;
268 }
269 
270 
271 /** activates */
273  SCIP* scip /**< SCIP data structure */
274  )
275 {
276  SCIP_RELAX* relax = SCIPfindRelax(scip, "stpdp");
277  SCIP_RELAXDATA* relaxdata = SCIPrelaxGetData(relax);
278 
279  assert(relaxdata);
280 
281  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/TM/initruns", 0) );
282  SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrounds", 0) );
283  SCIP_CALL( SCIPsetIntParam(scip, "heuristics/trivial/freq", -1) );
284  SCIP_CALL( SCIPsetIntParam(scip, "propagating/maxroundsroot", 0) );
285 
286  relaxdata->isActive = TRUE;
287 
288  return SCIP_OKAY;
289 }
290 
291 
292 /** is active? */
294  SCIP* scip /**< SCIP data structure */
295  )
296 {
297  SCIP_RELAX* relax = SCIPfindRelax(scip, "stpdp");
298  SCIP_RELAXDATA* relaxdata = SCIPrelaxGetData(relax);
299 
300  assert(relaxdata);
301 
302  return relaxdata->isActive;
303 }
304 
305 
306 /** creates the relaxator and includes it in SCIP */
308  SCIP* scip /**< SCIP data structure */
309  )
310 {
311  SCIP_RELAXDATA* relaxdata;
312  SCIP_RELAX* relax = NULL;
313 
314  SCIP_CALL( SCIPallocMemory(scip, &relaxdata) );
315 
316  /* include relaxator */
318  relaxExecStpdp, relaxdata) );
319  assert(relax != NULL);
320 
321  SCIP_CALL( SCIPsetRelaxInitsol(scip, relax, relaxInitsolStpdp) );
322  SCIP_CALL( SCIPsetRelaxExitsol(scip, relax, relaxExitsolStpdp) );
323  SCIP_CALL( SCIPsetRelaxFree(scip, relax, relaxFreeStpdp) );
324 
325  relaxdata->isActive = FALSE;
326  relaxdata->mode = dp_terms;
327  relaxdata->dpborder = NULL;
328 
329  return SCIP_OKAY;
330 }
#define RELAX_FREQ
Definition: relax_stpdp.c:37
SCIP_RETCODE solstp_addSolToProb(SCIP *scip, const GRAPH *g, const int *soledge, SCIP_HEUR *heur, SCIP_Bool *success)
Definition: solstp.c:1279
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_RETCODE substpsolver_getObjFromGraph(SCIP *scip, const GRAPH *graph, SCIP_Real *obj)
Definition: substpsolver.c:585
includes methods for Steiner tree problem solutions
#define RELAX_NAME
Definition: relax_stpdp.c:34
SCIP_RETCODE SCIPsetRelaxExitsol(SCIP *scip, SCIP_RELAX *relax, SCIP_DECL_RELAXEXITSOL((*relaxexitsol)))
Definition: scip_relax.c:208
#define FALSE
Definition: def.h:87
static SCIP_RETCODE solveWithDpBorder(SCIP *scip, GRAPH *graph, DPBORDER *dpborder, SCIP_Real *obj, SCIP_Bool *wasSolved)
Definition: relax_stpdp.c:62
SCIP_RETCODE SCIPincludeRelaxBasic(SCIP *scip, SCIP_RELAX **relaxptr, const char *name, const char *desc, int priority, int freq, SCIP_DECL_RELAXEXEC((*relaxexec)), SCIP_RELAXDATA *relaxdata)
Definition: scip_relax.c:94
SCIP_Real SCIPinfinity(SCIP *scip)
Problem data for stp problem.
#define TRUE
Definition: def.h:86
DP_TYPE
Definition: relax_stpdp.c:39
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
Dynamic programming solver for Steiner tree (sub-) problems with small number of terminals.
SCIP_Bool SCIPStpDpRelaxIsActive(SCIP *scip)
Definition: relax_stpdp.c:293
void graph_printInfo(const GRAPH *)
Definition: graph_stats.c:299
SCIP_Bool SCIPStpDpRelaxIsPromising(SCIP *scip, GRAPH *graph)
Definition: relax_stpdp.c:239
#define RELAX_DESC
Definition: relax_stpdp.c:35
SCIP_RETCODE SCIPsetRelaxFree(SCIP *scip, SCIP_RELAX *relax, SCIP_DECL_RELAXFREE((*relaxfree)))
Definition: scip_relax.c:144
#define NULL
Definition: lpi_spx1.cpp:155
Solver for Steiner tree (sub-) problems.
void dpborder_free(SCIP *, DPBORDER **)
#define EQ(a, b)
Definition: portab.h:79
SCIP_RELAXDATA * SCIPrelaxGetData(SCIP_RELAX *relax)
Definition: relax.c:446
#define SCIP_CALL(x)
Definition: def.h:384
static SCIP_RETCODE solveWithDpTerms(SCIP *scip, GRAPH *graph, SCIP_Real *obj, SCIP_Bool *wasSolved)
Definition: relax_stpdp.c:103
#define RELAX_PRIORITY
Definition: relax_stpdp.c:36
SCIP_RETCODE dpterms_solve(SCIP *, GRAPH *, int *, SCIP_Bool *)
Definition: dpterms_base.c:489
#define SCIP_Bool
Definition: def.h:84
static SCIP_DECL_RELAXEXEC(relaxExecStpdp)
Definition: relax_stpdp.c:194
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
SCIP_RETCODE dpborder_solve(SCIP *, GRAPH *, DPBORDER *, int *, SCIP_Bool *)
SCIP_Bool dpterms_isPromisingPartly(const GRAPH *)
Definition: dpterms_base.c:518
void SCIPrelaxSetData(SCIP_RELAX *relax, SCIP_RELAXDATA *relaxdata)
Definition: relax.c:456
SCIP_RETCODE dpborder_init(SCIP *, const GRAPH *, DPBORDER **)
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
Dynamic programming solver for Steiner tree (sub-) problems with small border.
static SCIP_DECL_RELAXEXITSOL(relaxExitsolStpdp)
Definition: relax_stpdp.c:185
struct SCIP_RelaxData SCIP_RELAXDATA
Definition: type_relax.h:38
SCIP_RETCODE SCIPincludeRelaxStpdp(SCIP *scip)
Definition: relax_stpdp.c:307
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
SCIP_RETCODE SCIPStpDpRelaxActivate(SCIP *scip)
Definition: relax_stpdp.c:272
int edges
Definition: graphdefs.h:219
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
SCIP_RETCODE dpborder_probePotential(SCIP *, GRAPH *, DPBORDER *, SCIP_Bool *)
static SCIP_DECL_RELAXINITSOL(relaxInitsolStpdp)
Definition: relax_stpdp.c:172
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
GRAPH * SCIPprobdataGetGraph2(SCIP *scip)
Steiner tree dynamic programming relaxator.
SCIP_RETCODE SCIPsetRelaxInitsol(SCIP *scip, SCIP_RELAX *relax, SCIP_DECL_RELAXINITSOL((*relaxinitsol)))
Definition: scip_relax.c:192
SCIP_RELAX * SCIPfindRelax(SCIP *scip, const char *name)
Definition: scip_relax.c:225
static SCIP_DECL_RELAXFREE(relaxFreeStpdp)
Definition: relax_stpdp.c:155