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