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-2019 Konrad-Zuse-Zentrum                            */
/*                            fuer Informationstechnik Berlin                */
/*                                                                           */
/*  SCIP is distributed under the terms of the ZIB Academic License.         */
/*                                                                           */
/*  You should have received a copy of the ZIB Academic License              */
/*  along with SCIP; see the file COPYING. If not visit scip.zib.de.         */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/**@file   lp.c
 * @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>



/*
 * 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;
   }

   /* 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;
}


#if 0 /* 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

#if 0 /* 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) != 0) )
   {
      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) != 0) )
   {
      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;
}

#if 0 /* 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 */
static
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 */
static
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 */
static
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 */
static
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 */
   )
{/*lint --e{715}*/
   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;

   /* This assert is currently disabled because it can happen that the feasibility tolerance is changed to a
    * value outside the interval allowed by the LP solver, in which case the lpi might project it to the bounds
    * of the LP solver and this assert will fail the next time.
    * It should be reenabled once this behaviour is unified among the lpis and handled explicitly in
    * lpSetFeastol() etc. with dedicated code instead of calling lpCheckRealpar().
    */
#if SCIP_DISABLED_CODE/*lint !e553*/
   /* check value */
   assert(lpivalue == value); /*lint !e777*/
#endif

   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) (set->lp_disablecutoff == 1 || (set->nactivepricers > 0 && 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_Real             objlim              /**< new objective limit */
   )
{
   assert(lp != NULL);
   assert(set != NULL);

   /* 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 return here and do not apply the objective limit. */
   if( lpCutoffDisabled(set) || set->misc_exactsolve )
      return SCIP_OKAY;

   /* 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_Bool success;

      SCIP_CALL( lpSetRealpar(lp, SCIP_LPPAR_OBJLIM, objlim, &success) );
      if( success )
      {
         /* 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 = objlim;
      }
   }

   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 successfully 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 )
      {
         if( lp->nrows > 0 && feastol < 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;
         }
         lp->lpifeastol = feastol;
      }
   }
   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 successfully 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 )
      {
         if( lp->nrows > 0 && dualfeastol < 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;
         }
         lp->lpidualfeastol = dualfeastol;
      }
   }
   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 successfully 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 )
      {
         if( lp->nrows > 0 && barrierconvtol < 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;
         }
         lp->lpibarrierconvtol = barrierconvtol;
      }
   }
   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;
   }
   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 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);

   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);

   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);
      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);

   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);
      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);

   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_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 */
   )
{
   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);
   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;

   if( col->validsblp != stat->nlps || itlim > col->sbitlim )
   {
      col->validsblp = stat->nlps;
      col->sbsolval = col->primsol;
      col->sblpobjval = SCIPlpGetObjval(lp, set, prob);
      col->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 )
      {
         col->sbdown = -SCIPsetInfinity(set);
         col->sbup = -SCIPsetInfinity(set);
         col->sbdownvalid = FALSE;
         col->sbupvalid = FALSE;
      }
      else
      {
         SCIP_RETCODE retcode;
         SCIP_Real sbdown;
         SCIP_Real sbup;
         SCIP_Bool sbdownvalid;
         SCIP_Bool sbupvalid;
         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 */
         col->sbitlim = itlim;
         col->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;
            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;
         }
         else
         {
            SCIP_Real looseobjval;

            *lperror = FALSE;
            SCIP_CALL( retcode );

            looseobjval = getFiniteLooseObjval(lp, set, prob);
            col->sbdown = MIN(sbdown + looseobjval, lp->cutoffbound);
            col->sbup = MIN(sbup + looseobjval, lp->cutoffbound);

            col->sbdownvalid = sbdownvalid;
            col->sbupvalid = 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;
            }
            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 || col->sbdown < SCIP_INVALID);
   assert(*lperror || col->sbup < SCIP_INVALID);

   if( down != NULL)
      *down = col->sbdown;
   if( up != NULL )
      *up = col->sbup;
   if( downvalid != NULL )
      *downvalid = col->sbdownvalid;
   if( upvalid != NULL )
      *upvalid = col->sbupvalid;

   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);
      assert(col->lpipos >= 0);
      assert(col->lppos >= 0);

      if( col->validsblp != stat->nlps || itlim > col->sbitlim )
      {
         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;
         }
      }
      else
      {
         /* directly set up resulting values (use stored values) */
         down[j] = col->sbdown;
         up[j] = col->sbup;
         if( downvalid != NULL )
            downvalid[j] = col->sbdownvalid;
         if( upvalid != NULL )
            upvalid[j] = col->sbupvalid;
      }
   }

   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);
         assert( col->sbup < SCIP_INVALID);

         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 = SCIPsetSumFloor(set, newval);
      }
      SCIP_CALL( SCIProwChgRhs(row, blkmem, set, eventqueue, lp, newval) );
   }

   /* clear the row constant */
   SCIP_CALL( SCIProwChgConstant(row, blkmem, set, stat, eventqueue, lp, 0.0) );

   SCIPsetDebugMsg(set, "scaled row <%s> (integral: %u)\n", row->name, row->integral);
   debugRowPrint(set, row);

#ifdef SCIP_DEBUG
   /* check integrality status of row */
   for( c = 0; c < row->len && SCIPcolIsIntegral(row->cols[c]) && SCIPsetIsIntegral(set, row->vals[c]); ++c )
   {}
   assert(row->integral == (c == row->len));
#endif

   /* invalid the activity */
   row->validactivitylp = -1;

   return SCIP_OKAY;
}

/** creates and captures an LP row */
SCIP_RETCODE SCIProwCreate(
   SCIP_ROW**            row,                /**< pointer to LP row data */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_STAT*            stat,               /**< problem statistics */
   SCIP_LP*              lp,                 /**< current LP data */
   const char*           name,               /**< name of row */
   int                   len,                /**< number of nonzeros in the row */
   SCIP_COL**            cols,               /**< array with columns of row entries */
   SCIP_Real*            vals,               /**< array with coefficients of row entries */
   SCIP_Real             lhs,                /**< left hand side of row */
   SCIP_Real             rhs,                /**< right hand side of row */
   SCIP_ROWORIGINTYPE    origintype,         /**< type of origin of row */
   void*                 origin,             /**< pointer to constraint handler or separator who created the row (NULL if unkown) */
   SCIP_Bool             local,              /**< is row only valid locally? */
   SCIP_Bool             modifiable,         /**< is row modifiable during node processing (subject to column generation)? */
   SCIP_Bool             removable           /**< should the row be removed from the LP due to aging or cleanup? */
   )
{
   assert(row != NULL);
   assert(blkmem != NULL);
   assert(stat != NULL);
   assert(len >= 0);
   assert(len == 0 || (cols != NULL && vals != NULL));
   /* note, that the assert tries to avoid numerical troubles in the LP solver.
    * in case, for example, lhs > rhs but they are equal with tolerances, one could pass lhs=rhs=lhs+rhs/2 to
    * SCIProwCreate() (see cons_linear.c: detectRedundantConstraints())
    */
   assert(lhs <= rhs);

   SCIP_ALLOC( BMSallocBlockMemory(blkmem, row) );

   (*row)->integral = TRUE;
   if( len > 0 )
   {
      SCIP_VAR* var;
      int i;

      SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*row)->cols, cols, len) );
      SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*row)->vals, vals, len) );
      SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*row)->cols_index, len) );
      SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*row)->linkpos, len) );

      for( i = 0; i < len; ++i )
      {
         assert(cols[i] != NULL);
         assert(!SCIPsetIsZero(set, vals[i]));

         var = cols[i]->var;
         (*row)->cols_index[i] = cols[i]->index;
         (*row)->linkpos[i] = -1;
         if( SCIPsetIsIntegral(set, (*row)->vals[i]) )
         {
            (*row)->vals[i] = SCIPsetRound(set, (*row)->vals[i]);
            (*row)->integral = (*row)->integral && SCIPvarIsIntegral(var);
         }
         else
         {
            (*row)->integral = FALSE;
         }
      }
   }
   else
   {
      (*row)->cols = NULL;
      (*row)->cols_index = NULL;
      (*row)->vals = NULL;
      (*row)->linkpos = NULL;
   }

   SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*row)->name, name, strlen(name)+1) );
   (*row)->constant = 0.0;
   (*row)->lhs = lhs;
   (*row)->rhs = rhs;
   (*row)->flushedlhs = -SCIPsetInfinity(set);
   (*row)->flushedrhs = SCIPsetInfinity(set);
   (*row)->sqrnorm = 0.0;
   (*row)->sumnorm = 0.0;
   (*row)->objprod = 0.0;
   (*row)->maxval = 0.0;
   (*row)->minval = SCIPsetInfinity(set);
   (*row)->dualsol = 0.0;
   (*row)->activity = SCIP_INVALID;
   (*row)->dualfarkas = 0.0;
   (*row)->pseudoactivity = SCIP_INVALID;
   (*row)->minactivity = SCIP_INVALID;
   (*row)->maxactivity = SCIP_INVALID;
   (*row)->origin = origin;
   (*row)->eventfilter = NULL;
   (*row)->index = stat->nrowidx;
   SCIPstatIncrement(stat, set, nrowidx);
   (*row)->size = len;
   (*row)->len = len;
   (*row)->nlpcols = 0;
   (*row)->nunlinked = len;
   (*row)->nuses = 0;
   (*row)->lppos = -1;
   (*row)->lpipos = -1;
   (*row)->lpdepth = -1;
   (*row)->minidx = INT_MAX;
   (*row)->maxidx = INT_MIN;
   (*row)->nummaxval = 0;
   (*row)->numminval = 0;
   (*row)->numintcols = -1;
   (*row)->validactivitylp = -1;
   (*row)->validpsactivitydomchg = -1;
   (*row)->validactivitybdsdomchg = -1;
   (*row)->nlpsaftercreation = 0L;
   (*row)->activeinlpcounter = 0L;
   (*row)->age = 0;
   (*row)->rank = 0;
   (*row)->obsoletenode = -1;
   (*row)->basisstatus = SCIP_BASESTAT_BASIC; /*lint !e641*/
   (*row)->lpcolssorted = TRUE;
   (*row)->nonlpcolssorted = (len <= 1);
   (*row)->delaysort = FALSE;
   (*row)->validminmaxidx = FALSE;
   (*row)->lhschanged = FALSE;
   (*row)->rhschanged = FALSE;
   (*row)->coefchanged = FALSE;
   (*row)->local = local;
   (*row)->modifiable = modifiable;
   (*row)->nlocks = 0;
   (*row)->origintype = origintype; /*lint !e641*/
   (*row)->removable = removable;
   (*row)->inglobalcutpool = FALSE;
   (*row)->storedsolvals = NULL;

   /* calculate row norms and min/maxidx, and check if row is sorted */
   rowCalcNorms(*row, set);

   /* capture the row */
   SCIProwCapture(*row);

   /* create event filter */
   SCIP_CALL( SCIPeventfilterCreate(&(*row)->eventfilter, blkmem) );

   return SCIP_OKAY;
} /*lint !e715*/

/** frees an LP row */
SCIP_RETCODE SCIProwFree(
   SCIP_ROW**            row,                /**< pointer to LP row */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   assert(blkmem != NULL);
   assert(row != NULL);
   assert(*row != NULL);
   assert((*row)->nuses == 0);
   assert((*row)->lppos == -1);
   assert((*row)->eventfilter != NULL);

   /* remove column indices from corresponding rows */
   SCIP_CALL( rowUnlink(*row, set, lp) );

   /* free event filter */
   SCIP_CALL( SCIPeventfilterFree(&(*row)->eventfilter, blkmem, set) );

   BMSfreeBlockMemoryNull(blkmem, &(*row)->storedsolvals);
   BMSfreeBlockMemoryArray(blkmem, &(*row)->name, strlen((*row)->name)+1);
   BMSfreeBlockMemoryArrayNull(blkmem, &(*row)->cols, (*row)->size);
   BMSfreeBlockMemoryArrayNull(blkmem, &(*row)->cols_index, (*row)->size);
   BMSfreeBlockMemoryArrayNull(blkmem, &(*row)->vals, (*row)->size);
   BMSfreeBlockMemoryArrayNull(blkmem, &(*row)->linkpos, (*row)->size);
   BMSfreeBlockMemory(blkmem, row);

   return SCIP_OKAY;
}

/** output row to file stream */
void SCIProwPrint(
   SCIP_ROW*             row,                /**< LP row */
   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
   FILE*                 file                /**< output file (or NULL for standard output) */
   )
{
   int i;

   assert(row != NULL);

   /* print row name */
   if( row->name != NULL && row->name[0] != '\0' )
   {
      SCIPmessageFPrintInfo(messagehdlr, file, "%s: ", row->name);
   }

   /* print left hand side */
   SCIPmessageFPrintInfo(messagehdlr, file, "%.15g <= ", row->lhs);

   /* print coefficients */
   if( row->len == 0 )
      SCIPmessageFPrintInfo(messagehdlr, file, "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);
      SCIPmessageFPrintInfo(messagehdlr, file, "%+.15g<%s> ", row->vals[i], SCIPvarGetName(row->cols[i]->var));
   }

   /* print constant */
   if( REALABS(row->constant) > SCIP_DEFAULT_EPSILON )
      SCIPmessageFPrintInfo(messagehdlr, file, "%+.15g ", row->constant);

   /* print right hand side */
   SCIPmessageFPrintInfo(messagehdlr, file, "<= %.15g\n", row->rhs);
}

/** increases usage counter of LP row */
void SCIProwCapture(
   SCIP_ROW*             row                 /**< LP row */
   )
{
   assert(row != NULL);
   assert(row->nuses >= 0);
   assert(row->nlocks <= (unsigned int)(row->nuses)); /*lint !e574*/

   SCIPdebugMessage("capture row <%s> with nuses=%d and nlocks=%u\n", row->name, row->nuses, row->nlocks);
   row->nuses++;
}

/** decreases usage counter of LP row, and frees memory if necessary */
SCIP_RETCODE SCIProwRelease(
   SCIP_ROW**            row,                /**< pointer to LP row */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_LP*              lp                  /**< current LP data */
   )
{
   assert(blkmem != NULL);
   assert(row != NULL);
   assert(*row != NULL);
   assert((*row)->nuses >= 1);
   assert((*row)->nlocks < (unsigned int)((*row)->nuses)); /*lint !e574*/

   SCIPsetDebugMsg(set, "release row <%s> with nuses=%d and nlocks=%u\n", (*row)->name, (*row)->nuses, (*row)->nlocks);
   (*row)->nuses--;
   if( (*row)->nuses == 0 )
   {
      SCIP_CALL( SCIProwFree(row, blkmem, set, lp) );
   }

   *row = NULL;

   return SCIP_OKAY;
}

/** locks an unmodifiable row, which forbids further changes; has no effect on modifiable rows */
void SCIProwLock(
   SCIP_ROW*             row                 /**< LP row */
   )
{
   assert(row != NULL);

   /* check, if row is modifiable */
   if( !row->modifiable )
   {
      SCIPdebugMessage("lock row <%s> with nuses=%d and nlocks=%u\n", row->name, row->nuses, row->nlocks);
      row->nlocks++;
   }
}

/** unlocks a lock of an unmodifiable row; a row with no sealed lock may be modified; has no effect on modifiable rows */
void SCIProwUnlock(
   SCIP_ROW*             row                 /**< LP row */
   )
{
   assert(row != NULL);

   /* check, if row is modifiable */
   if( !row->modifiable )
   {
      SCIPdebugMessage("unlock row <%s> with nuses=%d and nlocks=%u\n", row->name, row->nuses, row->nlocks);
      assert(row->nlocks > 0);
      row->nlocks--;
   }
}

/** adds a previously non existing coefficient to an LP row */
SCIP_RETCODE SCIProwAddCoef(
   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 */
   )
{
   assert(lp != NULL);
   assert(!lp->diving || row->lppos == -1);

   SCIP_CALL( rowAddCoef(row, blkmem, set, eventqueue, lp, col, val, -1) );

   checkLinks(lp);

   return SCIP_OKAY;
}

/** deletes coefficient from row */
SCIP_RETCODE SCIProwDelCoef(
   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 */
   SCIP_COL*             col                 /**< coefficient to be deleted */
   )
{
   int pos;

   assert(row != NULL);
   assert(!row->delaysort);
   assert(lp != NULL);
   assert(!lp->diving || row->lppos == -1);
   assert(col != NULL);
   assert(col->var != NULL);

   /* search the position of the column in the row's col vector */
   pos = rowSearchCoef(row, col);
   if( pos == -1 )
   {
      SCIPerrorMessage("coefficient for column <%s> doesn't exist in row <%s>\n", SCIPvarGetName(col->var), row->name);
      return SCIP_INVALIDDATA;
   }
   assert(0 <= pos && pos < row->len);
   assert(row->cols[pos] == col);
   assert(row->cols_index[pos] == col->index);

   /* if column knows of the row, remove the row from the column's row vector */
   if( row->linkpos[pos] >= 0 )
   {
      assert(col->rows[row->linkpos[pos]] == row);
      assert(SCIPsetIsEQ(set, col->vals[row->linkpos[pos]], row->vals[pos]));
      SCIP_CALL( colDelCoefPos(col, set, lp, row->linkpos[pos]) );
   }

   /* delete the column from the row's col vector */
   SCIP_CALL( rowDelCoefPos(row, blkmem, set, eventqueue, lp, pos) );

   checkLinks(lp);

   return SCIP_OKAY;
}

/** changes or adds a coefficient to an LP row */
SCIP_RETCODE SCIProwChgCoef(
   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 pos;

   assert(row != NULL);
   assert(!row->delaysort);
   assert(lp != NULL);
   assert(!lp->diving || row->lppos == -1);
   assert(col != NULL);

   /* search the position of the column in the row's col vector */
   pos = rowSearchCoef(row, col);

   /* check, if column already exists in the row's col vector */
   if( pos == -1 )
   {
      /* add previously not existing coefficient */
      SCIP_CALL( rowAddCoef(row, blkmem, set, eventqueue, lp, col, val, -1) );
   }
   else
   {
      /* modify already existing coefficient */
      assert(0 <= pos && pos < row->len);
      assert(row->cols[pos] == col);
      assert(row->cols_index[pos] == col->index);

      /* if column knows of the row, change the corresponding coefficient in the column */
      if( row->linkpos[pos] >= 0 )
      {
         assert(col->rows[row->linkpos[pos]] == row);
         assert(SCIPsetIsEQ(set, col->vals[row->linkpos[pos]], row->vals[pos]));
         SCIP_CALL( colChgCoefPos(col, set, lp, row->linkpos[pos], val) );
      }

      /* change the coefficient in the row */
      SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, pos, val) );
   }

   checkLinks(lp);

   return SCIP_OKAY;
}

/** increases value of an existing or non-existing coefficient in an LP row */
SCIP_RETCODE SCIProwIncCoef(
   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             incval              /**< value to add to the coefficient */
   )
{
   int pos;

   assert(row != NULL);
   assert(lp != NULL);
   assert(!lp->diving || row->lppos == -1);
   assert(col != NULL);

   if( SCIPsetIsZero(set, incval) )
      return SCIP_OKAY;

   /* search the position of the column in the row's col vector */
   pos = rowSearchCoef(row, col);

   /* check, if column already exists in the row's col vector */
   if( pos == -1 )
   {
      /* coefficient doesn't exist, or sorting is delayed: add coefficient to the end of the row's arrays */
      SCIP_CALL( rowAddCoef(row, blkmem, set, eventqueue, lp, col, incval, -1) );
   }
   else
   {
      /* modify already existing coefficient */
      assert(0 <= pos && pos < row->len);
      assert(row->cols[pos] == col);
      assert(row->cols_index[pos] == col->index);

      /* if column knows of the row, change the corresponding coefficient in the column */
      if( row->linkpos[pos] >= 0 )
      {
         assert(col->rows[row->linkpos[pos]] == row);
         assert(SCIPsetIsEQ(set, col->vals[row->linkpos[pos]], row->vals[pos]));
         SCIP_CALL( colChgCoefPos(col, set, lp, row->linkpos[pos], row->vals[pos] + incval) );
      }

      /* change the coefficient in the row */
      SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, pos, row->vals[pos] + incval) );
   }

   checkLinks(lp);

   /* invalid the activity */
   row->validactivitylp = -1;

   return SCIP_OKAY;
}

/** changes constant value of a row */
SCIP_RETCODE SCIProwChgConstant(
   SCIP_ROW*             row,                /**< LP row */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_STAT*            stat,               /**< problem statistics */
   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
   SCIP_LP*              lp,                 /**< current LP data */
   SCIP_Real             constant            /**< new constant value */
   )
{
   assert(row != NULL);
   assert(row->lhs <= row->rhs);
   assert(!SCIPsetIsInfinity(set, REALABS(constant)));
   assert(stat != NULL);
   assert(lp != NULL);
   assert(!lp->diving || row->lppos == -1);

   if( !SCIPsetIsEQ(set, constant, row->constant) )
   {
      SCIP_Real oldconstant;

      if( row->validpsactivitydomchg == stat->domchgcount )
      {
         assert(row->pseudoactivity < SCIP_INVALID);
         row->pseudoactivity += constant - row->constant;
      }
      if( row->validactivitybdsdomchg == stat->domchgcount )
      {
         assert(row->minactivity < SCIP_INVALID);
         assert(row->maxactivity < SCIP_INVALID);
         row->minactivity += constant - row->constant;
         row->maxactivity += constant - row->constant;
      }

      if( !SCIPsetIsInfinity(set, -row->lhs) )
      {
         SCIP_CALL( rowSideChanged(row, set, lp, SCIP_SIDETYPE_LEFT) );
      }
      if( !SCIPsetIsInfinity(set, row->rhs) )
      {
         SCIP_CALL( rowSideChanged(row, set, lp, SCIP_SIDETYPE_RIGHT) );
      }