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