Scippy

SCIP

Solving Constraint Integer Programs

reader_stp.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 reader_stp.c
17  * @brief Steiner tree problem file reader
18  * @author Gerald Gamrath
19  * @author Thorsten Koch
20  * @author Daniel Rehfeldt
21  * @author Michael Winkler
22  *
23  * This file implements the reader used to read and write Steiner tree problems.
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 #include <assert.h>
29 #include <string.h>
30 
31 #include "probdata_stp.h"
32 #include "reader_stp.h"
33 #include "reduce.h"
34 #include "graph.h"
35 
36 
37 /**@name Reader properties
38  *
39  * @{
40  */
41 
42 #define READER_NAME "stpreader"
43 #define READER_DESC "file reader for steiner tree data format"
44 #define READER_EXTENSION "stp"
45 
46 #define DEFAULT_COMPCENTRAL STP_CENTER_DEG /**< selection type for the root (for undirected STPs) */
47 #define DEFAULT_EMITGRAPH FALSE /**< emit graph? */
48 #define DEFAULT_CHECKINPUT FALSE /**< check input data? */
49 #define DEFAULT_COUNTPRESOLTIME TRUE /**< count presolving time as part of overall solution time? */
50 #define DEFAULT_REDUCTION STP_REDUCTION_ADVANCED /**< reduction mode to apply */
51 #define DEFAULT_SYMCONS STP_CONS_AUTOMATIC /**< symmetry constraints */
52 #define DEFAULT_CYCLECONS STP_CONS_AUTOMATIC /**< cycle constraints */
53 #define DEFAULT_DACUTS STP_CONS_ALWAYS /**< always use dual-ascent cuts */
54 #define DEFAULT_DACUTSTYPE 1 /**< logicor */
55 #define DEFAULT_USEDACUTSINITIAL TRUE /**< use dual-ascent cuts for initial LP */
56 #define DEFAULT_USEDP STP_USEDP_AUTOMATIC /**< problem-specific */
57 #define DEFAULT_SDEXT 3 /**< sd extended */
58 #define DEFAULT_MINELIMS 3 /**< minimal number of eliminations to be achieved for reiteration of reduction methods */
59 #define DEFAULT_PRETIMELIMIT -1.0 /**< presolving time limit */
60 
61 #define STP_MODES "cfp" /**< valid values for user parameter 'stp/mode' */
62 
63 /**@} */
64 
65 
66 /**@name Callback methods
67  *
68  * @{
69  */
70 
71 /** copy method for reader plugins (called when SCIP copies plugins) */
72 static
73 SCIP_DECL_READERCOPY(readerCopyStp)
74 { /*lint --e{715}*/
75  assert(scip != NULL);
76  assert(reader != NULL);
77  assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
78 
79  /* call inclusion method of reader */
81 
82  return SCIP_OKAY;
83 }
84 
85 /** problem reading method of the reader */
86 static
87 SCIP_DECL_READERREAD(readerReadStp)
88 { /*lint --e{715}*/
89  SCIP_RETCODE retcode;
90  SCIP_PROBDATA* probdata;
91  char mode;
92 
93  *result = SCIP_DIDNOTRUN;
94 
95  /* get solving mode parameter */
96  SCIP_CALL( SCIPgetCharParam(scip, "stp/mode", &mode) );
97 
98  retcode = SCIPprobdataCreate(scip, filename);
99 
100  if( retcode == SCIP_READERROR )
101  return SCIP_READERROR;
102 
103  SCIP_CALL( retcode );
104 
105  probdata = SCIPgetProbData(scip);
106  if( SCIPgetStage(scip) == SCIP_STAGE_INIT || probdata == NULL )
107  return SCIP_READERROR;
108  else if(SCIPprobdataGetGraph(probdata) != NULL && mode == 'p')
109  {
110  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "activate pricer\n");
112  }
113 
114  *result = SCIP_SUCCESS;
115  return SCIP_OKAY;
116 }
117 
118 /** problem writing method of the reader */
119 static
120 SCIP_DECL_READERWRITE(readerWriteStp)
121 { /*lint --e{715}*/
122  const GRAPH* graph;
123  SCIP_Real offset;
124 
125  /* get the graph of the problem */
126  graph = SCIPprobdataGetGraph(probdata);
127 
128  /* get the offset of the problem */
129  offset = SCIPprobdataGetOffset(scip);
130 
131  /* save the graph in a .stp file */
132  graph_writeStp(scip, graph, file, offset);
133 
134  *result = SCIP_SUCCESS;
135  return SCIP_OKAY;
136 }
137 
138 /**@} */
139 
140 
141 /**@name Interface methods
142  *
143  * @{
144  */
145 
146 /** include user parameters */
148  SCIP* scip /**< SCIP data structure */
149 )
150 {
151  /* include user parameters */
153  "stp/compcentral",
154  "Comp. Central Term: 0 disable, 1 max. degree, 2 min. dist. sum to all terminals, 3 min. max. dist., 4 min. dist to all nodes",
155  NULL, FALSE, DEFAULT_COMPCENTRAL, 0, 4, NULL, NULL) );
156 
158  "stp/reduction",
159  "Reduction: 0 disable, 1 diminish, 2 default",
160  NULL, FALSE, DEFAULT_REDUCTION, 0, 2, NULL, NULL) );
161 
163  "stp/usesymcons",
164  "Use symmetry constraints (PC, MW): 0 never, 1 always, 2 problem specific",
165  NULL, FALSE, DEFAULT_SYMCONS, 0, 2, NULL, NULL) );
166 
168  "stp/usecyclecons",
169  "Use 2-cycle constraints (PC): 0 never, 1 always, 2 problem specific",
170  NULL, FALSE, DEFAULT_CYCLECONS, 0, 2, NULL, NULL) );
171 
173  "stp/usedacuts",
174  "Use initial dual ascent cuts: 0 never, 1 always, 2 problem specific",
175  NULL, FALSE, DEFAULT_DACUTS, 0, 2, NULL, NULL) );
176 
178  "stp/dacutstype",
179  "Type of dual ascent cuts: 0 linear, 1 logicor, 2 setppc",
180  NULL, FALSE, DEFAULT_DACUTSTYPE, 0, 2, NULL, NULL) );
181 
183  "stp/usedp",
184  "Use dynamic programming: 0 never, 1 always, 2 problem specific",
185  NULL, FALSE, DEFAULT_USEDP, 0, 2, NULL, NULL) );
186 
188  "stp/minelims",
189  "minimal number of eliminations per reduction method",
190  NULL, FALSE, DEFAULT_MINELIMS, 1, 10000, NULL, NULL) );
191 
193  "stp/sdext",
194  "mode of extended sd walk test 0 none, 1 fist, 2 second, 3 both",
195  NULL, FALSE, DEFAULT_SDEXT, 0, 3, NULL, NULL) );
196 
198  "stp/pretimelimit",
199  "presolving time limit",
200  NULL, FALSE, DEFAULT_PRETIMELIMIT, -1.0, SCIPinfinity(scip), NULL, NULL) );
201 
203  "stp/countpresoltime",
204  "count presolving time to solving time?",
206 
208  "stp/emitgraph",
209  "Emit graph",
211 
213  "stp/usedacutsinitial",
214  "use DA cuts for initial model?", NULL, FALSE, DEFAULT_USEDACUTSINITIAL, NULL, NULL) );
215 
217  "stp/bigt",
218  "use 'T' model", NULL, FALSE, FALSE, NULL, NULL) );
219 
221  "stp/printGraph",
222  "print the graph before and after the presolving", NULL, FALSE, FALSE, NULL, NULL) );
223 
225  "stp/checkinput",
226  "checks input data for errors",
228 
230  "stp/mode",
231  "Solving mode: 'c'ut, 'f'low ,'p'rice",
232  NULL, FALSE, 'c', STP_MODES, NULL, NULL) );
233 
235  "stp/logfile",
236  "log file in DIMACS challenge format; use_probname for using problem name",
237  NULL, FALSE, "",
238  NULL, NULL) );
239 
241  "stp/intlogfile",
242  "log file for intermediate solutions; use_probname for using problem name",
243  NULL, FALSE, "",
244  NULL, NULL) );
245 
247  "stp/redstatsfile",
248  "log file reduction statistics",
249  NULL, FALSE, "",
250  NULL, NULL) );
251 
252  return SCIP_OKAY;
253 }
254 
255 
256 /** includes the stp file reader in SCIP */
258  SCIP* scip /**< SCIP data structure */
259  )
260 {
261  SCIP_READERDATA* readerdata;
262  SCIP_READER* reader;
263 
264  /* create reader data */
265  readerdata = NULL;
266 
267  /* include reader */
269  assert(reader != NULL);
270 
271  SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyStp) );
272  SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadStp) );
273  SCIP_CALL( SCIPsetReaderWrite(scip, reader, readerWriteStp) );
274 
276 
277  return SCIP_OKAY;
278 }
279 
280 /**@} */
#define READER_EXTENSION
Definition: reader_stp.c:44
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip_param.c:317
#define DEFAULT_CYCLECONS
Definition: reader_stp.c:52
#define DEFAULT_COMPCENTRAL
Definition: reader_stp.c:46
SCIP_RETCODE SCIPStpReaderIncludeParams(SCIP *scip)
Definition: reader_stp.c:147
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
#define DEFAULT_REDUCTION
Definition: reader_stp.c:50
#define READER_DESC
Definition: reader_stp.c:43
void graph_writeStp(SCIP *, const GRAPH *, FILE *, SCIP_Real)
Definition: graph_save.c:568
const char * SCIPreaderGetName(SCIP_READER *reader)
Definition: reader.c:548
#define FALSE
Definition: def.h:87
#define DEFAULT_SDEXT
Definition: reader_stp.c:57
#define DEFAULT_EMITGRAPH
Definition: reader_stp.c:47
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_PRICER * SCIPfindPricer(SCIP *scip, const char *name)
Definition: scip_pricer.c:302
Problem data for stp problem.
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
Steiner tree problem file reader.
SCIP_RETCODE SCIPaddStringParam(SCIP *scip, const char *name, const char *desc, char **valueptr, SCIP_Bool isadvanced, const char *defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:185
SCIP_RETCODE SCIPprobdataCreate(SCIP *scip, const char *probname, int *demands, SCIP_Real *rints, SCIP_Real *rexts, int ntypes, SCIP_Real width, SCIP_Real height)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
#define DEFAULT_MINELIMS
Definition: reader_stp.c:58
#define READER_NAME
Definition: reader_stp.c:42
static SCIP_DECL_READERWRITE(readerWriteStp)
Definition: reader_stp.c:120
#define DEFAULT_DACUTSTYPE
Definition: reader_stp.c:54
SCIP_Real SCIPprobdataGetOffset(SCIP *scip)
SCIP_RETCODE SCIPincludeReaderStp(SCIP *scip)
Definition: reader_stp.c:257
#define NULL
Definition: lpi_spx1.cpp:155
#define DEFAULT_CHECKINPUT
Definition: reader_stp.c:48
static SCIP_DECL_READERCOPY(readerCopyStp)
Definition: reader_stp.c:73
#define DEFAULT_USEDP
Definition: reader_stp.c:56
#define SCIP_CALL(x)
Definition: def.h:384
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
#define STP_MODES
Definition: reader_stp.c:61
SCIP_RETCODE SCIPactivatePricer(SCIP *scip, SCIP_PRICER *pricer)
Definition: scip_pricer.c:375
struct SCIP_ReaderData SCIP_READERDATA
Definition: type_reader.h:44
#define DEFAULT_USEDACUTSINITIAL
Definition: reader_stp.c:55
SCIP_RETCODE SCIPincludeReaderBasic(SCIP *scip, SCIP_READER **readerptr, const char *name, const char *desc, const char *extension, SCIP_READERDATA *readerdata)
Definition: scip_reader.c:100
#define DEFAULT_SYMCONS
Definition: reader_stp.c:51
static SCIP_DECL_READERREAD(readerReadStp)
Definition: reader_stp.c:87
SCIP_RETCODE SCIPsetReaderWrite(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERWRITE((*readerwrite)))
Definition: scip_reader.c:210
SCIP_RETCODE SCIPsetReaderCopy(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERCOPY((*readercopy)))
Definition: scip_reader.c:138
#define DEFAULT_DACUTS
Definition: reader_stp.c:53
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:158
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:962
#define SCIP_Real
Definition: def.h:177
#define DEFAULT_PRETIMELIMIT
Definition: reader_stp.c:59
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:186
includes various reduction methods for Steiner tree problems
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
#define DEFAULT_COUNTPRESOLTIME
Definition: reader_stp.c:49