lp.c

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*                  This file is part of the program and library             */
/*         SCIP --- Solving Constraint Integer Programs                      */
/*                                                                           */
/*  Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB)                      */
/*                                                                           */
/*  Licensed under the Apache License, Version 2.0 (the "License");          */
/*  you may not use this file except in compliance with the License.         */
/*  You may obtain a copy of the License at                                  */
/*                                                                           */
/*      http://www.apache.org/licenses/LICENSE-2.0                           */
/*                                                                           */
/*  Unless required by applicable law or agreed to in writing, software      */
/*  distributed under the License is distributed on an "AS IS" BASIS,        */
/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
/*  See the License for the specific language governing permissions and      */
/*  limitations under the License.                                           */
/*                                                                           */
/*  You should have received a copy of the Apache-2.0 license                */
/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 
/**@file   lp.c
 * @ingroup OTHER_CFILES
 * @brief  LP management methods and data structures
 * @author Tobias Achterberg
 * @author Timo Berthold
 * @author Marc Pfetsch
 * @author Kati Wolter
 * @author Gerald Gamrath
 *
 *  In LP management, we have to differ between the current LP and the SCIP_LP
 *  stored in the LP solver. All LP methods affect the current LP only.
 *  Before solving the current LP with the LP solver or setting an LP state,
 *  the LP solvers data has to be updated to the current LP with a call to
 *  lpFlush().
 */
 
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
 
 
#include "lpi/lpi.h"
#include "scip/clock.h"
#include "scip/cons.h"
#include "scip/event.h"
#include "scip/intervalarith.h"
#include "scip/lp.h"
#include "scip/misc.h"
#include "scip/prob.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_var.h"
#include "scip/set.h"
#include "scip/sol.h"
#include "scip/solve.h"
#include "scip/stat.h"
#include "scip/struct_event.h"
#include "scip/struct_lp.h"
#include "scip/struct_prob.h"
#include "scip/struct_set.h"
#include "scip/struct_stat.h"
#include "scip/struct_var.h"
#include "scip/var.h"
#include <string.h>
 
 
/* activate this to use the row activities as given by the LPI instead of recalculating
 * using the LP solver activity is potentially faster, but may not be consistent with the SCIP_ROW calculations
 * see also #2594 for more details on possible trouble
 */
/* #define SCIP_USE_LPSOLVER_ACTIVITY */
 
/*
 * debug messages
 */
 
#ifdef SCIP_DEBUG
/** method is to print in row in case SCIP_DEBUG is defined */
static
void debugRowPrint(
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_ROW*             row                 /**< LP row */
   )
{
   int i;
 
   assert(row != NULL);
 
   /* print row name */
   if( row->name != NULL && row->name[0] != '\0' )
   {
      SCIPsetDebugMsgPrint(set, "%s: ", row->name);
   }
 
   /* print left hand side */
   SCIPsetDebugMsgPrint(set, "%.15g <= ", row->lhs);
 
   /* print coefficients */
   if( row->len == 0 )
   {
      SCIPsetDebugMsgPrint(set, "0 ");
   }
   for( i = 0; i < row->len; ++i )
   {
      assert(row->cols[i] != NULL);
      assert(row->cols[i]->var != NULL);
      assert(SCIPvarGetName(row->cols[i]->var) != NULL);
      assert(SCIPvarGetStatus(row->cols[i]->var) == SCIP_VARSTATUS_COLUMN);
      SCIPsetDebugMsgPrint(set, "%+.15g<%s> ", row->vals[i], SCIPvarGetName(row->cols[i]->var));
   }
 
   /* print constant */
   if( REALABS(row->constant) > SCIP_DEFAULT_EPSILON )
   {
      SCIPsetDebugMsgPrint(set, "%+.15g ", row->constant);
   }
 
   /* print right hand side */
   SCIPsetDebugMsgPrint(set, "<= %.15g\n", row->rhs);
}
#else
#define debugRowPrint(x,y) /**/
#endif
 
#ifdef SCIP_DEBUG
/** method to output column if SCIP_DEBUG is define */
static
void debugColPrint(
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_COL*             col                 /**< LP column */
   )
{
   int r;
 
   assert(col != NULL);
   assert(col->var != NULL);
 
   /* print bounds */
   SCIPsetDebugMsgPrint(set, "(obj: %.15g) [%.15g,%.15g], ", col->obj, col->lb, col->ub);
 
   /* print coefficients */
   if( col->len == 0 )
   {
      SCIPsetDebugMsgPrint(set, "<empty>");
   }
   for( r = 0; r < col->len; ++r )
   {
      assert(col->rows[r] != NULL);
      assert(col->rows[r]->name != NULL);
      SCIPsetDebugMsgPrint(set, "%+.15g<%s> ", col->vals[r], col->rows[r]->name);
   }
   SCIPsetDebugMsgPrint(set, "\n");
}
#else
#define debugColPrint(x,y) /**/
#endif
 
/*
 * memory growing methods for dynamically allocated arrays
 */
 
/** ensures, that chgcols array can store at least num entries */
static
SCIP_RETCODE ensureChgcolsSize(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   int                   num                 /**< minimum number of entries to store */
   )
{
   assert(lp->nchgcols <= lp->chgcolssize);
 
   if( num > lp->chgcolssize )
   {
      int newsize;
 
      newsize = SCIPsetCalcMemGrowSize(set, num);
      SCIP_ALLOC( BMSreallocMemoryArray(&lp->chgcols, newsize) );
      lp->chgcolssize = newsize;
   }
   assert(num <= lp->chgcolssize);
 
   return SCIP_OKAY;
}
 
/** ensures, that chgrows array can store at least num entries */
static
SCIP_RETCODE ensureChgrowsSize(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   int                   num                 /**< minimum number of entries to store */
   )
{
   assert(lp->nchgrows <= lp->chgrowssize);
 
   if( num > lp->chgrowssize )
   {
      int newsize;
 
      newsize = SCIPsetCalcMemGrowSize(set, num);
      SCIP_ALLOC( BMSreallocMemoryArray(&lp->chgrows, newsize) );
      lp->chgrowssize = newsize;
   }
   assert(num <= lp->chgrowssize);
 
   return SCIP_OKAY;
}
 
/** ensures, that lpicols array can store at least num entries */
static
SCIP_RETCODE ensureLpicolsSize(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   int                   num                 /**< minimum number of entries to store */
   )
{
   assert(lp->nlpicols <= lp->lpicolssize);
 
   if( num > lp->lpicolssize )
   {
      int newsize;
 
      newsize = SCIPsetCalcMemGrowSize(set, num);
      SCIP_ALLOC( BMSreallocMemoryArray(&lp->lpicols, newsize) );
      lp->lpicolssize = newsize;
   }
   assert(num <= lp->lpicolssize);
 
   return SCIP_OKAY;
}
 
/** ensures, that lpirows array can store at least num entries */
static
SCIP_RETCODE ensureLpirowsSize(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   int                   num                 /**< minimum number of entries to store */
   )
{
   assert(lp->nlpirows <= lp->lpirowssize);
 
   if( num > lp->lpirowssize )
   {
      int newsize;
 
      newsize = SCIPsetCalcMemGrowSize(set, num);
      SCIP_ALLOC( BMSreallocMemoryArray(&lp->lpirows, newsize) );
      lp->lpirowssize = newsize;
   }
   assert(num <= lp->lpirowssize);
 
   return SCIP_OKAY;
}
 
/** ensures, that cols array can store at least num entries */
static
SCIP_RETCODE ensureColsSize(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   int                   num                 /**< minimum number of entries to store */
   )
{
   assert(lp->ncols <= lp->colssize);
 
   if( num > lp->colssize )
   {
      int newsize;
 
      newsize = SCIPsetCalcMemGrowSize(set, num);
      SCIP_ALLOC( BMSreallocMemoryArray(&lp->cols, newsize) );
      lp->colssize = newsize;
   }
   assert(num <= lp->colssize);
 
   return SCIP_OKAY;
}
 
/** ensures, that soldirection array can store at least num entries */
static
SCIP_RETCODE ensureSoldirectionSize(
   SCIP_LP*              lp,                 /**< current LP data */
   int                   num                 /**< minimum number of entries to store */
   )
{
   if( num > lp->soldirectionsize )
   {
      BMSfreeMemoryArrayNull(&lp->soldirection);
      SCIP_ALLOC( BMSallocMemoryArray(&lp->soldirection, num) );
 
      lp->soldirectionsize = num;
   }
 
   assert(num <= lp->soldirectionsize);
 
   return SCIP_OKAY;
}
 
/** ensures, that lazy cols array can store at least num entries */
static
SCIP_RETCODE ensureLazycolsSize(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   int                   num                 /**< minimum number of entries to store */
   )
{
   assert(lp->nlazycols <= lp->lazycolssize);
 
   if( num > lp->lazycolssize )
   {
      int newsize;
 
      newsize = SCIPsetCalcMemGrowSize(set, num);
      SCIP_ALLOC( BMSreallocMemoryArray(&lp->lazycols, newsize) );
      lp->lazycolssize = newsize;
   }
   assert(num <= lp->lazycolssize);
 
   return SCIP_OKAY;
}
 
/** ensures, that rows array can store at least num entries */
static
SCIP_RETCODE ensureRowsSize(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   int                   num                 /**< minimum number of entries to store */
   )
{
   assert(lp->nrows <= lp->rowssize);
 
   if( num > lp->rowssize )
   {
      int newsize;
 
      newsize = SCIPsetCalcMemGrowSize(set, num);
      SCIP_ALLOC( BMSreallocMemoryArray(&lp->rows, newsize) );
      lp->rowssize = newsize;
   }
   assert(num <= lp->rowssize);
 
   return SCIP_OKAY;
}
 
/** ensures, that row array of column can store at least num entries */
static
SCIP_RETCODE colEnsureSize(
   SCIP_COL*             col,                /**< LP column */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   int                   num                 /**< minimum number of entries to store */
   )
{
   assert(col != NULL);
   assert(col->len <= col->size);
 
   if( num > col->size )
   {
      int newsize;
 
      newsize = SCIPsetCalcMemGrowSize(set, num);
      SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &col->rows, col->size, newsize) );
      SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &col->vals, col->size, newsize) );
      SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &col->linkpos, col->size, newsize) );
      col->size = newsize;
   }
   assert(num <= col->size);
 
   return SCIP_OKAY;
}
 
/** save current LP values dependent on the solution */
static
SCIP_RETCODE lpStoreSolVals(
   SCIP_LP*              lp,                 /**< LP data */
   SCIP_STAT*            stat,               /**< problem statistics */
   BMS_BLKMEM*           blkmem              /**< block memory */
   )
{
   SCIP_LPSOLVALS* storedsolvals;
 
   assert(lp != NULL);
   assert(stat != NULL);
   assert(blkmem != NULL);
 
   /* allocate memory for storage */
   if( lp->storedsolvals == NULL )
   {
      SCIP_ALLOC( BMSallocMemory(&lp->storedsolvals) );
   }
   storedsolvals = lp->storedsolvals;
 
   /* store values */
   storedsolvals->lpsolstat = lp->lpsolstat;
   storedsolvals->lpobjval = lp->lpobjval;
   storedsolvals->primalfeasible = lp->primalfeasible;
   storedsolvals->primalchecked = lp->primalchecked;
   storedsolvals->dualfeasible = lp->dualfeasible;
   storedsolvals->dualchecked = lp->dualchecked;
   storedsolvals->solisbasic = lp->solisbasic;
   storedsolvals->lpissolved = lp->solved;
 
   return SCIP_OKAY;
}
 
/** restore LP solution values in column */
static
SCIP_RETCODE lpRestoreSolVals(
   SCIP_LP*              lp,                 /**< LP data */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_Longint          validlp             /**< number of lp for which restored values are valid */
   )
{
   SCIP_LPSOLVALS* storedsolvals;
 
   assert(lp != NULL);
   assert(blkmem != NULL);
 
   /* if stored values are available, restore them */
   storedsolvals = lp->storedsolvals;
   if( storedsolvals != NULL )
   {
      lp->solved = storedsolvals->lpissolved;
      lp->validsollp = validlp;
 
      lp->lpsolstat = storedsolvals->lpsolstat;
      lp->lpobjval = storedsolvals->lpobjval;
      lp->primalfeasible = storedsolvals->primalfeasible;
      lp->primalchecked = storedsolvals->primalchecked;
      lp->dualfeasible = storedsolvals->dualfeasible;
      lp->dualchecked = storedsolvals->dualchecked;
      lp->solisbasic = storedsolvals->solisbasic;
 
      /* solution values are stored only for LPs solved to optimality or unboundedness */
      assert(lp->lpsolstat == SCIP_LPSOLSTAT_OPTIMAL ||
         lp->lpsolstat == SCIP_LPSOLSTAT_UNBOUNDEDRAY ||
         lp->storedsolvals->lpsolstat == SCIP_LPSOLSTAT_OBJLIMIT ||
         lp->storedsolvals->lpsolstat == SCIP_LPSOLSTAT_ITERLIMIT ||
         lp->storedsolvals->lpsolstat == SCIP_LPSOLSTAT_TIMELIMIT ||
         lp->storedsolvals->lpsolstat == SCIP_LPSOLSTAT_INFEASIBLE ||
         lp->validsollp == -1);
   }
   /* no values available, mark LP as unsolved */
   else
   {
      lp->solved = FALSE;
      lp->validsollp = -1;
 
      lp->lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
      lp->lpobjval = SCIP_INVALID;
      lp->primalfeasible = FALSE;
      lp->primalchecked = FALSE;
      lp->dualfeasible = FALSE;
      lp->dualchecked = FALSE;
      lp->solisbasic = FALSE;
      lp->validfarkaslp = -1;
   }
 
   lp->validdegeneracylp = -1;
 
   /* intentionally keep storage space allocated */
 
   return SCIP_OKAY;
}
 
/** save current LP solution values stored in each column */
static
SCIP_RETCODE colStoreSolVals(
   SCIP_COL*             col,                /**< LP column */
   BMS_BLKMEM*           blkmem              /**< block memory */
   )
{
   SCIP_COLSOLVALS* storedsolvals;
 
   assert(col != NULL);
   assert(blkmem != NULL);
 
   /* allocate memory for storage */
   if( col->storedsolvals == NULL )
   {
      SCIP_ALLOC( BMSallocBlockMemory(blkmem, &col->storedsolvals) );
   }
   storedsolvals = col->storedsolvals;
 
   /* store values */
   storedsolvals->primsol = col->primsol;
   storedsolvals->redcost = col->redcost;
   storedsolvals->basisstatus = col->basisstatus; /*lint !e641 !e732*/
 
   return SCIP_OKAY;
}
 
/** restore LP solution values in column */
static
SCIP_RETCODE colRestoreSolVals(
   SCIP_COL*             col,                /**< LP column */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_Longint          validlp,            /**< number of lp for which restored values are valid */
   SCIP_Bool             freebuffer          /**< should buffer for LP solution values be freed? */
   )
{
   SCIP_COLSOLVALS* storedsolvals;
 
   assert(col != NULL);
   assert(blkmem != NULL);
 
   /* if stored values are available, restore them */
   storedsolvals = col->storedsolvals;
   if( storedsolvals != NULL )
   {
      col->primsol = storedsolvals->primsol;
      col->redcost = storedsolvals->redcost;
      col->validredcostlp = validlp;
      col->basisstatus = storedsolvals->basisstatus; /*lint !e641 !e732*/
 
      /* we do not save the farkas coefficient, since it can be recomputed; thus, we invalidate it here */
      col->validfarkaslp = -1;
   }
   /* if the column was created after performing the storage (possibly during probing), we treat it as implicitly zero;
    * we make sure to invalidate the reduced cost and farkas coefficient, which are not available
    */
   else
   {
      col->primsol = 0.0;
      col->validredcostlp = -1;
      col->validfarkaslp = -1;
      col->basisstatus = SCIP_BASESTAT_ZERO; /*lint !e641*/
   }
 
   /* free memory */
   if( freebuffer )
   {
      BMSfreeBlockMemoryNull(blkmem, &col->storedsolvals);
      assert(col->storedsolvals == NULL);
   }
 
   return SCIP_OKAY;
}
 
/** save current LP solution values stored in each column */
static
SCIP_RETCODE rowStoreSolVals(
   SCIP_ROW*             row,                /**< LP row */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_Bool             infeasible          /**< is the solution infeasible? */
   )
{
   SCIP_ROWSOLVALS* storedsolvals;
 
   assert(row != NULL);
   assert(blkmem != NULL);
 
   /* allocate memory for storage */
   if( row->storedsolvals == NULL )
   {
      SCIP_ALLOC( BMSallocBlockMemory(blkmem, &row->storedsolvals) );
   }
   storedsolvals = row->storedsolvals;
 
   /* store values */
   if ( infeasible )
   {
      storedsolvals->dualsol = row->dualfarkas;
      storedsolvals->activity = SCIP_INVALID;
      storedsolvals->basisstatus = SCIP_BASESTAT_BASIC;  /*lint !e641*/
   }
   else
   {
      storedsolvals->dualsol = row->dualsol;
      storedsolvals->activity = row->activity;
      storedsolvals->basisstatus = row->basisstatus; /*lint !e641 !e732*/
   }
 
   return SCIP_OKAY;
}
 
/** restore LP solution values in row */
static
SCIP_RETCODE rowRestoreSolVals(
   SCIP_ROW*             row,                /**< LP column */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_Longint          validlp,            /**< number of lp for which restored values are valid */
   SCIP_Bool             freebuffer,         /**< should buffer for LP solution values be freed? */
   SCIP_Bool             infeasible          /**< is the solution infeasible? */
   )
{
   SCIP_ROWSOLVALS* storedsolvals;
 
   assert(row != NULL);
   assert(blkmem != NULL);
 
   /* if stored values are available, restore them */
   storedsolvals = row->storedsolvals;
   if( storedsolvals != NULL )
   {
      if ( infeasible )
         row->dualfarkas = storedsolvals->dualsol;
      else
         row->dualsol = storedsolvals->dualsol;
      row->activity = storedsolvals->activity;
      row->validactivitylp = validlp;
      row->basisstatus = storedsolvals->basisstatus; /*lint !e641 !e732*/
   }
   /* if the row was created after performing the storage (possibly during probing), we treat it as basic;
    * we make sure to invalidate the reduced cost and farkas coefficient, which are not available
    */
   else
   {
      row->dualsol = 0.0;
      row->dualfarkas = 0.0;
      row->activity = SCIP_INVALID;
      row->validactivitylp = -1;
      row->basisstatus = SCIP_BASESTAT_BASIC; /*lint !e641*/
   }
 
   /* free memory */
   if( freebuffer )
   {
      BMSfreeBlockMemoryNull(blkmem, &row->storedsolvals);
      assert(row->storedsolvals == NULL);
   }
 
   return SCIP_OKAY;
}
 
/** ensures, that column array of row can store at least num entries */
SCIP_RETCODE SCIProwEnsureSize(
   SCIP_ROW*             row,                /**< LP row */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   int                   num                 /**< minimum number of entries to store */
   )
{
   assert(row != NULL);
   assert(row->len <= row->size);
 
   if( num > row->size )
   {
      int newsize;
 
      newsize = SCIPsetCalcMemGrowSize(set, num);
      SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &row->cols, row->size, newsize) );
      SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &row->cols_index, row->size, newsize) );
      SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &row->vals, row->size, newsize) );
      SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &row->linkpos, row->size, newsize) );
      row->size = newsize;
   }
   assert(num <= row->size);
 
   return SCIP_OKAY;
}
 
 
#ifdef SCIP_MORE_DEBUG /* enable this to check the sortings within rows (for debugging, very slow!) */
static SCIP_Bool msgdisp_checkrow = FALSE;
 
static
void checkRow(
   SCIP_ROW*             row
   )
{
   int i;
 
   if( !msgdisp_checkrow )
   {
      printf("LP ROW CHECKING ACTIVATED! THIS IS VERY SLOW!\n");
      msgdisp_checkrow = TRUE;
   }
 
   /* validate sorting of LP part of row */
   if( row->lpcolssorted && row->nlpcols > 0)
   {
      assert(row->cols_index[0] == row->cols[0]->index);
      for( i = 1; i < row->nlpcols; ++i )
      {
         assert(row->cols_index[i] == row->cols[i]->index);
         assert(row->cols_index[i] >= row->cols_index[i-1]);
      }
   }
 
   /* validate sorting of non-LP part of row */
   if( row->nonlpcolssorted && row->len > row->nlpcols )
   {
      assert(row->cols_index[row->nlpcols] == row->cols[row->nlpcols]->index);
      for( i = row->nlpcols + 1; i < row->len; ++i )
      {
         assert(row->cols_index[i] == row->cols[i]->index);
         assert(row->cols_index[i] >= row->cols_index[i-1]);
      }
   }
}
#else
#define checkRow(row) /**/
#endif
 
#ifdef SCIP_MORE_DEBUG /* enable this to check norms of rows (for debugging, very slow!) */
static
void checkRowSqrnorm(
   SCIP_ROW*             row
   )
{
   SCIP_COL** cols;
   SCIP_Real sqrnorm;
   int c;
 
   cols = row->cols;
   assert(cols != NULL || row->len == 0);
 
   sqrnorm = 0.0;
 
   for( c = row->len - 1; c >= 0; --c )
   {
      if( cols[c]->lppos >= 0 )
         sqrnorm += SQR(row->vals[c]);
   }
 
   assert(ABS(sqrnorm - row->sqrnorm) < 1e-06 * MAX(1.0,sqrnorm));
}
 
static
void checkRowSumnorm(
   SCIP_ROW*             row
   )
{
   SCIP_COL** cols;
   SCIP_Real sumnorm;
   int c;
 
   cols = row->cols;
   assert(cols != NULL || row->len == 0);
 
   sumnorm = 0.0;
 
   for( c = row->len - 1; c >= 0; --c )
   {
      if( cols[c]->lppos >= 0 )
         sumnorm += REALABS(row->vals[c]);
   }
 
   assert(ABS(sumnorm - row->sumnorm) < 1e-06 * MAX(1.0,sumnorm));
}
 
static
void checkRowObjprod(
   SCIP_ROW*             row
   )
{
   SCIP_COL** cols;
   SCIP_Real objprod;
   int c;
 
   cols = row->cols;
   assert(cols != NULL || row->len == 0);
 
   objprod = 0.0;
 
   for( c = row->len - 1; c >= 0; --c )
   {
      if( cols[c]->lppos >= 0 )
         objprod += row->vals[c] * cols[c]->unchangedobj;
   }
 
   assert(ABS(objprod - row->objprod) < 1e-06 * MAX(1.0,objprod));
}
#else
#define checkRowSqrnorm(row) /**/
#define checkRowSumnorm(row) /**/
#define checkRowObjprod(row) /**/
#endif
 
/*
 * Local methods for pseudo and loose objective values
 */
 
/* recompute the loose objective value from scratch, if it was marked to be unreliable before */
static
void recomputeLooseObjectiveValue(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_PROB*            prob                /**< problem data */
   )
{
   SCIP_VAR** vars;
   SCIP_Real obj;
   int nvars;
   int v;
 
   assert(lp != NULL);
   assert(set != NULL);
   assert(prob != NULL);
   assert(!lp->looseobjvalid);
 
   vars = prob->vars;
   nvars = prob->nvars;
   lp->looseobjval = 0.0;
 
   /* iterate over all variables in the problem */
   for( v = 0; v < nvars; ++v )
   {
      if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_LOOSE )
      {
         obj = SCIPvarGetObj(vars[v]);
 
         /* we are only interested in variables with a finite impact, because the infinity counters should be correct */
         if( SCIPsetIsPositive(set, obj) && !SCIPsetIsInfinity(set, -SCIPvarGetLbLocal(vars[v])) )
            lp->looseobjval += obj * SCIPvarGetLbLocal(vars[v]);
         else if( SCIPsetIsNegative(set, obj) && !SCIPsetIsInfinity(set, SCIPvarGetUbLocal(vars[v])) )
            lp->looseobjval += obj * SCIPvarGetUbLocal(vars[v]);
      }
   }
 
   /* the recomputed value is reliable */
   lp->rellooseobjval = lp->looseobjval;
   lp->looseobjvalid = TRUE;
}
 
/* recompute the pseudo solution value from scratch, if it was marked to be unreliable before */
static
void recomputePseudoObjectiveValue(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_PROB*            prob                /**< problem data */
   )
{
   SCIP_VAR** vars;
   int nvars;
   int v;
 
   assert(lp != NULL);
   assert(set != NULL);
   assert(prob != NULL);
   assert(!lp->pseudoobjvalid);
 
   vars = prob->vars;
   nvars = prob->nvars;
   lp->pseudoobjval = 0.0;
 
   /* iterate over all variables in the problem */
   for( v = 0; v < nvars; ++v )
   {
      /* we are only interested in variables with a finite impact, because the infinity counters should be correct */
      if( SCIPsetIsPositive(set, SCIPvarGetObj(vars[v])) &&
         !SCIPsetIsInfinity(set, -SCIPvarGetLbLocal(vars[v])) )
      {
         lp->pseudoobjval += SCIPvarGetObj(vars[v]) * SCIPvarGetLbLocal(vars[v]);
      }
      else if( SCIPsetIsNegative(set, SCIPvarGetObj(vars[v])) &&
         !SCIPsetIsInfinity(set, SCIPvarGetUbLocal(vars[v])) )
      {
         lp->pseudoobjval += SCIPvarGetObj(vars[v]) * SCIPvarGetUbLocal(vars[v]);
      }
   }
 
   /* the recomputed value is reliable */
   lp->relpseudoobjval = lp->pseudoobjval;
   lp->pseudoobjvalid = TRUE;
}
 
/* recompute the global pseudo solution value from scratch, if it was marked to be unreliable before */
static
void recomputeGlbPseudoObjectiveValue(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_PROB*            prob                /**< problem data */
   )
{
   SCIP_VAR** vars;
   int nvars;
   int v;
 
   assert(lp != NULL);
   assert(set != NULL);
   assert(prob != NULL);
   assert(!lp->glbpseudoobjvalid);
 
   vars = prob->vars;
   nvars = prob->nvars;
   lp->glbpseudoobjval = 0.0;
 
   /* iterate over all variables in the problem */
   for( v = 0; v < nvars; ++v )
   {
      /* we are only interested in variables with a finite impact, because the infinity counters should be correct */
      if( SCIPsetIsPositive(set, SCIPvarGetObj(vars[v])) &&
         !SCIPsetIsInfinity(set, -SCIPvarGetLbGlobal(vars[v])) )
      {
         lp->glbpseudoobjval += SCIPvarGetObj(vars[v]) * SCIPvarGetLbGlobal(vars[v]);
      }
      else if( SCIPsetIsNegative(set, SCIPvarGetObj(vars[v])) &&
         !SCIPsetIsInfinity(set, SCIPvarGetUbGlobal(vars[v])) )
      {
         lp->glbpseudoobjval += SCIPvarGetObj(vars[v]) * SCIPvarGetUbGlobal(vars[v]);
      }
   }
 
   /* the recomputed value is reliable */
   lp->relglbpseudoobjval = lp->glbpseudoobjval;
   lp->glbpseudoobjvalid = TRUE;
}
 
/** gets finite part of objective value of current LP that results from LOOSE variables only */
static
SCIP_Real getFiniteLooseObjval(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_PROB*            prob                /**< problem data */
   )
{
   assert(lp != NULL);
   assert(set != NULL);
   assert(prob != NULL);
   assert((lp->nloosevars > 0) || (lp->looseobjvalinf == 0 && lp->looseobjval == 0.0));
   assert(lp->flushed);
   assert(lp->looseobjvalinf == 0);
 
   /* recalculate the loose objective value, if needed */
   if( !lp->looseobjvalid )
      recomputeLooseObjectiveValue(lp, set, prob);
 
   return lp->looseobjval;
}
 
/** gets finite part of pseudo objective value of current LP */
static
SCIP_Real getFinitePseudoObjval(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_PROB*            prob                /**< problem data */
   )
{
   assert(lp != NULL);
   assert(set != NULL);
   assert(prob != NULL);
 
   /* recalculate the pseudo objective value, if needed */
   if( !lp->pseudoobjvalid )
      recomputePseudoObjectiveValue(lp, set, prob);
 
   return lp->pseudoobjval;
}
 
/*
 * Sorting and searching rows and columns
 */
 
 
/** comparison method for sorting rows by non-decreasing index */
SCIP_DECL_SORTPTRCOMP(SCIProwComp)
{
   assert(elem1 != NULL);
   assert(elem2 != NULL);
 
   if( ((SCIP_ROW*)elem1)->index < ((SCIP_ROW*)elem2)->index )
      return -1;
   else if( ((SCIP_ROW*)elem1)->index > ((SCIP_ROW*)elem2)->index )
      return +1;
   else
   {
      assert(SCIProwGetIndex((SCIP_ROW*)(elem1)) == SCIProwGetIndex(((SCIP_ROW*)elem2)));
      return 0;
   }
}
 
 
/** sorts column entries of linked rows currently in the LP such that lower row indices precede higher ones */
static
void colSortLP(
   SCIP_COL*             col                 /**< column to be sorted */
   )
{
   int i;
 
   assert(col != NULL);
 
   /* check, if column is already sorted in the LP part */
   if( col->lprowssorted )
      return;
 
   /* sort coefficients */
   SCIPsortPtrRealInt((void**)col->rows, col->vals, col->linkpos, SCIProwComp, col->nlprows );
 
   /* update links */
   for( i = 0; i < col->nlprows; ++i )
   {
      if( col->linkpos[i] >= 0 )
      {
         assert(col->rows[i]->cols[col->linkpos[i]] == col);
         assert(col->rows[i]->linkpos[col->linkpos[i]] >= 0);
         col->rows[i]->linkpos[col->linkpos[i]] = i;
      }
   }
 
   col->lprowssorted = TRUE;
}
 
/** sorts column entries of unlinked rows or rows currently not in the LP such that lower row indices precede higher
 *  ones
 */
static
void colSortNonLP(
   SCIP_COL*             col                 /**< column to be sorted */
   )
{
   int i;
 
   assert(col != NULL);
 
   /* check, if column is already sorted in the non-LP part */
   if( col->nonlprowssorted )
      return;
 
   /* sort coefficients */
   SCIPsortPtrRealInt((void**)(&(col->rows[col->nlprows])), &(col->vals[col->nlprows]), &(col->linkpos[col->nlprows]), SCIProwComp, col->len - col->nlprows);
 
   /* update links */
   for( i = col->nlprows; i < col->len; ++i )
   {
      if( col->linkpos[i] >= 0 )
      {
         assert(col->rows[i]->cols[col->linkpos[i]] == col);
         assert(col->rows[i]->linkpos[col->linkpos[i]] >= 0);
         col->rows[i]->linkpos[col->linkpos[i]] = i;
      }
   }
 
   col->nonlprowssorted = TRUE;
}
 
/** sorts row entries of linked columns currently in the LP such that lower column indices precede higher ones */
static
void rowSortLP(
   SCIP_ROW*             row                 /**< row to be sorted */
   )
{
   int i;
 
   assert(row != NULL);
 
   /* check, if row is already sorted in the LP part, or if the sorting should be delayed */
   if( row->lpcolssorted || row->delaysort )
      return;
 
   /* sort coefficients */
   SCIPsortIntPtrIntReal(row->cols_index, (void**)row->cols, row->linkpos, row->vals, row->nlpcols);
 
   /* update links */
   for( i = 0; i < row->nlpcols; ++i )
   {
      if( row->linkpos[i] >= 0 )
      {
         assert(row->cols[i]->rows[row->linkpos[i]] == row);
         assert(row->cols[i]->linkpos[row->linkpos[i]] >= 0);
         row->cols[i]->linkpos[row->linkpos[i]] = i;
      }
   }
 
   row->lpcolssorted = TRUE;
}
 
/** sorts row entries of unlinked columns or columns currently not in the LP such that lower column indices precede
 *  higher ones
 */
static
void rowSortNonLP(
   SCIP_ROW*             row                 /**< row to be sorted */
   )
{
   int i;
 
   assert(row != NULL);
 
   checkRow(row);
 
   /* check, if row is already sorted in the non-LP part, or if the sorting should be delayed */
   if( row->nonlpcolssorted || row->delaysort )
      return;
 
   /* sort coefficients */
   SCIPsortIntPtrIntReal(&(row->cols_index[row->nlpcols]), (void**)(&(row->cols[row->nlpcols])), &(row->linkpos[row->nlpcols]), &(row->vals[row->nlpcols]), row->len - row->nlpcols);
 
   /* update links */
   for( i = row->nlpcols; i < row->len; ++i )
   {
      if( row->linkpos[i] >= 0 )
      {
         assert(row->cols[i]->rows[row->linkpos[i]] == row);
         assert(row->cols[i]->linkpos[row->linkpos[i]] >= 0);
         row->cols[i]->linkpos[row->linkpos[i]] = i;
      }
   }
 
   checkRow(row);
 
   row->nonlpcolssorted = TRUE;
}
 
/** searches coefficient in part of the column, returns position in col vector or -1 if not found */
static
int colSearchCoefPart(
   SCIP_COL*             col,                /**< column to be searched in */
   const SCIP_ROW*       row,                /**< coefficient to be searched for */
   int                   minpos,             /**< first position of search range */
   int                   maxpos              /**< last position of search range */
   )
{
   int pos;
   int idx;
   int searchidx;
 
   assert(col != NULL);
   assert(row != NULL);
 
   /* binary search */
   searchidx = row->index;
   while(minpos <= maxpos)
   {
      pos = (minpos + maxpos)/2;
      assert(0 <= pos && pos < col->len);
      assert(col->rows[pos] != NULL);
      assert((pos < col->nlprows) == (col->rows[pos]->lppos >= 0 && col->linkpos[pos] >= 0));
      idx = col->rows[pos]->index;
      if( searchidx == idx )
         return pos;
      else if( searchidx < idx )
         maxpos = pos-1;
      else
         minpos = pos+1;
   }
 
   return -1;
}
 
/** searches coefficient in column, returns position in col vector or -1 if not found */
static
int colSearchCoef(
   SCIP_COL*             col,                /**< column to be searched in */
   const SCIP_ROW*       row                 /**< coefficient to be searched for */
   )
{
   int pos;
 
   assert(col != NULL);
   assert(row != NULL);
 
   pos = -1;
 
   /* search in the linked LP rows */
   if( row->lppos >= 0 )
   {
      /* column has to be sorted, such that binary search works */
      colSortLP(col);
      assert(col->lprowssorted);
 
      pos = colSearchCoefPart(col, row, 0, col->nlprows-1);
      if( pos >= 0 )
         return pos;
   }
 
   /* search in the non-LP/unlinked rows */
   if( row->lppos == -1 || col->nunlinked > 0 )
   {
      /* column has to be sorted, such that binary search works */
      colSortNonLP(col);
      assert(col->nonlprowssorted);
 
      pos = colSearchCoefPart(col, row, col->nlprows, col->len-1);
   }
 
   return pos;
}
 
/** searches coefficient in part of the row, returns position in col vector or -1 if not found */
static
int rowSearchCoefPart(
   SCIP_ROW*             row,                /**< row to be searched in */
   const SCIP_COL*       col,                /**< coefficient to be searched for */
   int                   minpos,             /**< first position of search range */
   int                   maxpos              /**< last position of search range */
   )
{
   int pos;
   int idx;
   int searchidx;
 
   assert(row != NULL);
   assert(col != NULL);
 
   /* binary search */
   searchidx = col->index;
   while(minpos <= maxpos)
   {
      pos = (minpos + maxpos)/2;
      assert(0 <= pos && pos < row->len);
      assert(row->cols[pos] != NULL);
      assert((pos < row->nlpcols) == (row->cols[pos]->lppos >= 0 && row->linkpos[pos] >= 0));
      assert(row->cols_index[pos] == row->cols[pos]->index);
      idx = row->cols_index[pos];
      if( searchidx == idx )
         return pos;
      else if( searchidx < idx )
         maxpos = pos-1;
      else
         minpos = pos+1;
   }
 
   return -1;
}
 
/** searches coefficient in row, returns position in row vector or -1 if not found;
 *  if the sorting of the row is delayed, returns -1
 */
static
int rowSearchCoef(
   SCIP_ROW*             row,                /**< row to be searched in */
   const SCIP_COL*       col                 /**< coefficient to be searched for */
   )
{
   int pos;
 
   assert(row != NULL);
   assert(col != NULL);
 
   if( row->delaysort )
      return -1;
 
   pos = -1;
 
   /* search in the linked LP columns */
   if( col->lppos >= 0 )
   {
      /* row has to be sorted, such that binary search works */
      rowSortLP(row);
      assert(row->lpcolssorted);
 
      pos = rowSearchCoefPart(row, col, 0, row->nlpcols-1);
   }
 
   /* search in the non-LP/unlinked columns */
   if( pos == -1 && (col->lppos == -1 || row->nunlinked > 0) )
   {
      /* row has to be sorted, such that binary search works */
      rowSortNonLP(row);
      assert(row->nonlpcolssorted);
 
      pos = rowSearchCoefPart(row, col, row->nlpcols, row->len-1);
   }
 
#ifndef NDEBUG
   /* validate result */
   assert(-1 <= pos && pos < row->len);
   if( pos >= 0 )
      assert(row->cols[pos] == col);
   else
   {
      int i;
      for( i = 0; i < row->len; ++i )
         assert(row->cols[i] != col);
   }
#endif
 
   return pos;
}
 
/** moves a coefficient in a column to a different place, and updates all corresponding data structures */
static
void colMoveCoef(
   SCIP_COL*             col,                /**< LP column */
   int                   oldpos,             /**< old position of coefficient */
   int                   newpos              /**< new position of coefficient */
   )
{
   assert(col != NULL);
   assert(0 <= oldpos && oldpos < col->len);
   assert(0 <= newpos && newpos < col->len);
   assert(col->rows[oldpos] != NULL);
 
   if( oldpos == newpos )
      return;
 
   col->rows[newpos] = col->rows[oldpos];
   col->vals[newpos] = col->vals[oldpos];
   col->linkpos[newpos] = col->linkpos[oldpos];
 
   /* update link position in row */
   if( col->linkpos[newpos] >= 0 )
   {
      assert(col->rows[newpos]->cols[col->linkpos[newpos]] == col);
      assert(col->rows[newpos]->linkpos[col->linkpos[newpos]] == oldpos);
 
      col->rows[newpos]->linkpos[col->linkpos[newpos]] = newpos;
   }
 
   /* update sorted flags */
   if( col->rows[newpos]->lppos >= 0 && col->linkpos[newpos] >= 0 )
      col->lprowssorted = FALSE;
   else
      col->nonlprowssorted = FALSE;
}
 
/** swaps two coefficients in a column, and updates all corresponding data structures */
static
void colSwapCoefs(
   SCIP_COL*             col,                /**< LP column */
   int                   pos1,               /**< position of first coefficient */
   int                   pos2                /**< position of second coefficient */
   )
{
   SCIP_ROW* tmprow;
   SCIP_Real tmpval;
   int tmplinkpos;
 
   assert(col != NULL);
   assert(0 <= pos1 && pos1 < col->len);
   assert(0 <= pos2 && pos2 < col->len);
   assert(col->rows[pos1] != NULL);
 
   if( pos1 == pos2 )
      return;
 
   /* swap coefficients */
   tmprow = col->rows[pos2];
   tmpval = col->vals[pos2];
   tmplinkpos = col->linkpos[pos2];
 
   col->rows[pos2] = col->rows[pos1];
   col->vals[pos2] = col->vals[pos1];
   col->linkpos[pos2] = col->linkpos[pos1];
 
   col->rows[pos1] = tmprow;
   col->vals[pos1] = tmpval;
   col->linkpos[pos1] = tmplinkpos;
 
   /* update link position in rows */
   if( col->linkpos[pos1] >= 0 )
   {
      assert(col->rows[pos1]->cols[col->linkpos[pos1]] == col);
      assert(col->rows[pos1]->linkpos[col->linkpos[pos1]] == pos2);
 
      col->rows[pos1]->linkpos[col->linkpos[pos1]] = pos1;
   }
   if( col->linkpos[pos2] >= 0 )
   {
      assert(col->rows[pos2]->cols[col->linkpos[pos2]] == col);
      assert(col->rows[pos2]->linkpos[col->linkpos[pos2]] == pos1);
 
      col->rows[pos2]->linkpos[col->linkpos[pos2]] = pos2;
   }
 
   /* update sorted flags */
   if( col->rows[pos1]->lppos >= 0 && col->linkpos[pos1] >= 0 )
      col->lprowssorted = FALSE;
   else
      col->nonlprowssorted = FALSE;
   if( col->rows[pos2]->lppos >= 0 && col->linkpos[pos2] >= 0 )
      col->lprowssorted = FALSE;
   else
      col->nonlprowssorted = FALSE;
}
 
/** moves a coefficient in a row to a different place, and updates all corresponding data structures */
static
void rowMoveCoef(
   SCIP_ROW*             row,                /**< LP row */
   int                   oldpos,             /**< old position of coefficient */
   int                   newpos              /**< new position of coefficient */
   )
{
   assert(row != NULL);
   assert(0 <= oldpos && oldpos < row->len);
   assert(0 <= newpos && newpos < row->len);
   assert(row->cols[oldpos] != NULL);
 
   if( oldpos == newpos )
      return;
 
   row->cols[newpos] = row->cols[oldpos];
   row->cols_index[newpos] = row->cols_index[oldpos];
   row->vals[newpos] = row->vals[oldpos];
   row->linkpos[newpos] = row->linkpos[oldpos];
 
   /* update link position in column */
   if( row->linkpos[newpos] >= 0 )
   {
      assert(row->cols[newpos]->rows[row->linkpos[newpos]] == row);
      assert(row->cols[newpos]->linkpos[row->linkpos[newpos]] == oldpos);
 
      row->cols[newpos]->linkpos[row->linkpos[newpos]] = newpos;
   }
 
   /* update sorted flags */
   if( row->cols[newpos]->lppos >= 0 && row->linkpos[newpos] >= 0 )
      row->lpcolssorted = FALSE;
   else
      row->nonlpcolssorted = FALSE;
}
 
/** swaps two coefficients in a row, and updates all corresponding data structures */
static
void rowSwapCoefs(
   SCIP_ROW*             row,                /**< LP row */
   int                   pos1,               /**< position of first coefficient */
   int                   pos2                /**< position of second coefficient */
   )
{
   SCIP_COL* tmpcol;
   SCIP_Real tmpval;
   int tmpindex;
   int tmplinkpos;
 
   assert(row != NULL);
   assert(0 <= pos1 && pos1 < row->len);
   assert(0 <= pos2 && pos2 < row->len);
   assert(row->cols[pos1] != NULL);
   assert(row->cols[pos1]->index == row->cols_index[pos1]);
 
   if( pos1 == pos2 )
      return;
 
   /* swap coefficients */
   tmpcol = row->cols[pos2];
   tmpindex = row->cols_index[pos2];
   tmpval = row->vals[pos2];
   tmplinkpos = row->linkpos[pos2];
 
   row->cols[pos2] = row->cols[pos1];
   row->cols_index[pos2] = row->cols_index[pos1];
   row->vals[pos2] = row->vals[pos1];
   row->linkpos[pos2] = row->linkpos[pos1];
 
   row->cols[pos1] = tmpcol;
   row->cols_index[pos1] = tmpindex;
   row->vals[pos1] = tmpval;
   row->linkpos[pos1] = tmplinkpos;
 
   /* update link position in columns */
   if( row->linkpos[pos1] >= 0 )
   {
      assert(row->cols[pos1]->rows[row->linkpos[pos1]] == row);
      assert(row->cols[pos1]->linkpos[row->linkpos[pos1]] == pos2);
 
      row->cols[pos1]->linkpos[row->linkpos[pos1]] = pos1;
   }
   if( row->linkpos[pos2] >= 0 )
   {
      assert(row->cols[pos2]->rows[row->linkpos[pos2]] == row);
      assert(row->cols[pos2]->linkpos[row->linkpos[pos2]] == pos1);
 
      row->cols[pos2]->linkpos[row->linkpos[pos2]] = pos2;
   }
 
   /* update sorted flags */
   if( row->cols[pos1]->lppos >= 0 && row->linkpos[pos1] >= 0 )
      row->lpcolssorted = FALSE;
   else
      row->nonlpcolssorted = FALSE;
   if( row->cols[pos2]->lppos >= 0 && row->linkpos[pos2] >= 0 )
      row->lpcolssorted = FALSE;
   else
      row->nonlpcolssorted = FALSE;
}
 
/** issues a ROWCOEFCHANGED event on the given row */
static
SCIP_RETCODE rowEventCoefChanged(
   SCIP_ROW*             row,                /**< row which coefficient has changed */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_COL*             col,                /**< the column which coefficient has changed */
   SCIP_Real             oldval,             /**< old value of the coefficient */
   SCIP_Real             newval              /**< new value of the coefficient */
   )
{
   assert(row != NULL);
   assert(row->eventfilter != NULL);
   assert(col != NULL);
 
   /* check, if the row is being tracked for coefficient changes
    * if so, issue ROWCOEFCHANGED event
    */
   if( (row->eventfilter->len > 0 && (row->eventfilter->eventmask & SCIP_EVENTTYPE_ROWCOEFCHANGED) != 0) )
   {
      SCIP_EVENT* event;
 
      SCIP_CALL( SCIPeventCreateRowCoefChanged(&event, blkmem, row, col, oldval, newval) );
      SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, row->eventfilter, &event) );
   }
 
   return SCIP_OKAY;
}
 
/** issues a ROWCONSTCHANGED event on the given row */
static
SCIP_RETCODE rowEventConstantChanged(
   SCIP_ROW*             row,                /**< row which coefficient has changed */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_Real             oldval,             /**< old value of the constant */
   SCIP_Real             newval              /**< new value of the constant */
   )
{
   assert(row != NULL);
   assert(row->eventfilter != NULL);
 
   /* check, if the row is being tracked for coefficient changes
    * if so, issue ROWCONSTCHANGED event
    */
   if( (row->eventfilter->len > 0 && (row->eventfilter->eventmask & SCIP_EVENTTYPE_ROWCONSTCHANGED)) )
   {
      SCIP_EVENT* event;
 
      SCIP_CALL( SCIPeventCreateRowConstChanged(&event, blkmem, row, oldval, newval) );
      SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, row->eventfilter, &event) );
   }
 
   return SCIP_OKAY;
}
 
/** issues a ROWSIDECHANGED event on the given row */
static
SCIP_RETCODE rowEventSideChanged(
   SCIP_ROW*             row,                /**< row which coefficient has changed */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_SIDETYPE         side,               /**< the side that has changed */
   SCIP_Real             oldval,             /**< old value of side */
   SCIP_Real             newval              /**< new value of side */
   )
{
   assert(row != NULL);
   assert(row->eventfilter != NULL);
 
   /* check, if the row is being tracked for coefficient changes
    * if so, issue ROWSIDECHANGED event
    */
   if( (row->eventfilter->len > 0 && !(row->eventfilter->eventmask & SCIP_EVENTTYPE_ROWSIDECHANGED)) )
   {
      SCIP_EVENT* event;
 
      SCIP_CALL( SCIPeventCreateRowSideChanged(&event, blkmem, row, side, oldval, newval) );
      SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, row->eventfilter, &event) );
   }
 
   return SCIP_OKAY;
}
 
#ifdef SCIP_MORE_DEBUG /* enable this to check links between columns and rows in LP data structure (for debugging, very slow!) */
 
#ifdef NDEBUG
#define ASSERT(x) do { if( !(x) ) abort(); } while( FALSE )
#else
#define ASSERT(x) assert(x)
#endif
 
static SCIP_Bool msgdisp_checklinks = FALSE;
 
 
static
void checkLinks(
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   SCIP_COL* col;
   SCIP_ROW* row;
   int i;
   int j;
 
   ASSERT(lp != NULL);
 
   if( !msgdisp_checklinks )
   {
      printf("LP LINK CHECKING ACTIVATED! THIS IS VERY SLOW!\n");
      msgdisp_checklinks = TRUE;
   }
 
   for( i = 0; i < lp->ncols; ++i )
   {
      col = lp->cols[i];
      ASSERT(col != NULL);
      ASSERT(!lp->flushed || col->lppos >= 0 || col->primsol == 0.0);
      ASSERT(!lp->flushed || col->lppos >= 0 || col->farkascoef == 0.0);
      ASSERT(col->nlprows <= col->len);
      ASSERT(col->lppos == -1 || col->lppos >= lp->lpifirstchgcol || col->nunlinked == 0);
 
      for( j = 0; j < col->len; ++j )
      {
         row = col->rows[j];
         ASSERT(row != NULL);
         ASSERT(!lp->flushed || col->lppos == -1 || col->linkpos[j] >= 0);
         ASSERT(col->linkpos[j] == -1 || row->cols[col->linkpos[j]] == col);
         ASSERT(col->linkpos[j] == -1 || EPSEQ(row->vals[col->linkpos[j]], col->vals[j], 1e-6));
         ASSERT((j < col->nlprows) == (col->linkpos[j] >= 0 && row->lppos >= 0));
      }
   }
 
   for( i = 0; i < lp->nrows; ++i )
   {
      row = lp->rows[i];
      ASSERT(row != NULL);
      ASSERT(!lp->flushed || row->lppos >= 0 || row->dualsol == 0.0);
      ASSERT(!lp->flushed || row->lppos >= 0 || row->dualfarkas == 0.0);
      ASSERT(row->nlpcols <= row->len);
      ASSERT(row->lppos == -1 || row->lppos >= lp->lpifirstchgrow || row->nunlinked == 0);
 
      for( j = 0; j < row->len; ++j )
      {
         col = row->cols[j];
         ASSERT(col != NULL);
         ASSERT(!lp->flushed || row->lppos == -1 || row->linkpos[j] >= 0);
         ASSERT(row->linkpos[j] == -1 || col->rows[row->linkpos[j]] == row);
         ASSERT(row->linkpos[j] == -1 || EPSEQ(col->vals[row->linkpos[j]], row->vals[j], 1e-6));
         ASSERT((j < row->nlpcols) == (row->linkpos[j] >= 0 && col->lppos >= 0));
      }
   }
}
 
#undef ASSERT
 
#else
#define checkLinks(lp) /**/
#endif
 
/*
 * Changing announcements
 */
 
/** announces, that the given coefficient in the constraint matrix changed */
static
void coefChanged(
   SCIP_ROW*             row,                /**< LP row */
   SCIP_COL*             col,                /**< LP col */
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   assert(row != NULL);
   assert(col != NULL);
   assert(lp != NULL);
 
   if( row->lpipos >= 0 && col->lpipos >= 0 )
   {
      assert(row->lpipos < lp->nlpirows);
      assert(col->lpipos < lp->nlpicols);
 
      /* we have to remember the change only in the row or in the column,
       * because the readdition of one vector would change the other automatically.
       */
      if( row->lpipos >= lp->lpifirstchgrow )
         row->coefchanged = TRUE;
      else if( col->lpipos >= lp->lpifirstchgcol )
         col->coefchanged = TRUE;
      else if( lp->lpifirstchgrow - row->lpipos <= lp->lpifirstchgcol - col->lpipos )
      {
         row->coefchanged = TRUE;
         lp->lpifirstchgrow = row->lpipos;
      }
      else
      {
         col->coefchanged = TRUE;
         lp->lpifirstchgcol = col->lpipos;
      }
 
      /* mark the current LP unflushed */
      lp->flushed = FALSE;
   }
 
   row->pseudoactivity = SCIP_INVALID;
   row->minactivity = SCIP_INVALID;
   row->maxactivity = SCIP_INVALID;
   row->validpsactivitydomchg = -1;
   row->validactivitybdsdomchg = -1;
}
 
 
 
/*
 * local column changing methods
 */
 
/* forward declaration for colAddCoef() */
static
SCIP_RETCODE rowAddCoef(
   SCIP_ROW*             row,                /**< LP row */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_COL*             col,                /**< LP column */
   SCIP_Real             val,                /**< value of coefficient */
   int                   linkpos             /**< position of row in the column's row array, or -1 */
   );
 
/** adds a previously non existing coefficient to an LP column */
static
SCIP_RETCODE colAddCoef(
   SCIP_COL*             col,                /**< LP column */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_ROW*             row,                /**< LP row */
   SCIP_Real             val,                /**< value of coefficient */
   int                   linkpos             /**< position of column in the row's col array, or -1 */
   )
{
   int pos;
 
   assert(blkmem != NULL);
   assert(col != NULL);
   assert(col->nlprows <= col->len);
   assert(col->var != NULL);
   assert(row != NULL);
   assert(!SCIPsetIsZero(set, val));
   /*assert(colSearchCoef(col, row) == -1);*/ /* this assert would lead to slight differences in the solution process */
 
   SCIP_CALL( colEnsureSize(col, blkmem, set, col->len+1) );
   assert(col->rows != NULL);
   assert(col->vals != NULL);
   assert(col->linkpos != NULL);
 
   pos = col->len;
   col->len++;
 
   /* 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
    * part of the column's arrays
    */
   if( row->lppos >= 0 && linkpos >= 0 )
   {
      /* move the first non-LP/not linked row to the end */
      if( col->nlprows < pos )
      {
         colMoveCoef(col, col->nlprows, pos);
         pos = col->nlprows;
      }
      col->nlprows++;
   }
 
   /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
   val = SCIPsetIsIntegral(set, val) ? SCIPsetRound(set, val) : val;
 
   /* insert the row at the correct position and update the links */
   col->rows[pos] = row;
   col->vals[pos] = val;
   col->linkpos[pos] = linkpos;
   if( linkpos == -1 )
   {
      col->nunlinked++;
 
      /* if the column is in current LP, we have to link it to the row, because otherwise, the primal information
       * of the row is not complete
       */
      if( col->lppos >= 0 )
      {
         /* this call might swap the current row with the first non-LP/not linked row, s.t. insertion position
          * has to be updated
          */
         SCIP_CALL( rowAddCoef(row, blkmem, set, eventqueue, lp, col, val, pos) );
         if( row->lppos >= 0 )
            pos = col->nlprows-1;
         linkpos = col->linkpos[pos];
 
         assert(0 <= linkpos && linkpos < row->len);
         assert(row->cols[linkpos] == col);
         assert(col->rows[pos] == row);
         assert(col->rows[pos]->cols[col->linkpos[pos]] == col);
         assert(col->rows[pos]->linkpos[col->linkpos[pos]] == pos);
      }
   }
   else
   {
      assert(row->linkpos[linkpos] == -1);
      assert(row->nunlinked > 0);
      row->linkpos[linkpos] = pos;
      row->nunlinked--;
 
      /* if the column is in current LP, now both conditions, row->cols[linkpos]->lppos >= 0 and row->linkpos[linkpos] >= 0
       * hold, so we have to move the column to the linked LP-cols part of the row's cols array
       */
      if( col->lppos >= 0 )
      {
         row->nlpcols++;
         rowSwapCoefs(row, linkpos, row->nlpcols-1);
 
         /* if no swap was necessary, mark nonlpcols to be unsorted */
         if( linkpos == row->nlpcols-1 )
            row->lpcolssorted = FALSE;
      }
   }
 
   /* update the sorted flags */
   if( row->lppos >= 0 && linkpos >= 0 )
   {
      assert(col->nlprows >= 1);
      assert(col->rows[col->nlprows-1] == row);
      if( col->nlprows > 1 )
         col->lprowssorted = col->lprowssorted && (col->rows[col->nlprows-2]->index < row->index);
   }
   else
   {
      assert(col->len - col->nlprows >= 1);
      assert(col->rows[col->len-1] == row);
      if( col->len - col->nlprows > 1 )
         col->nonlprowssorted = col->nonlprowssorted && (col->rows[col->len-2]->index < row->index);
   }
 
   coefChanged(row, col, lp);
 
   SCIPsetDebugMsg(set, "added coefficient %g * <%s> at position %d (%d/%d) to column <%s> (nunlinked=%d)\n",
      val, row->name, pos, col->nlprows, col->len, SCIPvarGetName(col->var), col->nunlinked);
 
   return SCIP_OKAY;
}
 
/** deletes coefficient at given position from column */
static
SCIP_RETCODE colDelCoefPos(
   SCIP_COL*             col,                /**< column to be changed */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_LP*              lp,                 /**< current LP data */
   int                   pos                 /**< position in column vector to delete */
   )
{
   SCIP_ROW* row;
 
   assert(col != NULL);
   assert(col->var != NULL);
   assert(set != NULL);
   assert(0 <= pos && pos < col->len);
   assert(col->rows[pos] != NULL);
   assert(col->linkpos[pos] == -1 || col->rows[pos]->cols[col->linkpos[pos]] == col);
   assert((pos < col->nlprows) == (col->linkpos[pos] >= 0 && col->rows[pos]->lppos >= 0));
 
   row = col->rows[pos];
   assert((row->lppos >= 0) == (pos < col->nlprows));
 
   /*SCIPsetDebugMsg(set, "deleting coefficient %g * <%s> at position %d from column <%s>\n",
     col->vals[pos], row->name, pos, SCIPvarGetName(col->var));*/
 
   if( col->linkpos[pos] == -1 )
      col->nunlinked--;
 
   /* if row is a linked LP row, move last linked LP coefficient to position of empty slot (deleted coefficient) */
   if( pos < col->nlprows )
   {
      colMoveCoef(col, col->nlprows-1, pos);
      col->nlprows--;
      pos = col->nlprows;
   }
 
   /* move last coefficient to position of empty slot */
   colMoveCoef(col, col->len-1, pos);
   col->len--;
 
   coefChanged(row, col, lp);
 
   return SCIP_OKAY;
}
 
/** changes a coefficient at given position of an LP column */
static
SCIP_RETCODE colChgCoefPos(
   SCIP_COL*             col,                /**< LP column */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_LP*              lp,                 /**< current LP data */
   int                   pos,                /**< position in column vector to change */
   SCIP_Real             val                 /**< value of coefficient */
   )
{
   assert(col != NULL);
   assert(col->var != NULL);
   assert(0 <= pos && pos < col->len);
   assert(col->rows[pos] != NULL);
   assert(col->linkpos[pos] == -1 || col->rows[pos]->cols[col->linkpos[pos]] == col);
 
   /*debugMsg(scip, "changing coefficient %g * <%s> at position %d of column <%s> to %g\n",
     col->vals[pos], col->rows[pos]->name, pos, SCIPvarGetName(col->var), val);*/
 
   /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
   val = SCIPsetIsIntegral(set, val) ? SCIPsetRound(set, val) : val;
 
   if( SCIPsetIsZero(set, val) )
   {
      /* delete existing coefficient */
      SCIP_CALL( colDelCoefPos(col, set, lp, pos) );
   }
   else if( !SCIPsetIsEQ(set, col->vals[pos], val) )
   {
      /* change existing coefficient */
      col->vals[pos] = val;
      coefChanged(col->rows[pos], col, lp);
   }
 
   return SCIP_OKAY;
}
 
 
 
 
/*
 * local row changing methods
 */
 
/** update row norms after addition of coefficient */
static
void rowAddNorms(
   SCIP_ROW*             row,                /**< LP row */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_COL*             col,                /**< column of added coefficient */
   SCIP_Real             val,                /**< value of added coefficient */
   SCIP_Bool             updateidxvals       /**< update min/max idx and min/max val? */
   )
{
   SCIP_Real absval;
 
   assert(row != NULL);
   assert(row->nummaxval >= 0);
   assert(row->numminval >= 0);
   assert(set != NULL);
   assert(col != NULL);
 
   absval = REALABS(val);
   assert(!SCIPsetIsZero(set, absval));
 
   /* Euclidean norm, sum norm, and objective function scalar product only take LP columns into account */
   if( col->lppos >= 0 )
   {
      /* update squared Euclidean norm and sum norm */
      row->sqrnorm += SQR(absval);
      row->sumnorm += absval;
 
      /* update objective function scalar product */
      row->objprod += val * col->unchangedobj;
   }
 
   if( updateidxvals )
   {
      /* update min/maxidx */
      row->minidx = MIN(row->minidx, col->index);
      row->maxidx = MAX(row->maxidx, col->index);
 
      /* update maximal and minimal non-zero value */
      if( row->nummaxval > 0 )
      {
         if( SCIPsetIsGT(set, absval, row->maxval) )
         {
            row->maxval = absval;
            row->nummaxval = 1;
         }
         else if( SCIPsetIsGE(set, absval, row->maxval) )
         {
            /* make sure the maxval is always exactly the same */
            row->maxval = MAX(absval, row->maxval);
            row->nummaxval++;
         }
      }
      if( row->numminval > 0 )
      {
         if( SCIPsetIsLT(set, absval, row->minval) )
         {
            row->minval = absval;
            row->numminval = 1;
         }
         else if( SCIPsetIsLE(set, absval, row->minval) )
         {
            /* make sure the minval is always exactly the same */
            row->minval = MIN(absval, row->minval);
            row->numminval++;
         }
      }
   }
   else
   {
      assert(row->minidx <= col->index);
      assert(row->maxidx >= col->index);
      assert(row->numminval <= 0 || absval >= row->minval);
      assert(row->nummaxval <= 0 || absval <= row->maxval);
   }
}
 
/** update row norms after deletion of coefficient */
static
void rowDelNorms(
   SCIP_ROW*             row,                /**< LP row */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_COL*             col,                /**< column of deleted coefficient */
   SCIP_Real             val,                /**< value of deleted coefficient */
   SCIP_Bool             forcenormupdate,    /**< should the norms be updated even if lppos of column is -1? */
   SCIP_Bool             updateindex,        /**< should the minimal/maximal column index of row be updated? */
   SCIP_Bool             updateval           /**< should the minimal/maximal value of row be updated? */
   )
{
   SCIP_Real absval;
 
   assert(row != NULL);
   assert(row->nummaxval >= 0);
   assert(row->numminval >= 0);
   assert(set != NULL);
   assert(col != NULL);
 
   absval = REALABS(val);
   assert(!SCIPsetIsZero(set, absval));
   assert(row->nummaxval == 0 || row->maxval >= absval);
   assert(row->numminval == 0 || row->minval <= absval);
 
   /* update min/maxidx validity */
   if( updateindex && (col->index == row->minidx || col->index == row->maxidx) )
      row->validminmaxidx = FALSE;
 
   /* Euclidean norm, sum norm, and objective function scalar product only take LP columns into account */
   if( forcenormupdate || col->lppos >= 0 )
   {
      /* update squared Euclidean norm and sum norm */
      row->sqrnorm -= SQR(absval);
      row->sqrnorm = MAX(row->sqrnorm, 0.0);
      row->sumnorm -= absval;
      row->sumnorm = MAX(row->sumnorm, 0.0);
 
      /* update objective function scalar product */
      row->objprod -= val * col->unchangedobj;
   }
 
   if( updateval )
   {
      /* update maximal and minimal non-zero value */
      if( row->nummaxval > 0 )
      {
         if( SCIPsetIsGE(set, absval, row->maxval) )
            row->nummaxval--;
      }
      if( row->numminval > 0 )
      {
         if( SCIPsetIsLE(set, absval, row->minval) )
            row->numminval--;
      }
   }
}
 
/** adds a previously non existing coefficient to an LP row */
static
SCIP_RETCODE rowAddCoef(
   SCIP_ROW*             row,                /**< LP row */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_COL*             col,                /**< LP column */
   SCIP_Real             val,                /**< value of coefficient */
   int                   linkpos             /**< position of row in the column's row array, or -1 */
   )
{
   int pos;
 
   assert(row != NULL);
   assert(row->nlpcols <= row->len);
   assert(blkmem != NULL);
   assert(col != NULL);
   assert(col->var != NULL);
   assert(col->var_probindex == SCIPvarGetProbindex(col->var));
   assert(!SCIPsetIsZero(set, val));
   /*assert(rowSearchCoef(row, col) == -1);*/ /* this assert would lead to slight differences in the solution process */
 
   if( row->nlocks > 0 )
   {
      SCIPerrorMessage("cannot add a coefficient to the locked unmodifiable row <%s>\n", row->name);
      return SCIP_INVALIDDATA;
   }
 
   SCIP_CALL( SCIProwEnsureSize(row, blkmem, set, row->len+1) );
   assert(row->cols != NULL);
   assert(row->vals != NULL);
 
   pos = row->len;
   row->len++;
 
   /* 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
    * part of the row's arrays
    */
   if( col->lppos >= 0 && linkpos >= 0 )
   {
      /* move the first non-LP/not linked column to the end */
      if( row->nlpcols < pos )
      {
         rowMoveCoef(row, row->nlpcols, pos);
         pos = row->nlpcols;
      }
      row->nlpcols++;
   }
 
   /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
   val = SCIPsetIsIntegral(set, val) ? SCIPsetRound(set, val) : val;
 
   /* insert the column at the correct position and update the links */
   row->cols[pos] = col;
   row->cols_index[pos] = col->index;
   row->vals[pos] = val;
   row->linkpos[pos] = linkpos;
   row->integral = row->integral && SCIPcolIsIntegral(col) && SCIPsetIsIntegral(set, val);
   if( linkpos == -1 )
   {
      row->nunlinked++;
 
      /* if the row is in current LP, we have to link it to the column, because otherwise, the dual information
       * of the column is not complete
       */
      if( row->lppos >= 0 )
      {
         /* this call might swap the current column with the first non-LP/not linked column, s.t. insertion position
          * has to be updated
          */
         SCIP_CALL( colAddCoef(col, blkmem, set, eventqueue, lp, row, val, pos) );
         if( col->lppos >= 0 )
            pos = row->nlpcols-1;
         linkpos = row->linkpos[pos];
 
         assert(0 <= linkpos && linkpos < col->len);
         assert(col->rows[linkpos] == row);
         assert(row->cols[pos] == col);
         assert(row->cols[pos]->rows[row->linkpos[pos]] == row);
         assert(row->cols[pos]->linkpos[row->linkpos[pos]] == pos);
      }
   }
   else
   {
      assert(col->linkpos[linkpos] == -1);
      assert(col->nunlinked > 0);
      col->linkpos[linkpos] = pos;
      col->nunlinked--;
 
      /* if the row is in current LP, now both conditions, col->rows[linkpos]->lppos >= 0 and col->linkpos[linkpos] >= 0
       * hold, so we have to move the row to the linked LP-rows part of the column's rows array
       */
      if( row->lppos >= 0 )
      {
         col->nlprows++;
         colSwapCoefs(col, linkpos, col->nlprows-1);
 
         /* if no swap was necessary, mark lprows to be unsorted */
         if( linkpos == col->nlprows-1 )
            col->lprowssorted = FALSE;
      }
   }
 
   /* update the sorted flags */
   if( col->lppos >= 0 && linkpos >= 0 )
   {
      assert(row->nlpcols >= 1);
      assert(row->cols[row->nlpcols-1] == col);
      if( row->nlpcols > 1 )
      {
         assert(row->cols_index[row->nlpcols-2] == row->cols[row->nlpcols-2]->index);
         row->lpcolssorted = row->lpcolssorted && (row->cols_index[row->nlpcols-2] < col->index);
      }
   }
   else
   {
      assert(row->len - row->nlpcols >= 1);
      assert(row->cols[row->len-1] == col);
      if( row->len - row->nlpcols > 1 )
      {
         assert(row->cols_index[row->len-2] == row->cols[row->len-2]->index);
         row->nonlpcolssorted = row->nonlpcolssorted && (row->cols_index[row->len-2] < col->index);
      }
   }
 
   /* update row norm */
   rowAddNorms(row, set, col, val, TRUE);
 
   coefChanged(row, col, lp);
 
   SCIPsetDebugMsg(set, "added coefficient %g * <%s> at position %d (%d/%d) to row <%s> (nunlinked=%d)\n",
      val, SCIPvarGetName(col->var), pos, row->nlpcols, row->len, row->name, row->nunlinked);
 
   /* issue row coefficient changed event */
   SCIP_CALL( rowEventCoefChanged(row, blkmem, set, eventqueue, col, 0.0, val) );
 
   return SCIP_OKAY;
}
 
/** deletes coefficient at given position from row */
static
SCIP_RETCODE rowDelCoefPos(
   SCIP_ROW*             row,                /**< row to be changed */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp,                 /**< current LP data */
   int                   pos                 /**< position in row vector to delete */
   )
{
   SCIP_COL* col;
   SCIP_Real val;
 
   assert(row != NULL);
   assert(set != NULL);
   assert(0 <= pos && pos < row->len);
   assert(row->cols[pos] != NULL);
   assert((pos < row->nlpcols) == (row->linkpos[pos] >= 0 && row->cols[pos]->lppos >= 0));
 
   col = row->cols[pos];
   val = row->vals[pos];
   assert((pos < row->nlpcols) == (col->lppos >= 0 && row->linkpos[pos] >= 0));
 
   /*SCIPsetDebugMsg(set, "deleting coefficient %g * <%s> at position %d from row <%s>\n",
     val, SCIPvarGetName(col->var), pos, row->name);*/
 
   if( row->nlocks > 0 )
   {
      SCIPerrorMessage("cannot delete a coefficient from the locked unmodifiable row <%s>\n", row->name);
      return SCIP_INVALIDDATA;
   }
 
   if( row->linkpos[pos] == -1 )
      row->nunlinked--;
 
   /* if column is a linked LP column, move last linked LP coefficient to position of empty slot (deleted coefficient) */
   if( pos < row->nlpcols )
   {
      rowMoveCoef(row, row->nlpcols-1, pos);
      assert(!row->lpcolssorted);
      row->nlpcols--;
      pos = row->nlpcols;
   }
 
   /* move last coefficient to position of empty slot */
   rowMoveCoef(row, row->len-1, pos);
   row->len--;
 
   /* update norms */
   rowDelNorms(row, set, col, val, FALSE, TRUE, TRUE);
 
   coefChanged(row, col, lp);
 
   /* issue row coefficient changed event */
   SCIP_CALL( rowEventCoefChanged(row, blkmem, set, eventqueue, col, val, 0.0) );
 
   return SCIP_OKAY;
}
 
/** changes a coefficient at given position of an LP row */
static
SCIP_RETCODE rowChgCoefPos(
   SCIP_ROW*             row,                /**< LP row */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp,                 /**< current LP data */
   int                   pos,                /**< position in row vector to change */
   SCIP_Real             val                 /**< value of coefficient */
   )
{
   SCIP_COL* col;
 
   assert(row != NULL);
   assert(0 <= pos && pos < row->len);
 
   /*SCIPsetDebugMsg(set, "changing coefficient %g * <%s> at position %d of row <%s> to %g\n",
     row->vals[pos], SCIPvarGetName(row->cols[pos]->var), pos, row->name, val);*/
 
   if( row->nlocks > 0 )
   {
      SCIPerrorMessage("cannot change a coefficient of the locked unmodifiable row <%s>\n", row->name);
      return SCIP_INVALIDDATA;
   }
 
   /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
   val = SCIPsetIsIntegral(set, val) ? SCIPsetRound(set, val) : val;
   col = row->cols[pos];
   assert(row->cols[pos] != NULL);
 
   if( SCIPsetIsZero(set, val) )
   {
      /* delete existing coefficient */
      SCIP_CALL( rowDelCoefPos(row, blkmem, set, eventqueue, lp, pos) );
   }
   else if( !SCIPsetIsEQ(set, row->vals[pos], val) )
   {
      SCIP_Real oldval;
 
      oldval = row->vals[pos];
 
      /* change existing coefficient */
      rowDelNorms(row, set, col, row->vals[pos], FALSE, FALSE, TRUE);
      row->vals[pos] = val;
      row->integral = row->integral && SCIPcolIsIntegral(col) && SCIPsetIsIntegral(set, val);
      rowAddNorms(row, set, col, row->vals[pos], TRUE);
      coefChanged(row, col, lp);
 
      /* issue row coefficient changed event */
      SCIP_CALL( rowEventCoefChanged(row, blkmem, set, eventqueue, col, oldval, val) );
   }
 
   return SCIP_OKAY;
}
 
/** notifies LP row, that its sides were changed */
static
SCIP_RETCODE rowSideChanged(
   SCIP_ROW*             row,                /**< LP row */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SIDETYPE         sidetype            /**< type of side: left or right hand side */
   )
{
   assert(row != NULL);
   assert(lp != NULL);
 
   if( row->lpipos >= 0 )
   {
      /* insert row in the chgrows list (if not already there) */
      if( !row->lhschanged && !row->rhschanged )
      {
         SCIP_CALL( ensureChgrowsSize(lp, set, lp->nchgrows+1) );
         lp->chgrows[lp->nchgrows] = row;
         lp->nchgrows++;
      }
 
      /* mark side change in the row */
      switch( sidetype )
      {
      case SCIP_SIDETYPE_LEFT:
         row->lhschanged = TRUE;
         break;
      case SCIP_SIDETYPE_RIGHT:
         row->rhschanged = TRUE;
         break;
      default:
         SCIPerrorMessage("unknown row side type\n");
         SCIPABORT();
         return SCIP_INVALIDDATA;  /*lint !e527*/
      }
 
      /* mark the current LP unflushed */
      lp->flushed = FALSE;
 
      assert(lp->nchgrows > 0);
   }
 
   return SCIP_OKAY;
}
 
 
 
 
/*
 * double linked coefficient matrix methods
 */
 
/** insert column coefficients in corresponding rows */
SCIP_RETCODE colLink(
   SCIP_COL*             col,                /**< column data */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   int i;
 
   assert(col != NULL);
   assert(col->var != NULL);
   assert(blkmem != NULL);
   assert(set != NULL);
   assert(lp != NULL);
 
   if( col->nunlinked > 0 )
   {
      SCIPsetDebugMsg(set, "linking column <%s>\n", SCIPvarGetName(col->var));
 
      /* unlinked rows can only be in the non-LP/unlinked rows part of the rows array */
      for( i = col->nlprows; i < col->len; ++i )
      {
         assert(!SCIPsetIsZero(set, col->vals[i]));
         if( col->linkpos[i] == -1 )
         {
            /* this call might swap the current row with the first non-LP/not linked row, but this is of no harm */
            SCIP_CALL( rowAddCoef(col->rows[i], blkmem, set, eventqueue, lp, col, col->vals[i], i) );
         }
         assert(col->rows[i]->cols[col->linkpos[i]] == col);
         assert(col->rows[i]->linkpos[col->linkpos[i]] == i);
         assert(col->nlprows == 0 || col->rows[col->nlprows-1]->cols[col->linkpos[col->nlprows-1]] == col);
         assert(col->nlprows == 0 || col->rows[col->nlprows-1]->linkpos[col->linkpos[col->nlprows-1]] == col->nlprows-1);
      }
   }
   assert(col->nunlinked == 0);
 
   checkLinks(lp);
 
   return SCIP_OKAY;
}
 
/** removes column coefficients from corresponding rows */
SCIP_RETCODE colUnlink(
   SCIP_COL*             col,                /**< column data */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   int i;
 
   assert(col != NULL);
   assert(col->var != NULL);
   assert(blkmem != NULL);
   assert(set != NULL);
   assert(lp != NULL);
 
   if( col->nunlinked < col->len )
   {
      SCIPsetDebugMsg(set, "unlinking column <%s>\n", SCIPvarGetName(col->var));
      for( i = 0; i < col->len; ++i )
      {
         if( col->linkpos[i] >= 0 )
         {
            assert(col->rows[i]->cols[col->linkpos[i]] == col);
            SCIP_CALL( rowDelCoefPos(col->rows[i], blkmem, set, eventqueue, lp, col->linkpos[i]) );
            col->linkpos[i] = -1;
            col->nunlinked++;
         }
      }
   }
   assert(col->nunlinked == col->len);
 
   checkLinks(lp);
 
   return SCIP_OKAY;
}
 
/** insert row coefficients in corresponding columns */
SCIP_RETCODE rowLink(
   SCIP_ROW*             row,                /**< row data */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   int i;
 
   assert(row != NULL);
   assert(blkmem != NULL);
   assert(set != NULL);
   assert(lp != NULL);
 
   if( row->nunlinked > 0 )
   {
      SCIPsetDebugMsg(set, "linking row <%s>\n", row->name);
 
      /* unlinked columns can only be in the non-LP/unlinked columns part of the cols array */
      for( i = row->nlpcols; i < row->len; ++i )
      {
         assert(!SCIPsetIsZero(set, row->vals[i]));
         if( row->linkpos[i] == -1 )
         {
            /* this call might swap the current column with the first non-LP/not linked column, but this is of no harm */
            SCIP_CALL( colAddCoef(row->cols[i], blkmem, set, eventqueue, lp, row, row->vals[i], i) );
         }
         assert(row->cols[i]->rows[row->linkpos[i]] == row);
         assert(row->cols[i]->linkpos[row->linkpos[i]] == i);
         assert(row->nlpcols == 0 || row->cols[row->nlpcols-1]->rows[row->linkpos[row->nlpcols-1]] == row);
         assert(row->nlpcols == 0 || row->cols[row->nlpcols-1]->linkpos[row->linkpos[row->nlpcols-1]] == row->nlpcols-1);
      }
   }
   assert(row->nunlinked == 0);
 
   checkLinks(lp);
 
   return SCIP_OKAY;
}
 
/** removes row coefficients from corresponding columns */
SCIP_RETCODE rowUnlink(
   SCIP_ROW*             row,                /**< row data */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   int i;
 
   assert(row != NULL);
   assert(set != NULL);
   assert(lp != NULL);
 
   if( row->nunlinked < row->len )
   {
      SCIPsetDebugMsg(set, "unlinking row <%s>\n", row->name);
      for( i = 0; i < row->len; ++i )
      {
         if( row->linkpos[i] >= 0 )
         {
            assert(row->cols[i]->rows[row->linkpos[i]] == row);
            SCIP_CALL( colDelCoefPos(row->cols[i], set, lp, row->linkpos[i]) );
            row->nunlinked++;
         }
      }
   }
   assert(row->nunlinked == row->len);
 
   return SCIP_OKAY;
}
 
 
 
 
/*
 * local LP parameter methods
 */
 
/** sets parameter of type int in LP solver, ignoring unknown parameters */
static
SCIP_RETCODE lpSetIntpar(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_LPPARAM          lpparam,            /**< LP parameter */
   int                   value,              /**< value to set parameter to */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   SCIP_RETCODE retcode;
 
   assert(lp != NULL);
   assert(success != NULL);
 
   retcode = SCIPlpiSetIntpar(lp->lpi, lpparam, value);
 
   /* check, if parameter is unknown */
   if( retcode == SCIP_PARAMETERUNKNOWN )
   {
      *success = FALSE;
      return SCIP_OKAY;
   }
   *success = TRUE;
 
   return retcode;
}
 
/** sets parameter of type SCIP_Bool in LP solver, ignoring unknown parameters */
static
SCIP_RETCODE lpSetBoolpar(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_LPPARAM          lpparam,            /**< LP parameter */
   SCIP_Bool             value,              /**< value to set parameter to */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   return lpSetIntpar(lp, lpparam, (int)value, success);
}
 
/** sets parameter of type SCIP_Real in LP solver, ignoring unknown parameters */
static
SCIP_RETCODE lpSetRealpar(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_LPPARAM          lpparam,            /**< LP parameter */
   SCIP_Real             value,              /**< value to set parameter to */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   SCIP_RETCODE retcode;
 
   assert(lp != NULL);
   assert(success != NULL);
 
   retcode = SCIPlpiSetRealpar(lp->lpi, lpparam, value);
 
   /* check, if parameter is unknown */
   if( retcode == SCIP_PARAMETERUNKNOWN )
   {
      *success = FALSE;
      return SCIP_OKAY;
   }
   *success = TRUE;
 
   return retcode;
}
 
#ifndef NDEBUG
/** checks, that parameter of type int in LP solver has the given value, ignoring unknown parameters */
static
SCIP_RETCODE lpCheckIntpar(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_LPPARAM          lpparam,            /**< LP parameter */
   int                   value               /**< value parameter should have */
   )
{
   SCIP_RETCODE retcode;
   int lpivalue;
 
   assert(lp != NULL);
 
   retcode = SCIPlpiGetIntpar(lp->lpi, lpparam, &lpivalue);
 
   /* ignore unknown parameter error */
   if( retcode == SCIP_PARAMETERUNKNOWN )
      return SCIP_OKAY;
 
   /* check value */
   assert(lpivalue == value);
 
   return retcode;
}
 
/** checks, that parameter of type SCIP_Bool in LP solver has the given value, ignoring unknown parameters */
static
SCIP_RETCODE lpCheckBoolpar(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_LPPARAM          lpparam,            /**< LP parameter */
   SCIP_Bool             value               /**< value parameter should have */
   )
{
   return lpCheckIntpar(lp, lpparam, (int)value);
}
 
/** checks, that parameter of type SCIP_Real in LP solver has the given value, ignoring unknown parameters */
static
SCIP_RETCODE lpCheckRealpar(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_LPPARAM          lpparam,            /**< LP parameter */
   SCIP_Real             value               /**< value parameter should have */
   )
{
   SCIP_RETCODE retcode;
   SCIP_Real lpivalue;
 
   assert(lp != NULL);
 
   retcode = SCIPlpiGetRealpar(lp->lpi, lpparam, &lpivalue);
 
   /* ignore unknown parameter error */
   if( retcode == SCIP_PARAMETERUNKNOWN )
      return SCIP_OKAY;
 
   /* check value */
   assert(lpivalue == value); /*lint !e777*/
 
   return retcode;
}
#else
#define lpCheckIntpar(lp, lpparam, value) SCIP_OKAY
#define lpCheckBoolpar(lp, lpparam, value) SCIP_OKAY
#define lpCheckRealpar(lp, lpparam, value) SCIP_OKAY
#endif
 
/** should the objective limit of the LP solver be disabled */
#define lpCutoffDisabled(set,prob) (set->lp_disablecutoff == 1 || ((set->nactivepricers > 0 || !SCIPprobAllColsInLP(prob, set, lp)) && set->lp_disablecutoff == 2))
 
/** sets the objective limit of the LP solver
 *
 *  Note that we are always minimizing.
 */
static
SCIP_RETCODE lpSetObjlim(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_PROB*            prob,               /**< problem data */
   SCIP_Real             objlim,             /**< new objective limit */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was actually changed */
   )
{
   assert(lp != NULL);
   assert(set != NULL);
   assert(success != NULL);
 
   *success = FALSE;
 
   /* We disabled the objective limit in the LP solver or we want so solve exactly and thus cannot rely on the LP
    * solver's objective limit handling, so we make sure that the objective limit is inactive (infinity). */
   if( lpCutoffDisabled(set, prob) || set->misc_exactsolve )
      objlim = SCIPlpiInfinity(lp->lpi);
 
   /* convert SCIP infinity value to lp-solver infinity value if necessary */
   if( SCIPsetIsInfinity(set, objlim) )
      objlim = SCIPlpiInfinity(lp->lpi);
 
   SCIP_CALL( lpCheckRealpar(lp, SCIP_LPPAR_OBJLIM, lp->lpiobjlim) );
 
   if( objlim != lp->lpiobjlim ) /*lint !e777*/
   {
      SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_OBJLIM, objlim, success) );
      if( *success )
      {
         SCIP_Real actualobjlim;
 
         /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
         SCIP_CALL( SCIPlpiGetRealpar(lp->lpi, SCIP_LPPAR_OBJLIM, &actualobjlim) );
         if( actualobjlim != lp->lpiobjlim ) /*lint !e777*/
         {
            /* mark the current solution invalid */
            lp->solved = FALSE;
            lp->primalfeasible = FALSE;
            lp->primalchecked = FALSE;
            lp->lpobjval = SCIP_INVALID;
            lp->lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
         }
         lp->lpiobjlim = actualobjlim;
      }
   }
 
   return SCIP_OKAY;
}
 
/** sets the feasibility tolerance of the LP solver */
static
SCIP_RETCODE lpSetFeastol(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Real             feastol,            /**< new feasibility tolerance */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was actually changed */
   )
{
   assert(lp != NULL);
   assert(feastol >= 0.0);
   assert(success != NULL);
 
   SCIP_CALL( lpCheckRealpar(lp, SCIP_LPPAR_FEASTOL, lp->lpifeastol) );
 
   if( feastol != lp->lpifeastol ) /*lint !e777*/
   {
      SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_FEASTOL, feastol, success) );
      if( *success )
      {
         SCIP_Real actualfeastol;
 
         /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
         SCIP_CALL( SCIPlpiGetRealpar(lp->lpi, SCIP_LPPAR_FEASTOL, &actualfeastol) );
         if( lp->nrows > 0 && actualfeastol < lp->lpifeastol )
         {
            /* mark the current solution invalid */
            lp->solved = FALSE;
            lp->primalfeasible = FALSE;
            lp->primalchecked = FALSE;
            lp->lpobjval = SCIP_INVALID;
            lp->lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
         }
         else
            *success = FALSE;
         lp->lpifeastol = actualfeastol;
      }
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the reduced costs feasibility tolerance of the LP solver */
static
SCIP_RETCODE lpSetDualfeastol(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Real             dualfeastol,        /**< new reduced costs feasibility tolerance */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was actually changed */
   )
{
   assert(lp != NULL);
   assert(dualfeastol >= 0.0);
   assert(success != NULL);
 
   SCIP_CALL( lpCheckRealpar(lp, SCIP_LPPAR_DUALFEASTOL, lp->lpidualfeastol) );
 
   if( dualfeastol != lp->lpidualfeastol ) /*lint !e777*/
   {
      SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_DUALFEASTOL, dualfeastol, success) );
      if( *success )
      {
         SCIP_Real actualdualfeastol;
 
         /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
         SCIP_CALL( SCIPlpiGetRealpar(lp->lpi, SCIP_LPPAR_DUALFEASTOL, &actualdualfeastol) );
         if( lp->nrows > 0 && actualdualfeastol < lp->lpidualfeastol )
         {
            /* mark the current solution invalid */
            lp->solved = FALSE;
            lp->dualfeasible = FALSE;
            lp->dualchecked = FALSE;
            lp->lpobjval = SCIP_INVALID;
            lp->lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
         }
         else
            *success = FALSE;
         lp->lpidualfeastol = actualdualfeastol;
      }
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the convergence tolerance used in barrier algorithm of the LP solver */
static
SCIP_RETCODE lpSetBarrierconvtol(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Real             barrierconvtol,     /**< new convergence tolerance used in barrier algorithm */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was actually changed */
   )
{
   assert(lp != NULL);
   assert(barrierconvtol >= 0.0);
   assert(success != NULL);
 
   SCIP_CALL( lpCheckRealpar(lp, SCIP_LPPAR_BARRIERCONVTOL, lp->lpibarrierconvtol) );
 
   if( barrierconvtol != lp->lpibarrierconvtol ) /*lint !e777*/
   {
      SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_BARRIERCONVTOL, barrierconvtol, success) );
      if( *success )
      {
         SCIP_Real actualbarrierconvtol;
 
         /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
         SCIP_CALL( SCIPlpiGetRealpar(lp->lpi, SCIP_LPPAR_BARRIERCONVTOL, &actualbarrierconvtol) );
         if( lp->nrows > 0 && actualbarrierconvtol < lp->lpibarrierconvtol
            && (lp->lastlpalgo == SCIP_LPALGO_BARRIER || lp->lastlpalgo == SCIP_LPALGO_BARRIERCROSSOVER) )
         {
            /* mark the current solution invalid */
            lp->solved = FALSE;
            lp->dualfeasible = FALSE;
            lp->dualchecked = FALSE;
            lp->lpobjval = SCIP_INVALID;
            lp->lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
         }
         else
            *success = FALSE;
         lp->lpibarrierconvtol = actualbarrierconvtol;
      }
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the FROMSCRATCH setting of the LP solver */
static
SCIP_RETCODE lpSetFromscratch(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Bool             fromscratch,        /**< new FROMSCRATCH setting */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   assert(lp != NULL);
   assert(success != NULL);
 
   SCIP_CALL( lpCheckBoolpar(lp, SCIP_LPPAR_FROMSCRATCH, lp->lpifromscratch) );
 
   if( fromscratch != lp->lpifromscratch )
   {
      SCIP_CALL( lpSetBoolpar(lp, SCIP_LPPAR_FROMSCRATCH, fromscratch, success) );
      if( *success )
         lp->lpifromscratch = fromscratch;
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the FASTMIP setting of the LP solver */
static
SCIP_RETCODE lpSetFastmip(
   SCIP_LP*              lp,                 /**< current LP data */
   int                   fastmip,            /**< new FASTMIP setting */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   assert(lp != NULL);
   assert(success != NULL);
   assert(0 <= fastmip && fastmip <= 1);
 
   SCIP_CALL( lpCheckIntpar(lp, SCIP_LPPAR_FASTMIP, lp->lpifastmip) );
 
   if( fastmip != lp->lpifastmip )
   {
      SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_FASTMIP, fastmip, success) );
      if( *success )
      {
         lp->lpifastmip = fastmip;
         lp->solved = FALSE;
         /* We might only set lp->solved to false if fastmip is turned off, since the latter should be the more
          * demanding setting; however, in the current code, this should have not effect. */
      }
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the SCALING setting of the LP solver */
static
SCIP_RETCODE lpSetScaling(
   SCIP_LP*              lp,                 /**< current LP data */
   int                   scaling,            /**< new SCALING setting */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   assert(lp != NULL);
   assert(success != NULL);
 
   SCIP_CALL( lpCheckIntpar(lp, SCIP_LPPAR_SCALING, lp->lpiscaling) );
 
   if( scaling != lp->lpiscaling )
   {
      SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_SCALING, scaling, success) );
      if( *success )
         lp->lpiscaling = scaling;
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the number of THREADS  of the LP solver */
static
SCIP_RETCODE lpSetThreads(
   SCIP_LP*              lp,                 /**< current LP data */
   int                   threads,            /**< new number of threads used to solve the LP */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   assert(lp != NULL);
   assert(success != NULL);
 
   SCIP_CALL( lpCheckIntpar(lp, SCIP_LPPAR_THREADS, lp->lpithreads) );
 
   if( threads != lp->lpithreads )
   {
      SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_THREADS, threads, success) );
      if( *success )
         lp->lpithreads = threads;
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the PRESOLVING setting of the LP solver */
static
SCIP_RETCODE lpSetPresolving(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Bool             presolving,         /**< new PRESOLVING setting */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   assert(lp != NULL);
   assert(success != NULL);
 
   SCIP_CALL( lpCheckBoolpar(lp, SCIP_LPPAR_PRESOLVING, lp->lpipresolving) );
 
   if( presolving != lp->lpipresolving )
   {
      SCIP_CALL( lpSetBoolpar(lp, SCIP_LPPAR_PRESOLVING, presolving, success) );
      if( *success )
         lp->lpipresolving = presolving;
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the ROWREPSWITCH setting of the LP solver */
static
SCIP_RETCODE lpSetRowrepswitch(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Real             rowrepswitch,       /**< new ROWREPSWITCH value */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   assert(lp != NULL);
   assert(success != NULL);
 
   SCIP_CALL( lpCheckRealpar(lp, SCIP_LPPAR_ROWREPSWITCH, lp->lpirowrepswitch) );
 
   if( rowrepswitch != lp->lpirowrepswitch )  /*lint !e777*/
   {
      SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_ROWREPSWITCH, rowrepswitch, success) );
      if( *success )
         lp->lpirowrepswitch = rowrepswitch;
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the iteration limit of the LP solver */
static
SCIP_RETCODE lpSetIterationLimit(
   SCIP_LP*              lp,                 /**< current LP data */
   int                   itlim               /**< maximal number of LP iterations to perform, or -1 for no limit */
   )
{
   SCIP_Bool success;
 
   assert(lp != NULL);
   assert(itlim >= -1);
 
   if( itlim == -1 )
      itlim = INT_MAX;
 
   SCIP_CALL( lpCheckIntpar(lp, SCIP_LPPAR_LPITLIM, lp->lpiitlim) );
 
   if( itlim != lp->lpiitlim )
   {
      SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_LPITLIM, itlim, &success) );
      if( success )
      {
         if( itlim > lp->lpiitlim )
         {
            /* mark the current solution invalid */
            lp->solved = FALSE;
            lp->lpobjval = SCIP_INVALID;
            lp->lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
         }
         lp->lpiitlim = itlim;
      }
   }
 
   return SCIP_OKAY;
}
 
/** sets the pricing strategy of the LP solver */
static
SCIP_RETCODE lpSetPricing(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_PRICING          pricing             /**< pricing strategy */
   )
{
   SCIP_Bool success;
 
   assert(lp != NULL);
 
   SCIP_CALL( lpCheckIntpar(lp, SCIP_LPPAR_PRICING, (int)lp->lpipricing) );
 
   if( pricing != lp->lpipricing )
   {
      SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_PRICING, (int)pricing, &success) );
      if( success )
         lp->lpipricing = pricing;
   }
 
   return SCIP_OKAY;
}
 
/** sets the pricing strategy of the LP solver (given the character representation of the strategy) */
static
SCIP_RETCODE lpSetPricingChar(
   SCIP_LP*              lp,                 /**< current LP data */
   char                  pricingchar         /**< character representing the pricing strategy */
   )
{
   SCIP_PRICING pricing;
 
   switch( pricingchar )
   {
   case 'l':
      pricing = SCIP_PRICING_LPIDEFAULT;
      break;
   case 'a':
      pricing = SCIP_PRICING_AUTO;
      break;
   case 'f':
      pricing = SCIP_PRICING_FULL;
      break;
   case 'p':
      pricing = SCIP_PRICING_PARTIAL;
      break;
   case 's':
      pricing = SCIP_PRICING_STEEP;
      break;
   case 'q':
      pricing = SCIP_PRICING_STEEPQSTART;
      break;
   case 'd':
      pricing = SCIP_PRICING_DEVEX;
      break;
   default:
      SCIPerrorMessage("invalid LP pricing parameter <%c>\n", pricingchar);
      return SCIP_INVALIDDATA;
   }
 
   SCIP_CALL( lpSetPricing(lp, pricing) );
 
   return SCIP_OKAY;
}
 
/** sets the verbosity of the LP solver */
static
SCIP_RETCODE lpSetLPInfo(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Bool             lpinfo              /**< should the LP solver display status messages? */
   )
{
   SCIP_Bool success;
 
   assert(lp != NULL);
 
   SCIP_CALL( lpCheckBoolpar(lp, SCIP_LPPAR_LPINFO, lp->lpilpinfo) );
 
   if( lpinfo != lp->lpilpinfo )
   {
      SCIP_CALL( lpSetBoolpar(lp, SCIP_LPPAR_LPINFO, lpinfo, &success) );
      if( success )
         lp->lpilpinfo = lpinfo;
   }
 
   return SCIP_OKAY;
}
 
/** sets the CONDITIONLIMIT setting of the LP solver */
static
SCIP_RETCODE lpSetConditionLimit(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Real             condlimit,          /**< new CONDITIONLIMIT value */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   assert(lp != NULL);
   assert(success != NULL);
 
   SCIP_CALL( lpCheckRealpar(lp, SCIP_LPPAR_CONDITIONLIMIT, lp->lpiconditionlimit) );
 
   if( condlimit != lp->lpiconditionlimit )  /*lint !e777*/
   {
      SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_CONDITIONLIMIT, condlimit, success) );
      if( *success )
         lp->lpiconditionlimit = condlimit;
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the MARKOWITZ setting of the LP solver */
static
SCIP_RETCODE lpSetMarkowitz(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Real             threshhold,         /**< new MARKOWITZ value */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   assert(lp != NULL);
   assert(success != NULL);
 
   SCIP_CALL( lpCheckRealpar(lp, SCIP_LPPAR_MARKOWITZ, lp->lpimarkowitz) );
 
   if( threshhold != lp->lpimarkowitz )  /*lint !e777*/
   {
      SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_MARKOWITZ, threshhold, success) );
      if( *success )
         lp->lpimarkowitz = threshhold;
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the type of timer of the LP solver */
static
SCIP_RETCODE lpSetTiming(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_CLOCKTYPE        timing,             /**< new timing value */
   SCIP_Bool             enabled,            /**< is timing enabled? */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   int lptiming;
 
   assert(lp != NULL);
   assert(success != NULL);
   assert((int) SCIP_CLOCKTYPE_CPU == 1 && (int) SCIP_CLOCKTYPE_WALL == 2); /*lint !e506*//*lint !e1564*/
 
   SCIP_CALL( lpCheckIntpar(lp, SCIP_LPPAR_TIMING, lp->lpitiming) );
 
   if( !enabled )
      lptiming = 0;
   else
      lptiming = (int) timing;
 
   if( lptiming != lp->lpitiming )  /*lint !e777*/
   {
      SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_TIMING, lptiming, success) );
      if( *success )
         lp->lpitiming = lptiming;
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the initial random seed of the LP solver */
static
SCIP_RETCODE lpSetRandomseed(
   SCIP_LP*              lp,                 /**< current LP data */
   int                   randomseed,         /**< new initial random seed */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   assert(lp != NULL);
   assert(success != NULL);
 
   /* we don't check this parameter because SoPlex will always return its current random seed, not the initial one */
 
   if( randomseed == 0 )
   {
      lp->lpirandomseed = randomseed;
      *success = TRUE;
   }
   else if( randomseed != lp->lpirandomseed )  /*lint !e777*/
   {
      SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_RANDOMSEED, randomseed, success) );
      if( *success )
         lp->lpirandomseed = randomseed;
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the LP solution polishing method */
static
SCIP_RETCODE lpSetSolutionPolishing(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Bool             polishing,          /**< LP solution polishing activated (0: disabled, 1: enabled) */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   assert(lp != NULL);
   assert(success != NULL);
 
   if( polishing != lp->lpisolutionpolishing )
   {
      SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_POLISHING, (polishing ? 1 : 0), success) );
      if( *success )
         lp->lpisolutionpolishing = polishing;
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
/** sets the LP refactorization interval */
static
SCIP_RETCODE lpSetRefactorInterval(
   SCIP_LP*              lp,                 /**< current LP data */
   int                   refactor,           /**< LP refactorization interval (0: automatic) */
   SCIP_Bool*            success             /**< pointer to store whether the parameter was successfully changed */
   )
{
   assert(lp != NULL);
   assert(success != NULL);
 
   if( refactor != lp->lpirefactorinterval )
   {
      SCIP_CALL( lpSetIntpar(lp, SCIP_LPPAR_REFACTOR, refactor, success) );
      if( *success )
         lp->lpirefactorinterval = refactor;
   }
   else
      *success = FALSE;
 
   return SCIP_OKAY;
}
 
 
/*
 * Column methods
 */
 
/** creates an LP column */
SCIP_RETCODE SCIPcolCreate(
   SCIP_COL**            col,                /**< pointer to column data */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_STAT*            stat,               /**< problem statistics */
   SCIP_VAR*             var,                /**< variable, this column represents */
   int                   len,                /**< number of nonzeros in the column */
   SCIP_ROW**            rows,               /**< array with rows of column entries */
   SCIP_Real*            vals,               /**< array with coefficients of column entries */
   SCIP_Bool             removable           /**< should the column be removed from the LP due to aging or cleanup? */
   )
{
   int i;
 
   assert(col != NULL);
   assert(blkmem != NULL);
   assert(set != NULL);
   assert(stat != NULL);
   assert(var != NULL);
   assert(len >= 0);
   assert(len == 0 || (rows != NULL && vals != NULL));
 
   SCIP_ALLOC( BMSallocBlockMemory(blkmem, col) );
 
   if( len > 0 )
   {
      SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*col)->rows, rows, len) );
      SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*col)->vals, vals, len) );
      SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*col)->linkpos, len) );
 
      for( i = 0; i < len; ++i )
      {
         assert(rows[i] != NULL);
         assert(!SCIPsetIsZero(set, vals[i]));
         (*col)->linkpos[i] = -1;
      }
   }
   else
   {
      (*col)->rows = NULL;
      (*col)->vals = NULL;
      (*col)->linkpos = NULL;
   }
 
   (*col)->var = var;
   (*col)->obj = SCIPvarGetObj(var);
   (*col)->unchangedobj = SCIPvarGetUnchangedObj(var);
   (*col)->lb = SCIPvarGetLbLocal(var);
   (*col)->ub = SCIPvarGetUbLocal(var);
   (*col)->flushedobj = 0.0;
   (*col)->flushedlb = 0.0;
   (*col)->flushedub = 0.0;
   (*col)->index = stat->ncolidx;
   SCIPstatIncrement(stat, set, ncolidx);
   (*col)->size = len;
   (*col)->len = len;
   (*col)->nlprows = 0;
   (*col)->nunlinked = len;
   (*col)->lppos = -1;
   (*col)->lpipos = -1;
   (*col)->lpdepth = -1;
   (*col)->primsol = 0.0;
   (*col)->redcost = SCIP_INVALID;
   (*col)->farkascoef = SCIP_INVALID;
   (*col)->minprimsol = (*col)->ub;
   (*col)->maxprimsol = (*col)->lb;
   (*col)->sbdown = SCIP_INVALID;
   (*col)->sbup = SCIP_INVALID;
   (*col)->sbsolval  = SCIP_INVALID;
   (*col)->sblpobjval = SCIP_INVALID;
   (*col)->sbnode = -1;
   (*col)->validredcostlp = -1;
   (*col)->validfarkaslp = -1;
   (*col)->validsblp = -1;
   (*col)->sbitlim = -1;
   (*col)->nsbcalls = 0;
   (*col)->age = 0;
   (*col)->obsoletenode = -1;
   (*col)->var_probindex = SCIPvarGetProbindex(var);
   (*col)->basisstatus = SCIP_BASESTAT_ZERO; /*lint !e641*/
   (*col)->lprowssorted = TRUE;
   (*col)->nonlprowssorted = (len <= 1);
   (*col)->objchanged = FALSE;
   (*col)->lbchanged = FALSE;
   (*col)->ubchanged = FALSE;
   (*col)->coefchanged = FALSE;
   (*col)->integral = SCIPvarIsIntegral(var);
   (*col)->removable = removable;
   (*col)->sbdownvalid = FALSE;
   (*col)->sbupvalid = FALSE;
   (*col)->lazylb = SCIPvarGetLbLazy(var);
   (*col)->lazyub = SCIPvarGetUbLazy(var);
   (*col)->storedsolvals = NULL;
 
   return SCIP_OKAY;
}
 
/** frees an LP column */
SCIP_RETCODE SCIPcolFree(
   SCIP_COL**            col,                /**< pointer to LP column */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   assert(blkmem != NULL);
   assert(col != NULL);
   assert(*col != NULL);
   assert((*col)->var != NULL);
   assert(SCIPvarGetStatus((*col)->var) == SCIP_VARSTATUS_COLUMN);
   assert(&(*col)->var->data.col == col); /* SCIPcolFree() has to be called from SCIPvarFree() */
   assert((*col)->lppos == -1);
   assert((*col)->lpipos == -1);
 
   /* remove column indices from corresponding rows */
   SCIP_CALL( colUnlink(*col, blkmem, set, eventqueue, lp) );
 
   BMSfreeBlockMemoryNull(blkmem, &(*col)->storedsolvals);
   BMSfreeBlockMemoryArrayNull(blkmem, &(*col)->rows, (*col)->size);
   BMSfreeBlockMemoryArrayNull(blkmem, &(*col)->vals, (*col)->size);
   BMSfreeBlockMemoryArrayNull(blkmem, &(*col)->linkpos, (*col)->size);
   BMSfreeBlockMemory(blkmem, col);
 
   return SCIP_OKAY;
}
 
/** output column to file stream */
void SCIPcolPrint(
   SCIP_COL*             col,                /**< LP column */
   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
   FILE*                 file                /**< output file (or NULL for standard output) */
   )
{
   int r;
 
   assert(col != NULL);
   assert(col->var != NULL);
 
   /* print bounds */
   SCIPmessageFPrintInfo(messagehdlr, file, "(obj: %.15g) [%.15g,%.15g], ", col->obj, col->lb, col->ub);
 
   /* print coefficients */
   if( col->len == 0 )
      SCIPmessageFPrintInfo(messagehdlr, file, "<empty>");
   for( r = 0; r < col->len; ++r )
   {
      assert(col->rows[r] != NULL);
      assert(col->rows[r]->name != NULL);
      SCIPmessageFPrintInfo(messagehdlr, file, "%+.15g<%s> ", col->vals[r], col->rows[r]->name);
   }
   SCIPmessageFPrintInfo(messagehdlr, file, "\n");
}
 
/** sorts column entries such that LP rows precede non-LP rows and inside both parts lower row indices precede higher ones
 */
void SCIPcolSort(
   SCIP_COL*             col                 /**< column to be sorted */
   )
{
   /* sort LP rows */
   colSortLP(col);
 
   /* sort non-LP rows */
   colSortNonLP(col);
}
 
/** adds a previously non existing coefficient to an LP column */
SCIP_RETCODE SCIPcolAddCoef(
   SCIP_COL*             col,                /**< LP column */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_ROW*             row,                /**< LP row */
   SCIP_Real             val                 /**< value of coefficient */
   )
{
   assert(lp != NULL);
   assert(!lp->diving);
 
   SCIP_CALL( colAddCoef(col, blkmem, set, eventqueue, lp, row, val, -1) );
 
   checkLinks(lp);
 
   return SCIP_OKAY;
}
 
/** deletes existing coefficient from column */
SCIP_RETCODE SCIPcolDelCoef(
   SCIP_COL*             col,                /**< column to be changed */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_ROW*             row                 /**< coefficient to be deleted */
   )
{
   int pos;
 
   assert(col != NULL);
   assert(col->var != NULL);
   assert(lp != NULL);
   assert(!lp->diving);
   assert(row != NULL);
 
   /* search the position of the row in the column's row vector */
   pos = colSearchCoef(col, row);
   if( pos == -1 )
   {
      SCIPerrorMessage("coefficient for row <%s> doesn't exist in column <%s>\n", row->name, SCIPvarGetName(col->var));
      return SCIP_INVALIDDATA;
   }
   assert(0 <= pos && pos < col->len);
   assert(col->rows[pos] == row);
 
   /* if row knows of the column, remove the column from the row's col vector */
   if( col->linkpos[pos] >= 0 )
   {
      assert(row->cols[col->linkpos[pos]] == col);
      assert(row->cols_index[col->linkpos[pos]] == col->index);
      assert(SCIPsetIsEQ(set, row->vals[col->linkpos[pos]], col->vals[pos]));
      SCIP_CALL( rowDelCoefPos(row, blkmem, set, eventqueue, lp, col->linkpos[pos]) );
   }
 
   /* delete the row from the column's row vector */
   SCIP_CALL( colDelCoefPos(col, set, lp, pos) );
 
   checkLinks(lp);
 
   return SCIP_OKAY;
}
 
/** changes or adds a coefficient to an LP column */
SCIP_RETCODE SCIPcolChgCoef(
   SCIP_COL*             col,                /**< LP column */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_ROW*             row,                /**< LP row */
   SCIP_Real             val                 /**< value of coefficient */
   )
{
   int pos;
 
   assert(col != NULL);
   assert(lp != NULL);
   assert(!lp->diving);
   assert(row != NULL);
 
   /* search the position of the row in the column's row vector */
   pos = colSearchCoef(col, row);
 
   /* check, if row already exists in the column's row vector */
   if( pos == -1 )
   {
      /* add previously not existing coefficient */
      SCIP_CALL( colAddCoef(col, blkmem, set, eventqueue, lp, row, val, -1) );
   }
   else
   {
      /* modify already existing coefficient */
      assert(0 <= pos && pos < col->len);
      assert(col->rows[pos] == row);
 
      /* if row knows of the column, change the corresponding coefficient in the row */
      if( col->linkpos[pos] >= 0 )
      {
         assert(row->cols[col->linkpos[pos]] == col);
         assert(row->cols_index[col->linkpos[pos]] == col->index);
         assert(SCIPsetIsEQ(set, row->vals[col->linkpos[pos]], col->vals[pos]));
         SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, col->linkpos[pos], val) );
      }
 
      /* change the coefficient in the column */
      SCIP_CALL( colChgCoefPos(col, set, lp, pos, val) );
   }
 
   checkLinks(lp);
 
   return SCIP_OKAY;
}
 
/** increases value of an existing or non-existing coefficient in an LP column */
SCIP_RETCODE SCIPcolIncCoef(
   SCIP_COL*             col,                /**< LP column */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_ROW*             row,                /**< LP row */
   SCIP_Real             incval              /**< value to add to the coefficient */
   )
{
   int pos;
 
   assert(col != NULL);
   assert(lp != NULL);
   assert(!lp->diving);
   assert(row != NULL);
 
   if( SCIPsetIsZero(set, incval) )
      return SCIP_OKAY;
 
   /* search the position of the row in the column's row vector */
   pos = colSearchCoef(col, row);
 
   /* check, if row already exists in the column's row vector */
   if( pos == -1 )
   {
      /* add previously not existing coefficient */
      SCIP_CALL( colAddCoef(col, blkmem, set, eventqueue, lp, row, incval, -1) );
   }
   else
   {
      /* modify already existing coefficient */
      assert(0 <= pos && pos < col->len);
      assert(col->rows[pos] == row);
 
      /* if row knows of the column, change the corresponding coefficient in the row */
      if( col->linkpos[pos] >= 0 )
      {
         assert(row->cols[col->linkpos[pos]] == col);
         assert(row->cols_index[col->linkpos[pos]] == col->index);
         assert(SCIPsetIsEQ(set, row->vals[col->linkpos[pos]], col->vals[pos]));
         SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, col->linkpos[pos], col->vals[pos] + incval) );
      }
 
      /* change the coefficient in the column */
      SCIP_CALL( colChgCoefPos(col, set, lp, pos, col->vals[pos] + incval) );
   }
 
   checkLinks(lp);
 
   return SCIP_OKAY;
}
 
/** insert column in the chgcols list (if not already there) */
static
SCIP_RETCODE insertColChgcols(
   SCIP_COL*             col,                /**< LP column to change */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   if( !col->objchanged && !col->lbchanged && !col->ubchanged )
   {
      SCIP_CALL( ensureChgcolsSize(lp, set, lp->nchgcols+1) );
      lp->chgcols[lp->nchgcols] = col;
      lp->nchgcols++;
   }
 
   /* mark the current LP unflushed */
   lp->flushed = FALSE;
 
   return SCIP_OKAY;
}
 
/** Is the new value reliable or may we have cancellation?
 *
 *  @note: Here we only consider cancellations which can occur during decreasing the oldvalue to newvalue; not the
 *  cancellations which can occur during increasing the oldvalue to the newvalue
 */
static
SCIP_Bool isNewValueUnreliable(
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_Real             newvalue,           /**< new value */
   SCIP_Real             oldvalue            /**< old reliable value */
   )
{
   SCIP_Real quotient;
 
   assert(set != NULL);
   assert(oldvalue != SCIP_INVALID);  /*lint !e777*/
 
   quotient = (REALABS(newvalue)+1.0) / (REALABS(oldvalue) + 1.0);
 
   return SCIPsetIsZero(set, quotient);
}
 
/** update norms of objective function vector */
static
void lpUpdateObjNorms(
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_Real             oldobj,             /**< old objective value of variable */
   SCIP_Real             newobj              /**< new objective value of variable */
   )
{
   if( REALABS(newobj) != REALABS(oldobj) )   /*lint !e777*/
   {
      if( !lp->objsqrnormunreliable )
      {
         SCIP_Real oldvalue;
 
         oldvalue = lp->objsqrnorm;
         lp->objsqrnorm += SQR(newobj) - SQR(oldobj);
 
         /* due to numerical cancellations, we recalculate lp->objsqrnorm using all variables */
         if( SCIPsetIsLT(set, lp->objsqrnorm, 0.0) || isNewValueUnreliable(set, lp->objsqrnorm, oldvalue) )
            lp->objsqrnormunreliable = TRUE;
         else
         {
            assert(SCIPsetIsGE(set, lp->objsqrnorm, 0.0));
 
            /* due to numerical troubles it still can appear that lp->objsqrnorm is a little bit smaller than 0 */
            lp->objsqrnorm = MAX(lp->objsqrnorm, 0.0);
 
            assert(lp->objsqrnorm >= 0.0);
         }
      }
 
      lp->objsumnorm += REALABS(newobj) - REALABS(oldobj);
      lp->objsumnorm = MAX(lp->objsumnorm, 0.0);
   }
}
 
/** changes objective value of column */
SCIP_RETCODE SCIPcolChgObj(
   SCIP_COL*             col,                /**< LP column to change */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Real             newobj              /**< new objective value */
   )
{
   assert(col != NULL);
   assert(col->var != NULL);
   assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
   assert(SCIPvarGetCol(col->var) == col);
   assert(lp != NULL);
 
   SCIPsetDebugMsg(set, "changing objective value of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->obj, newobj);
 
   /* only add actual changes */
   if( !SCIPsetIsEQ(set, col->obj, newobj) )
   {
      /* only variables with a real position in the LPI can be inserted */
      if( col->lpipos >= 0 )
      {
         /* insert column in the chgcols list (if not already there) */
         SCIP_CALL( insertColChgcols(col, set, lp) );
 
         /* mark objective value change in the column */
         col->objchanged = TRUE;
 
         assert(lp->nchgcols > 0);
      }
      /* in any case, when the sign of the objective (and thereby the best bound) changes, the variable has to enter the
       * LP and the LP has to be flushed
       */
      else if( (col->obj < 0.0 && newobj >= 0.0 && SCIPsetIsZero(set, col->ub))
         || (col->obj >= 0.0 && newobj < 0.0 && SCIPsetIsZero(set, col->lb)) )
      {
         /* mark the LP unflushed */
         lp->flushed = FALSE;
      }
   }
 
   /* store new objective function value */
   col->obj = newobj;
 
   /* update original objective value, as long as we are not in diving or probing and changed objective values */
   if( !lp->divingobjchg )
   {
      SCIP_Real oldobj = col->unchangedobj;
 
      assert(SCIPsetIsEQ(set, newobj, SCIPvarGetUnchangedObj(col->var)));
      col->unchangedobj = newobj;
 
      /* update the objective function vector norms */
      lpUpdateObjNorms(lp, set, oldobj, newobj);
   }
 
   return SCIP_OKAY;
}
 
/** changes lower bound of column */
SCIP_RETCODE SCIPcolChgLb(
   SCIP_COL*             col,                /**< LP column to change */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Real             newlb               /**< new lower bound value */
   )
{
   assert(col != NULL);
   assert(col->var != NULL);
   assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
   assert(SCIPvarGetCol(col->var) == col);
   assert(lp != NULL);
 
   SCIPsetDebugMsg(set, "changing lower bound of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->lb, newlb);
 
   /* only add actual changes */
   if( !SCIPsetIsEQ(set, col->lb, newlb) )
   {
      /* only variables with a real position in the LPI can be inserted */
      if( col->lpipos >= 0 )
      {
         /* insert column in the chgcols list (if not already there) */
         SCIP_CALL( insertColChgcols(col, set, lp) );
 
         /* mark bound change in the column */
         col->lbchanged = TRUE;
 
         assert(lp->nchgcols > 0);
      }
      /* 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
       * flushed
       */
      else if( col->obj >= 0.0 && SCIPsetIsZero(set, col->lb) )
      {
         /* mark the LP unflushed */
         lp->flushed = FALSE;
      }
   }
 
   col->lb = newlb;
 
   return SCIP_OKAY;
}
 
/** changes upper bound of column */
SCIP_RETCODE SCIPcolChgUb(
   SCIP_COL*             col,                /**< LP column to change */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Real             newub               /**< new upper bound value */
   )
{
   assert(col != NULL);
   assert(col->var != NULL);
   assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
   assert(SCIPvarGetCol(col->var) == col);
   assert(lp != NULL);
 
   SCIPsetDebugMsg(set, "changing upper bound of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->ub, newub);
 
   /* only add actual changes */
   if( !SCIPsetIsEQ(set, col->ub, newub) )
   {
      /* only variables with a real position in the LPI can be inserted */
      if( col->lpipos >= 0 )
      {
         /* insert column in the chgcols list (if not already there) */
         SCIP_CALL( insertColChgcols(col, set, lp) );
 
         /* mark bound change in the column */
         col->ubchanged = TRUE;
 
         assert(lp->nchgcols > 0);
      }
      /* 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
       * flushed
       */
      else if( col->obj < 0.0 && SCIPsetIsZero(set, col->ub) )
      {
         /* mark the LP unflushed */
         lp->flushed = FALSE;
      }
   }
 
   col->ub = newub;
 
   return SCIP_OKAY;
}
 
/** calculates the reduced costs of a column using the given dual solution vector */
SCIP_Real SCIPcolCalcRedcost(
   SCIP_COL*             col,                /**< LP column */
   SCIP_Real*            dualsol             /**< dual solution vector for current LP rows */
   )
{
   SCIP_ROW* row;
   SCIP_Real redcost;
   int i;
 
   assert(col != NULL);
   assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
   assert(SCIPvarGetCol(col->var) == col);
   assert(dualsol != NULL);
 
   redcost = col->obj;
   for( i = 0; i < col->nlprows; ++i )
   {
      row = col->rows[i];
      assert(row != NULL);
      assert(row->lppos >= 0);
      redcost -= col->vals[i] * dualsol[row->lppos];
   }
 
   if( col->nunlinked > 0 )
   {
      for( i = col->nlprows; i < col->len; ++i )
      {
         row = col->rows[i];
         assert(row != NULL);
         assert(row->lppos == -1 || col->linkpos[i] == -1);
         if( row->lppos >= 0 )
            redcost -= col->vals[i] * dualsol[row->lppos];
      }
   }
#ifndef NDEBUG
   else
   {
      for( i = col->nlprows; i < col->len; ++i )
      {
         row = col->rows[i];
         assert(row != NULL);
         assert(row->lppos == -1);
         assert(col->linkpos[i] >= 0);
      }
   }
#endif
 
   return redcost;
}
 
/** calculates the reduced costs of a column using the dual solution stored in the rows */
static
SCIP_Real colCalcInternalRedcost(
   SCIP_COL*             col                 /**< LP column */
   )
{
   SCIP_ROW* row;
   SCIP_Real redcost;
   int i;
 
   assert(col != NULL);
   assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
   assert(SCIPvarGetCol(col->var) == col);
 
   redcost = col->obj;
   for( i = 0; i < col->nlprows; ++i )
   {
      row = col->rows[i];
      assert(row != NULL);
      assert(row->dualsol != SCIP_INVALID);  /*lint !e777*/
      assert(row->lppos >= 0);
      assert(col->linkpos[i] >= 0);
      redcost -= col->vals[i] * row->dualsol;
   }
 
   if( col->nunlinked > 0 )
   {
      for( i = col->nlprows; i < col->len; ++i )
      {
         row = col->rows[i];
         assert(row != NULL);
         assert(row->lppos >= 0 || row->dualsol == 0.0);
         assert(row->lppos == -1 || col->linkpos[i] == -1);
         if( row->lppos >= 0 )
            redcost -= col->vals[i] * row->dualsol;
      }
   }
#ifndef NDEBUG
   else
   {
      for( i = col->nlprows; i < col->len; ++i )
      {
         row = col->rows[i];
         assert(row != NULL);
         assert(row->dualsol == 0.0);
         assert(row->lppos == -1);
         assert(col->linkpos[i] >= 0);
      }
   }
#endif
 
   return redcost;
}
 
/** gets the reduced costs of a column in last LP or after recalculation */
SCIP_Real SCIPcolGetRedcost(
   SCIP_COL*             col,                /**< LP column */
   SCIP_STAT*            stat,               /**< problem statistics */
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   assert(col != NULL);
   assert(stat != NULL);
   assert(lp != NULL);
   assert(col->validredcostlp <= stat->lpcount);
   assert(lp->validsollp == stat->lpcount);
 
   if( col->validredcostlp < stat->lpcount )
   {
      col->redcost = colCalcInternalRedcost(col);
      col->validredcostlp = stat->lpcount;
   }
   assert(col->validredcostlp == stat->lpcount);
   assert(col->redcost != SCIP_INVALID);  /*lint !e777*/
 
   return col->redcost;
}
 
/** gets the feasibility of (the dual row of) a column in last LP or after recalculation */
SCIP_Real SCIPcolGetFeasibility(
   SCIP_COL*             col,                /**< LP column */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_STAT*            stat,               /**< problem statistics */
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   assert(col != NULL);
   assert(set != NULL);
   assert(stat != NULL);
   assert(lp != NULL);
   assert(lp->validsollp == stat->lpcount);
 
   /* A column's reduced cost is defined as
    *   redcost  = obj - activity,  activity = y^T * col.   (activity = obj - redcost)
    * The activity is equal to the activity of the corresponding row in the dual LP.
    * The column's feasibility is the feasibility of the corresponding row in the dual LP.
    * The sides of the dual row depend on the bounds of the column:
    *  - lb == ub      :  dual row is a free row with infinite sides
    *  -  0 <= lb <  ub:         activity <= obj  =>  0 <= redcost
    *  - lb <   0 <  ub:  obj <= activity <= obj  =>  0 <= redcost <= 0
    *  - lb <  ub <=  0:  obj <= activity         =>       redcost <= 0
    */
   if( SCIPsetIsEQ(set, col->lb, col->ub) )
   {
      /* dual row is free */
      return SCIPsetInfinity(set);
   }
   else
   {
      SCIP_Real redcost;
 
      /* calculate reduced costs */
      redcost = SCIPcolGetRedcost(col, stat, lp);
 
      if( !SCIPsetIsNegative(set, col->lb) )
      {
         /* dual row is  activity <= obj  <=>  redcost >= 0 */
         return redcost;
      }
      else if( SCIPsetIsPositive(set, col->ub) )
      {
         /* dual row is  activity == obj  <=>  redcost == 0 */
         return -REALABS(redcost);
      }
      else
      {
         /* dual row is  activity >= obj  <=>  redcost <= 0 */
         return -redcost;
      }
   }
}
 
/** calculates the Farkas coefficient y^T A_i of a column i using the given dual Farkas vector y */
SCIP_Real SCIPcolCalcFarkasCoef(
   SCIP_COL*             col,                /**< LP column */
   SCIP_Real*            dualfarkas          /**< dense dual Farkas vector for current LP rows */
   )
{
   SCIP_ROW* row;
   SCIP_Real farkas;
   int i;
 
   assert(col != NULL);
   assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
   assert(SCIPvarGetCol(col->var) == col);
   assert(dualfarkas != NULL);
 
   farkas = 0.0;
   for( i = 0; i < col->nlprows; ++i )
   {
      row = col->rows[i];
      assert(row != NULL);
      assert(row->lppos >= 0);
      farkas += col->vals[i] * dualfarkas[row->lppos];
   }
 
   if( col->nunlinked > 0 )
   {
      for( i = col->nlprows; i < col->len; ++i )
      {
         row = col->rows[i];
         assert(row != NULL);
         assert(row->lppos == -1 || col->linkpos[i] == -1);
         if( row->lppos >= 0 )
            farkas += col->vals[i] * dualfarkas[row->lppos];
      }
   }
#ifndef NDEBUG
   else
   {
      for( i = col->nlprows; i < col->len; ++i )
      {
         row = col->rows[i];
         assert(row != NULL);
         assert(row->lppos == -1);
         assert(col->linkpos[i] >= 0);
      }
   }
#endif
 
   return farkas;
}
 
/** gets the Farkas coefficient y^T A_i of a column i in last LP (which must be infeasible) */
static
SCIP_Real colCalcInternalFarkasCoef(
   SCIP_COL*             col                 /**< LP column */
   )
{
   SCIP_ROW* row;
   SCIP_Real farkas;
   int i;
 
   assert(col != NULL);
   assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
   assert(SCIPvarGetCol(col->var) == col);
 
   farkas = 0.0;
   for( i = 0; i < col->nlprows; ++i )
   {
      row = col->rows[i];
      assert(row != NULL);
      assert(row->dualfarkas != SCIP_INVALID);  /*lint !e777*/
      assert(row->lppos >= 0);
      assert(col->linkpos[i] >= 0);
      farkas += col->vals[i] * row->dualfarkas;
   }
 
   if( col->nunlinked > 0 )
   {
      for( i = col->nlprows; i < col->len; ++i )
      {
         row = col->rows[i];
         assert(row != NULL);
         assert(row->lppos >= 0 || row->dualfarkas == 0.0);
         assert(row->lppos == -1 || col->linkpos[i] == -1);
         if( row->lppos >= 0 )
            farkas += col->vals[i] * row->dualfarkas;
      }
   }
#ifndef NDEBUG
   else
   {
      for( i = col->nlprows; i < col->len; ++i )
      {
         row = col->rows[i];
         assert(row != NULL);
         assert(row->dualfarkas == 0.0);
         assert(row->lppos == -1);
         assert(col->linkpos[i] >= 0);
      }
   }
#endif
 
   return farkas;
}
 
/** gets the Farkas coefficient of a column in last LP (which must be infeasible) */
SCIP_Real SCIPcolGetFarkasCoef(
   SCIP_COL*             col,                /**< LP column */
   SCIP_STAT*            stat,               /**< problem statistics */
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   assert(col != NULL);
   assert(stat != NULL);
   assert(lp != NULL);
   assert(col->validfarkaslp <= stat->lpcount);
   assert(lp->validfarkaslp == stat->lpcount);
 
   if( col->validfarkaslp < stat->lpcount )
   {
      col->farkascoef = colCalcInternalFarkasCoef(col);
      col->validfarkaslp = stat->lpcount;
   }
   assert(col->validfarkaslp == stat->lpcount);
   assert(col->farkascoef != SCIP_INVALID);  /*lint !e777*/
 
   return col->farkascoef;
}
 
/** gets the Farkas value of a column in last LP (which must be infeasible), i.e. the Farkas coefficient y^T A_i times
 *  the best bound for this coefficient, i.e. max{y^T A_i x_i | lb <= x_i <= ub}
 */
SCIP_Real SCIPcolGetFarkasValue(
   SCIP_COL*             col,                /**< LP column */
   SCIP_STAT*            stat,               /**< problem statistics */
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   SCIP_Real farkascoef;
 
   assert(col != NULL);
 
   farkascoef = SCIPcolGetFarkasCoef(col, stat, lp);
 
   if( farkascoef > 0.0 )
      return col->ub * farkascoef;
   else
      return col->lb * farkascoef;
}
 
/** start strong branching - call before any strong branching */
SCIP_RETCODE SCIPlpStartStrongbranch(
   SCIP_LP*              lp                  /**< LP data */
   )
{
   assert(lp != NULL);
   assert(!lp->strongbranching);
 
   lp->strongbranching = TRUE;
   SCIPdebugMessage("starting strong branching ...\n");
   SCIP_CALL( SCIPlpiStartStrongbranch(lp->lpi) );
 
   return SCIP_OKAY;
}
 
/** end strong branching - call after any strong branching */
SCIP_RETCODE SCIPlpEndStrongbranch(
   SCIP_LP*              lp                  /**< LP data */
   )
{
   assert(lp != NULL);
   assert(lp->strongbranching);
 
   lp->strongbranching = FALSE;
   SCIPdebugMessage("ending strong branching ...\n");
   SCIP_CALL( SCIPlpiEndStrongbranch(lp->lpi) );
 
   return SCIP_OKAY;
}
 
/** sets strong branching information for a column variable */
void SCIPcolSetStrongbranchData(
   SCIP_COL*             col,                /**< LP column */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_STAT*            stat,               /**< dynamic problem statistics */
   SCIP_LP*              lp,                 /**< LP data */
   SCIP_Real             lpobjval,           /**< objective value of the current LP */
   SCIP_Real             primsol,            /**< primal solution value of the column in the current LP */
   SCIP_Real             sbdown,             /**< dual bound after branching column down */
   SCIP_Real             sbup,               /**< dual bound after branching column up */
   SCIP_Bool             sbdownvalid,        /**< is the returned down value a valid dual bound? */
   SCIP_Bool             sbupvalid,          /**< is the returned up value a valid dual bound? */
   SCIP_Longint          iter,               /**< total number of strong branching iterations */
   int                   itlim               /**< iteration limit applied to the strong branching call */
   )
{
   assert(col != NULL);
   assert(col->var != NULL);
   assert(SCIPcolIsIntegral(col));
   assert(SCIPvarIsIntegral(col->var));
   assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
   assert(SCIPvarGetCol(col->var) == col);
   assert(col->lpipos >= 0);
   assert(col->lppos >= 0);
   assert(set != NULL);
   assert(stat != NULL);
   assert(lp != NULL);
   assert(lp->strongbranchprobing);
   assert(col->lppos < lp->ncols);
   assert(lp->cols[col->lppos] == col);
   assert(itlim >= 1);
 
   col->sblpobjval = lpobjval;
   col->sbsolval = primsol;
   col->validsblp = stat->nlps;
   col->sbnode = stat->nnodes;
 
   col->sbitlim = itlim;
   col->nsbcalls++;
 
   col->sbdown = MIN(sbdown, lp->cutoffbound);
   col->sbup = MIN(sbup, lp->cutoffbound);
   col->sbdownvalid = sbdownvalid;
   col->sbupvalid = sbupvalid;
 
   SCIPstatIncrement(stat, set, nstrongbranchs);
   SCIPstatAdd(stat, set, nsblpiterations, iter);
   if( stat->nnodes == 1 )
   {
      SCIPstatIncrement(stat, set, nrootstrongbranchs);
      SCIPstatAdd(stat, set, nrootsblpiterations, iter);
   }
}
 
/** invalidates strong branching information for a column variable */
void SCIPcolInvalidateStrongbranchData(
   SCIP_COL*             col,                /**< LP column */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_STAT*            stat,               /**< dynamic problem statistics */
   SCIP_LP*              lp                  /**< LP data */
   )
{
   assert(col != NULL);
   assert(col->var != NULL);
   assert(SCIPcolIsIntegral(col));
   assert(SCIPvarIsIntegral(col->var));
   assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
   assert(SCIPvarGetCol(col->var) == col);
   assert(col->lpipos >= 0);
   assert(col->lppos >= 0);
   assert(set != NULL);
   assert(stat != NULL);
   assert(lp != NULL);
   assert(lp->strongbranchprobing);
   assert(col->lppos < lp->ncols);
   assert(lp->cols[col->lppos] == col);
 
   col->sbdown = SCIP_INVALID;
   col->sbup = SCIP_INVALID;
   col->sbdownvalid = FALSE;
   col->sbupvalid = FALSE;
   col->validsblp = -1;
   col->sbsolval = SCIP_INVALID;
   col->sblpobjval = SCIP_INVALID;
   col->sbnode = -1;
   col->sbitlim = -1;
}
 
 
/** gets strong branching information on a column variable */
SCIP_RETCODE SCIPcolGetStrongbranch(
   SCIP_COL*             col,                /**< LP column */
   SCIP_Bool             integral,           /**< should integral strong branching be performed? */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_STAT*            stat,               /**< dynamic problem statistics */
   SCIP_PROB*            prob,               /**< problem data */
   SCIP_LP*              lp,                 /**< LP data */
   int                   itlim,              /**< iteration limit for strong branchings */
   SCIP_Bool             updatecol,          /**< should col be updated, or should it stay in its current state ? */
   SCIP_Bool             updatestat,         /**< should stat be updated, or should it stay in its current state ? */
   SCIP_Real*            down,               /**< stores dual bound after branching column down */
   SCIP_Real*            up,                 /**< stores dual bound after branching column up */
   SCIP_Bool*            downvalid,          /**< stores whether the returned down value is a valid dual bound, or NULL;
                                              *   otherwise, it can only be used as an estimate value */
   SCIP_Bool*            upvalid,            /**< stores whether the returned up value is a valid dual bound, or NULL;
                                              *   otherwise, it can only be used as an estimate value */
   SCIP_Bool*            lperror             /**< pointer to store whether an unresolved LP error occurred */
   )
{
   SCIP_Real sbdown;
   SCIP_Real sbup;
   SCIP_Bool sbdownvalid;
   SCIP_Bool sbupvalid;
   SCIP_Longint validsblp;
   SCIP_Real sbsolval;
   SCIP_Real sblpobjval;
   SCIP_Longint sbnode;
   int sbitlim;
   int nsbcalls;
 
   assert(col != NULL);
   assert(col->var != NULL);
   assert(SCIPcolIsIntegral(col));
   assert(SCIPvarIsIntegral(col->var));
   assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
   assert(SCIPvarGetCol(col->var) == col);
   assert(col->primsol != SCIP_INVALID);  /*lint !e777*/
   assert(col->lpipos >= 0);
   assert(col->lppos >= 0);
   assert(set != NULL);
   assert(stat != NULL);
   assert(lp != NULL);
   assert(lp->flushed);
   assert(lp->solved);
   assert(lp->strongbranching);
   assert(lp->lpsolstat == SCIP_LPSOLSTAT_OPTIMAL);
   assert(lp->validsollp == stat->lpcount);
   assert(col->lppos < lp->ncols);
   assert(lp->cols[col->lppos] == col);
   assert(itlim >= 1);
   /*   assert(down != NULL);
    *  assert(up != NULL); temporary hack for cloud branching
    */
   assert(lperror != NULL);
 
   *lperror = FALSE;
 
   sbdown = col->sbdown;
   sbup = col->sbup;
   sbdownvalid = col->sbdownvalid;
   sbupvalid = col->sbupvalid;
   sbitlim = col->sbitlim;
   nsbcalls = col->nsbcalls;
 
   validsblp = stat->nlps;
   sbsolval = col->primsol;
   sblpobjval = SCIPlpGetObjval(lp, set, prob);
   sbnode = stat->nnodes;
   assert(integral || !SCIPsetIsFeasIntegral(set, col->primsol));
 
   /* if a loose variables has an infinite best bound, the LP bound is -infinity and no gain can be achieved */
   if( lp->looseobjvalinf > 0 )
   {
      sbdown = -SCIPsetInfinity(set);
      sbup = -SCIPsetInfinity(set);
      sbdownvalid = FALSE;
      sbupvalid = FALSE;
   }
   else
   {
      SCIP_RETCODE retcode;
      int iter;
 
      SCIPsetDebugMsg(set, "performing strong branching on variable <%s>(%g) with %d iterations\n",
         SCIPvarGetName(col->var), col->primsol, itlim);
 
      /* start timing */
      SCIPclockStart(stat->strongbranchtime, set);
 
      /* call LPI strong branching */
      sbitlim = itlim;
      nsbcalls++;
 
      sbdown = lp->lpobjval;
      sbup = lp->lpobjval;
 
      if( integral )
         retcode = SCIPlpiStrongbranchInt(lp->lpi, col->lpipos, col->primsol, itlim, down  == NULL ? NULL : &sbdown, up  == NULL ? NULL : &sbup, &sbdownvalid, &sbupvalid, &iter);
      else
      {
         assert( ! SCIPsetIsIntegral(set, col->primsol) );
         retcode = SCIPlpiStrongbranchFrac(lp->lpi, col->lpipos, col->primsol, itlim, down == NULL ? NULL : &sbdown, up == NULL ? NULL :  &sbup, &sbdownvalid, &sbupvalid, &iter);
      }
 
      /* check return code for errors */
      if( retcode == SCIP_LPERROR )
      {
         *lperror = TRUE;
         sbdown = SCIP_INVALID;
         sbup = SCIP_INVALID;
         sbdownvalid = FALSE;
         sbupvalid = FALSE;
         validsblp = -1;
         sbsolval = SCIP_INVALID;
         sblpobjval = SCIP_INVALID;
         sbnode = -1;
      }
      else
      {
         SCIP_Real looseobjval;
 
         *lperror = FALSE;
         SCIP_CALL( retcode );
 
         looseobjval = getFiniteLooseObjval(lp, set, prob);
         sbdown = MIN(sbdown + looseobjval, lp->cutoffbound);
         sbup = MIN(sbup + looseobjval, lp->cutoffbound);
 
         /* update strong branching statistics */
         if( updatestat )
         {
            if( iter == -1 )
            {
               /* calculate average iteration number */
               iter = stat->ndualresolvelps > 0 ? (int)(2*stat->ndualresolvelpiterations / stat->ndualresolvelps)
                  : stat->nduallps > 0 ? (int)((stat->nduallpiterations / stat->nduallps) / 5)
                  : stat->nprimalresolvelps > 0 ? (int)(2*stat->nprimalresolvelpiterations / stat->nprimalresolvelps)
                  : stat->nprimallps > 0 ? (int)((stat->nprimallpiterations / stat->nprimallps) / 5)
                  : 0;
               if( iter/2 >= itlim )
                  iter = 2*itlim;
            }
            SCIPstatIncrement(stat, set, nstrongbranchs);
            SCIPstatAdd(stat, set, nsblpiterations, iter);
            if( stat->nnodes == 1 )
            {
               SCIPstatIncrement(stat, set, nrootstrongbranchs);
               SCIPstatAdd(stat, set, nrootsblpiterations, iter);
            }
         }
      }
 
      /* stop timing */
      SCIPclockStop(stat->strongbranchtime, set);
   }
   assert(*lperror || sbdown != SCIP_INVALID);  /*lint !e777*/
   assert(*lperror || sbup != SCIP_INVALID);  /*lint !e777*/
 
   if( down != NULL)
      *down = sbdown;
   if( up != NULL )
      *up = sbup;
   if( downvalid != NULL )
      *downvalid = sbdownvalid;
   if( upvalid != NULL )
      *upvalid = sbupvalid;
 
   if( updatecol )
   {
      col->sbdown = sbdown;
      col->sbup = sbup;
      col->sbdownvalid = sbdownvalid;
      col->sbupvalid = sbupvalid;
      col->validsblp = validsblp;
      col->sbsolval = sbsolval;
      col->sblpobjval = sblpobjval;
      col->sbnode = sbnode;
      col->sbitlim = sbitlim;
      col->nsbcalls = nsbcalls;
   }
 
   return SCIP_OKAY;
}
 
/** gets strong branching information on column variables */
SCIP_RETCODE SCIPcolGetStrongbranches(
   SCIP_COL**            cols,               /**< LP columns */
   int                   ncols,              /**< number of columns */
   SCIP_Bool             integral,           /**< should integral strong branching be performed? */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_STAT*            stat,               /**< dynamic problem statistics */
   SCIP_PROB*            prob,               /**< problem data */
   SCIP_LP*              lp,                 /**< LP data */
   int                   itlim,              /**< iteration limit for strong branchings */
   SCIP_Real*            down,               /**< stores dual bounds after branching columns down */
   SCIP_Real*            up,                 /**< stores dual bounds after branching columns up */
   SCIP_Bool*            downvalid,          /**< stores whether the returned down values are valid dual bounds, or NULL;
                                              *   otherwise, they can only be used as an estimate value */
   SCIP_Bool*            upvalid,            /**< stores whether the returned up values are valid dual bounds, or NULL;
                                              *   otherwise, they can only be used as an estimate value */
   SCIP_Bool*            lperror             /**< pointer to store whether an unresolved LP error occurred */
   )
{
   SCIP_RETCODE retcode;
   SCIP_Real* sbdown;
   SCIP_Real* sbup;
   SCIP_Bool* sbdownvalid;
   SCIP_Bool* sbupvalid;
   SCIP_Real* primsols;
   SCIP_COL** subcols;
   int* lpipos;
   int* subidx;
   int nsubcols;
   int iter;
   int j;
 
   assert(cols != NULL);
   assert(set != NULL);
   assert(stat != NULL);
   assert(lp != NULL);
   assert(lp->flushed);
   assert(lp->solved);
   assert(lp->lpsolstat == SCIP_LPSOLSTAT_OPTIMAL);
   assert(lp->validsollp == stat->lpcount);
   assert(itlim >= 1);
   assert(down != NULL);
   assert(up != NULL);
   assert(lperror != NULL);
 
   *lperror = FALSE;
 
   if ( ncols <= 0 )
      return SCIP_OKAY;
 
   /* start timing */
   SCIPclockStart(stat->strongbranchtime, set);
 
   /* initialize storage */
   SCIP_CALL( SCIPsetAllocBufferArray(set, &subcols, ncols) );
   SCIP_CALL( SCIPsetAllocBufferArray(set, &subidx, ncols) );
   SCIP_CALL( SCIPsetAllocBufferArray(set, &lpipos, ncols) );
   SCIP_CALL( SCIPsetAllocBufferArray(set, &primsols, ncols) );
   SCIP_CALL( SCIPsetAllocBufferArray(set, &sbdown, ncols) );
   SCIP_CALL( SCIPsetAllocBufferArray(set, &sbup, ncols) );
   SCIP_CALL( SCIPsetAllocBufferArray(set, &sbdownvalid, ncols) );
   SCIP_CALL( SCIPsetAllocBufferArray(set, &sbupvalid, ncols) );
 
   nsubcols = 0;
   for( j = 0; j < ncols; ++j )
   {
      SCIP_COL* col;
      col = cols[j];
 
      assert(col->lppos < lp->ncols);
      assert(lp->cols[col->lppos] == col);
      assert(SCIPcolIsIntegral(col));
      assert(SCIPvarIsIntegral(col->var));
      assert(SCIPvarGetStatus(col->var) == SCIP_VARSTATUS_COLUMN);
      assert(SCIPvarGetCol(col->var) == col);
      assert(col->primsol != SCIP_INVALID);  /*lint !e777*/
      assert(col->lpipos >= 0);
      assert(col->lppos >= 0);
 
      col->validsblp = stat->nlps;
      col->sbsolval = col->primsol;
      col->sblpobjval = SCIPlpGetObjval(lp, set, prob);
      col->sbnode = stat->nnodes;
      assert(!SCIPsetIsFeasIntegral(set, col->primsol));
 
      /* if a loose variables has an infinite best bound, the LP bound is -infinity and no gain can be achieved */
      if( lp->looseobjvalinf > 0 )
      {
         /* directly set up column and result vectors*/
         col->sbdown = -SCIPsetInfinity(set);
         col->sbup = -SCIPsetInfinity(set);
         col->sbdownvalid = FALSE;
         col->sbupvalid = FALSE;
         down[j] = col->sbdown;
         up[j] = col->sbup;
         if( downvalid != NULL )
            downvalid[j] = col->sbdownvalid;
         if( upvalid != NULL )
            upvalid[j] = col->sbupvalid;
      }
      else
      {
         col->sbitlim = itlim;
         col->nsbcalls++;
 
         lpipos[nsubcols] = col->lpipos;
         primsols[nsubcols] = col->primsol;
         assert( integral || ! SCIPsetIsFeasIntegral(set, col->primsol) );
         subidx[nsubcols] = j;
         subcols[nsubcols++] = col;
      }
   }
 
   SCIPsetDebugMsg(set, "performing strong branching on %d variables with %d iterations\n", ncols, itlim);
 
   /* call LPI strong branching */
   if ( integral )
      retcode = SCIPlpiStrongbranchesInt(lp->lpi, lpipos, nsubcols, primsols, itlim, sbdown, sbup, sbdownvalid, sbupvalid, &iter);
   else
      retcode = SCIPlpiStrongbranchesFrac(lp->lpi, lpipos, nsubcols, primsols, itlim, sbdown, sbup, sbdownvalid, sbupvalid, &iter);
 
   /* check return code for errors */
   if( retcode == SCIP_LPERROR )
   {
      *lperror = TRUE;
 
      for( j = 0; j < nsubcols; ++j )
      {
         SCIP_COL* col;
         int idx;
 
         col = subcols[j];
         idx = subidx[j];
 
         col->sbdown = SCIP_INVALID;
         col->sbup = SCIP_INVALID;
         col->sbdownvalid = FALSE;
         col->sbupvalid = FALSE;
         col->validsblp = -1;
         col->sbsolval = SCIP_INVALID;
         col->sblpobjval = SCIP_INVALID;
         col->sbnode = -1;
 
         down[idx] = col->sbdown;
         up[idx] = col->sbup;
         if( downvalid != NULL )
            downvalid[idx] = col->sbdownvalid;
         if( upvalid != NULL )
            upvalid[idx] = col->sbupvalid;
      }
   }
   else
   {
      SCIP_Real looseobjval;
 
      *lperror = FALSE;
      SCIP_CALL( retcode );
 
      looseobjval = getFiniteLooseObjval(lp, set, prob);
 
      for( j = 0; j < nsubcols; ++j )
      {
         SCIP_COL* col;
         int idx;
 
         col = subcols[j];
         idx = subidx[j];
 
         assert( col->sbdown != SCIP_INVALID);  /*lint !e777*/
         assert( col->sbup != SCIP_INVALID);  /*lint !e777*/
 
         col->sbdown = MIN(sbdown[j] + looseobjval, lp->cutoffbound);
         col->sbup = MIN(sbup[j] + looseobjval, lp->cutoffbound);
         col->sbdownvalid = sbdownvalid[j];
         col->sbupvalid = sbupvalid[j];
 
         down[idx] = col->sbdown;
         up[idx] = col->sbup;
         if( downvalid != NULL )
            downvalid[idx] = col->sbdownvalid;
         if( upvalid != NULL )
            upvalid[idx] = col->sbupvalid;
      }
 
      /* update strong branching statistics */
      if( iter == -1 )
      {
         /* calculate average iteration number */
         iter = stat->ndualresolvelps > 0 ? (int)(2*stat->ndualresolvelpiterations / stat->ndualresolvelps)
            : stat->nduallps > 0 ? (int)((stat->nduallpiterations / stat->nduallps) / 5)
            : stat->nprimalresolvelps > 0 ? (int)(2*stat->nprimalresolvelpiterations / stat->nprimalresolvelps)
            : stat->nprimallps > 0 ? (int)((stat->nprimallpiterations / stat->nprimallps) / 5)
            : 0;
         if( iter/2 >= itlim )
            iter = 2*itlim;
      }
      SCIPstatAdd(stat, set, nstrongbranchs, ncols);
      SCIPstatAdd(stat, set, nsblpiterations, iter);
      if( stat->nnodes == 1 )
      {
         SCIPstatAdd(stat, set, nrootstrongbranchs, ncols);
         SCIPstatAdd(stat, set, nrootsblpiterations, iter);
      }
   }
 
   SCIPsetFreeBufferArray(set, &sbupvalid);
   SCIPsetFreeBufferArray(set, &sbdownvalid);
   SCIPsetFreeBufferArray(set, &sbup);
   SCIPsetFreeBufferArray(set, &sbdown);
   SCIPsetFreeBufferArray(set, &primsols);
   SCIPsetFreeBufferArray(set, &lpipos);
   SCIPsetFreeBufferArray(set, &subidx);
   SCIPsetFreeBufferArray(set, &subcols);
 
   /* stop timing */
   SCIPclockStop(stat->strongbranchtime, set);
 
   return SCIP_OKAY;
}
 
/** gets last strong branching information available for a column variable;
 *  returns values of SCIP_INVALID, if strong branching was not yet called on the given column;
 *  keep in mind, that the returned old values may have nothing to do with the current LP solution
 */
void SCIPcolGetStrongbranchLast(
   SCIP_COL*             col,                /**< LP column */
   SCIP_Real*            down,               /**< stores dual bound after branching column down, or NULL */
   SCIP_Real*            up,                 /**< stores dual bound after branching column up, or NULL */
   SCIP_Bool*            downvalid,          /**< stores whether the returned down value is a valid dual bound, or NULL;
                                              *   otherwise, it can only be used as an estimate value */
   SCIP_Bool*            upvalid,            /**< stores whether the returned up value is a valid dual bound, or NULL;
                                              *   otherwise, it can only be used as an estimate value */
   SCIP_Real*            solval,             /**< stores LP solution value of column at last strong branching call, or NULL */
   SCIP_Real*            lpobjval            /**< stores LP objective value at last strong branching call, or NULL */
   )
{
   assert(col != NULL);
 
   if( down != NULL )
      *down = col->sbdown;
   if( up != NULL )
      *up = col->sbup;
   if( downvalid != NULL )
      *downvalid = col->sbdownvalid;
   if( upvalid != NULL )
      *upvalid = col->sbupvalid;
   if( solval != NULL )
      *solval = col->sbsolval;
   if( lpobjval != NULL )
      *lpobjval = col->sblpobjval;
}
 
/** if strong branching was already applied on the column at the current node, returns the number of LPs solved after
 *  the LP where the strong branching on this column was applied;
 *  if strong branching was not yet applied on the column at the current node, returns INT_MAX
 */
SCIP_Longint SCIPcolGetStrongbranchLPAge(
   SCIP_COL*             col,                /**< LP column */
   SCIP_STAT*            stat                /**< dynamic problem statistics */
   )
{
   assert(col != NULL);
   assert(stat != NULL);
 
   return (col->sbnode != stat->nnodes ? SCIP_LONGINT_MAX : stat->nlps - col->validsblp);
}
 
/** marks a column to be not removable from the LP in the current node because it became obsolete */
void SCIPcolMarkNotRemovableLocal(
   SCIP_COL*             col,                /**< LP column */
   SCIP_STAT*            stat                /**< problem statistics */
   )
{
   assert(col  != NULL);
   assert(stat != NULL);
   assert(stat->nnodes > 0);
 
   /* lpRemoveObsoleteCols() does not remove a column if the node number stored in obsoletenode equals the current node number */
   col->obsoletenode = stat->nnodes;
}
 
 
/*
 * Row methods
 */
 
/** calculates row norms and min/maxidx from scratch, and checks for sorting */
static
void rowCalcNorms(
   SCIP_ROW*             row,                /**< LP row */
   SCIP_SET*             set                 /**< global SCIP settings */
   )
{
   int i;
 
   assert(row != NULL);
   assert(set != NULL);
 
   row->sqrnorm = 0.0;
   row->sumnorm = 0.0;
   row->objprod = 0.0;
   row->maxval = 0.0;
   row->nummaxval = 1;
   row->minval = SCIPsetInfinity(set);
   row->numminval = 1;
   row->minidx = INT_MAX;
   row->maxidx = INT_MIN;
   row->validminmaxidx = TRUE;
   row->lpcolssorted = TRUE;
   row->nonlpcolssorted = TRUE;
 
   /* check, if row is sorted
    * calculate sqrnorm, sumnorm, maxval, minval, minidx, and maxidx
    */
   for( i = 0; i < row->nlpcols; ++i )
   {
      assert(row->cols[i] != NULL);
      assert(!SCIPsetIsZero(set, row->vals[i]));
      assert(row->cols[i]->lppos >= 0);
      assert(row->linkpos[i] >= 0);
      assert(row->cols[i]->index == row->cols_index[i]);
 
      rowAddNorms(row, set, row->cols[i], row->vals[i], TRUE);
      if( i > 0 )
      {
         assert(row->cols[i-1]->index == row->cols_index[i-1]);
         row->lpcolssorted = row->lpcolssorted && (row->cols_index[i-1] < row->cols_index[i]);
      }
   }
   for( i = row->nlpcols; i < row->len; ++i )
   {
      assert(row->cols[i] != NULL);
      assert(!SCIPsetIsZero(set, row->vals[i]));
      assert(row->cols[i]->lppos == -1 || row->linkpos[i] == -1);
      assert(row->cols[i]->index == row->cols_index[i]);
 
      rowAddNorms(row, set, row->cols[i], row->vals[i], TRUE);
      if( i > row->nlpcols )
      {
         assert(row->cols[i-1]->index == row->cols_index[i-1]);
         row->nonlpcolssorted = row->nonlpcolssorted && (row->cols_index[i-1] < row->cols_index[i]);
      }
   }
}
 
/** calculates min/maxval and min/maxidx from scratch */
static
void rowCalcIdxsAndVals(
   SCIP_ROW*             row,                /**< LP row */
   SCIP_SET*             set                 /**< global SCIP settings */
   )
{
   SCIP_COL* col;
   SCIP_Real absval;
   int i;
 
   assert(row != NULL);
   assert(set != NULL);
 
   row->maxval = 0.0;
   row->nummaxval = 1;
   row->numintcols = 0;
   row->minval = SCIPsetInfinity(set);
   row->numminval = 1;
   row->minidx = INT_MAX;
   row->maxidx = INT_MIN;
   row->validminmaxidx = TRUE;
 
   /* calculate maxval, minval, minidx, and maxidx */
   for( i = 0; i < row->len; ++i )
   {
      col = row->cols[i];
      assert(col != NULL);
      assert(!SCIPsetIsZero(set, row->vals[i]));
 
      absval = REALABS(row->vals[i]);
      assert(!SCIPsetIsZero(set, absval));
 
      /* update min/maxidx */
      row->minidx = MIN(row->minidx, col->index);
      row->maxidx = MAX(row->maxidx, col->index);
      row->numintcols += SCIPcolIsIntegral(col); /*lint !e713*/
 
      /* update maximal and minimal non-zero value */
      if( row->nummaxval > 0 )
      {
         if( SCIPsetIsGT(set, absval, row->maxval) )
         {
            row->maxval = absval;
            row->nummaxval = 1;
         }
         else if( SCIPsetIsGE(set, absval, row->maxval) )
         {
            /* make sure the maxval is always exactly the same */
            row->maxval = MAX(absval, row->maxval);
            row->nummaxval++;
         }
      }
      if( row->numminval > 0 )
      {
         if( SCIPsetIsLT(set, absval, row->minval) )
         {
            row->minval = absval;
            row->numminval = 1;
         }
         else if( SCIPsetIsLE(set, absval, row->minval) )
         {
            /* make sure the minval is always exactly the same */
            row->minval = MIN(absval, row->minval);
            row->numminval++;
         }
      }
   }
}
 
/** checks, whether the given scalar scales the given value to an integral number with error in the given bounds */
static
SCIP_Bool isIntegralScalar(
   SCIP_Real             val,                /**< value that should be scaled to an integral value */
   SCIP_Real             scalar,             /**< scalar that should be tried */
   SCIP_Real             mindelta,           /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
   SCIP_Real             maxdelta,           /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
   SCIP_Real*            intval              /**< pointer to store the scaled integral value, or NULL */
   )
{
   SCIP_Real sval;
   SCIP_Real downval;
   SCIP_Real upval;
 
   assert(mindelta <= 0.0);
   assert(maxdelta >= 0.0);
 
   sval = val * scalar;
   downval = floor(sval);
   upval = ceil(sval);
 
   if( SCIPrelDiff(sval, downval) <= maxdelta )
   {
      if( intval != NULL )
         *intval = downval;
      return TRUE;
   }
   else if( SCIPrelDiff(sval, upval) >= mindelta )
   {
      if( intval != NULL )
         *intval = upval;
      return TRUE;
   }
 
   return FALSE;
}
 
/** scales row with given factor, and rounds coefficients to integers if close enough;
 *  the constant is automatically moved to the sides;
 *  if the row's activity is proven to be integral, the sides are automatically rounded to the next integer
 */
static
SCIP_RETCODE rowScale(
   SCIP_ROW*             row,                /**< LP row */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_STAT*            stat,               /**< problem statistics */
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Real             scaleval,           /**< value to scale row with */
   SCIP_Bool             integralcontvars,   /**< should the coefficients of the continuous variables also be made integral,
                                              *   if they are close to integral values? */
   SCIP_Real             minrounddelta,      /**< minimal relative difference of scaled coefficient s*c and integral i,
                                              *   upto which the integral is used instead of the scaled real coefficient */
   SCIP_Real             maxrounddelta       /**< maximal relative difference of scaled coefficient s*c and integral i
                                              *   upto which the integral is used instead of the scaled real coefficient */
   )
{
   SCIP_COL* col;
   SCIP_Real val;
   SCIP_Real newval;
   SCIP_Real intval;
   SCIP_Real mindelta;
   SCIP_Real maxdelta;
   SCIP_Real lb;
   SCIP_Real ub;
   SCIP_Bool mindeltainf;
   SCIP_Bool maxdeltainf;
   int oldlen;
   int c;
 
   assert(row != NULL);
   assert(row->len == 0 || row->cols != NULL);
   assert(row->len == 0 || row->vals != NULL);
   assert(SCIPsetIsPositive(set, scaleval));
   assert(-1.0 < minrounddelta && minrounddelta <= 0.0);
   assert(0.0 <= maxrounddelta && maxrounddelta < 1.0);
 
   SCIPsetDebugMsg(set, "scale row <%s> with %g (tolerance=[%g,%g])\n", row->name, scaleval, minrounddelta, maxrounddelta);
 
   mindelta = 0.0;
   maxdelta = 0.0;
   mindeltainf = FALSE;
   maxdeltainf = FALSE;
   oldlen = row->len;
 
   /* scale the row coefficients, thereby recalculating whether the row's activity is always integral;
    * if the row coefficients are rounded to the nearest integer value, calculate the maximal activity difference,
    * this rounding can lead to
    */
   row->integral = TRUE;
 
   c = 0;
   while( c < row->len )
   {
      col = row->cols[c];
      val = row->vals[c];
      assert(!SCIPsetIsZero(set, val));
 
      /* get local or global bounds for column, depending on the local or global feasibility of the row */
      if( row->local )
      {
         lb = col->lb;
         ub = col->ub;
      }
      else
      {
         lb = SCIPvarGetLbGlobal(col->var);
         ub = SCIPvarGetUbGlobal(col->var);
      }
 
      /* calculate scaled coefficient */
      newval = val * scaleval;
      if( (integralcontvars || SCIPcolIsIntegral(col) || SCIPsetIsIntegral(set, newval))
         && isIntegralScalar(val, scaleval, minrounddelta, maxrounddelta, &intval) )
      {
         if( !SCIPsetIsEQ(set, intval, newval) )
         {
            if( intval < newval )
            {
               mindelta += (intval - newval)*ub;
               maxdelta += (intval - newval)*lb;
               mindeltainf = mindeltainf || SCIPsetIsInfinity(set, ub);
               maxdeltainf = maxdeltainf || SCIPsetIsInfinity(set, -lb);
            }
            else
            {
               mindelta += (intval - newval)*lb;
               maxdelta += (intval - newval)*ub;
               mindeltainf = mindeltainf || SCIPsetIsInfinity(set, -lb);
               maxdeltainf = maxdeltainf || SCIPsetIsInfinity(set, ub);
            }
         }
         newval = intval;
      }
 
      if( !SCIPsetIsEQ(set, val, newval) )
      {
         /* if column knows of the row, change the corresponding coefficient in the column */
         if( row->linkpos[c] >= 0 )
         {
            assert(col->rows[row->linkpos[c]] == row);
            assert(SCIPsetIsEQ(set, col->vals[row->linkpos[c]], row->vals[c]));
            SCIP_CALL( colChgCoefPos(col, set, lp, row->linkpos[c], newval) );
         }
 
         /* change the coefficient in the row, and update the norms and integrality status */
         SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, c, newval) );
 
         /* current coefficient has been deleted from the row because it was almost zero */
         if( oldlen != row->len )
         {
            assert(row->len == oldlen - 1);
            c--;
            oldlen = row->len;
         }
      }
      else
         row->integral = row->integral && SCIPcolIsIntegral(col) && SCIPsetIsIntegral(set, val);
 
      ++c;
   }
 
   /* scale the row sides, and move the constant to the sides; relax the sides with accumulated delta in order
    * to not destroy feasibility due to rounding
    */
   /**@todo ensure that returned cut does not have infinite lhs and rhs */
   if( !SCIPsetIsInfinity(set, -row->lhs) )
   {
      if( mindeltainf )
         newval = -SCIPsetInfinity(set);
      else
      {
         newval = (row->lhs - row->constant) * scaleval + mindelta;
         if( SCIPsetIsIntegral(set, newval) || (row->integral && !row->modifiable) )
            newval = SCIPsetSumCeil(set, newval);
      }
      SCIP_CALL( SCIProwChgLhs(row, blkmem, set, eventqueue, lp, newval) );
   }
   if( !SCIPsetIsInfinity(set, row->rhs) )
   {
      if( maxdeltainf )
         newval = SCIPsetInfinity(set);
      else
      {
         newval = (row->rhs - row->constant) * scaleval + maxdelta;
         if( SCIPsetIsIntegral(set, newval) || (row->integral && !row->modifiable) )
            newval = SCIPsetSumF