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-2020 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 "grph.h"
34 
35 
36 /**@name Reader properties
37  *
38  * @{
39  */
40 
41 #define READER_NAME "stpreader"
42 #define READER_DESC "file reader for steiner tree data format"
43 #define READER_EXTENSION "stp"
44 
45 #define DEFAULT_COMPCENTRAL 1 /**< selection type for the root (for undirected STPs) */
46 #define DEFAULT_EMITGRAPH FALSE /**< emit graph? */
47 #define DEFAULT_COUNTPRESOLTIME TRUE /**< count presolving time as part of overall solution time? */
48 #define DEFAULT_REDUCTION 2 /**< reduction mode to apply */
49 #define DEFAULT_SYMCONS 2 /**< symmetry constraints */
50 #define DEFAULT_CYCLECONS 2 /**< cycle constraints */
51 #define DEFAULT_MINELIMS 3 /**< minimal number of eliminations to be achieved for reiteration of reduction methods */
52 #define DEFAULT_PRETIMELIMIT -1.0 /**< presolving time limit */
53 
54 #define STP_MODES "cfp" /**< valid values for user parameter 'stp/mode' */
55 
56 /**@} */
57 
58 
59 /**@name Callback methods
60  *
61  * @{
62  */
63 
64 /** copy method for reader plugins (called when SCIP copies plugins) */
65 static
66 SCIP_DECL_READERCOPY(readerCopyStp)
67 { /*lint --e{715}*/
68  assert(scip != NULL);
69  assert(reader != NULL);
70  assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
71 
72  /* call inclusion method of reader */
74 
75  return SCIP_OKAY;
76 }
77 
78 /** problem reading method of the reader */
79 static
80 SCIP_DECL_READERREAD(readerReadStp)
81 { /*lint --e{715}*/
82  SCIP_RETCODE retcode;
83  SCIP_PROBDATA* probdata;
84  char mode;
85 
86  *result = SCIP_DIDNOTRUN;
87 
88  /* get solving mode parameter */
89  SCIP_CALL( SCIPgetCharParam(scip, "stp/mode", &mode) );
90 
91  retcode = SCIPprobdataCreate(scip, filename);
92 
93  if( retcode == SCIP_READERROR )
94  return SCIP_READERROR;
95 
96  SCIP_CALL( retcode );
97 
98  probdata = SCIPgetProbData(scip);
99  if( SCIPgetStage(scip) == SCIP_STAGE_INIT || probdata == NULL )
100  return SCIP_READERROR;
101  else if(SCIPprobdataGetGraph(probdata) != NULL && mode == 'p')
102  {
103  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "activate pricer\n");
105  }
106 
107  *result = SCIP_SUCCESS;
108  return SCIP_OKAY;
109 }
110 
111 /** problem writing method of the reader */
112 static
113 SCIP_DECL_READERWRITE(readerWriteStp)
114 { /*lint --e{715}*/
115  const GRAPH* graph;
116  SCIP_Real offset;
117 
118  /* get the graph of the problem */
119  graph = SCIPprobdataGetGraph(probdata);
120 
121  /* get the offset of the problem */
122  offset = SCIPprobdataGetOffset(scip);
123 
124  /* save the graph in a .stp file */
125  SCIPwriteStp(scip, graph, file, offset);
126 
127  *result = SCIP_SUCCESS;
128  return SCIP_OKAY;
129 }
130 
131 /**@} */
132 
133 
134 /**@name Interface methods
135  *
136  * @{
137  */
138 
139 /** include user parameters */
141  SCIP* scip /**< SCIP data structure */
142 )
143 {
144  /* include user parameters */
146  "stp/compcentral",
147  "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",
148  NULL, FALSE, DEFAULT_COMPCENTRAL, 0, 4, NULL, NULL) );
149 
151  "stp/reduction",
152  "Reduction: 0 disable, 1 diminish, 2 default",
153  NULL, FALSE, DEFAULT_REDUCTION, 0, 2, NULL, NULL) );
154 
156  "stp/usesymcons",
157  "Use symmetry constraints (PC, MW): 0 never, 1 always, 2 problem specific",
158  NULL, FALSE, DEFAULT_SYMCONS, 0, 2, NULL, NULL) );
159 
161  "stp/usecyclecons",
162  "Use 2-cycle constraints (PC): 0 never, 1 always, 2 problem specific",
163  NULL, FALSE, DEFAULT_CYCLECONS, 0, 2, NULL, NULL) );
164 
166  "stp/minelims",
167  "minimal number of eliminations per reduction method",
168  NULL, FALSE, DEFAULT_MINELIMS, 0, 10000, NULL, NULL) );
169 
171  "stp/pretimelimit",
172  "presolving time limit",
173  NULL, FALSE, DEFAULT_PRETIMELIMIT, -1.0, SCIPinfinity(scip), NULL, NULL) );
174 
176  "stp/countpresoltime",
177  "count presolving time to solving time?",
179 
181  "stp/emitgraph",
182  "Emit graph",
184 
186  "stp/bigt",
187  "use 'T' model", NULL, FALSE, FALSE, NULL, NULL) );
188 
190  "stp/printGraph",
191  "print the graph before and after the presolving", NULL, FALSE, FALSE, NULL, NULL) );
192 
194  "stp/mode",
195  "Solving mode: 'c'ut, 'f'low ,'p'rice",
196  NULL, FALSE, 'c', STP_MODES, NULL, NULL) );
197 
199  "stp/logfile",
200  "log file in DIMACS challenge format; use_probname for using problem name",
201  NULL, FALSE, "",
202  NULL, NULL) );
203 
205  "stp/intlogfile",
206  "log file for intermediate solutions; use_probname for using problem name",
207  NULL, FALSE, "",
208  NULL, NULL) );
209 
210  return SCIP_OKAY;
211 }
212 
213 
214 /** includes the stp file reader in SCIP */
216  SCIP* scip /**< SCIP data structure */
217  )
218 {
219  SCIP_READERDATA* readerdata;
220  SCIP_READER* reader;
221 
222  /* create reader data */
223  readerdata = NULL;
224 
225  /* include reader */
227  assert(reader != NULL);
228 
229  SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyStp) );
230  SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadStp) );
231  SCIP_CALL( SCIPsetReaderWrite(scip, reader, readerWriteStp) );
232 
234 
235  return SCIP_OKAY;
236 }
237 
238 /**@} */
#define READER_EXTENSION
Definition: reader_stp.c:43
void SCIPwriteStp(SCIP *, const GRAPH *, FILE *, SCIP_Real)
Definition: grphsave.c:38
SCIP_EXPORT const char * SCIPreaderGetName(SCIP_READER *reader)
Definition: reader.c:548
#define DEFAULT_CYCLECONS
Definition: reader_stp.c:50
#define DEFAULT_COMPCENTRAL
Definition: reader_stp.c:45
SCIP_RETCODE SCIPStpReaderIncludeParams(SCIP *scip)
Definition: reader_stp.c:140
Definition: grph.h:57
#define DEFAULT_REDUCTION
Definition: reader_stp.c:48
#define READER_DESC
Definition: reader_stp.c:42
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:186
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
#define FALSE
Definition: def.h:73
SCIP_RETCODE SCIPsetReaderCopy(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERCOPY((*readercopy)))
Definition: scip_reader.c:138
#define DEFAULT_EMITGRAPH
Definition: reader_stp.c:46
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
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:962
Steiner tree problem file reader.
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
SCIP_RETCODE SCIPprobdataCreate(SCIP *scip, const char *probname, int *demands, SCIP_Real *rints, SCIP_Real *rexts, int ntypes, SCIP_Real width, SCIP_Real height)
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip_param.c:317
#define DEFAULT_MINELIMS
Definition: reader_stp.c:51
SCIP_RETCODE SCIPsetReaderWrite(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERWRITE((*readerwrite)))
Definition: scip_reader.c:210
#define READER_NAME
Definition: reader_stp.c:41
static SCIP_DECL_READERWRITE(readerWriteStp)
Definition: reader_stp.c:113
SCIP_Real SCIPprobdataGetOffset(SCIP *scip)
SCIP_RETCODE SCIPincludeReaderStp(SCIP *scip)
Definition: reader_stp.c:215
#define NULL
Definition: lpi_spx1.cpp:155
static SCIP_DECL_READERCOPY(readerCopyStp)
Definition: reader_stp.c:66
#define SCIP_CALL(x)
Definition: def.h:364
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
#define STP_MODES
Definition: reader_stp.c:54
struct SCIP_ReaderData SCIP_READERDATA
Definition: type_reader.h:44
SCIP_Real SCIPinfinity(SCIP *scip)
#define DEFAULT_SYMCONS
Definition: reader_stp.c:49
static SCIP_DECL_READERREAD(readerReadStp)
Definition: reader_stp.c:80
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
includes various files containing graph methods used 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
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
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
#define SCIP_Real
Definition: def.h:163
#define DEFAULT_PRETIMELIMIT
Definition: reader_stp.c:52
SCIP_RETCODE SCIPactivatePricer(SCIP *scip, SCIP_PRICER *pricer)
Definition: scip_pricer.c:375
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
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
#define DEFAULT_COUNTPRESOLTIME
Definition: reader_stp.c:47