Scippy

SCIP

Solving Constraint Integer Programs

reader_pbm.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file reader_pbm.c
17  * @brief file writer for portable bitmap file format (PBM), open with common graphic viewer programs (e.g. xview)
18  * @author Alexandra Kraft
19  *
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <stdlib.h>
25 #include <assert.h>
26 #include <string.h>
27 
28 #include "scip/reader_pbm.h"
29 #include "scip/cons_knapsack.h"
30 #include "scip/cons_linear.h"
31 #include "scip/cons_logicor.h"
32 #include "scip/cons_setppc.h"
33 #include "scip/cons_varbound.h"
34 #include "scip/pub_misc.h"
35 
36 #define READER_NAME "pbmreader"
37 #define READER_DESC "file writer for portable bitmap file format (PBM), open with common graphic viewer programs (e.g. xview)"
38 #define READER_EXTENSION "pbm"
39 
40 /*
41  * Data structures
42  */
43 #define PBM_MAX_LINELEN 71 /**< the maximum length of any line is 70 + '\\0' = 71*/
44 #define DEFAULT_PBM_BINARY TRUE /**< binary is the default format for PBM */
45 #define DEFAULT_PBM_MAXROWS 1000 /**< allowed maximum of pixel-rows int the picture */
46 #define DEFAULT_PBM_MAXCOLS 1000 /**< allowed maximum of pixel-columns in the picture */
47 
48 /** LP reading data */
49 struct SCIP_ReaderData
50 {
51  SCIP_Bool binary; /**< binary is the default format for PBM */
52  int maxrows; /**< allowed maximum of pixel-rows int the picture */
53  int maxcols; /**< allowed maximum of pixel-columns in the picture */
54 };
55 
56 /*
57  * Local methods (for writing)
58  */
59 
60 /** transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant */
61 static
63  SCIP* scip, /**< SCIP data structure */
64  SCIP_VAR** vars, /**< vars array to get active variables for */
65  SCIP_Real* scalars, /**< scalars a_1, ..., a_n in sum a_1*x_1 + ... + a_n*x_n + c */
66  int* nvars, /**< pointer to number of variables and values in vars and vals array */
67  SCIP_Real* constant, /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */
68  SCIP_Bool transformed /**< transformed constraint? */
69  )
70 {
71  int requiredsize;
72  int v;
73 
74  assert(scip != NULL);
75  assert(vars != NULL);
76  assert(scalars != NULL);
77  assert(nvars != NULL);
78  assert(constant != NULL);
79 
80  if( transformed )
81  {
82  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, nvars, *nvars, constant, &requiredsize, TRUE) );
83 
84  if( requiredsize > *nvars )
85  {
86  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, requiredsize) );
87  SCIP_CALL( SCIPreallocBufferArray(scip, &scalars, requiredsize) );
88 
89  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, nvars, requiredsize, constant, &requiredsize, TRUE) );
90  assert(requiredsize <= *nvars);
91  }
92  }
93  else
94  {
95  for( v = 0; v < *nvars; ++v )
96  {
97  SCIP_CALL( SCIPvarGetOrigvarSum(&vars[v], &scalars[v], constant) );
98  }
99  }
100 
101  return SCIP_OKAY;
102 }
103 
104 /** transforms given variables to the corresponding active variables */
105 static
107  SCIP* scip, /**< SCIP data structure */
108  SCIP_VAR** vars, /**< vars array to get active variables for */
109  int* nvars, /**< pointer to number of variables and values in vars and vals array */
110  SCIP_Bool transformed /**< transformed constraint? */
111  )
112 {
113  int requiredsize;
114  int v;
115 
116  assert(scip != NULL);
117  assert(vars != NULL);
118  assert(nvars != NULL);
119 
120  if( transformed )
121  {
122  SCIP_CALL( SCIPgetActiveVars(scip, vars, nvars, *nvars, &requiredsize) );
123 
124  if( requiredsize > *nvars )
125  {
126  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, requiredsize) );
127 
128  SCIP_CALL( SCIPgetActiveVars(scip, vars, nvars, requiredsize, &requiredsize) );
129  assert(requiredsize <= *nvars);
130  }
131  }
132  else
133  {
134  SCIP_Real scalar;
135  SCIP_Real constant;
136  for( v = 0; v < *nvars; ++v )
137  {
138  scalar = 1.0;
139  constant = 0.0;
140  SCIP_CALL( SCIPvarGetOrigvarSum(&vars[v], &scalar, &constant) );
141  }
142  }
143 
144  return SCIP_OKAY;
145 }
146 
147 /** clears the given line buffer */
148 static
150  char* linebuffer, /**< line */
151  int* linecnt /**< number of characters in line */
152  )
153 {
154  assert(linebuffer != NULL);
155  assert(linecnt != NULL);
156 
157  (*linecnt) = 0;
158  linebuffer[0] = '\0';
159 }
160 
161 
162 /** appends a bit to buffer and prints it to the give file stream if we've gather a whole byte */
163 static
165  SCIP* scip, /**< SCIP data structure */
166  FILE* file, /**< output file (or NULL for standard output) */
167  unsigned char* bitcnt, /**< counts bits until whole byte is gathered */
168  unsigned char* bitbuffer /**< bit buffer */
169  )
170 {
171  assert(scip != NULL);
172 
173  if( *bitcnt == 0 )
174  return;
175 
176  assert(bitbuffer != NULL);
177  assert(*bitcnt > 0 && *bitcnt <= 8);
178 
179  (*bitbuffer) <<= (8 - *bitcnt); /*lint !e701 !e734*/
180 
181  fputc(*bitbuffer, file);
182 
183  *bitcnt = 0;
184  *bitbuffer = 0;
185 }
186 
187 
188 /** appends a bit to buffer and prints it to the given file stream if we've gathered a whole byte */
189 static
191  SCIP* scip, /**< SCIP data structure */
192  FILE* file, /**< output file (or NULL for standard output) */
193  unsigned char bit, /**< bit to append */
194  unsigned char* bitcnt, /**< counts bits until whole byte is gathered */
195  unsigned char* bitbuffer /**< bit buffer */
196  )
197 {
198  assert(scip != NULL);
199  assert(*bitcnt < 8);
200  assert(bitbuffer != NULL);
201 
202  (*bitbuffer) = ((*bitbuffer)<<1)|(bit&1); /*lint !e734*/
203  *bitcnt += 1;
204 
205  if( *bitcnt == 8 )
206  flushBits(scip, file, bitcnt, bitbuffer);
207 }
208 
209 /** calculates the size of the quadratic matrix, which will correspond to one pixel in the picture */
210 static
212  SCIP_READERDATA* readerdata, /**< information for reader */
213  int nvars, /**< number of variables */
214  int nconss /**< number of constraints */
215  )
216 {
217  int sizev;
218  int sizeh;
219  int res;
220 
221  assert(readerdata->maxrows != 0 && readerdata->maxcols != 0);
222 
223  if( readerdata->maxrows > nconss )
224  readerdata->maxrows = nconss;
225 
226  if( readerdata->maxcols > nvars )
227  readerdata->maxcols = nvars;
228 
229  sizev = (nconss + readerdata->maxrows - 1) / readerdata->maxrows;
230  sizeh = (nvars + readerdata->maxcols - 1) / readerdata->maxcols;
231 
232  /* both defined with -1 */
233  if( readerdata->maxrows == -1 && readerdata->maxcols == -1 )
234  res = 1;
235 
236  /* only width is defined */
237  else if( readerdata->maxrows == -1 && readerdata->maxcols > 0 )
238  res = sizeh;
239 
240  /* only height is defined */
241  else if( readerdata->maxrows > 0 && readerdata->maxcols == -1 )
242  res = sizev;
243 
244  /* both are defined, use smaller scaling factor */
245  else if( sizev > sizeh )
246  res = sizev;
247  else
248  res = sizeh;
249 
250  readerdata->maxrows = (nconss + res - 1) / res;
251  readerdata->maxcols = (nvars + res - 1) / res;
252 
253  return res;
254 }
255 
256 
257 /** print row in PBM format to file stream */
258 static
259 void printRow(
260  SCIP* scip, /**< SCIP data structure */
261  SCIP_READERDATA* readerdata, /**< information for reader */
262  SCIP_VAR** vars, /**< array of constraint variables */
263  int conscnt, /**< current constraint */
264  int nvars, /**< number of constraint variables */
265  int submatrixsize, /**< size of the submatrices */
266  int* scaledimage /**< array of ints that count variables in every submatrix */
267  )
268 {
269  int v;
270  int i;
271  const int y = conscnt / submatrixsize;
272  int x;
273 
274  assert(scip != NULL);
275  assert(nvars > 0);
276  assert(readerdata != NULL);
277 
278  for( i = 0; i < nvars; ++i )
279  {
280  v = SCIPvarGetProbindex(vars[i]);
281  if( v != -1 )
282  {
283  x = v / submatrixsize;
284  ++(scaledimage[y * readerdata->maxcols + x]);
285  }
286  }
287 
288  return;
289 }
290 
291 /** prints given linear constraint information in PBM format to file stream */
292 static
294  SCIP* scip, /**< SCIP data structure */
295  SCIP_READERDATA* readerdata, /**< information for reader */
296  SCIP_VAR** vars, /**< array of variables */
297  SCIP_Real* vals, /**< array of coefficients values (or NULL if all coefficient values are 1) */
298  int nvars, /**< current constraint */
299  int conscnt, /**< counts variables in the constraint */
300  SCIP_Bool transformed, /**< transformed constraint? */
301  int submatrixsize, /**< size of the submatrices */
302  int* scaledimage /**< array of ints that count variables in every submatrix */
303  )
304 {
305  SCIP_VAR** activevars;
306  SCIP_Real* activevals;
307  SCIP_Real activeconstant = 0.0;
308  int nactivevars;
309  int v;
310 
311  assert(scip != NULL);
312  assert(vars != NULL);
313  assert(nvars > 0);
314  assert(conscnt >= 0);
315  assert(readerdata != NULL);
316 
317  /* duplicate variable and value array */
318  nactivevars = nvars;
319  SCIP_CALL( SCIPduplicateBufferArray(scip, &activevars, vars, nactivevars ) );
320  if( vals != NULL )
321  {
322  SCIP_CALL( SCIPduplicateBufferArray(scip, &activevals, vals, nactivevars ) );
323  }
324  else
325  {
326  SCIP_CALL( SCIPallocBufferArray(scip, &activevals, nactivevars) );
327 
328  for( v = 0; v < nactivevars; ++v )
329  activevals[v] = 1.0;
330  }
331 
332  /* retransform given variables to active variables */
333  SCIP_CALL( getActiveVariables(scip, activevars, activevals, &nactivevars, &activeconstant, transformed) );
334 
335  /* print constraint */
336  printRow(scip, readerdata, activevars, conscnt, nactivevars, submatrixsize, scaledimage);
337 
338  /* free buffer arrays */
339  SCIPfreeBufferArray(scip, &activevars);
340  SCIPfreeBufferArray(scip, &activevals);
341 
342  return SCIP_OKAY;
343 }
344 
345 /* draws the scaled image */
346 static
348  SCIP* scip, /**< SCIP data structure */
349  FILE* file, /**< output file, or NULL if standard output should be used */
350  SCIP_READERDATA* readerdata, /**< information for reader */
351  int* scaledimage /**< array of ints that count variables in every submatrix */
352  )
353 {
354  int y;
355  int x;
356  unsigned char bitcnt = 0;
357  unsigned char bitbuffer = '\0';
358 
359  assert(scip != NULL);
360  assert(readerdata != NULL);
361 
362 
363  for( y = 0; y < readerdata->maxrows; y++ )
364  {
365  for( x = 0; x < readerdata->maxcols; x++ )
366  {
367  unsigned char v = 0;
368  if( scaledimage[y*readerdata->maxcols+x] >= 1 )
369  {
370  v = 1;
371  }
372  appendBit(scip, file, v, &bitcnt, &bitbuffer);
373  }
374  flushBits(scip, file, &bitcnt, &bitbuffer);
375  }
376 }
377 
378 
379 /*
380  * Callback methods of reader
381  */
382 
383 /** copy method for reader plugins (called when SCIP copies plugins) */
384 static
385 SCIP_DECL_READERCOPY(readerCopyPbm)
386 { /*lint --e{715}*/
387  assert(scip != NULL);
388  assert(reader != NULL);
389  assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
390 
391  /* call inclusion method of reader */
393 
394  return SCIP_OKAY;
395 }
396 
397 /** destructor of reader to free user data (called when SCIP is exiting) */
398 static
399 SCIP_DECL_READERFREE(readerFreePbm)
400 {
401  SCIP_READERDATA* readerdata;
402 
403  assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
404 
405  readerdata = SCIPreaderGetData(reader);
406  assert(readerdata != NULL);
407 
408  SCIPfreeMemory(scip, &readerdata);
409 
410  return SCIP_OKAY;
411 }
412 
413 /** problem reading method of reader */
414 #define readerReadPbm NULL
415 
416 /** problem writing method of reader */
417 static
418 SCIP_DECL_READERWRITE(readerWritePbm)
419 { /*lint --e{715}*/
420 
421  SCIP_READERDATA* readerdata;
422 
423  assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
424 
425  readerdata = SCIPreaderGetData(reader);
426  assert(readerdata != NULL);
427 
428  SCIP_CALL( SCIPwritePbm(scip, file, name, readerdata, transformed, nvars, conss, nconss, result) );
429 
430  return SCIP_OKAY;
431 }
432 
433 /*
434  * reader specific interface methods
435  */
436 
437 /** includes the pbm file reader in SCIP */
439  SCIP* scip /**< SCIP data structure */
440  )
441 {
442  SCIP_READERDATA* readerdata;
443 
444  /* create pbm reader data */
445  SCIP_CALL( SCIPallocMemory(scip, &readerdata) );
446 
447  /* include pbm reader */
449  readerCopyPbm, readerFreePbm, readerReadPbm, readerWritePbm, readerdata) );
450 
451  /* add pbm reader parameters */
453  "reading/pbmreader/binary", "should the output format be binary(P4) (otherwise plain(P1) format)",
454  &readerdata->binary, FALSE, DEFAULT_PBM_BINARY, NULL, NULL) );
456  "reading/pbmreader/maxrows", "maximum number of rows in the scaled picture (-1 for no limit)",
457  &readerdata->maxrows, FALSE, DEFAULT_PBM_MAXROWS, -1, INT_MAX, NULL, NULL) );
459  "reading/pbmreader/maxcols", "maximum number of columns in the scaled picture (-1 for no limit)",
460  &readerdata->maxcols, FALSE, DEFAULT_PBM_MAXCOLS, -1, INT_MAX, NULL, NULL) );
461 
462  return SCIP_OKAY;
463 }
464 
465 /* writes picture of matrix structure to file */
467  SCIP* scip, /**< SCIP data structure */
468  FILE* file, /**< output file, or NULL if standard output should be used */
469  const char* name, /**< problem name */
470  SCIP_READERDATA* readerdata, /**< information for reader */
471  SCIP_Bool transformed, /**< TRUE iff problem is the transformed problem */
472  int nvars, /**< number of active variables in the problem */
473  SCIP_CONS** conss, /**< array with constraints of the problem */
474  int nconss, /**< number of constraints in the problem */
475  SCIP_RESULT* result /**< pointer to store the result of the file writing call */
476  )
477 {
478  SCIP_CONSHDLR* conshdlr;
479  SCIP_CONS* cons;
480  SCIP_VAR** consvars;
481  SCIP_Real* consvals;
482  SCIP_READERDATA readerdata_copy;
483  char linebuffer[PBM_MAX_LINELEN];
484  const char* conshdlrname;
485  int* scaledimage;
486  int submatrixsize;
487  int nconsvars;
488  int linecnt;
489  int c;
490  int v;
491 
492  assert(scip != NULL);
493  assert(readerdata != NULL);
494  assert(conss != NULL);
495 
496  readerdata_copy = *readerdata;
497  submatrixsize = getSubmatrixSize(&readerdata_copy, nvars, nconss);
498  readerdata = &readerdata_copy;
499 
500  SCIP_CALL( SCIPallocBufferArray(scip, &scaledimage, readerdata_copy.maxrows * readerdata_copy.maxcols) );
501  assert(scaledimage != NULL);
502  BMSclearMemoryArray(scaledimage, readerdata->maxrows * readerdata->maxcols);
503 
504  /* print statistics as comment to file */
505  if( readerdata->binary )
506  SCIPinfoMessage(scip, file, "P4\n");
507  else
508  SCIPinfoMessage(scip, file, "P1\n");
509 
510  SCIPinfoMessage(scip, file, "# %s\n", name);
511  SCIPinfoMessage(scip, file, "%d %d\n", readerdata->maxcols, readerdata->maxrows);
512 
513  clearLine(linebuffer, &linecnt);
514 
515  for( c = 0; c < nconss; ++c )
516  {
517  cons = conss[c];
518  assert(cons != NULL);
519 
520  /* in case the transformed is written only constraint are posted which are enabled in the current node */
521  assert(!transformed || SCIPconsIsEnabled(cons));
522 
523  conshdlr = SCIPconsGetHdlr(cons);
524  assert(conshdlr != NULL);
525 
526  conshdlrname = SCIPconshdlrGetName(conshdlr);
527  assert(transformed == SCIPconsIsTransformed(cons));
528 
529  if( strcmp(conshdlrname, "linear") == 0 )
530  {
531  consvars = SCIPgetVarsLinear(scip, cons);
532  nconsvars = SCIPgetNVarsLinear(scip, cons);
533  assert(consvars != NULL || nconsvars == 0);
534 
535  if( nconsvars > 0 )
536  {
537  SCIP_CALL( printLinearCons(scip, readerdata, consvars, SCIPgetValsLinear(scip, cons),
538  nconsvars, c, transformed, submatrixsize, scaledimage) );
539  }
540  }
541  else if( strcmp(conshdlrname, "setppc") == 0 )
542  {
543  consvars = SCIPgetVarsSetppc(scip, cons);
544  nconsvars = SCIPgetNVarsSetppc(scip, cons);
545  assert(consvars != NULL || nconsvars == 0);
546 
547  if( nconsvars > 0 )
548  {
549  SCIP_CALL( printLinearCons(scip, readerdata, consvars, NULL,
550  nconsvars, c, transformed, submatrixsize, scaledimage) );
551  }
552  }
553  else if( strcmp(conshdlrname, "logicor") == 0 )
554  {
555  consvars = SCIPgetVarsLogicor(scip, cons);
556  nconsvars = SCIPgetNVarsLogicor(scip, cons);
557  assert(consvars != NULL || nconsvars == 0);
558 
559  if( nconsvars > 0 )
560  {
561  SCIP_CALL( printLinearCons(scip, readerdata, consvars, NULL,
562  nconsvars, c, transformed, submatrixsize, scaledimage) );
563  }
564  }
565  else if( strcmp(conshdlrname, "knapsack") == 0 )
566  {
567  SCIP_Longint* weights;
568 
569  consvars = SCIPgetVarsKnapsack(scip, cons);
570  nconsvars = SCIPgetNVarsKnapsack(scip, cons);
571  assert(consvars != NULL || nconsvars == 0);
572 
573  /* copy Longint array to SCIP_Real array */
574  weights = SCIPgetWeightsKnapsack(scip, cons);
575  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nconsvars) );
576  for( v = 0; v < nconsvars; ++v )
577  consvals[v] = weights[v];
578 
579  if( nconsvars > 0 )
580  {
581  SCIP_CALL( printLinearCons(scip, readerdata, consvars, consvals, nconsvars, c, transformed,
582  submatrixsize, scaledimage) );
583  }
584 
585  SCIPfreeBufferArray(scip, &consvals);
586  }
587  else if( strcmp(conshdlrname, "varbound") == 0 )
588  {
589  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) );
590  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) );
591 
592  consvars[0] = SCIPgetVarVarbound(scip, cons);
593  consvars[1] = SCIPgetVbdvarVarbound(scip, cons);
594 
595  consvals[0] = 1.0;
596  consvals[1] = SCIPgetVbdcoefVarbound(scip, cons);
597 
598  SCIP_CALL( printLinearCons(scip, readerdata, consvars, consvals, 2, c, transformed,
599  submatrixsize, scaledimage) );
600 
601  SCIPfreeBufferArray(scip, &consvars);
602  SCIPfreeBufferArray(scip, &consvals);
603  }
604  else
605  {
606  SCIP_Bool success;
607 
608  consvars = NULL;
609  SCIP_CALL( SCIPgetConsNVars(scip, cons, &nconsvars, &success) );
610 
611  if( success )
612  {
613  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nconsvars) );
614 
615  SCIP_CALL( SCIPgetConsVars(scip, cons, consvars, nconsvars, &success) );
616  }
617 
618  if( success )
619  {
620  /* retransform given variables to active variables */
621  SCIP_CALL( getActiveVariables2(scip, consvars, &nconsvars, transformed) );
622 
623  printRow(scip, readerdata, consvars, c, nconsvars, submatrixsize, scaledimage);
624  }
625  else
626  {
627  SCIPwarningMessage(scip, "constraint handler <%s> cannot print requested format\n", conshdlrname );
628  SCIPinfoMessage(scip, file, "\\ ");
629  SCIP_CALL( SCIPprintCons(scip, cons, file) );
630  }
631 
632  SCIPfreeBufferArrayNull(scip, &consvars);
633  }
634  }
635 
636  drawScaledImage(scip, file, readerdata, scaledimage);
637 
638  SCIPfreeBufferArray(scip, &scaledimage);
639 
640  *result = SCIP_SUCCESS;
641 
642  return SCIP_OKAY;
643 }
644