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-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_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 */
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 };
103 
104 /** reads the given decomposition file */
105 static
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 
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
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 */
341 
342  return SCIP_OKAY;
343 }
344 
345 /** problem reading method of reader */
346 static
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 
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 */
374  SCIP* scip /**< SCIP data structure */
375  )
376 {
377  SCIP_READER* reader;
378 
379  /* include reader */
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 }
public methods for SCIP parameter handling
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
SCIP_RETCODE SCIPcomputeDecompVarsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:444
public methods for memory management
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition: scip_dcmp.c:1125
#define READER_NAME
Definition: reader_dec.c:87
public solving methods
const char * SCIPreaderGetName(SCIP_READER *reader)
Definition: reader.c:548
#define FALSE
Definition: def.h:87
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define READER_DESC
Definition: reader_dec.c:88
public methods for problem variables
#define SCIP_DECOMP_LINKCONS
Definition: type_dcmp.h:36
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3086
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
public methods for SCIP variables
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
#define SCIPdebugMsg
Definition: scip_message.h:69
public methods for numerical tolerances
public methods for decompositions
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:144
#define SCIPerrorMessage
Definition: pub_message.h:55
int SCIPfeof(SCIP_FILE *stream)
Definition: fileio.c:218
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:34
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:191
enum Dec_Section DEC_SECTION
Definition: reader_dec.c:102
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
SCIP_CONS * SCIPfindCons(SCIP *scip, const char *name)
Definition: scip_prob.c:2945
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE SCIPincludeReaderDec(SCIP *scip)
Definition: reader_dec.c:373
static SCIP_DECL_READERREAD(readerReadDec)
Definition: reader_dec.c:347
#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 READER_EXTENSION
Definition: reader_dec.c:89
wrapper functions to map file i/o to standard or zlib file i/o
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
public data structures and miscellaneous methods
SCIP_RETCODE SCIPdecompSetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:163
#define SCIP_Bool
Definition: def.h:84
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
void SCIPprintSysError(const char *message)
Definition: misc.c:10664
static SCIP_DECL_READERCOPY(readerCopyDec)
Definition: reader_dec.c:333
SCIP_RETCODE SCIPsetReaderCopy(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERCOPY((*readercopy)))
Definition: scip_reader.c:138
general public methods
char * SCIPdecompPrintStats(SCIP_DECOMP *decomp, char *strbuf)
Definition: dcmp.c:445
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3040
public methods for message output
public methods for input file readers
#define SCIP_CALL_TERMINATE(retcode, x, TERM)
Definition: def.h:405
public methods for message handling
SCIP_RETCODE SCIPcreateDecomp(SCIP *scip, SCIP_DECOMP **decomp, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: scip_dcmp.c:208
type definitions for decompositions and the decomposition store
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:186
SCIP_RETCODE SCIPaddDecomp(SCIP *scip, SCIP_DECOMP *decomp)
Definition: scip_dcmp.c:235
static SCIP_RETCODE readDecomposition(SCIP *scip, const char *filename)
Definition: reader_dec.c:106
file reader for decompositions in the constraint based dec-file format.
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:223
public methods for decompositions
public methods for reader plugins
public methods for global and local (sub)problems
Dec_Section
Definition: reader_dec.c:96