reader_blk.cpp
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-2018 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 
48 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
49 
50 #include <stdlib.h>
51 #include <assert.h>
52 #include <string.h>
53 #if defined(_WIN32) || defined(_WIN64)
54 #else
55 #include <strings.h> /*lint --e{766}*/ /* needed for strcasecmp() */
56 #endif
57 #include <ctype.h>
58 
59 #include "reader_blk.h"
60 #include "relax_gcg.h"
61 #include "pub_gcgvar.h"
62 #include "pub_decomp.h"
63 #include "cons_decomp.h"
64 #include "scip_misc.h"
65 
66 #define READER_NAME "blkreader"
67 #define READER_DESC "file reader for structures in blk format"
68 #define READER_EXTENSION "blk"
69 
70 /*
71  * Data structures
72  */
73 #define BLK_MAX_LINELEN 65536
74 #define BLK_MAX_PUSHEDTOKENS 2
75 
78 {
80 };
81 typedef enum BlkSection BLKSECTION;
82 
85 {
87 };
88 typedef enum BlkExpType BLKEXPTYPE;
89 
90 
92 struct BlkInput
93 {
94  SCIP_FILE* file;
96  char* token;
97  char* tokenbuf;
101  int linepos;
102  SCIP_Bool presolved;
103  SCIP_Bool haspresolvesection;
104  int nblocks;
105  int blocknr;
107  SCIP_Bool haserror;
108 };
109 typedef struct BlkInput BLKINPUT;
110 
113 {
114  int* varstoblock;
115  int* nblockvars;
118  SCIP_HASHMAP* constoblock;
119  SCIP_CONS*** blockcons;
120  int* nblockcons;
123 };
124 
125 static const int NOVALUE = -1;
126 static const int LINKINGVALUE = -2;
127 static const char delimchars[] = " \f\n\r\t\v";
128 static const char tokenchars[] = "-+:<>=";
129 static const char commentchars[] = "\\";
130 
131 
132 
133 
134 /*
135  * Local methods (for reading)
136  */
137 
139 static
141  SCIP* scip,
142  BLKINPUT* blkinput,
143  const char* msg
144  )
145 {
146  char formatstr[256];
147 
148  assert(blkinput != NULL);
149 
150  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error in line %d: %s ('%s')\n",
151  blkinput->linenumber, msg, blkinput->token);
152  if( blkinput->linebuf[strlen(blkinput->linebuf)-1] == '\n' )
153  {
154  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, " input: %s", blkinput->linebuf);
155  }
156  else
157  {
158  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, " input: %s\n", blkinput->linebuf);
159  }
160  (void) SCIPsnprintf(formatstr, 256, " %%%ds\n", blkinput->linepos);
161  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, formatstr, "^");
162  blkinput->section = BLK_END;
163  blkinput->haserror = TRUE;
164 }
165 
167 static
168 SCIP_Bool hasError(
169  BLKINPUT* blkinput
170  )
171 {
172  assert(blkinput != NULL);
173 
174  return blkinput->haserror;
175 }
176 
178 static
179 SCIP_Bool isDelimChar(
180  char c
181  )
182 {
183  return (c == '\0') || (strchr(delimchars, c) != NULL);
184 }
185 
187 static
188 SCIP_Bool isTokenChar(
189  char c
190  )
191 {
192  return (strchr(tokenchars, c) != NULL);
193 }
194 
196 static
197 SCIP_Bool isValueChar(
198  char c,
199  char nextc,
200  SCIP_Bool firstchar,
201  SCIP_Bool* hasdot,
202  BLKEXPTYPE* exptype
203  )
204 {
205  assert(hasdot != NULL);
206  assert(exptype != NULL);
207 
208  if( isdigit(c) )
209  return TRUE;
210  else if( (*exptype == BLK_EXP_NONE) && !(*hasdot) && (c == '.') )
211  {
212  *hasdot = TRUE;
213  return TRUE;
214  }
215  else if( !firstchar && (*exptype == BLK_EXP_NONE) && (c == 'e' || c == 'E') )
216  {
217  if( nextc == '+' || nextc == '-' )
218  {
219  *exptype = BLK_EXP_SIGNED;
220  return TRUE;
221  }
222  else if( isdigit(nextc) )
223  {
224  *exptype = BLK_EXP_UNSIGNED;
225  return TRUE;
226  }
227  }
228  else if( (*exptype == BLK_EXP_SIGNED) && (c == '+' || c == '-') )
229  {
230  *exptype = BLK_EXP_UNSIGNED;
231  return TRUE;
232  }
233 
234  return FALSE;
235 }
236 
240 static
241 SCIP_Bool getNextLine(
242  BLKINPUT* blkinput
243  )
244 {
245  int i;
246 
247  assert(blkinput != NULL);
248 
249  /* clear the line */
250  BMSclearMemoryArray(blkinput->linebuf, BLK_MAX_LINELEN);
251 
252  /* read next line */
253  blkinput->linepos = 0;
254  blkinput->linebuf[BLK_MAX_LINELEN-2] = '\0';
255  if( SCIPfgets(blkinput->linebuf, BLK_MAX_LINELEN, blkinput->file) == NULL )
256  return FALSE;
257  blkinput->linenumber++;
258  if( blkinput->linebuf[BLK_MAX_LINELEN-2] != '\0' )
259  {
260  SCIPerrorMessage("Error: line %d exceeds %d characters\n", blkinput->linenumber, BLK_MAX_LINELEN-2);
261  blkinput->haserror = TRUE;
262  return FALSE;
263  }
264  blkinput->linebuf[BLK_MAX_LINELEN-1] = '\0';
265  blkinput->linebuf[BLK_MAX_LINELEN-2] = '\0'; /* we want to use lookahead of one char -> we need two \0 at the end */
266 
267  /* skip characters after comment symbol */
268  for( i = 0; commentchars[i] != '\0'; ++i )
269  {
270  char* commentstart;
271 
272  commentstart = strchr(blkinput->linebuf, commentchars[i]);
273  if( commentstart != NULL )
274  {
275  *commentstart = '\0';
276  *(commentstart+1) = '\0'; /* we want to use lookahead of one char -> we need two \0 at the end */
277  }
278  }
279 
280  return TRUE;
281 }
282 
284 static
286  char** pointer1,
287  char** pointer2
288  )
289 {
290  char* tmp;
291 
292  tmp = *pointer1;
293  *pointer1 = *pointer2;
294  *pointer2 = tmp;
295 }
296 
298 static
299 SCIP_Bool getNextToken(
300  BLKINPUT* blkinput
301  )
302 {
303  SCIP_Bool hasdot;
304  BLKEXPTYPE exptype;
305  char* buf;
306  int tokenlen;
307 
308  assert(blkinput != NULL);
309  assert(blkinput->linepos < BLK_MAX_LINELEN);
310 
311  /* check the token stack */
312  if( blkinput->npushedtokens > 0 )
313  {
314  swapPointers(&blkinput->token, &blkinput->pushedtokens[blkinput->npushedtokens-1]);
315  blkinput->npushedtokens--;
316  SCIPdebugMessage("(line %d) read token again: '%s'\n", blkinput->linenumber, blkinput->token);
317  return TRUE;
318  }
319 
320  /* skip delimiters */
321  buf = blkinput->linebuf;
322  while( isDelimChar(buf[blkinput->linepos]) )
323  {
324  if( buf[blkinput->linepos] == '\0' )
325  {
326  if( !getNextLine(blkinput) )
327  {
328  blkinput->section = BLK_END;
329  SCIPdebugMessage("(line %d) end of file\n", blkinput->linenumber);
330  return FALSE;
331  }
332  assert(blkinput->linepos == 0);
333  }
334  else
335  blkinput->linepos++;
336  }
337  assert(blkinput->linepos < BLK_MAX_LINELEN);
338  assert(!isDelimChar(buf[blkinput->linepos]));
339 
340  /* check if the token is a value */
341  hasdot = FALSE;
342  exptype = BLK_EXP_NONE;
343  if( isValueChar(buf[blkinput->linepos], buf[blkinput->linepos+1], TRUE, &hasdot, &exptype) ) /*lint !e679*/
344  {
345  /* read value token */
346  tokenlen = 0;
347  do
348  {
349  assert(tokenlen < BLK_MAX_LINELEN);
350  assert(!isDelimChar(buf[blkinput->linepos]));
351  blkinput->token[tokenlen] = buf[blkinput->linepos];
352  ++tokenlen;
353  ++(blkinput->linepos);
354  assert(blkinput->linepos < BLK_MAX_LINELEN);
355  }
356  while( isValueChar(buf[blkinput->linepos], buf[blkinput->linepos+1], FALSE, &hasdot, &exptype) ); /*lint !e679*/
357  }
358  else
359  {
360  /* read non-value token */
361  tokenlen = 0;
362  do
363  {
364  assert(tokenlen < BLK_MAX_LINELEN);
365  blkinput->token[tokenlen] = buf[blkinput->linepos];
366  tokenlen++;
367  blkinput->linepos++;
368  if( tokenlen == 1 && isTokenChar(blkinput->token[0]) )
369  break;
370  }
371  while( !isDelimChar(buf[blkinput->linepos]) && !isTokenChar(buf[blkinput->linepos]) );
372 
373  /* if the token is an equation sense '<', '>', or '=', skip a following '='
374  * if the token is an equality token '=' and the next character is a '<' or '>', replace the token by the inequality sense
375  */
376  if( tokenlen >= 1
377  && (blkinput->token[tokenlen-1] == '<' || blkinput->token[tokenlen-1] == '>' || blkinput->token[tokenlen-1] == '=')
378  && buf[blkinput->linepos] == '=' )
379  {
380  blkinput->linepos++;
381  }
382  else if( blkinput->token[tokenlen-1] == '=' && (buf[blkinput->linepos] == '<' || buf[blkinput->linepos] == '>') )
383  {
384  blkinput->token[tokenlen-1] = buf[blkinput->linepos];
385  blkinput->linepos++;
386  }
387  }
388  assert(tokenlen < BLK_MAX_LINELEN);
389  blkinput->token[tokenlen] = '\0';
390 
391  SCIPdebugMessage("(line %d) read token: '%s'\n", blkinput->linenumber, blkinput->token);
392 
393  return TRUE;
394 }
395 
397 static
399  BLKINPUT* blkinput
400  )
401 {
402  assert(blkinput != NULL);
403  assert(blkinput->npushedtokens < BLK_MAX_PUSHEDTOKENS);
404 
405  swapPointers(&blkinput->pushedtokens[blkinput->npushedtokens], &blkinput->token);
406  blkinput->npushedtokens++;
407 }
408 
410 static
412  BLKINPUT* blkinput
413  )
414 {
415  assert(blkinput != NULL);
416 
417  swapPointers(&blkinput->token, &blkinput->tokenbuf);
418 }
419 
421 static
422 SCIP_Bool isInt(
423  SCIP* scip,
424  BLKINPUT* blkinput,
425  int* value
426  )
427 {
428  long val;
429  char* endptr;
430 
431  assert(blkinput != NULL);
432  assert(value != NULL);
433  assert(!(strcasecmp(blkinput->token, "INFINITY") == 0) && !(strcasecmp(blkinput->token, "INF") == 0));
434 
435  val = strtol(blkinput->token, &endptr, 0);
436  if( endptr != blkinput->token && *endptr == '\0' )
437  {
438  if(val < INT_MIN || val > INT_MAX ) /*lint !e685*/
439  return FALSE;
440 
441  *value = (int) val;
442  return TRUE;
443  }
444 
445  return FALSE;
446 }
447 
449 static
450 SCIP_Bool isNewSection(
451  SCIP* scip,
452  BLKINPUT* blkinput
453  )
454 {
455  SCIP_Bool iscolon;
456 
457  assert(blkinput != NULL);
458 
459  /* remember first token by swapping the token buffer */
460  swapTokenBuffer(blkinput);
461 
462  /* look at next token: if this is a ':', the first token is a name and no section keyword */
463  iscolon = FALSE;
464  if( getNextToken(blkinput) )
465  {
466  iscolon = (strcmp(blkinput->token, ":") == 0);
467  pushToken(blkinput);
468  }
469 
470  /* reinstall the previous token by swapping back the token buffer */
471  swapTokenBuffer(blkinput);
472 
473  /* check for ':' */
474  if( iscolon )
475  return FALSE;
476 
477  if( strcasecmp(blkinput->token, "PRESOLVED") == 0 )
478  {
479  SCIPdebugMessage("(line %d) new section: PRESOLVED\n", blkinput->linenumber);
480  blkinput->section = BLK_PRESOLVED;
481  return TRUE;
482  }
483 
484  if( strcasecmp(blkinput->token, "NBLOCKS") == 0 )
485  {
486  SCIPdebugMessage("(line %d) new section: NBLOCKS\n", blkinput->linenumber);
487  blkinput->section = BLK_NBLOCKS;
488  return TRUE;
489  }
490 
491  if( strcasecmp(blkinput->token, "BLOCK") == 0 )
492  {
493  int blocknr;
494 
495  blkinput->section = BLK_BLOCK;
496 
497  if( getNextToken(blkinput) )
498  {
499  /* read block number */
500  if( isInt(scip, blkinput, &blocknr) )
501  {
502  assert(blocknr >= 0);
503  assert(blocknr <= blkinput->nblocks);
504 
505  blkinput->blocknr = blocknr-1;
506  }
507  else
508  syntaxError(scip, blkinput, "no block number after block keyword!\n");
509  }
510  else
511  syntaxError(scip, blkinput, "no block number after block keyword!\n");
512 
513  SCIPdebugMessage("new section: BLOCK %d\n", blkinput->blocknr);
514 
515  return TRUE;
516 
517  }
518 
519  if( strcasecmp(blkinput->token, "MASTERCONSS") == 0 )
520  {
521  blkinput->section = BLK_MASTERCONSS;
522 
523  SCIPdebugMessage("new section: MASTERCONSS\n");
524 
525  return TRUE;
526  }
527 
528  if( strcasecmp(blkinput->token, "END") == 0 )
529  {
530  SCIPdebugMessage("(line %d) new section: END\n", blkinput->linenumber);
531  blkinput->section = BLK_END;
532  return TRUE;
533  }
534 
535  return FALSE;
536 }
537 
539 static
540 SCIP_RETCODE readStart(
541  SCIP* scip,
542  BLKINPUT* blkinput
543  )
544 {
545  assert(blkinput != NULL);
546 
547  /* everything before first section is treated as comment */
548  do
549  {
550  /* get token */
551  if( !getNextToken(blkinput) )
552  return SCIP_OKAY;
553  }
554  while( !isNewSection(scip, blkinput) );
555 
556  return SCIP_OKAY;
557 }
558 
560 static
561 SCIP_RETCODE readPresolved(
562  SCIP* scip,
563  BLKINPUT* blkinput
564  )
565 {
566  int presolved;
567 
568  assert(scip != NULL);
569  assert(blkinput != NULL);
570 
571  while( getNextToken(blkinput) )
572  {
573  /* check if we reached a new section */
574  if( isNewSection(scip, blkinput) )
575  return SCIP_OKAY;
576 
577  /* read number of blocks */
578  if( isInt(scip, blkinput, &presolved) )
579  {
580  blkinput->haspresolvesection = TRUE;
581  if( presolved == 1 )
582  blkinput->presolved = TRUE;
583  else if ( presolved == 0 )
584  blkinput->presolved = FALSE;
585  else
586  syntaxError(scip, blkinput, "presolved parameter must be 0 or 1");
587  SCIPdebugMessage("Decomposition is%s from presolved problem\n",
588  blkinput->presolved ? "" : " not");
589  }
590  }
591 
592  return SCIP_OKAY;
593 }
594 
596 static
597 SCIP_RETCODE readNBlocks(
598  SCIP* scip,
599  BLKINPUT* blkinput
600  )
601 {
602  int nblocks;
603 
604  assert(scip != NULL);
605  assert(blkinput != NULL);
606 
607  while( getNextToken(blkinput) )
608  {
609  /* check if we reached a new section */
610  if( isNewSection(scip, blkinput) )
611  {
612  if( blkinput->nblocks == NOVALUE )
613  syntaxError(scip, blkinput, "no integer value in nblocks section");
614  else
615  return SCIP_OKAY;
616  }
617 
618  /* read number of blocks */
619  if( isInt(scip, blkinput, &nblocks) )
620  {
621  if( blkinput->nblocks == NOVALUE )
622  {
623  blkinput->nblocks = nblocks;
625  }
626  else
627  syntaxError(scip, blkinput, "2 integer values in nblocks section");
628  SCIPdebugMessage("Number of blocks = %d\n", blkinput->nblocks);
629  }
630  }
631 
632  return SCIP_OKAY;
633 }
634 
636 static
637 SCIP_RETCODE readBlock(
638  SCIP* scip,
639  BLKINPUT* blkinput,
640  SCIP_READERDATA* readerdata
641  )
642 {
643  int blockid;
644 
645  assert(blkinput != NULL);
646 
647  blockid = blkinput->blocknr;
648 
649  while( getNextToken(blkinput) )
650  {
651  SCIP_VAR* var;
652  int varidx;
653  int oldblock;
654 
655  /* check if we reached a new section */
656  if( isNewSection(scip, blkinput) )
657  return SCIP_OKAY;
658 
659  /* the token must be the name of an existing variable */
660  var = SCIPfindVar(scip, blkinput->token);
661  if( var == NULL )
662  {
663  syntaxError(scip, blkinput, "unknown variable in block section");
664  return SCIP_OKAY;
665  }
666 
667  varidx = SCIPvarGetProbindex(var);
668  oldblock = readerdata->varstoblock[varidx];
669 
670  /* set the block number of the variable to the number of the current block */
671  if( oldblock == NOVALUE )
672  {
673  SCIPdebugMessage("\tVar %s temporary in block %d.\n", SCIPvarGetName(var), blockid);
674  readerdata->varstoblock[varidx] = blockid;
675  ++(readerdata->nblockvars[blockid]);
676  SCIPconshdlrDecompUserSeeedSetVarToBlock(scip, blkinput->token, blockid);
677  }
678  /* variable was assigned to another (non-linking) block before, so it becomes a linking variable, now */
679  else if( (oldblock != LINKINGVALUE) )
680  {
681  assert(oldblock != blockid);
682  SCIPdebugMessage("\tVar %s is linking (old %d != %d new).\n", SCIPvarGetName(var), oldblock, blockid);
683 
684  readerdata->varstoblock[varidx] = LINKINGVALUE;
685 
686  /* decrease the number of variables in the old block and increase the number of linking variables */
687  --(readerdata->nblockvars[oldblock]);
688  ++(readerdata->nlinkingvars);
689 
690  assert(readerdata->nlinkingvarsblocks[varidx] == 0);
691  assert(readerdata->linkingvarsblocks[varidx] == NULL);
692  SCIP_CALL( SCIPallocMemoryArray(scip, &readerdata->linkingvarsblocks[varidx], 2) ); /*lint !e506 !e866*/
693  readerdata->linkingvarsblocks[varidx][0] = oldblock;
694  readerdata->linkingvarsblocks[varidx][1] = blockid;
695  readerdata->nlinkingvarsblocks[varidx] = 2;
696 
698  }
699  /* variable is a linking variable already, store the new block to which it belongs */
700  else
701  {
702  assert(oldblock == LINKINGVALUE);
703  assert(readerdata->nlinkingvarsblocks[varidx] >= 2);
704  assert(readerdata->linkingvarsblocks[varidx] != NULL);
705  SCIP_CALL( SCIPreallocMemoryArray(scip, &readerdata->linkingvarsblocks[varidx], (size_t) readerdata->nlinkingvarsblocks[varidx] + 1) ); /*lint !e866*/
706  readerdata->linkingvarsblocks[varidx][readerdata->nlinkingvarsblocks[varidx]] = blockid;
707  ++(readerdata->nlinkingvarsblocks[varidx]);
708  }
709  }
710 
711  return SCIP_OKAY;
712 }
713 
715 static
716 SCIP_RETCODE readMasterconss(
717  SCIP* scip,
718  BLKINPUT* blkinput,
719  SCIP_READERDATA* readerdata
720  )
721 {
722  assert(blkinput != NULL);
723 
724  while( getNextToken(blkinput) )
725  {
726  SCIP_CONS* cons;
727 
728  /* check if we reached a new section */
729  if( isNewSection(scip, blkinput) )
730  return SCIP_OKAY;
731 
732  /* the token must be the name of an existing constraint */
733  cons = SCIPfindCons(scip, blkinput->token);
734  if( cons == NULL )
735  {
736  syntaxError(scip, blkinput, "unknown constraint in masterconss section");
737  return SCIP_OKAY;
738  }
739  else
740  {
741  assert(SCIPhashmapGetImage(readerdata->constoblock, cons) == (void*) (size_t) NOVALUE);
742  SCIP_CALL( SCIPhashmapSetImage(readerdata->constoblock, cons, (void*) (size_t) (blkinput->nblocks +1)) );
744  }
745  }
746 
747  return SCIP_OKAY;
748 }
749 
751 static
752 SCIP_RETCODE fillDecompStruct(
753  SCIP* scip,
754  BLKINPUT* blkinput,
755  DEC_DECOMP* decomp,
756  SCIP_READERDATA* readerdata
757  )
758 {
759 
760  SCIP_HASHMAP* constoblock;
761  SCIP_CONS** allcons;
762  SCIP_VAR** allvars;
763 
764  SCIP_VAR** consvars;
765  SCIP_RETCODE retcode;
766  int i;
767  int j;
768  int nvars;
769  int blocknr;
770  int nconss;
771  int nblocks;
772 
773  assert(scip != NULL);
774  assert(blkinput != NULL);
775  assert(readerdata != NULL);
776 
777  allcons = SCIPgetConss(scip);
778  allvars = SCIPgetVars(scip);
779  nvars = SCIPgetNVars(scip);
780  nconss = SCIPgetNConss(scip);
781  nblocks = blkinput->nblocks;
782 
783  DECdecompSetPresolved(decomp, blkinput->presolved);
784  DECdecompSetNBlocks(decomp, nblocks);
785  DECdecompSetDetector(decomp, NULL);
786 
787  SCIP_CALL( DECdecompSetType(decomp, DEC_DECTYPE_ARROWHEAD) );
788 
789  /* hashmaps */
790  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(scip), nconss) );
791  SCIP_CALL( SCIPallocMemoryArray(scip, &consvars, nvars) );
792 
793  /* assign unassigned variables as master variables */
794  for( i = 0; i < nvars; ++i)
795  {
796  SCIP_VAR* var;
797  var = allvars[i];
798  if( readerdata->varstoblock[i] == NOVALUE )
799  {
800  SCIP_CALL( SCIPconshdlrDecompUserSeeedSetVarToMaster(scip, SCIPvarGetName(var) ) );
801  }
802  }
803 
804  /* assign constraints to blocks or declare them linking */
805  for( i = 0; i < nconss; ++i )
806  {
807  SCIP_CONS* cons;
808 
809  cons = allcons[i];
810 
811  if( SCIPhashmapGetImage(readerdata->constoblock, cons) == (void*) (size_t) LINKINGVALUE )
812  {
813  SCIP_CALL( SCIPhashmapInsert(constoblock, cons, (void*) (size_t) (nblocks+1)) );
814 
815  SCIPdebugMessage("cons %s is linking\n", SCIPconsGetName(cons));
816  }
817  /* check whether all variables in the constraint belong to one block */
818  else
819  {
820  int nconsvars;
821 
822  nconsvars = GCGconsGetNVars(scip, cons);
823  assert(nconsvars < nvars);
824 
825  SCIP_CALL( GCGconsGetVars(scip, cons, consvars, nvars) );
826 
827  blocknr = -1;
828 
829  /* find the first unique assignment of a contained variable to a block */
830  for( j = 0; j < nconsvars; ++j )
831  {
832  /* if a contained variable is directly transferred to the master, the constraint is a linking constraint */
833  if( readerdata->varstoblock[SCIPvarGetProbindex(consvars[j])] == NOVALUE )
834  {
835  blocknr = -1;
836  break;
837  }
838  /* assign the constraint temporarily to the block of the variable, if it is unique */
839  if( blocknr == -1 && readerdata->varstoblock[SCIPvarGetProbindex(consvars[j])] != LINKINGVALUE )
840  {
841  blocknr = readerdata->varstoblock[SCIPvarGetProbindex(consvars[j])];
842  }
843  }
844  if( blocknr != -1 )
845  {
846  /* check whether all contained variables are copied into the assigned block;
847  * if not, the constraint is treated as a linking constraint
848  */
849  for( j = 0; j < nconsvars; ++j )
850  {
851  int varidx = SCIPvarGetProbindex(consvars[j]);
852  int varblock = readerdata->varstoblock[varidx];
853  assert(varblock != NOVALUE);
854 
855  if( varblock != LINKINGVALUE && varblock != blocknr )
856  {
857  blocknr = -1;
858  break;
859  }
860  else if( varblock == LINKINGVALUE )
861  {
862  int k;
863 
864  for( k = 0; k < readerdata->nlinkingvarsblocks[varidx]; ++k )
865  {
866  if( readerdata->linkingvarsblocks[varidx][k] == blocknr )
867  break;
868  }
869  /* we did not break, so the variable is not assigned to the block */
870  if( k == readerdata->nlinkingvarsblocks[varidx] )
871  {
872  blocknr = -1;
873  break;
874  }
875  }
876  }
877  }
878 
879  if( blocknr == -1 )
880  {
881  SCIP_CALL( SCIPhashmapInsert(constoblock, cons, (void*) (size_t) (nblocks+1)) );
882  SCIP_CALL( SCIPconshdlrDecompUserSeeedSetConsToMaster(scip, SCIPconsGetName(cons) ) );
883 
884  SCIPdebugMessage("constraint <%s> is a linking constraint\n",
885  SCIPconsGetName(cons));
886  }
887  else
888  {
889  SCIP_CALL( SCIPhashmapInsert(constoblock, cons, (void*) (size_t) (blocknr+1)) );
890  SCIP_CALL( SCIPconshdlrDecompUserSeeedSetConsToBlock(scip, SCIPconsGetName(cons), blocknr ) );
891  SCIPdebugMessage("constraint <%s> is assigned to block %d\n", SCIPconsGetName(cons), blocknr);
892  }
893  }
894  }
895 
896  SCIPinfoMessage(scip, NULL, "just read blk file:\n");
898 
899 
900 
901  retcode = DECfilloutDecompFromConstoblock(scip, decomp, constoblock, nblocks, FALSE);
902  SCIPfreeMemoryArray(scip, &consvars);
903 
904  return retcode;
905 }
906 
908 static
909 SCIP_RETCODE readBLKFile(
910  SCIP* scip,
911  SCIP_READER* reader,
912  BLKINPUT* blkinput,
913  const char* filename
914  )
915 {
916  SCIP_RETCODE retcode = SCIP_ERROR;
917  DEC_DECOMP *decdecomp;
918  int i;
919  int nconss;
920  int nblocksread;
921  int nvars;
922  SCIP_READERDATA* readerdata;
923  SCIP_CONS** conss;
924  nblocksread = FALSE;
925 
926  assert(scip != NULL);
927  assert(reader != NULL);
928  assert(blkinput != NULL);
929 
930  if( SCIPgetStage(scip) < SCIP_STAGE_TRANSFORMED )
931  SCIP_CALL( SCIPtransformProb(scip) );
932 
933  readerdata = SCIPreaderGetData(reader);
934  assert(readerdata != NULL);
935 
936  readerdata->nlinkingcons = SCIPgetNConss(scip);
937  readerdata->nlinkingvars = 0;
938  nvars = SCIPgetNVars(scip);
939  conss = SCIPgetConss(scip);
940  nconss = SCIPgetNConss(scip);
941 
942  /* alloc: var -> block mapping */
943  SCIP_CALL( SCIPallocMemoryArray(scip, &readerdata->varstoblock, nvars) );
944  for( i = 0; i < nvars; i ++ )
945  {
946  readerdata->varstoblock[i] = NOVALUE;
947  }
948 
949  /* alloc: linkingvar -> blocks mapping */
950  SCIP_CALL( SCIPallocMemoryArray(scip, &readerdata->linkingvarsblocks, nvars) );
951  SCIP_CALL( SCIPallocMemoryArray(scip, &readerdata->nlinkingvarsblocks, nvars) );
952  BMSclearMemoryArray(readerdata->linkingvarsblocks, nvars);
953  BMSclearMemoryArray(readerdata->nlinkingvarsblocks, nvars);
954 
955  /* cons -> block mapping */
956  SCIP_CALL( SCIPhashmapCreate(&readerdata->constoblock, SCIPblkmem(scip), nconss) );
957  for( i = 0; i < SCIPgetNConss(scip); i ++ )
958  {
959  SCIP_CALL( SCIPhashmapInsert(readerdata->constoblock, conss[i], (void*)(size_t) NOVALUE) );
960  }
961 
962 
963  /* open file */
964  blkinput->file = SCIPfopen(filename, "r");
965  if( blkinput->file == NULL )
966  {
967  SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
968  SCIPprintSysError(filename);
969  return SCIP_NOFILE;
970  }
971 
972  /* parse the file */
973  blkinput->section = BLK_START;
974  while( blkinput->section != BLK_END && !hasError(blkinput) )
975  {
976  switch( blkinput->section )
977  {
978  case BLK_START:
979  SCIP_CALL( readStart(scip, blkinput) );
980  break;
981 
982  case BLK_PRESOLVED:
983  SCIP_CALL( readPresolved(scip, blkinput) );
984  if( blkinput->presolved && SCIPgetStage(scip) < SCIP_STAGE_PRESOLVED )
985  {
986  SCIPpresolve(scip);
987  assert(blkinput->haspresolvesection);
988 
991  // SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "decomposition belongs to the presolved problem, please presolve the problem first.\n");
992  }
993 
994 
995  if ( blkinput->presolved )
996  {
998  // seeedpool = SCIPconshdlrDecompGetSeeedpool(scip);
999  // decinput->seeed = new gcg::Seeed(scip, seeedpool->getNewIdForSeeed(), seeedpool->getNConss(), seeedpool->getNVars() );
1000 
1001  }
1002  else
1003  {
1005  }
1006 
1007 
1008 
1009  break;
1010 
1011  case BLK_NBLOCKS:
1012  if( blkinput->haspresolvesection )
1013  {
1014  SCIPconshdlrDecompCreateUserSeeed(scip, blkinput->presolved, FALSE);
1015  }
1016  SCIP_CALL( readNBlocks(scip, blkinput) );
1017  if( blkinput->haspresolvesection && !blkinput->presolved && SCIPgetStage(scip) >= SCIP_STAGE_PRESOLVED )
1018  {
1019  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "decomposition belongs to the unpresolved problem, please re-read the problem and read the decomposition without presolving.\n");
1020  goto TERMINATE;
1021  }
1022  if( !blkinput->haspresolvesection )
1023  {
1024  SCIPwarningMessage(scip, "decomposition has no presolve section at beginning. It is assumed to belong to the unpresolved problem but the behaviour is undefined. See the FAQ for further information.\n");
1025  blkinput->presolved = FALSE;
1027  SCIPconshdlrDecompCreateUserSeeed(scip, blkinput->presolved, FALSE);
1028  }
1029 
1030  break;
1031 
1032  case BLK_BLOCK:
1033  if( nblocksread == FALSE )
1034  {
1035  /* alloc n vars per block */
1036  SCIP_CALL( SCIPallocMemoryArray(scip, &readerdata->nblockvars, blkinput->nblocks) );
1037  SCIP_CALL( SCIPallocMemoryArray(scip, &readerdata->nblockcons, blkinput->nblocks) );
1038  SCIP_CALL( SCIPallocMemoryArray(scip, &readerdata->blockcons, blkinput->nblocks) );
1039  for( i = 0; i < blkinput->nblocks; ++i )
1040  {
1041  readerdata->nblockvars[i] = 0;
1042  readerdata->nblockcons[i] = 0;
1043  SCIP_CALL( SCIPallocMemoryArray(scip, &(readerdata->blockcons[i]), nconss) ); /*lint !e866*/
1044  }
1045  nblocksread = TRUE;
1046  }
1047  SCIP_CALL( readBlock(scip, blkinput, readerdata) );
1048  break;
1049 
1050  case BLK_MASTERCONSS:
1051  SCIP_CALL( readMasterconss(scip, blkinput, readerdata) );
1052  break;
1053 
1054  case BLK_END: /* this is already handled in the while() loop */
1055  default:
1056  SCIPerrorMessage("invalid BLK file section <%d>\n", blkinput->section);
1057  return SCIP_INVALIDDATA;
1058  }
1059  }
1060 
1061 
1062  SCIP_CALL( DECdecompCreate(scip, &decdecomp) );
1063 
1064  /* fill decomp */
1065  retcode = fillDecompStruct(scip, blkinput, decdecomp, readerdata);
1066 
1067  SCIP_CALL( DECdecompFree(scip, &decdecomp) );
1068 
1069  for( i = 0; i < nvars; ++i )
1070  {
1071  assert(readerdata->linkingvarsblocks[i] != NULL || readerdata->nlinkingvarsblocks[i] == 0);
1072  if( readerdata->nlinkingvarsblocks[i] > 0 )
1073  {
1074  SCIPfreeMemoryArray(scip, &readerdata->linkingvarsblocks[i]);
1075  }
1076  }
1077 
1078  TERMINATE:
1079  if( nblocksread )
1080  {
1081  for( i = blkinput->nblocks - 1; i >= 0; --i )
1082  {
1083  SCIPfreeMemoryArray(scip, &(readerdata->blockcons[i]));
1084  }
1085  SCIPfreeMemoryArray(scip, &readerdata->blockcons);
1086  SCIPfreeMemoryArray(scip, &readerdata->nblockcons);
1087  SCIPfreeMemoryArray(scip, &readerdata->nblockvars);
1088  }
1089 
1090  SCIPhashmapFree(&readerdata->constoblock);
1091 
1092  SCIPfreeMemoryArray(scip, &readerdata->nlinkingvarsblocks);
1093  SCIPfreeMemoryArray(scip, &readerdata->linkingvarsblocks);
1094  SCIPfreeMemoryArray(scip, &readerdata->varstoblock);
1095 
1096  /* close file */
1097  SCIPfclose(blkinput->file);
1098 
1099  return retcode;
1100 }
1101 
1102 
1103 /*
1104  * Callback methods of reader
1105  */
1106 
1108 static
1109 SCIP_DECL_READERFREE(readerFreeBlk)
1110 {
1111  SCIP_READERDATA* readerdata;
1112 
1113  readerdata = SCIPreaderGetData(reader);
1114  assert(readerdata != NULL);
1115 
1116  SCIPfreeMemory(scip, &readerdata);
1117 
1118  return SCIP_OKAY;
1119 }
1120 
1121 
1123 static
1124 SCIP_DECL_READERREAD(readerReadBlk)
1125 { /*lint --e{715} */
1126 
1127  if( SCIPgetStage(scip) == SCIP_STAGE_INIT || SCIPgetNVars(scip) == 0 || SCIPgetNConss(scip) == 0 )
1128  {
1129  SCIPverbMessage(scip, SCIP_VERBLEVEL_DIALOG, NULL, "Please read in a problem before reading in the corresponding structure file!\n");
1130  return SCIP_OKAY;
1131  }
1132  SCIP_CALL( SCIPreadBlk(scip, filename, result) );
1133 
1134  return SCIP_OKAY;
1135 }
1136 
1137 
1139 static
1140 SCIP_DECL_READERWRITE(readerWriteBlk)
1141 { /*lint --e{715}*/
1142  return SCIP_OKAY;
1143 }
1144 
1145 /*
1146  * reader specific interface methods
1147  */
1148 
1151  SCIP* scip
1152  )
1153 {
1154  SCIP_READERDATA* readerdata;
1155 
1156  /* create blk reader data */
1157  SCIP_CALL( SCIPallocMemory(scip, &readerdata) );
1158 
1159  /* include blk reader */
1160  SCIP_CALL( SCIPincludeReader(scip, READER_NAME, READER_DESC, READER_EXTENSION, NULL,
1161  readerFreeBlk, readerReadBlk, readerWriteBlk, readerdata) );
1162 
1163  return SCIP_OKAY;
1164 }
1165 
1166 
1167 /* reads problem from file */
1168 SCIP_RETCODE SCIPreadBlk(
1169  SCIP* scip,
1170  const char* filename,
1171  SCIP_RESULT* result
1172  )
1173 {
1174  SCIP_RETCODE retcode;
1175  SCIP_READER* reader;
1176  BLKINPUT blkinput;
1177  int i;
1178  char* ext;
1179  char copyfilename[SCIP_MAXSTRLEN];
1180 
1181  reader = SCIPfindReader(scip, READER_NAME);
1182  assert(reader != NULL);
1183 
1184 
1185  (void) SCIPsnprintf(copyfilename, SCIP_MAXSTRLEN, "%s", filename);
1186  SCIPsplitFilename(copyfilename, NULL, NULL, &ext, NULL);
1187 
1188  if ( strcmp(ext, "blk") != 0 )
1189  {
1190  return SCIP_READERROR;
1191  }
1192 
1193  /* initialize BLK input data */
1194  blkinput.file = NULL;
1195  blkinput.linebuf[0] = '\0';
1196  SCIP_CALL( SCIPallocMemoryArray(scip, &blkinput.token, BLK_MAX_LINELEN) ); /*lint !e506*/
1197  blkinput.token[0] = '\0';
1198  SCIP_CALL( SCIPallocMemoryArray(scip, &blkinput.tokenbuf, BLK_MAX_LINELEN) ); /*lint !e506*/
1199  blkinput.tokenbuf[0] = '\0';
1200  for( i = 0; i < BLK_MAX_PUSHEDTOKENS; ++i )
1201  {
1202  SCIP_CALL( SCIPallocMemoryArray(scip, &blkinput.pushedtokens[i], BLK_MAX_LINELEN) ); /*lint !e506 !e866*/
1203  }
1204 
1205  blkinput.npushedtokens = 0;
1206  blkinput.linenumber = 0;
1207  blkinput.linepos = 0;
1208  blkinput.section = BLK_START;
1209  blkinput.presolved = FALSE;
1210  blkinput.haspresolvesection = FALSE;
1211  blkinput.nblocks = -1;
1212  blkinput.blocknr = -2;
1213  blkinput.haserror = FALSE;
1214 
1215  /* read the file */
1216  retcode = readBLKFile(scip, reader, &blkinput, filename);
1217 
1218  /* free dynamically allocated memory */
1219  SCIPfreeMemoryArray(scip, &blkinput.token);
1220  SCIPfreeMemoryArray(scip, &blkinput.tokenbuf);
1221  for( i = 0; i < BLK_MAX_PUSHEDTOKENS; ++i )
1222  {
1223  SCIPfreeMemoryArray(scip, &blkinput.pushedtokens[i]);
1224  }
1225 
1226  /* evaluate the result */
1227  if( blkinput.haserror )
1228  return SCIP_READERROR;
1229  else if( retcode == SCIP_OKAY )
1230  {
1231  *result = SCIP_SUCCESS;
1232  }
1233 
1234  return SCIP_OKAY;
1235 }
#define BLK_MAX_LINELEN
Definition: reader_blk.cpp:73
#define BLK_MAX_PUSHEDTOKENS
Definition: reader_blk.cpp:74
static SCIP_Bool isInt(SCIP *scip, BLKINPUT *blkinput, int *value)
Definition: reader_blk.cpp:422
#define READER_DESC
Definition: reader_blk.cpp:67
static SCIP_Bool getNextLine(BLKINPUT *blkinput)
Definition: reader_blk.cpp:241
enum BlkSection BLKSECTION
Definition: reader_blk.cpp:81
static SCIP_RETCODE fillDecompStruct(SCIP *scip, BLKINPUT *blkinput, DEC_DECOMP *decomp, SCIP_READERDATA *readerdata)
Definition: reader_blk.cpp:752
BLKSECTION section
Definition: reader_blk.cpp:106
int ** linkingvarsblocks
Definition: reader_blk.cpp:116
static SCIP_DECL_READERWRITE(readerWriteBlk)
static void swapTokenBuffer(BLKINPUT *blkinput)
Definition: reader_blk.cpp:411
static SCIP_RETCODE readNBlocks(SCIP *scip, BLKINPUT *blkinput)
Definition: reader_blk.cpp:597
SCIP_RETCODE SCIPconshdlrDecompUserSeeedSetVarToLinking(SCIP *scip, const char *varname)
sets a variable by name to the linking variables in the current user seeed
SCIP_RETCODE SCIPconshdlrDecompUserSeeedSetConsToMaster(SCIP *scip, const char *consname)
sets a constraint by name to master in the current user seeed
static SCIP_Bool isNewSection(SCIP *scip, BLKINPUT *blkinput)
Definition: reader_blk.cpp:450
int npushedtokens
Definition: reader_blk.cpp:99
int GCGconsGetNVars(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:433
SCIP_RETCODE SCIPconshdlrDecompUserSeeedFlush(SCIP *scip)
finalizes and flushes the current user seeed, i.e. consider implicits, calc hashvalue, construct decdecomp if complete etc
static SCIP_Bool hasError(BLKINPUT *blkinput)
Definition: reader_blk.cpp:168
SCIP_RETCODE DECdecompFree(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:525
SCIP_RETCODE SCIPconshdlrDecompCreateUserSeeed(SCIP *scip, SCIP_Bool presolved, SCIP_Bool markedincomplete)
creates a user seeed for the problem
SCIP_HASHMAP * constoblock
Definition: reader_blk.cpp:118
static SCIP_RETCODE readStart(SCIP *scip, BLKINPUT *blkinput)
Definition: reader_blk.cpp:540
SCIP_CONS *** blockcons
Definition: reader_blk.cpp:119
SCIP_Bool presolved
Definition: reader_blk.cpp:102
static SCIP_DECL_READERFREE(readerFreeBlk)
static const int LINKINGVALUE
Definition: reader_blk.cpp:126
void DECdecompSetNBlocks(DEC_DECOMP *decomp, int nblocks)
Definition: decomp.c:728
static const int NOVALUE
Definition: reader_blk.cpp:125
SCIP_Bool haserror
Definition: reader_blk.cpp:107
BLK file reader for structure information.
static SCIP_RETCODE readMasterconss(SCIP *scip, BLKINPUT *blkinput, SCIP_READERDATA *readerdata)
Definition: reader_blk.cpp:716
static void syntaxError(SCIP *scip, BLKINPUT *blkinput, const char *msg)
Definition: reader_blk.cpp:140
static const char delimchars[]
Definition: reader_blk.cpp:127
static const char tokenchars[]
Definition: reader_blk.cpp:128
various SCIP helper methods
void DECdecompSetDetector(DEC_DECOMP *decomp, DEC_DETECTOR *detector)
Definition: decomp.c:1578
GCG relaxator.
SCIP_RETCODE DECdecompCreate(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:467
SCIP_RETCODE GCGconsGetVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars)
Definition: scip_misc.c:489
SCIP_RETCODE SCIPconshdlrDecompUserSeeedSetConsToBlock(SCIP *scip, const char *consname, int blockid)
sets a constraint by name to a block in the current user seeed
SCIP_RETCODE SCIPreadBlk(SCIP *scip, const char *filename, SCIP_RESULT *result)
SCIP_RETCODE SCIPconshdlrDecompCreateSeeedpool(SCIP *scip)
creates the seeedpool for the presolved problem
char * pushedtokens[BLK_MAX_PUSHEDTOKENS]
Definition: reader_blk.cpp:98
char linebuf[BLK_MAX_LINELEN]
Definition: reader_blk.cpp:95
static SCIP_RETCODE readBlock(SCIP *scip, BLKINPUT *blkinput, SCIP_READERDATA *readerdata)
Definition: reader_blk.cpp:637
BlkExpType
Definition: reader_blk.cpp:84
SCIP_RETCODE DECdecompSetType(DEC_DECOMP *decomp, DEC_DECTYPE type)
Definition: decomp.c:642
static SCIP_Bool isValueChar(char c, char nextc, SCIP_Bool firstchar, SCIP_Bool *hasdot, BLKEXPTYPE *exptype)
Definition: reader_blk.cpp:197
BlkSection
Definition: reader_blk.cpp:77
static SCIP_DECL_READERREAD(readerReadBlk)
public methods for GCG variables
int linenumber
Definition: reader_blk.cpp:100
#define READER_NAME
Definition: reader_blk.cpp:66
SCIP_Bool haspresolvesection
Definition: reader_blk.cpp:103
static SCIP_RETCODE readPresolved(SCIP *scip, BLKINPUT *blkinput)
Definition: reader_blk.cpp:561
SCIP_RETCODE DECfilloutDecompFromConstoblock(SCIP *scip, DEC_DECOMP *decomp, SCIP_HASHMAP *constoblock, int nblocks, SCIP_Bool staircase)
Definition: decomp.c:1454
static void swapPointers(char **pointer1, char **pointer2)
Definition: reader_blk.cpp:285
SCIP_RETCODE SCIPconshdlrDecompCreateSeeedpoolUnpresolved(SCIP *scip)
creates the seeedpool for the unpresolved problem
void DECdecompSetPresolved(DEC_DECOMP *decomp, SCIP_Bool presolved)
Definition: decomp.c:707
#define READER_EXTENSION
Definition: reader_blk.cpp:68
char * token
Definition: reader_blk.cpp:96
static SCIP_Bool isTokenChar(char c)
Definition: reader_blk.cpp:188
static SCIP_RETCODE readBLKFile(SCIP *scip, SCIP_READER *reader, BLKINPUT *blkinput, const char *filename)
Definition: reader_blk.cpp:909
static const char commentchars[]
Definition: reader_blk.cpp:129
char * tokenbuf
Definition: reader_blk.cpp:97
SCIP_FILE * file
Definition: reader_blk.cpp:94
static SCIP_Bool getNextToken(BLKINPUT *blkinput)
Definition: reader_blk.cpp:299
static SCIP_Bool isDelimChar(char c)
Definition: reader_blk.cpp:179
SCIP_RETCODE SCIPincludeReaderBlk(SCIP *scip)
constraint handler for structure detection
SCIP_RETCODE SCIPconshdlrDecompUserSeeedSetnumberOfBlocks(SCIP *scip, int nblocks)
set the number of blocks in the current user seeed (which is used for user input (read or modify) ) ...
struct DecDecomp DEC_DECOMP
Definition: type_decomp.h:43
public methods for working with decomposition structures
SCIP_RETCODE SCIPconshdlrDecompUserSeeedSetVarToMaster(SCIP *scip, const char *varname)
sets a variable by name to the master in the current user seeed
enum BlkExpType BLKEXPTYPE
Definition: reader_blk.cpp:88
static void pushToken(BLKINPUT *blkinput)
Definition: reader_blk.cpp:398
int * nlinkingvarsblocks
Definition: reader_blk.cpp:117
SCIP_RETCODE SCIPconshdlrDecompUserSeeedSetVarToBlock(SCIP *scip, const char *varname, int blockid)
sets a variable by name to a block in the current user seeed