Scippy

SCIP

Solving Constraint Integer Programs

matrix.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-2019 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 matrix.c
17  * @brief methods for MIP matrix data structure
18  * @author Dieter Weninger
19  * @author Gerald Gamrath
20  *
21  * The MIP matrix is organized as sparse data structure in row and
22  * and column major format.
23  */
24 
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 
27 #include "blockmemshell/memory.h"
28 #include "scip/cons_knapsack.h"
29 #include "scip/cons_linear.h"
30 #include "scip/cons_logicor.h"
31 #include "scip/cons_setppc.h"
32 #include "scip/cons_varbound.h"
33 #include "scip/pub_matrix.h"
34 #include "scip/pub_cons.h"
35 #include "scip/pub_message.h"
36 #include "scip/pub_misc_sort.h"
37 #include "scip/pub_var.h"
38 #include "scip/scip_cons.h"
39 #include "scip/scip_general.h"
40 #include "scip/scip_mem.h"
41 #include "scip/scip_message.h"
42 #include "scip/scip_numerics.h"
43 #include "scip/scip_prob.h"
44 #include "scip/scip_var.h"
45 #include "scip/struct_matrix.h"
46 #include <string.h>
47 
48 /*
49  * private functions
50  */
51 
52 /** transforms given variables, scalars and constant to the corresponding active variables, scalars and constant */
53 static
55  SCIP* scip, /**< SCIP instance */
56  SCIP_VAR*** vars, /**< vars array to get active variables for */
57  SCIP_Real** scalars, /**< scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */
58  int* nvars, /**< pointer to number of variables and values in vars and vals array */
59  SCIP_Real* constant /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */
60  )
61 {
62  int requiredsize;
63 
64  assert(scip != NULL);
65  assert(vars != NULL);
66  assert(scalars != NULL);
67  assert(*vars != NULL);
68  assert(*scalars != NULL);
69  assert(nvars != NULL);
70  assert(constant != NULL);
71 
72  SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, *nvars, constant, &requiredsize, TRUE) );
73 
74  if( requiredsize > *nvars )
75  {
76  SCIP_CALL( SCIPreallocBufferArray(scip, vars, requiredsize) );
77  SCIP_CALL( SCIPreallocBufferArray(scip, scalars, requiredsize) );
78 
79  /* call function a second time with enough memory */
80  SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, requiredsize, constant, &requiredsize, TRUE) );
81  assert(requiredsize <= *nvars);
82  }
83 
84  return SCIP_OKAY;
85 }
86 
87 /** add one row to the constraint matrix */
88 static
90  SCIP* scip, /**< SCIP data structure */
91  SCIP_MATRIX* matrix, /**< constraint matrix */
92  SCIP_VAR** vars, /**< variables of this row */
93  SCIP_Real* vals, /**< coefficients of this row */
94  int nvars, /**< number of variables of this row */
95  SCIP_Real lhs, /**< left hand side */
96  SCIP_Real rhs, /**< right hand side */
97  int maxnnonzsmem, /**< maximal number of fillable elements */
98  SCIP_Bool* rowadded /**< flag indicating if constraint was added to matrix */
99  )
100 {
101  int j;
102  int probindex;
103  int rowidx;
104  SCIP_Real factor;
105  SCIP_Bool rangedorequality;
106 
107  assert(vars != NULL);
108  assert(vals != NULL);
109 
110  rowidx = matrix->nrows;
111  rangedorequality = FALSE;
112 
113  if( SCIPisInfinity(scip, -lhs) )
114  {
115  factor = -1.0;
116  matrix->lhs[rowidx] = -rhs;
117  matrix->rhs[rowidx] = SCIPinfinity(scip);
118  matrix->isrhsinfinite[rowidx] = TRUE;
119  }
120  else
121  {
122  factor = 1.0;
123  matrix->lhs[rowidx] = lhs;
124  matrix->rhs[rowidx] = rhs;
125  matrix->isrhsinfinite[rowidx] = SCIPisInfinity(scip, matrix->rhs[rowidx]);
126 
127  if( !SCIPisInfinity(scip, rhs) )
128  rangedorequality = TRUE;
129  }
130 
131  if(SCIPisInfinity(scip, -matrix->lhs[rowidx]))
132  {
133  /* ignore redundant constraint */
134  *rowadded = FALSE;
135  return SCIP_OKAY;
136  }
137 
138  matrix->rowmatbeg[rowidx] = matrix->nnonzs;
139 
140  /* = or ranged */
141  if( rangedorequality )
142  {
143  assert(factor > 0);
144 
145  for( j = 0; j < nvars; j++ )
146  {
147  assert(maxnnonzsmem > matrix->nnonzs);
148 
149  /* ignore variables with very small coefficients */
150  if( SCIPisZero(scip, vals[j]) )
151  continue;
152 
153  matrix->rowmatval[matrix->nnonzs] = factor * vals[j];
154  probindex = SCIPvarGetProbindex(vars[j]);
155  assert(matrix->vars[probindex] == vars[j]);
156 
157  matrix->nuplocks[probindex]++;
158  matrix->ndownlocks[probindex]++;
159 
160  assert(0 <= probindex && probindex < matrix->ncols);
161  matrix->rowmatind[matrix->nnonzs] = probindex;
162 
163  (matrix->nnonzs)++;
164  }
165  }
166  /* >= or <= */
167  else
168  {
169  for( j = 0; j < nvars; j++ )
170  {
171  assert(maxnnonzsmem > matrix->nnonzs);
172 
173  /* ignore variables with very small coefficients */
174  if( SCIPisZero(scip, vals[j]) )
175  continue;
176 
177  /* due to the factor, <= constraints will be transfered to >= */
178  matrix->rowmatval[matrix->nnonzs] = factor * vals[j];
179  probindex = SCIPvarGetProbindex(vars[j]);
180  assert(matrix->vars[probindex] == vars[j]);
181 
182  if( matrix->rowmatval[matrix->nnonzs] > 0 )
183  matrix->ndownlocks[probindex]++;
184  else
185  {
186  assert(matrix->rowmatval[matrix->nnonzs] < 0);
187  matrix->nuplocks[probindex]++;
188  }
189 
190  assert(0 <= probindex && probindex < matrix->ncols);
191  matrix->rowmatind[matrix->nnonzs] = probindex;
192 
193  (matrix->nnonzs)++;
194  }
195  }
196 
197  matrix->rowmatcnt[rowidx] = matrix->nnonzs - matrix->rowmatbeg[rowidx];
198 
199  ++(matrix->nrows);
200  *rowadded = TRUE;
201 
202  return SCIP_OKAY;
203 }
204 
205 /** add one constraint to matrix */
206 static
208  SCIP* scip, /**< current scip instance */
209  SCIP_MATRIX* matrix, /**< constraint matrix */
210  SCIP_VAR** vars, /**< variables of this constraint */
211  SCIP_Real* vals, /**< variable coefficients of this constraint */
212  int nvars, /**< number of variables */
213  SCIP_Real lhs, /**< left hand side */
214  SCIP_Real rhs, /**< right hand side */
215  int maxnnonzsmem, /**< maximal number of fillable elements */
216  SCIP_Bool* rowadded /**< flag indicating of row was added to matrix */
217  )
218 {
219  SCIP_VAR** activevars;
220  SCIP_Real* activevals;
221  SCIP_Real activeconstant;
222  int nactivevars;
223  int v;
224 
225  assert(scip != NULL);
226  assert(matrix != NULL);
227  assert(vars != NULL || nvars == 0);
228  assert(SCIPisLE(scip, lhs, rhs));
229  assert(rowadded != NULL);
230 
231  *rowadded = FALSE;
232 
233  /* constraint is redundant */
234  if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) )
235  return SCIP_OKAY;
236 
237  /* we do not add empty constraints to the matrix */
238  if( nvars == 0 )
239  return SCIP_OKAY;
240 
241  activevars = NULL;
242  activevals = NULL;
243  nactivevars = nvars;
244  activeconstant = 0.0;
245 
246  /* duplicate variable and value array */
247  SCIP_CALL( SCIPduplicateBufferArray(scip, &activevars, vars, nactivevars ) );
248  if( vals != NULL )
249  {
250  SCIP_CALL( SCIPduplicateBufferArray(scip, &activevals, vals, nactivevars ) );
251  }
252  else
253  {
254  SCIP_CALL( SCIPallocBufferArray(scip, &activevals, nactivevars) );
255 
256  for( v = 0; v < nactivevars; v++ )
257  activevals[v] = 1.0;
258  }
259 
260  /* retransform given variables to active variables */
261  SCIP_CALL( getActiveVariables(scip, &activevars, &activevals, &nactivevars, &activeconstant) );
262 
263  /* adapt left and right hand side */
264  if( !SCIPisInfinity(scip, -lhs) )
265  lhs -= activeconstant;
266  if( !SCIPisInfinity(scip, rhs) )
267  rhs -= activeconstant;
268 
269  /* add single row to matrix */
270  if( nactivevars > 0 )
271  {
272  SCIP_CALL( addRow(scip, matrix, activevars, activevals, nactivevars, lhs, rhs, maxnnonzsmem, rowadded) );
273  }
274 
275  /* free buffer arrays */
276  SCIPfreeBufferArray(scip, &activevals);
277  SCIPfreeBufferArray(scip, &activevars);
278 
279  return SCIP_OKAY;
280 }
281 
282 /** transform row major format into column major format */
283 static
285  SCIP* scip, /**< current scip instance */
286  SCIP_MATRIX* matrix /**< constraint matrix */
287  )
288 {
289  int colidx;
290  int i;
291  int* rowpnt;
292  int* rowend;
293  SCIP_Real* valpnt;
294  int* fillidx;
295 
296  assert(scip != NULL);
297  assert(matrix != NULL);
298  assert(matrix->colmatval != NULL);
299  assert(matrix->colmatind != NULL);
300  assert(matrix->colmatbeg != NULL);
301  assert(matrix->colmatcnt != NULL);
302  assert(matrix->rowmatval != NULL);
303  assert(matrix->rowmatind != NULL);
304  assert(matrix->rowmatbeg != NULL);
305  assert(matrix->rowmatcnt != NULL);
306 
307  SCIP_CALL( SCIPallocBufferArray(scip, &fillidx, matrix->ncols) );
308  BMSclearMemoryArray(fillidx, matrix->ncols);
309  BMSclearMemoryArray(matrix->colmatcnt, matrix->ncols);
310 
311  for( i = 0; i < matrix->nrows; i++ )
312  {
313  rowpnt = matrix->rowmatind + matrix->rowmatbeg[i];
314  rowend = rowpnt + matrix->rowmatcnt[i];
315  for( ; rowpnt < rowend; rowpnt++ )
316  {
317  colidx = *rowpnt;
318  (matrix->colmatcnt[colidx])++;
319  }
320  }
321 
322  matrix->colmatbeg[0] = 0;
323  for( i = 0; i < matrix->ncols-1; i++ )
324  {
325  matrix->colmatbeg[i+1] = matrix->colmatbeg[i] + matrix->colmatcnt[i];
326  }
327 
328  for( i = 0; i < matrix->nrows; i++ )
329  {
330  rowpnt = matrix->rowmatind + matrix->rowmatbeg[i];
331  rowend = rowpnt + matrix->rowmatcnt[i];
332  valpnt = matrix->rowmatval + matrix->rowmatbeg[i];
333 
334  for( ; rowpnt < rowend; rowpnt++, valpnt++ )
335  {
336  assert(*rowpnt < matrix->ncols);
337  colidx = *rowpnt;
338  matrix->colmatval[matrix->colmatbeg[colidx] + fillidx[colidx]] = *valpnt;
339  matrix->colmatind[matrix->colmatbeg[colidx] + fillidx[colidx]] = i;
340  fillidx[colidx]++;
341  }
342  }
343 
344  SCIPfreeBufferArray(scip, &fillidx);
345 
346  return SCIP_OKAY;
347 }
348 
349 /** calculate min/max activity per row */
350 static
352  SCIP* scip, /**< current scip instance */
353  SCIP_MATRIX* matrix /**< constraint matrix */
354  )
355 {
356  SCIP_Real val;
357  int* rowpnt;
358  int* rowend;
359  SCIP_Real* valpnt;
360  int col;
361  int row;
362 
363  assert(scip != NULL);
364  assert(matrix != NULL);
365 
366  for( row = 0; row < matrix->nrows; row++ )
367  {
368  matrix->minactivity[row] = 0;
369  matrix->maxactivity[row] = 0;
370  matrix->minactivityneginf[row] = 0;
371  matrix->minactivityposinf[row] = 0;
372  matrix->maxactivityneginf[row] = 0;
373  matrix->maxactivityposinf[row] = 0;
374 
375  rowpnt = matrix->rowmatind + matrix->rowmatbeg[row];
376  rowend = rowpnt + matrix->rowmatcnt[row];
377  valpnt = matrix->rowmatval + matrix->rowmatbeg[row];
378 
379  for( ; rowpnt < rowend; rowpnt++, valpnt++ )
380  {
381  /* get column index */
382  col = *rowpnt;
383 
384  /* get variable coefficient */
385  val = *valpnt;
386  assert(!SCIPisZero(scip, val));
387 
388  assert(matrix->ncols > col);
389 
390  assert(!SCIPisInfinity(scip, matrix->lb[col]));
391  assert(!SCIPisInfinity(scip, -matrix->ub[col]));
392 
393  /* positive coefficient */
394  if( val > 0.0 )
395  {
396  if( SCIPisInfinity(scip, matrix->ub[col]) )
397  matrix->maxactivityposinf[row]++;
398  else
399  matrix->maxactivity[row] += val * matrix->ub[col];
400 
401  if( SCIPisInfinity(scip, -matrix->lb[col]) )
402  matrix->minactivityneginf[row]++;
403  else
404  matrix->minactivity[row] += val * matrix->lb[col];
405  }
406  /* negative coefficient */
407  else
408  {
409  if( SCIPisInfinity(scip, -matrix->lb[col]) )
410  matrix->maxactivityneginf[row]++;
411  else
412  matrix->maxactivity[row] += val * matrix->lb[col];
413 
414  if( SCIPisInfinity(scip, matrix->ub[col]) )
415  matrix->minactivityposinf[row]++;
416  else
417  matrix->minactivity[row] += val * matrix->ub[col];
418  }
419  }
420 
421  /* consider infinite bound contributions for the activities */
422  if( matrix->maxactivityneginf[row] + matrix->maxactivityposinf[row] > 0 )
423  matrix->maxactivity[row] = SCIPinfinity(scip);
424 
425  if( matrix->minactivityneginf[row] + matrix->minactivityposinf[row] > 0 )
426  matrix->minactivity[row] = -SCIPinfinity(scip);
427  }
428 
429  return SCIP_OKAY;
430 }
431 
432 /*
433  * public functions
434  */
435 
436 /** initialize matrix */
438  SCIP* scip, /**< current scip instance */
439  SCIP_MATRIX** matrixptr, /**< pointer to constraint matrix object to be initialized */
440  SCIP_Bool* initialized, /**< was the initialization successful? */
441  SCIP_Bool* complete /**< are all constraint represented within the matrix? */
442  )
443 {
444  SCIP_MATRIX* matrix;
445  SCIP_CONSHDLR** conshdlrs;
446  const char* conshdlrname;
447  SCIP_Bool stopped;
448  SCIP_VAR** vars;
449  SCIP_VAR* var;
450  SCIP_CONS* cons;
451  int nconshdlrs;
452  int nconss;
453  int nconssall;
454  int nnonzstmp;
455  int nvars;
456  int c;
457  int i;
458  int v;
459  int cnt;
460 
461  nnonzstmp = 0;
462 
463  assert(scip != NULL);
464  assert(matrixptr != NULL);
465  assert(initialized != NULL);
466  assert(complete != NULL);
467 
468  *initialized = FALSE;
469  *complete = FALSE;
470 
471  /* return if no variables or constraints are present */
472  if( SCIPgetNVars(scip) == 0 || SCIPgetNConss(scip) == 0 )
473  return SCIP_OKAY;
474 
475  /* loop over all constraint handlers and collect the number of checked constraints */
476  nconshdlrs = SCIPgetNConshdlrs(scip);
477  conshdlrs = SCIPgetConshdlrs(scip);
478  nconss = 0;
479  nconssall = 0;
480 
481  for( i = 0; i < nconshdlrs; ++i )
482  {
483  int nconshdlrconss;
484 
485  nconshdlrconss = SCIPconshdlrGetNCheckConss(conshdlrs[i]);
486 
487  if( nconshdlrconss > 0 )
488  {
489  conshdlrname = SCIPconshdlrGetName(conshdlrs[i]);
490 
491  if( (strcmp(conshdlrname, "linear") == 0) || (strcmp(conshdlrname, "setppc") == 0)
492  || (strcmp(conshdlrname, "logicor") == 0) || (strcmp(conshdlrname, "knapsack") == 0)
493  || (strcmp(conshdlrname, "varbound") == 0) )
494  {
495  /* increment number of supported constraints */
496  nconss += nconshdlrconss;
497  }
498 /* disabled because some of the presolvers can currently only handle 1-1 row-cons relationships */
499 #ifdef SCIP_DISABLED_CODE
500  else if( strcmp(conshdlrname, "linking") == 0 )
501  {
502  /* the linear representation of linking constraints involves two linear constraints */
503  nconss += 2* nconshdlrconss;
504  }
505 #endif
506  /* increment number of supported and unsupported constraints */
507  nconssall += nconshdlrconss;
508  }
509  }
510 
511  /* print warning if we have unsupported constraint types.
512  * we do not abort the matrix creation process here, because
513  * it makes sometimes sense to work on an incomplete
514  * matrix as long as the number of interesting variable
515  * uplocks or downlocks of the matrix and scip
516  * are the same.
517  */
518  if( nconss < nconssall )
519  {
520  SCIPdebugMsg(scip, "Warning: milp matrix not complete!\n");
521  }
522  else
523  {
524  /* all constraints represented within the matrix */
525  *complete = TRUE;
526  }
527 
528  /* do nothing if we have no checked constraints */
529  if( nconss == 0 )
530  return SCIP_OKAY;
531 
532  stopped = FALSE;
533 
534  vars = SCIPgetVars(scip);
535  nvars = SCIPgetNVars(scip);
536 
537  /* approximate number of nonzeros by taking for each variable the number of up- and downlocks;
538  * this counts nonzeros in equalities twice, but can be at most two times as high as the exact number
539  */
540  for( i = nvars - 1; i >= 0; --i )
541  {
542  nnonzstmp += SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL);
543  nnonzstmp += SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL);
544  }
545 
546  /* do nothing if we have no entries */
547  if( nnonzstmp == 0 )
548  return SCIP_OKAY;
549 
550  /* build the matrix structure */
551  SCIP_CALL( SCIPallocBuffer(scip, matrixptr) );
552  matrix = *matrixptr;
553 
554  /* copy vars array and set number of variables */
555  SCIP_CALL( SCIPduplicateBufferArray(scip, &matrix->vars, vars, nvars) );
556  matrix->ncols = nvars;
557 
558  matrix->nrows = 0;
559  matrix->nnonzs = 0;
560 
561  /* allocate memory */
562  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatval, nnonzstmp) );
563  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatind, nnonzstmp) );
564  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatbeg, matrix->ncols) );
565  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatcnt, matrix->ncols) );
566  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->lb, matrix->ncols) );
567  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->ub, matrix->ncols) );
568  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->nuplocks, matrix->ncols) );
569  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->ndownlocks, matrix->ncols) );
570 
571  BMSclearMemoryArray(matrix->nuplocks, matrix->ncols);
572  BMSclearMemoryArray(matrix->ndownlocks, matrix->ncols);
573 
574  /* init bounds */
575  for( v = 0; v < matrix->ncols; v++ )
576  {
577  var = matrix->vars[v];
578  assert(var != NULL);
579 
580  matrix->lb[v] = SCIPvarGetLbGlobal(var);
581  matrix->ub[v] = SCIPvarGetUbGlobal(var);
582  }
583 
584  /* allocate memory */
585  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatval, nnonzstmp) );
586  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatind, nnonzstmp) );
587  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatbeg, nconss) );
588  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatcnt, nconss) );
589  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->lhs, nconss) );
590  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rhs, nconss) );
591  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->cons, nconss) );
592  SCIP_CALL( SCIPallocClearMemoryArray(scip, &matrix->isrhsinfinite, nconss) );
593  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->minactivity, nconss) );
594  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->maxactivity, nconss) );
595  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->minactivityneginf, nconss) );
596  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->minactivityposinf, nconss) );
597  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->maxactivityneginf, nconss) );
598  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->maxactivityposinf, nconss) );
599 
600  cnt = 0;
601 
602  /* loop a second time over constraints handlers and add supported constraints to the matrix */
603  for( i = 0; i < nconshdlrs; ++i )
604  {
605  SCIP_CONS** conshdlrconss;
606  int nconshdlrconss;
607  SCIP_Bool rowadded;
608 
609  if( SCIPisStopped(scip) )
610  {
611  stopped = TRUE;
612  break;
613  }
614 
615  conshdlrname = SCIPconshdlrGetName(conshdlrs[i]);
616  conshdlrconss = SCIPconshdlrGetCheckConss(conshdlrs[i]);
617  nconshdlrconss = SCIPconshdlrGetNCheckConss(conshdlrs[i]);
618 
619  if( strcmp(conshdlrname, "linear") == 0 )
620  {
621  for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
622  {
623  cons = conshdlrconss[c];
624  assert(SCIPconsIsTransformed(cons));
625 
626  SCIP_CALL( addConstraint(scip, matrix, SCIPgetVarsLinear(scip, cons),
627  SCIPgetValsLinear(scip, cons), SCIPgetNVarsLinear(scip, cons),
628  SCIPgetLhsLinear(scip, cons), SCIPgetRhsLinear(scip, cons), nnonzstmp, &rowadded) );
629 
630  if(rowadded)
631  {
632  assert(cnt < nconss);
633  matrix->cons[cnt] = cons;
634  cnt++;
635  }
636  }
637  }
638  else if( strcmp(conshdlrname, "setppc") == 0 )
639  {
640  for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
641  {
642  SCIP_Real lhs;
643  SCIP_Real rhs;
644 
645  cons = conshdlrconss[c];
646  assert(SCIPconsIsTransformed(cons));
647 
648  switch( SCIPgetTypeSetppc(scip, cons) )
649  {
651  lhs = 1.0;
652  rhs = 1.0;
653  break;
655  lhs = -SCIPinfinity(scip);
656  rhs = 1.0;
657  break;
659  lhs = 1.0;
660  rhs = SCIPinfinity(scip);
661  break;
662  default:
663  return SCIP_ERROR;
664  }
665 
666  SCIP_CALL( addConstraint(scip, matrix, SCIPgetVarsSetppc(scip, cons), NULL,
667  SCIPgetNVarsSetppc(scip, cons), lhs, rhs, nnonzstmp, &rowadded) );
668 
669  if(rowadded)
670  {
671  assert(cnt < nconss);
672  matrix->cons[cnt] = cons;
673  cnt++;
674  }
675  }
676  }
677  else if( strcmp(conshdlrname, "logicor") == 0 )
678  {
679  for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
680  {
681  cons = conshdlrconss[c];
682  assert(SCIPconsIsTransformed(cons));
683 
684  SCIP_CALL( addConstraint(scip, matrix, SCIPgetVarsLogicor(scip, cons),
685  NULL, SCIPgetNVarsLogicor(scip, cons), 1.0, SCIPinfinity(scip), nnonzstmp, &rowadded) );
686 
687  if(rowadded)
688  {
689  assert(cnt < nconss);
690  matrix->cons[cnt] = cons;
691  cnt++;
692  }
693  }
694  }
695  else if( strcmp(conshdlrname, "knapsack") == 0 )
696  {
697  if( nconshdlrconss > 0 )
698  {
699  SCIP_Real* consvals;
700  int valssize;
701 
702  valssize = 100;
703  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, valssize) );
704 
705  for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
706  {
707  SCIP_Longint* weights;
708 
709  cons = conshdlrconss[c];
710  assert(SCIPconsIsTransformed(cons));
711 
712  weights = SCIPgetWeightsKnapsack(scip, cons);
713  nvars = SCIPgetNVarsKnapsack(scip, cons);
714 
715  if( nvars > valssize )
716  {
717  valssize = (int) (1.5 * nvars);
718  SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, valssize) );
719  }
720 
721  for( v = 0; v < nvars; v++ )
722  consvals[v] = (SCIP_Real)weights[v];
723 
724  SCIP_CALL( addConstraint(scip, matrix, SCIPgetVarsKnapsack(scip, cons), consvals,
725  SCIPgetNVarsKnapsack(scip, cons), -SCIPinfinity(scip),
726  (SCIP_Real)SCIPgetCapacityKnapsack(scip, cons), nnonzstmp, &rowadded) );
727 
728  if(rowadded)
729  {
730  assert(cnt < nconss);
731  matrix->cons[cnt] = cons;
732  cnt++;
733  }
734  }
735 
736  SCIPfreeBufferArray(scip, &consvals);
737  }
738  }
739  else if( strcmp(conshdlrname, "varbound") == 0 )
740  {
741  if( nconshdlrconss > 0 )
742  {
743  SCIP_VAR** consvars;
744  SCIP_Real* consvals;
745 
746  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) );
747  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) );
748  consvals[0] = 1.0;
749 
750  for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
751  {
752  cons = conshdlrconss[c];
753  assert(SCIPconsIsTransformed(cons));
754 
755  consvars[0] = SCIPgetVarVarbound(scip, cons);
756  consvars[1] = SCIPgetVbdvarVarbound(scip, cons);
757 
758  consvals[1] = SCIPgetVbdcoefVarbound(scip, cons);
759 
760  SCIP_CALL( addConstraint(scip, matrix, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons),
761  SCIPgetRhsVarbound(scip, cons), nnonzstmp, &rowadded) );
762 
763  if(rowadded)
764  {
765  assert(cnt < nconss);
766  matrix->cons[cnt] = cons;
767  cnt++;
768  }
769  }
770 
771  SCIPfreeBufferArray(scip, &consvals);
772  SCIPfreeBufferArray(scip, &consvars);
773  }
774  }
775 /* the code below is correct. However, it needs to be disabled
776  * because some of the presolvers can currently only handle 1-1 row-cons relationships,
777  * while the linking constraint handler requires a representation as 2 linear constraints.
778  */
779 #ifdef SCIP_DISABLED_CODE
780  else if( strcmp(conshdlrname, "linking") == 0 )
781  {
782  if( nconshdlrconss > 0 )
783  {
784  SCIP_VAR** consvars;
785  SCIP_VAR** curconsvars;
786  SCIP_Real* consvals;
787  int* curconsvals;
788  int valssize;
789  int nconsvars;
790  int j;
791 
792  valssize = 100;
793  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, valssize) );
794  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, valssize) );
795 
796  for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
797  {
798  cons = conshdlrconss[c];
799  assert(SCIPconsIsTransformed(cons));
800 
801  /* get constraint variables and their amount */
802  SCIP_CALL( SCIPgetBinvarsLinking(scip, cons, &curconsvars, &nconsvars) );
803  curconsvals = SCIPgetValsLinking(scip, cons);
804 
805  /* SCIPgetBinVarsLinking returns the number of binary variables, but we also need the integer variable */
806  nconsvars++;
807 
808  if( nconsvars > valssize )
809  {
810  valssize = (int) (1.5 * nconsvars);
811  SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, valssize) );
812  SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, valssize) );
813  }
814 
815  /* copy vars and vals for binary variables */
816  for( j = 0; j < nconsvars - 1; j++ )
817  {
818  consvars[j] = curconsvars[j];
819  consvals[j] = (SCIP_Real) curconsvals[j];
820  }
821 
822  /* set final entry of vars and vals to the linking variable and its coefficient, respectively */
823  consvars[nconsvars - 1] = SCIPgetIntvarLinking(scip, cons);
824  consvals[nconsvars - 1] = -1;
825 
826  SCIP_CALL( addConstraint(scip, matrix, consvars, consvals, nconsvars, 0.0, 0.0, nnonzstmp, &rowadded) );
827  SCIP_CALL( addConstraint(scip, matrix, consvars, NULL, nconsvars - 1, 1.0, 1.0, nnonzstmp, &rowadded) );
828 
829  if(rowadded)
830  {
831  assert(cnt < nconss);
832  matrix->cons[cnt] = cons;
833  matrix->cons[cnt + 1] = cons;
834  cnt += 2;
835  }
836  }
837 
838  SCIPfreeBufferArray(scip, &consvals);
839  SCIPfreeBufferArray(scip, &consvars);
840  }
841  }
842 #endif
843  }
844  assert(matrix->nrows == cnt);
845  assert(matrix->nrows <= nconss);
846  assert(matrix->nnonzs <= nnonzstmp);
847 
848  if( !stopped )
849  {
850  /* calculate row activity bounds */
851  SCIP_CALL( calcActivityBounds(scip, matrix) );
852 
853  /* transform row major format into column major format */
854  SCIP_CALL( setColumnMajorFormat(scip, matrix) );
855 
856  *initialized = TRUE;
857  }
858 
859  return SCIP_OKAY;
860 }
861 
862 
863 /** frees the constraint matrix */
865  SCIP* scip, /**< current SCIP instance */
866  SCIP_MATRIX** matrix /**< constraint matrix object */
867  )
868 {
869  assert(scip != NULL);
870  assert(matrix != NULL);
871 
872  if( (*matrix) != NULL )
873  {
874  assert((*matrix)->colmatval != NULL);
875  assert((*matrix)->colmatind != NULL);
876  assert((*matrix)->colmatbeg != NULL);
877  assert((*matrix)->colmatcnt != NULL);
878  assert((*matrix)->lb != NULL);
879  assert((*matrix)->ub != NULL);
880  assert((*matrix)->nuplocks != NULL);
881  assert((*matrix)->ndownlocks != NULL);
882 
883  assert((*matrix)->rowmatval != NULL);
884  assert((*matrix)->rowmatind != NULL);
885  assert((*matrix)->rowmatbeg != NULL);
886  assert((*matrix)->rowmatcnt != NULL);
887  assert((*matrix)->lhs != NULL);
888  assert((*matrix)->rhs != NULL);
889 
890  SCIPfreeBufferArray(scip, &((*matrix)->maxactivityposinf));
891  SCIPfreeBufferArray(scip, &((*matrix)->maxactivityneginf));
892  SCIPfreeBufferArray(scip, &((*matrix)->minactivityposinf));
893  SCIPfreeBufferArray(scip, &((*matrix)->minactivityneginf));
894  SCIPfreeBufferArray(scip, &((*matrix)->maxactivity));
895  SCIPfreeBufferArray(scip, &((*matrix)->minactivity));
896 
897  SCIPfreeMemoryArray(scip, &((*matrix)->isrhsinfinite));
898  SCIPfreeBufferArray(scip, &((*matrix)->cons));
899 
900  SCIPfreeBufferArray(scip, &((*matrix)->rhs));
901  SCIPfreeBufferArray(scip, &((*matrix)->lhs));
902  SCIPfreeBufferArray(scip, &((*matrix)->rowmatcnt));
903  SCIPfreeBufferArray(scip, &((*matrix)->rowmatbeg));
904  SCIPfreeBufferArray(scip, &((*matrix)->rowmatind));
905  SCIPfreeBufferArray(scip, &((*matrix)->rowmatval));
906 
907  SCIPfreeBufferArray(scip, &((*matrix)->ndownlocks));
908  SCIPfreeBufferArray(scip, &((*matrix)->nuplocks));
909  SCIPfreeBufferArray(scip, &((*matrix)->ub));
910  SCIPfreeBufferArray(scip, &((*matrix)->lb));
911  SCIPfreeBufferArray(scip, &((*matrix)->colmatcnt));
912  SCIPfreeBufferArray(scip, &((*matrix)->colmatbeg));
913  SCIPfreeBufferArray(scip, &((*matrix)->colmatind));
914  SCIPfreeBufferArray(scip, &((*matrix)->colmatval));
915 
916  (*matrix)->nrows = 0;
917  (*matrix)->ncols = 0;
918  (*matrix)->nnonzs = 0;
919 
920  SCIPfreeBufferArrayNull(scip, &((*matrix)->vars));
921 
922  SCIPfreeBuffer(scip, matrix);
923  }
924 }
925 
926 /** print one row of the matrix */
928  SCIP* scip, /**< current SCIP instance */
929  SCIP_MATRIX* matrix, /**< constraint matrix object */
930  int row /**< row index */
931  )
932 {
933  int* rowpnt;
934  int* rowend;
935  int col;
936  SCIP_Real val;
937  SCIP_Real* valpnt;
938 
939  rowpnt = matrix->rowmatind + matrix->rowmatbeg[row];
940  rowend = rowpnt + matrix->rowmatcnt[row];
941  valpnt = matrix->rowmatval + matrix->rowmatbeg[row];
942 
943  printf("### %s: %.15g <=", SCIPconsGetName(matrix->cons[row]), matrix->lhs[row]);
944  for(; (rowpnt < rowend); rowpnt++, valpnt++)
945  {
946  col = *rowpnt;
947  val = *valpnt;
948  if( val < 0 )
949  printf(" %.15g %s [%.15g,%.15g]", val, SCIPvarGetName(matrix->vars[col]),
950  SCIPvarGetLbGlobal(matrix->vars[col]), SCIPvarGetUbGlobal(matrix->vars[col]));
951  else
952  printf(" +%.15g %s [%.15g,%.15g]", val, SCIPvarGetName(matrix->vars[col]),
953  SCIPvarGetLbGlobal(matrix->vars[col]), SCIPvarGetUbGlobal(matrix->vars[col]));
954  }
955  printf(" <= %.15g ###\n", matrix->rhs[row]);
956 }
957 
958 /** detect parallel rows of matrix. rhs/lhs are ignored. */
960  SCIP* scip, /**< SCIP instance */
961  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
962  SCIP_Real* scale, /**< scale factors of rows */
963  int* pclass /**< parallel row classes */
964  )
965 {
966  SCIP_Real* valpnt;
967  SCIP_Real* values;
968  int* classsizes;
969  int* pcset;
970  int* colpnt;
971  int* colend;
972  int* rowindices;
973  int* pcs;
974  SCIP_Real startval;
975  SCIP_Real aij;
976  int startpc;
977  int startk;
978  int startt;
979  int pcsetfill;
980  int rowidx;
981  int k;
982  int t;
983  int m;
984  int i;
985  int c;
986  int newpclass;
987  int pc;
988 
989  assert(scip != NULL);
990  assert(matrix != NULL);
991  assert(pclass != NULL);
992 
993  SCIP_CALL( SCIPallocBufferArray(scip, &classsizes, matrix->nrows) );
994  SCIP_CALL( SCIPallocBufferArray(scip, &pcset, matrix->nrows) );
995  SCIP_CALL( SCIPallocBufferArray(scip, &values, matrix->nrows) );
996  SCIP_CALL( SCIPallocBufferArray(scip, &rowindices, matrix->nrows) );
997  SCIP_CALL( SCIPallocBufferArray(scip, &pcs, matrix->nrows) );
998 
999  /* init */
1000  BMSclearMemoryArray(scale, matrix->nrows);
1001  BMSclearMemoryArray(pclass, matrix->nrows);
1002  BMSclearMemoryArray(classsizes, matrix->nrows);
1003  classsizes[0] = matrix->nrows;
1004  pcsetfill = 0;
1005  for( t = 1; t < matrix->nrows; ++t )
1006  pcset[pcsetfill++] = t;
1007 
1008  /* loop over all columns */
1009  for( c = 0; c < matrix->ncols; ++c )
1010  {
1011  if( matrix->colmatcnt[c] == 0 )
1012  continue;
1013 
1014  colpnt = matrix->colmatind + matrix->colmatbeg[c];
1015  colend = colpnt + matrix->colmatcnt[c];
1016  valpnt = matrix->colmatval + matrix->colmatbeg[c];
1017 
1018  i = 0;
1019  for( ; (colpnt < colend); colpnt++, valpnt++ )
1020  {
1021  aij = *valpnt;
1022  rowidx = *colpnt;
1023 
1024  if( scale[rowidx] == 0.0 )
1025  scale[rowidx] = aij;
1026  assert(scale[rowidx] != 0.0);
1027 
1028  rowindices[i] = rowidx;
1029  values[i] = aij / scale[rowidx];
1030  pc = pclass[rowidx];
1031  assert(pc < matrix->nrows);
1032 
1033  /* update class sizes and pclass set */
1034  assert(classsizes[pc] > 0);
1035  classsizes[pc]--;
1036  if( classsizes[pc] == 0 )
1037  {
1038  assert(pcsetfill < matrix->nrows);
1039  pcset[pcsetfill++] = pc;
1040  }
1041  pcs[i] = pc;
1042 
1043  i++;
1044  }
1045 
1046  /* sort on the pclass values */
1047  if( i > 1 )
1048  {
1049  SCIPsortIntIntReal(pcs, rowindices, values, i);
1050  }
1051 
1052  k = 0;
1053  while( TRUE ) /*lint !e716*/
1054  {
1055  assert(k < i);
1056  startpc = pcs[k];
1057  startk = k;
1058 
1059  /* find pclass-sets */
1060  while( k < i && pcs[k] == startpc )
1061  k++;
1062 
1063  /* sort on the A values which have equal pclass values */
1064  if( k - startk > 1 )
1065  SCIPsortRealInt(&(values[startk]), &(rowindices[startk]), k - startk);
1066 
1067  t = 0;
1068  while( TRUE ) /*lint !e716*/
1069  {
1070  assert(startk + t < i);
1071  startval = values[startk + t];
1072  startt = t;
1073 
1074  /* find A-sets */
1075  while( t < k - startk && SCIPisEQ(scip, startval, values[startk + t]) )
1076  t++;
1077 
1078  /* get new pclass */
1079  newpclass = pcset[0];
1080  assert(pcsetfill > 0);
1081  pcset[0] = pcset[--pcsetfill];
1082 
1083  /* renumbering */
1084  for( m = startk + startt; m < startk + t; m++ )
1085  {
1086  assert(m < i);
1087  assert(rowindices[m] < matrix->nrows);
1088  assert(newpclass < matrix->nrows);
1089 
1090  pclass[rowindices[m]] = newpclass;
1091  classsizes[newpclass]++;
1092  }
1093 
1094  if( t == k - startk )
1095  break;
1096  }
1097 
1098  if( k == matrix->colmatcnt[c] )
1099  break;
1100  }
1101  }
1102 
1103  SCIPfreeBufferArray(scip, &pcs);
1104  SCIPfreeBufferArray(scip, &rowindices);
1105  SCIPfreeBufferArray(scip, &values);
1106  SCIPfreeBufferArray(scip, &pcset);
1107  SCIPfreeBufferArray(scip, &classsizes);
1108 
1109  return SCIP_OKAY;
1110 }
1111 
1112 /** detect parallel rows of matrix.
1113  * obj coefficients are ignored.
1114  */
1116  SCIP* scip, /**< SCIP instance */
1117  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1118  SCIP_Real* scale, /**< scale factors of cols */
1119  int* pclass, /**< parallel column classes */
1120  SCIP_Bool* varineq /**< indicating if variable is within an equation */
1121  )
1122 {
1123  SCIP_Real* valpnt;
1124  SCIP_Real* values;
1125  int* classsizes;
1126  int* pcset;
1127  int* rowpnt;
1128  int* rowend;
1129  int* colindices;
1130  int* pcs;
1131  SCIP_Real startval;
1132  SCIP_Real aij;
1133  int startpc;
1134  int startk;
1135  int startt;
1136  int pcsetfill;
1137  int colidx;
1138  int k;
1139  int t;
1140  int m;
1141  int i;
1142  int r;
1143  int newpclass;
1144  int pc;
1145 
1146  assert(scip != NULL);
1147  assert(matrix != NULL);
1148  assert(pclass != NULL);
1149  assert(varineq != NULL);
1150 
1151  SCIP_CALL( SCIPallocBufferArray(scip, &classsizes, matrix->ncols) );
1152  SCIP_CALL( SCIPallocBufferArray(scip, &pcset, matrix->ncols) );
1153  SCIP_CALL( SCIPallocBufferArray(scip, &values, matrix->ncols) );
1154  SCIP_CALL( SCIPallocBufferArray(scip, &colindices, matrix->ncols) );
1155  SCIP_CALL( SCIPallocBufferArray(scip, &pcs, matrix->ncols) );
1156 
1157  /* init */
1158  BMSclearMemoryArray(scale, matrix->ncols);
1159  BMSclearMemoryArray(pclass, matrix->ncols);
1160  BMSclearMemoryArray(classsizes, matrix->ncols);
1161  classsizes[0] = matrix->ncols;
1162  pcsetfill = 0;
1163  for( t = 1; t < matrix->ncols; ++t )
1164  pcset[pcsetfill++] = t;
1165 
1166  /* loop over all rows */
1167  for( r = 0; r < matrix->nrows; ++r )
1168  {
1169  /* we consider only equations or ranged rows */
1170  if( !matrix->isrhsinfinite[r] )
1171  {
1172  rowpnt = matrix->rowmatind + matrix->rowmatbeg[r];
1173  rowend = rowpnt + matrix->rowmatcnt[r];
1174  valpnt = matrix->rowmatval + matrix->rowmatbeg[r];
1175 
1176  i = 0;
1177  for( ; (rowpnt < rowend); rowpnt++, valpnt++ )
1178  {
1179  aij = *valpnt;
1180  colidx = *rowpnt;
1181 
1182  /* remember variable was part of an equation or ranged row */
1183  varineq[colidx] = TRUE;
1184 
1185  if( scale[colidx] == 0.0 )
1186  scale[colidx] = aij;
1187  assert(scale[colidx] != 0.0);
1188 
1189  colindices[i] = colidx;
1190  values[i] = aij / scale[colidx];
1191  pc = pclass[colidx];
1192  assert(pc < matrix->ncols);
1193 
1194  /* update class sizes and pclass set */
1195  assert(classsizes[pc] > 0);
1196  classsizes[pc]--;
1197  if( classsizes[pc] == 0 )
1198  {
1199  assert(pcsetfill < matrix->ncols);
1200  pcset[pcsetfill++] = pc;
1201  }
1202  pcs[i] = pc;
1203 
1204  i++;
1205  }
1206 
1207  /* sort on the pclass values */
1208  if( i > 1 )
1209  {
1210  SCIPsortIntIntReal(pcs, colindices, values, i);
1211  }
1212 
1213  k = 0;
1214  while( TRUE ) /*lint !e716*/
1215  {
1216  assert(k < i);
1217  startpc = pcs[k];
1218  startk = k;
1219 
1220  /* find pclass-sets */
1221  while( k < i && pcs[k] == startpc )
1222  k++;
1223 
1224  /* sort on the A values which have equal pclass values */
1225  if( k - startk > 1 )
1226  SCIPsortRealInt(&(values[startk]), &(colindices[startk]), k - startk);
1227 
1228  t = 0;
1229  while( TRUE ) /*lint !e716*/
1230  {
1231  assert(startk + t < i);
1232  startval = values[startk + t];
1233  startt = t;
1234 
1235  /* find A-sets */
1236  while( t < k - startk && SCIPisEQ(scip, startval, values[startk + t]) )
1237  t++;
1238 
1239  /* get new pclass */
1240  newpclass = pcset[0];
1241  assert(pcsetfill > 0);
1242  pcset[0] = pcset[--pcsetfill];
1243 
1244  /* renumbering */
1245  for( m = startk + startt; m < startk + t; m++ )
1246  {
1247  assert(m < i);
1248  assert(colindices[m] < matrix->ncols);
1249  assert(newpclass < matrix->ncols);
1250 
1251  pclass[colindices[m]] = newpclass;
1252  classsizes[newpclass]++;
1253  }
1254 
1255  if( t == k - startk )
1256  break;
1257  }
1258 
1259  if( k == matrix->rowmatcnt[r] )
1260  break;
1261  }
1262  }
1263  }
1264 
1265  SCIPfreeBufferArray(scip, &pcs);
1266  SCIPfreeBufferArray(scip, &colindices);
1267  SCIPfreeBufferArray(scip, &values);
1268  SCIPfreeBufferArray(scip, &pcset);
1269  SCIPfreeBufferArray(scip, &classsizes);
1270 
1271  return SCIP_OKAY;
1272 }
1273 
1274 
1275 /*
1276  * access functions implemented as defines
1277  */
1278 
1279 /* In debug mode, the following methods are implemented as function calls to ensure
1280  * type validity.
1281  * In optimized mode, the methods are implemented as defines to improve performance.
1282  * However, we want to have them in the library anyways, so we have to undef the defines.
1283  */
1284 
1285 #undef SCIPmatrixGetColValPtr
1286 #undef SCIPmatrixGetColIdxPtr
1287 #undef SCIPmatrixGetColNNonzs
1288 #undef SCIPmatrixGetNColumns
1289 #undef SCIPmatrixGetColUb
1290 #undef SCIPmatrixGetColLb
1291 #undef SCIPmatrixGetColNUplocks
1292 #undef SCIPmatrixGetColNDownlocks
1293 #undef SCIPmatrixGetVar
1294 #undef SCIPmatrixGetColName
1295 #undef SCIPmatrixGetRowValPtr
1296 #undef SCIPmatrixGetRowIdxPtr
1297 #undef SCIPmatrixGetRowNNonzs
1298 #undef SCIPmatrixGetRowName
1299 #undef SCIPmatrixGetNRows
1300 #undef SCIPmatrixGetRowLhs
1301 #undef SCIPmatrixGetRowRhs
1302 #undef SCIPmatrixIsRowRhsInfinity
1303 #undef SCIPmatrixGetNNonzs
1304 #undef SCIPmatrixGetRowMinActivity
1305 #undef SCIPmatrixGetRowMaxActivity
1306 #undef SCIPmatrixGetRowNMinActNegInf
1307 #undef SCIPmatrixGetRowNMinActPosInf
1308 #undef SCIPmatrixGetRowNMaxActNegInf
1309 #undef SCIPmatrixGetRowNMaxActPosInf
1310 #undef SCIPmatrixGetCons
1311 #undef SCIPmatrixUplockConflict
1312 #undef SCIPmatrixDownlockConflict
1313 
1314 /** get column based start pointer of values */
1316  SCIP_MATRIX* matrix, /**< matrix instance */
1317  int col /**< column index */
1318  )
1319 {
1320  assert(matrix != NULL);
1321  assert(0 <= col && col < matrix->ncols);
1322 
1323  return matrix->colmatval + matrix->colmatbeg[col];
1324 }
1325 
1326 /** get column based start pointer of row indices */
1328  SCIP_MATRIX* matrix, /**< matrix instance */
1329  int col /**< column index */
1330  )
1331 {
1332  assert(matrix != NULL);
1333  assert(0 <= col && col < matrix->ncols);
1334 
1335  return matrix->colmatind + matrix->colmatbeg[col];
1336 }
1337 
1338 /** get the number of non-zero entries of this column */
1340  SCIP_MATRIX* matrix, /**< matrix instance */
1341  int col /**< column index */
1342  )
1343 {
1344  assert(matrix != NULL);
1345  assert(0 <= col && col < matrix->ncols);
1346 
1347  return matrix->colmatcnt[col];
1348 }
1349 
1350 /** get number of columns of the matrix */
1352  SCIP_MATRIX* matrix /**< matrix instance */
1353  )
1354 {
1355  assert(matrix != NULL);
1356 
1357  return matrix->ncols;
1358 }
1359 
1360 /** get upper bound of column */
1362  SCIP_MATRIX* matrix, /**< matrix instance */
1363  int col /**< column index */
1364  )
1365 {
1366  assert(matrix != NULL);
1367 
1368  return matrix->ub[col];
1369 }
1370 
1371 /** get lower bound of column */
1373  SCIP_MATRIX* matrix, /**< matrix instance */
1374  int col /**< column index */
1375  )
1376 {
1377  assert(matrix != NULL);
1378 
1379  return matrix->lb[col];
1380 }
1381 
1382 /** get number of uplocks of column */
1384  SCIP_MATRIX* matrix, /**< matrix instance */
1385  int col /**< column index */
1386  )
1387 {
1388  assert(matrix != NULL);
1389  assert(0 <= col && col < matrix->ncols);
1390 
1391  return matrix->nuplocks[col];
1392 }
1393 
1394 /** get number of downlocks of column */
1396  SCIP_MATRIX* matrix, /**< matrix instance */
1397  int col /**< column index */
1398  )
1399 {
1400  assert(matrix != NULL);
1401  assert(0 <= col && col < matrix->ncols);
1402 
1403  return matrix->ndownlocks[col];
1404 }
1405 
1406 /** get variable pointer of column */
1408  SCIP_MATRIX* matrix, /**< matrix instance */
1409  int col /**< column index */
1410  )
1411 {
1412  assert(matrix != NULL);
1413  assert(0 <= col && col < matrix->ncols);
1414 
1415  return matrix->vars[col];
1416 }
1417 
1418 /** get name of column/variable */
1420  SCIP_MATRIX* matrix, /**< matrix instance */
1421  int col /**< column index */
1422  )
1423 {
1424  assert(matrix != NULL);
1425  assert(0 <= col && col < matrix->ncols);
1426 
1427  return SCIPvarGetName(matrix->vars[col]);
1428 }
1429 
1430 /** get row based start pointer of values */
1432  SCIP_MATRIX* matrix, /**< matrix instance */
1433  int row /**< row index */
1434  )
1435 {
1436  assert(matrix != NULL);
1437  assert(0 <= row && row < matrix->nrows);
1438 
1439  return matrix->rowmatval + matrix->rowmatbeg[row];
1440 }
1441 
1442 /** get row based start pointer of column indices */
1444  SCIP_MATRIX* matrix, /**< matrix instance */
1445  int row /**< row index */
1446  )
1447 {
1448  assert(matrix != NULL);
1449  assert(0 <= row && row < matrix->nrows);
1450 
1451  return matrix->rowmatind + matrix->rowmatbeg[row];
1452 }
1453 
1454 /** get number of non-zeros of this row */
1456  SCIP_MATRIX* matrix, /**< matrix instance */
1457  int row /**< row index */
1458  )
1459 {
1460  assert(matrix != NULL);
1461  assert(0 <= row && row < matrix->nrows);
1462 
1463  return matrix->rowmatcnt[row];
1464 }
1465 
1466 /** get name of row */
1468  SCIP_MATRIX* matrix, /**< matrix instance */
1469  int row /**< row index */
1470  )
1471 {
1472  assert(matrix != NULL);
1473  assert(0 <= row && row < matrix->nrows);
1474 
1475  return SCIPconsGetName(matrix->cons[row]);
1476 }
1477 
1478 /** get number of rows of the matrix */
1480  SCIP_MATRIX* matrix /**< matrix instance */
1481  )
1482 {
1483  assert(matrix != NULL);
1484 
1485  return matrix->nrows;
1486 }
1487 
1488 /** get left-hand-side of row */
1490  SCIP_MATRIX* matrix, /**< matrix instance */
1491  int row /**< row index */
1492  )
1493 {
1494  assert(matrix != NULL);
1495  assert(0 <= row && row < matrix->nrows);
1496 
1497  return matrix->lhs[row];
1498 }
1499 
1500 /** get right-hand-side of row */
1502  SCIP_MATRIX* matrix, /**< matrix instance */
1503  int row /**< row index */
1504  )
1505 {
1506  assert(matrix != NULL);
1507  assert(0 <= row && row < matrix->nrows);
1508 
1509  return matrix->rhs[row];
1510 }
1511 
1512 /** flag indicating if right-hand-side of row is infinity */
1514  SCIP_MATRIX* matrix, /**< matrix instance */
1515  int row /**< row index */
1516  )
1517 {
1518  assert(matrix != NULL);
1519  assert(0 <= row && row < matrix->nrows);
1520 
1521  return matrix->isrhsinfinite[row];
1522 }
1523 
1524 /** get number of non-zeros of matrix */
1526  SCIP_MATRIX* matrix /**< matrix instance */
1527  )
1528 {
1529  assert(matrix != NULL);
1530 
1531  return matrix->nnonzs;
1532 }
1533 
1534 /** get minimal activity of row */
1536  SCIP_MATRIX* matrix, /**< matrix instance */
1537  int row /**< row index */
1538  )
1539 {
1540  assert(matrix != NULL);
1541  assert(0 <= row && row < matrix->nrows);
1542 
1543  return matrix->minactivity[row];
1544 }
1545 
1546 /** get maximal activity of row */
1548  SCIP_MATRIX* matrix, /**< matrix instance */
1549  int row /**< row index */
1550  )
1551 {
1552  assert(matrix != NULL);
1553  assert(0 <= row && row < matrix->nrows);
1554 
1555  return matrix->maxactivity[row];
1556 }
1557 
1558 /** get number of negative infinities present within minimal activity */
1560  SCIP_MATRIX* matrix, /**< matrix instance */
1561  int row /**< row index */
1562  )
1563 {
1564  assert(matrix != NULL);
1565  assert(0 <= row && row < matrix->nrows);
1566 
1567  return matrix->minactivityneginf[row];
1568 }
1569 
1570 /** get number of positive infinities present within minimal activity */
1572  SCIP_MATRIX* matrix, /**< matrix instance */
1573  int row /**< row index */
1574  )
1575 {
1576  assert(matrix != NULL);
1577  assert(0 <= row && row < matrix->nrows);
1578 
1579  return matrix->minactivityposinf[row];
1580 }
1581 
1582 /** get number of negative infinities present within maximal activity */
1584  SCIP_MATRIX* matrix, /**< matrix instance */
1585  int row /**< row index */
1586  )
1587 {
1588  assert(matrix != NULL);
1589  assert(0 <= row && row < matrix->nrows);
1590 
1591  return matrix->maxactivityneginf[row];
1592 }
1593 
1594 /** get number of positive infinities present within maximal activity */
1596  SCIP_MATRIX* matrix, /**< matrix instance */
1597  int row /**< row index */
1598  )
1599 {
1600  assert(matrix != NULL);
1601  assert(0 <= row && row < matrix->nrows);
1602 
1603  return matrix->maxactivityposinf[row];
1604 }
1605 
1606 /** get constraint pointer for constraint representing row */
1608  SCIP_MATRIX* matrix, /**< matrix instance */
1609  int row /**< row index */
1610  )
1611 {
1612  assert(matrix != NULL);
1613  assert(0 <= row && row < matrix->nrows);
1614 
1615  return matrix->cons[row];
1616 }
1617 
1618 /** get if conflicting uplocks of a specific variable present */
1620  SCIP_MATRIX* matrix, /**< matrix instance */
1621  int col /**< column index */
1622  )
1623 {
1624  assert(matrix != NULL);
1625  assert(0 <= col && col < matrix->ncols);
1626 
1627  return (SCIPvarGetNLocksUpType(matrix->vars[col], SCIP_LOCKTYPE_MODEL) == matrix->nuplocks[col]);
1628 }
1629 
1630 /** get if conflicting downlocks of a specific variable present */
1632  SCIP_MATRIX* matrix, /**< matrix instance */
1633  int col /**< column index */
1634  )
1635 {
1636  assert(matrix != NULL);
1637  assert(0 <= col && col < matrix->ncols);
1638 
1639  return (SCIPvarGetNLocksDownType(matrix->vars[col], SCIP_LOCKTYPE_MODEL) == matrix->ndownlocks[col]);
1640 }
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPmatrixPrintRow(SCIP *scip, SCIP_MATRIX *matrix, int row)
Definition: matrix.c:927
SCIP_RETCODE SCIPmatrixGetParallelRows(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real *scale, int *pclass)
Definition: matrix.c:959
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1407
#define NULL
Definition: def.h:246
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1479
int * maxactivityneginf
Definition: struct_matrix.h:69
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3176
int * minactivityneginf
Definition: struct_matrix.h:67
Constraint handler for variable bound constraints .
public methods for memory management
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9252
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:88
static SCIP_RETCODE addConstraint(SCIP *scip, SCIP_MATRIX *matrix, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real lhs, SCIP_Real rhs, int maxnnonzsmem, SCIP_Bool *rowadded)
Definition: matrix.c:207
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17344
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3233
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1607
int * SCIPgetValsLinking(SCIP *scip, SCIP_CONS *cons)
SCIP_Real * colmatval
Definition: struct_matrix.h:40
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:864
int * minactivityposinf
Definition: struct_matrix.h:68
int * colmatcnt
Definition: struct_matrix.h:43
#define FALSE
Definition: def.h:72
SCIP_Real SCIPinfinity(SCIP *scip)
#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)
void SCIPsortIntIntReal(int *intarray1, int *intarray2, SCIP_Real *realarray, int len)
SCIP_RETCODE SCIPmatrixGetParallelCols(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real *scale, int *pclass, SCIP_Bool *varineq)
Definition: matrix.c:1115
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:138
SCIP_Real * maxactivity
Definition: struct_matrix.h:66
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
SCIP_Real SCIPmatrixGetRowMaxActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1547
Constraint handler for the set partitioning / packing / covering constraints .
public methods for SCIP variables
#define SCIPallocClearMemoryArray(scip, ptr, num)
Definition: scip_mem.h:74
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool *initialized, SCIP_Bool *complete)
Definition: matrix.c:437
#define SCIPdebugMsg
Definition: scip_message.h:88
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
public methods for numerical tolerances
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1455
int SCIPgetNConshdlrs(SCIP *scip)
Definition: scip_cons.c:978
SCIP_Real * rowmatval
Definition: struct_matrix.h:52
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17354
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1489
public methods for managing constraints
Constraint handler for knapsack constraints of the form , x binary and .
SCIP_VAR * SCIPgetIntvarLinking(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1315
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4191
SCIP_CONSHDLR ** SCIPgetConshdlrs(SCIP *scip)
Definition: scip_cons.c:967
SCIP_Real * ub
Definition: struct_matrix.h:46
int * nuplocks
Definition: struct_matrix.h:47
static SCIP_RETCODE calcActivityBounds(SCIP *scip, SCIP_MATRIX *matrix)
Definition: matrix.c:351
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
#define SCIPallocBuffer(scip, ptr)
Definition: scip_mem.h:128
SCIP_Real * lhs
Definition: struct_matrix.h:58
int SCIPmatrixGetRowNMaxActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1595
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:143
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8076
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1443
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16730
int * rowmatind
Definition: struct_matrix.h:53
const char * SCIPmatrixGetRowName(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1467
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
int SCIPmatrixGetRowNMaxActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1583
const char * SCIPmatrixGetColName(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1419
int * colmatind
Definition: struct_matrix.h:41
#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
SCIP_Real SCIPmatrixGetColLb(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1372
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1431
SCIP_Real SCIPmatrixGetColUb(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1361
SCIP_Bool SCIPmatrixDownlockConflict(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1631
public methods for constraint handler plugins and constraints
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
#define SCIP_Bool
Definition: def.h:69
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9294
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1327
SCIP_Bool * isrhsinfinite
Definition: struct_matrix.h:63
SCIP_VAR ** vars
Definition: struct_matrix.h:50
Constraint handler for linear constraints in their most general form, .
int SCIPmatrixGetRowNMinActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1559
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
data structure for MIP matrix
public methods for matrix
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9273
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2044
int * colmatbeg
Definition: struct_matrix.h:42
int * rowmatbeg
Definition: struct_matrix.h:54
SCIP_Real * lb
Definition: struct_matrix.h:45
SCIP_Real * r
Definition: circlepacking.c:50
methods for sorting joint arrays of various types
general public methods
#define SCIPfreeBuffer(scip, ptr)
Definition: scip_mem.h:140
SCIP_Real * rhs
Definition: struct_matrix.h:59
static SCIP_RETCODE setColumnMajorFormat(SCIP *scip, SCIP_MATRIX *matrix)
Definition: matrix.c:284
static const SCIP_Real scalars[]
Definition: lp.c:5650
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1501
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_CONS ** SCIPconshdlrGetCheckConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4583
SCIP_RETCODE SCIPgetBinvarsLinking(SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***binvars, int *nbinvars)
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3094
SCIP_Bool SCIPmatrixIsRowRhsInfinity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1513
SCIP_Real * minactivity
Definition: struct_matrix.h:65
public methods for message output
int * maxactivityposinf
Definition: struct_matrix.h:70
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1999
#define SCIP_Real
Definition: def.h:157
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:738
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4613
public methods for message handling
SCIP_Real SCIPmatrixGetRowMinActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1535
SCIP_Bool SCIPmatrixUplockConflict(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1619
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1395
SCIP_CONS ** cons
Definition: struct_matrix.h:61
#define SCIP_Longint
Definition: def.h:142
int SCIPmatrixGetNNonzs(SCIP_MATRIX *matrix)
Definition: matrix.c:1525
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int SCIPmatrixGetRowNMinActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1571
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE addRow(SCIP *scip, SCIP_MATRIX *matrix, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real lhs, SCIP_Real rhs, int maxnnonzsmem, SCIP_Bool *rowadded)
Definition: matrix.c:89
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1383
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:119
int * rowmatcnt
Definition: struct_matrix.h:55
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE getActiveVariables(SCIP *scip, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant)
Definition: matrix.c:54
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
public methods for global and local (sub)problems
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1351
int * ndownlocks
Definition: struct_matrix.h:48
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:134
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1339
memory allocation routines