Scippy

SCIP

Solving Constraint Integer Programs

lp.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-2024 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 lp.c
26 * @ingroup OTHER_CFILES
27 * @brief LP management methods and data structures
28 * @author Tobias Achterberg
29 * @author Timo Berthold
30 * @author Marc Pfetsch
31 * @author Kati Wolter
32 * @author Gerald Gamrath
33 *
34 * In LP management, we have to differ between the current LP and the SCIP_LP
35 * stored in the LP solver. All LP methods affect the current LP only.
36 * Before solving the current LP with the LP solver or setting an LP state,
37 * the LP solvers data has to be updated to the current LP with a call to
38 * lpFlush().
39 */
40
41/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
42
43
44#include "lpi/lpi.h"
45#include "scip/clock.h"
46#include "scip/cons.h"
47#include "scip/event.h"
48#include "scip/intervalarith.h"
49#include "scip/lp.h"
50#include "scip/misc.h"
51#include "scip/prob.h"
52#include "scip/pub_lp.h"
53#include "scip/pub_message.h"
54#include "scip/pub_misc.h"
55#include "scip/pub_misc_sort.h"
56#include "scip/pub_var.h"
57#include "scip/set.h"
58#include "scip/sol.h"
59#include "scip/solve.h"
60#include "scip/stat.h"
61#include "scip/struct_event.h"
62#include "scip/struct_lp.h"
63#include "scip/struct_prob.h"
64#include "scip/struct_set.h"
65#include "scip/struct_stat.h"
66#include "scip/struct_var.h"
67#include "scip/var.h"
68#include <string.h>
69
70
71/* activate this to use the row activities as given by the LPI instead of recalculating
72 * using the LP solver activity is potentially faster, but may not be consistent with the SCIP_ROW calculations
73 * see also #2594 for more details on possible trouble
74 */
75/* #define SCIP_USE_LPSOLVER_ACTIVITY */
76
77/*
78 * debug messages
79 */
80
81#ifdef SCIP_DEBUG
82/** method is to print in row in case SCIP_DEBUG is defined */
83static
84void debugRowPrint(
85 SCIP_SET* set, /**< global SCIP settings */
86 SCIP_ROW* row /**< LP row */
87 )
88{
89 int i;
90
91 assert(row != NULL);
92
93 /* print row name */
94 if( row->name != NULL && row->name[0] != '\0' )
95 {
96 SCIPsetDebugMsgPrint(set, "%s: ", row->name);
97 }
98
99 /* print left hand side */
100 SCIPsetDebugMsgPrint(set, "%.15g <= ", row->lhs);
101
102 /* print coefficients */
103 if( row->len == 0 )
104 {
106 }
107 for( i = 0; i < row->len; ++i )
108 {
109 assert(row->cols[i] != NULL);
110 assert(row->cols[i]->var != NULL);
111 assert(SCIPvarGetName(row->cols[i]->var) != NULL);
112 assert(SCIPvarGetStatus(row->cols[i]->var) == SCIP_VARSTATUS_COLUMN);
113 SCIPsetDebugMsgPrint(set, "%+.15g<%s> ", row->vals[i], SCIPvarGetName(row->cols[i]->var));
114 }
115
116 /* print constant */
118 {
119 SCIPsetDebugMsgPrint(set, "%+.15g ", row->constant);
120 }
121
122 /* print right hand side */
123 SCIPsetDebugMsgPrint(set, "<= %.15g\n", row->rhs);
124}
125#else
126#define debugRowPrint(x,y) /**/
127#endif
128
129#ifdef SCIP_DEBUG
130/** method to output column if SCIP_DEBUG is define */
131static
132void debugColPrint(
133 SCIP_SET* set, /**< global SCIP settings */
134 SCIP_COL* col /**< LP column */
135 )
136{
137 int r;
138
139 assert(col != NULL);
140 assert(col->var != NULL);
141
142 /* print bounds */
143 SCIPsetDebugMsgPrint(set, "(obj: %.15g) [%.15g,%.15g], ", col->obj, col->lb, col->ub);
144
145 /* print coefficients */
146 if( col->len == 0 )
147 {
148 SCIPsetDebugMsgPrint(set, "<empty>");
149 }
150 for( r = 0; r < col->len; ++r )
151 {
152 assert(col->rows[r] != NULL);
153 assert(col->rows[r]->name != NULL);
154 SCIPsetDebugMsgPrint(set, "%+.15g<%s> ", col->vals[r], col->rows[r]->name);
155 }
157}
158#else
159#define debugColPrint(x,y) /**/
160#endif
161
162/*
163 * memory growing methods for dynamically allocated arrays
164 */
165
166/** ensures, that chgcols array can store at least num entries */
167static
169 SCIP_LP* lp, /**< current LP data */
170 SCIP_SET* set, /**< global SCIP settings */
171 int num /**< minimum number of entries to store */
172 )
173{
174 assert(lp->nchgcols <= lp->chgcolssize);
175
176 if( num > lp->chgcolssize )
177 {
178 int newsize;
179
180 newsize = SCIPsetCalcMemGrowSize(set, num);
181 SCIP_ALLOC( BMSreallocMemoryArray(&lp->chgcols, newsize) );
182 lp->chgcolssize = newsize;
183 }
184 assert(num <= lp->chgcolssize);
185
186 return SCIP_OKAY;
187}
188
189/** ensures, that chgrows array can store at least num entries */
190static
192 SCIP_LP* lp, /**< current LP data */
193 SCIP_SET* set, /**< global SCIP settings */
194 int num /**< minimum number of entries to store */
195 )
196{
197 assert(lp->nchgrows <= lp->chgrowssize);
198
199 if( num > lp->chgrowssize )
200 {
201 int newsize;
202
203 newsize = SCIPsetCalcMemGrowSize(set, num);
204 SCIP_ALLOC( BMSreallocMemoryArray(&lp->chgrows, newsize) );
205 lp->chgrowssize = newsize;
206 }
207 assert(num <= lp->chgrowssize);
208
209 return SCIP_OKAY;
210}
211
212/** ensures, that lpicols array can store at least num entries */
213static
215 SCIP_LP* lp, /**< current LP data */
216 SCIP_SET* set, /**< global SCIP settings */
217 int num /**< minimum number of entries to store */
218 )
219{
220 assert(lp->nlpicols <= lp->lpicolssize);
221
222 if( num > lp->lpicolssize )
223 {
224 int newsize;
225
226 newsize = SCIPsetCalcMemGrowSize(set, num);
227 SCIP_ALLOC( BMSreallocMemoryArray(&lp->lpicols, newsize) );
228 lp->lpicolssize = newsize;
229 }
230 assert(num <= lp->lpicolssize);
231
232 return SCIP_OKAY;
233}
234
235/** ensures, that lpirows array can store at least num entries */
236static
238 SCIP_LP* lp, /**< current LP data */
239 SCIP_SET* set, /**< global SCIP settings */
240 int num /**< minimum number of entries to store */
241 )
242{
243 assert(lp->nlpirows <= lp->lpirowssize);
244
245 if( num > lp->lpirowssize )
246 {
247 int newsize;
248
249 newsize = SCIPsetCalcMemGrowSize(set, num);
250 SCIP_ALLOC( BMSreallocMemoryArray(&lp->lpirows, newsize) );
251 lp->lpirowssize = newsize;
252 }
253 assert(num <= lp->lpirowssize);
254
255 return SCIP_OKAY;
256}
257
258/** ensures, that cols array can store at least num entries */
259static
261 SCIP_LP* lp, /**< current LP data */
262 SCIP_SET* set, /**< global SCIP settings */
263 int num /**< minimum number of entries to store */
264 )
265{
266 assert(lp->ncols <= lp->colssize);
267
268 if( num > lp->colssize )
269 {
270 int newsize;
271
272 newsize = SCIPsetCalcMemGrowSize(set, num);
273 SCIP_ALLOC( BMSreallocMemoryArray(&lp->cols, newsize) );
274 lp->colssize = newsize;
275 }
276 assert(num <= lp->colssize);
277
278 return SCIP_OKAY;
279}
280
281/** ensures, that soldirection array can store at least num entries */
282static
284 SCIP_LP* lp, /**< current LP data */
285 int num /**< minimum number of entries to store */
286 )
287{
288 if( num > lp->soldirectionsize )
289 {
292
293 lp->soldirectionsize = num;
294 }
295
296 assert(num <= lp->soldirectionsize);
297
298 return SCIP_OKAY;
299}
300
301/** ensures, that lazy cols array can store at least num entries */
302static
304 SCIP_LP* lp, /**< current LP data */
305 SCIP_SET* set, /**< global SCIP settings */
306 int num /**< minimum number of entries to store */
307 )
308{
309 assert(lp->nlazycols <= lp->lazycolssize);
310
311 if( num > lp->lazycolssize )
312 {
313 int newsize;
314
315 newsize = SCIPsetCalcMemGrowSize(set, num);
316 SCIP_ALLOC( BMSreallocMemoryArray(&lp->lazycols, newsize) );
317 lp->lazycolssize = newsize;
318 }
319 assert(num <= lp->lazycolssize);
320
321 return SCIP_OKAY;
322}
323
324/** ensures, that rows array can store at least num entries */
325static
327 SCIP_LP* lp, /**< current LP data */
328 SCIP_SET* set, /**< global SCIP settings */
329 int num /**< minimum number of entries to store */
330 )
331{
332 assert(lp->nrows <= lp->rowssize);
333
334 if( num > lp->rowssize )
335 {
336 int newsize;
337
338 newsize = SCIPsetCalcMemGrowSize(set, num);
339 SCIP_ALLOC( BMSreallocMemoryArray(&lp->rows, newsize) );
340 lp->rowssize = newsize;
341 }
342 assert(num <= lp->rowssize);
343
344 return SCIP_OKAY;
345}
346
347/** ensures, that row array of column can store at least num entries */
348static
350 SCIP_COL* col, /**< LP column */
351 BMS_BLKMEM* blkmem, /**< block memory */
352 SCIP_SET* set, /**< global SCIP settings */
353 int num /**< minimum number of entries to store */
354 )
355{
356 assert(col != NULL);
357 assert(col->len <= col->size);
358
359 if( num > col->size )
360 {
361 int newsize;
362
363 newsize = SCIPsetCalcMemGrowSize(set, num);
364 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &col->rows, col->size, newsize) );
365 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &col->vals, col->size, newsize) );
366 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &col->linkpos, col->size, newsize) );
367 col->size = newsize;
368 }
369 assert(num <= col->size);
370
371 return SCIP_OKAY;
372}
373
374/** save current LP values dependent on the solution */
375static
377 SCIP_LP* lp, /**< LP data */
378 SCIP_STAT* stat, /**< problem statistics */
379 BMS_BLKMEM* blkmem /**< block memory */
380 )
381{
382 SCIP_LPSOLVALS* storedsolvals;
383
384 assert(lp != NULL);
385 assert(stat != NULL);
386 assert(blkmem != NULL);
387
388 /* allocate memory for storage */
389 if( lp->storedsolvals == NULL )
390 {
392 }
393 storedsolvals = lp->storedsolvals;
394
395 /* store values */
396 storedsolvals->lpsolstat = lp->lpsolstat;
397 storedsolvals->lpobjval = lp->lpobjval;
398 storedsolvals->primalfeasible = lp->primalfeasible;
399 storedsolvals->primalchecked = lp->primalchecked;
400 storedsolvals->dualfeasible = lp->dualfeasible;
401 storedsolvals->dualchecked = lp->dualchecked;
402 storedsolvals->solisbasic = lp->solisbasic;
403 storedsolvals->lpissolved = lp->solved;
404
405 return SCIP_OKAY;
406}
407
408/** restore LP solution values in column */
409static
411 SCIP_LP* lp, /**< LP data */
412 BMS_BLKMEM* blkmem, /**< block memory */
413 SCIP_Longint validlp /**< number of lp for which restored values are valid */
414 )
415{
416 SCIP_LPSOLVALS* storedsolvals;
417
418 assert(lp != NULL);
419 assert(blkmem != NULL);
420
421 /* if stored values are available, restore them */
422 storedsolvals = lp->storedsolvals;
423 if( storedsolvals != NULL )
424 {
425 lp->solved = storedsolvals->lpissolved;
426 lp->validsollp = validlp;
427
428 lp->lpsolstat = storedsolvals->lpsolstat;
429 lp->lpobjval = storedsolvals->lpobjval;
430 lp->primalfeasible = storedsolvals->primalfeasible;
431 lp->primalchecked = storedsolvals->primalchecked;
432 lp->dualfeasible = storedsolvals->dualfeasible;
433 lp->dualchecked = storedsolvals->dualchecked;
434 lp->solisbasic = storedsolvals->solisbasic;
435
436 /* solution values are stored only for LPs solved to optimality or unboundedness */
437 assert(lp->lpsolstat == SCIP_LPSOLSTAT_OPTIMAL ||
443 lp->validsollp == -1);
444 }
445 /* no values available, mark LP as unsolved */
446 else
447 {
448 lp->solved = FALSE;
449 lp->validsollp = -1;
450
453 lp->primalfeasible = FALSE;
454 lp->primalchecked = FALSE;
455 lp->dualfeasible = FALSE;
456 lp->dualchecked = FALSE;
457 lp->solisbasic = FALSE;
458 lp->validfarkaslp = -1;
459 }
460
461 lp->validdegeneracylp = -1;
462
463 /* intentionally keep storage space allocated */
464
465 return SCIP_OKAY;
466}
467
468/** save current LP solution values stored in each column */
469static
471 SCIP_COL* col, /**< LP column */
472 BMS_BLKMEM* blkmem /**< block memory */
473 )
474{
475 SCIP_COLSOLVALS* storedsolvals;
476
477 assert(col != NULL);
478 assert(blkmem != NULL);
479
480 /* allocate memory for storage */
481 if( col->storedsolvals == NULL )
482 {
484 }
485 storedsolvals = col->storedsolvals;
486
487 /* store values */
488 storedsolvals->primsol = col->primsol;
489 storedsolvals->redcost = col->redcost;
490 storedsolvals->basisstatus = col->basisstatus; /*lint !e641 !e732*/
491
492 return SCIP_OKAY;
493}
494
495/** restore LP solution values in column */
496static
498 SCIP_COL* col, /**< LP column */
499 BMS_BLKMEM* blkmem, /**< block memory */
500 SCIP_Longint validlp, /**< number of lp for which restored values are valid */
501 SCIP_Bool freebuffer /**< should buffer for LP solution values be freed? */
502 )
503{
504 SCIP_COLSOLVALS* storedsolvals;
505
506 assert(col != NULL);
507 assert(blkmem != NULL);
508
509 /* if stored values are available, restore them */
510 storedsolvals = col->storedsolvals;
511 if( storedsolvals != NULL )
512 {
513 col->primsol = storedsolvals->primsol;
514 col->redcost = storedsolvals->redcost;
515 col->validredcostlp = validlp;
516 col->basisstatus = storedsolvals->basisstatus; /*lint !e641 !e732*/
517
518 /* we do not save the farkas coefficient, since it can be recomputed; thus, we invalidate it here */
519 col->validfarkaslp = -1;
520 }
521 /* if the column was created after performing the storage (possibly during probing), we treat it as implicitly zero;
522 * we make sure to invalidate the reduced cost and farkas coefficient, which are not available
523 */
524 else
525 {
526 col->primsol = 0.0;
527 col->validredcostlp = -1;
528 col->validfarkaslp = -1;
529 col->basisstatus = SCIP_BASESTAT_ZERO; /*lint !e641*/
530 }
531
532 /* free memory */
533 if( freebuffer )
534 {
536 assert(col->storedsolvals == NULL);
537 }
538
539 return SCIP_OKAY;
540}
541
542/** save current LP solution values stored in each column */
543static
545 SCIP_ROW* row, /**< LP row */
546 BMS_BLKMEM* blkmem, /**< block memory */
547 SCIP_Bool infeasible /**< is the solution infeasible? */
548 )
549{
550 SCIP_ROWSOLVALS* storedsolvals;
551
552 assert(row != NULL);
553 assert(blkmem != NULL);
554
555 /* allocate memory for storage */
556 if( row->storedsolvals == NULL )
557 {
559 }
560 storedsolvals = row->storedsolvals;
561
562 /* store values */
563 if ( infeasible )
564 {
565 storedsolvals->dualsol = row->dualfarkas;
566 storedsolvals->activity = SCIP_INVALID;
567 storedsolvals->basisstatus = SCIP_BASESTAT_BASIC; /*lint !e641*/
568 }
569 else
570 {
571 storedsolvals->dualsol = row->dualsol;
572 storedsolvals->activity = row->activity;
573 storedsolvals->basisstatus = row->basisstatus; /*lint !e641 !e732*/
574 }
575
576 return SCIP_OKAY;
577}
578
579/** restore LP solution values in row */
580static
582 SCIP_ROW* row, /**< LP column */
583 BMS_BLKMEM* blkmem, /**< block memory */
584 SCIP_Longint validlp, /**< number of lp for which restored values are valid */
585 SCIP_Bool freebuffer, /**< should buffer for LP solution values be freed? */
586 SCIP_Bool infeasible /**< is the solution infeasible? */
587 )
588{
589 SCIP_ROWSOLVALS* storedsolvals;
590
591 assert(row != NULL);
592 assert(blkmem != NULL);
593
594 /* if stored values are available, restore them */
595 storedsolvals = row->storedsolvals;
596 if( storedsolvals != NULL )
597 {
598 if ( infeasible )
599 row->dualfarkas = storedsolvals->dualsol;
600 else
601 row->dualsol = storedsolvals->dualsol;
602 row->activity = storedsolvals->activity;
603 row->validactivitylp = validlp;
604 row->basisstatus = storedsolvals->basisstatus; /*lint !e641 !e732*/
605 }
606 /* if the row was created after performing the storage (possibly during probing), we treat it as basic;
607 * we make sure to invalidate the reduced cost and farkas coefficient, which are not available
608 */
609 else
610 {
611 row->dualsol = 0.0;
612 row->dualfarkas = 0.0;
613 row->activity = SCIP_INVALID;
614 row->validactivitylp = -1;
615 row->basisstatus = SCIP_BASESTAT_BASIC; /*lint !e641*/
616 }
617
618 /* free memory */
619 if( freebuffer )
620 {
622 assert(row->storedsolvals == NULL);
623 }
624
625 return SCIP_OKAY;
626}
627
628/** ensures, that column array of row can store at least num entries */
630 SCIP_ROW* row, /**< LP row */
631 BMS_BLKMEM* blkmem, /**< block memory */
632 SCIP_SET* set, /**< global SCIP settings */
633 int num /**< minimum number of entries to store */
634 )
635{
636 assert(row != NULL);
637 assert(row->len <= row->size);
638
639 if( num > row->size )
640 {
641 int newsize;
642
643 newsize = SCIPsetCalcMemGrowSize(set, num);
644 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &row->cols, row->size, newsize) );
645 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &row->cols_index, row->size, newsize) );
646 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &row->vals, row->size, newsize) );
647 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &row->linkpos, row->size, newsize) );
648 row->size = newsize;
649 }
650 assert(num <= row->size);
651
652 return SCIP_OKAY;
653}
654
655
656#ifdef SCIP_MORE_DEBUG /* enable this to check the sortings within rows (for debugging, very slow!) */
657static SCIP_Bool msgdisp_checkrow = FALSE;
658
659static
660void checkRow(
661 SCIP_ROW* row
662 )
663{
664 int i;
665
666 if( !msgdisp_checkrow )
667 {
668 printf("LP ROW CHECKING ACTIVATED! THIS IS VERY SLOW!\n");
669 msgdisp_checkrow = TRUE;
670 }
671
672 /* validate sorting of LP part of row */
673 if( row->lpcolssorted && row->nlpcols > 0)
674 {
675 assert(row->cols_index[0] == row->cols[0]->index);
676 for( i = 1; i < row->nlpcols; ++i )
677 {
678 assert(row->cols_index[i] == row->cols[i]->index);
679 assert(row->cols_index[i] >= row->cols_index[i-1]);
680 }
681 }
682
683 /* validate sorting of non-LP part of row */
684 if( row->nonlpcolssorted && row->len > row->nlpcols )
685 {
686 assert(row->cols_index[row->nlpcols] == row->cols[row->nlpcols]->index);
687 for( i = row->nlpcols + 1; i < row->len; ++i )
688 {
689 assert(row->cols_index[i] == row->cols[i]->index);
690 assert(row->cols_index[i] >= row->cols_index[i-1]);
691 }
692 }
693}
694#else
695#define checkRow(row) /**/
696#endif
697
698#ifdef SCIP_MORE_DEBUG /* enable this to check norms of rows (for debugging, very slow!) */
699static
700void checkRowSqrnorm(
701 SCIP_ROW* row
702 )
703{
704 SCIP_COL** cols;
705 SCIP_Real sqrnorm;
706 int c;
707
708 cols = row->cols;
709 assert(cols != NULL || row->len == 0);
710
711 sqrnorm = 0.0;
712
713 for( c = row->len - 1; c >= 0; --c )
714 {
715 if( cols[c]->lppos >= 0 )
716 sqrnorm += SQR(row->vals[c]);
717 }
718
719 assert(ABS(sqrnorm - row->sqrnorm) < 1e-06 * MAX(1.0,sqrnorm));
720}
721
722static
723void checkRowSumnorm(
724 SCIP_ROW* row
725 )
726{
727 SCIP_COL** cols;
728 SCIP_Real sumnorm;
729 int c;
730
731 cols = row->cols;
732 assert(cols != NULL || row->len == 0);
733
734 sumnorm = 0.0;
735
736 for( c = row->len - 1; c >= 0; --c )
737 {
738 if( cols[c]->lppos >= 0 )
739 sumnorm += REALABS(row->vals[c]);
740 }
741
742 assert(ABS(sumnorm - row->sumnorm) < 1e-06 * MAX(1.0,sumnorm));
743}
744
745static
746void checkRowObjprod(
747 SCIP_ROW* row
748 )
749{
750 SCIP_COL** cols;
751 SCIP_Real objprod;
752 int c;
753
754 cols = row->cols;
755 assert(cols != NULL || row->len == 0);
756
757 objprod = 0.0;
758
759 for( c = row->len - 1; c >= 0; --c )
760 {
761 if( cols[c]->lppos >= 0 )
762 objprod += row->vals[c] * cols[c]->unchangedobj;
763 }
764
765 assert(ABS(objprod - row->objprod) < 1e-06 * MAX(1.0,objprod));
766}
767#else
768#define checkRowSqrnorm(row) /**/
769#define checkRowSumnorm(row) /**/
770#define checkRowObjprod(row) /**/
771#endif
772
773/*
774 * Local methods for pseudo and loose objective values
775 */
776
777/* recompute the loose objective value from scratch, if it was marked to be unreliable before */
778static
780 SCIP_LP* lp, /**< current LP data */
781 SCIP_SET* set, /**< global SCIP settings */
782 SCIP_PROB* prob /**< problem data */
783 )
784{
785 SCIP_VAR** vars;
786 SCIP_Real obj;
787 int nvars;
788 int v;
789
790 assert(lp != NULL);
791 assert(set != NULL);
792 assert(prob != NULL);
793 assert(!lp->looseobjvalid);
794
795 vars = prob->vars;
796 nvars = prob->nvars;
797 lp->looseobjval = 0.0;
798
799 /* iterate over all variables in the problem */
800 for( v = 0; v < nvars; ++v )
801 {
802 if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_LOOSE )
803 {
804 obj = SCIPvarGetObj(vars[v]);
805
806 /* we are only interested in variables with a finite impact, because the infinity counters should be correct */
808 lp->looseobjval += obj * SCIPvarGetLbLocal(vars[v]);
809 else if( SCIPsetIsNegative(set, obj) && !SCIPsetIsInfinity(set, SCIPvarGetUbLocal(vars[v])) )
810 lp->looseobjval += obj * SCIPvarGetUbLocal(vars[v]);
811 }
812 }
813
814 /* the recomputed value is reliable */
815 lp->rellooseobjval = lp->looseobjval;
816 lp->looseobjvalid = TRUE;
817}
818
819/* recompute the pseudo solution value from scratch, if it was marked to be unreliable before */
820static
822 SCIP_LP* lp, /**< current LP data */
823 SCIP_SET* set, /**< global SCIP settings */
824 SCIP_PROB* prob /**< problem data */
825 )
826{
827 SCIP_VAR** vars;
828 int nvars;
829 int v;
830
831 assert(lp != NULL);
832 assert(set != NULL);
833 assert(prob != NULL);
834 assert(!lp->pseudoobjvalid);
835
836 vars = prob->vars;
837 nvars = prob->nvars;
838 lp->pseudoobjval = 0.0;
839
840 /* iterate over all variables in the problem */
841 for( v = 0; v < nvars; ++v )
842 {
843 /* we are only interested in variables with a finite impact, because the infinity counters should be correct */
844 if( SCIPsetIsPositive(set, SCIPvarGetObj(vars[v])) &&
846 {
847 lp->pseudoobjval += SCIPvarGetObj(vars[v]) * SCIPvarGetLbLocal(vars[v]);
848 }
849 else if( SCIPsetIsNegative(set, SCIPvarGetObj(vars[v])) &&
851 {
852 lp->pseudoobjval += SCIPvarGetObj(vars[v]) * SCIPvarGetUbLocal(vars[v]);
853 }
854 }
855
856 /* the recomputed value is reliable */
858 lp->pseudoobjvalid = TRUE;
859}
860
861/* recompute the global pseudo solution value from scratch, if it was marked to be unreliable before */
862static
864 SCIP_LP* lp, /**< current LP data */
865 SCIP_SET* set, /**< global SCIP settings */
866 SCIP_PROB* prob /**< problem data */
867 )
868{
869 SCIP_VAR** vars;
870 int nvars;
871 int v;
872
873 assert(lp != NULL);
874 assert(set != NULL);
875 assert(prob != NULL);
876 assert(!lp->glbpseudoobjvalid);
877
878 vars = prob->vars;
879 nvars = prob->nvars;
880 lp->glbpseudoobjval = 0.0;
881
882 /* iterate over all variables in the problem */
883 for( v = 0; v < nvars; ++v )
884 {
885 /* we are only interested in variables with a finite impact, because the infinity counters should be correct */
886 if( SCIPsetIsPositive(set, SCIPvarGetObj(vars[v])) &&
888 {
889 lp->glbpseudoobjval += SCIPvarGetObj(vars[v]) * SCIPvarGetLbGlobal(vars[v]);
890 }
891 else if( SCIPsetIsNegative(set, SCIPvarGetObj(vars[v])) &&
893 {
894 lp->glbpseudoobjval += SCIPvarGetObj(vars[v]) * SCIPvarGetUbGlobal(vars[v]);
895 }
896 }
897
898 /* the recomputed value is reliable */
901}
902
903/** gets finite part of objective value of current LP that results from LOOSE variables only */
904static
906 SCIP_LP* lp, /**< current LP data */
907 SCIP_SET* set, /**< global SCIP settings */
908 SCIP_PROB* prob /**< problem data */
909 )
910{
911 assert(lp != NULL);
912 assert(set != NULL);
913 assert(prob != NULL);
914 assert((lp->nloosevars > 0) || (lp->looseobjvalinf == 0 && lp->looseobjval == 0.0));
915 assert(lp->flushed);
916 assert(lp->looseobjvalinf == 0);
917
918 /* recalculate the loose objective value, if needed */
919 if( !lp->looseobjvalid )
921
922 return lp->looseobjval;
923}
924
925/** gets finite part of pseudo objective value of current LP */
926static
928 SCIP_LP* lp, /**< current LP data */
929 SCIP_SET* set, /**< global SCIP settings */
930 SCIP_PROB* prob /**< problem data */
931 )
932{
933 assert(lp != NULL);
934 assert(set != NULL);
935 assert(prob != NULL);
936
937 /* recalculate the pseudo objective value, if needed */
938 if( !lp->pseudoobjvalid )
940
941 return lp->pseudoobjval;
942}
943
944/*
945 * Sorting and searching rows and columns
946 */
947
948
949/** comparison method for sorting rows by non-decreasing index */
951{
952 assert(elem1 != NULL);
953 assert(elem2 != NULL);
954
955 if( ((SCIP_ROW*)elem1)->index < ((SCIP_ROW*)elem2)->index )
956 return -1;
957 else if( ((SCIP_ROW*)elem1)->index > ((SCIP_ROW*)elem2)->index )
958 return +1;
959 else
960 {
961 assert(SCIProwGetIndex((SCIP_ROW*)(elem1)) == SCIProwGetIndex(((SCIP_ROW*)elem2)));
962 return 0;
963 }
964}
965
966
967/** sorts column entries of linked rows currently in the LP such that lower row indices precede higher ones */
968static
970 SCIP_COL* col /**< column to be sorted */
971 )
972{
973 int i;
974
975 assert(col != NULL);
976
977 /* check, if column is already sorted in the LP part */
978 if( col->lprowssorted )
979 return;
980
981 /* sort coefficients */
982 SCIPsortPtrRealInt((void**)col->rows, col->vals, col->linkpos, SCIProwComp, col->nlprows );
983
984 /* update links */
985 for( i = 0; i < col->nlprows; ++i )
986 {
987 if( col->linkpos[i] >= 0 )
988 {
989 assert(col->rows[i]->cols[col->linkpos[i]] == col);
990 assert(col->rows[i]->linkpos[col->linkpos[i]] >= 0);
991 col->rows[i]->linkpos[col->linkpos[i]] = i;
992 }
993 }
994
995 col->lprowssorted = TRUE;
996}
997
998/** sorts column entries of unlinked rows or rows currently not in the LP such that lower row indices precede higher
999 * ones
1000 */
1001static
1003 SCIP_COL* col /**< column to be sorted */
1004 )
1005{
1006 int i;
1007
1008 assert(col != NULL);
1009
1010 /* check, if column is already sorted in the non-LP part */
1011 if( col->nonlprowssorted )
1012 return;
1013
1014 /* sort coefficients */
1015 SCIPsortPtrRealInt((void**)(&(col->rows[col->nlprows])), &(col->vals[col->nlprows]), &(col->linkpos[col->nlprows]), SCIProwComp, col->len - col->nlprows);
1016
1017 /* update links */
1018 for( i = col->nlprows; i < col->len; ++i )
1019 {
1020 if( col->linkpos[i] >= 0 )
1021 {
1022 assert(col->rows[i]->cols[col->linkpos[i]] == col);
1023 assert(col->rows[i]->linkpos[col->linkpos[i]] >= 0);
1024 col->rows[i]->linkpos[col->linkpos[i]] = i;
1025 }
1026 }
1027
1028 col->nonlprowssorted = TRUE;
1029}
1030
1031/** sorts row entries of linked columns currently in the LP such that lower column indices precede higher ones */
1032static
1034 SCIP_ROW* row /**< row to be sorted */
1035 )
1036{
1037 int i;
1038
1039 assert(row != NULL);
1040
1041 /* check, if row is already sorted in the LP part, or if the sorting should be delayed */
1042 if( row->lpcolssorted || row->delaysort )
1043 return;
1044
1045 /* sort coefficients */
1046 SCIPsortIntPtrIntReal(row->cols_index, (void**)row->cols, row->linkpos, row->vals, row->nlpcols);
1047
1048 /* update links */
1049 for( i = 0; i < row->nlpcols; ++i )
1050 {
1051 if( row->linkpos[i] >= 0 )
1052 {
1053 assert(row->cols[i]->rows[row->linkpos[i]] == row);
1054 assert(row->cols[i]->linkpos[row->linkpos[i]] >= 0);
1055 row->cols[i]->linkpos[row->linkpos[i]] = i;
1056 }
1057 }
1058
1059 row->lpcolssorted = TRUE;
1060}
1061
1062/** sorts row entries of unlinked columns or columns currently not in the LP such that lower column indices precede
1063 * higher ones
1064 */
1065static
1067 SCIP_ROW* row /**< row to be sorted */
1068 )
1069{
1070 int i;
1071
1072 assert(row != NULL);
1073
1074 checkRow(row);
1075
1076 /* check, if row is already sorted in the non-LP part, or if the sorting should be delayed */
1077 if( row->nonlpcolssorted || row->delaysort )
1078 return;
1079
1080 /* sort coefficients */
1081 SCIPsortIntPtrIntReal(&(row->cols_index[row->nlpcols]), (void**)(&(row->cols[row->nlpcols])), &(row->linkpos[row->nlpcols]), &(row->vals[row->nlpcols]), row->len - row->nlpcols);
1082
1083 /* update links */
1084 for( i = row->nlpcols; i < row->len; ++i )
1085 {
1086 if( row->linkpos[i] >= 0 )
1087 {
1088 assert(row->cols[i]->rows[row->linkpos[i]] == row);
1089 assert(row->cols[i]->linkpos[row->linkpos[i]] >= 0);
1090 row->cols[i]->linkpos[row->linkpos[i]] = i;
1091 }
1092 }
1093
1094 checkRow(row);
1095
1096 row->nonlpcolssorted = TRUE;
1097}
1098
1099/** searches coefficient in part of the column, returns position in col vector or -1 if not found */
1100static
1102 SCIP_COL* col, /**< column to be searched in */
1103 const SCIP_ROW* row, /**< coefficient to be searched for */
1104 int minpos, /**< first position of search range */
1105 int maxpos /**< last position of search range */
1106 )
1107{
1108 int pos;
1109 int idx;
1110 int searchidx;
1111
1112 assert(col != NULL);
1113 assert(row != NULL);
1114
1115 /* binary search */
1116 searchidx = row->index;
1117 while(minpos <= maxpos)
1118 {
1119 pos = (minpos + maxpos)/2;
1120 assert(0 <= pos && pos < col->len);
1121 assert(col->rows[pos] != NULL);
1122 assert((pos < col->nlprows) == (col->rows[pos]->lppos >= 0 && col->linkpos[pos] >= 0));
1123 idx = col->rows[pos]->index;
1124 if( searchidx == idx )
1125 return pos;
1126 else if( searchidx < idx )
1127 maxpos = pos-1;
1128 else
1129 minpos = pos+1;
1130 }
1131
1132 return -1;
1133}
1134
1135/** searches coefficient in column, returns position in col vector or -1 if not found */
1136static
1138 SCIP_COL* col, /**< column to be searched in */
1139 const SCIP_ROW* row /**< coefficient to be searched for */
1140 )
1141{
1142 int pos;
1143
1144 assert(col != NULL);
1145 assert(row != NULL);
1146
1147 pos = -1;
1148
1149 /* search in the linked LP rows */
1150 if( row->lppos >= 0 )
1151 {
1152 /* column has to be sorted, such that binary search works */
1153 colSortLP(col);
1154 assert(col->lprowssorted);
1155
1156 pos = colSearchCoefPart(col, row, 0, col->nlprows-1);
1157 if( pos >= 0 )
1158 return pos;
1159 }
1160
1161 /* search in the non-LP/unlinked rows */
1162 if( row->lppos == -1 || col->nunlinked > 0 )
1163 {
1164 /* column has to be sorted, such that binary search works */
1165 colSortNonLP(col);
1166 assert(col->nonlprowssorted);
1167
1168 pos = colSearchCoefPart(col, row, col->nlprows, col->len-1);
1169 }
1170
1171 return pos;
1172}
1173
1174/** searches coefficient in part of the row, returns position in col vector or -1 if not found */
1175static
1177 SCIP_ROW* row, /**< row to be searched in */
1178 const SCIP_COL* col, /**< coefficient to be searched for */
1179 int minpos, /**< first position of search range */
1180 int maxpos /**< last position of search range */
1181 )
1182{
1183 int pos;
1184 int idx;
1185 int searchidx;
1186
1187 assert(row != NULL);
1188 assert(col != NULL);
1189
1190 /* binary search */
1191 searchidx = col->index;
1192 while(minpos <= maxpos)
1193 {
1194 pos = (minpos + maxpos)/2;
1195 assert(0 <= pos && pos < row->len);
1196 assert(row->cols[pos] != NULL);
1197 assert((pos < row->nlpcols) == (row->cols[pos]->lppos >= 0 && row->linkpos[pos] >= 0));
1198 assert(row->cols_index[pos] == row->cols[pos]->index);
1199 idx = row->cols_index[pos];
1200 if( searchidx == idx )
1201 return pos;
1202 else if( searchidx < idx )
1203 maxpos = pos-1;
1204 else
1205 minpos = pos+1;
1206 }
1207
1208 return -1;
1209}
1210
1211/** searches coefficient in row, returns position in row vector or -1 if not found;
1212 * if the sorting of the row is delayed, returns -1
1213 */
1214static
1216 SCIP_ROW* row, /**< row to be searched in */
1217 const SCIP_COL* col /**< coefficient to be searched for */
1218 )
1219{
1220 int pos;
1221
1222 assert(row != NULL);
1223 assert(col != NULL);
1224
1225 if( row->delaysort )
1226 return -1;
1227
1228 pos = -1;
1229
1230 /* search in the linked LP columns */
1231 if( col->lppos >= 0 )
1232 {
1233 /* row has to be sorted, such that binary search works */
1234 rowSortLP(row);
1235 assert(row->lpcolssorted);
1236
1237 pos = rowSearchCoefPart(row, col, 0, row->nlpcols-1);
1238 }
1239
1240 /* search in the non-LP/unlinked columns */
1241 if( pos == -1 && (col->lppos == -1 || row->nunlinked > 0) )
1242 {
1243 /* row has to be sorted, such that binary search works */
1244 rowSortNonLP(row);
1245 assert(row->nonlpcolssorted);
1246
1247 pos = rowSearchCoefPart(row, col, row->nlpcols, row->len-1);
1248 }
1249
1250#ifndef NDEBUG
1251 /* validate result */
1252 assert(-1 <= pos && pos < row->len);
1253 if( pos >= 0 )
1254 assert(row->cols[pos] == col);
1255 else
1256 {
1257 int i;
1258 for( i = 0; i < row->len; ++i )
1259 assert(row->cols[i] != col);
1260 }
1261#endif
1262
1263 return pos;
1264}
1265
1266/** moves a coefficient in a column to a different place, and updates all corresponding data structures */
1267static
1269 SCIP_COL* col, /**< LP column */
1270 int oldpos, /**< old position of coefficient */
1271 int newpos /**< new position of coefficient */
1272 )
1273{
1274 assert(col != NULL);
1275 assert(0 <= oldpos && oldpos < col->len);
1276 assert(0 <= newpos && newpos < col->len);
1277 assert(col->rows[oldpos] != NULL);
1278
1279 if( oldpos == newpos )
1280 return;
1281
1282 col->rows[newpos] = col->rows[oldpos];
1283 col->vals[newpos] = col->vals[oldpos];
1284 col->linkpos[newpos] = col->linkpos[oldpos];
1285
1286 /* update link position in row */
1287 if( col->linkpos[newpos] >= 0 )
1288 {
1289 assert(col->rows[newpos]->cols[col->linkpos[newpos]] == col);
1290 assert(col->rows[newpos]->linkpos[col->linkpos[newpos]] == oldpos);
1291
1292 col->rows[newpos]->linkpos[col->linkpos[newpos]] = newpos;
1293 }
1294
1295 /* update sorted flags */
1296 if( col->rows[newpos]->lppos >= 0 && col->linkpos[newpos] >= 0 )
1297 col->lprowssorted = FALSE;
1298 else
1299 col->nonlprowssorted = FALSE;
1300}
1301
1302/** swaps two coefficients in a column, and updates all corresponding data structures */
1303static
1305 SCIP_COL* col, /**< LP column */
1306 int pos1, /**< position of first coefficient */
1307 int pos2 /**< position of second coefficient */
1308 )
1309{
1310 SCIP_ROW* tmprow;
1311 SCIP_Real tmpval;
1312 int tmplinkpos;
1313
1314 assert(col != NULL);
1315 assert(0 <= pos1 && pos1 < col->len);
1316 assert(0 <= pos2 && pos2 < col->len);
1317 assert(col->rows[pos1] != NULL);
1318
1319 if( pos1 == pos2 )
1320 return;
1321
1322 /* swap coefficients */
1323 tmprow = col->rows[pos2];
1324 tmpval = col->vals[pos2];
1325 tmplinkpos = col->linkpos[pos2];
1326
1327 col->rows[pos2] = col->rows[pos1];
1328 col->vals[pos2] = col->vals[pos1];
1329 col->linkpos[pos2] = col->linkpos[pos1];
1330
1331 col->rows[pos1] = tmprow;
1332 col->vals[pos1] = tmpval;
1333 col->linkpos[pos1] = tmplinkpos;
1334
1335 /* update link position in rows */
1336 if( col->linkpos[pos1] >= 0 )
1337 {
1338 assert(col->rows[pos1]->cols[col->linkpos[pos1]] == col);
1339 assert(col->rows[pos1]->linkpos[col->linkpos[pos1]] == pos2);
1340
1341 col->rows[pos1]->linkpos[col->linkpos[pos1]] = pos1;
1342 }
1343 if( col->linkpos[pos2] >= 0 )
1344 {
1345 assert(col->rows[pos2]->cols[col->linkpos[pos2]] == col);
1346 assert(col->rows[pos2]->linkpos[col->linkpos[pos2]] == pos1);
1347
1348 col->rows[pos2]->linkpos[col->linkpos[pos2]] = pos2;
1349 }
1350
1351 /* update sorted flags */
1352 if( col->rows[pos1]->lppos >= 0 && col->linkpos[pos1] >= 0 )
1353 col->lprowssorted = FALSE;
1354 else
1355 col->nonlprowssorted = FALSE;
1356 if( col->rows[pos2]->lppos >= 0 && col->linkpos[pos2] >= 0 )
1357 col->lprowssorted = FALSE;
1358 else
1359 col->nonlprowssorted = FALSE;
1360}
1361
1362/** moves a coefficient in a row to a different place, and updates all corresponding data structures */
1363static
1365 SCIP_ROW* row, /**< LP row */
1366 int oldpos, /**< old position of coefficient */
1367 int newpos /**< new position of coefficient */
1368 )
1369{
1370 assert(row != NULL);
1371 assert(0 <= oldpos && oldpos < row->len);
1372 assert(0 <= newpos && newpos < row->len);
1373 assert(row->cols[oldpos] != NULL);
1374
1375 if( oldpos == newpos )
1376 return;
1377
1378 row->cols[newpos] = row->cols[oldpos];
1379 row->cols_index[newpos] = row->cols_index[oldpos];
1380 row->vals[newpos] = row->vals[oldpos];
1381 row->linkpos[newpos] = row->linkpos[oldpos];
1382
1383 /* update link position in column */
1384 if( row->linkpos[newpos] >= 0 )
1385 {
1386 assert(row->cols[newpos]->rows[row->linkpos[newpos]] == row);
1387 assert(row->cols[newpos]->linkpos[row->linkpos[newpos]] == oldpos);
1388
1389 row->cols[newpos]->linkpos[row->linkpos[newpos]] = newpos;
1390 }
1391
1392 /* update sorted flags */
1393 if( row->cols[newpos]->lppos >= 0 && row->linkpos[newpos] >= 0 )
1394 row->lpcolssorted = FALSE;
1395 else
1396 row->nonlpcolssorted = FALSE;
1397}
1398
1399/** swaps two coefficients in a row, and updates all corresponding data structures */
1400static
1402 SCIP_ROW* row, /**< LP row */
1403 int pos1, /**< position of first coefficient */
1404 int pos2 /**< position of second coefficient */
1405 )
1406{
1407 SCIP_COL* tmpcol;
1408 SCIP_Real tmpval;
1409 int tmpindex;
1410 int tmplinkpos;
1411
1412 assert(row != NULL);
1413 assert(0 <= pos1 && pos1 < row->len);
1414 assert(0 <= pos2 && pos2 < row->len);
1415 assert(row->cols[pos1] != NULL);
1416 assert(row->cols[pos1]->index == row->cols_index[pos1]);
1417
1418 if( pos1 == pos2 )
1419 return;
1420
1421 /* swap coefficients */
1422 tmpcol = row->cols[pos2];
1423 tmpindex = row->cols_index[pos2];
1424 tmpval = row->vals[pos2];
1425 tmplinkpos = row->linkpos[pos2];
1426
1427 row->cols[pos2] = row->cols[pos1];
1428 row->cols_index[pos2] = row->cols_index[pos1];
1429 row->vals[pos2] = row->vals[pos1];
1430 row->linkpos[pos2] = row->linkpos[pos1];
1431
1432 row->cols[pos1] = tmpcol;
1433 row->cols_index[pos1] = tmpindex;
1434 row->vals[pos1] = tmpval;
1435 row->linkpos[pos1] = tmplinkpos;
1436
1437 /* update link position in columns */
1438 if( row->linkpos[pos1] >= 0 )
1439 {
1440 assert(row->cols[pos1]->rows[row->linkpos[pos1]] == row);
1441 assert(row->cols[pos1]->linkpos[row->linkpos[pos1]] == pos2);
1442
1443 row->cols[pos1]->linkpos[row->linkpos[pos1]] = pos1;
1444 }
1445 if( row->linkpos[pos2] >= 0 )
1446 {
1447 assert(row->cols[pos2]->rows[row->linkpos[pos2]] == row);
1448 assert(row->cols[pos2]->linkpos[row->linkpos[pos2]] == pos1);
1449
1450 row->cols[pos2]->linkpos[row->linkpos[pos2]] = pos2;
1451 }
1452
1453 /* update sorted flags */
1454 if( row->cols[pos1]->lppos >= 0 && row->linkpos[pos1] >= 0 )
1455 row->lpcolssorted = FALSE;
1456 else
1457 row->nonlpcolssorted = FALSE;
1458 if( row->cols[pos2]->lppos >= 0 && row->linkpos[pos2] >= 0 )
1459 row->lpcolssorted = FALSE;
1460 else
1461 row->nonlpcolssorted = FALSE;
1462}
1463
1464/** issues a ROWCOEFCHANGED event on the given row */
1465static
1467 SCIP_ROW* row, /**< row which coefficient has changed */
1468 BMS_BLKMEM* blkmem, /**< block memory */
1469 SCIP_SET* set, /**< global SCIP settings */
1470 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1471 SCIP_COL* col, /**< the column which coefficient has changed */
1472 SCIP_Real oldval, /**< old value of the coefficient */
1473 SCIP_Real newval /**< new value of the coefficient */
1474 )
1475{
1476 assert(row != NULL);
1477 assert(row->eventfilter != NULL);
1478 assert(col != NULL);
1479
1480 /* check, if the row is being tracked for coefficient changes
1481 * if so, issue ROWCOEFCHANGED event
1482 */
1483 if( (row->eventfilter->len > 0 && (row->eventfilter->eventmask & SCIP_EVENTTYPE_ROWCOEFCHANGED) != 0) )
1484 {
1485 SCIP_EVENT* event;
1486
1487 SCIP_CALL( SCIPeventCreateRowCoefChanged(&event, blkmem, row, col, oldval, newval) );
1488 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, row->eventfilter, &event) );
1489 }
1490
1491 return SCIP_OKAY;
1492}
1493
1494/** issues a ROWCONSTCHANGED event on the given row */
1495static
1497 SCIP_ROW* row, /**< row which coefficient has changed */
1498 BMS_BLKMEM* blkmem, /**< block memory */
1499 SCIP_SET* set, /**< global SCIP settings */
1500 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1501 SCIP_Real oldval, /**< old value of the constant */
1502 SCIP_Real newval /**< new value of the constant */
1503 )
1504{
1505 assert(row != NULL);
1506 assert(row->eventfilter != NULL);
1507
1508 /* check, if the row is being tracked for coefficient changes
1509 * if so, issue ROWCONSTCHANGED event
1510 */
1512 {
1513 SCIP_EVENT* event;
1514
1515 SCIP_CALL( SCIPeventCreateRowConstChanged(&event, blkmem, row, oldval, newval) );
1516 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, row->eventfilter, &event) );
1517 }
1518
1519 return SCIP_OKAY;
1520}
1521
1522/** issues a ROWSIDECHANGED event on the given row */
1523static
1525 SCIP_ROW* row, /**< row which coefficient has changed */
1526 BMS_BLKMEM* blkmem, /**< block memory */
1527 SCIP_SET* set, /**< global SCIP settings */
1528 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1529 SCIP_SIDETYPE side, /**< the side that has changed */
1530 SCIP_Real oldval, /**< old value of side */
1531 SCIP_Real newval /**< new value of side */
1532 )
1533{
1534 assert(row != NULL);
1535 assert(row->eventfilter != NULL);
1536
1537 /* check, if the row is being tracked for coefficient changes
1538 * if so, issue ROWSIDECHANGED event
1539 */
1540 if( (row->eventfilter->len > 0 && !(row->eventfilter->eventmask & SCIP_EVENTTYPE_ROWSIDECHANGED)) )
1541 {
1542 SCIP_EVENT* event;
1543
1544 SCIP_CALL( SCIPeventCreateRowSideChanged(&event, blkmem, row, side, oldval, newval) );
1545 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, row->eventfilter, &event) );
1546 }
1547
1548 return SCIP_OKAY;
1549}
1550
1551#ifdef SCIP_MORE_DEBUG /* enable this to check links between columns and rows in LP data structure (for debugging, very slow!) */
1552
1553#ifdef NDEBUG
1554#define ASSERT(x) do { if( !(x) ) abort(); } while( FALSE )
1555#else
1556#define ASSERT(x) assert(x)
1557#endif
1558
1559static SCIP_Bool msgdisp_checklinks = FALSE;
1560
1561
1562static
1563void checkLinks(
1564 SCIP_LP* lp /**< current LP data */
1565 )
1566{
1567 SCIP_COL* col;
1568 SCIP_ROW* row;
1569 int i;
1570 int j;
1571
1572 ASSERT(lp != NULL);
1573
1574 if( !msgdisp_checklinks )
1575 {
1576 printf("LP LINK CHECKING ACTIVATED! THIS IS VERY SLOW!\n");
1577 msgdisp_checklinks = TRUE;
1578 }
1579
1580 for( i = 0; i < lp->ncols; ++i )
1581 {
1582 col = lp->cols[i];
1583 ASSERT(col != NULL);
1584 ASSERT(!lp->flushed || col->lppos >= 0 || col->primsol == 0.0);
1585 ASSERT(!lp->flushed || col->lppos >= 0 || col->farkascoef == 0.0);
1586 ASSERT(col->nlprows <= col->len);
1587 ASSERT(col->lppos == -1 || col->lppos >= lp->lpifirstchgcol || col->nunlinked == 0);
1588
1589 for( j = 0; j < col->len; ++j )
1590 {
1591 row = col->rows[j];
1592 ASSERT(row != NULL);
1593 ASSERT(!lp->flushed || col->lppos == -1 || col->linkpos[j] >= 0);
1594 ASSERT(col->linkpos[j] == -1 || row->cols[col->linkpos[j]] == col);
1595 ASSERT(col->linkpos[j] == -1 || EPSEQ(row->vals[col->linkpos[j]], col->vals[j], 1e-6));
1596 ASSERT((j < col->nlprows) == (col->linkpos[j] >= 0 && row->lppos >= 0));
1597 }
1598 }
1599
1600 for( i = 0; i < lp->nrows; ++i )
1601 {
1602 row = lp->rows[i];
1603 ASSERT(row != NULL);
1604 ASSERT(!lp->flushed || row->lppos >= 0 || row->dualsol == 0.0);
1605 ASSERT(!lp->flushed || row->lppos >= 0 || row->dualfarkas == 0.0);
1606 ASSERT(row->nlpcols <= row->len);
1607 ASSERT(row->lppos == -1 || row->lppos >= lp->lpifirstchgrow || row->nunlinked == 0);
1608
1609 for( j = 0; j < row->len; ++j )
1610 {
1611 col = row->cols[j];
1612 ASSERT(col != NULL);
1613 ASSERT(!lp->flushed || row->lppos == -1 || row->linkpos[j] >= 0);
1614 ASSERT(row->linkpos[j] == -1 || col->rows[row->linkpos[j]] == row);
1615 ASSERT(row->linkpos[j] == -1 || EPSEQ(col->vals[row->linkpos[j]], row->vals[j], 1e-6));
1616 ASSERT((j < row->nlpcols) == (row->linkpos[j] >= 0 && col->lppos >= 0));
1617 }
1618 }
1619}
1620
1621#undef ASSERT
1622
1623#else
1624#define checkLinks(lp) /**/
1625#endif
1626
1627/*
1628 * Changing announcements
1629 */
1630
1631/** announces, that the given coefficient in the constraint matrix changed */
1632static
1634 SCIP_ROW* row, /**< LP row */
1635 SCIP_COL* col, /**< LP col */
1636 SCIP_LP* lp /**< current LP data */
1637 )
1638{
1639 assert(row != NULL);
1640 assert(col != NULL);
1641 assert(lp != NULL);
1642
1643 if( row->lpipos >= 0 && col->lpipos >= 0 )
1644 {
1645 assert(row->lpipos < lp->nlpirows);
1646 assert(col->lpipos < lp->nlpicols);
1647
1648 /* we have to remember the change only in the row or in the column,
1649 * because the readdition of one vector would change the other automatically.
1650 */
1651 if( row->lpipos >= lp->lpifirstchgrow )
1652 row->coefchanged = TRUE;
1653 else if( col->lpipos >= lp->lpifirstchgcol )
1654 col->coefchanged = TRUE;
1655 else if( lp->lpifirstchgrow - row->lpipos <= lp->lpifirstchgcol - col->lpipos )
1656 {
1657 row->coefchanged = TRUE;
1658 lp->lpifirstchgrow = row->lpipos;
1659 }
1660 else
1661 {
1662 col->coefchanged = TRUE;
1663 lp->lpifirstchgcol = col->lpipos;
1664 }
1665
1666 /* mark the current LP unflushed */
1667 lp->flushed = FALSE;
1668 }
1669
1673 row->validpsactivitydomchg = -1;
1674 row->validactivitybdsdomchg = -1;
1675}
1676
1677
1678
1679/*
1680 * local column changing methods
1681 */
1682
1683/* forward declaration for colAddCoef() */
1684static
1686 SCIP_ROW* row, /**< LP row */
1687 BMS_BLKMEM* blkmem, /**< block memory */
1688 SCIP_SET* set, /**< global SCIP settings */
1689 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1690 SCIP_LP* lp, /**< current LP data */
1691 SCIP_COL* col, /**< LP column */
1692 SCIP_Real val, /**< value of coefficient */
1693 int linkpos /**< position of row in the column's row array, or -1 */
1694 );
1695
1696/** adds a previously non existing coefficient to an LP column */
1697static
1699 SCIP_COL* col, /**< LP column */
1700 BMS_BLKMEM* blkmem, /**< block memory */
1701 SCIP_SET* set, /**< global SCIP settings */
1702 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1703 SCIP_LP* lp, /**< current LP data */
1704 SCIP_ROW* row, /**< LP row */
1705 SCIP_Real val, /**< value of coefficient */
1706 int linkpos /**< position of column in the row's col array, or -1 */
1707 )
1708{
1709 int pos;
1710
1711 assert(blkmem != NULL);
1712 assert(col != NULL);
1713 assert(col->nlprows <= col->len);
1714 assert(col->var != NULL);
1715 assert(row != NULL);
1716 assert(!SCIPsetIsZero(set, val));
1717 /*assert(colSearchCoef(col, row) == -1);*/ /* this assert would lead to slight differences in the solution process */
1718
1719 SCIP_CALL( colEnsureSize(col, blkmem, set, col->len+1) );
1720 assert(col->rows != NULL);
1721 assert(col->vals != NULL);
1722 assert(col->linkpos != NULL);
1723
1724 pos = col->len;
1725 col->len++;
1726
1727 /* if the row is in current LP and is linked to the column, we have to insert it at the end of the linked LP rows
1728 * part of the column's arrays
1729 */
1730 if( row->lppos >= 0 && linkpos >= 0 )
1731 {
1732 /* move the first non-LP/not linked row to the end */
1733 if( col->nlprows < pos )
1734 {
1735 colMoveCoef(col, col->nlprows, pos);
1736 pos = col->nlprows;
1737 }
1738 col->nlprows++;
1739 }
1740
1741 /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
1742 val = SCIPsetIsIntegral(set, val) ? SCIPsetRound(set, val) : val;
1743
1744 /* insert the row at the correct position and update the links */
1745 col->rows[pos] = row;
1746 col->vals[pos] = val;
1747 col->linkpos[pos] = linkpos;
1748 if( linkpos == -1 )
1749 {
1750 col->nunlinked++;
1751
1752 /* if the column is in current LP, we have to link it to the row, because otherwise, the primal information
1753 * of the row is not complete
1754 */
1755 if( col->lppos >= 0 )
1756 {
1757 /* this call might swap the current row with the first non-LP/not linked row, s.t. insertion position
1758 * has to be updated
1759 */
1760 SCIP_CALL( rowAddCoef(row, blkmem, set, eventqueue, lp, col, val, pos) );
1761 if( row->lppos >= 0 )
1762 pos = col->nlprows-1;
1763 linkpos = col->linkpos[pos];
1764
1765 assert(0 <= linkpos && linkpos < row->len);
1766 assert(row->cols[linkpos] == col);
1767 assert(col->rows[pos] == row);
1768 assert(col->rows[pos]->cols[col->linkpos[pos]] == col);
1769 assert(col->rows[pos]->linkpos[col->linkpos[pos]] == pos);
1770 }
1771 }
1772 else
1773 {
1774 assert(row->linkpos[linkpos] == -1);
1775 assert(row->nunlinked > 0);
1776 row->linkpos[linkpos] = pos;
1777 row->nunlinked--;
1778
1779 /* if the column is in current LP, now both conditions, row->cols[linkpos]->lppos >= 0 and row->linkpos[linkpos] >= 0
1780 * hold, so we have to move the column to the linked LP-cols part of the row's cols array
1781 */
1782 if( col->lppos >= 0 )
1783 {
1784 row->nlpcols++;
1785 rowSwapCoefs(row, linkpos, row->nlpcols-1);
1786
1787 /* if no swap was necessary, mark nonlpcols to be unsorted */
1788 if( linkpos == row->nlpcols-1 )
1789 row->lpcolssorted = FALSE;
1790 }
1791 }
1792
1793 /* update the sorted flags */
1794 if( row->lppos >= 0 && linkpos >= 0 )
1795 {
1796 assert(col->nlprows >= 1);
1797 assert(col->rows[col->nlprows-1] == row);
1798 if( col->nlprows > 1 )
1799 col->lprowssorted = col->lprowssorted && (col->rows[col->nlprows-2]->index < row->index);
1800 }
1801 else
1802 {
1803 assert(col->len - col->nlprows >= 1);
1804 assert(col->rows[col->len-1] == row);
1805 if( col->len - col->nlprows > 1 )
1806 col->nonlprowssorted = col->nonlprowssorted && (col->rows[col->len-2]->index < row->index);
1807 }
1808
1809 coefChanged(row, col, lp);
1810
1811 SCIPsetDebugMsg(set, "added coefficient %g * <%s> at position %d (%d/%d) to column <%s> (nunlinked=%d)\n",
1812 val, row->name, pos, col->nlprows, col->len, SCIPvarGetName(col->var), col->nunlinked);
1813
1814 return SCIP_OKAY;
1815}
1816
1817/** deletes coefficient at given position from column */
1818static
1820 SCIP_COL* col, /**< column to be changed */
1821 SCIP_SET* set, /**< global SCIP settings */
1822 SCIP_LP* lp, /**< current LP data */
1823 int pos /**< position in column vector to delete */
1824 )
1825{
1826 SCIP_ROW* row;
1827
1828 assert(col != NULL);
1829 assert(col->var != NULL);
1830 assert(set != NULL);
1831 assert(0 <= pos && pos < col->len);
1832 assert(col->rows[pos] != NULL);
1833 assert(col->linkpos[pos] == -1 || col->rows[pos]->cols[col->linkpos[pos]] == col);
1834 assert((pos < col->nlprows) == (col->linkpos[pos] >= 0 && col->rows[pos]->lppos >= 0));
1835
1836 row = col->rows[pos];
1837 assert((row->lppos >= 0) == (pos < col->nlprows));
1838
1839 /*SCIPsetDebugMsg(set, "deleting coefficient %g * <%s> at position %d from column <%s>\n",
1840 col->vals[pos], row->name, pos, SCIPvarGetName(col->var));*/
1841
1842 if( col->linkpos[pos] == -1 )
1843 col->nunlinked--;
1844
1845 /* if row is a linked LP row, move last linked LP coefficient to position of empty slot (deleted coefficient) */
1846 if( pos < col->nlprows )
1847 {
1848 colMoveCoef(col, col->nlprows-1, pos);
1849 col->nlprows--;
1850 pos = col->nlprows;
1851 }
1852
1853 /* move last coefficient to position of empty slot */
1854 colMoveCoef(col, col->len-1, pos);
1855 col->len--;
1856
1857 coefChanged(row, col, lp);
1858
1859 return SCIP_OKAY;
1860}
1861
1862/** changes a coefficient at given position of an LP column */
1863static
1865 SCIP_COL* col, /**< LP column */
1866 SCIP_SET* set, /**< global SCIP settings */
1867 SCIP_LP* lp, /**< current LP data */
1868 int pos, /**< position in column vector to change */
1869 SCIP_Real val /**< value of coefficient */
1870 )
1871{
1872 assert(col != NULL);
1873 assert(col->var != NULL);
1874 assert(0 <= pos && pos < col->len);
1875 assert(col->rows[pos] != NULL);
1876 assert(col->linkpos[pos] == -1 || col->rows[pos]->cols[col->linkpos[pos]] == col);
1877
1878 /*debugMsg(scip, "changing coefficient %g * <%s> at position %d of column <%s> to %g\n",
1879 col->vals[pos], col->rows[pos]->name, pos, SCIPvarGetName(col->var), val);*/
1880
1881 /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
1882 val = SCIPsetIsIntegral(set, val) ? SCIPsetRound(set, val) : val;
1883
1884 if( SCIPsetIsZero(set, val) )
1885 {
1886 /* delete existing coefficient */
1887 SCIP_CALL( colDelCoefPos(col, set, lp, pos) );
1888 }
1889 else if( !SCIPsetIsEQ(set, col->vals[pos], val) )
1890 {
1891 /* change existing coefficient */
1892 col->vals[pos] = val;
1893 coefChanged(col->rows[pos], col, lp);
1894 }
1895
1896 return SCIP_OKAY;
1897}
1898
1899
1900
1901
1902/*
1903 * local row changing methods
1904 */
1905
1906/** update row norms after addition of coefficient */
1907static
1909 SCIP_ROW* row, /**< LP row */
1910 SCIP_SET* set, /**< global SCIP settings */
1911 SCIP_COL* col, /**< column of added coefficient */
1912 SCIP_Real val, /**< value of added coefficient */
1913 SCIP_Bool updateidxvals /**< update min/max idx and min/max val? */
1914 )
1915{
1916 SCIP_Real absval;
1917
1918 assert(row != NULL);
1919 assert(row->nummaxval >= 0);
1920 assert(row->numminval >= 0);
1921 assert(set != NULL);
1922 assert(col != NULL);
1923
1924 absval = REALABS(val);
1925 assert(!SCIPsetIsZero(set, absval));
1926
1927 /* Euclidean norm, sum norm, and objective function scalar product only take LP columns into account */
1928 if( col->lppos >= 0 )
1929 {
1930 /* update squared Euclidean norm and sum norm */
1931 row->sqrnorm += SQR(absval);
1932 row->sumnorm += absval;
1933
1934 /* update objective function scalar product */
1935 row->objprod += val * col->unchangedobj;
1936 }
1937
1938 if( updateidxvals )
1939 {
1940 /* update min/maxidx */
1941 row->minidx = MIN(row->minidx, col->index);
1942 row->maxidx = MAX(row->maxidx, col->index);
1943
1944 /* update maximal and minimal non-zero value */
1945 if( row->nummaxval > 0 )
1946 {
1947 if( SCIPsetIsGT(set, absval, row->maxval) )
1948 {
1949 row->maxval = absval;
1950 row->nummaxval = 1;
1951 }
1952 else if( SCIPsetIsGE(set, absval, row->maxval) )
1953 {
1954 /* make sure the maxval is always exactly the same */
1955 row->maxval = MAX(absval, row->maxval);
1956 row->nummaxval++;
1957 }
1958 }
1959 if( row->numminval > 0 )
1960 {
1961 if( SCIPsetIsLT(set, absval, row->minval) )
1962 {
1963 row->minval = absval;
1964 row->numminval = 1;
1965 }
1966 else if( SCIPsetIsLE(set, absval, row->minval) )
1967 {
1968 /* make sure the minval is always exactly the same */
1969 row->minval = MIN(absval, row->minval);
1970 row->numminval++;
1971 }
1972 }
1973 }
1974 else
1975 {
1976 assert(row->minidx <= col->index);
1977 assert(row->maxidx >= col->index);
1978 assert(row->numminval <= 0 || absval >= row->minval);
1979 assert(row->nummaxval <= 0 || absval <= row->maxval);
1980 }
1981}
1982
1983/** update row norms after deletion of coefficient */
1984static
1986 SCIP_ROW* row, /**< LP row */
1987 SCIP_SET* set, /**< global SCIP settings */
1988 SCIP_COL* col, /**< column of deleted coefficient */
1989 SCIP_Real val, /**< value of deleted coefficient */
1990 SCIP_Bool forcenormupdate, /**< should the norms be updated even if lppos of column is -1? */
1991 SCIP_Bool updateindex, /**< should the minimal/maximal column index of row be updated? */
1992 SCIP_Bool updateval /**< should the minimal/maximal value of row be updated? */
1993 )
1994{
1995 SCIP_Real absval;
1996
1997 assert(row != NULL);
1998 assert(row->nummaxval >= 0);
1999 assert(row->numminval >= 0);
2000 assert(set != NULL);
2001 assert(col != NULL);
2002
2003 absval = REALABS(val);
2004 assert(!SCIPsetIsZero(set, absval));
2005 assert(row->nummaxval == 0 || row->maxval >= absval);
2006 assert(row->numminval == 0 || row->minval <= absval);
2007
2008 /* update min/maxidx validity */
2009 if( updateindex && (col->index == row->minidx || col->index == row->maxidx) )
2010 row->validminmaxidx = FALSE;
2011
2012 /* Euclidean norm, sum norm, and objective function scalar product only take LP columns into account */
2013 if( forcenormupdate || col->lppos >= 0 )
2014 {
2015 /* update squared Euclidean norm and sum norm */
2016 row->sqrnorm -= SQR(absval);
2017 row->sqrnorm = MAX(row->sqrnorm, 0.0);
2018 row->sumnorm -= absval;
2019 row->sumnorm = MAX(row->sumnorm, 0.0);
2020
2021 /* update objective function scalar product */
2022 row->objprod -= val * col->unchangedobj;
2023 }
2024
2025 if( updateval )
2026 {
2027 /* update maximal and minimal non-zero value */
2028 if( row->nummaxval > 0 )
2029 {
2030 if( SCIPsetIsGE(set, absval, row->maxval) )
2031 row->nummaxval--;
2032 }
2033 if( row->numminval > 0 )
2034 {
2035 if( SCIPsetIsLE(set, absval, row->minval) )
2036 row->numminval--;
2037 }
2038 }
2039}
2040
2041/** adds a previously non existing coefficient to an LP row */
2042static
2044 SCIP_ROW* row, /**< LP row */
2045 BMS_BLKMEM* blkmem, /**< block memory */
2046 SCIP_SET* set, /**< global SCIP settings */
2047 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2048 SCIP_LP* lp, /**< current LP data */
2049 SCIP_COL* col, /**< LP column */
2050 SCIP_Real val, /**< value of coefficient */
2051 int linkpos /**< position of row in the column's row array, or -1 */
2052 )
2053{
2054 int pos;
2055
2056 assert(row != NULL);
2057 assert(row->nlpcols <= row->len);
2058 assert(blkmem != NULL);
2059 assert(col != NULL);
2060 assert(col->var != NULL);
2061 assert(col->var_probindex == SCIPvarGetProbindex(col->var));
2062 assert(!SCIPsetIsZero(set, val));
2063 /*assert(rowSearchCoef(row, col) == -1);*/ /* this assert would lead to slight differences in the solution process */
2064
2065 if( row->nlocks > 0 )
2066 {
2067 SCIPerrorMessage("cannot add a coefficient to the locked unmodifiable row <%s>\n", row->name);
2068 return SCIP_INVALIDDATA;
2069 }
2070
2071 SCIP_CALL( SCIProwEnsureSize(row, blkmem, set, row->len+1) );
2072 assert(row->cols != NULL);
2073 assert(row->vals != NULL);
2074
2075 pos = row->len;
2076 row->len++;
2077
2078 /* if the column is in current LP and is linked to the row, we have to insert it at the end of the linked LP columns
2079 * part of the row's arrays
2080 */
2081 if( col->lppos >= 0 && linkpos >= 0 )
2082 {
2083 /* move the first non-LP/not linked column to the end */
2084 if( row->nlpcols < pos )
2085 {
2086 rowMoveCoef(row, row->nlpcols, pos);
2087 pos = row->nlpcols;
2088 }
2089 row->nlpcols++;
2090 }
2091
2092 /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
2093 val = SCIPsetIsIntegral(set, val) ? SCIPsetRound(set, val) : val;
2094
2095 /* insert the column at the correct position and update the links */
2096 row->cols[pos] = col;
2097 row->cols_index[pos] = col->index;
2098 row->vals[pos] = val;
2099 row->linkpos[pos] = linkpos;
2100 row->integral = row->integral && SCIPcolIsIntegral(col) && SCIPsetIsIntegral(set, val);
2101 if( linkpos == -1 )
2102 {
2103 row->nunlinked++;
2104
2105 /* if the row is in current LP, we have to link it to the column, because otherwise, the dual information
2106 * of the column is not complete
2107 */
2108 if( row->lppos >= 0 )
2109 {
2110 /* this call might swap the current column with the first non-LP/not linked column, s.t. insertion position
2111 * has to be updated
2112 */
2113 SCIP_CALL( colAddCoef(col, blkmem, set, eventqueue, lp, row, val, pos) );
2114 if( col->lppos >= 0 )
2115 pos = row->nlpcols-1;
2116 linkpos = row->linkpos[pos];
2117
2118 assert(0 <= linkpos && linkpos < col->len);
2119 assert(col->rows[linkpos] == row);
2120 assert(row->cols[pos] == col);
2121 assert(row->cols[pos]->rows[row->linkpos[pos]] == row);
2122 assert(row->cols[pos]->linkpos[row->linkpos[pos]] == pos);
2123 }
2124 }
2125 else
2126 {
2127 assert(col->linkpos[linkpos] == -1);
2128 assert(col->nunlinked > 0);
2129 col->linkpos[linkpos] = pos;
2130 col->nunlinked--;
2131
2132 /* if the row is in current LP, now both conditions, col->rows[linkpos]->lppos >= 0 and col->linkpos[linkpos] >= 0
2133 * hold, so we have to move the row to the linked LP-rows part of the column's rows array
2134 */
2135 if( row->lppos >= 0 )
2136 {
2137 col->nlprows++;
2138 colSwapCoefs(col, linkpos, col->nlprows-1);
2139
2140 /* if no swap was necessary, mark lprows to be unsorted */
2141 if( linkpos == col->nlprows-1 )
2142 col->lprowssorted = FALSE;
2143 }
2144 }
2145
2146 /* update the sorted flags */
2147 if( col->lppos >= 0 && linkpos >= 0 )
2148 {
2149 assert(row->nlpcols >= 1);
2150 assert(row->cols[row->nlpcols-1] == col);
2151 if( row->nlpcols > 1 )
2152 {
2153 assert(row->cols_index[row->nlpcols-2] == row->cols[row->nlpcols-2]->index);
2154 row->lpcolssorted = row->lpcolssorted && (row->cols_index[row->nlpcols-2] < col->index);
2155 }
2156 }
2157 else
2158 {
2159 assert(row->len - row->nlpcols >= 1);
2160 assert(row->cols[row->len-1] == col);
2161 if( row->len - row->nlpcols > 1 )
2162 {
2163 assert(row->cols_index[row->len-2] == row->cols[row->len-2]->index);
2164 row->nonlpcolssorted = row->nonlpcolssorted && (row->cols_index[row->len-2] < col->index);
2165 }
2166 }
2167
2168 /* update row norm */
2169 rowAddNorms(row, set, col, val, TRUE);
2170
2171 coefChanged(row, col, lp);
2172
2173 SCIPsetDebugMsg(set, "added coefficient %g * <%s> at position %d (%d/%d) to row <%s> (nunlinked=%d)\n",
2174 val, SCIPvarGetName(col->var), pos, row->nlpcols, row->len, row->name, row->nunlinked);
2175
2176 /* issue row coefficient changed event */
2177 SCIP_CALL( rowEventCoefChanged(row, blkmem, set, eventqueue, col, 0.0, val) );
2178
2179 return SCIP_OKAY;
2180}
2181
2182/** deletes coefficient at given position from row */
2183static
2185 SCIP_ROW* row, /**< row to be changed */
2186 BMS_BLKMEM* blkmem, /**< block memory */
2187 SCIP_SET* set, /**< global SCIP settings */
2188 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2189 SCIP_LP* lp, /**< current LP data */
2190 int pos /**< position in row vector to delete */
2191 )
2192{
2193 SCIP_COL* col;
2194 SCIP_Real val;
2195
2196 assert(row != NULL);
2197 assert(set != NULL);
2198 assert(0 <= pos && pos < row->len);
2199 assert(row->cols[pos] != NULL);
2200 assert((pos < row->nlpcols) == (row->linkpos[pos] >= 0 && row->cols[pos]->lppos >= 0));
2201
2202 col = row->cols[pos];
2203 val = row->vals[pos];
2204 assert((pos < row->nlpcols) == (col->lppos >= 0 && row->linkpos[pos] >= 0));
2205
2206 /*SCIPsetDebugMsg(set, "deleting coefficient %g * <%s> at position %d from row <%s>\n",
2207 val, SCIPvarGetName(col->var), pos, row->name);*/
2208
2209 if( row->nlocks > 0 )
2210 {
2211 SCIPerrorMessage("cannot delete a coefficient from the locked unmodifiable row <%s>\n", row->name);
2212 return SCIP_INVALIDDATA;
2213 }
2214
2215 if( row->linkpos[pos] == -1 )
2216 row->nunlinked--;
2217
2218 /* if column is a linked LP column, move last linked LP coefficient to position of empty slot (deleted coefficient) */
2219 if( pos < row->nlpcols )
2220 {
2221 rowMoveCoef(row, row->nlpcols-1, pos);
2222 assert(!row->lpcolssorted);
2223 row->nlpcols--;
2224 pos = row->nlpcols;
2225 }
2226
2227 /* move last coefficient to position of empty slot */
2228 rowMoveCoef(row, row->len-1, pos);
2229 row->len--;
2230
2231 /* update norms */
2232 rowDelNorms(row, set, col, val, FALSE, TRUE, TRUE);
2233
2234 coefChanged(row, col, lp);
2235
2236 /* issue row coefficient changed event */
2237 SCIP_CALL( rowEventCoefChanged(row, blkmem, set, eventqueue, col, val, 0.0) );
2238
2239 return SCIP_OKAY;
2240}
2241
2242/** changes a coefficient at given position of an LP row */
2243static
2245 SCIP_ROW* row, /**< LP row */
2246 BMS_BLKMEM* blkmem, /**< block memory */
2247 SCIP_SET* set, /**< global SCIP settings */
2248 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2249 SCIP_LP* lp, /**< current LP data */
2250 int pos, /**< position in row vector to change */
2251 SCIP_Real val /**< value of coefficient */
2252 )
2253{
2254 SCIP_COL* col;
2255
2256 assert(row != NULL);
2257 assert(0 <= pos && pos < row->len);
2258
2259 /*SCIPsetDebugMsg(set, "changing coefficient %g * <%s> at position %d of row <%s> to %g\n",
2260 row->vals[pos], SCIPvarGetName(row->cols[pos]->var), pos, row->name, val);*/
2261
2262 if( row->nlocks > 0 )
2263 {
2264 SCIPerrorMessage("cannot change a coefficient of the locked unmodifiable row <%s>\n", row->name);
2265 return SCIP_INVALIDDATA;
2266 }
2267
2268 /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
2269 val = SCIPsetIsIntegral(set, val) ? SCIPsetRound(set, val) : val;
2270 col = row->cols[pos];
2271 assert(row->cols[pos] != NULL);
2272
2273 if( SCIPsetIsZero(set, val) )
2274 {
2275 /* delete existing coefficient */
2276 SCIP_CALL( rowDelCoefPos(row, blkmem, set, eventqueue, lp, pos) );
2277 }
2278 else if( !SCIPsetIsEQ(set, row->vals[pos], val) )
2279 {
2280 SCIP_Real oldval;
2281
2282 oldval = row->vals[pos];
2283
2284 /* change existing coefficient */
2285 rowDelNorms(row, set, col, row->vals[pos], FALSE, FALSE, TRUE);
2286 row->vals[pos] = val;
2287 row->integral = row->integral && SCIPcolIsIntegral(col) && SCIPsetIsIntegral(set, val);
2288 rowAddNorms(row, set, col, row->vals[pos], TRUE);
2289 coefChanged(row, col, lp);
2290
2291 /* issue row coefficient changed event */
2292 SCIP_CALL( rowEventCoefChanged(row, blkmem, set, eventqueue, col, oldval, val) );
2293 }
2294
2295 return SCIP_OKAY;
2296}
2297
2298/** notifies LP row, that its sides were changed */
2299static
2301 SCIP_ROW* row, /**< LP row */
2302 SCIP_SET* set, /**< global SCIP settings */
2303 SCIP_LP* lp, /**< current LP data */
2304 SCIP_SIDETYPE sidetype /**< type of side: left or right hand side */
2305 )
2306{
2307 assert(row != NULL);
2308 assert(lp != NULL);
2309
2310 if( row->lpipos >= 0 )
2311 {
2312 /* insert row in the chgrows list (if not already there) */
2313 if( !row->lhschanged && !row->rhschanged )
2314 {
2315 SCIP_CALL( ensureChgrowsSize(lp, set, lp->nchgrows+1) );
2316 lp->chgrows[lp->nchgrows] = row;
2317 lp->nchgrows++;
2318 }
2319
2320 /* mark side change in the row */
2321 switch( sidetype )
2322 {
2323 case SCIP_SIDETYPE_LEFT:
2324 row->lhschanged = TRUE;
2325 break;
2327 row->rhschanged = TRUE;
2328 break;
2329 default:
2330 SCIPerrorMessage("unknown row side type\n");
2331 SCIPABORT();
2332 return SCIP_INVALIDDATA; /*lint !e527*/
2333 }
2334
2335 /* mark the current LP unflushed */
2336 lp->flushed = FALSE;
2337
2338 assert(lp->nchgrows > 0);
2339 }
2340
2341 return SCIP_OKAY;
2342}
2343
2344
2345
2346
2347/*
2348 * double linked coefficient matrix methods
2349 */
2350
2351/** insert column coefficients in corresponding rows */
2353 SCIP_COL* col, /**< column data */
2354 BMS_BLKMEM* blkmem, /**< block memory */
2355 SCIP_SET* set, /**< global SCIP settings */
2356 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2357 SCIP_LP* lp /**< current LP data */
2358 )
2359{
2360 int i;
2361
2362 assert(col != NULL);
2363 assert(col->var != NULL);
2364 assert(blkmem != NULL);
2365 assert(set != NULL);
2366 assert(lp != NULL);
2367
2368 if( col->nunlinked > 0 )
2369 {
2370 SCIPsetDebugMsg(set, "linking column <%s>\n", SCIPvarGetName(col->var));
2371
2372 /* unlinked rows can only be in the non-LP/unlinked rows part of the rows array */
2373 for( i = col->nlprows; i < col->len; ++i )
2374 {
2375 assert(!SCIPsetIsZero(set, col->vals[i]));
2376 if( col->linkpos[i] == -1 )
2377 {
2378 /* this call might swap the current row with the first non-LP/not linked row, but this is of no harm */
2379 SCIP_CALL( rowAddCoef(col->rows[i], blkmem, set, eventqueue, lp, col, col->vals[i], i) );
2380 }
2381 assert(col->rows[i]->cols[col->linkpos[i]] == col);
2382 assert(col->rows[i]->linkpos[col->linkpos[i]] == i);
2383 assert(col->nlprows == 0 || col->rows[col->nlprows-1]->cols[col->linkpos[col->nlprows-1]] == col);
2384 assert(col->nlprows == 0 || col->rows[col->nlprows-1]->linkpos[col->linkpos[col->nlprows-1]] == col->nlprows-1);
2385 }
2386 }
2387 assert(col->nunlinked == 0);
2388
2389 checkLinks(lp);
2390
2391 return SCIP_OKAY;
2392}
2393
2394/** removes column coefficients from corresponding rows */
2396 SCIP_COL* col, /**< column data */
2397 BMS_BLKMEM* blkmem, /**< block memory */
2398 SCIP_SET* set, /**< global SCIP settings */
2399 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2400 SCIP_LP* lp /**< current LP data */
2401 )
2402{
2403 int i;
2404
2405 assert(col != NULL);
2406 assert(col->var != NULL);
2407 assert(blkmem != NULL);
2408 assert(set != NULL);
2409 assert(lp != NULL);
2410
2411 if( col->nunlinked < col->len )
2412 {
2413 SCIPsetDebugMsg(set, "unlinking column <%s>\n", SCIPvarGetName(col->var));
2414 for( i = 0; i < col->len; ++i )
2415 {
2416 if( col->linkpos[i] >= 0 )
2417 {
2418 assert(col->rows[i]->cols[col->linkpos[i]] == col);
2419 SCIP_CALL( rowDelCoefPos(col->rows[i], blkmem, set, eventqueue, lp, col->linkpos[i]) );
2420 col->linkpos[i] = -1;
2421 col->nunlinked++;
2422 }
2423 }
2424 }
2425 assert(col->nunlinked == col->len);
2426
2427 checkLinks(lp);
2428
2429 return SCIP_OKAY;
2430}
2431
2432/** insert row coefficients in corresponding columns */
2434 SCIP_ROW* row, /**< row data */
2435 BMS_BLKMEM* blkmem, /**< block memory */
2436 SCIP_SET* set, /**< global SCIP settings */
2437 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2438 SCIP_LP* lp /**< current LP data */
2439 )
2440{
2441 int i;
2442
2443 assert(row != NULL);
2444 assert(blkmem != NULL);
2445 assert(set != NULL);
2446 assert(lp != NULL);
2447
2448 if( row->nunlinked > 0 )
2449 {
2450 SCIPsetDebugMsg(set, "linking row <%s>\n", row->name);
2451
2452 /* unlinked columns can only be in the non-LP/unlinked columns part of the cols array */
2453 for( i = row->nlpcols; i < row->len; ++i )
2454 {
2455 assert(!SCIPsetIsZero(set, row->vals[i]));
2456 if( row->linkpos[i] == -1 )
2457 {
2458 /* this call might swap the current column with the first non-LP/not linked column, but this is of no harm */
2459 SCIP_CALL( colAddCoef(row->cols[i], blkmem, set, eventqueue, lp, row, row->vals[i], i) );
2460 }
2461 assert(row->cols[i]->rows[row->linkpos[i]] == row);
2462 assert(row->cols[i]->linkpos[row->linkpos[i]] == i);
2463 assert(row->nlpcols == 0 || row->cols[row->nlpcols-1]->rows[row->linkpos[row->nlpcols-1]] == row);
2464 assert(row->nlpcols == 0 || row->cols[row->nlpcols-1]->linkpos[row->linkpos[row->nlpcols-1]] == row->nlpcols-1);
2465 }
2466 }
2467 assert(row->nunlinked == 0);
2468
2469 checkLinks(lp);
2470
2471 return SCIP_OKAY;
2472}
2473
2474/** removes row coefficients from corresponding columns */
2476 SCIP_ROW* row, /**< row data */
2477 SCIP_SET* set, /**< global SCIP settings */
2478 SCIP_LP* lp /**< current LP data */
2479 )
2480{
2481 int i;
2482
2483 assert(row != NULL);
2484 assert(set != NULL);
2485 assert(lp != NULL);
2486
2487 if( row->nunlinked < row->len )
2488 {
2489 SCIPsetDebugMsg(set, "unlinking row <%s>\n", row->name);
2490 for( i = 0; i < row->len; ++i )
2491 {
2492 if( row->linkpos[i] >= 0 )
2493 {
2494 assert(row->cols[i]->rows[row->linkpos[i]] == row);
2495 SCIP_CALL( colDelCoefPos(row->cols[i], set, lp, row->linkpos[i]) );
2496 row->nunlinked++;
2497 }
2498 }
2499 }
2500 assert(row->nunlinked == row->len);
2501
2502 return SCIP_OKAY;
2503}
2504
2505
2506
2507
2508/*
2509 * local LP parameter methods
2510 */
2511
2512/** sets parameter of type int in LP solver, ignoring unknown parameters */
2513static
2515 SCIP_LP* lp, /**< current LP data */
2516 SCIP_LPPARAM lpparam, /**< LP parameter */
2517 int value, /**< value to set parameter to */
2518 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2519 )
2520{
2521 SCIP_RETCODE retcode;
2522
2523 assert(lp != NULL);
2524 assert(success != NULL);
2525
2526 retcode = SCIPlpiSetIntpar(lp->lpi, lpparam, value);
2527
2528 /* check, if parameter is unknown */
2529 if( retcode == SCIP_PARAMETERUNKNOWN )
2530 {
2531 *success = FALSE;
2532 return SCIP_OKAY;
2533 }
2534 *success = TRUE;
2535
2536 return retcode;
2537}
2538
2539/** sets parameter of type SCIP_Bool in LP solver, ignoring unknown parameters */
2540static
2542 SCIP_LP* lp, /**< current LP data */
2543 SCIP_LPPARAM lpparam, /**< LP parameter */
2544 SCIP_Bool value, /**< value to set parameter to */
2545 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2546 )
2547{
2548 return lpSetIntpar(lp, lpparam, (int)value, success);
2549}
2550
2551/** sets parameter of type SCIP_Real in LP solver, ignoring unknown parameters */
2552static
2554 SCIP_LP* lp, /**< current LP data */
2555 SCIP_LPPARAM lpparam, /**< LP parameter */
2556 SCIP_Real value, /**< value to set parameter to */
2557 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2558 )
2559{
2560 SCIP_RETCODE retcode;
2561
2562 assert(lp != NULL);
2563 assert(success != NULL);
2564
2565 retcode = SCIPlpiSetRealpar(lp->lpi, lpparam, value);
2566
2567 /* check, if parameter is unknown */
2568 if( retcode == SCIP_PARAMETERUNKNOWN )
2569 {
2570 *success = FALSE;
2571 return SCIP_OKAY;
2572 }
2573 *success = TRUE;
2574
2575 return retcode;
2576}
2577
2578#ifndef NDEBUG
2579/** checks, that parameter of type int in LP solver has the given value, ignoring unknown parameters */
2580static
2582 SCIP_LP* lp, /**< current LP data */
2583 SCIP_LPPARAM lpparam, /**< LP parameter */
2584 int value /**< value parameter should have */
2585 )
2586{
2587 SCIP_RETCODE retcode;
2588 int lpivalue;
2589
2590 assert(lp != NULL);
2591
2592 retcode = SCIPlpiGetIntpar(lp->lpi, lpparam, &lpivalue);
2593
2594 /* ignore unknown parameter error */
2595 if( retcode == SCIP_PARAMETERUNKNOWN )
2596 return SCIP_OKAY;
2597
2598 /* check value */
2599 assert(lpivalue == value);
2600
2601 return retcode;
2602}
2603
2604/** checks, that parameter of type SCIP_Bool in LP solver has the given value, ignoring unknown parameters */
2605static
2607 SCIP_LP* lp, /**< current LP data */
2608 SCIP_LPPARAM lpparam, /**< LP parameter */
2609 SCIP_Bool value /**< value parameter should have */
2610 )
2611{
2612 return lpCheckIntpar(lp, lpparam, (int)value);
2613}
2614
2615/** checks, that parameter of type SCIP_Real in LP solver has the given value, ignoring unknown parameters */
2616static
2618 SCIP_LP* lp, /**< current LP data */
2619 SCIP_LPPARAM lpparam, /**< LP parameter */
2620 SCIP_Real value /**< value parameter should have */
2621 )
2622{
2623 SCIP_RETCODE retcode;
2624 SCIP_Real lpivalue;
2625
2626 assert(lp != NULL);
2627
2628 retcode = SCIPlpiGetRealpar(lp->lpi, lpparam, &lpivalue);
2629
2630 /* ignore unknown parameter error */
2631 if( retcode == SCIP_PARAMETERUNKNOWN )
2632 return SCIP_OKAY;
2633
2634 /* check value */
2635 assert(lpivalue == value); /*lint !e777*/
2636
2637 return retcode;
2638}
2639#else
2640#define lpCheckIntpar(lp, lpparam, value) SCIP_OKAY
2641#define lpCheckBoolpar(lp, lpparam, value) SCIP_OKAY
2642#define lpCheckRealpar(lp, lpparam, value) SCIP_OKAY
2643#endif
2644
2645/** should the objective limit of the LP solver be disabled */
2646#define lpCutoffDisabled(set,prob) (set->lp_disablecutoff == 1 || ((set->nactivepricers > 0 || !SCIPprobAllColsInLP(prob, set, lp)) && set->lp_disablecutoff == 2))
2647
2648/** sets the objective limit of the LP solver
2649 *
2650 * Note that we are always minimizing.
2651 */
2652static
2654 SCIP_LP* lp, /**< current LP data */
2655 SCIP_SET* set, /**< global SCIP settings */
2656 SCIP_PROB* prob, /**< problem data */
2657 SCIP_Real objlim, /**< new objective limit */
2658 SCIP_Bool* success /**< pointer to store whether the parameter was actually changed */
2659 )
2660{
2661 assert(lp != NULL);
2662 assert(set != NULL);
2663 assert(success != NULL);
2664
2665 *success = FALSE;
2666
2667 /* We disabled the objective limit in the LP solver or we want so solve exactly and thus cannot rely on the LP
2668 * solver's objective limit handling, so we make sure that the objective limit is inactive (infinity). */
2669 if( lpCutoffDisabled(set, prob) || set->misc_exactsolve )
2670 objlim = SCIPlpiInfinity(lp->lpi);
2671
2672 /* convert SCIP infinity value to lp-solver infinity value if necessary */
2673 if( SCIPsetIsInfinity(set, objlim) )
2674 objlim = SCIPlpiInfinity(lp->lpi);
2675
2677
2678 if( objlim != lp->lpiobjlim ) /*lint !e777*/
2679 {
2680 SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_OBJLIM, objlim, success) );
2681 if( *success )
2682 {
2683 SCIP_Real actualobjlim;
2684
2685 /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2686 SCIP_CALL( SCIPlpiGetRealpar(lp->lpi, SCIP_LPPAR_OBJLIM, &actualobjlim) );
2687 if( actualobjlim != lp->lpiobjlim ) /*lint !e777*/
2688 {
2689 /* mark the current solution invalid */
2690 lp->solved = FALSE;
2691 lp->primalfeasible = FALSE;
2692 lp->primalchecked = FALSE;
2693 lp->lpobjval = SCIP_INVALID;
2695 }
2696 lp->lpiobjlim = actualobjlim;
2697 }
2698 }
2699
2700 return SCIP_OKAY;
2701}
2702
2703/** sets the feasibility tolerance of the LP solver */
2704static
2706 SCIP_LP* lp, /**< current LP data */
2707 SCIP_Real feastol, /**< new feasibility tolerance */
2708 SCIP_Bool* success /**< pointer to store whether the parameter was actually changed */
2709 )
2710{
2711 assert(lp != NULL);
2712 assert(feastol >= 0.0);
2713 assert(success != NULL);
2714
2716
2717 if( feastol != lp->lpifeastol ) /*lint !e777*/
2718 {
2719 SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_FEASTOL, feastol, success) );
2720 if( *success )
2721 {
2722 SCIP_Real actualfeastol;
2723
2724 /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2725 SCIP_CALL( SCIPlpiGetRealpar(lp->lpi, SCIP_LPPAR_FEASTOL, &actualfeastol) );
2726 if( lp->nrows > 0 && actualfeastol < lp->lpifeastol )
2727 {
2728 /* mark the current solution invalid */
2729 lp->solved = FALSE;
2730 lp->primalfeasible = FALSE;
2731 lp->primalchecked = FALSE;
2732 lp->lpobjval = SCIP_INVALID;
2734 }
2735 else
2736 *success = FALSE;
2737 lp->lpifeastol = actualfeastol;
2738 }
2739 }
2740 else
2741 *success = FALSE;
2742
2743 return SCIP_OKAY;
2744}
2745
2746/** sets the reduced costs feasibility tolerance of the LP solver */
2747static
2749 SCIP_LP* lp, /**< current LP data */
2750 SCIP_Real dualfeastol, /**< new reduced costs feasibility tolerance */
2751 SCIP_Bool* success /**< pointer to store whether the parameter was actually changed */
2752 )
2753{
2754 assert(lp != NULL);
2755 assert(dualfeastol >= 0.0);
2756 assert(success != NULL);
2757
2759
2760 if( dualfeastol != lp->lpidualfeastol ) /*lint !e777*/
2761 {
2762 SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_DUALFEASTOL, dualfeastol, success) );
2763 if( *success )
2764 {
2765 SCIP_Real actualdualfeastol;
2766
2767 /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2768 SCIP_CALL( SCIPlpiGetRealpar(lp->lpi, SCIP_LPPAR_DUALFEASTOL, &actualdualfeastol) );
2769 if( lp->nrows > 0 && actualdualfeastol < lp->lpidualfeastol )
2770 {
2771 /* mark the current solution invalid */
2772 lp->solved = FALSE;
2773 lp->dualfeasible = FALSE;
2774 lp->dualchecked = FALSE;
2775 lp->lpobjval = SCIP_INVALID;
2777 }
2778 else
2779 *success = FALSE;
2780 lp->lpidualfeastol = actualdualfeastol;
2781 }
2782 }
2783 else
2784 *success = FALSE;
2785
2786 return SCIP_OKAY;
2787}
2788
2789/** sets the convergence tolerance used in barrier algorithm of the LP solver */
2790static
2792 SCIP_LP* lp, /**< current LP data */
2793 SCIP_Real barrierconvtol, /**< new convergence tolerance used in barrier algorithm */
2794 SCIP_Bool* success /**< pointer to store whether the parameter was actually changed */
2795 )
2796{
2797 assert(lp != NULL);
2798 assert(barrierconvtol >= 0.0);
2799 assert(success != NULL);
2800
2802
2803 if( barrierconvtol != lp->lpibarrierconvtol ) /*lint !e777*/
2804 {
2805 SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_BARRIERCONVTOL, barrierconvtol, success) );
2806 if( *success )
2807 {
2808 SCIP_Real actualbarrierconvtol;
2809
2810 /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2811 SCIP_CALL( SCIPlpiGetRealpar(lp->lpi, SCIP_LPPAR_BARRIERCONVTOL, &actualbarrierconvtol) );
2812 if( lp->nrows > 0 && actualbarrierconvtol < lp->lpibarrierconvtol
2814 {
2815 /* mark the current solution invalid */
2816 lp->solved = FALSE;
2817 lp->dualfeasible = FALSE;
2818 lp->dualchecked = FALSE;
2819 lp->lpobjval = SCIP_INVALID;
2821 }
2822 else
2823 *success = FALSE;
2824 lp->lpibarrierconvtol = actualbarrierconvtol;
2825 }
2826 }
2827 else
2828 *success = FALSE;
2829
2830 return SCIP_OKAY;
2831}
2832
2833/** sets the FROMSCRATCH setting of the LP solver */
2834static
2836 SCIP_LP* lp, /**< current LP data */
2837 SCIP_Bool fromscratch, /**< new FROMSCRATCH setting */
2838 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2839 )
2840{
2841 assert(lp != NULL);
2842 assert(success != NULL);
2843
2845
2846 if( fromscratch != lp->lpifromscratch )
2847 {
2848 SCIP_CALL( lpSetBoolpar(lp, SCIP_LPPAR_FROMSCRATCH, fromscratch, success) );
2849 if( *success )
2850 lp->lpifromscratch = fromscratch;
2851 }
2852 else
2853 *success = FALSE;
2854
2855 return SCIP_OKAY;
2856}
2857
2858/** sets the FASTMIP setting of the LP solver */
2859static
2861 SCIP_LP* lp, /**< current LP data */
2862 int fastmip, /**< new FASTMIP setting */
2863 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2864 )
2865{
2866 assert(lp != NULL);
2867 assert(success != NULL);
2868 assert(0 <= fastmip && fastmip <= 1);
2869
2871
2872 if( fastmip != lp->lpifastmip )
2873 {
2874 SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_FASTMIP, fastmip, success) );
2875 if( *success )
2876 {
2877 lp->lpifastmip = fastmip;
2878 lp->solved = FALSE;
2879 /* We might only set lp->solved to false if fastmip is turned off, since the latter should be the more
2880 * demanding setting; however, in the current code, this should have not effect. */
2881 }
2882 }
2883 else
2884 *success = FALSE;
2885
2886 return SCIP_OKAY;
2887}
2888
2889/** sets the SCALING setting of the LP solver */
2890static
2892 SCIP_LP* lp, /**< current LP data */
2893 int scaling, /**< new SCALING setting */
2894 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2895 )
2896{
2897 assert(lp != NULL);
2898 assert(success != NULL);
2899
2901
2902 if( scaling != lp->lpiscaling )
2903 {
2904 SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_SCALING, scaling, success) );
2905 if( *success )
2906 lp->lpiscaling = scaling;
2907 }
2908 else
2909 *success = FALSE;
2910
2911 return SCIP_OKAY;
2912}
2913
2914/** sets the number of THREADS of the LP solver */
2915static
2917 SCIP_LP* lp, /**< current LP data */
2918 int threads, /**< new number of threads used to solve the LP */
2919 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2920 )
2921{
2922 assert(lp != NULL);
2923 assert(success != NULL);
2924
2926
2927 if( threads != lp->lpithreads )
2928 {
2929 SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_THREADS, threads, success) );
2930 if( *success )
2931 lp->lpithreads = threads;
2932 }
2933 else
2934 *success = FALSE;
2935
2936 return SCIP_OKAY;
2937}
2938
2939/** sets the PRESOLVING setting of the LP solver */
2940static
2942 SCIP_LP* lp, /**< current LP data */
2943 SCIP_Bool presolving, /**< new PRESOLVING setting */
2944 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2945 )
2946{
2947 assert(lp != NULL);
2948 assert(success != NULL);
2949
2951
2952 if( presolving != lp->lpipresolving )
2953 {
2954 SCIP_CALL( lpSetBoolpar(lp, SCIP_LPPAR_PRESOLVING, presolving, success) );
2955 if( *success )
2956 lp->lpipresolving = presolving;
2957 }
2958 else
2959 *success = FALSE;
2960
2961 return SCIP_OKAY;
2962}
2963
2964/** sets the ROWREPSWITCH setting of the LP solver */
2965static
2967 SCIP_LP* lp, /**< current LP data */
2968 SCIP_Real rowrepswitch, /**< new ROWREPSWITCH value */
2969 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2970 )
2971{
2972 assert(lp != NULL);
2973 assert(success != NULL);
2974
2976
2977 if( rowrepswitch != lp->lpirowrepswitch ) /*lint !e777*/
2978 {
2979 SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_ROWREPSWITCH, rowrepswitch, success) );
2980 if( *success )
2981 lp->lpirowrepswitch = rowrepswitch;
2982 }
2983 else
2984 *success = FALSE;
2985
2986 return SCIP_OKAY;
2987}
2988
2989/** sets the iteration limit of the LP solver */
2990static
2992 SCIP_LP* lp, /**< current LP data */
2993 int itlim /**< maximal number of LP iterations to perform, or -1 for no limit */
2994 )
2995{
2996 SCIP_Bool success;
2997
2998 assert(lp != NULL);
2999 assert(itlim >= -1);
3000
3001 if( itlim == -1 )
3002 itlim = INT_MAX;
3003
3005
3006 if( itlim != lp->lpiitlim )
3007 {
3008 SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_LPITLIM, itlim, &success) );
3009 if( success )
3010 {
3011 if( itlim > lp->lpiitlim )
3012 {
3013 /* mark the current solution invalid */
3014 lp->solved = FALSE;
3015 lp->lpobjval = SCIP_INVALID;
3017 }
3018 lp->lpiitlim = itlim;
3019 }
3020 }
3021
3022 return SCIP_OKAY;
3023}
3024
3025/** sets the pricing strategy of the LP solver */
3026static
3028 SCIP_LP* lp, /**< current LP data */
3029 SCIP_PRICING pricing /**< pricing strategy */
3030 )
3031{
3032 SCIP_Bool success;
3033
3034 assert(lp != NULL);
3035
3037
3038 if( pricing != lp->lpipricing )
3039 {
3040 SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_PRICING, (int)pricing, &success) );
3041 if( success )
3042 lp->lpipricing = pricing;
3043 }
3044
3045 return SCIP_OKAY;
3046}
3047
3048/** sets the pricing strategy of the LP solver (given the character representation of the strategy) */
3049static
3051 SCIP_LP* lp, /**< current LP data */
3052 char pricingchar /**< character representing the pricing strategy */
3053 )
3054{
3055 SCIP_PRICING pricing;
3056
3057 switch( pricingchar )
3058 {
3059 case 'l':
3060 pricing = SCIP_PRICING_LPIDEFAULT;
3061 break;
3062 case 'a':
3063 pricing = SCIP_PRICING_AUTO;
3064 break;
3065 case 'f':
3066 pricing = SCIP_PRICING_FULL;
3067 break;
3068 case 'p':
3069 pricing = SCIP_PRICING_PARTIAL;
3070 break;
3071 case 's':
3072 pricing = SCIP_PRICING_STEEP;
3073 break;
3074 case 'q':
3075 pricing = SCIP_PRICING_STEEPQSTART;
3076 break;
3077 case 'd':
3078 pricing = SCIP_PRICING_DEVEX;
3079 break;
3080 default:
3081 SCIPerrorMessage("invalid LP pricing parameter <%c>\n", pricingchar);
3082 return SCIP_INVALIDDATA;
3083 }
3084
3085 SCIP_CALL( lpSetPricing(lp, pricing) );
3086
3087 return SCIP_OKAY;
3088}
3089
3090/** sets the verbosity of the LP solver */
3091static
3093 SCIP_LP* lp, /**< current LP data */
3094 SCIP_Bool lpinfo /**< should the LP solver display status messages? */
3095 )
3096{
3097 SCIP_Bool success;
3098
3099 assert(lp != NULL);
3100
3102
3103 if( lpinfo != lp->lpilpinfo )
3104 {
3105 SCIP_CALL( lpSetBoolpar(lp, SCIP_LPPAR_LPINFO, lpinfo, &success) );
3106 if( success )
3107 lp->lpilpinfo = lpinfo;
3108 }
3109
3110 return SCIP_OKAY;
3111}
3112
3113/** sets the CONDITIONLIMIT setting of the LP solver */
3114static
3116 SCIP_LP* lp, /**< current LP data */
3117 SCIP_Real condlimit, /**< new CONDITIONLIMIT value */
3118 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
3119 )
3120{
3121 assert(lp != NULL);
3122 assert(success != NULL);
3123
3125
3126 if( condlimit != lp->lpiconditionlimit ) /*lint !e777*/
3127 {
3128 SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_CONDITIONLIMIT, condlimit, success) );
3129 if( *success )
3130 lp->lpiconditionlimit = condlimit;
3131 }
3132 else
3133 *success = FALSE;
3134
3135 return SCIP_OKAY;
3136}
3137
3138/** sets the MARKOWITZ setting of the LP solver */
3139static
3141 SCIP_LP* lp, /**< current LP data */
3142 SCIP_Real threshhold, /**< new MARKOWITZ value */
3143 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
3144 )
3145{
3146 assert(lp != NULL);
3147 assert(success != NULL);
3148
3150
3151 if( threshhold != lp->lpimarkowitz ) /*lint !e777*/
3152 {
3153 SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_MARKOWITZ, threshhold, success) );
3154 if( *success )
3155 lp->lpimarkowitz = threshhold;
3156 }
3157 else
3158 *success = FALSE;
3159
3160 return SCIP_OKAY;
3161}
3162
3163/** sets the type of timer of the LP solver */
3164static
3166 SCIP_LP* lp, /**< current LP data */
3167 SCIP_CLOCKTYPE timing, /**< new timing value */
3168 SCIP_Bool enabled, /**< is timing enabled? */
3169 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
3170 )
3171{
3172 int lptiming;
3173
3174 assert(lp != NULL);
3175 assert(success != NULL);
3176 assert((int) SCIP_CLOCKTYPE_CPU == 1 && (int) SCIP_CLOCKTYPE_WALL == 2); /*lint !e506*//*lint !e1564*/
3177
3179
3180 if( !enabled )
3181 lptiming = 0;
3182 else
3183 lptiming = (int) timing;
3184
3185 if( lptiming != lp->lpitiming ) /*lint !e777*/
3186 {
3187 SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_TIMING, lptiming, success) );
3188 if( *success )
3189 lp->lpitiming = lptiming;
3190 }
3191 else
3192 *success = FALSE;
3193
3194 return SCIP_OKAY;
3195}
3196
3197/** sets the initial random seed of the LP solver */
3198static
3200 SCIP_LP* lp, /**< current LP data */
3201 int randomseed, /**< new initial random seed */
3202 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
3203 )
3204{
3205 assert(lp != NULL);
3206 assert(success != NULL);
3207
3208 /* we don't check this parameter because SoPlex will always return its current random seed, not the initial one */
3209
3210 if( randomseed == 0 )
3211 {
3212 lp->lpirandomseed = randomseed;
3213 *success = TRUE;
3214 }
3215 else if( randomseed != lp->lpirandomseed ) /*lint !e777*/
3216 {
3217 SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_RANDOMSEED, randomseed, success) );
3218 if( *success )
3219 lp->lpirandomseed = randomseed;
3220 }
3221 else
3222 *success = FALSE;
3223
3224 return SCIP_OKAY;
3225}
3226
3227/** sets the LP solution polishing method */
3228static
3230 SCIP_LP* lp, /**< current LP data */
3231 SCIP_Bool polishing, /**< LP solution polishing activated (0: disabled, 1: enabled) */
3232 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
3233 )
3234{
3235 assert(lp != NULL);
3236 assert(success != NULL);
3237
3238 if( polishing != lp->lpisolutionpolishing )
3239 {
3240 SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_POLISHING, (polishing ? 1 : 0), success) );
3241 if( *success )
3242 lp->lpisolutionpolishing = polishing;
3243 }
3244 else
3245 *success = FALSE;
3246
3247 return SCIP_OKAY;
3248}
3249
3250/** sets the LP refactorization interval */
3251static
3253 SCIP_LP* lp, /**< current LP data */
3254 int refactor, /**< LP refactorization interval (0: automatic) */
3255 SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
3256 )
3257{
3258 assert(lp != NULL);
3259 assert(success != NULL);
3260
3261 if( refactor != lp->lpirefactorinterval )
3262 {
3263 SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_REFACTOR, refactor, success) );
3264 if( *success )
3265 lp->lpirefactorinterval = refactor;
3266 }
3267 else
3268 *success = FALSE;
3269
3270 return SCIP_OKAY;
3271}
3272
3273
3274/*
3275 * Column methods
3276 */
3277
3278/** creates an LP column */
3280 SCIP_COL** col, /**< pointer to column data */
3281 BMS_BLKMEM* blkmem, /**< block memory */
3282 SCIP_SET* set, /**< global SCIP settings */
3283 SCIP_STAT* stat, /**< problem statistics */
3284 SCIP_VAR* var, /**< variable, this column represents */
3285 int len, /**< number of nonzeros in the column */
3286 SCIP_ROW** rows, /**< array with rows of column entries */
3287 SCIP_Real* vals, /**< array with coefficients of column entries */
3288 SCIP_Bool removable /**< should the column be removed from the LP due to aging or cleanup? */
3289 )
3290{
3291 int i;
3292
3293 assert(col != NULL);
3294 assert(blkmem != NULL);
3295 assert(set != NULL);
3296 assert(stat != NULL);
3297 assert(var != NULL);
3298 assert(len >= 0);
3299 assert(len == 0 || (rows != NULL && vals != NULL));
3300
3301 SCIP_ALLOC( BMSallocBlockMemory(blkmem, col) );
3302
3303 if( len > 0 )
3304 {
3305 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*col)->rows, rows, len) );
3306 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*col)->vals, vals, len) );
3307 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*col)->linkpos, len) );
3308
3309 for( i = 0; i < len; ++i )
3310 {
3311 assert(rows[i] != NULL);
3312 assert(!SCIPsetIsZero(set, vals[i]));
3313 (*col)->linkpos[i] = -1;
3314 }
3315 }
3316 else
3317 {
3318 (*col)->rows = NULL;
3319 (*col)->vals = NULL;
3320 (*col)->linkpos = NULL;
3321 }
3322
3323 (*col)->var = var;
3324 (*col)->obj = SCIPvarGetObj(var);
3325 (*col)->unchangedobj = SCIPvarGetUnchangedObj(var);
3326 (*col)->lb = SCIPvarGetLbLocal(var);
3327 (*col)->ub = SCIPvarGetUbLocal(var);
3328 (*col)->flushedobj = 0.0;
3329 (*col)->flushedlb = 0.0;
3330 (*col)->flushedub = 0.0;
3331 (*col)->index = stat->ncolidx;
3332 SCIPstatIncrement(stat, set, ncolidx);
3333 (*col)->size = len;
3334 (*col)->len = len;
3335 (*col)->nlprows = 0;
3336 (*col)->nunlinked = len;
3337 (*col)->lppos = -1;
3338 (*col)->lpipos = -1;
3339 (*col)->lpdepth = -1;
3340 (*col)->primsol = 0.0;
3341 (*col)->redcost = SCIP_INVALID;
3342 (*col)->farkascoef = SCIP_INVALID;
3343 (*col)->minprimsol = (*col)->ub;
3344 (*col)->maxprimsol = (*col)->lb;
3345 (*col)->sbdown = SCIP_INVALID;
3346 (*col)->sbup = SCIP_INVALID;
3347 (*col)->sbsolval = SCIP_INVALID;
3348 (*col)->sblpobjval = SCIP_INVALID;
3349 (*col)->sbnode = -1;
3350 (*col)->validredcostlp = -1;
3351 (*col)->validfarkaslp = -1;
3352 (*col)->validsblp = -1;
3353 (*col)->sbitlim = -1;
3354 (*col)->nsbcalls = 0;
3355 (*col)->age = 0;
3356 (*col)->obsoletenode = -1;
3357 (*col)->var_probindex = SCIPvarGetProbindex(var);
3358 (*col)->basisstatus = SCIP_BASESTAT_ZERO; /*lint !e641*/
3359 (*col)->lprowssorted = TRUE;
3360 (*col)->nonlprowssorted = (len <= 1);
3361 (*col)->objchanged = FALSE;
3362 (*col)->lbchanged = FALSE;
3363 (*col)->ubchanged = FALSE;
3364 (*col)->coefchanged = FALSE;
3365 (*col)->integral = SCIPvarIsIntegral(var);
3366 (*col)->removable = removable;
3367 (*col)->sbdownvalid = FALSE;
3368 (*col)->sbupvalid = FALSE;
3369 (*col)->lazylb = SCIPvarGetLbLazy(var);
3370 (*col)->lazyub = SCIPvarGetUbLazy(var);
3371 (*col)->storedsolvals = NULL;
3372
3373 return SCIP_OKAY;
3374}
3375
3376/** frees an LP column */
3378 SCIP_COL** col, /**< pointer to LP column */
3379 BMS_BLKMEM* blkmem, /**< block memory */
3380 SCIP_SET* set, /**< global SCIP settings */
3381 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3382 SCIP_LP* lp /**< current LP data */
3383 )
3384{
3385 assert(blkmem != NULL);
3386 assert(col != NULL);
3387 assert(*col != NULL);
3388 assert((*col)->var != NULL);
3389 assert(SCIPvarGetStatus((*col)->var) == SCIP_VARSTATUS_COLUMN);
3390 assert(&(*col)->var->data.col == col); /* SCIPcolFree() has to be called from SCIPvarFree() */
3391 assert((*col)->lppos == -1);
3392 assert((*col)->lpipos == -1);
3393
3394 /* remove column indices from corresponding rows */
3395 SCIP_CALL( colUnlink(*col, blkmem, set, eventqueue, lp) );
3396
3397 BMSfreeBlockMemoryNull(blkmem, &(*col)->storedsolvals);
3398 BMSfreeBlockMemoryArrayNull(blkmem, &(*col)->rows, (*col)->size);
3399 BMSfreeBlockMemoryArrayNull(blkmem, &(*col)->vals, (*col)->size);
3400 BMSfreeBlockMemoryArrayNull(blkmem, &(*col)->linkpos, (*col)->size);
3401 BMSfreeBlockMemory(blkmem, col);
3402
3403 return SCIP_OKAY;
3404}
3405
3406/** output column to file stream */
3408 SCIP_COL* col, /**< LP column */
3409 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3410 FILE* file /**< output file (or NULL for standard output) */
3411 )
3412{
3413 int r;
3414
3415 assert(col != NULL);
3416 assert(col->var != NULL);
3417
3418 /* print bounds */
3419 SCIPmessageFPrintInfo(messagehdlr, file, "(obj: %.15g) [%.15g,%.15g], ", col->obj, col->lb, col->ub);
3420
3421 /* print coefficients */
3422 if( col->len == 0 )
3423 SCIPmessageFPrintInfo(messagehdlr, file, "<empty>");
3424 for( r = 0; r < col->len; ++r )
3425 {
3426 assert(col->rows[r] != NULL);
3427 assert(col->rows[r]->name != NULL);
3428 SCIPmessageFPrintInfo(messagehdlr, file, "%+.15g<%s> ", col->vals[r], col->rows[r]->name);
3429 }
3430 SCIPmessageFPrintInfo(messagehdlr, file, "\n");
3431}
3432
3433/** sorts column entries such that LP rows precede non-LP rows and inside both parts lower row indices precede higher ones
3434 */
3436 SCIP_COL* col /**< column to be sorted */
3437 )
3438{
3439 /* sort LP rows */
3440 colSortLP(col);
3441
3442 /* sort non-LP rows */
3443 colSortNonLP(col);
3444}
3445
3446/** adds a previously non existing coefficient to an LP column */
3448 SCIP_COL* col, /**< LP column */
3449 BMS_BLKMEM* blkmem, /**< block memory */
3450 SCIP_SET* set, /**< global SCIP settings */
3451 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3452 SCIP_LP* lp, /**< current LP data */
3453 SCIP_ROW* row, /**< LP row */
3454 SCIP_Real val /**< value of coefficient */
3455 )
3456{
3457 assert(lp != NULL);
3458 assert(!lp->diving);
3459
3460 SCIP_CALL( colAddCoef(col, blkmem, set, eventqueue, lp, row, val, -1) );
3461
3462 checkLinks(lp);
3463
3464 return SCIP_OKAY;
3465}
3466
3467/** deletes existing coefficient from column */
3469 SCIP_COL* col, /**< column to be changed */
3470 BMS_BLKMEM* blkmem, /**< block memory */
3471 SCIP_SET* set, /**< global SCIP settings */
3472 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3473 SCIP_LP* lp, /**< current LP data */
3474 SCIP_ROW* row /**< coefficient to be deleted */
3475 )
3476{
3477 int pos;
3478
3479 assert(col != NULL);
3480 assert(col->var != NULL);
3481 assert(lp != NULL);
3482 assert(!lp->diving);
3483 assert(row != NULL);
3484
3485 /* search the position of the row in the column's row vector */
3486 pos = colSearchCoef(col, row);
3487 if( pos == -1 )
3488 {
3489 SCIPerrorMessage("coefficient for row <%s> doesn't exist in column <%s>\n", row->name, SCIPvarGetName(col->var));
3490 return SCIP_INVALIDDATA;
3491 }
3492 assert(0 <= pos && pos < col->len);
3493 assert(col->rows[pos] == row);
3494
3495 /* if row knows of the column, remove the column from the row's col vector */
3496 if( col->linkpos[pos] >= 0 )
3497 {
3498 assert(row->cols[col->linkpos[pos]] == col);
3499 assert(row->cols_index[col->linkpos[pos]] == col->index);
3500 assert(SCIPsetIsEQ(set, row->vals[col->linkpos[pos]], col->vals[pos]));
3501 SCIP_CALL( rowDelCoefPos(row, blkmem, set, eventqueue, lp, col->linkpos[pos]) );
3502 }
3503
3504 /* delete the row from the column's row vector */
3505 SCIP_CALL( colDelCoefPos(col, set, lp, pos) );
3506
3507 checkLinks(lp);
3508
3509 return SCIP_OKAY;
3510}
3511
3512/** changes or adds a coefficient to an LP column */
3514 SCIP_COL* col, /**< LP column */
3515 BMS_BLKMEM* blkmem, /**< block memory */
3516 SCIP_SET* set, /**< global SCIP settings */
3517 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3518 SCIP_LP* lp, /**< current LP data */
3519 SCIP_ROW* row, /**< LP row */
3520 SCIP_Real val /**< value of coefficient */
3521 )
3522{
3523 int pos;
3524
3525 assert(col != NULL);
3526 assert(lp != NULL);
3527 assert(!lp->diving);
3528 assert(row != NULL);
3529
3530 /* search the position of the row in the column's row vector */
3531 pos = colSearchCoef(col, row);
3532
3533 /* check, if row already exists in the column's row vector */
3534 if( pos == -1 )
3535 {
3536 /* add previously not existing coefficient */
3537 SCIP_CALL( colAddCoef(col, blkmem, set, eventqueue, lp, row, val, -1) );
3538 }
3539 else
3540 {
3541 /* modify already existing coefficient */
3542 assert(0 <= pos && pos < col->len);
3543 assert(col->rows[pos] == row);
3544
3545 /* if row knows of the column, change the corresponding coefficient in the row */
3546 if( col->linkpos[pos] >= 0 )
3547 {
3548 assert(row->cols[col->linkpos[pos]] == col);
3549 assert(row->cols_index[col->linkpos[pos]] == col->index);
3550 assert(SCIPsetIsEQ(set, row->vals[col->linkpos[pos]], col->vals[pos]));
3551 SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, col->linkpos[pos], val) );
3552 }
3553
3554 /* change the coefficient in the column */
3555 SCIP_CALL( colChgCoefPos(col, set, lp, pos, val) );
3556 }
3557
3558 checkLinks(lp);
3559
3560 return SCIP_OKAY;
3561}
3562
3563/** increases value of an existing or non-existing coefficient in an LP column */
3565 SCIP_COL* col, /**< LP column */
3566 BMS_BLKMEM* blkmem, /**< block memory */
3567 SCIP_SET* set, /**< global SCIP settings */
3568 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3569 SCIP_LP* lp, /**< current LP data */
3570 SCIP_ROW* row, /**< LP row */
3571 SCIP_Real incval /**< value to add to the coefficient */
3572 )
3573{
3574 int pos;
3575
3576 assert(col != NULL);
3577 assert(lp != NULL);
3578 assert(!lp->diving);
3579 assert(row != NULL);
3580
3581 if( SCIPsetIsZero(set, incval) )
3582 return SCIP_OKAY;
3583
3584 /* search the position of the row in the column's row vector */
3585 pos = colSearchCoef(col, row);
3586
3587 /* check, if row already exists in the column's row vector */
3588 if( pos == -1 )
3589 {
3590 /* add previously not existing coefficient */
3591 SCIP_CALL( colAddCoef(col, blkmem, set, eventqueue, lp, row, incval, -1) );
3592 }
3593 else
3594 {
3595 /* modify already existing coefficient */
3596 assert(0 <= pos && pos < col->len);
3597 assert(col->rows[pos] == row);
3598
3599 /* if row knows of the column, change the corresponding coefficient in the row */
3600 if( col->linkpos[pos] >= 0 )
3601 {
3602 assert(row->cols[col->linkpos[pos]] == col);
3603 assert(row->cols_index[col->linkpos[pos]] == col->index);
3604 assert(SCIPsetIsEQ(set, row->vals[col->linkpos[pos]], col->vals[pos]));
3605 SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, col->linkpos[pos], col->vals[pos] + incval) );
3606 }
3607
3608 /* change the coefficient in the column */
3609 SCIP_CALL( colChgCoefPos(col, set, lp, pos, col->vals[pos] + incval) );
3610 }
3611
3612 checkLinks(lp);
3613
3614 return SCIP_OKAY;
3615}
3616
3617/** insert column in the chgcols list (if not already there) */
3618static
3620 SCIP_COL* col, /**< LP column to change */
3621 SCIP_SET* set, /**< global SCIP settings */
3622 SCIP_LP* lp /**< current LP data */
3623 )
3624{
3625 if( !col->objchanged && !col->lbchanged && !col->ubchanged )
3626 {
3627 SCIP_CALL( ensureChgcolsSize(lp, set, lp->nchgcols+1) );
3628 lp->chgcols[lp->nchgcols] = col;
3629 lp->nchgcols++;
3630 }
3631
3632 /* mark the current LP unflushed */
3633 lp->flushed = FALSE;
3634
3635 return SCIP_OKAY;
3636}
3637
3638/** Is the new value reliable or may we have cancellation?
3639 *
3640 * @note: Here we only consider cancellations which can occur during decreasing the oldvalue to newvalue; not the
3641 * cancellations which can occur during increasing the oldvalue to the newvalue
3642 */
3643static
3645 SCIP_SET* set, /**< global SCIP settings */
3646 SCIP_Real newvalue, /**< new value */
3647 SCIP_Real oldvalue /**< old reliable value */
3648 )
3649{
3650 SCIP_Real quotient;
3651
3652 assert(set != NULL);
3653 assert(oldvalue != SCIP_INVALID); /*lint !e777*/
3654
3655 quotient = (REALABS(newvalue)+1.0) / (REALABS(oldvalue) + 1.0);
3656
3657 return SCIPsetIsZero(set, quotient);
3658}
3659
3660/** update norms of objective function vector */
3661static
3663 SCIP_LP* lp, /**< current LP data */
3664 SCIP_SET* set, /**< global SCIP settings */
3665 SCIP_Real oldobj, /**< old objective value of variable */
3666 SCIP_Real newobj /**< new objective value of variable */
3667 )
3668{
3669 if( REALABS(newobj) != REALABS(oldobj) ) /*lint !e777*/
3670 {
3671 if( !lp->objsqrnormunreliable )
3672 {
3673 SCIP_Real oldvalue;
3674
3675 oldvalue = lp->objsqrnorm;
3676 lp->objsqrnorm += SQR(newobj) - SQR(oldobj);
3677
3678 /* due to numerical cancellations, we recalculate lp->objsqrnorm using all variables */
3679 if( SCIPsetIsLT(set, lp->objsqrnorm, 0.0) || isNewValueUnreliable(set, lp->objsqrnorm, oldvalue) )
3681 else
3682 {
3683 assert(SCIPsetIsGE(set, lp->objsqrnorm, 0.0));
3684
3685 /* due to numerical troubles it still can appear that lp->objsqrnorm is a little bit smaller than 0 */
3686 lp->objsqrnorm = MAX(lp->objsqrnorm, 0.0);
3687
3688 assert(lp->objsqrnorm >= 0.0);
3689 }
3690 }
3691
3692 lp->objsumnorm += REALABS(newobj) - REALABS(oldobj);
3693 lp->objsumnorm = MAX(lp->objsumnorm, 0.0);
3694 }
3695}
3696
3697/** changes objective value of column */
3699 SCIP_COL* col, /**< LP column to change */
3700 SCIP_SET* set, /**< global SCIP settings */
3701 SCIP_LP* lp, /**< current LP data */
3702 SCIP_Real newobj /**< new objective value */
3703 )
3704{
3705 assert(col != NULL);
3706 assert(col->var != NULL);
3708 assert(SCIPvarGetCol(col->var) == col);
3709 assert(lp != NULL);
3710
3711 SCIPsetDebugMsg(set, "changing objective value of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->obj, newobj);
3712
3713 /* only add actual changes */
3714 if( !SCIPsetIsEQ(set, col->obj, newobj) )
3715 {
3716 /* only variables with a real position in the LPI can be inserted */
3717 if( col->lpipos >= 0 )
3718 {
3719 /* insert column in the chgcols list (if not already there) */
3720 SCIP_CALL( insertColChgcols(col, set, lp) );
3721
3722 /* mark objective value change in the column */
3723 col->objchanged = TRUE;
3724
3725 assert(lp->nchgcols > 0);
3726 }
3727 /* in any case, when the sign of the objective (and thereby the best bound) changes, the variable has to enter the
3728 * LP and the LP has to be flushed
3729 */
3730 else if( (col->obj < 0.0 && newobj >= 0.0 && SCIPsetIsZero(set, col->ub))
3731 || (col->obj >= 0.0 && newobj < 0.0 && SCIPsetIsZero(set, col->lb)) )
3732 {
3733 /* mark the LP unflushed */
3734 lp->flushed = FALSE;
3735 }
3736 }
3737
3738 /* store new objective function value */
3739 col->obj = newobj;
3740
3741 /* update original objective value, as long as we are not in diving or probing and changed objective values */
3742 if( !lp->divingobjchg )
3743 {
3744 SCIP_Real oldobj = col->unchangedobj;
3745
3746 assert(SCIPsetIsEQ(set, newobj, SCIPvarGetUnchangedObj(col->var)));
3747 col->unchangedobj = newobj;
3748
3749 /* update the objective function vector norms */
3750 lpUpdateObjNorms(lp, set, oldobj, newobj);
3751 }
3752
3753 return SCIP_OKAY;
3754}
3755
3756/** changes lower bound of column */
3758 SCIP_COL* col, /**< LP column to change */
3759 SCIP_SET* set, /**< global SCIP settings */
3760 SCIP_LP* lp, /**< current LP data */
3761 SCIP_Real newlb /**< new lower bound value */
3762 )
3763{
3764 assert(col != NULL);
3765 assert(col->var != NULL);
3767 assert(SCIPvarGetCol(col->var) == col);
3768 assert(lp != NULL);
3769
3770 SCIPsetDebugMsg(set, "changing lower bound of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->lb, newlb);
3771
3772 /* only add actual changes */
3773 if( !SCIPsetIsEQ(set, col->lb, newlb) )
3774 {
3775 /* only variables with a real position in the LPI can be inserted */
3776 if( col->lpipos >= 0 )
3777 {
3778 /* insert column in the chgcols list (if not already there) */
3779 SCIP_CALL( insertColChgcols(col, set, lp) );
3780
3781 /* mark bound change in the column */
3782 col->lbchanged = TRUE;
3783
3784 assert(lp->nchgcols > 0);
3785 }
3786 /* in any case, when the best bound is zero and gets changed, the variable has to enter the LP and the LP has to be
3787 * flushed
3788 */
3789 else if( col->obj >= 0.0 && SCIPsetIsZero(set, col->lb) )
3790 {
3791 /* mark the LP unflushed */
3792 lp->flushed = FALSE;
3793 }
3794 }
3795
3796 col->lb = newlb;
3797
3798 return SCIP_OKAY;
3799}
3800
3801/** changes upper bound of column */
3803 SCIP_COL* col, /**< LP column to change */
3804 SCIP_SET* set, /**< global SCIP settings */
3805 SCIP_LP* lp, /**< current LP data */
3806 SCIP_Real newub /**< new upper bound value */
3807 )
3808{
3809 assert(col != NULL);
3810 assert(col->var != NULL);
3812 assert(SCIPvarGetCol(col->var) == col);
3813 assert(lp != NULL);
3814
3815 SCIPsetDebugMsg(set, "changing upper bound of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->ub, newub);
3816
3817 /* only add actual changes */
3818 if( !SCIPsetIsEQ(set, col->ub, newub) )
3819 {
3820 /* only variables with a real position in the LPI can be inserted */
3821 if( col->lpipos >= 0 )
3822 {
3823 /* insert column in the chgcols list (if not already there) */
3824 SCIP_CALL( insertColChgcols(col, set, lp) );
3825
3826 /* mark bound change in the column */
3827 col->ubchanged = TRUE;
3828
3829 assert(lp->nchgcols > 0);
3830 }
3831 /* in any case, when the best bound is zero and gets changed, the variable has to enter the LP and the LP has to be
3832 * flushed
3833 */
3834 else if( col->obj < 0.0 && SCIPsetIsZero(set, col->ub) )
3835 {
3836 /* mark the LP unflushed */
3837 lp->flushed = FALSE;
3838 }
3839 }
3840
3841 col->ub = newub;
3842
3843 return SCIP_OKAY;
3844}
3845
3846/** calculates the reduced costs of a column using the given dual solution vector */
3848 SCIP_COL* col, /**< LP column */
3849 SCIP_Real* dualsol /**< dual solution vector for current LP rows */
3850 )
3851{
3852 SCIP_ROW* row;
3853 SCIP_Real redcost;
3854 int i;
3855
3856 assert(col != NULL);
3858 assert(SCIPvarGetCol(col->var) == col);
3859 assert(dualsol != NULL);
3860
3861 redcost = col->obj;
3862 for( i = 0; i < col->nlprows; ++i )
3863 {
3864 row = col->rows[i];
3865 assert(row != NULL);
3866 assert(row->lppos >= 0);
3867 redcost -= col->vals[i] * dualsol[row->lppos];
3868 }
3869
3870 if( col->nunlinked > 0 )
3871 {
3872 for( i = col->nlprows; i < col->len; ++i )
3873 {
3874 row = col->rows[i];
3875 assert(row != NULL);
3876 assert(row->lppos == -1 || col->linkpos[i] == -1);
3877 if( row->lppos >= 0 )
3878 redcost -= col->vals[i] * dualsol[row->lppos];
3879 }
3880 }
3881#ifndef NDEBUG
3882 else
3883 {
3884 for( i = col->nlprows; i < col->len; ++i )
3885 {
3886 row = col->rows[i];
3887 assert(row != NULL);
3888 assert(row->lppos == -1);
3889 assert(col->linkpos[i] >= 0);
3890 }
3891 }
3892#endif
3893
3894 return redcost;
3895}
3896
3897/** calculates the reduced costs of a column using the dual solution stored in the rows */
3898static
3900 SCIP_COL* col /**< LP column */
3901 )
3902{
3903 SCIP_ROW* row;
3904 SCIP_Real redcost;
3905 int i;
3906
3907 assert(col != NULL);
3909 assert(SCIPvarGetCol(col->var) == col);
3910
3911 redcost = col->obj;
3912 for( i = 0; i < col->nlprows; ++i )
3913 {
3914 row = col->rows[i];
3915 assert(row != NULL);
3916 assert(row->dualsol != SCIP_INVALID); /*lint !e777*/
3917 assert(row->lppos >= 0);
3918 assert(col->linkpos[i] >= 0);
3919 redcost -= col->vals[i] * row->dualsol;
3920 }
3921
3922 if( col->nunlinked > 0 )
3923 {
3924 for( i = col->nlprows; i < col->len; ++i )
3925 {
3926 row = col->rows[i];
3927 assert(row != NULL);
3928 assert(row->lppos >= 0 || row->dualsol == 0.0);
3929 assert(row->lppos == -1 || col->linkpos[i] == -1);
3930 if( row->lppos >= 0 )
3931 redcost -= col->vals[i] * row->dualsol;
3932 }
3933 }
3934#ifndef NDEBUG
3935 else
3936 {
3937 for( i = col->nlprows; i < col->len; ++i )
3938 {
3939 row = col->rows[i];
3940 assert(row != NULL);
3941 assert(row->dualsol == 0.0);
3942 assert(row->lppos == -1);
3943 assert(col->linkpos[i] >= 0);
3944 }
3945 }
3946#endif
3947
3948 return redcost;
3949}
3950
3951/** gets the reduced costs of a column in last LP or after recalculation */
3953 SCIP_COL* col, /**< LP column */
3954 SCIP_STAT* stat, /**< problem statistics */
3955 SCIP_LP* lp /**< current LP data */
3956 )
3957{
3958 assert(col != NULL);
3959 assert(stat != NULL);
3960 assert(lp != NULL);
3961 assert(col->validredcostlp <= stat->lpcount);
3962 assert(lp->validsollp == stat->lpcount);
3963
3964 if( col->validredcostlp < stat->lpcount )
3965 {
3966 col->redcost = colCalcInternalRedcost(col);
3967 col->validredcostlp = stat->lpcount;
3968 }
3969 assert(col->validredcostlp == stat->lpcount);
3970 assert(col->redcost != SCIP_INVALID); /*lint !e777*/
3971
3972 return col->redcost;
3973}
3974
3975/** gets the feasibility of (the dual row of) a column in last LP or after recalculation */
3977 SCIP_COL* col, /**< LP column */
3978 SCIP_SET* set, /**< global SCIP settings */
3979 SCIP_STAT* stat, /**< problem statistics */
3980 SCIP_LP* lp /**< current LP data */
3981 )
3982{
3983 assert(col != NULL);
3984 assert(set != NULL);
3985 assert(stat != NULL);
3986 assert(lp != NULL);
3987 assert(lp->validsollp == stat->lpcount);
3988
3989 /* A column's reduced cost is defined as
3990 * redcost = obj - activity, activity = y^T * col. (activity = obj - redcost)
3991 * The activity is equal to the activity of the corresponding row in the dual LP.
3992 * The column's feasibility is the feasibility of the corresponding row in the dual LP.
3993 * The sides of the dual row depend on the bounds of the column:
3994 * - lb == ub : dual row is a free row with infinite sides
3995 * - 0 <= lb < ub: activity <= obj => 0 <= redcost
3996 * - lb < 0 < ub: obj <= activity <= obj => 0 <= redcost <= 0
3997 * - lb < ub <= 0: obj <= activity => redcost <= 0
3998 */
3999 if( SCIPsetIsEQ(set, col->lb, col->ub) )
4000 {
4001 /* dual row is free */
4002 return SCIPsetInfinity(set);
4003 }
4004 else
4005 {
4006 SCIP_Real redcost;
4007
4008 /* calculate reduced costs */
4009 redcost = SCIPcolGetRedcost(col, stat, lp);
4010
4011 if( !SCIPsetIsNegative(set, col->lb) )
4012 {
4013 /* dual row is activity <= obj <=> redcost >= 0 */
4014 return redcost;
4015 }
4016 else if( SCIPsetIsPositive(set, col->ub) )
4017 {
4018 /* dual row is activity == obj <=> redcost == 0 */
4019 return -REALABS(redcost);
4020 }
4021 else
4022 {
4023 /* dual row is activity >= obj <=> redcost <= 0 */
4024 return -redcost;
4025 }
4026 }
4027}
4028
4029/** calculates the Farkas coefficient y^T A_i of a column i using the given dual Farkas vector y */
4031 SCIP_COL* col, /**< LP column */
4032 SCIP_Real* dualfarkas /**< dense dual Farkas vector for current LP rows */
4033 )
4034{
4035 SCIP_ROW* row;
4036 SCIP_Real farkas;
4037 int i;
4038
4039 assert(col != NULL);
4041 assert(SCIPvarGetCol(col->var) == col);
4042 assert(dualfarkas != NULL);
4043
4044 farkas = 0.0;
4045 for( i = 0; i < col->nlprows; ++i )
4046 {
4047 row = col->rows[i];
4048 assert(row != NULL);
4049 assert(row->lppos >= 0);
4050 farkas += col->vals[i] * dualfarkas[row->lppos];
4051 }
4052
4053 if( col->nunlinked > 0 )
4054 {
4055 for( i = col->nlprows; i < col->len; ++i )
4056 {
4057 row = col->rows[i];
4058 assert(row != NULL);
4059 assert(row->lppos == -1 || col->linkpos[i] == -1);
4060 if( row->lppos >= 0 )
4061 farkas += col->vals[i] * dualfarkas[row->lppos];
4062 }
4063 }
4064#ifndef NDEBUG
4065 else
4066 {
4067 for( i = col->nlprows; i < col->len; ++i )
4068 {
4069 row = col->rows[i];
4070 assert(row != NULL);
4071 assert(row->lppos == -1);
4072 assert(col->linkpos[i] >= 0);
4073 }
4074 }
4075#endif
4076
4077 return farkas;
4078}
4079
4080/** gets the Farkas coefficient y^T A_i of a column i in last LP (which must be infeasible) */
4081static
4083 SCIP_COL* col /**< LP column */
4084 )
4085{
4086 SCIP_ROW* row;
4087 SCIP_Real farkas;
4088 int i;
4089
4090 assert(col != NULL);
4092 assert(SCIPvarGetCol(col->var) == col);
4093
4094 farkas = 0.0;
4095 for( i = 0; i < col->nlprows; ++i )
4096 {
4097 row = col->rows[i];
4098 assert(row != NULL);
4099 assert(row->dualfarkas != SCIP_INVALID); /*lint !e777*/
4100 assert(row->lppos >= 0);
4101 assert(col->linkpos[i] >= 0);
4102 farkas += col->vals[i] * row->dualfarkas;
4103 }
4104
4105 if( col->nunlinked > 0 )
4106 {
4107 for( i = col->nlprows; i < col->len; ++i )
4108 {
4109 row = col->rows[i];
4110 assert(row != NULL);
4111 assert(row->lppos >= 0 || row->dualfarkas == 0.0);
4112 assert(row->lppos == -1 || col->linkpos[i] == -1);
4113 if( row->lppos >= 0 )
4114 farkas += col->vals[i] * row->dualfarkas;
4115 }
4116 }
4117#ifndef NDEBUG
4118 else
4119 {
4120 for( i = col->nlprows; i < col->len; ++i )
4121 {
4122 row = col->rows[i];
4123 assert(row != NULL);
4124 assert(row->dualfarkas == 0.0);
4125 assert(row->lppos == -1);
4126 assert(col->linkpos[i] >= 0);
4127 }
4128 }
4129#endif
4130
4131 return farkas;
4132}
4133
4134/** gets the Farkas coefficient of a column in last LP (which must be infeasible) */
4136 SCIP_COL* col, /**< LP column */
4137 SCIP_STAT* stat, /**< problem statistics */
4138 SCIP_LP* lp /**< current LP data */
4139 )
4140{
4141 assert(col != NULL);
4142 assert(stat != NULL);
4143 assert(lp != NULL);
4144 assert(col->validfarkaslp <= stat->lpcount);
4145 assert(lp->validfarkaslp == stat->lpcount);
4146
4147 if( col->validfarkaslp < stat->lpcount )
4148 {
4150 col->validfarkaslp = stat->lpcount;
4151 }
4152 assert(col->validfarkaslp == stat->lpcount);
4153 assert(col->farkascoef != SCIP_INVALID); /*lint !e777*/
4154
4155 return col->farkascoef;
4156}
4157
4158/** gets the Farkas value of a column in last LP (which must be infeasible), i.e. the Farkas coefficient y^T A_i times
4159 * the best bound for this coefficient, i.e. max{y^T A_i x_i | lb <= x_i <= ub}
4160 */
4162 SCIP_COL* col, /**< LP column */
4163 SCIP_STAT* stat, /**< problem statistics */
4164 SCIP_LP* lp /**< current LP data */
4165 )
4166{
4167 SCIP_Real farkascoef;
4168
4169 assert(col != NULL);
4170
4171 farkascoef = SCIPcolGetFarkasCoef(col, stat, lp);
4172
4173 if( farkascoef > 0.0 )
4174 return col->ub * farkascoef;
4175 else
4176 return col->lb * farkascoef;
4177}
4178
4179/** start strong branching - call before any strong branching */
4181 SCIP_LP* lp /**< LP data */
4182 )
4183{
4184 assert(lp != NULL);
4185 assert(!lp->strongbranching);
4186
4187 lp->strongbranching = TRUE;
4188 SCIPdebugMessage("starting strong branching ...\n");
4190
4191 return SCIP_OKAY;
4192}
4193
4194/** end strong branching - call after any strong branching */
4196 SCIP_LP* lp /**< LP data */
4197 )
4198{
4199 assert(lp != NULL);
4200 assert(lp->strongbranching);
4201
4202 lp->strongbranching = FALSE;
4203 SCIPdebugMessage("ending strong branching ...\n");
4205
4206 return SCIP_OKAY;
4207}
4208
4209/** sets strong branching information for a column variable */
4211 SCIP_COL* col, /**< LP column */
4212 SCIP_SET* set, /**< global SCIP settings */
4213 SCIP_STAT* stat, /**< dynamic problem statistics */
4214 SCIP_LP* lp, /**< LP data */
4215 SCIP_Real lpobjval, /**< objective value of the current LP */
4216 SCIP_Real primsol, /**< primal solution value of the column in the current LP */
4217 SCIP_Real sbdown, /**< dual bound after branching column down */
4218 SCIP_Real sbup, /**< dual bound after branching column up */
4219 SCIP_Bool sbdownvalid, /**< is the returned down value a valid dual bound? */
4220 SCIP_Bool sbupvalid, /**< is the returned up value a valid dual bound? */
4221 SCIP_Longint iter, /**< total number of strong branching iterations */
4222 int itlim /**< iteration limit applied to the strong branching call */
4223 )
4224{
4225 assert(col != NULL);
4226 assert(col->var != NULL);
4227 assert(SCIPcolIsIntegral(col));
4228 assert(SCIPvarIsIntegral(col->var));
4230 assert(SCIPvarGetCol(col->var) == col);
4231 assert(col->lpipos >= 0);
4232 assert(col->lppos >= 0);
4233 assert(set != NULL);
4234 assert(stat != NULL);
4235 assert(lp != NULL);
4236 assert(lp->strongbranchprobing);
4237 assert(col->lppos < lp->ncols);
4238 assert(lp->cols[col->lppos] == col);
4239 assert(itlim >= 1);
4240
4241 col->sblpobjval = lpobjval;
4242 col->sbsolval = primsol;
4243 col->validsblp = stat->nlps;
4244 col->sbnode = stat->nnodes;
4245
4246 col->sbitlim = itlim;
4247 col->nsbcalls++;
4248
4249 col->sbdown = MIN(sbdown, lp->cutoffbound);
4250 col->sbup = MIN(sbup, lp->cutoffbound);
4251 col->sbdownvalid = sbdownvalid;
4252 col->sbupvalid = sbupvalid;
4253
4254 SCIPstatIncrement(stat, set, nstrongbranchs);
4255 SCIPstatAdd(stat, set, nsblpiterations, iter);
4256 if( stat->nnodes == 1 )
4257 {
4258 SCIPstatIncrement(stat, set, nrootstrongbranchs);
4259 SCIPstatAdd(stat, set, nrootsblpiterations, iter);
4260 }
4261}
4262
4263/** invalidates strong branching information for a column variable */
4265 SCIP_COL* col, /**< LP column */
4266 SCIP_SET* set, /**< global SCIP settings */
4267 SCIP_STAT* stat, /**< dynamic problem statistics */
4268 SCIP_LP* lp /**< LP data */
4269 )
4270{
4271 assert(col != NULL);
4272 assert(col->var != NULL);
4273 assert(SCIPcolIsIntegral(col));
4274 assert(SCIPvarIsIntegral(col->var));
4276 assert(SCIPvarGetCol(col->var) == col);
4277 assert(col->lpipos >= 0);
4278 assert(col->lppos >= 0);
4279 assert(set != NULL);
4280 assert(stat != NULL);
4281 assert(lp != NULL);
4282 assert(lp->strongbranchprobing);
4283 assert(col->lppos < lp->ncols);
4284 assert(lp->cols[col->lppos] == col);
4285
4286 col->sbdown = SCIP_INVALID;
4287 col->sbup = SCIP_INVALID;
4288 col->sbdownvalid = FALSE;
4289 col->sbupvalid = FALSE;
4290 col->validsblp = -1;
4291 col->sbsolval = SCIP_INVALID;
4292 col->sblpobjval = SCIP_INVALID;
4293 col->sbnode = -1;
4294 col->sbitlim = -1;
4295}
4296
4297
4298/** gets strong branching information on a column variable */
4300 SCIP_COL* col, /**< LP column */
4301 SCIP_Bool integral, /**< should integral strong branching be performed? */
4302 SCIP_SET* set, /**< global SCIP settings */
4303 SCIP_STAT* stat, /**< dynamic problem statistics */
4304 SCIP_PROB* prob, /**< problem data */
4305 SCIP_LP* lp, /**< LP data */
4306 int itlim, /**< iteration limit for strong branchings */
4307 SCIP_Bool updatecol, /**< should col be updated, or should it stay in its current state ? */
4308 SCIP_Bool updatestat, /**< should stat be updated, or should it stay in its current state ? */
4309 SCIP_Real* down, /**< stores dual bound after branching column down */
4310 SCIP_Real* up, /**< stores dual bound after branching column up */
4311 SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound, or NULL;
4312 * otherwise, it can only be used as an estimate value */
4313 SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound, or NULL;
4314 * otherwise, it can only be used as an estimate value */
4315 SCIP_Bool* lperror /**< pointer to store whether an unresolved LP error occurred */
4316 )
4317{
4318 SCIP_Real sbdown;
4319 SCIP_Real sbup;
4320 SCIP_Bool sbdownvalid;
4321 SCIP_Bool sbupvalid;
4322 SCIP_Longint validsblp;
4323 SCIP_Real sbsolval;
4324 SCIP_Real sblpobjval;
4325 SCIP_Longint sbnode;
4326 int sbitlim;
4327 int nsbcalls;
4328
4329 assert(col != NULL);
4330 assert(col->var != NULL);
4331 assert(SCIPcolIsIntegral(col));
4332 assert(SCIPvarIsIntegral(col->var));
4334 assert(SCIPvarGetCol(col->var) == col);
4335 assert(col->primsol != SCIP_INVALID); /*lint !e777*/
4336 assert(col->lpipos >= 0);
4337 assert(col->lppos >= 0);
4338 assert(set != NULL);
4339 assert(stat != NULL);
4340 assert(lp != NULL);
4341 assert(lp->flushed);
4342 assert(lp->solved);
4343 assert(lp->strongbranching);
4344 assert(lp->lpsolstat == SCIP_LPSOLSTAT_OPTIMAL);
4345 assert(lp->validsollp == stat->lpcount);
4346 assert(col->lppos < lp->ncols);
4347 assert(lp->cols[col->lppos] == col);
4348 assert(itlim >= 1);
4349 /* assert(down != NULL);
4350 * assert(up != NULL); temporary hack for cloud branching
4351 */
4352 assert(lperror != NULL);
4353
4354 *lperror = FALSE;
4355
4356 sbdown = col->sbdown;
4357 sbup = col->sbup;
4358 sbdownvalid = col->sbdownvalid;
4359 sbupvalid = col->sbupvalid;
4360 sbitlim = col->sbitlim;
4361 nsbcalls = col->nsbcalls;
4362
4363 validsblp = stat->nlps;
4364 sbsolval = col->primsol;
4365 sblpobjval = SCIPlpGetObjval(lp, set, prob);
4366 sbnode = stat->nnodes;
4367 assert(integral || !SCIPsetIsFeasIntegral(set, col->primsol));
4368
4369 /* if a loose variables has an infinite best bound, the LP bound is -infinity and no gain can be achieved */
4370 if( lp->looseobjvalinf > 0 )
4371 {
4372 sbdown = -SCIPsetInfinity(set);
4373 sbup = -SCIPsetInfinity(set);
4374 sbdownvalid = FALSE;
4375 sbupvalid = FALSE;
4376 }
4377 else
4378 {
4379 SCIP_RETCODE retcode;
4380 int iter;
4381
4382 SCIPsetDebugMsg(set, "performing strong branching on variable <%s>(%g) with %d iterations\n",
4383 SCIPvarGetName(col->var), col->primsol, itlim);
4384
4385 /* start timing */
4387
4388 /* call LPI strong branching */
4389 sbitlim = itlim;
4390 nsbcalls++;
4391
4392 sbdown = lp->lpobjval;
4393 sbup = lp->lpobjval;
4394
4395 if( integral )
4396 retcode = SCIPlpiStrongbranchInt(lp->lpi, col->lpipos, col->primsol, itlim, down == NULL ? NULL : &sbdown, up == NULL ? NULL : &sbup, &sbdownvalid, &sbupvalid, &iter);
4397 else
4398 {
4399 assert( ! SCIPsetIsIntegral(set, col->primsol) );
4400 retcode = SCIPlpiStrongbranchFrac(lp->lpi, col->lpipos, col->primsol, itlim, down == NULL ? NULL : &sbdown, up == NULL ? NULL : &sbup, &sbdownvalid, &sbupvalid, &iter);
4401 }
4402
4403 /* check return code for errors */
4404 if( retcode == SCIP_LPERROR )
4405 {
4406 *lperror = TRUE;
4407 sbdown = SCIP_INVALID;
4408 sbup = SCIP_INVALID;
4409 sbdownvalid = FALSE;
4410 sbupvalid = FALSE;
4411 validsblp = -1;
4412 sbsolval = SCIP_INVALID;
4413 sblpobjval = SCIP_INVALID;
4414 sbnode = -1;
4415 }
4416 else
4417 {
4418 SCIP_Real looseobjval;
4419
4420 *lperror = FALSE;
4421 SCIP_CALL( retcode );
4422
4423 looseobjval = getFiniteLooseObjval(lp, set, prob);
4424 sbdown = MIN(sbdown + looseobjval, lp->cutoffbound);
4425 sbup = MIN(sbup + looseobjval, lp->cutoffbound);
4426
4427 /* update strong branching statistics */
4428 if( updatestat )
4429 {
4430 if( iter == -1 )
4431 {
4432 /* calculate average iteration number */
4433 iter = stat->ndualresolvelps > 0 ? (int)(2*stat->ndualresolvelpiterations / stat->ndualresolvelps)
4434 : stat->nduallps > 0 ? (int)((stat->nduallpiterations / stat->nduallps) / 5)
4435 : stat->nprimalresolvelps > 0 ? (int)(2*stat->nprimalresolvelpiterations / stat->nprimalresolvelps)
4436 : stat->nprimallps > 0 ? (int)((stat->nprimallpiterations / stat->nprimallps) / 5)
4437 : 0;
4438 if( iter/2 >= itlim )
4439 iter = 2*itlim;
4440 }
4441 SCIPstatIncrement(stat, set, nstrongbranchs);
4442 SCIPstatAdd(stat, set, nsblpiterations, iter);
4443 if( stat->nnodes == 1 )
4444 {
4445 SCIPstatIncrement(stat, set, nrootstrongbranchs);
4446 SCIPstatAdd(stat, set, nrootsblpiterations, iter);
4447 }
4448 }
4449 }
4450
4451 /* stop timing */
4453 }
4454 assert(*lperror || sbdown != SCIP_INVALID); /*lint !e777*/
4455 assert(*lperror || sbup != SCIP_INVALID); /*lint !e777*/
4456
4457 if( down != NULL)
4458 *down = sbdown;
4459 if( up != NULL )
4460 *up = sbup;
4461 if( downvalid != NULL )
4462 *downvalid = sbdownvalid;
4463 if( upvalid != NULL )
4464 *upvalid = sbupvalid;
4465
4466 if( updatecol )
4467 {
4468 col->sbdown = sbdown;
4469 col->sbup = sbup;
4470 col->sbdownvalid = sbdownvalid;
4471 col->sbupvalid = sbupvalid;
4472 col->validsblp = validsblp;
4473 col->sbsolval = sbsolval;
4474 col->sblpobjval = sblpobjval;
4475 col->sbnode = sbnode;
4476 col->sbitlim = sbitlim;
4477 col->nsbcalls = nsbcalls;
4478 }
4479
4480 return SCIP_OKAY;
4481}
4482
4483/** gets strong branching information on column variables */
4485 SCIP_COL** cols, /**< LP columns */
4486 int ncols, /**< number of columns */
4487 SCIP_Bool integral, /**< should integral strong branching be performed? */
4488 SCIP_SET* set, /**< global SCIP settings */
4489 SCIP_STAT* stat, /**< dynamic problem statistics */
4490 SCIP_PROB* prob, /**< problem data */
4491 SCIP_LP* lp, /**< LP data */
4492 int itlim, /**< iteration limit for strong branchings */
4493 SCIP_Real* down, /**< stores dual bounds after branching columns down */
4494 SCIP_Real* up, /**< stores dual bounds after branching columns up */
4495 SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds, or NULL;
4496 * otherwise, they can only be used as an estimate value */
4497 SCIP_Bool* upvalid, /**< stores whether the returned up values are valid dual bounds, or NULL;
4498 * otherwise, they can only be used as an estimate value */
4499 SCIP_Bool* lperror /**< pointer to store whether an unresolved LP error occurred */
4500 )
4501{
4502 SCIP_RETCODE retcode;
4503 SCIP_Real* sbdown;
4504 SCIP_Real* sbup;
4505 SCIP_Bool* sbdownvalid;
4506 SCIP_Bool* sbupvalid;
4507 SCIP_Real* primsols;
4508 SCIP_COL** subcols;
4509 int* lpipos;
4510 int* subidx;
4511 int nsubcols;
4512 int iter;
4513 int j;
4514
4515 assert(cols != NULL);
4516 assert(set != NULL);
4517 assert(stat != NULL);
4518 assert(lp != NULL);
4519 assert(lp->flushed);
4520 assert(lp->solved);
4521 assert(lp->lpsolstat == SCIP_LPSOLSTAT_OPTIMAL);
4522 assert(lp->validsollp == stat->lpcount);
4523 assert(itlim >= 1);
4524 assert(down != NULL);
4525 assert(up != NULL);
4526 assert(lperror != NULL);
4527
4528 *lperror = FALSE;
4529
4530 if ( ncols <= 0 )
4531 return SCIP_OKAY;
4532
4533 /* start timing */
4535
4536 /* initialize storage */
4537 SCIP_CALL( SCIPsetAllocBufferArray(set, &subcols, ncols) );
4538 SCIP_CALL( SCIPsetAllocBufferArray(set, &subidx, ncols) );
4539 SCIP_CALL( SCIPsetAllocBufferArray(set, &lpipos, ncols) );
4540 SCIP_CALL( SCIPsetAllocBufferArray(set, &primsols, ncols) );
4541 SCIP_CALL( SCIPsetAllocBufferArray(set, &sbdown, ncols) );
4542 SCIP_CALL( SCIPsetAllocBufferArray(set, &sbup, ncols) );
4543 SCIP_CALL( SCIPsetAllocBufferArray(set, &sbdownvalid, ncols) );
4544 SCIP_CALL( SCIPsetAllocBufferArray(set, &sbupvalid, ncols) );
4545
4546 nsubcols = 0;
4547 for( j = 0; j < ncols; ++j )
4548 {
4549 SCIP_COL* col;
4550 col = cols[j];
4551
4552 assert(col->lppos < lp->ncols);
4553 assert(lp->cols[col->lppos] == col);
4554 assert(SCIPcolIsIntegral(col));
4555 assert(SCIPvarIsIntegral(col->var));
4557 assert(SCIPvarGetCol(col->var) == col);
4558 assert(col->primsol != SCIP_INVALID); /*lint !e777*/
4559 assert(col->lpipos >= 0);
4560 assert(col->lppos >= 0);
4561
4562 col->validsblp = stat->nlps;
4563 col->sbsolval = col->primsol;
4564 col->sblpobjval = SCIPlpGetObjval(lp, set, prob);
4565 col->sbnode = stat->nnodes;
4566 assert(!SCIPsetIsFeasIntegral(set, col->primsol));
4567
4568 /* if a loose variables has an infinite best bound, the LP bound is -infinity and no gain can be achieved */
4569 if( lp->looseobjvalinf > 0 )
4570 {
4571 /* directly set up column and result vectors*/
4572 col->sbdown = -SCIPsetInfinity(set);
4573 col->sbup = -SCIPsetInfinity(set);
4574 col->sbdownvalid = FALSE;
4575 col->sbupvalid = FALSE;
4576 down[j] = col->sbdown;
4577 up[j] = col->sbup;
4578 if( downvalid != NULL )
4579 downvalid[j] = col->sbdownvalid;
4580 if( upvalid != NULL )
4581 upvalid[j] = col->sbupvalid;
4582 }
4583 else
4584 {
4585 col->sbitlim = itlim;
4586 col->nsbcalls++;
4587
4588 lpipos[nsubcols] = col->lpipos;
4589 primsols[nsubcols] = col->primsol;
4590 assert( integral || ! SCIPsetIsFeasIntegral(set, col->primsol) );
4591 subidx[nsubcols] = j;
4592 subcols[nsubcols++] = col;
4593 }
4594 }
4595
4596 SCIPsetDebugMsg(set, "performing strong branching on %d variables with %d iterations\n", ncols, itlim);
4597
4598 /* call LPI strong branching */
4599 if ( integral )
4600 retcode = SCIPlpiStrongbranchesInt(lp->lpi, lpipos, nsubcols, primsols, itlim, sbdown, sbup, sbdownvalid, sbupvalid, &iter);
4601 else
4602 retcode = SCIPlpiStrongbranchesFrac(lp->lpi, lpipos, nsubcols, primsols, itlim, sbdown, sbup, sbdownvalid, sbupvalid, &iter);
4603
4604 /* check return code for errors */
4605 if( retcode == SCIP_LPERROR )
4606 {
4607 *lperror = TRUE;
4608
4609 for( j = 0; j < nsubcols; ++j )
4610 {
4611 SCIP_COL* col;
4612 int idx;
4613
4614 col = subcols[j];
4615 idx = subidx[j];
4616
4617 col->sbdown = SCIP_INVALID;
4618 col->sbup = SCIP_INVALID;
4619 col->sbdownvalid = FALSE;
4620 col->sbupvalid = FALSE;
4621 col->validsblp = -1;
4622 col->sbsolval = SCIP_INVALID;
4623 col->sblpobjval = SCIP_INVALID;
4624 col->sbnode = -1;
4625
4626 down[idx] = col->sbdown;
4627 up[idx] = col->sbup;
4628 if( downvalid != NULL )
4629 downvalid[idx] = col->sbdownvalid;
4630 if( upvalid != NULL )
4631 upvalid[idx] = col->sbupvalid;
4632 }
4633 }
4634 else
4635 {
4636 SCIP_Real looseobjval;
4637
4638 *lperror = FALSE;
4639 SCIP_CALL( retcode );
4640
4641 looseobjval = getFiniteLooseObjval(lp, set, prob);
4642
4643 for( j = 0; j < nsubcols; ++j )
4644 {
4645 SCIP_COL* col;
4646 int idx;
4647
4648 col = subcols[j];
4649 idx = subidx[j];
4650
4651 assert( col->sbdown != SCIP_INVALID); /*lint !e777*/
4652 assert( col->sbup != SCIP_INVALID); /*lint !e777*/
4653
4654 col->sbdown = MIN(sbdown[j] + looseobjval, lp->cutoffbound);
4655 col->sbup = MIN(sbup[j] + looseobjval, lp->cutoffbound);
4656 col->sbdownvalid = sbdownvalid[j];
4657 col->sbupvalid = sbupvalid[j];
4658
4659 down[idx] = col->sbdown;
4660 up[idx] = col->sbup;
4661 if( downvalid != NULL )
4662 downvalid[idx] = col->sbdownvalid;
4663 if( upvalid != NULL )
4664 upvalid[idx] = col->sbupvalid;
4665 }
4666
4667 /* update strong branching statistics */
4668 if( iter == -1 )
4669 {
4670 /* calculate average iteration number */
4671 iter = stat->ndualresolvelps > 0 ? (int)(2*stat->ndualresolvelpiterations / stat->ndualresolvelps)
4672 : stat->nduallps > 0 ? (int)((stat->nduallpiterations / stat->nduallps) / 5)
4673 : stat->nprimalresolvelps > 0 ? (int)(2*stat->nprimalresolvelpiterations / stat->nprimalresolvelps)
4674 : stat->nprimallps > 0 ? (int)((stat->nprimallpiterations / stat->nprimallps) / 5)
4675 : 0;
4676 if( iter/2 >= itlim )
4677 iter = 2*itlim;
4678 }
4679 SCIPstatAdd(stat, set, nstrongbranchs, ncols);
4680 SCIPstatAdd(stat, set, nsblpiterations, iter);
4681 if( stat->nnodes == 1 )
4682 {
4683 SCIPstatAdd(stat, set, nrootstrongbranchs, ncols);
4684 SCIPstatAdd(stat, set, nrootsblpiterations, iter);
4685 }
4686 }
4687
4688 SCIPsetFreeBufferArray(set, &sbupvalid);
4689 SCIPsetFreeBufferArray(set, &sbdownvalid);
4691 SCIPsetFreeBufferArray(set, &sbdown);
4692 SCIPsetFreeBufferArray(set, &primsols);
4693 SCIPsetFreeBufferArray(set, &lpipos);
4694 SCIPsetFreeBufferArray(set, &subidx);
4695 SCIPsetFreeBufferArray(set, &subcols);
4696
4697 /* stop timing */
4699
4700 return SCIP_OKAY;
4701}
4702
4703/** gets last strong branching information available for a column variable;
4704 * returns values of SCIP_INVALID, if strong branching was not yet called on the given column;
4705 * keep in mind, that the returned old values may have nothing to do with the current LP solution
4706 */
4708 SCIP_COL* col, /**< LP column */
4709 SCIP_Real* down, /**< stores dual bound after branching column down, or NULL */
4710 SCIP_Real* up, /**< stores dual bound after branching column up, or NULL */
4711 SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound, or NULL;
4712 * otherwise, it can only be used as an estimate value */
4713 SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound, or NULL;
4714 * otherwise, it can only be used as an estimate value */
4715 SCIP_Real* solval, /**< stores LP solution value of column at last strong branching call, or NULL */
4716 SCIP_Real* lpobjval /**< stores LP objective value at last strong branching call, or NULL */
4717 )
4718{
4719 assert(col != NULL);
4720
4721 if( down != NULL )
4722 *down = col->sbdown;
4723 if( up != NULL )
4724 *up = col->sbup;
4725 if( downvalid != NULL )
4726 *downvalid = col->sbdownvalid;
4727 if( upvalid != NULL )
4728 *upvalid = col->sbupvalid;
4729 if( solval != NULL )
4730 *solval = col->sbsolval;
4731 if( lpobjval != NULL )
4732 *lpobjval = col->sblpobjval;
4733}
4734
4735/** if strong branching was already applied on the column at the current node, returns the number of LPs solved after
4736 * the LP where the strong branching on this column was applied;
4737 * if strong branching was not yet applied on the column at the current node, returns INT_MAX
4738 */
4740 SCIP_COL* col, /**< LP column */
4741 SCIP_STAT* stat /**< dynamic problem statistics */
4742 )
4743{
4744 assert(col != NULL);
4745 assert(stat != NULL);
4746
4747 return (col->sbnode != stat->nnodes ? SCIP_LONGINT_MAX : stat->nlps - col->validsblp);
4748}
4749
4750/** marks a column to be not removable from the LP in the current node because it became obsolete */
4752 SCIP_COL* col, /**< LP column */
4753 SCIP_STAT* stat /**< problem statistics */
4754 )
4755{
4756 assert(col != NULL);
4757 assert(stat != NULL);
4758 assert(stat->nnodes > 0);
4759
4760 /* lpRemoveObsoleteCols() does not remove a column if the node number stored in obsoletenode equals the current node number */
4761 col->obsoletenode = stat->nnodes;
4762}
4763
4764
4765/*
4766 * Row methods
4767 */
4768
4769/** calculates row norms and min/maxidx from scratch, and checks for sorting */
4770static
4772 SCIP_ROW* row, /**< LP row */
4773 SCIP_SET* set /**< global SCIP settings */
4774 )
4775{
4776 int i;
4777
4778 assert(row != NULL);
4779 assert(set != NULL);
4780
4781 row->sqrnorm = 0.0;
4782 row->sumnorm = 0.0;
4783 row->objprod = 0.0;
4784 row->maxval = 0.0;
4785 row->nummaxval = 1;
4786 row->minval = SCIPsetInfinity(set);
4787 row->numminval = 1;
4788 row->minidx = INT_MAX;
4789 row->maxidx = INT_MIN;
4790 row->validminmaxidx = TRUE;
4791 row->lpcolssorted = TRUE;
4792 row->nonlpcolssorted = TRUE;
4793
4794 /* check, if row is sorted
4795 * calculate sqrnorm, sumnorm, maxval, minval, minidx, and maxidx
4796 */
4797 for( i = 0; i < row->nlpcols; ++i )
4798 {
4799 assert(row->cols[i] != NULL);
4800 assert(!SCIPsetIsZero(set, row->vals[i]));
4801 assert(row->cols[i]->lppos >= 0);
4802 assert(row->linkpos[i] >= 0);
4803 assert(row->cols[i]->index == row->cols_index[i]);
4804
4805 rowAddNorms(row, set, row->cols[i], row->vals[i], TRUE);
4806 if( i > 0 )
4807 {
4808 assert(row->cols[i-1]->index == row->cols_index[i-1]);
4809 row->lpcolssorted = row->lpcolssorted && (row->cols_index[i-1] < row->cols_index[i]);
4810 }
4811 }
4812 for( i = row->nlpcols; i < row->len; ++i )
4813 {
4814 assert(row->cols[i] != NULL);
4815 assert(!SCIPsetIsZero(set, row->vals[i]));
4816 assert(row->cols[i]->lppos == -1 || row->linkpos[i] == -1);
4817 assert(row->cols[i]->index == row->cols_index[i]);
4818
4819 rowAddNorms(row, set, row->cols[i], row->vals[i], TRUE);
4820 if( i > row->nlpcols )
4821 {
4822 assert(row->cols[i-1]->index == row->cols_index[i-1]);
4823 row->nonlpcolssorted = row->nonlpcolssorted && (row->cols_index[i-1] < row->cols_index[i]);
4824 }
4825 }
4826}
4827
4828/** calculates min/maxval and min/maxidx from scratch */
4829static
4831 SCIP_ROW* row, /**< LP row */
4832 SCIP_SET* set /**< global SCIP settings */
4833 )
4834{
4835 SCIP_COL* col;
4836 SCIP_Real absval;
4837 int i;
4838
4839 assert(row != NULL);
4840 assert(set != NULL);
4841
4842 row->maxval = 0.0;
4843 row->nummaxval = 1;
4844 row->numintcols = 0;
4845 row->minval = SCIPsetInfinity(set);
4846 row->numminval = 1;
4847 row->minidx = INT_MAX;
4848 row->maxidx = INT_MIN;
4849 row->validminmaxidx = TRUE;
4850
4851 /* calculate maxval, minval, minidx, and maxidx */
4852 for( i = 0; i < row->len; ++i )
4853 {
4854 col = row->cols[i];
4855 assert(col != NULL);
4856 assert(!SCIPsetIsZero(set, row->vals[i]));
4857
4858 absval = REALABS(row->vals[i]);
4859 assert(!SCIPsetIsZero(set, absval));
4860
4861 /* update min/maxidx */
4862 row->minidx = MIN(row->minidx, col->index);
4863 row->maxidx = MAX(row->maxidx, col->index);
4864 row->numintcols += SCIPcolIsIntegral(col); /*lint !e713*/
4865
4866 /* update maximal and minimal non-zero value */
4867 if( row->nummaxval > 0 )
4868 {
4869 if( SCIPsetIsGT(set, absval, row->maxval) )
4870 {
4871 row->maxval = absval;
4872 row->nummaxval = 1;
4873 }
4874 else if( SCIPsetIsGE(set, absval, row->maxval) )
4875 {
4876 /* make sure the maxval is always exactly the same */
4877 row->maxval = MAX(absval, row->maxval);
4878 row->nummaxval++;
4879 }
4880 }
4881 if( row->numminval > 0 )
4882 {
4883 if( SCIPsetIsLT(set, absval, row->minval) )
4884 {
4885 row->minval = absval;
4886 row->numminval = 1;
4887 }
4888 else if( SCIPsetIsLE(set, absval, row->minval) )
4889 {
4890 /* make sure the minval is always exactly the same */
4891 row->minval = MIN(absval, row->minval);
4892 row->numminval++;
4893 }
4894 }
4895 }
4896}
4897
4898/** checks, whether the given scalar scales the given value to an integral number with error in the given bounds */
4899static
4901 SCIP_Real val, /**< value that should be scaled to an integral value */
4902 SCIP_Real scalar, /**< scalar that should be tried */
4903 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
4904 SCIP_Real maxdelta, /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
4905 SCIP_Real* intval /**< pointer to store the scaled integral value, or NULL */
4906 )
4907{
4908 SCIP_Real sval;
4909 SCIP_Real downval;
4910 SCIP_Real upval;
4911
4912 assert(mindelta <= 0.0);
4913 assert(maxdelta >= 0.0);
4914
4915 sval = val * scalar;
4916 downval = floor(sval);
4917 upval = ceil(sval);
4918
4919 if( SCIPrelDiff(sval, downval) <= maxdelta )
4920 {
4921 if( intval != NULL )
4922 *intval = downval;
4923 return TRUE;
4924 }
4925 else if( SCIPrelDiff(sval, upval) >= mindelta )
4926 {
4927 if( intval != NULL )
4928 *intval = upval;
4929 return TRUE;
4930 }
4931
4932 return FALSE;
4933}
4934
4935/** scales row with given factor, and rounds coefficients to integers if close enough;
4936 * the constant is automatically moved to the sides;
4937 * if the row's activity is proven to be integral, the sides are automatically rounded to the next integer
4938 */
4939static
4941 SCIP_ROW* row, /**< LP row */
4942 BMS_BLKMEM* blkmem, /**< block memory */
4943 SCIP_SET* set, /**< global SCIP settings */
4944 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4945 SCIP_STAT* stat, /**< problem statistics */
4946 SCIP_LP* lp, /**< current LP data */
4947 SCIP_Real scaleval, /**< value to scale row with */
4948 SCIP_Bool integralcontvars, /**< should the coefficients of the continuous variables also be made integral,
4949 * if they are close to integral values? */
4950 SCIP_Real minrounddelta, /**< minimal relative difference of scaled coefficient s*c and integral i,
4951 * upto which the integral is used instead of the scaled real coefficient */
4952 SCIP_Real maxrounddelta /**< maximal relative difference of scaled coefficient s*c and integral i
4953 * upto which the integral is used instead of the scaled real coefficient */
4954 )
4955{
4956 SCIP_COL* col;
4957 SCIP_Real val;
4958 SCIP_Real newval;
4959 SCIP_Real intval;
4960 SCIP_Real mindelta;
4961 SCIP_Real maxdelta;
4962 SCIP_Real lb;
4963 SCIP_Real ub;
4964 SCIP_Bool mindeltainf;
4965 SCIP_Bool maxdeltainf;
4966 int oldlen;
4967 int c;
4968
4969 assert(row != NULL);
4970 assert(row->len == 0 || row->cols != NULL);
4971 assert(row->len == 0 || row->vals != NULL);
4972 assert(SCIPsetIsPositive(set, scaleval));
4973 assert(-1.0 < minrounddelta && minrounddelta <= 0.0);
4974 assert(0.0 <= maxrounddelta && maxrounddelta < 1.0);
4975
4976 SCIPsetDebugMsg(set, "scale row <%s> with %g (tolerance=[%g,%g])\n", row->name, scaleval, minrounddelta, maxrounddelta);
4977
4978 mindelta = 0.0;
4979 maxdelta = 0.0;
4980 mindeltainf = FALSE;
4981 maxdeltainf = FALSE;
4982 oldlen = row->len;
4983
4984 /* scale the row coefficients, thereby recalculating whether the row's activity is always integral;
4985 * if the row coefficients are rounded to the nearest integer value, calculate the maximal activity difference,
4986 * this rounding can lead to
4987 */
4988 row->integral = TRUE;
4989
4990 c = 0;
4991 while( c < row->len )
4992 {
4993 col = row->cols[c];
4994 val = row->vals[c];
4995 assert(!SCIPsetIsZero(set, val));
4996
4997 /* get local or global bounds for column, depending on the local or global feasibility of the row */
4998 if( row->local )
4999 {
5000 lb = col->lb;
5001 ub = col->ub;
5002 }
5003 else
5004 {
5005 lb = SCIPvarGetLbGlobal(col->var);
5006 ub = SCIPvarGetUbGlobal(col->var);
5007 }
5008
5009 /* calculate scaled coefficient */
5010 newval = val * scaleval;
5011 if( (integralcontvars || SCIPcolIsIntegral(col) || SCIPsetIsIntegral(set, newval))
5012 && isIntegralScalar(val, scaleval, minrounddelta, maxrounddelta, &intval) )
5013 {
5014 if( !SCIPsetIsEQ(set, intval, newval) )
5015 {
5016 if( intval < newval )
5017 {
5018 mindelta += (intval - newval)*ub;
5019 maxdelta += (intval - newval)*lb;
5020 mindeltainf = mindeltainf || SCIPsetIsInfinity(set, ub);
5021 maxdeltainf = maxdeltainf || SCIPsetIsInfinity(set, -lb);
5022 }
5023 else
5024 {
5025 mindelta += (intval - newval)*lb;
5026 maxdelta += (intval - newval)*ub;
5027 mindeltainf = mindeltainf || SCIPsetIsInfinity(set, -lb);
5028 maxdeltainf = maxdeltainf || SCIPsetIsInfinity(set, ub);
5029 }
5030 }
5031 newval = intval;
5032 }
5033
5034 if( !SCIPsetIsEQ(set, val, newval) )
5035 {
5036 /* if column knows of the row, change the corresponding coefficient in the column */
5037 if( row->linkpos[c] >= 0 )
5038 {
5039 assert(col->rows[row->linkpos[c]] == row);
5040 assert(SCIPsetIsEQ(set, col->vals[row->linkpos[c]], row->vals[c]));
5041 SCIP_CALL( colChgCoefPos(col, set, lp, row->linkpos[c], newval) );
5042 }
5043
5044 /* change the coefficient in the row, and update the norms and integrality status */
5045 SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, c, newval) );
5046
5047 /* current coefficient has been deleted from the row because it was almost zero */
5048 if( oldlen != row->len )
5049 {
5050 assert(row->len == oldlen - 1);
5051 c--;
5052 oldlen = row->len;
5053 }
5054 }
5055 else
5056 row->integral = row->integral && SCIPcolIsIntegral(col) && SCIPsetIsIntegral(set, val);
5057
5058 ++c;
5059 }
5060
5061 /* scale the row sides, and move the constant to the sides; relax the sides with accumulated delta in order
5062 * to not destroy feasibility due to rounding
5063 */
5064 /**@todo ensure that returned cut does not have infinite lhs and rhs */
5065 if( !SCIPsetIsInfinity(set, -row->lhs) )
5066 {
5067 if( mindeltainf )
5068 newval = -SCIPsetInfinity(set);
5069 else
5070 {
5071 newval = (row->lhs - row->constant) * scaleval + mindelta;
5072 if( SCIPsetIsIntegral(set, newval) || (row->integral && !row->modifiable) )
5073 newval = SCIPsetSumCeil(set, newval);
5074 }
5075 SCIP_CALL( SCIProwChgLhs(row, blkmem, set, eventqueue, lp, newval) );
5076 }
5077 if( !SCIPsetIsInfinity(set, row->rhs) )
5078 {
5079 if( maxdeltainf )
5080 newval = SCIPsetInfinity(set);
5081 else
5082 {
5083 newval = (row->rhs - row->constant) * scaleval + maxdelta;
5084 if( SCIPsetIsIntegral(set, newval) || (row->integral && !row->