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