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