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