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