Scippy

SCIP

Solving Constraint Integer Programs

lp.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
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 */
2353  SCIP_COL* col, /**< column data */
2354  BMS_BLKMEM* blkmem, /**< block memory */
2355  SCIP_SET* set, /**< global SCIP settings */
2356  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2357  SCIP_LP* lp /**< current LP data */
2358  )
2359 {
2360  int i;
2361 
2362  assert(col != NULL);
2363  assert(col->var != NULL);
2364  assert(blkmem != NULL);
2365  assert(set != NULL);
2366  assert(lp != NULL);
2367 
2368  if( col->nunlinked > 0 )
2369  {
2370  SCIPsetDebugMsg(set, "linking column <%s>\n", SCIPvarGetName(col->var));
2371 
2372  /* unlinked rows can only be in the non-LP/unlinked rows part of the rows array */
2373  for( i = col->nlprows; i < col->len; ++i )
2374  {
2375  assert(!SCIPsetIsZero(set, col->vals[i]));
2376  if( col->linkpos[i] == -1 )
2377  {
2378  /* this call might swap the current row with the first non-LP/not linked row, but this is of no harm */
2379  SCIP_CALL( rowAddCoef(col->rows[i], blkmem, set, eventqueue, lp, col, col->vals[i], i) );
2380  }
2381  assert(col->rows[i]->cols[col->linkpos[i]] == col);
2382  assert(col->rows[i]->linkpos[col->linkpos[i]] == i);
2383  assert(col->nlprows == 0 || col->rows[col->nlprows-1]->cols[col->linkpos[col->nlprows-1]] == col);
2384  assert(col->nlprows == 0 || col->rows[col->nlprows-1]->linkpos[col->linkpos[col->nlprows-1]] == col->nlprows-1);
2385  }
2386  }
2387  assert(col->nunlinked == 0);
2388 
2389  checkLinks(lp);
2390 
2391  return SCIP_OKAY;
2392 }
2393 
2394 /** removes column coefficients from corresponding rows */
2396  SCIP_COL* col, /**< column data */
2397  BMS_BLKMEM* blkmem, /**< block memory */
2398  SCIP_SET* set, /**< global SCIP settings */
2399  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2400  SCIP_LP* lp /**< current LP data */
2401  )
2402 {
2403  int i;
2404 
2405  assert(col != NULL);
2406  assert(col->var != NULL);
2407  assert(blkmem != NULL);
2408  assert(set != NULL);
2409  assert(lp != NULL);
2410 
2411  if( col->nunlinked < col->len )
2412  {
2413  SCIPsetDebugMsg(set, "unlinking column <%s>\n", SCIPvarGetName(col->var));
2414  for( i = 0; i < col->len; ++i )
2415  {
2416  if( col->linkpos[i] >= 0 )
2417  {
2418  assert(col->rows[i]->cols[col->linkpos[i]] == col);
2419  SCIP_CALL( rowDelCoefPos(col->rows[i], blkmem, set, eventqueue, lp, col->linkpos[i]) );
2420  col->linkpos[i] = -1;
2421  col->nunlinked++;
2422  }
2423  }
2424  }
2425  assert(col->nunlinked == col->len);
2426 
2427  checkLinks(lp);
2428 
2429  return SCIP_OKAY;
2430 }
2431 
2432 /** insert row coefficients in corresponding columns */
2434  SCIP_ROW* row, /**< row data */
2435  BMS_BLKMEM* blkmem, /**< block memory */
2436  SCIP_SET* set, /**< global SCIP settings */
2437  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2438  SCIP_LP* lp /**< current LP data */
2439  )
2440 {
2441  int i;
2442 
2443  assert(row != NULL);
2444  assert(blkmem != NULL);
2445  assert(set != NULL);
2446  assert(lp != NULL);
2447 
2448  if( row->nunlinked > 0 )
2449  {
2450  SCIPsetDebugMsg(set, "linking row <%s>\n", row->name);
2451 
2452  /* unlinked columns can only be in the non-LP/unlinked columns part of the cols array */
2453  for( i = row->nlpcols; i < row->len; ++i )
2454  {
2455  assert(!SCIPsetIsZero(set, row->vals[i]));
2456  if( row->linkpos[i] == -1 )
2457  {
2458  /* this call might swap the current column with the first non-LP/not linked column, but this is of no harm */
2459  SCIP_CALL( colAddCoef(row->cols[i], blkmem, set, eventqueue, lp, row, row->vals[i], i) );
2460  }
2461  assert(row->cols[i]->rows[row->linkpos[i]] == row);
2462  assert(row->cols[i]->linkpos[row->linkpos[i]] == i);
2463  assert(row->nlpcols == 0 || row->cols[row->nlpcols-1]->rows[row->linkpos[row->nlpcols-1]] == row);
2464  assert(row->nlpcols == 0 || row->cols[row->nlpcols-1]->linkpos[row->linkpos[row->nlpcols-1]] == row->nlpcols-1);
2465  }
2466  }
2467  assert(row->nunlinked == 0);
2468 
2469  checkLinks(lp);
2470 
2471  return SCIP_OKAY;
2472 }
2473 
2474 /** removes row coefficients from corresponding columns */
2476  SCIP_ROW* row, /**< row data */
2477  SCIP_SET* set, /**< global SCIP settings */
2478  SCIP_LP* lp /**< current LP data */
2479  )
2480 {
2481  int i;
2482 
2483  assert(row != NULL);
2484  assert(set != NULL);
2485  assert(lp != NULL);
2486 
2487  if( row->nunlinked < row->len )
2488  {
2489  SCIPsetDebugMsg(set, "unlinking row <%s>\n", row->name);
2490  for( i = 0; i < row->len; ++i )
2491  {
2492  if( row->linkpos[i] >= 0 )
2493  {
2494  assert(row->cols[i]->rows[row->linkpos[i]] == row);
2495  SCIP_CALL( colDelCoefPos(row->cols[i], set, lp, row->linkpos[i]) );
2496  row->nunlinked++;
2497  }
2498  }
2499  }
2500  assert(row->nunlinked == row->len);
2501 
2502  return SCIP_OKAY;
2503 }
2504 
2505 
2506 
2507 
2508 /*
2509  * local LP parameter methods
2510  */
2511 
2512 /** sets parameter of type int in LP solver, ignoring unknown parameters */
2513 static
2515  SCIP_LP* lp, /**< current LP data */
2516  SCIP_LPPARAM lpparam, /**< LP parameter */
2517  int value, /**< value to set parameter to */
2518  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2519  )
2520 {
2521  SCIP_RETCODE retcode;
2522 
2523  assert(lp != NULL);
2524  assert(success != NULL);
2525 
2526  retcode = SCIPlpiSetIntpar(lp->lpi, lpparam, value);
2527 
2528  /* check, if parameter is unknown */
2529  if( retcode == SCIP_PARAMETERUNKNOWN )
2530  {
2531  *success = FALSE;
2532  return SCIP_OKAY;
2533  }
2534  *success = TRUE;
2535 
2536  return retcode;
2537 }
2538 
2539 /** sets parameter of type SCIP_Bool in LP solver, ignoring unknown parameters */
2540 static
2542  SCIP_LP* lp, /**< current LP data */
2543  SCIP_LPPARAM lpparam, /**< LP parameter */
2544  SCIP_Bool value, /**< value to set parameter to */
2545  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2546  )
2547 {
2548  return lpSetIntpar(lp, lpparam, (int)value, success);
2549 }
2550 
2551 /** sets parameter of type SCIP_Real in LP solver, ignoring unknown parameters */
2552 static
2554  SCIP_LP* lp, /**< current LP data */
2555  SCIP_LPPARAM lpparam, /**< LP parameter */
2556  SCIP_Real value, /**< value to set parameter to */
2557  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2558  )
2559 {
2560  SCIP_RETCODE retcode;
2561 
2562  assert(lp != NULL);
2563  assert(success != NULL);
2564 
2565  retcode = SCIPlpiSetRealpar(lp->lpi, lpparam, value);
2566 
2567  /* check, if parameter is unknown */
2568  if( retcode == SCIP_PARAMETERUNKNOWN )
2569  {
2570  *success = FALSE;
2571  return SCIP_OKAY;
2572  }
2573  *success = TRUE;
2574 
2575  return retcode;
2576 }
2577 
2578 #ifndef NDEBUG
2579 /** checks, that parameter of type int in LP solver has the given value, ignoring unknown parameters */
2580 static
2582  SCIP_LP* lp, /**< current LP data */
2583  SCIP_LPPARAM lpparam, /**< LP parameter */
2584  int value /**< value parameter should have */
2585  )
2586 {
2587  SCIP_RETCODE retcode;
2588  int lpivalue;
2589 
2590  assert(lp != NULL);
2591 
2592  retcode = SCIPlpiGetIntpar(lp->lpi, lpparam, &lpivalue);
2593 
2594  /* ignore unknown parameter error */
2595  if( retcode == SCIP_PARAMETERUNKNOWN )
2596  return SCIP_OKAY;
2597 
2598  /* check value */
2599  assert(lpivalue == value);
2600 
2601  return retcode;
2602 }
2603 
2604 /** checks, that parameter of type SCIP_Bool in LP solver has the given value, ignoring unknown parameters */
2605 static
2607  SCIP_LP* lp, /**< current LP data */
2608  SCIP_LPPARAM lpparam, /**< LP parameter */
2609  SCIP_Bool value /**< value parameter should have */
2610  )
2611 {
2612  return lpCheckIntpar(lp, lpparam, (int)value);
2613 }
2614 
2615 /** checks, that parameter of type SCIP_Real in LP solver has the given value, ignoring unknown parameters */
2616 static
2618  SCIP_LP* lp, /**< current LP data */
2619  SCIP_LPPARAM lpparam, /**< LP parameter */
2620  SCIP_Real value /**< value parameter should have */
2621  )
2622 {
2623  SCIP_RETCODE retcode;
2624  SCIP_Real lpivalue;
2625 
2626  assert(lp != NULL);
2627 
2628  retcode = SCIPlpiGetRealpar(lp->lpi, lpparam, &lpivalue);
2629 
2630  /* ignore unknown parameter error */
2631  if( retcode == SCIP_PARAMETERUNKNOWN )
2632  return SCIP_OKAY;
2633 
2634  /* check value */
2635  assert(lpivalue == value); /*lint !e777*/
2636 
2637  return retcode;
2638 }
2639 #else
2640 #define lpCheckIntpar(lp, lpparam, value) SCIP_OKAY
2641 #define lpCheckBoolpar(lp, lpparam, value) SCIP_OKAY
2642 #define lpCheckRealpar(lp, lpparam, value) SCIP_OKAY
2643 #endif
2644 
2645 /** should the objective limit of the LP solver be disabled */
2646 #define lpCutoffDisabled(set,prob) (set->lp_disablecutoff == 1 || ((set->nactivepricers > 0 || !SCIPprobAllColsInLP(prob, set, lp)) && set->lp_disablecutoff == 2))
2647 
2648 /** sets the objective limit of the LP solver
2649  *
2650  * Note that we are always minimizing.
2651  */
2652 static
2654  SCIP_LP* lp, /**< current LP data */
2655  SCIP_SET* set, /**< global SCIP settings */
2656  SCIP_PROB* prob, /**< problem data */
2657  SCIP_Real objlim, /**< new objective limit */
2658  SCIP_Bool* success /**< pointer to store whether the parameter was actually changed */
2659  )
2660 {
2661  assert(lp != NULL);
2662  assert(set != NULL);
2663  assert(success != NULL);
2664 
2665  *success = FALSE;
2666 
2667  /* We disabled the objective limit in the LP solver or we want so solve exactly and thus cannot rely on the LP
2668  * solver's objective limit handling, so we make sure that the objective limit is inactive (infinity). */
2669  if( lpCutoffDisabled(set, prob) || set->misc_exactsolve )
2670  objlim = SCIPlpiInfinity(lp->lpi);
2671 
2672  /* convert SCIP infinity value to lp-solver infinity value if necessary */
2673  if( SCIPsetIsInfinity(set, objlim) )
2674  objlim = SCIPlpiInfinity(lp->lpi);
2675 
2677 
2678  if( objlim != lp->lpiobjlim ) /*lint !e777*/
2679  {
2680  SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_OBJLIM, objlim, success) );
2681  if( *success )
2682  {
2683  SCIP_Real actualobjlim;
2684 
2685  /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2686  SCIP_CALL( SCIPlpiGetRealpar(lp->lpi, SCIP_LPPAR_OBJLIM, &actualobjlim) );
2687  if( actualobjlim != lp->lpiobjlim ) /*lint !e777*/
2688  {
2689  /* mark the current solution invalid */
2690  lp->solved = FALSE;
2691  lp->primalfeasible = FALSE;
2692  lp->primalchecked = FALSE;
2693  lp->lpobjval = SCIP_INVALID;
2695  }
2696  lp->lpiobjlim = actualobjlim;
2697  }
2698  }
2699 
2700  return SCIP_OKAY;
2701 }
2702 
2703 /** sets the feasibility tolerance of the LP solver */
2704 static
2706  SCIP_LP* lp, /**< current LP data */
2707  SCIP_Real feastol, /**< new feasibility tolerance */
2708  SCIP_Bool* success /**< pointer to store whether the parameter was actually changed */
2709  )
2710 {
2711  assert(lp != NULL);
2712  assert(feastol >= 0.0);
2713  assert(success != NULL);
2714 
2716 
2717  if( feastol != lp->lpifeastol ) /*lint !e777*/
2718  {
2719  SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_FEASTOL, feastol, success) );
2720  if( *success )
2721  {
2722  SCIP_Real actualfeastol;
2723 
2724  /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2725  SCIP_CALL( SCIPlpiGetRealpar(lp->lpi, SCIP_LPPAR_FEASTOL, &actualfeastol) );
2726  if( lp->nrows > 0 && actualfeastol < lp->lpifeastol )
2727  {
2728  /* mark the current solution invalid */
2729  lp->solved = FALSE;
2730  lp->primalfeasible = FALSE;
2731  lp->primalchecked = FALSE;
2732  lp->lpobjval = SCIP_INVALID;
2734  }
2735  else
2736  *success = FALSE;
2737  lp->lpifeastol = actualfeastol;
2738  }
2739  }
2740  else
2741  *success = FALSE;
2742 
2743  return SCIP_OKAY;
2744 }
2745 
2746 /** sets the reduced costs feasibility tolerance of the LP solver */
2747 static
2749  SCIP_LP* lp, /**< current LP data */
2750  SCIP_Real dualfeastol, /**< new reduced costs feasibility tolerance */
2751  SCIP_Bool* success /**< pointer to store whether the parameter was actually changed */
2752  )
2753 {
2754  assert(lp != NULL);
2755  assert(dualfeastol >= 0.0);
2756  assert(success != NULL);
2757 
2759 
2760  if( dualfeastol != lp->lpidualfeastol ) /*lint !e777*/
2761  {
2762  SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_DUALFEASTOL, dualfeastol, success) );
2763  if( *success )
2764  {
2765  SCIP_Real actualdualfeastol;
2766 
2767  /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2768  SCIP_CALL( SCIPlpiGetRealpar(lp->lpi, SCIP_LPPAR_DUALFEASTOL, &actualdualfeastol) );
2769  if( lp->nrows > 0 && actualdualfeastol < lp->lpidualfeastol )
2770  {
2771  /* mark the current solution invalid */
2772  lp->solved = FALSE;
2773  lp->dualfeasible = FALSE;
2774  lp->dualchecked = FALSE;
2775  lp->lpobjval = SCIP_INVALID;
2777  }
2778  else
2779  *success = FALSE;
2780  lp->lpidualfeastol = actualdualfeastol;
2781  }
2782  }
2783  else
2784  *success = FALSE;
2785 
2786  return SCIP_OKAY;
2787 }
2788 
2789 /** sets the convergence tolerance used in barrier algorithm of the LP solver */
2790 static
2792  SCIP_LP* lp, /**< current LP data */
2793  SCIP_Real barrierconvtol, /**< new convergence tolerance used in barrier algorithm */
2794  SCIP_Bool* success /**< pointer to store whether the parameter was actually changed */
2795  )
2796 {
2797  assert(lp != NULL);
2798  assert(barrierconvtol >= 0.0);
2799  assert(success != NULL);
2800 
2802 
2803  if( barrierconvtol != lp->lpibarrierconvtol ) /*lint !e777*/
2804  {
2805  SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_BARRIERCONVTOL, barrierconvtol, success) );
2806  if( *success )
2807  {
2808  SCIP_Real actualbarrierconvtol;
2809 
2810  /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2811  SCIP_CALL( SCIPlpiGetRealpar(lp->lpi, SCIP_LPPAR_BARRIERCONVTOL, &actualbarrierconvtol) );
2812  if( lp->nrows > 0 && actualbarrierconvtol < lp->lpibarrierconvtol
2814  {
2815  /* mark the current solution invalid */
2816  lp->solved = FALSE;
2817  lp->dualfeasible = FALSE;
2818  lp->dualchecked = FALSE;
2819  lp->lpobjval = SCIP_INVALID;
2821  }
2822  else
2823  *success = FALSE;
2824  lp->lpibarrierconvtol = actualbarrierconvtol;
2825  }
2826  }
2827  else
2828  *success = FALSE;
2829 
2830  return SCIP_OKAY;
2831 }
2832 
2833 /** sets the FROMSCRATCH setting of the LP solver */
2834 static
2836  SCIP_LP* lp, /**< current LP data */
2837  SCIP_Bool fromscratch, /**< new FROMSCRATCH setting */
2838  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2839  )
2840 {
2841  assert(lp != NULL);
2842  assert(success != NULL);
2843 
2845 
2846  if( fromscratch != lp->lpifromscratch )
2847  {
2848  SCIP_CALL( lpSetBoolpar(lp, SCIP_LPPAR_FROMSCRATCH, fromscratch, success) );
2849  if( *success )
2850  lp->lpifromscratch = fromscratch;
2851  }
2852  else
2853  *success = FALSE;
2854 
2855  return SCIP_OKAY;
2856 }
2857 
2858 /** sets the FASTMIP setting of the LP solver */
2859 static
2861  SCIP_LP* lp, /**< current LP data */
2862  int fastmip, /**< new FASTMIP setting */
2863  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2864  )
2865 {
2866  assert(lp != NULL);
2867  assert(success != NULL);
2868  assert(0 <= fastmip && fastmip <= 1);
2869 
2871 
2872  if( fastmip != lp->lpifastmip )
2873  {
2874  SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_FASTMIP, fastmip, success) );
2875  if( *success )
2876  {
2877  lp->lpifastmip = fastmip;
2878  lp->solved = FALSE;
2879  /* We might only set lp->solved to false if fastmip is turned off, since the latter should be the more
2880  * demanding setting; however, in the current code, this should have not effect. */
2881  }
2882  }
2883  else
2884  *success = FALSE;
2885 
2886  return SCIP_OKAY;
2887 }
2888 
2889 /** sets the SCALING setting of the LP solver */
2890 static
2892  SCIP_LP* lp, /**< current LP data */
2893  int scaling, /**< new SCALING setting */
2894  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2895  )
2896 {
2897  assert(lp != NULL);
2898  assert(success != NULL);
2899 
2901 
2902  if( scaling != lp->lpiscaling )
2903  {
2904  SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_SCALING, scaling, success) );
2905  if( *success )
2906  lp->lpiscaling = scaling;
2907  }
2908  else
2909  *success = FALSE;
2910 
2911  return SCIP_OKAY;
2912 }
2913 
2914 /** sets the number of THREADS of the LP solver */
2915 static
2917  SCIP_LP* lp, /**< current LP data */
2918  int threads, /**< new number of threads used to solve the LP */
2919  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2920  )
2921 {
2922  assert(lp != NULL);
2923  assert(success != NULL);
2924 
2926 
2927  if( threads != lp->lpithreads )
2928  {
2929  SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_THREADS, threads, success) );
2930  if( *success )
2931  lp->lpithreads = threads;
2932  }
2933  else
2934  *success = FALSE;
2935 
2936  return SCIP_OKAY;
2937 }
2938 
2939 /** sets the PRESOLVING setting of the LP solver */
2940 static
2942  SCIP_LP* lp, /**< current LP data */
2943  SCIP_Bool presolving, /**< new PRESOLVING setting */
2944  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2945  )
2946 {
2947  assert(lp != NULL);
2948  assert(success != NULL);
2949 
2951 
2952  if( presolving != lp->lpipresolving )
2953  {
2954  SCIP_CALL( lpSetBoolpar(lp, SCIP_LPPAR_PRESOLVING, presolving, success) );
2955  if( *success )
2956  lp->lpipresolving = presolving;
2957  }
2958  else
2959  *success = FALSE;
2960 
2961  return SCIP_OKAY;
2962 }
2963 
2964 /** sets the ROWREPSWITCH setting of the LP solver */
2965 static
2967  SCIP_LP* lp, /**< current LP data */
2968  SCIP_Real rowrepswitch, /**< new ROWREPSWITCH value */
2969  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
2970  )
2971 {
2972  assert(lp != NULL);
2973  assert(success != NULL);
2974 
2976 
2977  if( rowrepswitch != lp->lpirowrepswitch ) /*lint !e777*/
2978  {
2979  SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_ROWREPSWITCH, rowrepswitch, success) );
2980  if( *success )
2981  lp->lpirowrepswitch = rowrepswitch;
2982  }
2983  else
2984  *success = FALSE;
2985 
2986  return SCIP_OKAY;
2987 }
2988 
2989 /** sets the iteration limit of the LP solver */
2990 static
2992  SCIP_LP* lp, /**< current LP data */
2993  int itlim /**< maximal number of LP iterations to perform, or -1 for no limit */
2994  )
2995 {
2996  SCIP_Bool success;
2997 
2998  assert(lp != NULL);
2999  assert(itlim >= -1);
3000 
3001  if( itlim == -1 )
3002  itlim = INT_MAX;
3003 
3005 
3006  if( itlim != lp->lpiitlim )
3007  {
3008  SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_LPITLIM, itlim, &success) );
3009  if( success )
3010  {
3011  if( itlim > lp->lpiitlim )
3012  {
3013  /* mark the current solution invalid */
3014  lp->solved = FALSE;
3015  lp->lpobjval = SCIP_INVALID;
3017  }
3018  lp->lpiitlim = itlim;
3019  }
3020  }
3021 
3022  return SCIP_OKAY;
3023 }
3024 
3025 /** sets the pricing strategy of the LP solver */
3026 static
3028  SCIP_LP* lp, /**< current LP data */
3029  SCIP_PRICING pricing /**< pricing strategy */
3030  )
3031 {
3032  SCIP_Bool success;
3033 
3034  assert(lp != NULL);
3035 
3037 
3038  if( pricing != lp->lpipricing )
3039  {
3040  SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_PRICING, (int)pricing, &success) );
3041  if( success )
3042  lp->lpipricing = pricing;
3043  }
3044 
3045  return SCIP_OKAY;
3046 }
3047 
3048 /** sets the pricing strategy of the LP solver (given the character representation of the strategy) */
3049 static
3051  SCIP_LP* lp, /**< current LP data */
3052  char pricingchar /**< character representing the pricing strategy */
3053  )
3054 {
3055  SCIP_PRICING pricing;
3056 
3057  switch( pricingchar )
3058  {
3059  case 'l':
3060  pricing = SCIP_PRICING_LPIDEFAULT;
3061  break;
3062  case 'a':
3063  pricing = SCIP_PRICING_AUTO;
3064  break;
3065  case 'f':
3066  pricing = SCIP_PRICING_FULL;
3067  break;
3068  case 'p':
3069  pricing = SCIP_PRICING_PARTIAL;
3070  break;
3071  case 's':
3072  pricing = SCIP_PRICING_STEEP;
3073  break;
3074  case 'q':
3075  pricing = SCIP_PRICING_STEEPQSTART;
3076  break;
3077  case 'd':
3078  pricing = SCIP_PRICING_DEVEX;
3079  break;
3080  default:
3081  SCIPerrorMessage("invalid LP pricing parameter <%c>\n", pricingchar);
3082  return SCIP_INVALIDDATA;
3083  }
3084 
3085  SCIP_CALL( lpSetPricing(lp, pricing) );
3086 
3087  return SCIP_OKAY;
3088 }
3089 
3090 /** sets the verbosity of the LP solver */
3091 static
3093  SCIP_LP* lp, /**< current LP data */
3094  SCIP_Bool lpinfo /**< should the LP solver display status messages? */
3095  )
3096 {
3097  SCIP_Bool success;
3098 
3099  assert(lp != NULL);
3100 
3102 
3103  if( lpinfo != lp->lpilpinfo )
3104  {
3105  SCIP_CALL( lpSetBoolpar(lp, SCIP_LPPAR_LPINFO, lpinfo, &success) );
3106  if( success )
3107  lp->lpilpinfo = lpinfo;
3108  }
3109 
3110  return SCIP_OKAY;
3111 }
3112 
3113 /** sets the CONDITIONLIMIT setting of the LP solver */
3114 static
3116  SCIP_LP* lp, /**< current LP data */
3117  SCIP_Real condlimit, /**< new CONDITIONLIMIT value */
3118  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
3119  )
3120 {
3121  assert(lp != NULL);
3122  assert(success != NULL);
3123 
3125 
3126  if( condlimit != lp->lpiconditionlimit ) /*lint !e777*/
3127  {
3128  SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_CONDITIONLIMIT, condlimit, success) );
3129  if( *success )
3130  lp->lpiconditionlimit = condlimit;
3131  }
3132  else
3133  *success = FALSE;
3134 
3135  return SCIP_OKAY;
3136 }
3137 
3138 /** sets the MARKOWITZ setting of the LP solver */
3139 static
3141  SCIP_LP* lp, /**< current LP data */
3142  SCIP_Real threshhold, /**< new MARKOWITZ value */
3143  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
3144  )
3145 {
3146  assert(lp != NULL);
3147  assert(success != NULL);
3148 
3150 
3151  if( threshhold != lp->lpimarkowitz ) /*lint !e777*/
3152  {
3153  SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_MARKOWITZ, threshhold, success) );
3154  if( *success )
3155  lp->lpimarkowitz = threshhold;
3156  }
3157  else
3158  *success = FALSE;
3159 
3160  return SCIP_OKAY;
3161 }
3162 
3163 /** sets the type of timer of the LP solver */
3164 static
3166  SCIP_LP* lp, /**< current LP data */
3167  SCIP_CLOCKTYPE timing, /**< new timing value */
3168  SCIP_Bool enabled, /**< is timing enabled? */
3169  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
3170  )
3171 {
3172  int lptiming;
3173 
3174  assert(lp != NULL);
3175  assert(success != NULL);
3176  assert((int) SCIP_CLOCKTYPE_CPU == 1 && (int) SCIP_CLOCKTYPE_WALL == 2); /*lint !e506*//*lint !e1564*/
3177 
3179 
3180  if( !enabled )
3181  lptiming = 0;
3182  else
3183  lptiming = (int) timing;
3184 
3185  if( lptiming != lp->lpitiming ) /*lint !e777*/
3186  {
3187  SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_TIMING, lptiming, success) );
3188  if( *success )
3189  lp->lpitiming = lptiming;
3190  }
3191  else
3192  *success = FALSE;
3193 
3194  return SCIP_OKAY;
3195 }
3196 
3197 /** sets the initial random seed of the LP solver */
3198 static
3200  SCIP_LP* lp, /**< current LP data */
3201  int randomseed, /**< new initial random seed */
3202  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
3203  )
3204 {
3205  assert(lp != NULL);
3206  assert(success != NULL);
3207 
3208  /* we don't check this parameter because SoPlex will always return its current random seed, not the initial one */
3209 
3210  if( randomseed == 0 )
3211  {
3212  lp->lpirandomseed = randomseed;
3213  *success = TRUE;
3214  }
3215  else if( randomseed != lp->lpirandomseed ) /*lint !e777*/
3216  {
3217  SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_RANDOMSEED, randomseed, success) );
3218  if( *success )
3219  lp->lpirandomseed = randomseed;
3220  }
3221  else
3222  *success = FALSE;
3223 
3224  return SCIP_OKAY;
3225 }
3226 
3227 /** sets the LP solution polishing method */
3228 static
3230  SCIP_LP* lp, /**< current LP data */
3231  SCIP_Bool polishing, /**< LP solution polishing activated (0: disabled, 1: enabled) */
3232  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
3233  )
3234 {
3235  assert(lp != NULL);
3236  assert(success != NULL);
3237 
3238  if( polishing != lp->lpisolutionpolishing )
3239  {
3240  SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_POLISHING, (polishing ? 1 : 0), success) );
3241  if( *success )
3242  lp->lpisolutionpolishing = polishing;
3243  }
3244  else
3245  *success = FALSE;
3246 
3247  return SCIP_OKAY;
3248 }
3249 
3250 /** sets the LP refactorization interval */
3251 static
3253  SCIP_LP* lp, /**< current LP data */
3254  int refactor, /**< LP refactorization interval (0: automatic) */
3255  SCIP_Bool* success /**< pointer to store whether the parameter was successfully changed */
3256  )
3257 {
3258  assert(lp != NULL);
3259  assert(success != NULL);
3260 
3261  if( refactor != lp->lpirefactorinterval )
3262  {
3263  SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_REFACTOR, refactor, success) );
3264  if( *success )
3265  lp->lpirefactorinterval = refactor;
3266  }
3267  else
3268  *success = FALSE;
3269 
3270  return SCIP_OKAY;
3271 }
3272 
3273 
3274 /*
3275  * Column methods
3276  */
3277 
3278 /** creates an LP column */
3280  SCIP_COL** col, /**< pointer to column data */
3281  BMS_BLKMEM* blkmem, /**< block memory */
3282  SCIP_SET* set, /**< global SCIP settings */
3283  SCIP_STAT* stat, /**< problem statistics */
3284  SCIP_VAR* var, /**< variable, this column represents */
3285  int len, /**< number of nonzeros in the column */
3286  SCIP_ROW** rows, /**< array with rows of column entries */
3287  SCIP_Real* vals, /**< array with coefficients of column entries */
3288  SCIP_Bool removable /**< should the column be removed from the LP due to aging or cleanup? */
3289  )
3290 {
3291  int i;
3292 
3293  assert(col != NULL);
3294  assert(blkmem != NULL);
3295  assert(set != NULL);
3296  assert(stat != NULL);
3297  assert(var != NULL);
3298  assert(len >= 0);
3299  assert(len == 0 || (rows != NULL && vals != NULL));
3300 
3301  SCIP_ALLOC( BMSallocBlockMemory(blkmem, col) );
3302 
3303  if( len > 0 )
3304  {
3305  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*col)->rows, rows, len) );
3306  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*col)->vals, vals, len) );
3307  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*col)->linkpos, len) );
3308 
3309  for( i = 0; i < len; ++i )
3310  {
3311  assert(rows[i] != NULL);
3312  assert(!SCIPsetIsZero(set, vals[i]));
3313  (*col)->linkpos[i] = -1;
3314  }
3315  }
3316  else
3317  {
3318  (*col)->rows = NULL;
3319  (*col)->vals = NULL;
3320  (*col)->linkpos = NULL;
3321  }
3322 
3323  (*col)->var = var;
3324  (*col)->obj = SCIPvarGetObj(var);
3325  (*col)->unchangedobj = SCIPvarGetUnchangedObj(var);
3326  (*col)->lb = SCIPvarGetLbLocal(var);
3327  (*col)->ub = SCIPvarGetUbLocal(var);
3328  (*col)->flushedobj = 0.0;
3329  (*col)->flushedlb = 0.0;
3330  (*col)->flushedub = 0.0;
3331  (*col)->index = stat->ncolidx;
3332  SCIPstatIncrement(stat, set, ncolidx);
3333  (*col)->size = len;
3334  (*col)->len = len;
3335  (*col)->nlprows = 0;
3336  (*col)->nunlinked = len;
3337  (*col)->lppos = -1;
3338  (*col)->lpipos = -1;
3339  (*col)->lpdepth = -1;
3340  (*col)->primsol = 0.0;
3341  (*col)->redcost = SCIP_INVALID;
3342  (*col)->farkascoef = SCIP_INVALID;
3343  (*col)->minprimsol = (*col)->ub;
3344  (*col)->maxprimsol = (*col)->lb;
3345  (*col)->sbdown = SCIP_INVALID;
3346  (*col)->sbup = SCIP_INVALID;
3347  (*col)->sbsolval = SCIP_INVALID;
3348  (*col)->sblpobjval = SCIP_INVALID;
3349  (*col)->sbnode = -1;
3350  (*col)->validredcostlp = -1;
3351  (*col)->validfarkaslp = -1;
3352  (*col)->validsblp = -1;
3353  (*col)->sbitlim = -1;
3354  (*col)->nsbcalls = 0;
3355  (*col)->age = 0;
3356  (*col)->obsoletenode = -1;
3357  (*col)->var_probindex = SCIPvarGetProbindex(var);
3358  (*col)->basisstatus = SCIP_BASESTAT_ZERO; /*lint !e641*/
3359  (*col)->lprowssorted = TRUE;
3360  (*col)->nonlprowssorted = (len <= 1);
3361  (*col)->objchanged = FALSE;
3362  (*col)->lbchanged = FALSE;
3363  (*col)->ubchanged = FALSE;
3364  (*col)->coefchanged = FALSE;
3365  (*col)->integral = SCIPvarIsIntegral(var);
3366  (*col)->removable = removable;
3367  (*col)->sbdownvalid = FALSE;
3368  (*col)->sbupvalid = FALSE;
3369  (*col)->lazylb = SCIPvarGetLbLazy(var);
3370  (*col)->lazyub = SCIPvarGetUbLazy(var);
3371  (*col)->storedsolvals = NULL;
3372 
3373  return SCIP_OKAY;
3374 }
3375 
3376 /** frees an LP column */
3378  SCIP_COL** col, /**< pointer to LP column */
3379  BMS_BLKMEM* blkmem, /**< block memory */
3380  SCIP_SET* set, /**< global SCIP settings */
3381  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3382  SCIP_LP* lp /**< current LP data */
3383  )
3384 {
3385  assert(blkmem != NULL);
3386  assert(col != NULL);
3387  assert(*col != NULL);
3388  assert((*col)->var != NULL);
3389  assert(SCIPvarGetStatus((*col)->var) == SCIP_VARSTATUS_COLUMN);
3390  assert(&(*col)->var->data.col == col); /* SCIPcolFree() has to be called from SCIPvarFree() */
3391  assert((*col)->lppos == -1);
3392  assert((*col)->lpipos == -1);
3393 
3394  /* remove column indices from corresponding rows */
3395  SCIP_CALL( colUnlink(*col, blkmem, set, eventqueue, lp) );
3396 
3397  BMSfreeBlockMemoryNull(blkmem, &(*col)->storedsolvals);
3398  BMSfreeBlockMemoryArrayNull(blkmem, &(*col)->rows, (*col)->size);
3399  BMSfreeBlockMemoryArrayNull(blkmem, &(*col)->vals, (*col)->size);
3400  BMSfreeBlockMemoryArrayNull(blkmem, &(*col)->linkpos, (*col)->size);
3401  BMSfreeBlockMemory(blkmem, col);
3402 
3403  return SCIP_OKAY;
3404 }
3405 
3406 /** output column to file stream */
3408  SCIP_COL* col, /**< LP column */
3409  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3410  FILE* file /**< output file (or NULL for standard output) */
3411  )
3412 {
3413  int r;
3414 
3415  assert(col != NULL);
3416  assert(col->var != NULL);
3417 
3418  /* print bounds */
3419  SCIPmessageFPrintInfo(messagehdlr, file, "(obj: %.15g) [%.15g,%.15g], ", col->obj, col->lb, col->ub);
3420 
3421  /* print coefficients */
3422  if( col->len == 0 )
3423  SCIPmessageFPrintInfo(messagehdlr, file, "<empty>");
3424  for( r = 0; r < col->len; ++r )
3425  {
3426  assert(col->rows[r] != NULL);
3427  assert(col->rows[r]->name != NULL);
3428  SCIPmessageFPrintInfo(messagehdlr, file, "%+.15g<%s> ", col->vals[r], col->rows[r]->name);
3429  }
3430  SCIPmessageFPrintInfo(messagehdlr, file, "\n");
3431 }
3432 
3433 /** sorts column entries such that LP rows precede non-LP rows and inside both parts lower row indices precede higher ones
3434  */
3436  SCIP_COL* col /**< column to be sorted */
3437  )
3438 {
3439  /* sort LP rows */
3440  colSortLP(col);
3441 
3442  /* sort non-LP rows */
3443  colSortNonLP(col);
3444 }
3445 
3446 /** adds a previously non existing coefficient to an LP column */
3448  SCIP_COL* col, /**< LP column */
3449  BMS_BLKMEM* blkmem, /**< block memory */
3450  SCIP_SET* set, /**< global SCIP settings */
3451  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3452  SCIP_LP* lp, /**< current LP data */
3453  SCIP_ROW* row, /**< LP row */
3454  SCIP_Real val /**< value of coefficient */
3455  )
3456 {
3457  assert(lp != NULL);
3458  assert(!lp->diving);
3459 
3460  SCIP_CALL( colAddCoef(col, blkmem, set, eventqueue, lp, row, val, -1) );
3461 
3462  checkLinks(lp);
3463 
3464  return SCIP_OKAY;
3465 }
3466 
3467 /** deletes existing coefficient from column */
3469  SCIP_COL* col, /**< column to be changed */
3470  BMS_BLKMEM* blkmem, /**< block memory */
3471  SCIP_SET* set, /**< global SCIP settings */
3472  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3473  SCIP_LP* lp, /**< current LP data */
3474  SCIP_ROW* row /**< coefficient to be deleted */
3475  )
3476 {
3477  int pos;
3478 
3479  assert(col != NULL);
3480  assert(col->var != NULL);
3481  assert(lp != NULL);
3482  assert(!lp->diving);
3483  assert(row != NULL);
3484 
3485  /* search the position of the row in the column's row vector */
3486  pos = colSearchCoef(col, row);
3487  if( pos == -1 )
3488  {
3489  SCIPerrorMessage("coefficient for row <%s> doesn't exist in column <%s>\n", row->name, SCIPvarGetName(col->var));
3490  return SCIP_INVALIDDATA;
3491  }
3492  assert(0 <= pos && pos < col->len);
3493  assert(col->rows[pos] == row);
3494 
3495  /* if row knows of the column, remove the column from the row's col vector */
3496  if( col->linkpos[pos] >= 0 )
3497  {
3498  assert(row->cols[col->linkpos[pos]] == col);
3499  assert(row->cols_index[col->linkpos[pos]] == col->index);
3500  assert(SCIPsetIsEQ(set, row->vals[col->linkpos[pos]], col->vals[pos]));
3501  SCIP_CALL( rowDelCoefPos(row, blkmem, set, eventqueue, lp, col->linkpos[pos]) );
3502  }
3503 
3504  /* delete the row from the column's row vector */
3505  SCIP_CALL( colDelCoefPos(col, set, lp, pos) );
3506 
3507  checkLinks(lp);
3508 
3509  return SCIP_OKAY;
3510 }
3511 
3512 /** changes or adds a coefficient to an LP column */
3514  SCIP_COL* col, /**< LP column */
3515  BMS_BLKMEM* blkmem, /**< block memory */
3516  SCIP_SET* set, /**< global SCIP settings */
3517  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3518  SCIP_LP* lp, /**< current LP data */
3519  SCIP_ROW* row, /**< LP row */
3520  SCIP_Real val /**< value of coefficient */
3521  )
3522 {
3523  int pos;
3524 
3525  assert(col != NULL);
3526  assert(lp != NULL);
3527  assert(!lp->diving);
3528  assert(row != NULL);
3529 
3530  /* search the position of the row in the column's row vector */
3531  pos = colSearchCoef(col, row);
3532 
3533  /* check, if row already exists in the column's row vector */
3534  if( pos == -1 )
3535  {
3536  /* add previously not existing coefficient */
3537  SCIP_CALL( colAddCoef(col, blkmem, set, eventqueue, lp, row, val, -1) );
3538  }
3539  else
3540  {
3541  /* modify already existing coefficient */
3542  assert(0 <= pos && pos < col->len);
3543  assert(col->rows[pos] == row);
3544 
3545  /* if row knows of the column, change the corresponding coefficient in the row */
3546  if( col->linkpos[pos] >= 0 )
3547  {
3548  assert(row->cols[col->linkpos[pos]] == col);
3549  assert(row->cols_index[col->linkpos[pos]] == col->index);
3550  assert(SCIPsetIsEQ(set, row->vals[col->linkpos[pos]], col->vals[pos]));
3551  SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, col->linkpos[pos], val) );
3552  }
3553 
3554  /* change the coefficient in the column */
3555  SCIP_CALL( colChgCoefPos(col, set, lp, pos, val) );
3556  }
3557 
3558  checkLinks(lp);
3559 
3560  return SCIP_OKAY;
3561 }
3562 
3563 /** increases value of an existing or non-existing coefficient in an LP column */
3565  SCIP_COL* col, /**< LP column */
3566  BMS_BLKMEM* blkmem, /**< block memory */
3567  SCIP_SET* set, /**< global SCIP settings */
3568  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3569  SCIP_LP* lp, /**< current LP data */
3570  SCIP_ROW* row, /**< LP row */
3571  SCIP_Real incval /**< value to add to the coefficient */
3572  )
3573 {
3574  int pos;
3575 
3576  assert(col != NULL);
3577  assert(lp != NULL);
3578  assert(!lp->diving);
3579  assert(row != NULL);
3580 
3581  if( SCIPsetIsZero(set, incval) )
3582  return SCIP_OKAY;
3583 
3584  /* search the position of the row in the column's row vector */
3585  pos = colSearchCoef(col, row);
3586 
3587  /* check, if row already exists in the column's row vector */
3588  if( pos == -1 )
3589  {
3590  /* add previously not existing coefficient */
3591  SCIP_CALL( colAddCoef(col, blkmem, set, eventqueue, lp, row, incval, -1) );
3592  }
3593  else
3594  {
3595  /* modify already existing coefficient */
3596  assert(0 <= pos && pos < col->len);
3597  assert(col->rows[pos] == row);
3598 
3599  /* if row knows of the column, change the corresponding coefficient in the row */
3600  if( col->linkpos[pos] >= 0 )
3601  {
3602  assert(row->cols[col->linkpos[pos]] == col);
3603  assert(row->cols_index[col->linkpos[pos]] == col->index);
3604  assert(SCIPsetIsEQ(set, row->vals[col->linkpos[pos]], col->vals[pos]));
3605  SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, col->linkpos[pos], col->vals[pos] + incval) );
3606  }
3607 
3608  /* change the coefficient in the column */
3609  SCIP_CALL( colChgCoefPos(col, set, lp, pos, col->vals[pos] + incval) );
3610  }
3611 
3612  checkLinks(lp);
3613 
3614  return SCIP_OKAY;
3615 }
3616 
3617 /** insert column in the chgcols list (if not already there) */
3618 static
3620  SCIP_COL* col, /**< LP column to change */
3621  SCIP_SET* set, /**< global SCIP settings */
3622  SCIP_LP* lp /**< current LP data */
3623  )
3624 {
3625  if( !col->objchanged && !col->lbchanged && !col->ubchanged )
3626  {
3627  SCIP_CALL( ensureChgcolsSize(lp, set, lp->nchgcols+1) );
3628  lp->chgcols[lp->nchgcols] = col;
3629  lp->nchgcols++;
3630  }
3631 
3632  /* mark the current LP unflushed */
3633  lp->flushed = FALSE;
3634 
3635  return SCIP_OKAY;
3636 }
3637 
3638 /** Is the new value reliable or may we have cancellation?
3639  *
3640  * @note: Here we only consider cancellations which can occur during decreasing the oldvalue to newvalue; not the
3641  * cancellations which can occur during increasing the oldvalue to the newvalue
3642  */
3643 static
3645  SCIP_SET* set, /**< global SCIP settings */
3646  SCIP_Real newvalue, /**< new value */
3647  SCIP_Real oldvalue /**< old reliable value */
3648  )
3649 {
3650  SCIP_Real quotient;
3651 
3652  assert(set != NULL);
3653  assert(oldvalue != SCIP_INVALID); /*lint !e777*/
3654 
3655  quotient = (REALABS(newvalue)+1.0) / (REALABS(oldvalue) + 1.0);
3656 
3657  return SCIPsetIsZero(set, quotient);
3658 }
3659 
3660 /** update norms of objective function vector */
3661 static
3663  SCIP_LP* lp, /**< current LP data */
3664  SCIP_SET* set, /**< global SCIP settings */
3665  SCIP_Real oldobj, /**< old objective value of variable */
3666  SCIP_Real newobj /**< new objective value of variable */
3667  )
3668 {
3669  if( REALABS(newobj) != REALABS(oldobj) ) /*lint !e777*/
3670  {
3671  if( !lp->objsqrnormunreliable )
3672  {
3673  SCIP_Real oldvalue;
3674 
3675  oldvalue = lp->objsqrnorm;
3676  lp->objsqrnorm += SQR(newobj) - SQR(oldobj);
3677 
3678  /* due to numerical cancellations, we recalculate lp->objsqrnorm using all variables */
3679  if( SCIPsetIsLT(set, lp->objsqrnorm, 0.0) || isNewValueUnreliable(set, lp->objsqrnorm, oldvalue) )
3680  lp->objsqrnormunreliable = TRUE;
3681  else
3682  {
3683  assert(SCIPsetIsGE(set, lp->objsqrnorm, 0.0));
3684 
3685  /* due to numerical troubles it still can appear that lp->objsqrnorm is a little bit smaller than 0 */
3686  lp->objsqrnorm = MAX(lp->objsqrnorm, 0.0);
3687 
3688  assert(lp->objsqrnorm >= 0.0);
3689  }
3690  }
3691 
3692  lp->objsumnorm += REALABS(newobj) - REALABS(oldobj);
3693  lp->objsumnorm = MAX(lp->objsumnorm, 0.0);
3694  }
3695 }
3696 
3697 /** changes objective value of column */
3699  SCIP_COL* col, /**< LP column to change */
3700  SCIP_SET* set, /**< global SCIP settings */
3701  SCIP_LP* lp, /**< current LP data */
3702  SCIP_Real newobj /**< new objective value */
3703  )
3704 {
3705  assert(col != NULL);
3706  assert(col->var != NULL);
3707  assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
3708  assert(SCIPvarGetCol(col->var) == col);
3709  assert(lp != NULL);
3710 
3711  SCIPsetDebugMsg(set, "changing objective value of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->obj, newobj);
3712 
3713  /* only add actual changes */
3714  if( !SCIPsetIsEQ(set, col->obj, newobj) )
3715  {
3716  /* only variables with a real position in the LPI can be inserted */
3717  if( col->lpipos >= 0 )
3718  {
3719  /* insert column in the chgcols list (if not already there) */
3720  SCIP_CALL( insertColChgcols(col, set, lp) );
3721 
3722  /* mark objective value change in the column */
3723  col->objchanged = TRUE;
3724 
3725  assert(lp->nchgcols > 0);
3726  }
3727  /* in any case, when the sign of the objective (and thereby the best bound) changes, the variable has to enter the
3728  * LP and the LP has to be flushed
3729  */
3730  else if( (col->obj < 0.0 && newobj >= 0.0 && SCIPsetIsZero(set, col->ub))
3731  || (col->obj >= 0.0 && newobj < 0.0 && SCIPsetIsZero(set, col->lb)) )
3732  {
3733  /* mark the LP unflushed */
3734  lp->flushed = FALSE;
3735  }
3736  }
3737 
3738  /* store new objective function value */
3739  col->obj = newobj;
3740 
3741  /* update original objective value, as long as we are not in diving or probing and changed objective values */
3742  if( !lp->divingobjchg )
3743  {
3744  SCIP_Real oldobj = col->unchangedobj;
3745 
3746  assert(SCIPsetIsEQ(set, newobj, SCIPvarGetUnchangedObj(col->var)));
3747  col->unchangedobj = newobj;
3748 
3749  /* update the objective function vector norms */
3750  lpUpdateObjNorms(lp, set, oldobj, newobj);
3751  }
3752 
3753  return SCIP_OKAY;
3754 }
3755 
3756 /** changes lower bound of column */
3758  SCIP_COL* col, /**< LP column to change */
3759  SCIP_SET* set, /**< global SCIP settings */
3760  SCIP_LP* lp, /**< current LP data */
3761  SCIP_Real newlb /**< new lower bound value */
3762  )
3763 {
3764  assert(col != NULL);
3765  assert(col->var != NULL);
3766  assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
3767  assert(SCIPvarGetCol(col->var) == col);
3768  assert(lp != NULL);
3769 
3770  SCIPsetDebugMsg(set, "changing lower bound of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->lb, newlb);
3771 
3772  /* only add actual changes */
3773  if( !SCIPsetIsEQ(set, col->lb, newlb) )
3774  {
3775  /* only variables with a real position in the LPI can be inserted */
3776  if( col->lpipos >= 0 )
3777  {
3778  /* insert column in the chgcols list (if not already there) */
3779  SCIP_CALL( insertColChgcols(col, set, lp) );
3780 
3781  /* mark bound change in the column */
3782  col->lbchanged = TRUE;
3783 
3784  assert(lp->nchgcols > 0);
3785  }
3786  /* 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
3787  * flushed
3788  */
3789  else if( col->obj >= 0.0 && SCIPsetIsZero(set, col->lb) )
3790  {
3791  /* mark the LP unflushed */
3792  lp->flushed = FALSE;
3793  }
3794  }
3795 
3796  col->lb = newlb;
3797 
3798  return SCIP_OKAY;
3799 }
3800 
3801 /** changes upper bound of column */
3803  SCIP_COL* col, /**< LP column to change */
3804  SCIP_SET* set, /**< global SCIP settings */
3805  SCIP_LP* lp, /**< current LP data */
3806  SCIP_Real newub /**< new upper bound value */
3807  )
3808 {
3809  assert(col != NULL);
3810  assert(col->var != NULL);
3811  assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
3812  assert(SCIPvarGetCol(col->var) == col);
3813  assert(lp != NULL);
3814 
3815  SCIPsetDebugMsg(set, "changing upper bound of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->ub, newub);
3816 
3817  /* only add actual changes */
3818  if( !SCIPsetIsEQ(set, col->ub, newub) )
3819  {
3820  /* only variables with a real position in the LPI can be inserted */
3821  if( col->lpipos >= 0 )
3822  {
3823  /* insert column in the chgcols list (if not already there) */
3824  SCIP_CALL( insertColChgcols(col, set, lp) );
3825 
3826  /* mark bound change in the column */
3827  col->ubchanged = TRUE;
3828 
3829  assert(lp->nchgcols > 0);
3830  }
3831  /* 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
3832  * flushed
3833  */
3834  else if( col->obj < 0.0 && SCIPsetIsZero(set, col->ub) )
3835  {
3836  /* mark the LP unflushed */
3837  lp->flushed = FALSE;
3838  }
3839  }
3840 
3841  col->ub = newub;
3842 
3843  return SCIP_OKAY;
3844 }
3845 
3846 /** calculates the reduced costs of a column using the given dual solution vector */
3848  SCIP_COL* col, /**< LP column */
3849  SCIP_Real* dualsol /**< dual solution vector for current LP rows */
3850  )
3851 {
3852  SCIP_ROW* row;
3853  SCIP_Real redcost;
3854  int i;
3855 
3856  assert(col != NULL);
3857  assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
3858  assert(SCIPvarGetCol(col->var) == col);
3859  assert(dualsol != NULL);
3860 
3861  redcost = col->obj;
3862  for( i = 0; i < col->nlprows; ++i )
3863  {
3864  row = col->rows[i];
3865  assert(row != NULL);
3866  assert(row->lppos >= 0);
3867  redcost -= col->vals[i] * dualsol[row->lppos];
3868  }
3869 
3870  if( col->nunlinked > 0 )
3871  {
3872  for( i = col->nlprows; i < col->len; ++i )
3873  {
3874  row = col->rows[i];
3875  assert(row != NULL);
3876  assert(row->lppos == -1 || col->linkpos[i] == -1);
3877  if( row->lppos >= 0 )
3878  redcost -= col->vals[i] * dualsol[row->lppos];
3879  }
3880  }
3881 #ifndef NDEBUG
3882  else
3883  {
3884  for( i = col->nlprows; i < col->len; ++i )
3885  {
3886  row = col->rows[i];
3887  assert(row != NULL);
3888  assert(row->lppos == -1);
3889  assert(col->linkpos[i] >= 0);
3890  }
3891  }
3892 #endif
3893 
3894  return redcost;
3895 }
3896 
3897 /** calculates the reduced costs of a column using the dual solution stored in the rows */
3898 static
3900  SCIP_COL* col /**< LP column */
3901  )
3902 {
3903  SCIP_ROW* row;
3904  SCIP_Real redcost;
3905  int i;
3906 
3907  assert(col != NULL);
3908  assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
3909  assert(SCIPvarGetCol(col->var) == col);
3910 
3911  redcost = col->obj;
3912  for( i = 0; i < col->nlprows; ++i )
3913  {
3914  row = col->rows[i];
3915  assert(row != NULL);
3916  assert(row->dualsol != SCIP_INVALID); /*lint !e777*/
3917  assert(row->lppos >= 0);
3918  assert(col->linkpos[i] >= 0);
3919  redcost -= col->vals[i] * row->dualsol;
3920  }
3921 
3922  if( col->nunlinked > 0 )
3923  {
3924  for( i = col->nlprows; i < col->len; ++i )
3925  {
3926  row = col->rows[i];
3927  assert(row != NULL);
3928  assert(row->lppos >= 0 || row->dualsol == 0.0);
3929  assert(row->lppos == -1 || col->linkpos[i] == -1);
3930  if( row->lppos >= 0 )
3931  redcost -= col->vals[i] * row->dualsol;
3932  }
3933  }
3934 #ifndef NDEBUG
3935  else
3936  {
3937  for( i = col->nlprows; i < col->len; ++i )
3938  {
3939  row = col->rows[i];
3940  assert(row != NULL);
3941  assert(row->dualsol == 0.0);
3942  assert(row->lppos == -1);
3943  assert(col->linkpos[i] >= 0);
3944  }
3945  }
3946 #endif
3947 
3948  return redcost;
3949 }
3950 
3951 /** gets the reduced costs of a column in last LP or after recalculation */
3953  SCIP_COL* col, /**< LP column */
3954  SCIP_STAT* stat, /**< problem statistics */
3955  SCIP_LP* lp /**< current LP data */
3956  )
3957 {
3958  assert(col != NULL);
3959  assert(stat != NULL);
3960  assert(lp != NULL);
3961  assert(col->validredcostlp <= stat->lpcount);
3962  assert(lp->validsollp == stat->lpcount);
3963 
3964  if( col->validredcostlp < stat->lpcount )
3965  {
3966  col->redcost = colCalcInternalRedcost(col);
3967  col->validredcostlp = stat->lpcount;
3968  }
3969  assert(col->validredcostlp == stat->lpcount);
3970  assert(col->redcost != SCIP_INVALID); /*lint !e777*/
3971 
3972  return col->redcost;
3973 }
3974 
3975 /** gets the feasibility of (the dual row of) a column in last LP or after recalculation */
3977  SCIP_COL* col, /**< LP column */
3978  SCIP_SET* set, /**< global SCIP settings */
3979  SCIP_STAT* stat, /**< problem statistics */
3980  SCIP_LP* lp /**< current LP data */
3981  )
3982 {
3983  assert(col != NULL);
3984  assert(set != NULL);
3985  assert(stat != NULL);
3986  assert(lp != NULL);
3987  assert(lp->validsollp == stat->lpcount);
3988 
3989  /* A column's reduced cost is defined as
3990  * redcost = obj - activity, activity = y^T * col. (activity = obj - redcost)
3991  * The activity is equal to the activity of the corresponding row in the dual LP.
3992  * The column's feasibility is the feasibility of the corresponding row in the dual LP.
3993  * The sides of the dual row depend on the bounds of the column:
3994  * - lb == ub : dual row is a free row with infinite sides
3995  * - 0 <= lb < ub: activity <= obj => 0 <= redcost
3996  * - lb < 0 < ub: obj <= activity <= obj => 0 <= redcost <= 0
3997  * - lb < ub <= 0: obj <= activity => redcost <= 0
3998  */
3999  if( SCIPsetIsEQ(set, col->lb, col->ub) )
4000  {
4001  /* dual row is free */
4002  return SCIPsetInfinity(set);
4003  }
4004  else
4005  {
4006  SCIP_Real redcost;
4007 
4008  /* calculate reduced costs */
4009  redcost = SCIPcolGetRedcost(col, stat, lp);
4010 
4011  if( !SCIPsetIsNegative(set, col->lb) )
4012  {
4013  /* dual row is activity <= obj <=> redcost >= 0 */
4014  return redcost;
4015  }
4016  else if( SCIPsetIsPositive(set, col->ub) )
4017  {
4018  /* dual row is activity == obj <=> redcost == 0 */
4019  return -REALABS(redcost);
4020  }
4021  else
4022  {
4023  /* dual row is activity >= obj <=> redcost <= 0 */
4024  return -redcost;
4025  }
4026  }
4027 }
4028 
4029 /** calculates the Farkas coefficient y^T A_i of a column i using the given dual Farkas vector y */
4031  SCIP_COL* col, /**< LP column */
4032  SCIP_Real* dualfarkas /**< dense dual Farkas vector for current LP rows */
4033  )
4034 {
4035  SCIP_ROW* row;
4036  SCIP_Real farkas;
4037  int i;
4038 
4039  assert(col != NULL);
4040  assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
4041  assert(SCIPvarGetCol(col->var) == col);
4042  assert(dualfarkas != NULL);
4043 
4044  farkas = 0.0;
4045  for( i = 0; i < col->nlprows; ++i )
4046  {
4047  row = col->rows[i];
4048  assert(row != NULL);
4049  assert(row->lppos >= 0);
4050  farkas += col->vals[i] * dualfarkas[row->lppos];
4051  }
4052 
4053  if( col->nunlinked > 0 )
4054  {
4055  for( i = col->nlprows; i < col->len; ++i )
4056  {
4057  row = col->rows[i];
4058  assert(row != NULL);
4059  assert(row->lppos == -1 || col->linkpos[i] == -1);
4060  if( row->lppos >= 0 )
4061  farkas += col->vals[i] * dualfarkas[row->lppos];
4062  }
4063  }
4064 #ifndef NDEBUG
4065  else
4066  {
4067  for( i = col->nlprows; i < col->len; ++i )
4068  {
4069  row = col->rows[i];
4070  assert(row != NULL);
4071  assert(row->lppos == -1);
4072  assert(col->linkpos[i] >= 0);
4073  }
4074  }
4075 #endif
4076 
4077  return farkas;
4078 }
4079 
4080 /** gets the Farkas coefficient y^T A_i of a column i in last LP (which must be infeasible) */
4081 static
4083  SCIP_COL* col /**< LP column */
4084  )
4085 {
4086  SCIP_ROW* row;
4087  SCIP_Real farkas;
4088  int i;
4089 
4090  assert(col != NULL);
4091  assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
4092  assert(SCIPvarGetCol(col->var) == col);
4093 
4094  farkas = 0.0;
4095  for( i = 0; i < col->nlprows; ++i )
4096  {
4097  row = col->rows[i];
4098  assert(row != NULL);
4099  assert(row->dualfarkas != SCIP_INVALID); /*lint !e777*/
4100  assert(row->lppos >= 0);
4101  assert(col->linkpos[i] >= 0);
4102  farkas += col->vals[i] * row->dualfarkas;
4103  }
4104 
4105  if( col->nunlinked > 0 )
4106  {
4107  for( i = col->nlprows; i < col->len; ++i )
4108  {
4109  row = col->rows[i];
4110  assert(row != NULL);
4111  assert(row->lppos >= 0 || row->dualfarkas == 0.0);
4112  assert(row->lppos == -1 || col->linkpos[i] == -1);
4113  if( row->lppos >= 0 )
4114  farkas += col->vals[i] * row->dualfarkas;
4115  }
4116  }
4117 #ifndef NDEBUG
4118  else
4119  {
4120  for( i = col->nlprows; i < col->len; ++i )
4121  {
4122  row = col->rows[i];
4123  assert(row != NULL);
4124  assert(row->dualfarkas == 0.0);
4125  assert(row->lppos == -1);
4126  assert(col->linkpos[i] >= 0);
4127  }
4128  }
4129 #endif
4130 
4131  return farkas;
4132 }
4133 
4134 /** gets the Farkas coefficient of a column in last LP (which must be infeasible) */
4136  SCIP_COL* col, /**< LP column */
4137  SCIP_STAT* stat, /**< problem statistics */
4138  SCIP_LP* lp /**< current LP data */
4139  )
4140 {
4141  assert(col != NULL);
4142  assert(stat != NULL);
4143  assert(lp != NULL);
4144  assert(col->validfarkaslp <= stat->lpcount);
4145  assert(lp->validfarkaslp == stat->lpcount);
4146 
4147  if( col->validfarkaslp < stat->lpcount )
4148  {
4150  col->validfarkaslp = stat->lpcount;
4151  }
4152  assert(col->validfarkaslp == stat->lpcount);
4153  assert(col->farkascoef != SCIP_INVALID); /*lint !e777*/
4154 
4155  return col->farkascoef;
4156 }
4157 
4158 /** gets the Farkas value of a column in last LP (which must be infeasible), i.e. the Farkas coefficient y^T A_i times
4159  * the best bound for this coefficient, i.e. max{y^T A_i x_i | lb <= x_i <= ub}
4160  */
4162  SCIP_COL* col, /**< LP column */
4163  SCIP_STAT* stat, /**< problem statistics */
4164  SCIP_LP* lp /**< current LP data */
4165  )
4166 {
4167  SCIP_Real farkascoef;
4168 
4169  assert(col != NULL);
4170 
4171  farkascoef = SCIPcolGetFarkasCoef(col, stat, lp);
4172 
4173  if( farkascoef > 0.0 )
4174  return col->ub * farkascoef;
4175  else
4176  return col->lb * farkascoef;
4177 }
4178 
4179 /** start strong branching - call before any strong branching */
4181  SCIP_LP* lp /**< LP data */
4182  )
4183 {
4184  assert(lp != NULL);
4185  assert(!lp->strongbranching);
4186 
4187  lp->strongbranching = TRUE;
4188  SCIPdebugMessage("starting strong branching ...\n");
4190 
4191  return SCIP_OKAY;
4192 }
4193 
4194 /** end strong branching - call after any strong branching */
4196  SCIP_LP* lp /**< LP data */
4197  )
4198 {
4199  assert(lp != NULL);
4200  assert(lp->strongbranching);
4201 
4202  lp->strongbranching = FALSE;
4203  SCIPdebugMessage("ending strong branching ...\n");
4205 
4206  return SCIP_OKAY;
4207 }
4208 
4209 /** sets strong branching information for a column variable */
4211  SCIP_COL* col, /**< LP column */
4212  SCIP_SET* set, /**< global SCIP settings */
4213  SCIP_STAT* stat, /**< dynamic problem statistics */
4214  SCIP_LP* lp, /**< LP data */
4215  SCIP_Real lpobjval, /**< objective value of the current LP */
4216  SCIP_Real primsol, /**< primal solution value of the column in the current LP */
4217  SCIP_Real sbdown, /**< dual bound after branching column down */
4218  SCIP_Real sbup, /**< dual bound after branching column up */
4219  SCIP_Bool sbdownvalid, /**< is the returned down value a valid dual bound? */
4220  SCIP_Bool sbupvalid, /**< is the returned up value a valid dual bound? */
4221  SCIP_Longint iter, /**< total number of strong branching iterations */
4222  int itlim /**< iteration limit applied to the strong branching call */
4223  )
4224 {
4225  assert(col != NULL);
4226  assert(col->var != NULL);
4227  assert(SCIPcolIsIntegral(col));
4228  assert(SCIPvarIsIntegral(col->var));
4229  assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
4230  assert(SCIPvarGetCol(col->var) == col);
4231  assert(col->lpipos >= 0);
4232  assert(col->lppos >= 0);
4233  assert(set != NULL);
4234  assert(stat != NULL);
4235  assert(lp != NULL);
4236  assert(lp->strongbranchprobing);
4237  assert(col->lppos < lp->ncols);
4238  assert(lp->cols[col->lppos] == col);
4239  assert(itlim >= 1);
4240 
4241  col->sblpobjval = lpobjval;
4242  col->sbsolval = primsol;
4243  col->validsblp = stat->nlps;
4244  col->sbnode = stat->nnodes;
4245 
4246  col->sbitlim = itlim;
4247  col->nsbcalls++;
4248 
4249  col->sbdown = MIN(sbdown, lp->cutoffbound);
4250  col->sbup = MIN(sbup, lp->cutoffbound);
4251  col->sbdownvalid = sbdownvalid;
4252  col->sbupvalid = sbupvalid;
4253 
4254  SCIPstatIncrement(stat, set, nstrongbranchs);
4255  SCIPstatAdd(stat, set, nsblpiterations, iter);
4256  if( stat->nnodes == 1 )
4257  {
4258  SCIPstatIncrement(stat, set, nrootstrongbranchs);
4259  SCIPstatAdd(stat, set, nrootsblpiterations, iter);
4260  }
4261 }
4262 
4263 /** invalidates strong branching information for a column variable */
4265  SCIP_COL* col, /**< LP column */
4266  SCIP_SET* set, /**< global SCIP settings */
4267  SCIP_STAT* stat, /**< dynamic problem statistics */
4268  SCIP_LP* lp /**< LP data */
4269  )
4270 {
4271  assert(col != NULL);
4272  assert(col->var != NULL);
4273  assert(SCIPcolIsIntegral(col));
4274  assert(SCIPvarIsIntegral(col->var));
4275  assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
4276  assert(SCIPvarGetCol(col->var) == col);
4277  assert(col->lpipos >= 0);
4278  assert(col->lppos >= 0);
4279  assert(set != NULL);
4280  assert(stat != NULL);
4281  assert(lp != NULL);
4282  assert(lp->strongbranchprobing);
4283  assert(col->lppos < lp->ncols);
4284  assert(lp->cols[col->lppos] == col);
4285 
4286  col->sbdown = SCIP_INVALID;
4287  col->sbup = SCIP_INVALID;
4288  col->sbdownvalid = FALSE;
4289  col->sbupvalid = FALSE;
4290  col->validsblp = -1;
4291  col->sbsolval = SCIP_INVALID;
4292  col->sblpobjval = SCIP_INVALID;
4293  col->sbnode = -1;
4294  col->sbitlim = -1;
4295 }
4296 
4297 
4298 /** gets strong branching information on a column variable */
4300  SCIP_COL* col, /**< LP column */
4301  SCIP_Bool integral, /**< should integral strong branching be performed? */
4302  SCIP_SET* set, /**< global SCIP settings */
4303  SCIP_STAT* stat, /**< dynamic problem statistics */
4304  SCIP_PROB* prob, /**< problem data */
4305  SCIP_LP* lp, /**< LP data */
4306  int itlim, /**< iteration limit for strong branchings */
4307  SCIP_Bool updatecol, /**< should col be updated, or should it stay in its current state ? */
4308  SCIP_Bool updatestat, /**< should stat be updated, or should it stay in its current state ? */
4309  SCIP_Real* down, /**< stores dual bound after branching column down */
4310  SCIP_Real* up, /**< stores dual bound after branching column up */
4311  SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound, or NULL;
4312  * otherwise, it can only be used as an estimate value */
4313  SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound, or NULL;
4314  * otherwise, it can only be used as an estimate value */
4315  SCIP_Bool* lperror /**< pointer to store whether an unresolved LP error occurred */
4316  )
4317 {
4318  SCIP_Real sbdown;
4319  SCIP_Real sbup;
4320  SCIP_Bool sbdownvalid;
4321  SCIP_Bool sbupvalid;
4322  SCIP_Longint validsblp;
4323  SCIP_Real sbsolval;
4324  SCIP_Real sblpobjval;
4325  SCIP_Longint sbnode;
4326  int sbitlim;
4327  int nsbcalls;
4328 
4329  assert(col != NULL);
4330  assert(col->var != NULL);
4331  assert(SCIPcolIsIntegral(col));
4332  assert(SCIPvarIsIntegral(col->var));
4333  assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
4334  assert(SCIPvarGetCol(col->var) == col);
4335  assert(col->primsol != SCIP_INVALID); /*lint !e777*/
4336  assert(col->lpipos >= 0);
4337  assert(col->lppos >= 0);
4338  assert(set != NULL);
4339  assert(stat != NULL);
4340  assert(lp != NULL);
4341  assert(lp->flushed);
4342  assert(lp->solved);
4343  assert(lp->strongbranching);
4344  assert(lp->lpsolstat == SCIP_LPSOLSTAT_OPTIMAL);
4345  assert(lp->validsollp == stat->lpcount);
4346  assert(col->lppos < lp->ncols);
4347  assert(lp->cols[col->lppos] == col);
4348  assert(itlim >= 1);
4349  /* assert(down != NULL);
4350  * assert(up != NULL); temporary hack for cloud branching
4351  */
4352  assert(lperror != NULL);
4353 
4354  *lperror = FALSE;
4355 
4356  sbdown = col->sbdown;
4357  sbup = col->sbup;
4358  sbdownvalid = col->sbdownvalid;
4359  sbupvalid = col->sbupvalid;
4360  sbitlim = col->sbitlim;
4361  nsbcalls = col->nsbcalls;
4362 
4363  validsblp = stat->nlps;
4364  sbsolval = col->primsol;
4365  sblpobjval = SCIPlpGetObjval(lp, set, prob);
4366  sbnode = stat->nnodes;
4367  assert(integral || !SCIPsetIsFeasIntegral(set, col->primsol));
4368 
4369  /* if a loose variables has an infinite best bound, the LP bound is -infinity and no gain can be achieved */
4370  if( lp->looseobjvalinf > 0 )
4371  {
4372  sbdown = -SCIPsetInfinity(set);
4373  sbup = -SCIPsetInfinity(set);
4374  sbdownvalid = FALSE;
4375  sbupvalid = FALSE;
4376  }
4377  else
4378  {
4379  SCIP_RETCODE retcode;
4380  int iter;
4381 
4382  SCIPsetDebugMsg(set, "performing strong branching on variable <%s>(%g) with %d iterations\n",
4383  SCIPvarGetName(col->var), col->primsol, itlim);
4384 
4385  /* start timing */
4386  SCIPclockStart(stat->strongbranchtime, set);
4387 
4388  /* call LPI strong branching */
4389  sbitlim = itlim;
4390  nsbcalls++;
4391 
4392  sbdown = lp->lpobjval;
4393  sbup = lp->lpobjval;
4394 
4395  if( integral )
4396  retcode = SCIPlpiStrongbranchInt(lp->lpi, col->lpipos, col->primsol, itlim, down == NULL ? NULL : &sbdown, up == NULL ? NULL : &sbup, &sbdownvalid, &sbupvalid, &iter);
4397  else
4398  {
4399  assert( ! SCIPsetIsIntegral(set, col->primsol) );
4400  retcode = SCIPlpiStrongbranchFrac(lp->lpi, col->lpipos, col->primsol, itlim, down == NULL ? NULL : &sbdown, up == NULL ? NULL : &sbup, &sbdownvalid, &sbupvalid, &iter);
4401  }
4402 
4403  /* check return code for errors */
4404  if( retcode == SCIP_LPERROR )
4405  {
4406  *lperror = TRUE;
4407  sbdown = SCIP_INVALID;
4408  sbup = SCIP_INVALID;
4409  sbdownvalid = FALSE;
4410  sbupvalid = FALSE;
4411  validsblp = -1;
4412  sbsolval = SCIP_INVALID;
4413  sblpobjval = SCIP_INVALID;
4414  sbnode = -1;
4415  }
4416  else
4417  {
4418  SCIP_Real looseobjval;
4419 
4420  *lperror = FALSE;
4421  SCIP_CALL( retcode );
4422 
4423  looseobjval = getFiniteLooseObjval(lp, set, prob);
4424  sbdown = MIN(sbdown + looseobjval, lp->cutoffbound);
4425  sbup = MIN(sbup + looseobjval, lp->cutoffbound);
4426 
4427  /* update strong branching statistics */
4428  if( updatestat )
4429  {
4430  if( iter == -1 )
4431  {
4432  /* calculate average iteration number */
4433  iter = stat->ndualresolvelps > 0 ? (int)(2*stat->ndualresolvelpiterations / stat->ndualresolvelps)
4434  : stat->nduallps > 0 ? (int)((stat->nduallpiterations / stat->nduallps) / 5)
4435  : stat->nprimalresolvelps > 0 ? (int)(2*stat->nprimalresolvelpiterations / stat->nprimalresolvelps)
4436  : stat->nprimallps > 0 ? (int)((stat->nprimallpiterations / stat->nprimallps) / 5)
4437  : 0;
4438  if( iter/2 >= itlim )
4439  iter = 2*itlim;
4440  }
4441  SCIPstatIncrement(stat, set, nstrongbranchs);
4442  SCIPstatAdd(stat, set, nsblpiterations, iter);
4443  if( stat->nnodes == 1 )
4444  {
4445  SCIPstatIncrement(stat, set, nrootstrongbranchs);
4446  SCIPstatAdd(stat, set, nrootsblpiterations, iter);
4447  }
4448  }
4449  }
4450 
4451  /* stop timing */
4452  SCIPclockStop(stat->strongbranchtime, set);
4453  }
4454  assert(*lperror || sbdown != SCIP_INVALID); /*lint !e777*/
4455  assert(*lperror || sbup != SCIP_INVALID); /*lint !e777*/
4456 
4457  if( down != NULL)
4458  *down = sbdown;
4459  if( up != NULL )
4460  *up = sbup;
4461  if( downvalid != NULL )
4462  *downvalid = sbdownvalid;
4463  if( upvalid != NULL )
4464  *upvalid = sbupvalid;
4465 
4466  if( updatecol )
4467  {
4468  col->sbdown = sbdown;
4469  col->sbup = sbup;
4470  col->sbdownvalid = sbdownvalid;
4471  col->sbupvalid = sbupvalid;
4472  col->validsblp = validsblp;
4473  col->sbsolval = sbsolval;
4474  col->sblpobjval = sblpobjval;
4475  col->sbnode = sbnode;
4476  col->sbitlim = sbitlim;
4477  col->nsbcalls = nsbcalls;
4478  }
4479 
4480  return SCIP_OKAY;
4481 }
4482 
4483 /** gets strong branching information on column variables */
4485  SCIP_COL** cols, /**< LP columns */
4486  int ncols, /**< number of columns */
4487  SCIP_Bool integral, /**< should integral strong branching be performed? */
4488  SCIP_SET* set, /**< global SCIP settings */
4489  SCIP_STAT* stat, /**< dynamic problem statistics */
4490  SCIP_PROB* prob, /**< problem data */
4491  SCIP_LP* lp, /**< LP data */
4492  int itlim, /**< iteration limit for strong branchings */
4493  SCIP_Real* down, /**< stores dual bounds after branching columns down */
4494  SCIP_Real* up, /**< stores dual bounds after branching columns up */
4495  SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds, or NULL;
4496  * otherwise, they can only be used as an estimate value */
4497  SCIP_Bool* upvalid, /**< stores whether the returned up values are valid dual bounds, or NULL;
4498  * otherwise, they can only be used as an estimate value */
4499  SCIP_Bool* lperror /**< pointer to store whether an unresolved LP error occurred */
4500  )
4501 {
4502  SCIP_RETCODE retcode;
4503  SCIP_Real* sbdown;
4504  SCIP_Real* sbup;
4505  SCIP_Bool* sbdownvalid;
4506  SCIP_Bool* sbupvalid;
4507  SCIP_Real* primsols;
4508  SCIP_COL** subcols;
4509  int* lpipos;
4510  int* subidx;
4511  int nsubcols;
4512  int iter;
4513  int j;
4514 
4515  assert(cols != NULL);
4516  assert(set != NULL);
4517  assert(stat != NULL);
4518  assert(lp != NULL);
4519  assert(lp->flushed);
4520  assert(lp->solved);
4521  assert(lp->lpsolstat == SCIP_LPSOLSTAT_OPTIMAL);
4522  assert(lp->validsollp == stat->lpcount);
4523  assert(itlim >= 1);
4524  assert(down != NULL);
4525  assert(up != NULL);
4526  assert(lperror != NULL);
4527 
4528  *lperror = FALSE;
4529 
4530  if ( ncols <= 0 )
4531  return SCIP_OKAY;
4532 
4533  /* start timing */
4534  SCIPclockStart(stat->strongbranchtime, set);
4535 
4536  /* initialize storage */
4537  SCIP_CALL( SCIPsetAllocBufferArray(set, &subcols, ncols) );
4538  SCIP_CALL( SCIPsetAllocBufferArray(set, &subidx, ncols) );
4539  SCIP_CALL( SCIPsetAllocBufferArray(set, &lpipos, ncols) );
4540  SCIP_CALL( SCIPsetAllocBufferArray(set, &primsols, ncols) );
4541  SCIP_CALL( SCIPsetAllocBufferArray(set, &sbdown, ncols) );
4542  SCIP_CALL( SCIPsetAllocBufferArray(set, &sbup, ncols) );
4543  SCIP_CALL( SCIPsetAllocBufferArray(set, &sbdownvalid, ncols) );
4544  SCIP_CALL( SCIPsetAllocBufferArray(set, &sbupvalid, ncols) );
4545 
4546  nsubcols = 0;
4547  for( j = 0; j < ncols; ++j )
4548  {
4549  SCIP_COL* col;
4550  col = cols[j];
4551 
4552  assert(col->lppos < lp->ncols);
4553  assert(lp->cols[col->lppos] == col);
4554  assert(SCIPcolIsIntegral(col));
4555  assert(SCIPvarIsIntegral(col->var));
4556  assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
4557  assert(SCIPvarGetCol(col->var) == col);
4558  assert(col->primsol != SCIP_INVALID); /*lint !e777*/
4559  assert(col->lpipos >= 0);
4560  assert(col->lppos >= 0);
4561 
4562  col->validsblp = stat->nlps;
4563  col->sbsolval = col->primsol;
4564  col->sblpobjval = SCIPlpGetObjval(lp, set, prob);
4565  col->sbnode = stat->nnodes;
4566  assert(!SCIPsetIsFeasIntegral(set, col->primsol));
4567 
4568  /* if a loose variables has an infinite best bound, the LP bound is -infinity and no gain can be achieved */
4569  if( lp->looseobjvalinf > 0 )
4570  {
4571  /* directly set up column and result vectors*/
4572  col->sbdown = -SCIPsetInfinity(set);
4573  col->sbup = -SCIPsetInfinity(set);
4574  col->sbdownvalid = FALSE;
4575  col->sbupvalid = FALSE;
4576  down[j] = col->sbdown;
4577  up[j] = col->sbup;
4578  if( downvalid != NULL )
4579  downvalid[j] = col->sbdownvalid;
4580  if( upvalid != NULL )
4581  upvalid[j] = col->sbupvalid;
4582  }
4583  else
4584  {
4585  col->sbitlim = itlim;
4586  col->nsbcalls++;
4587 
4588  lpipos[nsubcols] = col->lpipos;
4589  primsols[nsubcols] = col->primsol;
4590  assert( integral || ! SCIPsetIsFeasIntegral(set, col->primsol) );
4591  subidx[nsubcols] = j;
4592  subcols[nsubcols++] = col;
4593  }
4594  }
4595 
4596  SCIPsetDebugMsg(set, "performing strong branching on %d variables with %d iterations\n", ncols, itlim);
4597 
4598  /* call LPI strong branching */
4599  if ( integral )
4600  retcode = SCIPlpiStrongbranchesInt(lp->lpi, lpipos, nsubcols, primsols, itlim, sbdown, sbup, sbdownvalid, sbupvalid, &iter);
4601  else
4602  retcode = SCIPlpiStrongbranchesFrac(lp->lpi, lpipos, nsubcols, primsols, itlim, sbdown, sbup, sbdownvalid, sbupvalid, &iter);
4603 
4604  /* check return code for errors */
4605  if( retcode == SCIP_LPERROR )
4606  {
4607  *lperror = TRUE;
4608 
4609  for( j = 0; j < nsubcols; ++j )
4610  {
4611  SCIP_COL* col;
4612  int idx;
4613 
4614  col = subcols[j];
4615  idx = subidx[j];
4616 
4617  col->sbdown = SCIP_INVALID;
4618  col->sbup = SCIP_INVALID;
4619  col->sbdownvalid = FALSE;
4620  col->sbupvalid = FALSE;
4621  col->validsblp = -1;
4622  col->sbsolval = SCIP_INVALID;
4623  col->sblpobjval = SCIP_INVALID;
4624  col->sbnode = -1;
4625 
4626  down[idx] = col->sbdown;
4627  up[idx] = col->sbup;
4628  if( downvalid != NULL )
4629  downvalid[idx] = col->sbdownvalid;
4630  if( upvalid != NULL )
4631  upvalid[idx] = col->sbupvalid;
4632  }
4633  }
4634  else
4635  {
4636  SCIP_Real looseobjval;
4637 
4638  *lperror = FALSE;
4639  SCIP_CALL( retcode );
4640 
4641  looseobjval = getFiniteLooseObjval(lp, set, prob);
4642 
4643  for( j = 0; j < nsubcols; ++j )
4644  {
4645  SCIP_COL* col;
4646  int idx;
4647 
4648  col = subcols[j];
4649  idx = subidx[j];
4650 
4651  assert( col->sbdown != SCIP_INVALID); /*lint !e777*/
4652  assert( col->sbup != SCIP_INVALID); /*lint !e777*/
4653 
4654  col->sbdown = MIN(sbdown[j] + looseobjval, lp->cutoffbound);
4655  col->sbup = MIN(sbup[j] + looseobjval, lp->cutoffbound);
4656  col->sbdownvalid = sbdownvalid[j];
4657  col->sbupvalid = sbupvalid[j];
4658 
4659  down[idx] = col->sbdown;
4660  up[idx] = col->sbup;
4661  if( downvalid != NULL )
4662  downvalid[idx] = col->sbdownvalid;
4663  if( upvalid != NULL )
4664  upvalid[idx] = col->sbupvalid;
4665  }
4666 
4667  /* update strong branching statistics */
4668  if( iter == -1 )
4669  {
4670  /* calculate average iteration number */
4671  iter = stat->ndualresolvelps > 0 ? (int)(2*stat->ndualresolvelpiterations / stat->ndualresolvelps)
4672  : stat->nduallps > 0 ? (int)((stat->nduallpiterations / stat->nduallps) / 5)
4673  : stat->nprimalresolvelps > 0 ? (int)(2*stat->nprimalresolvelpiterations / stat->nprimalresolvelps)
4674  : stat->nprimallps > 0 ? (int)((stat->nprimallpiterations / stat->nprimallps) / 5)
4675  : 0;
4676  if( iter/2 >= itlim )
4677  iter = 2*itlim;
4678  }
4679  SCIPstatAdd(stat, set, nstrongbranchs, ncols);
4680  SCIPstatAdd(stat, set, nsblpiterations, iter);
4681  if( stat->nnodes == 1 )
4682  {
4683  SCIPstatAdd(stat, set, nrootstrongbranchs, ncols);
4684  SCIPstatAdd(stat, set, nrootsblpiterations, iter);
4685  }
4686  }
4687 
4688  SCIPsetFreeBufferArray(set, &sbupvalid);
4689  SCIPsetFreeBufferArray(set, &sbdownvalid);
4690  SCIPsetFreeBufferArray(set, &sbup);
4691  SCIPsetFreeBufferArray(set, &sbdown);
4692  SCIPsetFreeBufferArray(set, &primsols);
4693  SCIPsetFreeBufferArray(set, &lpipos);
4694  SCIPsetFreeBufferArray(set, &subidx);
4695  SCIPsetFreeBufferArray(set, &subcols);
4696 
4697  /* stop timing */
4698  SCIPclockStop(stat->strongbranchtime, set);
4699 
4700  return SCIP_OKAY;
4701 }
4702 
4703 /** gets last strong branching information available for a column variable;
4704  * returns values of SCIP_INVALID, if strong branching was not yet called on the given column;
4705  * keep in mind, that the returned old values may have nothing to do with the current LP solution
4706  */
4708  SCIP_COL* col, /**< LP column */
4709  SCIP_Real* down, /**< stores dual bound after branching column down, or NULL */
4710  SCIP_Real* up, /**< stores dual bound after branching column up, or NULL */
4711  SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound, or NULL;
4712  * otherwise, it can only be used as an estimate value */
4713  SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound, or NULL;
4714  * otherwise, it can only be used as an estimate value */
4715  SCIP_Real* solval, /**< stores LP solution value of column at last strong branching call, or NULL */
4716  SCIP_Real* lpobjval /**< stores LP objective value at last strong branching call, or NULL */
4717  )
4718 {
4719  assert(col != NULL);
4720 
4721  if( down != NULL )
4722  *down = col->sbdown;
4723  if( up != NULL )
4724  *up = col->sbup;
4725  if( downvalid != NULL )
4726  *downvalid = col->sbdownvalid;
4727  if( upvalid != NULL )
4728  *upvalid = col->sbupvalid;
4729  if( solval != NULL )
4730  *solval = col->sbsolval;
4731  if( lpobjval != NULL )
4732  *lpobjval = col->sblpobjval;
4733 }
4734 
4735 /** if strong branching was already applied on the column at the current node, returns the number of LPs solved after
4736  * the LP where the strong branching on this column was applied;
4737  * if strong branching was not yet applied on the column at the current node, returns INT_MAX
4738  */
4740  SCIP_COL* col, /**< LP column */
4741  SCIP_STAT* stat /**< dynamic problem statistics */
4742  )
4743 {
4744  assert(col != NULL);
4745  assert(stat != NULL);
4746 
4747  return (col->sbnode != stat->nnodes ? SCIP_LONGINT_MAX : stat->nlps - col->validsblp);
4748 }
4749 
4750 /** marks a column to be not removable from the LP in the current node because it became obsolete */
4752  SCIP_COL* col, /**< LP column */
4753  SCIP_STAT* stat /**< problem statistics */
4754  )
4755 {
4756  assert(col != NULL);
4757  assert(stat != NULL);
4758  assert(stat->nnodes > 0);
4759 
4760  /* lpRemoveObsoleteCols() does not remove a column if the node number stored in obsoletenode equals the current node number */
4761  col->obsoletenode = stat->nnodes;
4762 }
4763 
4764 
4765 /*
4766  * Row methods
4767  */
4768 
4769 /** calculates row norms and min/maxidx from scratch, and checks for sorting */
4770 static
4772  SCIP_ROW* row, /**< LP row */
4773  SCIP_SET* set /**< global SCIP settings */
4774  )
4775 {
4776  int i;
4777 
4778  assert(row != NULL);
4779  assert(set != NULL);
4780 
4781  row->sqrnorm = 0.0;
4782  row->sumnorm = 0.0;
4783  row->objprod = 0.0;
4784  row->maxval = 0.0;
4785  row->nummaxval = 1;
4786  row->minval = SCIPsetInfinity(set);
4787  row->numminval = 1;
4788  row->minidx = INT_MAX;
4789  row->maxidx = INT_MIN;
4790  row->validminmaxidx = TRUE;
4791  row->lpcolssorted = TRUE;
4792  row->nonlpcolssorted = TRUE;
4793 
4794  /* check, if row is sorted
4795  * calculate sqrnorm, sumnorm, maxval, minval, minidx, and maxidx
4796  */
4797  for( i = 0; i < row->nlpcols; ++i )
4798  {
4799  assert(row->cols[i] != NULL);
4800  assert(!SCIPsetIsZero(set, row->vals[i]));
4801  assert(row->cols[i]->lppos >= 0);
4802  assert(row->linkpos[i] >= 0);
4803  assert(row->cols[i]->index == row->cols_index[i]);
4804 
4805  rowAddNorms(row, set, row->cols[i], row->vals[i], TRUE);
4806  if( i > 0 )
4807  {
4808  assert(row->cols[i-1]->index == row->cols_index[i-1]);
4809  row->lpcolssorted = row->lpcolssorted && (row->cols_index[i-1] < row->cols_index[i]);
4810  }
4811  }
4812  for( i = row->nlpcols; i < row->len; ++i )
4813  {
4814  assert(row->cols[i] != NULL);
4815  assert(!SCIPsetIsZero(set, row->vals[i]));
4816  assert(row->cols[i]->lppos == -1 || row->linkpos[i] == -1);
4817  assert(row->cols[i]->index == row->cols_index[i]);
4818 
4819  rowAddNorms(row, set, row->cols[i], row->vals[i], TRUE);
4820  if( i > row->nlpcols )
4821  {
4822  assert(row->cols[i-1]->index == row->cols_index[i-1]);
4823  row->nonlpcolssorted = row->nonlpcolssorted && (row->cols_index[i-1] < row->cols_index[i]);
4824  }
4825  }
4826 }
4827 
4828 /** calculates min/maxval and min/maxidx from scratch */
4829 static
4831  SCIP_ROW* row, /**< LP row */
4832  SCIP_SET* set /**< global SCIP settings */
4833  )
4834 {
4835  SCIP_COL* col;
4836  SCIP_Real absval;
4837  int i;
4838 
4839  assert(row != NULL);
4840  assert(set != NULL);
4841 
4842  row->maxval = 0.0;
4843  row->nummaxval = 1;
4844  row->numintcols = 0;
4845  row->minval = SCIPsetInfinity(set);
4846  row->numminval = 1;
4847  row->minidx = INT_MAX;
4848  row->maxidx = INT_MIN;
4849  row->validminmaxidx = TRUE;
4850 
4851  /* calculate maxval, minval, minidx, and maxidx */
4852  for( i = 0; i < row->len; ++i )
4853  {
4854  col = row->cols[i];
4855  assert(col != NULL);
4856  assert(!SCIPsetIsZero(set, row->vals[i]));
4857 
4858  absval = REALABS(row->vals[i]);
4859  assert(!SCIPsetIsZero(set, absval));
4860 
4861  /* update min/maxidx */
4862  row->minidx = MIN(row->minidx, col->index);
4863  row->maxidx = MAX(row->maxidx, col->index);
4864  row->numintcols += SCIPcolIsIntegral(col); /*lint !e713*/
4865 
4866  /* update maximal and minimal non-zero value */
4867  if( row->nummaxval > 0 )
4868  {
4869  if( SCIPsetIsGT(set, absval, row->maxval) )
4870  {
4871  row->maxval = absval;
4872  row->nummaxval = 1;
4873  }
4874  else if( SCIPsetIsGE(set, absval, row->maxval) )
4875  {
4876  /* make sure the maxval is always exactly the same */
4877  row->maxval = MAX(absval, row->maxval);
4878  row->nummaxval++;
4879  }
4880  }
4881  if( row->numminval > 0 )
4882  {
4883  if( SCIPsetIsLT(set, absval, row->minval) )
4884  {
4885  row->minval = absval;
4886  row->numminval = 1;
4887  }
4888  else if( SCIPsetIsLE(set, absval, row->minval) )
4889  {
4890  /* make sure the minval is always exactly the same */
4891  row->minval = MIN(absval, row->minval);
4892  row->numminval++;
4893  }
4894  }
4895  }
4896 }
4897 
4898 /** checks, whether the given scalar scales the given value to an integral number with error in the given bounds */
4899 static
4901  SCIP_Real val, /**< value that should be scaled to an integral value */
4902  SCIP_Real scalar, /**< scalar that should be tried */
4903  SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
4904  SCIP_Real maxdelta, /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
4905  SCIP_Real* intval /**< pointer to store the scaled integral value, or NULL */
4906  )
4907 {
4908  SCIP_Real sval;
4909  SCIP_Real downval;
4910  SCIP_Real upval;
4911 
4912  assert(mindelta <= 0.0);
4913  assert(maxdelta >= 0.0);
4914 
4915  sval = val * scalar;
4916  downval = floor(sval);
4917  upval = ceil(sval);
4918 
4919  if( SCIPrelDiff(sval, downval) <= maxdelta )
4920  {
4921  if( intval != NULL )
4922  *intval = downval;
4923  return TRUE;
4924  }
4925  else if( SCIPrelDiff(sval, upval) >= mindelta )
4926  {
4927  if( intval != NULL )
4928  *intval = upval;
4929  return TRUE;
4930  }
4931 
4932  return FALSE;
4933 }
4934 
4935 /** scales row with given factor, and rounds coefficients to integers if close enough;
4936  * the constant is automatically moved to the sides;
4937  * if the row's activity is proven to be integral, the sides are automatically rounded to the next integer
4938  */
4939 static
4941  SCIP_ROW* row, /**< LP row */
4942  BMS_BLKMEM* blkmem, /**< block memory */
4943  SCIP_SET* set, /**< global SCIP settings */
4944  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4945  SCIP_STAT* stat, /**< problem statistics */
4946  SCIP_LP* lp, /**< current LP data */
4947  SCIP_Real scaleval, /**< value to scale row with */
4948  SCIP_Bool integralcontvars, /**< should the coefficients of the continuous variables also be made integral,
4949  * if they are close to integral values? */
4950  SCIP_Real minrounddelta, /**< minimal relative difference of scaled coefficient s*c and integral i,
4951  * upto which the integral is used instead of the scaled real coefficient */
4952  SCIP_Real maxrounddelta /**< maximal relative difference of scaled coefficient s*c and integral i
4953  * upto which the integral is used instead of the scaled real coefficient */
4954  )
4955 {
4956  SCIP_COL* col;
4957  SCIP_Real val;
4958  SCIP_Real newval;
4959  SCIP_Real intval;
4960  SCIP_Real mindelta;
4961  SCIP_Real maxdelta;
4962  SCIP_Real lb;
4963  SCIP_Real ub;
4964  SCIP_Bool mindeltainf;
4965  SCIP_Bool maxdeltainf;
4966  int oldlen;
4967  int c;
4968 
4969  assert(row != NULL);
4970  assert(row->len == 0 || row->cols != NULL);
4971  assert(row->len == 0 || row->vals != NULL);
4972  assert(SCIPsetIsPositive(set, scaleval));
4973  assert(-1.0 < minrounddelta && minrounddelta <= 0.0);
4974  assert(0.0 <= maxrounddelta && maxrounddelta < 1.0);
4975 
4976  SCIPsetDebugMsg(set, "scale row <%s> with %g (tolerance=[%g,%g])\n", row->name, scaleval, minrounddelta, maxrounddelta);
4977 
4978  mindelta = 0.0;
4979  maxdelta = 0.0;
4980  mindeltainf = FALSE;
4981  maxdeltainf = FALSE;
4982  oldlen = row->len;
4983 
4984  /* scale the row coefficients, thereby recalculating whether the row's activity is always integral;
4985  * if the row coefficients are rounded to the nearest integer value, calculate the maximal activity difference,
4986  * this rounding can lead to
4987  */
4988  row->integral = TRUE;
4989 
4990  c = 0;
4991  while( c < row->len )
4992  {
4993  col = row->cols[c];
4994  val = row->vals[c];
4995  assert(!SCIPsetIsZero(set, val));
4996 
4997  /* get local or global bounds for column, depending on the local or global feasibility of the row */
4998  if( row->local )
4999  {
5000  lb = col->lb;
5001  ub = col->ub;
5002  }
5003  else
5004  {
5005  lb = SCIPvarGetLbGlobal(col->var);
5006  ub = SCIPvarGetUbGlobal(col->var);
5007  }
5008 
5009  /* calculate scaled coefficient */
5010  newval = val * scaleval;
5011  if( (integralcontvars || SCIPcolIsIntegral(col) || SCIPsetIsIntegral(set, newval))
5012  && isIntegralScalar(val, scaleval, minrounddelta, maxrounddelta, &intval) )
5013  {
5014  if( !SCIPsetIsEQ(set, intval, newval) )
5015  {
5016  if( intval < newval )
5017  {
5018  mindelta += (intval - newval)*ub;
5019  maxdelta += (intval - newval)*lb;
5020  mindeltainf = mindeltainf || SCIPsetIsInfinity(set, ub);
5021  maxdeltainf = maxdeltainf || SCIPsetIsInfinity(set, -lb);
5022  }
5023  else
5024  {
5025  mindelta += (intval - newval)*lb;
5026  maxdelta += (intval - newval)*ub;
5027  mindeltainf = mindeltainf || SCIPsetIsInfinity(set, -lb);
5028  maxdeltainf = maxdeltainf || SCIPsetIsInfinity(set, ub);
5029  }
5030  }
5031  newval = intval;
5032  }
5033 
5034  if( !SCIPsetIsEQ(set, val, newval) )
5035  {
5036  /* if column knows of the row, change the corresponding coefficient in the column */
5037  if( row->linkpos[c] >= 0 )
5038  {
5039  assert(col->rows[row->linkpos[c]] == row);
5040  assert(SCIPsetIsEQ(set, col->vals[row->linkpos[c]], row->vals[c]));
5041  SCIP_CALL( colChgCoefPos(col, set, lp, row->linkpos[c], newval) );
5042  }
5043 
5044  /* change the coefficient in the row, and update the norms and integrality status */
5045  SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, c, newval) );
5046 
5047  /* current coefficient has been deleted from the row because it was almost zero */
5048  if( oldlen != row->len )
5049  {
5050  assert(row->len == oldlen - 1);
5051  c--;
5052  oldlen = row->len;
5053  }
5054  }
5055  else
5056  row->integral = row->integral && SCIPcolIsIntegral(col) && SCIPsetIsIntegral(set, val);
5057 
5058  ++c;
5059  }
5060 
5061  /* scale the row sides, and move the constant to the sides; relax the sides with accumulated delta in order
5062  * to not destroy feasibility due to rounding
5063  */
5064  /**@todo ensure that returned cut does not have infinite lhs and rhs */
5065  if( !SCIPsetIsInfinity(set, -row->lhs) )
5066  {
5067  if( mindeltainf )
5068  newval = -SCIPsetInfinity(set);
5069  else
5070  {
5071  newval = (row->lhs - row->constant) * scaleval + mindelta;
5072  if( SCIPsetIsIntegral(set, newval) || (row->integral && !row->modifiable) )
5073  newval = SCIPsetSumCeil(set, newval);
5074  }
5075  SCIP_CALL( SCIProwChgLhs(row, blkmem, set, eventqueue, lp, newval) );
5076  }
5077  if( !SCIPsetIsInfinity(set, row->rhs) )
5078  {
5079  if( maxdeltainf )
5080  newval = SCIPsetInfinity(set);
5081  else
5082  {
5083  newval = (row->rhs - row->constant) * scaleval + maxdelta;
5084  if( SCIPsetIsIntegral(set, newval) || (row->integral && !row->modifiable) )
5085  newval = SCIPsetSumFloor(set, newval);
5086  }
5087  SCIP_CALL( SCIProwChgRhs(row, blkmem, set, eventqueue, lp, newval) );
5088  }
5089 
5090  /* clear the row constant */
5091  SCIP_CALL( SCIProwChgConstant(row, blkmem, set, stat, eventqueue, lp, 0.0) );
5092 
5093  SCIPsetDebugMsg(set, "scaled row <%s> (integral: %u)\n", row->name, row->integral);
5094  debugRowPrint(set, row);
5095 
5096 #ifdef SCIP_DEBUG
5097  /* check integrality status of row */
5098  for( c = 0; c < row->len && SCIPcolIsIntegral(row->cols[c]) && SCIPsetIsIntegral(set, row->vals[c]); ++c )
5099  {}
5100  assert(row->integral == (c == row->len));
5101 #endif
5102 
5103  /* invalid the activity */
5104  row->validactivitylp = -1;
5105 
5106  return SCIP_OKAY;
5107 }
5108 
5109 /** creates and captures an LP row */
5111  SCIP_ROW** row, /**< pointer to LP row data */
5112  BMS_BLKMEM* blkmem, /**< block memory */
5113  SCIP_SET* set, /**< global SCIP settings */
5114  SCIP_STAT* stat, /**< problem statistics */
5115  const char* name, /**< name of row */
5116  int len, /**< number of nonzeros in the row */
5117  SCIP_COL** cols, /**< array with columns of row entries */
5118  SCIP_Real* vals, /**< array with coefficients of row entries */
5119  SCIP_Real lhs, /**< left hand side of row */
5120  SCIP_Real rhs, /**< right hand side of row */
5121  SCIP_ROWORIGINTYPE origintype, /**< type of origin of row */
5122  void* origin, /**< pointer to constraint handler or separator who created the row (NULL if unkown) */
5123  SCIP_Bool local, /**< is row only valid locally? */
5124  SCIP_Bool modifiable, /**< is row modifiable during node processing (subject to column generation)? */
5125  SCIP_Bool removable /**< should the row be removed from the LP due to aging or cleanup? */
5126  )
5127 {
5128  assert(row != NULL);
5129  assert(blkmem != NULL);
5130  assert(stat != NULL);
5131  assert(len >= 0);
5132  assert(len == 0 || (cols != NULL && vals != NULL));
5133  /* note, that the assert tries to avoid numerical troubles in the LP solver.
5134  * in case, for example, lhs > rhs but they are equal with tolerances, one could pass lhs=rhs=lhs+rhs/2 to
5135  * SCIProwCreate() (see cons_linear.c: detectRedundantConstraints())
5136  */
5137  assert(lhs <= rhs);
5138 
5139  SCIP_ALLOC( BMSallocBlockMemory(blkmem, row) );
5140 
5141  (*row)->integral = TRUE;
5142  if( len > 0 )
5143  {
5144  SCIP_VAR* var;
5145  int i;
5146 
5147  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*row)->cols, cols, len) );
5148  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*row)->vals, vals, len) );
5149  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*row)->cols_index, len) );
5150  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*row)->linkpos, len) );
5151 
5152  for( i = 0; i < len; ++i )
5153  {
5154  assert(cols[i] != NULL);
5155  assert(!SCIPsetIsZero(set, vals[i]));
5156 
5157  var = cols[i]->var;
5158  (*row)->cols_index[i] = cols[i]->index;
5159  (*row)->linkpos[i] = -1;
5160  if( SCIPsetIsIntegral(set, (*row)->vals[i]) )
5161  {
5162  (*row)->vals[i] = SCIPsetRound(set, (*row)->vals[i]);
5163  (*row)->integral = (*row)->integral && SCIPvarIsIntegral(var);
5164  }
5165  else
5166  {
5167  (*row)->integral = FALSE;
5168  }
5169  }
5170  }
5171  else
5172  {
5173  (*row)->cols = NULL;
5174  (*row)->cols_index = NULL;
5175  (*row)->vals = NULL;
5176  (*row)->linkpos = NULL;
5177  }
5178 
5179  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*row)->name, name, strlen(name)+1) );
5180  (*row)->constant = 0.0;
5181  (*row)->lhs = lhs;
5182  (*row)->rhs = rhs;
5183  (*row)->flushedlhs = -SCIPsetInfinity(set);
5184  (*row)->flushedrhs = SCIPsetInfinity(set);
5185  (*row)->sqrnorm = 0.0;
5186  (*row)->sumnorm = 0.0;
5187  (*row)->objprod = 0.0;
5188  (*row)->maxval = 0.0;
5189  (*row)->minval = SCIPsetInfinity(set);
5190  (*row)->dualsol = 0.0;
5191  (*row)->activity = SCIP_INVALID;
5192  (*row)->dualfarkas = 0.0;
5193  (*row)->pseudoactivity = SCIP_INVALID;
5194  (*row)->minactivity = SCIP_INVALID;
5195  (*row)->maxactivity = SCIP_INVALID;
5196  (*row)->origin = origin;
5197  (*row)->eventfilter = NULL;
5198  (*row)->index = stat->nrowidx;
5199  SCIPstatIncrement(stat, set, nrowidx);
5200  (*row)->size = len;
5201  (*row)->len = len;
5202  (*row)->nlpcols = 0;
5203  (*row)->nunlinked = len;
5204  (*row)->nuses = 0;
5205  (*row)->lppos = -1;
5206  (*row)->lpipos = -1;
5207  (*row)->lpdepth = -1;
5208  (*row)->minidx = INT_MAX;
5209  (*row)->maxidx = INT_MIN;
5210  (*row)->nummaxval = 0;
5211  (*row)->numminval = 0;
5212  (*row)->numintcols = -1;
5213  (*row)->validactivitylp = -1;
5214  (*row)->validpsactivitydomchg = -1;
5215  (*row)->validactivitybdsdomchg = -1;
5216  (*row)->nlpsaftercreation = 0L;
5217  (*row)->activeinlpcounter = 0L;
5218  (*row)->age = 0;
5219  (*row)->rank = 0;
5220  (*row)->obsoletenode = -1;
5221  (*row)->fromcutpool = FALSE;
5222  (*row)->basisstatus = SCIP_BASESTAT_BASIC; /*lint !e641*/
5223  (*row)->lpcolssorted = TRUE;
5224  (*row)->nonlpcolssorted = (len <= 1);
5225  (*row)->delaysort = FALSE;
5226  (*row)->validminmaxidx = FALSE;
5227  (*row)->lhschanged = FALSE;
5228  (*row)->rhschanged = FALSE;
5229  (*row)->coefchanged = FALSE;
5230  (*row)->local = local;
5231  (*row)->modifiable = modifiable;
5232  (*row)->nlocks = 0;
5233  (*row)->origintype = origintype; /*lint !e641*/
5234  (*row)->removable = removable;
5235  (*row)->inglobalcutpool = FALSE;
5236  (*row)->storedsolvals = NULL;
5237 
5238  /* calculate row norms and min/maxidx, and check if row is sorted */
5239  rowCalcNorms(*row, set);
5240 
5241  /* capture the row */
5242  SCIProwCapture(*row);
5243 
5244  /* create event filter */
5245  SCIP_CALL( SCIPeventfilterCreate(&(*row)->eventfilter, blkmem) );
5246 
5247  /* capture origin constraint if available */
5248  if( origintype == SCIP_ROWORIGINTYPE_CONS )
5249  {
5250  SCIP_CONS* cons = (SCIP_CONS*) origin;
5251  assert(cons != NULL);
5252  SCIPconsCapture(cons);
5253  }
5254 
5255  return SCIP_OKAY;
5256 } /*lint !e715*/
5257 
5258 /** frees an LP row */
5260  SCIP_ROW** row, /**< pointer to LP row */
5261  BMS_BLKMEM* blkmem, /**< block memory */
5262  SCIP_SET* set, /**< global SCIP settings */
5263  SCIP_LP* lp /**< current LP data */
5264  )
5265 {
5266  assert(blkmem != NULL);
5267  assert(row != NULL);
5268  assert(*row != NULL);
5269  assert((*row)->nuses == 0);
5270  assert((*row)->lppos == -1);
5271  assert((*row)->eventfilter != NULL);
5272 
5273  /* release constraint that has been used for creating the row */
5274  if( (SCIP_ROWORIGINTYPE) (*row)->origintype == SCIP_ROWORIGINTYPE_CONS )
5275  {
5276  SCIP_CONS* cons = (SCIP_CONS*) (*row)->origin;
5277  assert(cons != NULL);
5278  SCIP_CALL( SCIPconsRelease(&cons, blkmem, set) );
5279  }
5280 
5281  /* remove column indices from corresponding rows */
5282  SCIP_CALL( rowUnlink(*row, set, lp) );
5283 
5284  /* free event filter */
5285  SCIP_CALL( SCIPeventfilterFree(&(*row)->eventfilter, blkmem, set) );
5286 
5287  BMSfreeBlockMemoryNull(blkmem, &(*row)->storedsolvals);
5288  BMSfreeBlockMemoryArray(blkmem, &(*row)->name, strlen((*row)->name)+1);
5289  BMSfreeBlockMemoryArrayNull(blkmem, &(*row)->cols, (*row)->size);
5290  BMSfreeBlockMemoryArrayNull(blkmem, &(*row)->cols_index, (*row)->size);
5291  BMSfreeBlockMemoryArrayNull(blkmem, &(*row)->vals, (*row)->size);
5292  BMSfreeBlockMemoryArrayNull(blkmem, &(*row)->linkpos, (*row)->size);
5293  BMSfreeBlockMemory(blkmem, row);
5294 
5295  return SCIP_OKAY;
5296 }
5297 
5298 /** output row to file stream */
5300  SCIP_ROW* row, /**< LP row */
5301  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
5302  FILE* file /**< output file (or NULL for standard output) */
5303  )
5304 {
5305  int i;
5306 
5307  assert(row != NULL);
5308 
5309  /* print row name */
5310  if( row->name != NULL && row->name[0] != '\0' )
5311  {
5312  SCIPmessageFPrintInfo(messagehdlr, file, "%s: ", row->name);
5313  }
5314 
5315  /* print left hand side */
5316  SCIPmessageFPrintInfo(messagehdlr, file, "%.15g <= ", row->lhs);
5317 
5318  /* print coefficients */
5319  if( row->len == 0 )
5320  SCIPmessageFPrintInfo(messagehdlr, file, "0 ");
5321  for( i = 0; i < row->len; ++i )
5322  {
5323  assert(row->cols[i] != NULL);
5324  assert(row->cols[i]->var != NULL);
5325  assert(SCIPvarGetName(row->cols[i]->var) != NULL);
5326  assert(SCIPvarGetStatus(row->cols[i]->var) == SCIP_VARSTATUS_COLUMN);
5327  SCIPmessageFPrintInfo(messagehdlr, file, "%+.15g<%s> ", row->vals[i], SCIPvarGetName(row->cols[i]->var));
5328  }
5329 
5330  /* print constant */
5331  if( REALABS(row->constant) > SCIP_DEFAULT_EPSILON )
5332  SCIPmessageFPrintInfo(messagehdlr, file, "%+.15g ", row->constant);
5333 
5334  /* print right hand side */
5335  SCIPmessageFPrintInfo(messagehdlr, file, "<= %.15g\n", row->rhs);
5336 }
5337 
5338 /** increases usage counter of LP row */
5340  SCIP_ROW* row /**< LP row */
5341  )
5342 {
5343  assert(row != NULL);
5344  assert(row->nuses >= 0);
5345  assert(row->nlocks <= (unsigned int)(row->nuses)); /*lint !e574*/
5346 
5347  SCIPdebugMessage("capture row <%s> with nuses=%d and nlocks=%u\n", row->name, row->nuses, row->nlocks);
5348  row->nuses++;
5349 }
5350 
5351 /** decreases usage counter of LP row, and frees memory if necessary */
5353  SCIP_ROW** row, /**< pointer to LP row */
5354  BMS_BLKMEM* blkmem, /**< block memory */
5355  SCIP_SET* set, /**< global SCIP settings */
5356  SCIP_LP* lp /**< current LP data */
5357  )
5358 {
5359  assert(blkmem != NULL);
5360  assert(row != NULL);
5361  assert(*row != NULL);
5362  assert((*row)->nuses >= 1);
5363  assert((*row)->nlocks < (unsigned int)((*row)->nuses)); /*lint !e574*/
5364 
5365  SCIPsetDebugMsg(set, "release row <%s> with nuses=%d and nlocks=%u\n", (*row)->name, (*row)->nuses, (*row)->nlocks);
5366  (*row)->nuses--;
5367  if( (*row)->nuses == 0 )
5368  {
5369  SCIP_CALL( SCIProwFree(row, blkmem, set, lp) );
5370  }
5371 
5372  *row = NULL;
5373 
5374  return SCIP_OKAY;
5375 }
5376 
5377 /** locks an unmodifiable row, which forbids further changes; has no effect on modifiable rows */
5379  SCIP_ROW* row /**< LP row */
5380  )
5381 {
5382  assert(row != NULL);
5383 
5384  /* check, if row is modifiable */
5385  if( !row->modifiable )
5386  {
5387  SCIPdebugMessage("lock row <%s> with nuses=%d and nlocks=%u\n", row->name, row->nuses, row->nlocks);
5388  row->nlocks++;
5389  }
5390 }
5391 
5392 /** unlocks a lock of an unmodifiable row; a row with no sealed lock may be modified; has no effect on modifiable rows */
5394  SCIP_ROW* row /**< LP row */
5395  )
5396 {
5397  assert(row != NULL);
5398 
5399  /* check, if row is modifiable */
5400  if( !row->modifiable )
5401  {
5402  SCIPdebugMessage("unlock row <%s> with nuses=%d and nlocks=%u\n", row->name, row->nuses, row->nlocks);
5403  assert(row->nlocks > 0);
5404  row->nlocks--;
5405  }
5406 }
5407 
5408 /** adds a previously non existing coefficient to an LP row */
5410  SCIP_ROW* row, /**< LP row */
5411  BMS_BLKMEM* blkmem, /**< block memory */
5412  SCIP_SET* set, /**< global SCIP settings */
5413  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
5414  SCIP_LP* lp, /**< current LP data */
5415  SCIP_COL* col, /**< LP column */
5416  SCIP_Real val /**< value of coefficient */
5417  )
5418 {
5419  assert(lp != NULL);
5420  assert(!lp->diving || row->lppos == -1);
5421 
5422  SCIP_CALL( rowAddCoef(row, blkmem, set, eventqueue, lp, col, val, -1) );
5423 
5424  checkLinks(lp);
5425 
5426  return SCIP_OKAY;
5427 }
5428 
5429 /** deletes coefficient from row */
5431  SCIP_ROW* row, /**< row to be changed */
5432  BMS_BLKMEM* blkmem, /**< block memory */
5433  SCIP_SET* set, /**< global SCIP settings */
5434  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
5435  SCIP_LP* lp, /**< current LP data */
5436  SCIP_COL* col /**< coefficient to be deleted */
5437  )
5438 {
5439  int pos;
5440 
5441  assert(row != NULL);
5442  assert(!row->delaysort);
5443  assert(lp != NULL);
5444  assert(!lp->diving || row->lppos == -1);
5445  assert(col != NULL);
5446  assert(col->var != NULL);
5447 
5448  /* search the position of the column in the row's col vector */
5449  pos = rowSearchCoef(row, col);
5450  if( pos == -1 )
5451  {
5452  SCIPerrorMessage("coefficient for column <%s> doesn't exist in row <%s>\n", SCIPvarGetName(col->var), row->name);
5453  return SCIP_INVALIDDATA;
5454  }
5455  assert(0 <= pos && pos < row->len);
5456  assert(row->cols[pos] == col);
5457  assert(row->cols_index[pos] == col->index);
5458 
5459  /* if column knows of the row, remove the row from the column's row vector */
5460  if( row->linkpos[pos] >= 0 )
5461  {
5462  assert(col->rows[row->linkpos[pos]] == row);
5463  assert(SCIPsetIsEQ(set, col->vals[row->linkpos[pos]], row->vals[pos]));
5464  SCIP_CALL( colDelCoefPos(col, set, lp, row->linkpos[pos]) );
5465  }
5466 
5467  /* delete the column from the row's col vector */
5468  SCIP_CALL( rowDelCoefPos(row, blkmem, set, eventqueue, lp, pos) );
5469 
5470  checkLinks(lp);
5471 
5472  return SCIP_OKAY;
5473 }
5474 
5475 /** changes or adds a coefficient to an LP row */
5477  SCIP_ROW* row, /**< LP row */
5478  BMS_BLKMEM* blkmem, /**< block memory */
5479  SCIP_SET* set, /**< global SCIP settings */
5480  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
5481  SCIP_LP* lp, /**< current LP data */
5482  SCIP_COL* col, /**< LP column */
5483  SCIP_Real val /**< value of coefficient */
5484  )
5485 {
5486  int pos;
5487 
5488  assert(row != NULL);
5489  assert(!row->delaysort);
5490  assert(lp != NULL);
5491  assert(!lp->diving || row->lppos == -1);
5492  assert(col != NULL);
5493 
5494  /* search the position of the column in the row's col vector */
5495  pos = rowSearchCoef(row, col);
5496 
5497  /* check, if column already exists in the row's col vector */
5498  if( pos == -1 )
5499  {
5500  /* add previously not existing coefficient */
5501  SCIP_CALL( rowAddCoef(row, blkmem, set, eventqueue, lp, col, val, -1) );
5502  }
5503  else
5504  {
5505  /* modify already existing coefficient */
5506  assert(0 <= pos && pos < row->len);
5507  assert(row->cols[pos] == col);
5508  assert(row->cols_index[pos] == col->index);
5509 
5510  /* if column knows of the row, change the corresponding coefficient in the column */
5511  if( row->linkpos[pos] >= 0 )
5512  {
5513  assert(col->rows[row->linkpos[pos]] == row);
5514  assert(SCIPsetIsEQ(set, col->vals[row->linkpos[pos]], row->vals[pos]));
5515  SCIP_CALL( colChgCoefPos(col, set, lp, row->linkpos[pos], val) );
5516  }
5517 
5518  /* change the coefficient in the row */
5519  SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, pos, val) );
5520  }
5521 
5522  checkLinks(lp);
5523 
5524  return SCIP_OKAY;
5525 }
5526 
5527 /** increases value of an existing or non-existing coefficient in an LP row */
5529  SCIP_ROW* row, /**< LP row */
5530  BMS_BLKMEM* blkmem, /**< block memory */
5531  SCIP_SET* set, /**< global SCIP settings */
5532  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
5533  SCIP_LP* lp, /**< current LP data */
5534  SCIP_COL* col, /**< LP column */
5535  SCIP_Real incval /**< value to add to the coefficient */
5536  )
5537 {
5538  int pos;
5539 
5540  assert(row != NULL);
5541  assert(lp != NULL);
5542  assert(!lp->diving || row->lppos == -1);
5543  assert(col != NULL);
5544 
5545  if( SCIPsetIsZero(set, incval) )
5546  return SCIP_OKAY;
5547 
5548  /* search the position of the column in the row's col v