# SCIP

Solving Constraint Integer Programs

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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
17  * @brief Graph file reader (actually, only a writer)
18  * @author Marc Pfetsch
19  *
20  * Write a weighted column/variable graph, i.e., the nodes correspond to the columns (variables) of
21  * the constraint matrix. Two nodes are adjacent if the corresponding columns/variables appear
22  * in a common row/constraint (with nonzero coefficient). The weight is obtained by summing for
23  * each row that produces an edge the absolute values of coefficients in the row; hence, we avoid
24  * parallel edges.
25  *
26  * This graph gives an indication of the connectivity structure of the constraint matrix.
27  *
28  * The graph is output in DIMACS graph format.
29  */
30
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
33 #include "blockmemshell/memory.h"
34 #include "scip/cons_knapsack.h"
35 #include "scip/cons_linear.h"
36 #include "scip/cons_logicor.h"
37 #include "scip/cons_setppc.h"
38 #include "scip/cons_varbound.h"
39 #include "scip/pub_cons.h"
40 #include "scip/pub_message.h"
42 #include "scip/pub_var.h"
44 #include "scip/scip_cons.h"
45 #include "scip/scip_mem.h"
46 #include "scip/scip_message.h"
48 #include "scip/scip_var.h"
49 #include <string.h>
50
52 #define READER_DESC "file writer for column connectivity graph file format"
54
55 /*
56  * Data structures
57  */
58
59
60 /* graph data structure */
61 struct sparseGraph
62 {
63  unsigned int n; /**< number of nodes */
64  unsigned int m; /**< number of edges */
65  int** A; /**< adjacency list (= adjacent nodes) for each node (-1 for end of list) */
66  SCIP_Real** W; /**< weights for each edge */
67  unsigned int* deg; /**< degree each node */
68  unsigned int* size; /**< size of A/w for each node */
69 };
70
71 typedef struct sparseGraph SparseGraph;
72
73
74 /*
75  * Local methods (for writing)
76  */
77
78 /** initialize graph */
79 static
81  SCIP* scip, /**< SCIP data structure */
82  SparseGraph* G, /**< graph to free */
83  unsigned int nNodes, /**< number of nodes */
84  unsigned int initSize /**< initial size of lists */
85  )
86 {
87  unsigned int i;
88
89  G->n = nNodes;
90  G->m = 0;
91
92  SCIP_CALL( SCIPallocBufferArray(scip, &G->deg, (int) nNodes) );
93  SCIP_CALL( SCIPallocBufferArray(scip, &G->size, (int) nNodes) );
94  SCIP_CALL( SCIPallocBufferArray(scip, &G->A, (int) nNodes) );
95  SCIP_CALL( SCIPallocBufferArray(scip, &G->W, (int) nNodes) );
96
97  for( i = 0; i < nNodes; ++i )
98  {
99  G->deg[i] = 0;
100  G->size[i] = initSize;
101
102  SCIP_CALL( SCIPallocBufferArray(scip, &(G->A[i]), (int) initSize) ); /*lint !e866 */
103  SCIP_CALL( SCIPallocBufferArray(scip, &(G->W[i]), (int) initSize) ); /*lint !e866 */
104
105  G->A[i][0] = -1;
106  }
107
108  return SCIP_OKAY;
109 }
110
111
112 /** frees graph */
113 static
115  SCIP* scip, /**< SCIP data structure */
116  SparseGraph* G /**< graph to free */
117  )
118 {
119  unsigned int i;
120
121  for( i = 0; i < G->n; ++i )
122  {
123  SCIPfreeBufferArray(scip, &G->A[i]);
124  SCIPfreeBufferArray(scip, &G->W[i]);
125  }
126
127  SCIPfreeBufferArray(scip, &G->W);
128  SCIPfreeBufferArray(scip, &G->A);
129  SCIPfreeBufferArray(scip, &G->size);
130  SCIPfreeBufferArray(scip, &G->deg);
131 }
132
133
134 /** check whether there is enough capacity for one additional edge in the given adjacency list */
135 static
137  SCIP* scip, /**< SCIP data structure */
138  SparseGraph* G, /**< graph */
139  unsigned int node /**< list for node */
140  )
141 {
142  if( G->deg[node] + 2 > G->size[node] )
143  {
144  unsigned int newSize;
145  newSize = G->size[node] * 2;
146  SCIP_CALL( SCIPreallocBufferArray(scip, &(G->A[node]), (int) newSize) ); /*lint !e866 */
147  SCIP_CALL( SCIPreallocBufferArray(scip, &(G->W[node]), (int) newSize) ); /*lint !e866 */
148  G->size[node] = newSize;
149  }
150
151  return SCIP_OKAY;
152 }
153
154
155 /** transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant */
156 static
158  SCIP* scip, /**< SCIP data structure */
159  SCIP_VAR** vars, /**< vars array to get active variables for */
160  SCIP_Real* scalars, /**< scalars a_1, ..., a_n inrc/scip/reader_graph.c linear sum a_1*x_1 + ... + a_n*x_n + c */
161  int* nvars, /**< pointer to number of variables and values in vars and vals array */
162  SCIP_Real* constant, /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */
163  SCIP_Bool transformed /**< transformed constraint? */
164  )
165 {
166  int requiredsize;
167  int v;
168
169  assert( scip != NULL );
170  assert( vars != NULL );
171  assert( scalars != NULL );
172  assert( nvars != NULL );
173  assert( constant != NULL );
174
175  if( transformed )
176  {
177  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, nvars, *nvars, constant, &requiredsize, TRUE) );
178
179  if( requiredsize > *nvars )
180  {
181  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, requiredsize) );
182  SCIP_CALL( SCIPreallocBufferArray(scip, &scalars, requiredsize) );
183
184  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, nvars, requiredsize, constant, &requiredsize, TRUE) );
185  assert( requiredsize <= *nvars );
186  }
187  }
188  else
189  {
190  for( v = 0; v < *nvars; ++v )
191  SCIP_CALL( SCIPvarGetOrigvarSum(&vars[v], &scalars[v], constant) );
192  }
193  return SCIP_OKAY;
194 }
195
196
197 /* Generate edges from given row
198  *
199  * We avoid parallel edges. Each row generates a clique in the graph.
200  */
201 static
203  SCIP* scip, /**< SCIP data structure */
204  SCIP_VAR** vars, /**< array of constraint variables */
205  SCIP_Real* vals, /**< array of constraint values */
206  int nvars, /**< number of constraint variables */
207  SparseGraph* G /**< graph */
208  )
209 {
210  int i, j;
211  SCIP_Real w;
212
213  assert( scip != NULL );
214  assert( nvars > 0 );
215
216  /* compute weight */
217  w = 0;
218  for( i = 0; i < nvars; ++i )
219  w += ABS(vals[i]);
220
221  /* generate edges */
222  for( i = 0; i < nvars; ++i )
223  {
224  int s;
225  s = SCIPvarGetProbindex(vars[i]);
226  assert( s >= 0 );
227
228  for( j = i+1; j < nvars; ++j )
229  {
230  unsigned int k;
231  int t;
232  int a;
233  t = SCIPvarGetProbindex(vars[j]);
234  assert( t >= 0 );
235
236  /* search whether edge is already present */
237  k = 0;
238  a = G->A[s][k];
239  while( a >= 0 )
240  {
241  /* if we found edge, add weight */
242  if( a == t )
243  {
244  G->W[s][k] += w;
245  break;
246  }
247  a = G->A[s][++k];
248  assert( k <= G->size[s] );
249  }
250
251  /* add new edge */
252  if( a < 0 )
253  {
254  /* forward edge */
255  SCIP_CALL( ensureEdgeCapacity(scip, G, (unsigned int) s) );
256  k = G->deg[s];
257  assert( G->A[s][k] == -1 );
258
259  G->A[s][k] = t;
260  G->W[s][k] = w;
261
262  G->A[s][k+1] = -1; /*lint !e679*/
263  ++G->deg[s];
264
265  /* backward edge */
266  SCIP_CALL( ensureEdgeCapacity(scip, G, (unsigned int) t) );
267  k = G->deg[t];
268  assert( G->A[t][k] == -1 );
269
270  G->A[t][k] = s;
271  G->W[t][k] = w;
272
273  G->A[t][k+1] = -1; /*lint !e679*/
274  ++G->deg[t];
275
276  /* increase number of edges */
277  ++G->m;
278  }
279  }
280  }
281
282  return SCIP_OKAY;
283 }
284
285
286 /** handle given linear constraint information */
287 static
289  SCIP* scip, /**< SCIP data structure */
290  SCIP_VAR** vars, /**< array of variables */
291  SCIP_Real* vals, /**< array of coefficients values (or NULL if all coefficient values are 1) */
292  int nvars, /**< number of variables */
293  SCIP_Bool transformed, /**< transformed constraint? */
294  SparseGraph* G /**< graph */
295  )
296 {
297  int v;
298  SCIP_VAR** activevars;
299  SCIP_Real* activevals;
300  int nactivevars;
301  SCIP_Real activeconstant = 0.0;
302
303  assert( scip != NULL );
304  assert( nvars > 0 );
305
306  /* duplicate variable and value array */
307  nactivevars = nvars;
308  SCIP_CALL( SCIPduplicateBufferArray(scip, &activevars, vars, nactivevars ) );
309  if( vals != NULL )
310  SCIP_CALL( SCIPduplicateBufferArray(scip, &activevals, vals, nactivevars ) );
311  else
312  {
313  SCIP_CALL( SCIPallocBufferArray(scip, &activevals, nactivevars) );
314
315  for( v = 0; v < nactivevars; ++v )
316  activevals[v] = 1.0;
317  }
318
319  /* retransform given variables to active variables */
320  SCIP_CALL( getActiveVariables(scip, activevars, activevals, &nactivevars, &activeconstant, transformed) );
321
322  /* print constraint */
323  SCIP_CALL( createEdgesFromRow(scip, activevars, activevals, nactivevars, G) );
324
325  /* free buffer arrays */
326  SCIPfreeBufferArray(scip, &activevars);
327  SCIPfreeBufferArray(scip, &activevals);
328
329  return SCIP_OKAY;
330 }
331
332
333 /*
334  * Callback methods of reader
335  */
336
337 /** copy method for reader plugins (called when SCIP copies plugins) */
338 static
340 { /*lint --e{715}*/
341  assert(scip != NULL);
344
345  /* call inclusion method of reader */
347
348  return SCIP_OKAY;
349 }
350
351
352 /** problem writing method of reader */
353 static
355 { /*lint --e{715}*/
356
357  SCIP_CALL( SCIPwriteCcg(scip, file, name, transformed, vars, nvars, conss, nconss, result) );
358
359  return SCIP_OKAY;
360 }
361
362 /*
363  * reader specific interface methods
364  */
365
366 /** includes the ccg file reader in SCIP */
368  SCIP* scip /**< SCIP data structure */
369  )
370 {
372
375
377
378  /* set non-fundamental callbacks via setter functions */
381
382  return SCIP_OKAY;
383 }
384
385
386 /** writes problem to file */
388  SCIP* scip, /**< SCIP data structure */
389  FILE* file, /**< output file, or NULL if standard output should be used */
390  const char* name, /**< problem name */
391  SCIP_Bool transformed, /**< TRUE iff problem is the transformed problem */
392  SCIP_VAR** vars, /**< array with active variables ordered binary, integer, implicit, continuous */
393  int nvars, /**< number of active variables in the problem */
394  SCIP_CONS** conss, /**< array with constraints of the problem */
395  int nconss, /**< number of constraints in the problem */
396  SCIP_RESULT* result /**< pointer to store the result of the file writing call */
397  )
398 { /*lint --e{715}*/
399  int c;
400  int v;
401  int i;
402
403  SCIP_CONSHDLR* conshdlr;
404  const char* conshdlrname;
405  SCIP_CONS* cons;
406
407  SCIP_VAR** consvars;
408  SCIP_Real* consvals;
409  int nconsvars;
410
411  SparseGraph G;
412
413  assert( scip != NULL );
414  assert( nvars >= 0 );
415
416  /* initialize graph */
417  SCIP_CALL( initGraph(scip, &G, (unsigned int) nvars, 10) );
418
419  /* check all constraints */
420  for( c = 0; c < nconss; ++c)
421  {
422  cons = conss[c];
423  assert( cons != NULL);
424
425  /* in case the transformed is written only constraint are posted which are enabled in the current node */
426  assert(!transformed || SCIPconsIsEnabled(cons));
427
428  conshdlr = SCIPconsGetHdlr(cons);
429  assert( conshdlr != NULL );
430
431  conshdlrname = SCIPconshdlrGetName(conshdlr);
432  assert( transformed == SCIPconsIsTransformed(cons) );
433
434  if( strcmp(conshdlrname, "linear") == 0 )
435  {
436  consvars = SCIPgetVarsLinear(scip, cons);
437  nconsvars = SCIPgetNVarsLinear(scip, cons);
438  assert( consvars != NULL || nconsvars == 0 );
439
440  if( nconsvars > 0 )
441  {
442  SCIP_CALL( handleLinearCons(scip, SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons),
443  SCIPgetNVarsLinear(scip, cons), transformed, &G) );
444  }
445  }
446  else if( strcmp(conshdlrname, "setppc") == 0 )
447  {
450  assert( consvars != NULL || nconsvars == 0 );
451
452  if( nconsvars > 0 )
453  {
454  SCIP_CALL( handleLinearCons(scip, consvars, NULL, nconsvars, transformed, &G) );
455  }
456  }
457  else if( strcmp(conshdlrname, "logicor") == 0 )
458  {
459  consvars = SCIPgetVarsLogicor(scip, cons);
460  nconsvars = SCIPgetNVarsLogicor(scip, cons);
461  assert( consvars != NULL || nconsvars == 0 );
462
463  if( nconsvars > 0 )
464  {
465  SCIP_CALL( handleLinearCons(scip, SCIPgetVarsLogicor(scip, cons), NULL, SCIPgetNVarsLogicor(scip, cons), transformed, &G) );
466  }
467  }
468  else if( strcmp(conshdlrname, "knapsack") == 0 )
469  {
470  SCIP_Longint* w;
471
472  consvars = SCIPgetVarsKnapsack(scip, cons);
473  nconsvars = SCIPgetNVarsKnapsack(scip, cons);
474  assert( consvars != NULL || nconsvars == 0 );
475
476  /* copy Longint array to SCIP_Real array */
477  w = SCIPgetWeightsKnapsack(scip, cons);
478  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nconsvars) );
479  for( v = 0; v < nconsvars; ++v )
480  consvals[v] = (SCIP_Real)w[v];
481
482  if( nconsvars > 0 )
483  {
484  SCIP_CALL( handleLinearCons(scip, consvars, consvals, nconsvars, transformed, &G) );
485  }
486  SCIPfreeBufferArray(scip, &consvals);
487  }
488  else if( strcmp(conshdlrname, "varbound") == 0 )
489  {
490  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) );
491  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) );
492
493  consvars[0] = SCIPgetVarVarbound(scip, cons);
494  consvars[1] = SCIPgetVbdvarVarbound(scip, cons);
495
496  consvals[0] = 1.0;
497  consvals[1] = SCIPgetVbdcoefVarbound(scip, cons);
498
499  SCIP_CALL( handleLinearCons(scip, consvars, consvals, 2, transformed, &G) );
500
501  SCIPfreeBufferArray(scip, &consvars);
502  SCIPfreeBufferArray(scip, &consvals);
503  }
504  else
505  {
506  SCIPwarningMessage(scip, "constraint handler <%s> cannot print requested format\n", conshdlrname );
507  SCIPinfoMessage(scip, file, "\\ ");
508  SCIP_CALL( SCIPprintCons(scip, cons, file) );
509  SCIPinfoMessage(scip, file, ";\n");
510  }
511  }
512
513  /* output graph */
514  SCIPinfoMessage(scip, file, "c graph generated from %s\n", name);
515  SCIPinfoMessage(scip, file, "p edge %d %d\n", nvars, G.m);
516
517  for( i = 0; i < nvars; ++i )
518  {
519  unsigned int k;
520  int a;
521
522  k = 0;
523  a = G.A[i][k];
524  while( a >= 0 )
525  {
526  /* only output edges from lower to higher number */
527  if( i < a )
528  {
529  /* note: node numbers start with 1 in the DIMACS format */
530  SCIPinfoMessage(scip, file, "e %d %d %f\n", i+1, a+1, G.W[i][k]);
531  }
532
533  a = G.A[i][++k];
534  assert( k <= G.size[i] );
535  }
536  assert( k == G.deg[i] );
537  }
538
539  freeGraph(scip, &G);
540
541  *result = SCIP_SUCCESS;
542
543  return SCIP_OKAY;
544 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
static SCIP_RETCODE getActiveVariables(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
#define NULL
Definition: def.h:246
SCIP_Bool SCIPconsIsEnabled(SCIP_CONS *cons)
Definition: cons.c:8173
Constraint handler for variable bound constraints .
public methods for memory management
Definition: cons_setppc.c:9252
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17037
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8385
public methods for problem variables
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE ensureEdgeCapacity(SCIP *scip, SparseGraph *G, unsigned int node)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:138
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
Constraint handler for the set partitioning / packing / covering constraints .
public methods for SCIP variables
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:203
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:279
SCIP_VAR * w
Definition: circlepacking.c:58
public methods for managing constraints
Constraint handler for knapsack constraints of the form , x binary and .
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4191
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
#define SCIP_CALL(x)
Definition: def.h:358
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
Definition: scip_var.c:1740
public methods for constraint handler plugins and constraints
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
#define SCIP_Bool
Definition: def.h:69
Column connectivity graph file reader (actually, only a writer)
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2550
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8096
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPwriteCcg(SCIP *scip, FILE *file, const char *name, SCIP_Bool transformed, SCIP_VAR **vars, int nvars, SCIP_CONS **conss, int nconss, SCIP_RESULT *result)
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12260
static SCIP_RETCODE createEdgesFromRow(SCIP *scip, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SparseGraph *G)
static void freeGraph(SCIP *scip, SparseGraph *G)
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9273
struct sparseGraph SparseGraph
static const SCIP_Real scalars[]
Definition: lp.c:5650
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
public methods for message output
SCIP_VAR * a
Definition: circlepacking.c:57
static SCIP_RETCODE initGraph(SCIP *scip, SparseGraph *G, unsigned int nNodes, unsigned int initSize)
#define SCIP_Real
Definition: def.h:157
public methods for input file readers
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
public methods for message handling
static SCIP_RETCODE handleLinearCons(SCIP *scip, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Bool transformed, SparseGraph *G)