SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-2023 Zuse Institute Berlin (ZIB) */
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
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 */
66static
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);
80 assert(*vars != NULL);
81 assert(*scalars != NULL);
82 assert(nvars != NULL);
83 assert(constant != NULL);
84
86
87 if( requiredsize > *nvars )
88 {
91
92 /* call function a second time with enough memory */
95 }
96
97 return SCIP_OKAY;
98}
99
100/** add one row to the constraint matrix */
101static
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;
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) )
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 */
219static
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{
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
257 activeconstant = 0.0;
258
259 /* duplicate variable and value array */
261 if( vals != NULL )
262 {
264 }
265 else
266 {
268
269 for( v = 0; v < nactivevars; v++ )
270 activevals[v] = 1.0;
271 }
272
273 /* retransform given variables to active variables */
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 {
286 }
287
288 /* free buffer arrays */
291
292 return SCIP_OKAY;
293}
294
295/** transform row major format into column major format */
296static
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
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 {
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
358
359 return SCIP_OKAY;
360}
361
362/** calculate min/max activity per row */
363static
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);
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 */
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
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 */
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
586 if( *infeasible )
587 return SCIP_OKAY;
588
589 SCIP_CALL( SCIPcleanupConssLinear(scip, TRUE, infeasible) );
590 if( *infeasible )
591 return SCIP_OKAY;
592
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 {
603 }
604
605 /* do nothing if we have no entries */
606 if( nnonzstmp == 0 )
607 return SCIP_OKAY;
608
609 /* build the matrix structure */
611 matrix = *matrixptr;
612
613 /* copy vars array and set number of variables */
615 matrix->ncols = nvars;
616
617 matrix->nrows = 0;
618 matrix->nnonzs = 0;
619
620 /* allocate memory */
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 */
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) );
652 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->minactivity, nconss) );
653 SCIP_CALL( SCIPallocBufferArray(scip, &matrix->maxactivity, 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 {
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]);
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];
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
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];
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
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];
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
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;
796
797 for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
798 {
799 SCIP_Longint* weights;
800
801 cons = conshdlrconss[c];
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);
817
818 if( nvars > valssize )
819 {
820 valssize = (int) (1.5 * nvars);
822 }
823
824 for( v = 0; v < nvars; v++ )
825 consvals[v] = (SCIP_Real)weights[v];
826
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
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) );
851 consvals[0] = 1.0;
852
853 for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
854 {
855 cons = conshdlrconss[c];
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
873
874 SCIP_CALL( addConstraint(scip, matrix, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons),
876
877 if(rowadded)
878 {
879 assert(cnt < nconss);
880 matrix->cons[cnt] = cons;
881 cnt++;
882 }
883 }
884
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;
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) );
909
910 for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
911 {
912 cons = conshdlrconss[c];
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) );
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) );
938 }
939
940 /* copy vars and vals for binary variables */
941 for( j = 0; j < nconsvars - 1; j++ )
942 {
943 consvars[j] = curconsvars[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
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 {
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 */
998
999 /* transform row major format into column major format */
1001
1002 *initialized = TRUE;
1003 }
1004 else
1005 {
1012
1014 SCIPfreeBufferArray(scip, &matrix->cons);
1015
1016 SCIPfreeBufferArray(scip, &matrix->rhs);
1017 SCIPfreeBufferArray(scip, &matrix->lhs);
1022
1025 SCIPfreeBufferArray(scip, &matrix->ub);
1026 SCIPfreeBufferArray(scip, &matrix->lb);
1032
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
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
1219 SCIP_CALL( SCIPallocBufferArray(scip, &values, matrix->nrows) );
1222
1223 /* init */
1224 BMSclearMemoryArray(scale, 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 {
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 {
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);
1313
1316 }
1317
1318 if( t == k - startk )
1319 break;
1320 }
1321
1322 if( k == matrix->colmatcnt[c] )
1323 break;
1324 }
1325 }
1326
1329 SCIPfreeBufferArray(scip, &values);
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
1377 SCIP_CALL( SCIPallocBufferArray(scip, &values, matrix->ncols) );
1380
1381 /* init */
1382 BMSclearMemoryArray(scale, 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 {
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 {
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);
1474
1477 }
1478
1479 if( t == k - startk )
1480 break;
1481 }
1482
1483 if( k == matrix->rowmatcnt[r] )
1484 break;
1485 }
1486 }
1487 }
1488
1491 SCIPfreeBufferArray(scip, &values);
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}
Constraint handler for knapsack constraints of the form , x binary and .
Constraint handler for linear constraints in their most general form, .
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
Constraint handler for the set partitioning / packing / covering constraints .
Constraint handler for variable bound constraints .
#define SCIP_UNUSED(x)
Definition def.h:442
#define SCIP_Real
Definition def.h:186
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIP_CALL(x)
Definition def.h:388
SCIP_RETCODE SCIPgetBinvarsLinking(SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***binvars, int *nbinvars)
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcleanupConssSetppc(SCIP *scip, SCIP_Bool onlychecked, SCIP_Bool *infeasible, int *naddconss, int *ndelconss, int *nchgcoefs, int *nfixedvars)
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcleanupConssKnapsack(SCIP *scip, SCIP_Bool onlychecked, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPcleanupConssVarbound(SCIP *scip, SCIP_Bool onlychecked, SCIP_Bool *infeasible, int *naddconss, int *ndelconss, int *nchgbds)
SCIP_RETCODE SCIPcleanupConssLogicor(SCIP *scip, SCIP_Bool onlychecked, int *naddconss, int *ndelconss, int *nchgcoefs)
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcleanupConssLinear(SCIP *scip, SCIP_Bool onlychecked, SCIP_Bool *infeasible)
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real * SCIPgetValsLinking(SCIP *scip, SCIP_CONS *cons)
@ SCIP_SETPPCTYPE_PARTITIONING
Definition cons_setppc.h:87
@ SCIP_SETPPCTYPE_COVERING
Definition cons_setppc.h:89
@ SCIP_SETPPCTYPE_PACKING
Definition cons_setppc.h:88
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
int SCIPgetNConss(SCIP *scip)
Definition scip_prob.c:3042
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
#define SCIPdebugMsg
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4615
SCIP_CONS ** SCIPconshdlrGetCheckConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4572
int SCIPgetNConshdlrs(SCIP *scip)
Definition scip_cons.c:910
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4180
SCIP_CONSHDLR ** SCIPgetConshdlrs(SCIP *scip)
Definition scip_cons.c:899
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition cons.c:8397
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8088
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition cons.c:8337
#define SCIPfreeBuffer(scip, ptr)
Definition scip_mem.h:134
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition scip_mem.h:128
#define SCIPallocClearMemoryArray(scip, ptr, num)
Definition scip_mem.h:66
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPfreeMemoryArray(scip, ptr)
Definition scip_mem.h:80
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition scip_mem.h:132
#define SCIPallocBuffer(scip, ptr)
Definition scip_mem.h:122
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition scip_mem.h:137
int SCIPgetNActivePricers(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
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:1738
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3353
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:17910
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17590
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:17900
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3295
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortIntIntReal(int *intarray1, int *intarray2, SCIP_Real *realarray, int len)
return SCIP_OKAY
int c
int r
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
static const SCIP_Real scalars[]
Definition lp.c:5743
#define NULL
Definition lpi_spx1.cpp:161
SCIP_Bool SCIPmatrixUplockConflict(SCIP_MATRIX *matrix, int col)
Definition matrix.c:1841
int SCIPmatrixGetRowNMinActNegInf(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1781
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition matrix.c:1549
int SCIPmatrixGetNNonzs(SCIP_MATRIX *matrix)
Definition matrix.c:1747
static SCIP_RETCODE setColumnMajorFormat(SCIP *scip, SCIP_MATRIX *matrix)
Definition matrix.c:297
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1677
const char * SCIPmatrixGetRowName(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1689
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition matrix.c:1617
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition matrix.c:1561
SCIP_Bool SCIPmatrixIsRowRhsInfinity(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1735
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition matrix.c:1605
SCIP_Real SCIPmatrixGetRowMaxActivity(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1769
static SCIP_RETCODE calcActivityBounds(SCIP *scip, SCIP_MATRIX *matrix)
Definition matrix.c:364
SCIP_Real SCIPmatrixGetColLb(SCIP_MATRIX *matrix, int col)
Definition matrix.c:1594
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1711
const char * SCIPmatrixGetColName(SCIP_MATRIX *matrix, int col)
Definition matrix.c:1641
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1653
SCIP_Bool SCIPmatrixDownlockConflict(SCIP_MATRIX *matrix, int col)
Definition matrix.c:1853
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
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1723
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
Definition matrix.c:1537
int SCIPmatrixGetRowNMinActPosInf(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1793
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
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition matrix.c:1573
SCIP_Real SCIPmatrixGetRowMinActivity(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1757
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1829
SCIP_RETCODE SCIPmatrixGetParallelRows(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real *scale, int *pclass)
Definition matrix.c:1183
static SCIP_RETCODE getActiveVariables(SCIP *scip, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant)
Definition matrix.c:67
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition matrix.c:1041
int SCIPmatrixGetRowNMaxActPosInf(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1817
int SCIPmatrixGetRowNMaxActNegInf(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1805
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition matrix.c:1629
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1665
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
void SCIPmatrixPrintRow(SCIP *scip, SCIP_MATRIX *matrix, int row)
Definition matrix.c:1104
SCIP_RETCODE SCIPmatrixGetParallelCols(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real *scale, int *pclass, SCIP_Bool *varineq)
Definition matrix.c:1339
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition matrix.c:1701
void SCIPmatrixRemoveColumnBounds(SCIP *scip, SCIP_MATRIX *matrix, int col)
Definition matrix.c:1138
SCIP_Real SCIPmatrixGetColUb(SCIP_MATRIX *matrix, int col)
Definition matrix.c:1583
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:132
public methods for managing constraints
public methods for matrix
public methods for message output
methods for sorting joint arrays of various types
public methods for problem variables
public methods for constraint handler plugins and constraints
general public methods
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for variable pricer plugins
public methods for global and local (sub)problems
public methods for SCIP variables
SCIP_Real * lb
SCIP_Bool * isrhsinfinite
int * maxactivityneginf
SCIP_VAR ** vars
int * minactivityposinf
SCIP_Real * lhs
SCIP_Real * minactivity
SCIP_Real * colmatval
SCIP_CONS ** cons
SCIP_Real * maxactivity
int * maxactivityposinf
SCIP_Real * rowmatval
SCIP_Real * rhs
int * minactivityneginf
SCIP_Real * ub
data structure for MIP matrix
@ SCIP_ERROR
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_LOCKTYPE_MODEL
Definition type_var.h:97