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-2023 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 /**< */
110 };
112 
113 /** reads the given decomposition file */
114 static
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 */
141  if( SCIPgetStage(scip) != SCIP_STAGE_PROBLEM )
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;
226  case DEC_SECTION_NBLOCKS:
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;
236  case DEC_SECTION_BLOCK:
237  case DEC_SECTION_MASTER:
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 
304  SCIP_CALL( SCIPcomputeDecompStats(scip, decomp, TRUE) );
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 */
323 TERMINATE:
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) */
341 static
342 SCIP_DECL_READERCOPY(readerCopyDec)
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 */
355 static
356 SCIP_DECL_READERREAD(readerReadDec)
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 }
public methods for SCIP parameter handling
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:365
SCIP_RETCODE SCIPcomputeDecompVarsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:454
public methods for memory management
#define SCIP_MAXSTRLEN
Definition: def.h:302
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition: scip_dcmp.c:1135
#define READER_NAME
Definition: reader_dec.c:96
public solving methods
const char * SCIPreaderGetName(SCIP_READER *reader)
Definition: reader.c:557
#define FALSE
Definition: def.h:96
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
#define READER_DESC
Definition: reader_dec.c:97
public methods for problem variables
#define SCIP_DECOMP_LINKCONS
Definition: type_dcmp.h:45
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3096
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
public methods for SCIP variables
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
#define SCIPdebugMsg
Definition: scip_message.h:78
public methods for numerical tolerances
public methods for decompositions
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:153
#define SCIPerrorMessage
Definition: pub_message.h:64
int SCIPfeof(SCIP_FILE *stream)
Definition: fileio.c:227
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:43
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:200
enum Dec_Section DEC_SECTION
Definition: reader_dec.c:111
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
SCIP_CONS * SCIPfindCons(SCIP *scip, const char *name)
Definition: scip_prob.c:2955
#define NULL
Definition: lpi_spx1.cpp:164
SCIP_RETCODE SCIPincludeReaderDec(SCIP *scip)
Definition: reader_dec.c:382
static SCIP_DECL_READERREAD(readerReadDec)
Definition: reader_dec.c:356
#define SCIP_CALL(x)
Definition: def.h:394
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define READER_EXTENSION
Definition: reader_dec.c:98
wrapper functions to map file i/o to standard or zlib file i/o
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
public data structures and miscellaneous methods
SCIP_RETCODE SCIPdecompSetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:172
#define SCIP_Bool
Definition: def.h:93
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
void SCIPprintSysError(const char *message)
Definition: misc.c:10680
static SCIP_DECL_READERCOPY(readerCopyDec)
Definition: reader_dec.c:342
SCIP_RETCODE SCIPsetReaderCopy(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERCOPY((*readercopy)))
Definition: scip_reader.c:147
general public methods
char * SCIPdecompPrintStats(SCIP_DECOMP *decomp, char *strbuf)
Definition: dcmp.c:454
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3050
public methods for message output
public methods for input file readers
#define SCIP_CALL_TERMINATE(retcode, x, TERM)
Definition: def.h:415
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:217
type definitions for decompositions and the decomposition store
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:195
SCIP_RETCODE SCIPaddDecomp(SCIP *scip, SCIP_DECOMP *decomp)
Definition: scip_dcmp.c:244
static SCIP_RETCODE readDecomposition(SCIP *scip, const char *filename)
Definition: reader_dec.c:115
file reader for decompositions in the constraint based dec-file format.
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:232
public methods for decompositions
public methods for reader plugins
public methods for global and local (sub)problems
Dec_Section
Definition: reader_dec.c:105