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