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