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