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