Scippy

SCIP

Solving Constraint Integer Programs

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
362 *result = SCIP_DIDNOTRUN;
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
372 *result = SCIP_SUCCESS;
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 SCIP_Bool
Definition: def.h:91
#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)
Definition: scip_general.c:380
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,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
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 SCIPincludeReaderBasic(SCIP *scip, SCIP_READER **readerptr, const char *name, const char *desc, const char *extension, SCIP_READERDATA *readerdata)
Definition: scip_reader.c:109
SCIP_RETCODE SCIPsetReaderCopy(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERCOPY((*readercopy)))
Definition: scip_reader.c:147
const char * SCIPreaderGetName(SCIP_READER *reader)
Definition: reader.c:557
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:195
void SCIPprintSysError(const char *message)
Definition: misc.c:10769
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
static SCIP_DECL_READERREAD(readerReadDec)
Definition: reader_dec.c:356
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
static SCIP_DECL_READERCOPY(readerCopyDec)
Definition: reader_dec.c:342
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
Definition: type_message.h:55
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_NOFILE
Definition: type_retcode.h:47
@ SCIP_READERROR
Definition: type_retcode.h:45
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_PROBLEM
Definition: type_set.h:45