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 */
105  	enum Dec_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  	};
111  	typedef enum Dec_Section DEC_SECTION;
112  	
113  	/** reads the given decomposition file */
114  	static
115  	SCIP_RETCODE readDecomposition(
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 */
349  	   SCIP_CALL( SCIPincludeReaderDec(scip) );
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  	
364  	   if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM )
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 */
382  	SCIP_RETCODE SCIPincludeReaderDec(
383  	   SCIP*                 scip                /**< SCIP data structure */
384  	   )
385  	{
386  	   SCIP_READER* reader;
387  	
388  	   /* include reader */
389  	   SCIP_CALL( SCIPincludeReaderBasic(scip, &reader, READER_NAME, READER_DESC, READER_EXTENSION, NULL) );
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  	}
397