reader_dec.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2017 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 
38 #include <assert.h>
39 #include <string.h>
40 #if defined(_WIN32) || defined(_WIN64)
41 #else
42 #include <strings.h> /*lint --e{766}*/ /* needed for strcasecmp() */
43 #endif
44 #include <ctype.h>
45 
46 #include "reader_dec.h"
47 #include "scip_misc.h"
48 #include "pub_gcgvar.h"
49 
50 #include "cons_decomp.h"
51 #include "pub_decomp.h"
52 
53 #define READER_NAME "decreader"
54 #define READER_DESC "file reader for blocks in dec format"
55 #define READER_EXTENSION "dec"
56 
57 
58 /*
59  * Data structures
60  */
61 #define DEC_MAX_LINELEN 65536
62 #define DEC_MAX_PUSHEDTOKENS 2
63 
66 {
68 };
69 typedef enum DecSection DECSECTION;
70 
73 {
75 };
76 typedef enum DecExpType DECEXPTYPE;
77 
79 struct DecInput
80 {
81  SCIP_FILE* file;
83  char* token;
84  char* tokenbuf;
87  int linenumber;
88  int linepos;
89  SCIP_Bool presolved;
90  SCIP_Bool haspresolvesection;
91  int nblocks;
92  int blocknr;
94  SCIP_Bool haserror;
95 };
96 typedef struct DecInput DECINPUT;
97 
99 struct SCIP_ReaderData
100 {
101  SCIP_HASHMAP* constoblock;
102 };
103 static const int NOVALUE = -1;
104 static const int LINKINGVALUE = -2;
105 static const char delimchars[] = " \f\n\r\t\v";
106 static const char tokenchars[] = "-+:<>=";
107 static const char commentchars[] = "\\";
108 
109 
110 
111 
112 /*
113  * Local methods (for reading)
114  */
115 
117 static
119  SCIP* scip,
120  DECINPUT* decinput,
121  const char* msg
122  )
123 {
124  char formatstr[256];
125 
126  assert(decinput != NULL);
127 
128  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error in line %d: %s ('%s')\n",
129  decinput->linenumber, msg, decinput->token);
130  if( decinput->linebuf[strlen(decinput->linebuf) - 1] == '\n' )
131  {
132  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, " input: %s", decinput->linebuf);
133  }
134  else
135  {
136  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, " input: %s\n", decinput->linebuf);
137  }
138  (void) SCIPsnprintf(formatstr, 256, " %%%ds\n", decinput->linepos);
139  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, formatstr, "^");
140  decinput->section = DEC_END;
141  decinput->haserror = TRUE;
142 }
143 
145 static
146 SCIP_Bool hasError(
147  DECINPUT* decinput
148  )
149 {
150  assert(decinput != NULL);
151 
152  return decinput->haserror;
153 }
154 
156 static
157 SCIP_Bool isDelimChar(
158  char c
159  )
160 {
161  return (c == '\0') || (strchr(delimchars, c) != NULL);
162 }
163 
165 static
166 SCIP_Bool isTokenChar(
167  char c
168  )
169 {
170  return (strchr(tokenchars, c) != NULL);
171 }
172 
174 static
175 SCIP_Bool isValueChar(
176  char c,
177  char nextc,
178  SCIP_Bool firstchar,
179  SCIP_Bool* hasdot,
180  DECEXPTYPE* exptype
181  )
182 { /*lint --e{715}*/
183  assert(hasdot != NULL);
184  assert(exptype != NULL);
185 
186  if( isdigit(c) )
187  return TRUE;
188 
189  return FALSE;
190 }
191 
195 static
196 SCIP_Bool getNextLine(
197  DECINPUT* decinput
198  )
199 {
200  int i;
201 
202  assert(decinput != NULL);
203 
204  /* clear the line */
205  BMSclearMemoryArray(decinput->linebuf, DEC_MAX_LINELEN);
206 
207  /* read next line */
208  decinput->linepos = 0;
209  decinput->linebuf[DEC_MAX_LINELEN - 2] = '\0';
210  if( SCIPfgets(decinput->linebuf, DEC_MAX_LINELEN, decinput->file) == NULL )
211  return FALSE;
212  decinput->linenumber ++;
213  if( decinput->linebuf[DEC_MAX_LINELEN - 2] != '\0' )
214  {
215  SCIPerrorMessage("Error: line %d exceeds %d characters\n", decinput->linenumber, DEC_MAX_LINELEN - 2);
216  decinput->haserror = TRUE;
217  return FALSE;
218  }
219  decinput->linebuf[DEC_MAX_LINELEN - 1] = '\0';
220  decinput->linebuf[DEC_MAX_LINELEN - 2] = '\0'; /* we want to use lookahead of one char -> we need two \0 at the end */
221 
222  /* skip characters after comment symbol */
223  for( i = 0; commentchars[i] != '\0'; ++ i )
224  {
225  char* commentstart;
226 
227  commentstart = strchr(decinput->linebuf, commentchars[i]);
228  if( commentstart != NULL )
229  {
230  *commentstart = '\0';
231  *(commentstart + 1) = '\0'; /* we want to use lookahead of one char -> we need two \0 at the end */
232  }
233  }
234 
235  return TRUE;
236 }
237 
239 static
241  char** pointer1,
242  char** pointer2
243  )
244 {
245  char* tmp;
246 
247  tmp = * pointer1;
248  *pointer1 = * pointer2;
249  *pointer2 = tmp;
250 }
251 
253 static
254 SCIP_Bool getNextToken(
255  DECINPUT* decinput
256  )
257 {
258  SCIP_Bool hasdot;
259  DECEXPTYPE exptype;
260  char* buf;
261  int tokenlen;
262 
263  assert(decinput != NULL);
264  assert(decinput->linepos < DEC_MAX_LINELEN);
265 
266  /* check the token stack */
267  if( decinput->npushedtokens > 0 )
268  {
269  swapPointers(&decinput->token, &decinput->pushedtokens[decinput->npushedtokens - 1]);
270  decinput->npushedtokens --;
271  SCIPdebugMessage("(line %d) read token again: '%s'\n", decinput->linenumber, decinput->token);
272  return TRUE;
273  }
274 
275  /* skip delimiters */
276  buf = decinput->linebuf;
277  while( isDelimChar(buf[decinput->linepos]) )
278  {
279  if( buf[decinput->linepos] == '\0' )
280  {
281  if( ! getNextLine(decinput) )
282  {
283  decinput->section = DEC_END;
284  SCIPdebugMessage("(line %d) end of file\n", decinput->linenumber);
285  return FALSE;
286  }
287  assert(decinput->linepos == 0);
288  }
289  else
290  decinput->linepos ++;
291  }
292  assert(decinput->linepos < DEC_MAX_LINELEN);
293  assert(! isDelimChar(buf[decinput->linepos]));
294 
295  /* check if the token is a value */
296  hasdot = FALSE;
297  exptype = DEC_EXP_NONE;
298  if( isValueChar(buf[decinput->linepos], buf[decinput->linepos + 1], TRUE, &hasdot, &exptype) ) /*lint !e679*/
299  {
300  /* read value token */
301  tokenlen = 0;
302  do
303  {
304  assert(tokenlen < DEC_MAX_LINELEN);
305  assert(! isDelimChar(buf[decinput->linepos]));
306  decinput->token[tokenlen] = buf[decinput->linepos];
307  ++tokenlen;
308  ++(decinput->linepos);
309  assert(decinput->linepos < DEC_MAX_LINELEN-1);
310  }
311  while( isValueChar(buf[decinput->linepos], buf[decinput->linepos + 1], FALSE, &hasdot, &exptype) ); /*lint !e679*/
312  }
313  else
314  {
315  /* read non-value token */
316  tokenlen = 0;
317  do
318  {
319  assert(tokenlen < DEC_MAX_LINELEN);
320  decinput->token[tokenlen] = buf[decinput->linepos];
321  tokenlen ++;
322  decinput->linepos ++;
323  if( tokenlen == 1 && isTokenChar(decinput->token[0]) )
324  break;
325  }
326  while( ! isDelimChar(buf[decinput->linepos]) && ! isTokenChar(buf[decinput->linepos]) );
327 
328  /* if the token is an equation sense '<', '>', or '=', skip a following '='
329  * if the token is an equality token '=' and the next character is a '<' or '>', replace the token by the inequality sense
330  */
331  if( tokenlen >= 1
332  && (decinput->token[tokenlen - 1] == '<' || decinput->token[tokenlen - 1] == '>' || decinput->token[tokenlen - 1] == '=')
333  && buf[decinput->linepos] == '=' )
334  {
335  decinput->linepos ++;
336  }
337  else if( decinput->token[tokenlen - 1] == '=' && (buf[decinput->linepos] == '<' || buf[decinput->linepos] == '>') )
338  {
339  decinput->token[tokenlen - 1] = buf[decinput->linepos];
340  decinput->linepos ++;
341  }
342  }
343  assert(tokenlen < DEC_MAX_LINELEN);
344  decinput->token[tokenlen] = '\0';
345 
346  SCIPdebugMessage("(line %d) read token: '%s'\n", decinput->linenumber, decinput->token);
347 
348  return TRUE;
349 }
350 
352 static
354  DECINPUT* decinput
355  )
356 {
357  assert(decinput != NULL);
358  assert(decinput->npushedtokens < DEC_MAX_PUSHEDTOKENS);
359 
360  swapPointers(&decinput->pushedtokens[decinput->npushedtokens], &decinput->token);
361  decinput->npushedtokens ++;
362 }
363 
365 static
367  DECINPUT* decinput
368  )
369 {
370  assert(decinput != NULL);
371 
372  swapPointers(&decinput->token, &decinput->tokenbuf);
373 }
374 
376 static
377 SCIP_Bool isInt(
378  SCIP* scip,
379  DECINPUT* decinput,
380  int* value
381  )
382 {
383  long val;
384  char* endptr;
385 
386  assert(decinput != NULL);
387  assert(value != NULL);
388  assert(!(strcasecmp(decinput->token, "INFINITY") == 0) && !(strcasecmp(decinput->token, "INF") == 0));
389 
390  val = strtol(decinput->token, &endptr, 0);
391  if( endptr != decinput->token && * endptr == '\0' )
392  {
393  if( val < INT_MIN || val > INT_MAX ) /*lint !e685*/
394  return FALSE;
395 
396  *value = (int) val;
397  return TRUE;
398  }
399 
400  return FALSE;
401 }
402 
404 static
405 SCIP_Bool isNewSection(
406  SCIP* scip,
407  DECINPUT* decinput
408  )
409 {
410 
411  assert(decinput != NULL);
412 
413  /* remember first token by swapping the token buffer */
414  swapTokenBuffer(decinput);
415 
416  /* look at next token: if this is a ':', the first token is a name and no section keyword */
417  if( getNextToken(decinput) )
418  {
419  pushToken(decinput);
420  }
421 
422  /* reinstall the previous token by swapping back the token buffer */
423  swapTokenBuffer(decinput);
424 
425  if( strcasecmp(decinput->token, "PRESOLVED") == 0 )
426  {
427  SCIPdebugMessage("(line %d) new section: PRESOLVED\n", decinput->linenumber);
428  decinput->section = DEC_PRESOLVED;
429  return TRUE;
430  }
431 
432  if( strcasecmp(decinput->token, "NBLOCKS") == 0 )
433  {
434  SCIPdebugMessage("(line %d) new section: NBLOCKS\n", decinput->linenumber);
435  decinput->section = DEC_NBLOCKS;
436  return TRUE;
437  }
438 
439  if( strcasecmp(decinput->token, "BLOCK") == 0 )
440  {
441  int blocknr;
442 
443  decinput->section = DEC_BLOCK;
444 
445  if( getNextToken(decinput) )
446  {
447  /* read block number */
448  if( isInt(scip, decinput, &blocknr) )
449  {
450  assert(blocknr >= 0);
451  assert(blocknr <= decinput->nblocks);
452 
453  decinput->blocknr = blocknr - 1;
454  }
455  else
456  syntaxError(scip, decinput, "no block number after block keyword!\n");
457  }
458  else
459  syntaxError(scip, decinput, "no block number after block keyword!\n");
460 
461  SCIPdebugMessage("new section: BLOCK %d\n", decinput->blocknr);
462 
463  return TRUE;
464 
465  }
466 
467  if( strcasecmp(decinput->token, "MASTERCONSS") == 0 )
468  {
469  decinput->section = DEC_MASTERCONSS;
470 
471  SCIPdebugMessage("new section: MASTERCONSS\n");
472 
473  return TRUE;
474  }
475 
476  return FALSE;
477 }
478 
480 static
481 SCIP_RETCODE readStart(
482  SCIP* scip,
483  DECINPUT* decinput
484  )
485 {
486  assert(decinput != NULL);
487 
488  /* everything before first section is treated as comment */
489  do
490  {
491  /* get token */
492  if( ! getNextToken(decinput) )
493  return SCIP_OKAY;
494  }
495  while( ! isNewSection(scip, decinput) );
496 
497  return SCIP_OKAY;
498 }
499 
501 static
502 SCIP_RETCODE readPresolved(
503  SCIP* scip,
504  DECINPUT* decinput
505  )
506 {
507  int presolved;
508 
509  assert(scip != NULL);
510  assert(decinput != NULL);
511 
512  while( getNextToken(decinput) )
513  {
514  /* check if we reached a new section */
515  if( isNewSection(scip, decinput) )
516  return SCIP_OKAY;
517 
518  /* read number of blocks */
519  if( isInt(scip, decinput, &presolved) )
520  {
521  decinput->haspresolvesection = TRUE;
522  if( presolved == 1 )
523  decinput->presolved = TRUE;
524  else if ( presolved == 0 )
525  decinput->presolved = FALSE;
526  else
527  syntaxError(scip, decinput, "presolved parameter must be 0 or 1");
528  SCIPdebugMessage("Decomposition is%s from presolved problem\n",
529  decinput->presolved ? "" : " not");
530  }
531  }
532 
533  return SCIP_OKAY;
534 }
535 
537 static
538 SCIP_RETCODE readNBlocks(
539  SCIP* scip,
540  DECINPUT* decinput
541  )
542 {
543  int nblocks;
544 
545  assert(scip != NULL);
546  assert(decinput != NULL);
547 
548  while( getNextToken(decinput) )
549  {
550  /* check if we reached a new section */
551  if( isNewSection(scip, decinput) )
552  {
553  if( decinput->nblocks == NOVALUE )
554  syntaxError(scip, decinput, "no integer value in nblocks section");
555  else
556  return SCIP_OKAY;
557  }
558 
559  /* read number of blocks */
560  if( isInt(scip, decinput, &nblocks) )
561  {
562  if( decinput->nblocks == NOVALUE )
563  decinput->nblocks = nblocks;
564  else
565  syntaxError(scip, decinput, "2 integer values in nblocks section");
566  SCIPdebugMessage("Number of blocks = %d\n", decinput->nblocks);
567  }
568  }
569 
570  return SCIP_OKAY;
571 }
572 
574 static
575 SCIP_RETCODE readBlock(
576  SCIP* scip,
577  DECINPUT* decinput,
578  SCIP_READERDATA* readerdata
579  )
580 {
581  int blockid;
582 
583  SCIP_Bool success;
584  assert(decinput != NULL);
585  assert(readerdata != NULL);
586 
587  while( getNextToken(decinput) )
588  {
589  int i;
590  SCIP_CONS* cons;
591  SCIP_VAR** curvars = NULL;
592  int ncurvars;
593 
594  SCIP_Bool conshasvar = FALSE;
595  /* check if we reached a new section */
596  if( isNewSection(scip, decinput) )
597  break;
598 
599  /* the token must be the name of an existing cons */
600  cons = SCIPfindCons(scip, decinput->token);
601  if( cons == NULL )
602  {
603  syntaxError(scip, decinput, "unknown constraint in block section");
604  break;
605  }
606 
607  if( !SCIPconsIsActive(cons) )
608  {
609  assert( !SCIPhashmapExists(readerdata->constoblock, cons));
610  continue;
611  }
612 
613  /* get all curvars for the specific constraint */
614  SCIP_CALL( SCIPgetConsNVars(scip, cons, &ncurvars, &success) );
615  assert(success);
616  if( ncurvars > 0 )
617  {
618  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
619  SCIP_CALL( SCIPgetConsVars(scip, cons, curvars, ncurvars, &success) );
620  assert(success);
621  }
622 
623  blockid = decinput->blocknr;
624 
625  for( i = 0; i < ncurvars; i ++ )
626  {
627  assert(curvars != NULL); /* for flexelint */
628  if( decinput->presolved )
629  {
630  SCIP_VAR* var = SCIPvarGetProbvar(curvars[i]);
631  if( !GCGisVarRelevant(var) )
632  continue;
633  }
634 
635  conshasvar = TRUE;
636  }
637 
638  SCIPfreeBufferArrayNull(scip, &curvars);
639 
640  if( !conshasvar )
641  {
642  assert(!SCIPhashmapExists(readerdata->constoblock, cons));
643  SCIPwarningMessage(scip, "Cons <%s> has been deleted by presolving, skipping.\n", SCIPconsGetName(cons));
644  continue;
645  }
646  /*
647  * saving block <-> constraint
648  */
649 
650  assert(SCIPhashmapGetImage(readerdata->constoblock, cons) == (void*)(size_t) LINKINGVALUE);
651 
652  SCIPdebugMessage("cons %s is in block %d\n", SCIPconsGetName(cons), blockid);
653  SCIP_CALL( SCIPhashmapSetImage(readerdata->constoblock, cons, (void*) (size_t) (blockid+1)) );
654  }
655 
656  return SCIP_OKAY;
657 }
658 
660 static
661 SCIP_RETCODE readMasterconss(
662  SCIP* scip,
663  DECINPUT* decinput,
664  SCIP_READERDATA* readerdata
665  )
666 {
667  assert(scip != NULL);
668  assert(decinput != NULL);
669  assert(readerdata != NULL);
670 
671  while( getNextToken(decinput) )
672  {
673  SCIP_CONS* cons;
674 
675  /* check if we reached a new section */
676  if( isNewSection(scip, decinput) )
677  break;
678 
679  /* the token must be the name of an existing constraint */
680  cons = SCIPfindCons(scip, decinput->token);
681  if( cons == NULL )
682  {
683  syntaxError(scip, decinput, "unknown constraint in masterconss section");
684  break;
685  }
686  else
687  {
688  if( !SCIPhashmapExists( readerdata->constoblock, cons) )
689  {
690  SCIPwarningMessage(scip, "Cons <%s> has been deleted by presolving, skipping.\n", SCIPconsGetName(cons));
691  continue;
692  }
693 
694  assert(SCIPhashmapGetImage(readerdata->constoblock, cons) == (void*) (size_t) LINKINGVALUE);
695 
696  SCIPdebugMessage("cons %s is linking constraint\n", decinput->token);
697  }
698  }
699 
700  return SCIP_OKAY;
701 }
702 
704 static
705 SCIP_RETCODE fillDecompStruct(
706  SCIP* scip,
707  DECINPUT* decinput,
708  DEC_DECOMP* decomp,
709  SCIP_READERDATA* readerdata
710  )
711 {
712  int nblocks;
713 
714  SCIP_CONS** conss;
715  int nconss;
716  int i;
717  SCIP_HASHMAP* constoblock;
718  assert(scip != NULL);
719  assert(decinput != NULL);
720  assert(decomp != NULL);
721  assert(readerdata != NULL);
722 
723  nblocks = decinput->nblocks;
724 
725  DECdecompSetPresolved(decomp, decinput->presolved);
726  DECdecompSetNBlocks(decomp, nblocks);
727  DECdecompSetDetector(decomp, NULL);
728 
729  nconss = SCIPgetNConss(scip);
730  conss = SCIPgetConss(scip);
731 
732  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(scip), nconss) );
733 
734  for( i = 0; i < nconss; ++i )
735  {
736 
737  int blockid;
738  assert(SCIPhashmapExists(readerdata->constoblock, conss[i]));
739  blockid = (int) (size_t) SCIPhashmapGetImage(readerdata->constoblock, conss[i]); /*lint !e507*/
740  if( blockid == LINKINGVALUE )
741  {
742  blockid = decinput->nblocks+1;
743  SCIP_CALL( SCIPhashmapSetImage(constoblock, conss[i], (void*) (size_t) (nblocks+1)) );
744  }
745 
746  SCIP_CALL( SCIPhashmapSetImage(constoblock, conss[i], (void*) (size_t) blockid) );
747  }
748 
749 
750  SCIP_CALL_QUIET( DECfilloutDecompFromConstoblock(scip, decomp, constoblock, nblocks, FALSE) );
751  return SCIP_OKAY;
752 }
753 
755 static
756 SCIP_RETCODE readDECFile(
757  SCIP* scip,
758  SCIP_READER* reader,
759  DECINPUT* decinput,
760  const char* filename
761  )
762 {
763  SCIP_RETCODE retcode;
764  SCIP_READERDATA* readerdata;
765  SCIP_CONS** conss;
766  DEC_DECOMP* decdecomp;
767  int nconss;
768  int i;
769 
770  assert(decinput != NULL);
771  assert(scip != NULL);
772  assert(reader != NULL);
773 
774  if( SCIPgetStage(scip) == SCIP_STAGE_INIT || SCIPgetNVars(scip) == 0 || SCIPgetNConss(scip) == 0 )
775  {
776  SCIPverbMessage(scip, SCIP_VERBLEVEL_DIALOG, NULL, "No problem exists, will not read structure!\n");
777 
778  return SCIP_OKAY;
779  }
780 
781  /* open file */
782  decinput->file = SCIPfopen(filename, "r");
783  if( decinput->file == NULL )
784  {
785  SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
786  SCIPprintSysError(filename);
787  return SCIP_NOFILE;
788  }
789 
790  readerdata = SCIPreaderGetData(reader);
791  assert(readerdata != NULL);
792 
793  conss = SCIPgetConss(scip);
794  nconss = SCIPgetNConss(scip);
795 
796  /* cons -> block mapping */
797  SCIP_CALL( SCIPhashmapCreate(&readerdata->constoblock, SCIPblkmem(scip), nconss) );
798  for( i = 0; i < nconss; i ++ )
799  {
800  SCIP_CALL( SCIPhashmapInsert(readerdata->constoblock, conss[i], (void*) (size_t) LINKINGVALUE) );
801  }
802 
803  /* parse the file */
804  decinput->section = DEC_START;
805  retcode = SCIP_OKAY;
806 
807  while( decinput->section != DEC_END && ! hasError(decinput) && retcode == SCIP_OKAY )
808  {
809  switch( decinput->section )
810  {
811  case DEC_START:
812  SCIP_CALL( readStart(scip, decinput) );
813  break;
815  case DEC_PRESOLVED:
816  SCIP_CALL( readPresolved(scip, decinput) );
817  if( decinput->presolved && SCIPgetStage(scip) < SCIP_STAGE_PRESOLVED )
818  {
819  assert(decinput->haspresolvesection);
820  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "decomposition belongs to the presolved problem, please presolve the problem first.\n");
821  retcode = SCIP_READERROR;
822  break;
823  }
824  break;
825 
826  case DEC_NBLOCKS:
827  SCIP_CALL( readNBlocks(scip, decinput) );
828  if( decinput->haspresolvesection && !decinput->presolved && SCIPgetStage(scip) >= SCIP_STAGE_PRESOLVED )
829  {
830  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "decomposition belongs to the unpresolved problem, please re-read the problem and read the decomposition without presolving.\n");
831  retcode = SCIP_READERROR;
832  break;
833 
834  }
835  if( !decinput->haspresolvesection )
836  {
837  SCIPwarningMessage(scip, "decomposition has no presolve section at beginning. The behaviour is undefined. See the FAQ for further information.\n");
838  }
839  break;
840 
841  case DEC_BLOCK:
842  SCIP_CALL( readBlock(scip, decinput, readerdata) );
843  break;
844 
845  case DEC_MASTERCONSS:
846  SCIP_CALL( readMasterconss(scip, decinput, readerdata) );
847  break;
848 
849  case DEC_END: /* this is already handled in the while() loop */
850  default:
851  SCIPerrorMessage("invalid DEC file section <%d>\n", decinput->section);
852  return SCIP_INVALIDDATA;
853  }
854  }
855 
856  SCIP_CALL( DECdecompCreate(scip, &decdecomp) );
857 
858  if( retcode == SCIP_OKAY )
859  {
860  /* fill decomp */
861  retcode = fillDecompStruct(scip, decinput, decdecomp, readerdata);
862  }
863 
864  if( retcode == SCIP_OKAY )
865  {
866  /* add decomp to cons_decomp */
867  SCIP_CALL( SCIPconshdlrDecompAddDecdecomp(scip, decdecomp) );
868  }
869  else
870  {
871  SCIP_CALL( DECdecompFree(scip, &decdecomp) );
872  }
873  SCIPhashmapFree(&readerdata->constoblock);
874 
875  /* close file */
876  SCIPfclose(decinput->file);
877 
878  return retcode;
879 }
880 
881 
882 /*
883  * Callback methods of reader
884  */
885 
887 static
888 SCIP_DECL_READERFREE(readerFreeDec)
889 {
890  SCIP_READERDATA* readerdata;
891 
892  readerdata = SCIPreaderGetData(reader);
893  assert(readerdata != NULL);
894 
895  SCIPfreeMemory(scip, &readerdata);
896 
897  return SCIP_OKAY;
898 }
899 
901 static
902 SCIP_DECL_READERREAD(readerReadDec)
903 { /*lint --e{715}*/
904  if( SCIPgetStage(scip) == SCIP_STAGE_INIT || SCIPgetNVars(scip) == 0 || SCIPgetNConss(scip) == 0 )
905  {
906  SCIPverbMessage(scip, SCIP_VERBLEVEL_DIALOG, NULL, "Please read in a problem before reading in the corresponding structure file!\n");
907  return SCIP_OKAY;
908  }
909 
910  SCIP_CALL( SCIPreadDec(scip, filename, result) );
911 
912  return SCIP_OKAY;
913 }
914 
916 static
917 SCIP_DECL_READERWRITE(readerWriteDec)
918 { /*lint --e{715}*/
919  assert(scip != NULL);
920  assert(reader != NULL);
921 
922  SCIP_CALL( GCGwriteDecomp(scip, file, DECgetBestDecomp(scip)) );
923  *result = SCIP_SUCCESS;
924 
925  return SCIP_OKAY;
926 }
927 
928 /*
929  * reader specific interface methods
930  */
931 
933 SCIP_RETCODE
935  SCIP* scip
936  )
937 {
938  SCIP_READERDATA* readerdata;
939 
940  /* create dec reader data */
941  SCIP_CALL( SCIPallocMemory(scip, &readerdata) );
942 
943  /* include dec reader */
944  SCIP_CALL(SCIPincludeReader(scip, READER_NAME, READER_DESC, READER_EXTENSION, NULL,
945  readerFreeDec, readerReadDec, readerWriteDec, readerdata));
946 
947  return SCIP_OKAY;
948 }
949 
950 /* reads problem from file */
951 SCIP_RETCODE SCIPreadDec(
952  SCIP* scip,
953  const char* filename,
954  SCIP_RESULT* result
955  )
956 {
957  SCIP_RETCODE retcode;
958  SCIP_READER* reader;
959  DECINPUT decinput;
960  int i;
961 
962  if( SCIPgetStage(scip) < SCIP_STAGE_TRANSFORMED )
963  SCIP_CALL( SCIPtransformProb(scip) );
964 
965  reader = SCIPfindReader(scip, READER_NAME);
966  assert(reader != NULL);
967 
968  /* initialize DEC input data */
969  decinput.file = NULL;
970  decinput.linebuf[0] = '\0';
971  SCIP_CALL( SCIPallocMemoryArray(scip, &decinput.token, DEC_MAX_LINELEN) ); /*lint !e506*/
972  decinput.token[0] = '\0';
973  SCIP_CALL( SCIPallocMemoryArray(scip, &decinput.tokenbuf, DEC_MAX_LINELEN) ); /*lint !e506*/
974  decinput.tokenbuf[0] = '\0';
975  for( i = 0; i < DEC_MAX_PUSHEDTOKENS; ++ i )
976  {
977  SCIP_CALL( SCIPallocMemoryArray(scip, &decinput.pushedtokens[i], DEC_MAX_LINELEN) ); /*lint !e506 !e866*/
978  }
979 
980  decinput.npushedtokens = 0;
981  decinput.linenumber = 0;
982  decinput.linepos = 0;
983  decinput.section = DEC_START;
984  decinput.presolved = FALSE;
985  decinput.haspresolvesection = FALSE;
986  decinput.nblocks = NOVALUE;
987  decinput.blocknr = - 2;
988  decinput.haserror = FALSE;
989 
990  /* read the file */
991  retcode = readDECFile(scip, reader, &decinput, filename);
992 
993  /* free dynamically allocated memory */
994  SCIPfreeMemoryArray(scip, &decinput.token);
995  SCIPfreeMemoryArray(scip, &decinput.tokenbuf);
996  for( i = 0; i < DEC_MAX_PUSHEDTOKENS; ++ i )
997  {
998  SCIPfreeMemoryArray(scip, &decinput.pushedtokens[i]);
999  }
1000 
1001  /* evaluate the result */
1002  if( decinput.haserror )
1003  return SCIP_READERROR;
1004  else if( retcode == SCIP_OKAY )
1005  {
1006  *result = SCIP_SUCCESS;
1007  }
1008 
1009  return retcode;
1010 }
1011 
1013 static
1014 SCIP_RETCODE writeData(
1015  SCIP* scip,
1016  FILE* file,
1017  DEC_DECOMP* decdecomp
1018  )
1019 {
1020  SCIP_CONS*** subscipconss;
1021  SCIP_CONS** linkingconss;
1022  int* nsubscipconss;
1023  int nlinkingconss;
1024  int nblocks;
1025  SCIP_Bool presolved;
1026  int i;
1027  int j;
1028 
1029  assert(scip != NULL);
1030  assert(decdecomp != NULL);
1031 
1032  assert(DECdecompGetType(decdecomp) == DEC_DECTYPE_ARROWHEAD
1033  || DECdecompGetType(decdecomp) == DEC_DECTYPE_BORDERED
1034  || DECdecompGetType(decdecomp) == DEC_DECTYPE_DIAGONAL
1035  || DECdecompGetType(decdecomp) == DEC_DECTYPE_UNKNOWN
1036  || DECdecompGetType(decdecomp) == DEC_DECTYPE_STAIRCASE);
1037  SCIPdebugMessage("DEC_DECOMP Type: %s\n", DECgetStrType(DECdecompGetType(decdecomp)));
1038 
1039  /* if we don't have staicase, but something else, go through the blocks and create the indices */
1040  /* subscip conss */
1041  subscipconss = DECdecompGetSubscipconss(decdecomp);
1042  nsubscipconss = DECdecompGetNSubscipconss(decdecomp);
1043  assert(subscipconss != NULL);
1044  assert(nsubscipconss != NULL);
1045 
1046  /* linking cons */
1047  linkingconss = DECdecompGetLinkingconss(decdecomp);
1048  nlinkingconss = DECdecompGetNLinkingconss(decdecomp);
1049  assert(nlinkingconss >= 0 && nlinkingconss < SCIPgetNConss(scip));
1050  assert(linkingconss != NULL || nlinkingconss == 0 );
1051 
1052  presolved = DECdecompGetPresolved(decdecomp);
1053 
1054  SCIPinfoMessage(scip, file, "PRESOLVED\n");
1055  SCIPinfoMessage(scip, file, "%d\n", presolved ? 1 : 0);
1056 
1057  nblocks = DECdecompGetNBlocks(decdecomp);
1058 
1059  SCIPinfoMessage(scip, file, "NBLOCKS\n");
1060  SCIPinfoMessage(scip, file, "%d\n", nblocks);
1061 
1062  for( i = 0; i < nblocks; i ++ )
1063  {
1064  SCIPinfoMessage(scip, file, "BLOCK %d\n", i + 1);
1065  for( j = 0; j < nsubscipconss[i]; j ++ )
1066  {
1067  SCIPinfoMessage(scip, file, "%s\n", SCIPconsGetName(subscipconss[i][j]));
1068  }
1069  }
1070 
1071  if( nlinkingconss > 0 )
1072  {
1073  assert(linkingconss != NULL); /* for flexelint */
1074  SCIPinfoMessage(scip, file, "MASTERCONSS\n");
1075  for( i = 0; i < nlinkingconss; i ++ )
1076  {
1077  SCIPinfoMessage(scip, file, "%s\n", SCIPconsGetName(linkingconss[i]));
1078  }
1079  }
1080 
1081  return SCIP_OKAY;
1082 }
1083 
1085 SCIP_RETCODE GCGwriteDecomp(
1086  SCIP* scip,
1087  FILE* file,
1088  DEC_DECOMP* decdecomp
1089  )
1090 {
1091  char outname[SCIP_MAXSTRLEN];
1092  assert(scip != NULL);
1093 
1094  if( decdecomp == NULL )
1095  {
1096  SCIPwarningMessage(scip, "Cannot write decomposed problem if decomposition structure is empty!\n");
1097 
1098  (void) SCIPsnprintf(outname, SCIP_MAXSTRLEN, "%s", SCIPgetProbName(scip));
1099  }
1100  else
1101  {
1102  (void) SCIPsnprintf(outname, SCIP_MAXSTRLEN, "%s_%d", SCIPgetProbName(scip), DECdecompGetNBlocks(decdecomp));
1103 
1104  SCIP_CALL( writeData(scip, file, decdecomp) );
1105  }
1106 
1107  return SCIP_OKAY;
1108 }
SCIP_CONS *** DECdecompGetSubscipconss(DEC_DECOMP *decomp)
Definition: decomp.c:729
static SCIP_DECL_READERFREE(readerFreeDec)
Definition: reader_dec.c:888
static void swapTokenBuffer(DECINPUT *decinput)
Definition: reader_dec.c:366
static void pushToken(DECINPUT *decinput)
Definition: reader_dec.c:353
static SCIP_RETCODE fillDecompStruct(SCIP *scip, DECINPUT *decinput, DEC_DECOMP *decomp, SCIP_READERDATA *readerdata)
Definition: reader_dec.c:705
const char * DECgetStrType(DEC_DECTYPE type)
Definition: decomp.c:342
#define READER_NAME
Definition: reader_dec.c:53
static SCIP_Bool isTokenChar(char c)
Definition: reader_dec.c:166
#define READER_EXTENSION
Definition: reader_dec.c:55
static const char tokenchars[]
Definition: reader_dec.c:106
static const int LINKINGVALUE
Definition: reader_dec.c:104
static SCIP_Bool isValueChar(char c, char nextc, SCIP_Bool firstchar, SCIP_Bool *hasdot, DECEXPTYPE *exptype)
Definition: reader_dec.c:175
DEC_DECOMP * DECgetBestDecomp(SCIP *scip)
Definition: cons_decomp.c:735
static SCIP_RETCODE readBlock(SCIP *scip, DECINPUT *decinput, SCIP_READERDATA *readerdata)
Definition: reader_dec.c:575
static SCIP_Bool getNextLine(DECINPUT *decinput)
Definition: reader_dec.c:196
static SCIP_Bool isDelimChar(char c)
Definition: reader_dec.c:157
static SCIP_RETCODE readStart(SCIP *scip, DECINPUT *decinput)
Definition: reader_dec.c:481
SCIP_RETCODE SCIPreadDec(SCIP *scip, const char *filename, SCIP_RESULT *result)
Definition: reader_dec.c:951
char * tokenbuf
Definition: reader_dec.c:84
int blocknr
Definition: reader_dec.c:92
static SCIP_Bool isNewSection(SCIP *scip, DECINPUT *decinput)
Definition: reader_dec.c:405
int linenumber
Definition: reader_dec.c:87
char linebuf[DEC_MAX_LINELEN]
Definition: reader_dec.c:82
SCIP_RETCODE DECdecompFree(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:388
DEC file reader for structure information.
SCIP_HASHMAP * constoblock
Definition: reader_blk.c:118
SCIP_Bool presolved
Definition: reader_dec.c:89
SCIP_Bool haspresolvesection
Definition: reader_dec.c:90
void DECdecompSetNBlocks(DEC_DECOMP *decomp, int nblocks)
Definition: decomp.c:560
static SCIP_DECL_READERWRITE(readerWriteDec)
Definition: reader_dec.c:917
SCIP_Bool haserror
Definition: reader_dec.c:94
static SCIP_RETCODE readDECFile(SCIP *scip, SCIP_READER *reader, DECINPUT *decinput, const char *filename)
Definition: reader_dec.c:756
int DECdecompGetNLinkingconss(DEC_DECOMP *decomp)
Definition: decomp.c:798
SCIP_FILE * file
Definition: reader_dec.c:81
DEC_DECTYPE DECdecompGetType(DEC_DECOMP *decomp)
Definition: decomp.c:529
int DECdecompGetNBlocks(DEC_DECOMP *decomp)
Definition: decomp.c:572
static SCIP_Bool hasError(DECINPUT *decinput)
Definition: reader_dec.c:146
various SCIP helper methods
void DECdecompSetDetector(DEC_DECOMP *decomp, DEC_DETECTOR *detector)
Definition: decomp.c:1346
#define DEC_MAX_PUSHEDTOKENS
Definition: reader_dec.c:62
SCIP_RETCODE DECdecompCreate(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:351
SCIP_CONS ** DECdecompGetLinkingconss(DEC_DECOMP *decomp)
Definition: decomp.c:788
int * DECdecompGetNSubscipconss(DEC_DECOMP *decomp)
Definition: decomp.c:738
static SCIP_RETCODE writeData(SCIP *scip, FILE *file, DEC_DECOMP *decdecomp)
Definition: reader_dec.c:1014
DecSection
Definition: reader_dec.c:65
int linepos
Definition: reader_dec.c:88
SCIP_Bool GCGisVarRelevant(SCIP_VAR *var)
Definition: scip_misc.c:40
#define DEC_MAX_LINELEN
Definition: reader_dec.c:61
SCIP_RETCODE SCIPincludeReaderDec(SCIP *scip)
Definition: reader_dec.c:934
static SCIP_RETCODE readMasterconss(SCIP *scip, DECINPUT *decinput, SCIP_READERDATA *readerdata)
Definition: reader_dec.c:661
SCIP_RETCODE SCIPconshdlrDecompAddDecdecomp(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: cons_decomp.c:288
char * token
Definition: reader_dec.c:83
public methods for GCG variables
static SCIP_RETCODE readNBlocks(SCIP *scip, DECINPUT *decinput)
Definition: reader_dec.c:538
static SCIP_Bool getNextToken(DECINPUT *decinput)
Definition: reader_dec.c:254
#define READER_DESC
Definition: reader_dec.c:54
static const char delimchars[]
Definition: reader_dec.c:105
SCIP_RETCODE DECfilloutDecompFromConstoblock(SCIP *scip, DEC_DECOMP *decomp, SCIP_HASHMAP *constoblock, int nblocks, SCIP_Bool staircase)
Definition: decomp.c:1225
int nblocks
Definition: reader_dec.c:91
int npushedtokens
Definition: reader_dec.c:86
enum DecSection DECSECTION
Definition: reader_dec.c:69
void DECdecompSetPresolved(DEC_DECOMP *decomp, SCIP_Bool presolved)
Definition: decomp.c:539
static const char commentchars[]
Definition: reader_dec.c:107
SCIP_RETCODE GCGwriteDecomp(SCIP *scip, FILE *file, DEC_DECOMP *decdecomp)
Definition: reader_dec.c:1085
DecExpType
Definition: reader_dec.c:72
static void swapPointers(char **pointer1, char **pointer2)
Definition: reader_dec.c:240
static void syntaxError(SCIP *scip, DECINPUT *decinput, const char *msg)
Definition: reader_dec.c:118
constraint handler for structure detection
static SCIP_Bool isInt(SCIP *scip, DECINPUT *decinput, int *value)
Definition: reader_dec.c:377
static const int NOVALUE
Definition: reader_dec.c:103
static SCIP_RETCODE readPresolved(SCIP *scip, DECINPUT *decinput)
Definition: reader_dec.c:502
struct DecDecomp DEC_DECOMP
Definition: type_decomp.h:43
static SCIP_DECL_READERREAD(readerReadDec)
Definition: reader_dec.c:902
DECSECTION section
Definition: reader_dec.c:93
char * pushedtokens[DEC_MAX_PUSHEDTOKENS]
Definition: reader_dec.c:85
public methods for working with decomposition structures
enum DecExpType DECEXPTYPE
Definition: reader_dec.c:76
SCIP_Bool DECdecompGetPresolved(DEC_DECOMP *decomp)
Definition: decomp.c:550