1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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_dec.c
17 * @brief file reader for decompositions in the constraint based dec-file format.
18 * @author Gregor Hendel
19 *
20 * This reader allows to read a file containing decompositions for constraints of the current original problem. The
21 * standard line ending for this format is '.dec'. The content of the file should obey the following format
22 *
23 * \\ place for comments and statistics
24 * NBLOCKS
25 * 2
26 * BLOCK 0
27 * consA
28 * consB
29 * [...]
30 * BLOCK 1
31 * consC
32 * consD
33 * [...]
34 * MASTERCONSS
35 * linkingcons
36 *
37 * A block in a problem decomposition is a set of constraints that are independent from all other blocks after removing
38 * the special blocks of linking constraints denoted as MASTERCONSS.
39 *
40 * Imagine the following example, which involves seven variables
41 * and the five constraints from the file above. The asterisks (*) indicate that the variable affects the feasibility
42 * of the constraint. In the special case of a linear optimization problem, the asterisks correspond to the
43 * nonzero entries of the constraint matrix.
44 *
45 * x1 x2 x3 x4 x5 x6 x7
46 * consA * * \ BLOCK 0
47 * consB * * /
48 * consC * * \ BLOCK 1
49 * consD * * /
50 * linkingconss * * * * * * * > MASTERCONSS
51 *
52 * The nonzero pattern has been chosen in a way that after the removal of the last constraint 'linkingcons', the remaining problem
53 * consists of two independent parts, namely the blocks '0' and '1'.
54 *
55 * The corresponding variable labels are inferred from the constraint labels. A variable is assigned the label
56 *
57 * - of its unique block, if it only occurs in exactly 1 named block, and probably in MASTERCONSS.
58 * - the special label of a linking variable if it occurs only in the master constraints or in 2 or even more named blocks.
59 *
60 * @note A trivial decomposition is to assign all constraints of a problem to the MASTERCONSS.
61 *
62 * @note The number of blocks is the number of named blocks: a trivial decomposition should have 0 blocks
63 */
64
65 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
66
67 #include "scip/pub_dcmp.h"
68 #include "scip/pub_fileio.h"
69 #include "scip/pub_message.h"
70 #include "scip/pub_misc.h"
71 #include "scip/pub_reader.h"
72 #include "scip/pub_var.h"
73 #include "scip/reader_dec.h"
74 #include "scip/scip_dcmp.h"
75 #include "scip/scip_general.h"
76 #include "scip/scip_message.h"
77 #include "scip/scip_numerics.h"
78 #include "scip/scip_param.h"
79 #include "scip/scip_prob.h"
80 #include "scip/scip_reader.h"
81 #include "scip/scip_solve.h"
82 #include "scip/scip_var.h"
83 #include "scip/scip_mem.h"
84 #include "scip/type_dcmp.h"
85 #include <string.h>
86
87 #define READER_NAME "decreader"
88 #define READER_DESC "file reader for constraint decompositions"
89 #define READER_EXTENSION "dec"
90
91 /*
92 * local methods
93 */
94
95 /* enumerator for the current section */
96 enum Dec_Section {
97 DEC_SECTION_INIT = 0, /**< initial section before the number of blocks is specified */
98 DEC_SECTION_NBLOCKS = 1, /**< section that contains the number of */
99 DEC_SECTION_BLOCK = 2, /**< */
100 DEC_SECTION_MASTER = 3 /**< */
101 };
102 typedef enum Dec_Section DEC_SECTION;
103
104 /** reads the given decomposition file */
105 static
readDecomposition(SCIP * scip,const char * filename)106 SCIP_RETCODE readDecomposition(
107 SCIP* scip, /**< SCIP data structure */
108 const char* filename /**< name of the input file */
109 )
110 {
111 SCIP_RETCODE retcode;
112 SCIP_FILE* file;
113 SCIP_CONS** conss;
114 SCIP_CONS** scip_conss;
115 SCIP_Bool error;
116 int lineno;
117 int nblocks;
118 int currblock = SCIP_DECOMP_LINKCONS;
119 int* labels;
120 int nconss;
121 int consptr;
122 int nblockscounted;
123
124 DEC_SECTION section;
125
126 SCIP_DECOMP* decomp;
127
128 assert(scip != NULL);
129 assert(filename != NULL);
130
131 /* cannot read a decomposition after problem has been transformed */
132 if( SCIPgetStage(scip) != SCIP_STAGE_PROBLEM )
133 {
134 SCIPwarningMessage(scip, "Cannot read decomposition after problem has been transformed.\n");
135
136 return SCIP_OKAY;
137 }
138
139 /* open input file */
140 file = SCIPfopen(filename, "r");
141 if( file == NULL )
142 {
143 SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
144 SCIPprintSysError(filename);
145 return SCIP_NOFILE;
146 }
147
148 /* read the file */
149 error = FALSE;
150 lineno = 0;
151 nblocks = -1;
152
153 /* use the number of constraints of the problem as buffer storage size */
154 nconss = SCIPgetNConss(scip);
155
156 SCIP_CALL_TERMINATE( retcode, SCIPallocBufferArray(scip, &conss, nconss), TERMINATE );
157 SCIP_CALL_TERMINATE( retcode, SCIPallocBufferArray(scip, &labels, nconss), TERMINATE );
158
159 /* start parsing the file */
160 section = DEC_SECTION_INIT;
161 consptr = 0;
162 nblockscounted = 0;
163 while( !SCIPfeof(file) && !error )
164 {
165 char buffer[SCIP_MAXSTRLEN];
166 char consname[SCIP_MAXSTRLEN];
167 SCIP_CONS* cons = NULL;
168 int nread;
169
170 /* get next line */
171 if( SCIPfgets(buffer, (int) sizeof(buffer), file) == NULL )
172 break;
173 lineno++;
174
175 /* check if a new section begins */
176 if( strncmp(buffer, "NBLOCKS", 7) == 0 )
177 {
178 section = DEC_SECTION_NBLOCKS;
179 continue;
180 }
181 else if( strncmp(buffer, "BLOCK", 5) == 0 )
182 {
183 section = DEC_SECTION_BLOCK;
184
185 /* coverity[secure_coding] */
186 nread = sscanf(buffer, "BLOCK %1018d\n", &currblock);
187 if( nread < 1 )
188 {
189 error = TRUE;
190 break;
191 }
192 /* count number of block manually. If it is different from the number of specified blocks, throw an error */
193 else if( ++nblockscounted > nblocks )
194 {
195 error = TRUE;
196 break;
197 }
198
199 SCIPdebugMsg(scip, "Switching block to %d\n", currblock);
200 continue;
201 }
202 else if( strncmp(buffer, "MASTERCONSS", 11) == 0 )
203 {
204 section = DEC_SECTION_MASTER;
205 currblock = SCIP_DECOMP_LINKCONS;
206
207 SCIPdebugMsg(scip, "Continuing with master constraint block.\n");
208
209 continue;
210 }
211
212 /* base the parsing on the currently active section */
213 switch (section)
214 {
215 case DEC_SECTION_INIT:
216 break;
217 case DEC_SECTION_NBLOCKS:
218 /* read in number of blocks */
219 assert(nblocks == -1);
220 /* coverity[secure_coding] */
221 nread = sscanf(buffer, "%1024d\n", &nblocks);
222 if( nread < 1 )
223 error = TRUE;
224
225 SCIPdebugMsg(scip, "Decomposition with %d number of blocks\n", nblocks);
226 break;
227 case DEC_SECTION_BLOCK:
228 case DEC_SECTION_MASTER:
229 /* read constraint name in both cases */
230 /* coverity[secure_coding] */
231 nread = sscanf(buffer, "%1024s\n", consname);
232 if( nread < 1 )
233 error = TRUE;
234
235 cons = SCIPfindCons(scip, consname);
236 /* check if the constraint exists */
237 if( cons == NULL )
238 {
239 SCIPwarningMessage(scip, "Constraint <%s> in line %d does not exist.\n", consname, lineno);
240 continue;
241 }
242 break;
243
244 default:
245 break;
246 }
247
248 if( section == DEC_SECTION_NBLOCKS || section == DEC_SECTION_INIT )
249 continue;
250
251 /* check if buffer storage capacity has been reached, which means that there is a duplicate constraint entry */
252 if( consptr == nconss )
253 {
254 SCIPerrorMessage("Error: Too many constraints in decomposition file: Is there a double entry?\n");
255 error = TRUE;
256 break;
257 }
258
259 /* store constraint and corresponding label */
260 conss[consptr] = cons;
261 labels[consptr] = currblock;
262 ++consptr;
263 }
264
265 /* close input file */
266 SCIPfclose(file);
267
268 /* compare specified and actual number of blocks; stop on mismatch */
269 if( nblockscounted != nblocks )
270 {
271 SCIPerrorMessage("Error: Block number specification is wrong: Specified %d blocks, counted %d.\n",
272 nblocks, nblockscounted);
273 error = TRUE;
274 }
275
276 /* create a decomposition and add it to the decomposition storage of SCIP */
277 if( ! error )
278 {
279 char strbuf[SCIP_MAXSTRLEN];
280 SCIP_Bool benderslabels;
281
282 /* retrieving the Benders' variable labels setting */
283 SCIP_CALL( SCIPgetBoolParam(scip, "decomposition/benderslabels", &benderslabels) );
284
285 SCIP_CALL( SCIPcreateDecomp(scip, &decomp, nblocks, TRUE, benderslabels) );
286
287 SCIP_CALL( SCIPdecompSetConsLabels(decomp, conss, labels, consptr) );
288 SCIPdebugMsg(scip, "Setting labels for %d constraints.\n", nconss);
289
290 scip_conss = SCIPgetConss(scip);
291
292 SCIPdebugMsg(scip, "Using %d SCIP constraints for labeling variables.\n", nconss);
293 SCIP_CALL( SCIPcomputeDecompVarsLabels(scip, decomp, scip_conss, nconss) );
294
295 SCIP_CALL( SCIPcomputeDecompStats(scip, decomp, TRUE) );
296
297 SCIP_CALL( SCIPaddDecomp(scip, decomp) );
298
299 /* display result */
300 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Added decomposition <%s> with %d blocks to SCIP\n", filename, nblocks);
301
302 /* print decomposition statistics */
303 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Decomposition statistics:\n%s\n", SCIPdecompPrintStats(decomp, strbuf));
304 }
305 else
306 {
307 SCIPerrorMessage("Errors parsing decomposition <%s>. No decomposition added\n.", filename);
308 }
309
310 SCIPfreeBufferArray(scip, &labels);
311 SCIPfreeBufferArray(scip, &conss);
312
313 /* cppcheck-suppress unusedLabel */
314 TERMINATE:
315 if( retcode != SCIP_OKAY )
316 {
317 SCIPfclose(file);
318 return retcode;
319 }
320
321 if( error )
322 return SCIP_READERROR;
323 else
324 return SCIP_OKAY;
325 }
326
327 /*
328 * Callback methods of reader
329 */
330
331 /** copy method for reader plugins (called when SCIP copies plugins) */
332 static
SCIP_DECL_READERCOPY(readerCopyDec)333 SCIP_DECL_READERCOPY(readerCopyDec)
334 { /*lint --e{715}*/
335 assert(scip != NULL);
336 assert(reader != NULL);
337 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
338
339 /* call inclusion method of reader */
340 SCIP_CALL( SCIPincludeReaderDec(scip) );
341
342 return SCIP_OKAY;
343 }
344
345 /** problem reading method of reader */
346 static
SCIP_DECL_READERREAD(readerReadDec)347 SCIP_DECL_READERREAD(readerReadDec)
348 { /*lint --e{715}*/
349 assert(reader != NULL);
350 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
351 assert(result != NULL);
352
353 *result = SCIP_DIDNOTRUN;
354
355 if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM )
356 {
357 SCIPerrorMessage("reading of decomposition file is only possible after a problem was created\n");
358 return SCIP_READERROR;
359 }
360
361 SCIP_CALL( readDecomposition(scip, filename) );
362
363 *result = SCIP_SUCCESS;
364
365 return SCIP_OKAY;
366 }
367
368 /*
369 * dec file reader specific interface methods
370 */
371
372 /** includes the dec file reader in SCIP */
SCIPincludeReaderDec(SCIP * scip)373 SCIP_RETCODE SCIPincludeReaderDec(
374 SCIP* scip /**< SCIP data structure */
375 )
376 {
377 SCIP_READER* reader;
378
379 /* include reader */
380 SCIP_CALL( SCIPincludeReaderBasic(scip, &reader, READER_NAME, READER_DESC, READER_EXTENSION, NULL) );
381
382 /* set non fundamental callbacks via setter functions */
383 SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyDec) );
384 SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadDec) );
385
386 return SCIP_OKAY;
387 }
388