cons_linear.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-2023 Zuse Institute Berlin (ZIB)                      */
/*                                                                           */
/*  Licensed under the Apache License, Version 2.0 (the "License");          */
/*  you may not use this file except in compliance with the License.         */
/*  You may obtain a copy of the License at                                  */
/*                                                                           */
/*      http://www.apache.org/licenses/LICENSE-2.0                           */
/*                                                                           */
/*  Unless required by applicable law or agreed to in writing, software      */
/*  distributed under the License is distributed on an "AS IS" BASIS,        */
/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
/*  See the License for the specific language governing permissions and      */
/*  limitations under the License.                                           */
/*                                                                           */
/*  You should have received a copy of the Apache-2.0 license                */
/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/**@file   cons_linear.c
 * @ingroup DEFPLUGINS_CONS
 * @brief Constraint handler for linear constraints in their most general form, \f$lhs <= a^T x <= rhs\f$.
 * @author Tobias Achterberg
 * @author Timo Berthold
 * @author Marc Pfetsch
 * @author Kati Wolter
 * @author Michael Winkler
 * @author Gerald Gamrath
 * @author Domenico Salvagnin
 *
 *  Linear constraints are separated with a high priority, because they are easy
 *  to separate. Instead of using the global cut pool, the same effect can be
 *  implemented by adding linear constraints to the root node, such that they are
 *  separated each time, the linear constraints are separated. A constraint
 *  handler, which generates linear constraints in this way should have a lower
 *  separation priority than the linear constraint handler, and it should have a
 *  separation frequency that is a multiple of the frequency of the linear
 *  constraint handler. In this way, it can be avoided to separate the same cut
 *  twice, because if a separation run of the handler is always preceded by a
 *  separation of the linear constraints, the priorily added constraints are
 *  always satisfied.
 *
 *  Linear constraints are enforced and checked with a very low priority. Checking
 *  of (many) linear constraints is much more involved than checking the solution
 *  values for integrality. Because we are separating the linear constraints quite
 *  often, it is only necessary to enforce them for integral solutions. A constraint
 *  handler which generates pool cuts in its enforcing method should have an
 *  enforcing priority smaller than that of the linear constraint handler to avoid
 *  regenerating constraints which already exist.
 */

/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/

#include "blockmemshell/memory.h"
#include "scip/cons_nonlinear.h"
#include "scip/cons_knapsack.h"
#include "scip/cons_linear.h"
#include "scip/debug.h"
#include "scip/pub_conflict.h"
#include "scip/pub_cons.h"
#include "scip/pub_event.h"
#include "scip/pub_expr.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/scip_branch.h"
#include "scip/scip_conflict.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_cut.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include "scip/dbldblarith.h"


#define CONSHDLR_NAME          "linear"
#define CONSHDLR_DESC          "linear constraints of the form  lhs <= a^T x <= rhs"
#define CONSHDLR_SEPAPRIORITY   +100000 /**< priority of the constraint handler for separation */
#define CONSHDLR_ENFOPRIORITY  -1000000 /**< priority of the constraint handler for constraint enforcing */
#define CONSHDLR_CHECKPRIORITY -1000000 /**< priority of the constraint handler for checking feasibility */
#define CONSHDLR_SEPAFREQ             0 /**< frequency for separating cuts; zero means to separate only in the root node */
#define CONSHDLR_PROPFREQ             1 /**< frequency for propagating domains; zero means only preprocessing propagation */
#define CONSHDLR_EAGERFREQ          100 /**< frequency for using all instead of only the useful constraints in separation,
                                         *   propagation and enforcement, -1 for no eager evaluations, 0 for first only */
#define CONSHDLR_MAXPREROUNDS        -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
#define CONSHDLR_DELAYSEPA        FALSE /**< should separation method be delayed, if other separators found cuts? */
#define CONSHDLR_DELAYPROP        FALSE /**< should propagation method be delayed, if other propagators found reductions? */
#define CONSHDLR_NEEDSCONS         TRUE /**< should the constraint handler be skipped, if no constraints are available? */

#define CONSHDLR_PRESOLTIMING    (SCIP_PRESOLTIMING_FAST | SCIP_PRESOLTIMING_EXHAUSTIVE) /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
#define CONSHDLR_PROP_TIMING     SCIP_PROPTIMING_BEFORELP

#define EVENTHDLR_NAME         "linear"
#define EVENTHDLR_DESC         "bound change event handler for linear constraints"

#define CONFLICTHDLR_NAME      "linear"
#define CONFLICTHDLR_DESC      "conflict handler creating linear constraints"
#define CONFLICTHDLR_PRIORITY  -1000000

#define DEFAULT_TIGHTENBOUNDSFREQ       1 /**< multiplier on propagation frequency, how often the bounds are tightened */
#define DEFAULT_MAXROUNDS               5 /**< maximal number of separation rounds per node (-1: unlimited) */
#define DEFAULT_MAXROUNDSROOT          -1 /**< maximal number of separation rounds in the root node (-1: unlimited) */
#define DEFAULT_MAXSEPACUTS            50 /**< maximal number of cuts separated per separation round */
#define DEFAULT_MAXSEPACUTSROOT       200 /**< maximal number of cuts separated per separation round in root node */
#define DEFAULT_PRESOLPAIRWISE       TRUE /**< should pairwise constraint comparison be performed in presolving? */
#define DEFAULT_PRESOLUSEHASHING     TRUE /**< should hash table be used for detecting redundant constraints in advance */
#define DEFAULT_NMINCOMPARISONS    200000 /**< number for minimal pairwise presolving comparisons */
#define DEFAULT_MINGAINPERNMINCOMP  1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise
                                           *   comparison round */
#define DEFAULT_SORTVARS             TRUE /**< should variables be sorted after presolve w.r.t their coefficient absolute for faster
                                           *  propagation? */
#define DEFAULT_CHECKRELMAXABS      FALSE /**< should the violation for a constraint with side 0.0 be checked relative
                                           *   to 1.0 (FALSE) or to the maximum absolute value in the activity (TRUE)? */
#define DEFAULT_MAXAGGRNORMSCALE      0.0 /**< maximal allowed relative gain in maximum norm for constraint aggregation
                                           *   (0.0: disable constraint aggregation) */
#define DEFAULT_MAXEASYACTIVITYDELTA  1e6 /**< maximum activity delta to run easy propagation on linear constraint
                                           *   (faster, but numerically less stable) */
#define DEFAULT_MAXCARDBOUNDDIST      0.0 /**< maximal relative distance from current node's dual bound to primal bound compared
                                           *   to best node's dual bound for separating knapsack cardinality cuts */
#define DEFAULT_SEPARATEALL         FALSE /**< should all constraints be subject to cardinality cut generation instead of only
                                           *   the ones with non-zero dual value? */
#define DEFAULT_AGGREGATEVARIABLES   TRUE /**< should presolving search for redundant variables in equations */
#define DEFAULT_SIMPLIFYINEQUALITIES TRUE /**< should presolving try to simplify inequalities */
#define DEFAULT_DUALPRESOLVING       TRUE /**< should dual presolving steps be performed? */
#define DEFAULT_SINGLETONSTUFFING    TRUE /**< should stuffing of singleton continuous variables be performed? */
#define DEFAULT_SINGLEVARSTUFFING   FALSE /**< should single variable stuffing be performed, which tries to fulfill
                                           *   constraints using the cheapest variable? */
#define DEFAULT_DETECTCUTOFFBOUND    TRUE /**< should presolving try to detect constraints parallel to the objective
                                           *   function defining an upper bound and prevent these constraints from
                                           *   entering the LP */
#define DEFAULT_DETECTLOWERBOUND     TRUE /**< should presolving try to detect constraints parallel to the objective
                                           *   function defining a lower bound and prevent these constraints from
                                           *   entering the LP */
#define DEFAULT_DETECTPARTIALOBJECTIVE TRUE/**< should presolving try to detect subsets of constraints parallel to the
                                            *   objective function */
#define DEFAULT_RANGEDROWPROPAGATION TRUE /**< should we perform ranged row propagation */
#define DEFAULT_RANGEDROWARTCONS     TRUE /**< should presolving and propagation extract sub-constraints from ranged rows and equations? */
#define DEFAULT_RANGEDROWMAXDEPTH INT_MAX /**< maximum depth to apply ranged row propagation */
#define DEFAULT_RANGEDROWFREQ           1 /**< frequency for applying ranged row propagation */

#define DEFAULT_MULTAGGRREMOVE      FALSE /**< should multi-aggregations only be performed if the constraint can be
                                           *   removed afterwards? */
#define DEFAULT_MAXMULTAGGRQUOT     1e+03 /**< maximum coefficient dynamism (ie. maxabsval / minabsval) for multiaggregation */
#define DEFAULT_MAXDUALMULTAGGRQUOT 1e+20 /**< maximum coefficient dynamism (ie. maxabsval / minabsval) for multiaggregation */
#define DEFAULT_EXTRACTCLIQUES       TRUE /**< should cliques be extracted? */

#define MAXDNOM                   10000LL /**< maximal denominator for simple rational fixed values */
#define MAXSCALEDCOEF                   0 /**< maximal coefficient value after scaling */
#define MAXSCALEDCOEFINTEGER            0 /**< maximal coefficient value after scaling if all variables are of integral
                                           *   type
                                           */
#define MAXACTVAL                   1e+09 /**< maximal absolute value of full and partial activities such that
                                           *   redundancy-based simplifications are allowed to be applied
                                           */

#define MAXVALRECOMP                1e+06 /**< maximal abolsute value we trust without recomputing the activity */
#define MINVALRECOMP                1e-05 /**< minimal abolsute value we trust without recomputing the activity */


#define NONLINCONSUPGD_PRIORITY   1000000 /**< priority of the constraint handler for upgrading of expressions constraints */

/* @todo add multi-aggregation of variables that are in exactly two equations (, if not numerically an issue),
 *       maybe in fullDualPresolve(), see convertLongEquality()
 */


/** constraint data for linear constraints */
struct SCIP_ConsData
{
   SCIP_Real             lhs;                /**< left hand side of row (for ranged rows) */
   SCIP_Real             rhs;                /**< right hand side of row */
   SCIP_Real             maxabsval;          /**< maximum absolute value of all coefficients */
   SCIP_Real             minabsval;          /**< minimal absolute value of all coefficients */
   QUAD_MEMBER(SCIP_Real minactivity);       /**< minimal value w.r.t. the variable's local bounds for the constraint's
                                              *   activity, ignoring the coefficients contributing with infinite value */
   QUAD_MEMBER(SCIP_Real maxactivity);       /**< maximal value w.r.t. the variable's local bounds for the constraint's
                                              *   activity, ignoring the coefficients contributing with infinite value */
   SCIP_Real             lastminactivity;    /**< last minimal activity which was computed by complete summation
                                              *   over all contributing values */
   SCIP_Real             lastmaxactivity;    /**< last maximal activity which was computed by complete summation
                                              *   over all contributing values */
   QUAD_MEMBER(SCIP_Real glbminactivity);    /**< minimal value w.r.t. the variable's global bounds for the constraint's
                                              *   activity, ignoring the coefficients contributing with infinite value */
   QUAD_MEMBER(SCIP_Real glbmaxactivity);    /**< maximal value w.r.t. the variable's global bounds for the constraint's
                                              *   activity, ignoring the coefficients contributing with infinite value */
   SCIP_Real             lastglbminactivity; /**< last global minimal activity which was computed by complete summation
                                              *   over all contributing values */
   SCIP_Real             lastglbmaxactivity; /**< last global maximal activity which was computed by complete summation
                                              *   over all contributing values */
   SCIP_Real             maxactdelta;        /**< maximal activity contribution of a single variable, or SCIP_INVALID if invalid */
   SCIP_VAR*             maxactdeltavar;     /**< variable with maximal activity contribution, or NULL if invalid */
   uint64_t              possignature;       /**< bit signature of coefficients that may take a positive value */
   uint64_t              negsignature;       /**< bit signature of coefficients that may take a negative value */
   SCIP_ROW*             row;                /**< LP row, if constraint is already stored in LP row format */
   SCIP_NLROW*           nlrow;              /**< NLP row, if constraint has been added to NLP relaxation */
   SCIP_VAR**            vars;               /**< variables of constraint entries */
   SCIP_Real*            vals;               /**< coefficients of constraint entries */
   SCIP_EVENTDATA**      eventdata;          /**< event data for bound change events of the variables */
   int                   minactivityneginf;  /**< number of coefficients contributing with neg. infinite value to minactivity */
   int                   minactivityposinf;  /**< number of coefficients contributing with pos. infinite value to minactivity */
   int                   maxactivityneginf;  /**< number of coefficients contributing with neg. infinite value to maxactivity */
   int                   maxactivityposinf;  /**< number of coefficients contributing with pos. infinite value to maxactivity */
   int                   minactivityneghuge; /**< number of coefficients contributing with huge neg. value to minactivity */
   int                   minactivityposhuge; /**< number of coefficients contributing with huge pos. value to minactivity */
   int                   maxactivityneghuge; /**< number of coefficients contributing with huge neg. value to maxactivity */
   int                   maxactivityposhuge; /**< number of coefficients contributing with huge pos. value to maxactivity */
   int                   glbminactivityneginf;/**< number of coefficients contrib. with neg. infinite value to glbminactivity */
   int                   glbminactivityposinf;/**< number of coefficients contrib. with pos. infinite value to glbminactivity */
   int                   glbmaxactivityneginf;/**< number of coefficients contrib. with neg. infinite value to glbmaxactivity */
   int                   glbmaxactivityposinf;/**< number of coefficients contrib. with pos. infinite value to glbmaxactivity */
   int                   glbminactivityneghuge;/**< number of coefficients contrib. with huge neg. value to glbminactivity */
   int                   glbminactivityposhuge;/**< number of coefficients contrib. with huge pos. value to glbminactivity */
   int                   glbmaxactivityneghuge;/**< number of coefficients contrib. with huge neg. value to glbmaxactivity */
   int                   glbmaxactivityposhuge;/**< number of coefficients contrib. with huge pos. value to glbmaxactivity */
   int                   varssize;           /**< size of the vars- and vals-arrays */
   int                   nvars;              /**< number of nonzeros in constraint */
   int                   nbinvars;           /**< the number of binary variables in the constraint, only valid after
                                              *   sorting in stage >= SCIP_STAGE_INITSOLVE
                                              */
   unsigned int          boundstightened:2;  /**< is constraint already propagated with bound tightening? */
   unsigned int          rangedrowpropagated:2; /**< did we perform ranged row propagation on this constraint?
                                                 *   (0: no, 1: yes, 2: with potentially adding artificial constraint */
   unsigned int          validmaxabsval:1;   /**< is the maximum absolute value valid? */
   unsigned int          validminabsval:1;   /**< is the minimum absolute value valid? */
   unsigned int          validactivities:1;  /**< are the activity bounds (local and global) valid? */
   unsigned int          validminact:1;      /**< is the local minactivity valid? */
   unsigned int          validmaxact:1;      /**< is the local maxactivity valid? */
   unsigned int          validglbminact:1;   /**< is the global minactivity valid? */
   unsigned int          validglbmaxact:1;   /**< is the global maxactivity valid? */
   unsigned int          presolved:1;        /**< is constraint already presolved? */
   unsigned int          removedfixings:1;   /**< are all fixed variables removed from the constraint? */
   unsigned int          validsignature:1;   /**< is the bit signature valid? */
   unsigned int          changed:1;          /**< was constraint changed since last aggregation round in preprocessing? */
   unsigned int          normalized:1;       /**< is the constraint in normalized form? */
   unsigned int          upgradetried:1;     /**< was the constraint already tried to be upgraded? */
   unsigned int          upgraded:1;         /**< is the constraint upgraded and will it be removed after preprocessing? */
   unsigned int          indexsorted:1;      /**< are the constraint's variables sorted by type and index? */
   unsigned int          merged:1;           /**< are the constraint's equal variables already merged? */
   unsigned int          cliquesadded:1;     /**< were the cliques of the constraint already extracted? */
   unsigned int          implsadded:1;       /**< were the implications of the constraint already extracted? */
   unsigned int          coefsorted:1;       /**< are variables sorted by type and their absolute activity delta? */
   unsigned int          varsdeleted:1;      /**< were variables deleted after last cleanup? */
   unsigned int          hascontvar:1;       /**< does the constraint contain at least one continuous variable? */
   unsigned int          hasnonbinvar:1;     /**< does the constraint contain at least one non-binary variable? */
   unsigned int          hasnonbinvalid:1;   /**< is the information stored in hasnonbinvar and hascontvar valid? */
   unsigned int          checkabsolute:1;    /**< should the constraint be checked w.r.t. an absolute feasibilty tolerance? */
};

/** event data for bound change event */
struct SCIP_EventData
{
   SCIP_CONS*            cons;               /**< linear constraint to process the bound change for */
   int                   varpos;             /**< position of variable in vars array */
   int                   filterpos;          /**< position of event in variable's event filter */
};

/** constraint handler data */
struct SCIP_ConshdlrData
{
   SCIP_EVENTHDLR*       eventhdlr;          /**< event handler for bound change events */
   SCIP_LINCONSUPGRADE** linconsupgrades;    /**< linear constraint upgrade methods for specializing linear constraints */
   SCIP_Real             maxaggrnormscale;   /**< maximal allowed relative gain in maximum norm for constraint aggregation
                                              *   (0.0: disable constraint aggregation) */
   SCIP_Real             maxcardbounddist;   /**< maximal relative distance from current node's dual bound to primal bound compared
                                              *   to best node's dual bound for separating knapsack cardinality cuts */
   SCIP_Real             mingainpernmincomp; /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
   SCIP_Real             maxeasyactivitydelta;/**< maximum activity delta to run easy propagation on linear constraint
                                               *   (faster, but numerically less stable) */
   int                   linconsupgradessize;/**< size of linconsupgrade array */
   int                   nlinconsupgrades;   /**< number of linear constraint upgrade methods */
   int                   tightenboundsfreq;  /**< multiplier on propagation frequency, how often the bounds are tightened */
   int                   maxrounds;          /**< maximal number of separation rounds per node (-1: unlimited) */
   int                   maxroundsroot;      /**< maximal number of separation rounds in the root node (-1: unlimited) */
   int                   maxsepacuts;        /**< maximal number of cuts separated per separation round */
   int                   maxsepacutsroot;    /**< maximal number of cuts separated per separation round in root node */
   int                   nmincomparisons;    /**< number for minimal pairwise presolving comparisons */
   int                   naddconss;          /**< number of added constraints */
   SCIP_Bool             presolpairwise;     /**< should pairwise constraint comparison be performed in presolving? */
   SCIP_Bool             presolusehashing;   /**< should hash table be used for detecting redundant constraints in advance */
   SCIP_Bool             separateall;        /**< should all constraints be subject to cardinality cut generation instead of only
                                              *   the ones with non-zero dual value? */
   SCIP_Bool             aggregatevariables; /**< should presolving search for redundant variables in equations */
   SCIP_Bool             simplifyinequalities;/**< should presolving try to cancel down or delete coefficients in inequalities */
   SCIP_Bool             dualpresolving;     /**< should dual presolving steps be performed? */
   SCIP_Bool             singletonstuffing;  /**< should stuffing of singleton continuous variables be performed? */
   SCIP_Bool             singlevarstuffing;  /**< should single variable stuffing be performed, which tries to fulfill
                                              *   constraints using the cheapest variable? */
   SCIP_Bool             sortvars;           /**< should binary variables be sorted for faster propagation? */
   SCIP_Bool             checkrelmaxabs;     /**< should the violation for a constraint with side 0.0 be checked relative
                                              *   to 1.0 (FALSE) or to the maximum absolute value in the activity (TRUE)? */
   SCIP_Bool             detectcutoffbound;  /**< should presolving try to detect constraints parallel to the objective
                                              *   function defining an upper bound and prevent these constraints from
                                              *   entering the LP */
   SCIP_Bool             detectlowerbound;   /**< should presolving try to detect constraints parallel to the objective
                                              *   function defining a lower bound and prevent these constraints from
                                              *   entering the LP */
   SCIP_Bool             detectpartialobjective;/**< should presolving try to detect subsets of constraints parallel to
                                                 *   the objective function */
   SCIP_Bool             rangedrowpropagation;/**< should presolving and propagation try to improve bounds, detect
                                               *   infeasibility, and extract sub-constraints from ranged rows and
                                               *   equations */
   SCIP_Bool             rangedrowartcons;   /**< should presolving and propagation extract sub-constraints from ranged rows and equations?*/
   int                   rangedrowmaxdepth;  /**< maximum depth to apply ranged row propagation */
   int                   rangedrowfreq;      /**< frequency for applying ranged row propagation */
   SCIP_Bool             multaggrremove;     /**< should multi-aggregations only be performed if the constraint can be
                                              *   removed afterwards? */
   SCIP_Real             maxmultaggrquot;    /**< maximum coefficient dynamism (ie. maxabsval / minabsval) for primal multiaggregation */
   SCIP_Real             maxdualmultaggrquot;/**< maximum coefficient dynamism (ie. maxabsval / minabsval) for dual multiaggregation */
   SCIP_Bool             extractcliques;     /**< should cliques be extracted? */
};

/** linear constraint update method */
struct SCIP_LinConsUpgrade
{
   SCIP_DECL_LINCONSUPGD((*linconsupgd));    /**< method to call for upgrading linear constraint */
   int                   priority;           /**< priority of upgrading method */
   SCIP_Bool             active;             /**< is upgrading enabled */
};


/*
 * Propagation rules
 */

enum Proprule
{
   PROPRULE_1_RHS        = 1,                /**< activity residuals of all other variables tighten bounds of single
                                              *   variable due to the right hand side of the inequality */
   PROPRULE_1_LHS        = 2,                /**< activity residuals of all other variables tighten bounds of single
                                              *   variable due to the left hand side of the inequality */
   PROPRULE_1_RANGEDROW  = 3,                /**< fixed variables and gcd of all left variables tighten bounds of a
                                              *   single variable in this reanged row */
   PROPRULE_INVALID      = 0                 /**< propagation was applied without a specific propagation rule */
};
typedef enum Proprule PROPRULE;

/** inference information */
struct InferInfo
{
   union
   {
      struct
      {
         unsigned int    proprule:8;         /**< propagation rule that was applied */
         unsigned int    pos:24;             /**< variable position, the propagation rule was applied at */
      } asbits;
      int                asint;              /**< inference information as a single int value */
   } val;
};
typedef struct InferInfo INFERINFO;

/** converts an integer into an inference information */
static
INFERINFO intToInferInfo(
   int                   i                   /**< integer to convert */
   )
{
   INFERINFO inferinfo;

   inferinfo.val.asint = i;

   return inferinfo;
}

/** converts an inference information into an int */
static
int inferInfoToInt(
   INFERINFO             inferinfo           /**< inference information to convert */
   )
{
   return inferinfo.val.asint;
}

/** returns the propagation rule stored in the inference information */
static
int inferInfoGetProprule(
   INFERINFO             inferinfo           /**< inference information to convert */
   )
{
   return (int) inferinfo.val.asbits.proprule;
}

/** returns the position stored in the inference information */
static
int inferInfoGetPos(
   INFERINFO             inferinfo           /**< inference information to convert */
   )
{
   return (int) inferinfo.val.asbits.pos;
}

/** constructs an inference information out of a propagation rule and a position number */
static
INFERINFO getInferInfo(
   PROPRULE              proprule,           /**< propagation rule that deduced the value */
   int                   pos                 /**< variable position, the propagation rule was applied at */
   )
{
   INFERINFO inferinfo;

   assert(pos >= 0);
   /* in the inferinfo struct only 24 bits for 'pos' are reserved */
   assert(pos < (1<<24));

   inferinfo.val.asbits.proprule = (unsigned int) proprule; /*lint !e641*/
   inferinfo.val.asbits.pos = (unsigned int) pos; /*lint !e732*/

   return inferinfo;
}

/** constructs an inference information out of a propagation rule and a position number, returns info as int */
static
int getInferInt(
   PROPRULE              proprule,           /**< propagation rule that deduced the value */
   int                   pos                 /**< variable position, the propagation rule was applied at */
   )
{
   return inferInfoToInt(getInferInfo(proprule, pos));
}


/*
 * memory growing methods for dynamically allocated arrays
 */

/** ensures, that linconsupgrades array can store at least num entries */
static
SCIP_RETCODE conshdlrdataEnsureLinconsupgradesSize(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< linear constraint handler data */
   int                   num                 /**< minimum number of entries to store */
   )
{
   assert(scip != NULL);
   assert(conshdlrdata != NULL);
   assert(conshdlrdata->nlinconsupgrades <= conshdlrdata->linconsupgradessize);

   if( num > conshdlrdata->linconsupgradessize )
   {
      int newsize;

      newsize = SCIPcalcMemGrowSize(scip, num);
      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->linconsupgrades, conshdlrdata->linconsupgradessize, newsize) );
      conshdlrdata->linconsupgradessize = newsize;
   }
   assert(num <= conshdlrdata->linconsupgradessize);

   return SCIP_OKAY;
}

/** ensures, that vars and vals arrays can store at least num entries */
static
SCIP_RETCODE consdataEnsureVarsSize(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   int                   num                 /**< minimum number of entries to store */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);
   assert(consdata->nvars <= consdata->varssize);

   if( num > consdata->varssize )
   {
      int newsize;

      newsize = SCIPcalcMemGrowSize(scip, num);
      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vals, consdata->varssize, newsize) );
      if( consdata->eventdata != NULL )
      {
         SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventdata, consdata->varssize, newsize) );
      }
      consdata->varssize = newsize;
   }
   assert(num <= consdata->varssize);

   return SCIP_OKAY;
}


/*
 * local methods for managing linear constraint update methods
 */

/** creates a linear constraint upgrade data object */
static
SCIP_RETCODE linconsupgradeCreate(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_LINCONSUPGRADE** linconsupgrade,     /**< pointer to store the linear constraint upgrade */
   SCIP_DECL_LINCONSUPGD((*linconsupgd)),    /**< method to call for upgrading linear constraint */
   int                   priority            /**< priority of upgrading method */
   )
{
   assert(scip != NULL);
   assert(linconsupgrade != NULL);
   assert(linconsupgd != NULL);

   SCIP_CALL( SCIPallocBlockMemory(scip, linconsupgrade) );
   (*linconsupgrade)->linconsupgd = linconsupgd;
   (*linconsupgrade)->priority = priority;
   (*linconsupgrade)->active = TRUE;

   return SCIP_OKAY;
}

/** frees a linear constraint upgrade data object */
static
void linconsupgradeFree(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_LINCONSUPGRADE** linconsupgrade      /**< pointer to the linear constraint upgrade */
   )
{
   assert(scip != NULL);
   assert(linconsupgrade != NULL);
   assert(*linconsupgrade != NULL);

   SCIPfreeBlockMemory(scip, linconsupgrade);
}

/** creates constraint handler data for linear constraint handler */
static
SCIP_RETCODE conshdlrdataCreate(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA**   conshdlrdata,       /**< pointer to store the constraint handler data */
   SCIP_EVENTHDLR*       eventhdlr           /**< event handler */
   )
{
   assert(scip != NULL);
   assert(conshdlrdata != NULL);
   assert(eventhdlr != NULL);

   SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
   (*conshdlrdata)->linconsupgrades = NULL;
   (*conshdlrdata)->linconsupgradessize = 0;
   (*conshdlrdata)->nlinconsupgrades = 0;
   (*conshdlrdata)->naddconss = 0;

   /* set event handler for updating linear constraint activity bounds */
   (*conshdlrdata)->eventhdlr = eventhdlr;

   return SCIP_OKAY;
}

/** frees constraint handler data for linear constraint handler */
static
void conshdlrdataFree(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA**   conshdlrdata        /**< pointer to the constraint handler data */
   )
{
   int i;

   assert(scip != NULL);
   assert(conshdlrdata != NULL);
   assert(*conshdlrdata != NULL);

   for( i = 0; i < (*conshdlrdata)->nlinconsupgrades; ++i )
   {
      linconsupgradeFree(scip, &(*conshdlrdata)->linconsupgrades[i]);
   }
   SCIPfreeBlockMemoryArrayNull(scip, &(*conshdlrdata)->linconsupgrades, (*conshdlrdata)->linconsupgradessize);

   SCIPfreeBlockMemory(scip, conshdlrdata);
}

/** creates a linear constraint upgrade data object */
static
SCIP_Bool conshdlrdataHasUpgrade(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   SCIP_DECL_LINCONSUPGD((*linconsupgd)),    /**< method to call for upgrading linear constraint */
   const char*           conshdlrname        /**< name of the constraint handler */
   )
{
   int i;

   assert(scip != NULL);
   assert(conshdlrdata != NULL);
   assert(linconsupgd != NULL);
   assert(conshdlrname != NULL);

   for( i = conshdlrdata->nlinconsupgrades - 1; i >= 0; --i )
   {
      if( conshdlrdata->linconsupgrades[i]->linconsupgd == linconsupgd )
      {
#ifdef SCIP_DEBUG
         SCIPwarningMessage(scip, "Try to add already known upgrade message for constraint handler %s.\n", conshdlrname);
#endif
         return TRUE;
      }
   }

   return FALSE;
}

/** adds a linear constraint update method to the constraint handler's data */
static
SCIP_RETCODE conshdlrdataIncludeUpgrade(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   SCIP_LINCONSUPGRADE*  linconsupgrade      /**< linear constraint upgrade method */
   )
{
   int i;

   assert(scip != NULL);
   assert(conshdlrdata != NULL);
   assert(linconsupgrade != NULL);

   SCIP_CALL( conshdlrdataEnsureLinconsupgradesSize(scip, conshdlrdata, conshdlrdata->nlinconsupgrades+1) );

   for( i = conshdlrdata->nlinconsupgrades;
        i > 0 && conshdlrdata->linconsupgrades[i-1]->priority < linconsupgrade->priority; --i )
   {
      conshdlrdata->linconsupgrades[i] = conshdlrdata->linconsupgrades[i-1];
   }
   assert(0 <= i && i <= conshdlrdata->nlinconsupgrades);
   conshdlrdata->linconsupgrades[i] = linconsupgrade;
   conshdlrdata->nlinconsupgrades++;

   return SCIP_OKAY;
}

/*
 * local methods
 */

/** installs rounding locks for the given variable associated to the given coefficient in the linear constraint */
static
SCIP_RETCODE lockRounding(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   SCIP_VAR*             var,                /**< variable of constraint entry */
   SCIP_Real             val                 /**< coefficient of constraint entry */
   )
{
   SCIP_CONSDATA* consdata;

   assert(scip != NULL);
   assert(cons != NULL);
   assert(var != NULL);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(!SCIPisZero(scip, val));

   if( SCIPisPositive(scip, val) )
   {
      SCIP_CALL( SCIPlockVarCons(scip, var, cons,
         !SCIPisInfinity(scip, -consdata->lhs), !SCIPisInfinity(scip, consdata->rhs)) );
   }
   else
   {
      SCIP_CALL( SCIPlockVarCons(scip, var, cons,
         !SCIPisInfinity(scip, consdata->rhs), !SCIPisInfinity(scip, -consdata->lhs)) );
   }

   return SCIP_OKAY;
}

/** removes rounding locks for the given variable associated to the given coefficient in the linear constraint */
static
SCIP_RETCODE unlockRounding(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   SCIP_VAR*             var,                /**< variable of constraint entry */
   SCIP_Real             val                 /**< coefficient of constraint entry */
   )
{
   SCIP_CONSDATA* consdata;

   assert(scip != NULL);
   assert(cons != NULL);
   assert(var != NULL);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(!SCIPisZero(scip, val));

   if( SCIPisPositive(scip, val) )
   {
      SCIP_CALL( SCIPunlockVarCons(scip, var, cons, !SCIPisInfinity(scip, -consdata->lhs),
         !SCIPisInfinity(scip, consdata->rhs)) );
   }
   else
   {
      SCIP_CALL( SCIPunlockVarCons(scip, var, cons, !SCIPisInfinity(scip, consdata->rhs),
         !SCIPisInfinity(scip, -consdata->lhs)) );
   }

   return SCIP_OKAY;
}

/** creates event data for variable at given position, and catches events */
/**! [SnippetDebugAssertions] */
static
SCIP_RETCODE consCatchEvent(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   SCIP_EVENTHDLR*       eventhdlr,          /**< event handler to call for the event processing */
   int                   pos                 /**< array position of variable to catch bound change events for */
   )
{
   SCIP_CONSDATA* consdata;
   assert(scip != NULL);
   assert(cons != NULL);
   assert(eventhdlr != NULL);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);

   assert(0 <= pos && pos < consdata->nvars);
   assert(consdata->vars != NULL);
   assert(consdata->vars[pos] != NULL);
   assert(SCIPvarIsTransformed(consdata->vars[pos]));
   assert(consdata->eventdata != NULL);
   assert(consdata->eventdata[pos] == NULL);

   SCIP_CALL( SCIPallocBlockMemory(scip, &(consdata->eventdata[pos])) ); /*lint !e866*/
   consdata->eventdata[pos]->cons = cons;
   consdata->eventdata[pos]->varpos = pos;

   SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[pos],
         SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_VARFIXED | SCIP_EVENTTYPE_VARUNLOCKED
         | SCIP_EVENTTYPE_GBDCHANGED | SCIP_EVENTTYPE_VARDELETED | SCIP_EVENTTYPE_TYPECHANGED,
         eventhdlr, consdata->eventdata[pos], &consdata->eventdata[pos]->filterpos) );

   consdata->removedfixings = consdata->removedfixings && SCIPvarIsActive(consdata->vars[pos]);

   return SCIP_OKAY;
}
/**! [SnippetDebugAssertions] */

/** deletes event data for variable at given position, and drops events */
static
SCIP_RETCODE consDropEvent(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   SCIP_EVENTHDLR*       eventhdlr,          /**< event handler to call for the event processing */
   int                   pos                 /**< array position of variable to catch bound change events for */
   )
{
   SCIP_CONSDATA* consdata;
   assert(scip != NULL);
   assert(cons != NULL);
   assert(eventhdlr != NULL);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);

   assert(0 <= pos && pos < consdata->nvars);
   assert(consdata->vars[pos] != NULL);
   assert(consdata->eventdata != NULL);
   assert(consdata->eventdata[pos] != NULL);
   assert(consdata->eventdata[pos]->cons == cons);
   assert(consdata->eventdata[pos]->varpos == pos);

   SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos],
         SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_VARFIXED | SCIP_EVENTTYPE_VARUNLOCKED
         | SCIP_EVENTTYPE_GBDCHANGED | SCIP_EVENTTYPE_VARDELETED | SCIP_EVENTTYPE_TYPECHANGED,
         eventhdlr, consdata->eventdata[pos], consdata->eventdata[pos]->filterpos) );

   SCIPfreeBlockMemory(scip, &consdata->eventdata[pos]); /*lint !e866*/

   return SCIP_OKAY;
}

/** catches bound change events for all variables in transformed linear constraint */
static
SCIP_RETCODE consCatchAllEvents(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   SCIP_EVENTHDLR*       eventhdlr           /**< event handler to call for the event processing */
   )
{
   SCIP_CONSDATA* consdata;
   int i;

   assert(scip != NULL);
   assert(cons != NULL);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(consdata->eventdata == NULL);

   /* allocate eventdata array */
   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdata, consdata->varssize) );
   assert(consdata->eventdata != NULL);
   BMSclearMemoryArray(consdata->eventdata, consdata->nvars);

   /* catch event for every single variable */
   for( i = 0; i < consdata->nvars; ++i )
   {
      SCIP_CALL( consCatchEvent(scip, cons, eventhdlr, i) );
   }

   return SCIP_OKAY;
}

/** drops bound change events for all variables in transformed linear constraint */
static
SCIP_RETCODE consDropAllEvents(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   SCIP_EVENTHDLR*       eventhdlr           /**< event handler to call for the event processing */
   )
{
   SCIP_CONSDATA* consdata;
   int i;

   assert(scip != NULL);
   assert(cons != NULL);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(consdata->eventdata != NULL);

   /* drop event of every single variable */
   for( i = consdata->nvars - 1; i >= 0; --i )
   {
      SCIP_CALL( consDropEvent(scip, cons, eventhdlr, i) );
   }

   /* free eventdata array */
   SCIPfreeBlockMemoryArray(scip, &consdata->eventdata, consdata->varssize);
   assert(consdata->eventdata == NULL);

   return SCIP_OKAY;
}

/** creates a linear constraint data */
static
SCIP_RETCODE consdataCreate(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA**       consdata,           /**< pointer to linear constraint data */
   int                   nvars,              /**< number of nonzeros in the constraint */
   SCIP_VAR**            vars,               /**< array with variables of constraint entries */
   SCIP_Real*            vals,               /**< array with coefficients of constraint entries */
   SCIP_Real             lhs,                /**< left hand side of row */
   SCIP_Real             rhs                 /**< right hand side of row */
   )
{
   int v;
   SCIP_Real constant;

   assert(scip != NULL);
   assert(consdata != NULL);
   assert(nvars == 0 || vars != NULL);
   assert(nvars == 0 || vals != NULL);

   if( SCIPisInfinity(scip, rhs) )
      rhs = SCIPinfinity(scip);
   else if( SCIPisInfinity(scip, -rhs) )
      rhs = -SCIPinfinity(scip);

   if( SCIPisInfinity(scip, -lhs) )
      lhs = -SCIPinfinity(scip);
   else if( SCIPisInfinity(scip, lhs) )
      lhs = SCIPinfinity(scip);

   if( SCIPisGT(scip, lhs, rhs) )
   {
      SCIPwarningMessage(scip, "left hand side of linear constraint greater than right hand side\n");
      SCIPwarningMessage(scip, " -> lhs=%g, rhs=%g\n", lhs, rhs);
   }

   SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );

   (*consdata)->varssize = 0;
   (*consdata)->nvars = nvars;
   (*consdata)->hascontvar = FALSE;
   (*consdata)->hasnonbinvar = FALSE;
   (*consdata)->hasnonbinvalid = TRUE;
   (*consdata)->vars = NULL;
   (*consdata)->vals = NULL;

   constant = 0.0;
   if( nvars > 0 )
   {
      int k;

      SCIP_VAR** varsbuffer;
      SCIP_Real* valsbuffer;

      /* copy variables into temporary buffer */
      SCIP_CALL( SCIPallocBufferArray(scip, &varsbuffer, nvars) );
      SCIP_CALL( SCIPallocBufferArray(scip, &valsbuffer, nvars) );
      k = 0;

      /* loop over variables and sort out fixed ones */
      for( v = 0; v < nvars; ++v )
      {
         SCIP_VAR* var;
         SCIP_Real val;

         var = vars[v];
         val = vals[v];

         assert(var != NULL);
         if( !SCIPisZero(scip, val) )
         {
            /* treat fixed variable as a constant if problem compression is enabled */
            if( SCIPisConsCompressionEnabled(scip) && SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)) )
            {
               constant += SCIPvarGetLbGlobal(var) * val;
            }
            else
            {
               varsbuffer[k] = var;
               valsbuffer[k] = val;
               k++;

               /* update hascontvar and hasnonbinvar flags */
               if( !(*consdata)->hascontvar )
               {
                  SCIP_VARTYPE vartype = SCIPvarGetType(var);

                  if( vartype != SCIP_VARTYPE_BINARY )
                  {
                     (*consdata)->hasnonbinvar = TRUE;

                     if( vartype == SCIP_VARTYPE_CONTINUOUS )
                        (*consdata)->hascontvar = TRUE;
                  }
               }
            }
         }
      }
      (*consdata)->nvars = k;

      if( k > 0 )
      {
         /* copy the possibly reduced buffer arrays into block */
         SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, varsbuffer, k) );
         SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vals, valsbuffer, k) );
         (*consdata)->varssize = k;
      }
      /* free temporary buffer */
      SCIPfreeBufferArray(scip, &valsbuffer);
      SCIPfreeBufferArray(scip, &varsbuffer);
   }

   (*consdata)->eventdata = NULL;

   /* due to compressed copying, we may have fixed variables contributing to the left and right hand side */
   if( !SCIPisZero(scip, constant) )
   {
      if( !SCIPisInfinity(scip, REALABS(lhs)) )
         lhs -= constant;

      if( !SCIPisInfinity(scip, REALABS(rhs)) )
         rhs -= constant;
   }

   (*consdata)->row = NULL;
   (*consdata)->nlrow = NULL;
   (*consdata)->lhs = lhs;
   (*consdata)->rhs = rhs;
   (*consdata)->maxabsval = SCIP_INVALID;
   (*consdata)->minabsval = SCIP_INVALID;
   QUAD_ASSIGN((*consdata)->minactivity, SCIP_INVALID);
   QUAD_ASSIGN((*consdata)->maxactivity, SCIP_INVALID);
   (*consdata)->lastminactivity = SCIP_INVALID;
   (*consdata)->lastmaxactivity = SCIP_INVALID;
   (*consdata)->maxactdelta = SCIP_INVALID;
   (*consdata)->maxactdeltavar = NULL;
   (*consdata)->minactivityneginf = -1;
   (*consdata)->minactivityposinf = -1;
   (*consdata)->maxactivityneginf = -1;
   (*consdata)->maxactivityposinf = -1;
   (*consdata)->minactivityneghuge = -1;
   (*consdata)->minactivityposhuge = -1;
   (*consdata)->maxactivityneghuge = -1;
   (*consdata)->maxactivityposhuge = -1;
   QUAD_ASSIGN((*consdata)->glbminactivity, SCIP_INVALID);
   QUAD_ASSIGN((*consdata)->glbmaxactivity, SCIP_INVALID);
   (*consdata)->lastglbminactivity = SCIP_INVALID;
   (*consdata)->lastglbmaxactivity = SCIP_INVALID;
   (*consdata)->glbminactivityneginf = -1;
   (*consdata)->glbminactivityposinf = -1;
   (*consdata)->glbmaxactivityneginf = -1;
   (*consdata)->glbmaxactivityposinf = -1;
   (*consdata)->glbminactivityneghuge = -1;
   (*consdata)->glbminactivityposhuge = -1;
   (*consdata)->glbmaxactivityneghuge = -1;
   (*consdata)->glbmaxactivityposhuge = -1;
   (*consdata)->possignature = 0;
   (*consdata)->negsignature = 0;
   (*consdata)->validmaxabsval = FALSE;
   (*consdata)->validminabsval = FALSE;
   (*consdata)->validactivities = FALSE;
   (*consdata)->validminact = FALSE;
   (*consdata)->validmaxact = FALSE;
   (*consdata)->validglbminact = FALSE;
   (*consdata)->validglbmaxact = FALSE;
   (*consdata)->boundstightened = 0;
   (*consdata)->presolved = FALSE;
   (*consdata)->removedfixings = FALSE;
   (*consdata)->validsignature = FALSE;
   (*consdata)->changed = TRUE;
   (*consdata)->normalized = FALSE;
   (*consdata)->upgradetried = FALSE;
   (*consdata)->upgraded = FALSE;
   (*consdata)->indexsorted = (nvars <= 1);
   (*consdata)->merged = (nvars <= 1);
   (*consdata)->cliquesadded = FALSE;
   (*consdata)->implsadded = FALSE;
   (*consdata)->coefsorted = FALSE;
   (*consdata)->nbinvars = -1;
   (*consdata)->varsdeleted = FALSE;
   (*consdata)->rangedrowpropagated = 0;
   (*consdata)->checkabsolute = FALSE;

   if( SCIPisTransformed(scip) )
   {
      /* get transformed variables */
      SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
   }

   /* capture variables */
   for( v = 0; v < (*consdata)->nvars; v++ )
   {
      /* likely implies a deleted variable */
      if( (*consdata)->vars[v] == NULL )
      {
         SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->varssize);
         SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vals, (*consdata)->varssize);
         SCIPfreeBlockMemory(scip, consdata);
         return SCIP_INVALIDDATA;
      }

      assert(!SCIPisZero(scip, (*consdata)->vals[v]));
      SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
   }

   return SCIP_OKAY;
}

/** frees a linear constraint data */
static
SCIP_RETCODE consdataFree(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA**       consdata            /**< pointer to linear constraint data */
   )
{
   int v;

   assert(scip != NULL);
   assert(consdata != NULL);
   assert(*consdata != NULL);
   assert((*consdata)->varssize >= 0);

   /* release the row */
   if( (*consdata)->row != NULL )
   {
      SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row) );
   }

   /* release the nlrow */
   if( (*consdata)->nlrow != NULL )
   {
      SCIP_CALL( SCIPreleaseNlRow(scip, &(*consdata)->nlrow) );
   }

   /* release variables */
   for( v = 0; v < (*consdata)->nvars; v++ )
   {
      assert((*consdata)->vars[v] != NULL);
      assert(!SCIPisZero(scip, (*consdata)->vals[v]));
      SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->vars[v])) );
   }

   SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->varssize);
   SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vals, (*consdata)->varssize);
   SCIPfreeBlockMemory(scip, consdata);

   return SCIP_OKAY;
}

/** prints linear constraint in CIP format to file stream */
static
SCIP_RETCODE consdataPrint(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   FILE*                 file                /**< output file (or NULL for standard output) */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);

   /* print left hand side for ranged rows */
   if( !SCIPisInfinity(scip, -consdata->lhs)
      && !SCIPisInfinity(scip, consdata->rhs)
      && !SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
      SCIPinfoMessage(scip, file, "%.15g <= ", consdata->lhs);

   /* print coefficients and variables */
   if( consdata->nvars == 0 )
      SCIPinfoMessage(scip, file, "0");
   else
   {
      /* post linear sum of the linear constraint */
      SCIP_CALL( SCIPwriteVarsLinearsum(scip, file, consdata->vars, consdata->vals, consdata->nvars, TRUE) );
   }

   /* print right hand side */
   if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
      SCIPinfoMessage(scip, file, " == %.15g", consdata->rhs);
   else if( !SCIPisInfinity(scip, consdata->rhs) )
      SCIPinfoMessage(scip, file, " <= %.15g", consdata->rhs);
   else if( !SCIPisInfinity(scip, -consdata->lhs) )
      SCIPinfoMessage(scip, file, " >= %.15g", consdata->lhs);
   else
      SCIPinfoMessage(scip, file, " [free]");

   return SCIP_OKAY;
}

/** prints linear constraint and contained solution values of variables to file stream */
static
SCIP_RETCODE consPrintConsSol(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   SCIP_SOL*             sol,                /**< solution to print */
   FILE*                 file                /**< output file (or NULL for standard output) */
   )
{
   SCIP_CONSDATA* consdata;

   assert(scip != NULL);
   assert(cons != NULL);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);

   SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "  [%s] <%s>: ", SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), SCIPconsGetName(cons));

   /* print left hand side for ranged rows */
   if( !SCIPisInfinity(scip, -consdata->lhs)
      && !SCIPisInfinity(scip, consdata->rhs)
      && !SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
      SCIPinfoMessage(scip, file, "%.15g <= ", consdata->lhs);

   /* print coefficients and variables */
   if( consdata->nvars == 0 )
      SCIPinfoMessage(scip, file, "0");
   else
   {
      int v;

      /* post linear sum of the linear constraint */
      for( v = 0; v < consdata->nvars; ++v )
      {
         if( consdata->vals != NULL )
         {
            if( consdata->vals[v] == 1.0 )
            {
               if( v > 0 )
                  SCIPinfoMessage(scip, file, " +");
            }
            else if( consdata->vals[v] == -1.0 )
               SCIPinfoMessage(scip, file, " -");
            else
               SCIPinfoMessage(scip, file, " %+.9g", consdata->vals[v]);
         }
         else if( consdata->nvars > 0 )
            SCIPinfoMessage(scip, file, " +");

         /* print variable name */
         SCIP_CALL( SCIPwriteVarName(scip, file, consdata->vars[v], TRUE) );

         SCIPinfoMessage(scip, file, " (%+.9g)", SCIPgetSolVal(scip, sol, consdata->vars[v]));
      }
   }

   /* print right hand side */
   if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
      SCIPinfoMessage(scip, file, " == %.15g", consdata->rhs);
   else if( !SCIPisInfinity(scip, consdata->rhs) )
      SCIPinfoMessage(scip, file, " <= %.15g", consdata->rhs);
   else if( !SCIPisInfinity(scip, -consdata->lhs) )
      SCIPinfoMessage(scip, file, " >= %.15g", consdata->lhs);
   else
      SCIPinfoMessage(scip, file, " [free]");

   SCIPinfoMessage(scip, file, ";\n");

   return SCIP_OKAY;
}

/** invalidates activity bounds, such that they are recalculated in next get */
static
void consdataInvalidateActivities(
   SCIP_CONSDATA*        consdata            /**< linear constraint */
   )
{
   assert(consdata != NULL);

   consdata->validactivities = FALSE;
   consdata->validminact = FALSE;
   consdata->validmaxact = FALSE;
   consdata->validglbminact = FALSE;
   consdata->validglbmaxact = FALSE;
   consdata->validmaxabsval = FALSE;
   consdata->validminabsval = FALSE;
   consdata->hasnonbinvalid = FALSE;
   QUAD_ASSIGN(consdata->minactivity, SCIP_INVALID);
   QUAD_ASSIGN(consdata->maxactivity, SCIP_INVALID);
   consdata->lastminactivity = SCIP_INVALID;
   consdata->lastmaxactivity = SCIP_INVALID;
   consdata->maxabsval = SCIP_INVALID;
   consdata->minabsval = SCIP_INVALID;
   consdata->maxactdelta = SCIP_INVALID;
   consdata->maxactdeltavar = NULL;
   consdata->minactivityneginf = -1;
   consdata->minactivityposinf = -1;
   consdata->maxactivityneginf = -1;
   consdata->maxactivityposinf = -1;
   consdata->minactivityneghuge = -1;
   consdata->minactivityposhuge = -1;
   consdata->maxactivityneghuge = -1;
   consdata->maxactivityposhuge = -1;
   QUAD_ASSIGN(consdata->glbminactivity, SCIP_INVALID);
   QUAD_ASSIGN(consdata->glbmaxactivity, SCIP_INVALID);
   consdata->lastglbminactivity = SCIP_INVALID;
   consdata->lastglbmaxactivity = SCIP_INVALID;
   consdata->glbminactivityneginf = -1;
   consdata->glbminactivityposinf = -1;
   consdata->glbmaxactivityneginf = -1;
   consdata->glbmaxactivityposinf = -1;
   consdata->glbminactivityneghuge = -1;
   consdata->glbminactivityposhuge = -1;
   consdata->glbmaxactivityneghuge = -1;
   consdata->glbmaxactivityposhuge = -1;
}

/** compute the pseudo activity of a constraint */
static
SCIP_Real consdataComputePseudoActivity(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   int i;
   int pseudoactivityposinf;
   int pseudoactivityneginf;
   SCIP_Real pseudoactivity;
   SCIP_Real bound;
   SCIP_Real val;

   pseudoactivity = 0;
   pseudoactivityposinf = 0;
   pseudoactivityneginf = 0;

   for( i = consdata->nvars - 1; i >= 0; --i )
   {
      val = consdata->vals[i];
      bound = (SCIPvarGetBestBoundType(consdata->vars[i]) == SCIP_BOUNDTYPE_LOWER) ? SCIPvarGetLbLocal(consdata->vars[i]) : SCIPvarGetUbLocal(consdata->vars[i]);
      if( SCIPisInfinity(scip, bound) )
      {
         if( val > 0.0 )
            pseudoactivityposinf++;
         else
            pseudoactivityneginf++;
      }
      else
      {
         if( SCIPisInfinity(scip, -bound) )
         {
            if( val > 0.0 )
               pseudoactivityneginf++;
            else
               pseudoactivityposinf++;
         }
         else
            pseudoactivity += val * bound;
      }
   }

   if( pseudoactivityneginf > 0 && pseudoactivityposinf > 0 )
      return SCIP_INVALID;
   else if( pseudoactivityneginf > 0 )
      return -SCIPinfinity(scip);
   else if( pseudoactivityposinf > 0 )
      return SCIPinfinity(scip);

   return pseudoactivity;
}

/** recompute the minactivity of a constraint */
static
void consdataRecomputeMinactivity(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   int i;
   SCIP_Real bound;

   QUAD_ASSIGN(consdata->minactivity, 0.0);

   for( i = consdata->nvars - 1; i >= 0; --i )
   {
      bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetLbLocal(consdata->vars[i]) : SCIPvarGetUbLocal(consdata->vars[i]);
      if( !SCIPisInfinity(scip, bound) && !SCIPisInfinity(scip, -bound)
         && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
         SCIPquadprecSumQD(consdata->minactivity, consdata->minactivity, consdata->vals[i] * bound);
   }

   /* the activity was just computed from scratch and is valid now */
   consdata->validminact = TRUE;

   /* the activity was just computed from scratch, mark it to be reliable */
   consdata->lastminactivity = QUAD_TO_DBL(consdata->minactivity);
}

/** recompute the maxactivity of a constraint */
static
void consdataRecomputeMaxactivity(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   int i;
   SCIP_Real bound;

   QUAD_ASSIGN(consdata->maxactivity, 0.0);

   for( i = consdata->nvars - 1; i >= 0; --i )
   {
      bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetUbLocal(consdata->vars[i]) : SCIPvarGetLbLocal(consdata->vars[i]);
      if( !SCIPisInfinity(scip, bound) && !SCIPisInfinity(scip, -bound)
         && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
         SCIPquadprecSumQD(consdata->maxactivity, consdata->maxactivity, consdata->vals[i] * bound);
   }

   /* the activity was just computed from scratch and is valid now */
   consdata->validmaxact = TRUE;

   /* the activity was just computed from scratch, mark it to be reliable */
   consdata->lastmaxactivity = QUAD_TO_DBL(consdata->maxactivity);
}

/** recompute the global minactivity of a constraint */
static
void consdataRecomputeGlbMinactivity(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   int i;
   SCIP_Real bound;

   QUAD_ASSIGN(consdata->glbminactivity, 0.0);

   for( i = consdata->nvars - 1; i >= 0; --i )
   {
      bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetLbGlobal(consdata->vars[i]) : SCIPvarGetUbGlobal(consdata->vars[i]);
      if( !SCIPisInfinity(scip, bound) && !SCIPisInfinity(scip, -bound)
         && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
         SCIPquadprecSumQD(consdata->glbminactivity, consdata->glbminactivity, consdata->vals[i] * bound);
   }

   /* the activity was just computed from scratch and is valid now */
   consdata->validglbminact = TRUE;

   /* the activity was just computed from scratch, mark it to be reliable */
   consdata->lastglbminactivity = QUAD_TO_DBL(consdata->glbminactivity);
}

/** recompute the global maxactivity of a constraint */
static
void consdataRecomputeGlbMaxactivity(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   int i;
   SCIP_Real bound;

   QUAD_ASSIGN(consdata->glbmaxactivity, 0.0);

   for( i = consdata->nvars - 1; i >= 0; --i )
   {
      bound = (consdata->vals[i] > 0.0 ) ? SCIPvarGetUbGlobal(consdata->vars[i]) : SCIPvarGetLbGlobal(consdata->vars[i]);
      if( !SCIPisInfinity(scip, bound) && !SCIPisInfinity(scip, -bound)
         && !SCIPisHugeValue(scip, consdata->vals[i] * bound) && !SCIPisHugeValue(scip, -consdata->vals[i] * bound) )
         SCIPquadprecSumQD(consdata->glbmaxactivity, consdata->glbmaxactivity, consdata->vals[i] * bound);
   }

   /* the activity was just computed from scratch and is valid now */
   consdata->validglbmaxact = TRUE;

   /* the activity was just computed from scratch, mark it to be reliable */
   consdata->lastglbmaxactivity = QUAD_TO_DBL(consdata->glbmaxactivity);
}

/** calculates maximum absolute value of coefficients */
static
void consdataCalcMaxAbsval(
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   SCIP_Real absval;
   int i;

   assert(consdata != NULL);
   assert(!consdata->validmaxabsval);
   assert(consdata->maxabsval >= SCIP_INVALID);

   consdata->validmaxabsval = TRUE;
   consdata->maxabsval = 0.0;
   for( i = 0; i < consdata->nvars; ++i )
   {
      absval = consdata->vals[i];
      absval = REALABS(absval);
      if( absval > consdata->maxabsval )
         consdata->maxabsval = absval;
   }
}

/** calculates minimum absolute value of coefficients */
static
void consdataCalcMinAbsval(
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   SCIP_Real absval;
   int i;

   assert(consdata != NULL);
   assert(!consdata->validminabsval);
   assert(consdata->minabsval >= SCIP_INVALID);

   consdata->validminabsval = TRUE;

   if( consdata->nvars > 0 )
      consdata->minabsval = REALABS(consdata->vals[0]);
   else
      consdata->minabsval = 0.0;

   for( i = 1; i < consdata->nvars; ++i )
   {
      absval = consdata->vals[i];
      absval = REALABS(absval);
      if( absval < consdata->minabsval )
         consdata->minabsval = absval;
   }
}

/** checks the type of all variables of the constraint and sets hasnonbinvar and hascontvar flags accordingly */
static
void consdataCheckNonbinvar(
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   int v;

   assert(!consdata->hasnonbinvalid);
   consdata->hasnonbinvar = FALSE;
   consdata->hascontvar = FALSE;

   for( v = consdata->nvars - 1; v >= 0; --v )
   {
      SCIP_VARTYPE vartype = SCIPvarGetType(consdata->vars[v]);

      if( vartype != SCIP_VARTYPE_BINARY )
      {
         consdata->hasnonbinvar = TRUE;

         if( vartype == SCIP_VARTYPE_CONTINUOUS )
         {
            consdata->hascontvar = TRUE;
            break;
         }
      }
   }
   assert(consdata->hascontvar || v < 0);

   consdata->hasnonbinvalid = TRUE;
}


#ifdef CHECKMAXACTDELTA
/** checks that the stored maximal activity delta (if not invalid) is correct */
static
void checkMaxActivityDelta(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   if( consdata->maxactdelta != SCIP_INVALID )
   {
      SCIP_Real maxactdelta = 0.0;
      SCIP_Real domain;
      SCIP_Real delta;
      SCIP_Real lb;
      SCIP_Real ub;
      int v;

      for( v = consdata->nvars - 1; v >= 0; --v )
      {
         lb = SCIPvarGetLbLocal(consdata->vars[v]);
         ub = SCIPvarGetUbLocal(consdata->vars[v]);

         if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
         {
            maxactdelta = SCIPinfinity(scip);
            break;
         }

         domain = ub - lb;
         delta = REALABS(consdata->vals[v]) * domain;

         if( delta > maxactdelta )
         {
            maxactdelta = delta;
         }
      }
      assert(SCIPisFeasEQ(scip, maxactdelta, consdata->maxactdelta));
   }
}
#else
#define checkMaxActivityDelta(scip, consdata) /**/
#endif

/** recompute maximal activity contribution for a single variable */
static
void consdataRecomputeMaxActivityDelta(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   SCIP_Real delta;
   int v;

   consdata->maxactdelta = 0.0;

   if( !consdata->hasnonbinvalid )
      consdataCheckNonbinvar(consdata);

   /* easy case, the problem consists only of binary variables */
   if( !consdata->hasnonbinvar )
   {
      for( v = consdata->nvars - 1; v >= 0; --v )
      {
         if( SCIPvarGetLbLocal(consdata->vars[v]) < 0.5 && SCIPvarGetUbLocal(consdata->vars[v]) > 0.5 )
         {
            delta = REALABS(consdata->vals[v]);

            if( delta > consdata->maxactdelta )
            {
               consdata->maxactdelta = delta;
               consdata->maxactdeltavar = consdata->vars[v];
            }
         }
      }
      return;
   }

   for( v = consdata->nvars - 1; v >= 0; --v )
   {
      SCIP_Real domain;
      SCIP_Real lb;
      SCIP_Real ub;

      lb = SCIPvarGetLbLocal(consdata->vars[v]);
      ub = SCIPvarGetUbLocal(consdata->vars[v]);

      if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
      {
         consdata->maxactdelta = SCIPinfinity(scip);
         consdata->maxactdeltavar = consdata->vars[v];
         break;
      }

      domain = ub - lb;
      delta = REALABS(consdata->vals[v]) * domain;

      if( delta > consdata->maxactdelta )
      {
         consdata->maxactdelta = delta;
         consdata->maxactdeltavar = consdata->vars[v];
      }
   }
}


/** updates activities for a change in a bound */
static
void consdataUpdateActivities(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   SCIP_VAR*             var,                /**< variable that has been changed; can be NULL for global bound changes */
   SCIP_Real             oldbound,           /**< old bound of variable */
   SCIP_Real             newbound,           /**< new bound of variable */
   SCIP_Real             val,                /**< coefficient of constraint entry */
   SCIP_BOUNDTYPE        boundtype,          /**< type of the bound change */
   SCIP_Bool             global,             /**< is it a global or a local bound change? */
   SCIP_Bool             checkreliability    /**< should the reliability of the recalculated activity be checked? */
   )
{
   QUAD_MEMBER(SCIP_Real* activity);
   SCIP_Real* lastactivity;
   int* activityposinf;
   int* activityneginf;
   int* activityposhuge;
   int* activityneghuge;
   SCIP_Real oldcontribution;
   SCIP_Real newcontribution;
   SCIP_Real delta;
   SCIP_Bool validact;
   SCIP_Bool finitenewbound;
   SCIP_Bool hugevalnewcont;

   assert(scip != NULL);
   assert(consdata != NULL);
   assert(global || (var != NULL));
   assert(consdata->validactivities);
   assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
   assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
   assert(consdata->lastminactivity < SCIP_INVALID);
   assert(consdata->lastmaxactivity < SCIP_INVALID);
   assert(consdata->minactivityneginf >= 0);
   assert(consdata->minactivityposinf >= 0);
   assert(consdata->maxactivityneginf >= 0);
   assert(consdata->maxactivityposinf >= 0);
   assert(consdata->minactivityneghuge >= 0);
   assert(consdata->minactivityposhuge >= 0);
   assert(consdata->maxactivityneghuge >= 0);
   assert(consdata->maxactivityposhuge >= 0);
   assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
   assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
   assert(consdata->lastglbminactivity < SCIP_INVALID);
   assert(consdata->lastglbmaxactivity < SCIP_INVALID);
   assert(consdata->glbminactivityneginf >= 0);
   assert(consdata->glbminactivityposinf >= 0);
   assert(consdata->glbmaxactivityneginf >= 0);
   assert(consdata->glbmaxactivityposinf >= 0);
   assert(consdata->glbminactivityneghuge >= 0);
   assert(consdata->glbminactivityposhuge >= 0);
   assert(consdata->glbmaxactivityneghuge >= 0);
   assert(consdata->glbmaxactivityposhuge >= 0);

   delta = 0.0;

   /* we are updating global activities */
   if( global )
   {
      /* depending on the boundtype and the coefficient, we choose the activity to be updated:
       * lower bound + pos. coef: update minactivity
       * lower bound + neg. coef: update maxactivity, positive and negative infinity counters have to be switched
       * upper bound + pos. coef: update maxactivity
       * upper bound + neg. coef: update minactivity, positive and negative infinity counters have to be switched
       */
      if( boundtype == SCIP_BOUNDTYPE_LOWER )
      {
         if( val > 0.0 )
         {
            QUAD_ASSIGN_Q(activity, &consdata->glbminactivity);
            lastactivity = &(consdata->lastglbminactivity);
            activityposinf = &(consdata->glbminactivityposinf);
            activityneginf = &(consdata->glbminactivityneginf);
            activityposhuge = &(consdata->glbminactivityposhuge);
            activityneghuge = &(consdata->glbminactivityneghuge);
            validact = consdata->validglbminact;
         }
         else
         {
            QUAD_ASSIGN_Q(activity, &consdata->glbmaxactivity);
            lastactivity = &(consdata->lastglbmaxactivity);
            activityposinf = &(consdata->glbmaxactivityneginf);
            activityneginf = &(consdata->glbmaxactivityposinf);
            activityposhuge = &(consdata->glbmaxactivityposhuge);
            activityneghuge = &(consdata->glbmaxactivityneghuge);
            validact = consdata->validglbmaxact;
         }
      }
      else
      {
         if( val > 0.0 )
         {
            QUAD_ASSIGN_Q(activity, &consdata->glbmaxactivity);
            lastactivity = &(consdata->lastglbmaxactivity);
            activityposinf = &(consdata->glbmaxactivityposinf);
            activityneginf = &(consdata->glbmaxactivityneginf);
            activityposhuge = &(consdata->glbmaxactivityposhuge);
            activityneghuge = &(consdata->glbmaxactivityneghuge);
            validact = consdata->validglbmaxact;
         }
         else
         {
            QUAD_ASSIGN_Q(activity, &consdata->glbminactivity);
            lastactivity = &(consdata->lastglbminactivity);
            activityposinf = &(consdata->glbminactivityneginf);
            activityneginf = &(consdata->glbminactivityposinf);
            activityposhuge = &(consdata->glbminactivityposhuge);
            activityneghuge = &(consdata->glbminactivityneghuge);
            validact = consdata->validglbminact;
         }
      }
   }
   /* we are updating local activities */
   else
   {
      /* depending on the boundtype and the coefficient, we choose the activity to be updated:
       * lower bound + pos. coef: update minactivity
       * lower bound + neg. coef: update maxactivity, positive and negative infinity counters have to be switched
       * upper bound + pos. coef: update maxactivity
       * upper bound + neg. coef: update minactivity, positive and negative infinity counters have to be switched
       */
      if( boundtype == SCIP_BOUNDTYPE_LOWER )
      {
         if( val > 0.0 )
         {
            QUAD_ASSIGN_Q(activity, &consdata->minactivity);
            lastactivity = &(consdata->lastminactivity);
            activityposinf = &(consdata->minactivityposinf);
            activityneginf = &(consdata->minactivityneginf);
            activityposhuge = &(consdata->minactivityposhuge);
            activityneghuge = &(consdata->minactivityneghuge);
            validact = consdata->validminact;
         }
         else
         {
            QUAD_ASSIGN_Q(activity, &consdata->maxactivity);
            lastactivity = &(consdata->lastmaxactivity);
            activityposinf = &(consdata->maxactivityneginf);
            activityneginf = &(consdata->maxactivityposinf);
            activityposhuge = &(consdata->maxactivityposhuge);
            activityneghuge = &(consdata->maxactivityneghuge);
            validact = consdata->validmaxact;
         }
      }
      else
      {
         if( val > 0.0 )
         {
            QUAD_ASSIGN_Q(activity, &consdata->maxactivity);
            lastactivity = &(consdata->lastmaxactivity);
            activityposinf = &(consdata->maxactivityposinf);
            activityneginf = &(consdata->maxactivityneginf);
            activityposhuge = &(consdata->maxactivityposhuge);
            activityneghuge = &(consdata->maxactivityneghuge);
            validact = consdata->validmaxact;
         }
         else
         {
            QUAD_ASSIGN_Q(activity, &consdata->minactivity);
            lastactivity = &(consdata->lastminactivity);
            activityposinf = &(consdata->minactivityneginf);
            activityneginf = &(consdata->minactivityposinf);
            activityposhuge = &(consdata->minactivityposhuge);
            activityneghuge = &(consdata->minactivityneghuge);
            validact = consdata->validminact;
         }
      }
   }

   oldcontribution = val * oldbound;
   newcontribution = val * newbound;
   hugevalnewcont = SCIPisHugeValue(scip, REALABS(newcontribution));
   finitenewbound = !SCIPisInfinity(scip, REALABS(newbound));

   if( SCIPisInfinity(scip, REALABS(oldbound)) )
   {
      /* old bound was +infinity */
      if( oldbound > 0.0 )
      {
         assert((*activityposinf) >= 1);

         /* we only have to do something if the new bound is not again +infinity */
         if( finitenewbound || newbound < 0.0 )
         {
            /* decrease the counter for positive infinite contributions */
            (*activityposinf)--;

            /* if the bound changed to -infinity, increase the counter for negative infinite contributions */
            if( !finitenewbound && newbound < 0.0 )
               (*activityneginf)++;
            else if( hugevalnewcont )
            {
               /* if the contribution of this variable is too large, increase the counter for huge values */
               if( newcontribution > 0.0 )
                  (*activityposhuge)++;
               else
                  (*activityneghuge)++;
            }
            /* "normal case": just add the contribution to the activity */
            else
               delta = newcontribution;
         }
      }
      /* old bound was -infinity */
      else
      {
         assert(oldbound < 0.0);
         assert((*activityneginf) >= 1);

         /* we only have to do something ig the new bound is not again -infinity */
         if( finitenewbound || newbound > 0.0 )
         {
            /* decrease the counter for negative infinite contributions */
            (*activityneginf)--;

            /* if the bound changed to +infinity, increase the counter for positive infinite contributions */
            if( !finitenewbound && newbound > 0.0 )
               (*activityposinf)++;
            else if( hugevalnewcont )
            {
               /* if the contribution of this variable is too large, increase the counter for huge values */
               if( newcontribution > 0.0 )
                  (*activityposhuge)++;
               else
                  (*activityneghuge)++;
            }
            /* "normal case": just add the contribution to the activity */
            else
               delta = newcontribution;
         }
      }
   }
   else if( SCIPisHugeValue(scip, REALABS(oldcontribution)) )
   {
      /* old contribution was too large and positive */
      if( oldcontribution > 0.0 )
      {
         assert((*activityposhuge) >= 1);

         /* decrease the counter for huge positive contributions; it might be increased again later,
          * but checking here that the bound is not huge again would not handle a change from a huge to an infinite bound
          */
         (*activityposhuge)--;

         if( !finitenewbound )
         {
            /* if the bound changed to +infinity, increase the counter for positive infinite contributions */
            if( newbound > 0.0 )
               (*activityposinf)++;
            /* if the bound changed to -infinity, increase the counter for negative infinite contributions */
            else
               (*activityneginf)++;
         }
         else if( hugevalnewcont )
         {
            /* if the contribution of this variable is too large and positive, increase the corresponding counter */
            if( newcontribution > 0.0 )
               (*activityposhuge)++;
            /* if the contribution of this variable is too large and negative, increase the corresponding counter */
            else
               (*activityneghuge)++;
         }
         /* "normal case": just add the contribution to the activity */
         else
            delta = newcontribution;
      }
      /* old contribution was too large and negative */
      else
      {
         assert(oldcontribution < 0.0);
         assert((*activityneghuge) >= 1);

         /* decrease the counter for huge negative contributions; it might be increased again later,
          * but checking here that the bound is not huge again would not handle a change from a huge to an infinite bound
          */
         (*activityneghuge)--;

         if( !finitenewbound )
         {
            /* if the bound changed to +infinity, increase the counter for positive infinite contributions */
            if( newbound > 0.0 )
               (*activityposinf)++;
            /* if the bound changed to -infinity, increase the counter for negative infinite contributions */
            else
               (*activityneginf)++;
         }
         else if( hugevalnewcont )
         {
            /* if the contribution of this variable is too large and positive, increase the corresponding counter */
            if( newcontribution > 0.0 )
               (*activityposhuge)++;
            /* if the contribution of this variable is too large and negative, increase the corresponding counter */
            else
               (*activityneghuge)++;
         }
         /* "normal case": just add the contribution to the activity */
         else
            delta = newcontribution;
      }
   }
   /* old bound was finite and not too large */
   else
   {
      if( !finitenewbound )
      {
         /* if the new bound is +infinity, the old contribution has to be subtracted
          * and the counter for positive infinite contributions has to be increased
          */
         if( newbound > 0.0 )
         {
            (*activityposinf)++;
            delta = -oldcontribution;
         }
         /* if the new bound is -infinity, the old contribution has to be subtracted
          * and the counter for negative infinite contributions has to be increased
          */
         else
         {
            assert(newbound < 0.0 );

            (*activityneginf)++;
            delta = -oldcontribution;
         }
      }
      /* if the contribution of this variable is too large, increase the counter for huge values */
      else if( hugevalnewcont )
      {
         if( newcontribution > 0.0 )
         {
            (*activityposhuge)++;
            delta = -oldcontribution;
         }
         else
         {
            (*activityneghuge)++;
            delta = -oldcontribution;
         }
      }
      /* "normal case": just update the activity */
      else
         delta = newcontribution - oldcontribution;
   }

   /* update the activity, if the current value is valid and there was a change in the finite part */
   if( validact && (delta != 0.0) )
   {
      SCIP_Real curractivity;

      /* if the absolute value of the activity is increased, this is regarded as reliable,
       * otherwise, we check whether we can still trust the updated value
       */
      SCIPquadprecSumQD(*activity, *activity, delta);

      curractivity = QUAD_TO_DBL(*activity);
      assert(!SCIPisInfinity(scip, -curractivity) && !SCIPisInfinity(scip, curractivity));

      if( REALABS((*lastactivity)) < REALABS(curractivity) )
      {
         (*lastactivity) = curractivity;
      }
      else
      {
         if( checkreliability && SCIPisUpdateUnreliable(scip, curractivity, (*lastactivity)) )
         {
            SCIPdebugMsg(scip, "%s activity of linear constraint unreliable after update: %16.9g\n",
               (global ? "global " : ""), curractivity);

            /* mark the activity that was just changed and is not reliable anymore to be invalid */
            if( global )
            {
               if( (boundtype == SCIP_BOUNDTYPE_LOWER) == (val > 0.0) )
                  consdata->validglbminact = FALSE;
               else
                  consdata->validglbmaxact = FALSE;
            }
            else
            {
               if( (boundtype == SCIP_BOUNDTYPE_LOWER) == (val > 0.0) )
                  consdata->validminact = FALSE;
               else
                  consdata->validmaxact = FALSE;
            }
         }
      }
   }
}

/** updates minimum and maximum activity for a change in lower bound */
static
void consdataUpdateActivitiesLb(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   SCIP_VAR*             var,                /**< variable that has been changed */
   SCIP_Real             oldlb,              /**< old lower bound of variable */
   SCIP_Real             newlb,              /**< new lower bound of variable */
   SCIP_Real             val,                /**< coefficient of constraint entry */
   SCIP_Bool             checkreliability    /**< should the reliability of the recalculated activity be checked? */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);
   assert(var != NULL);

   if( consdata->validactivities )
   {
      consdataUpdateActivities(scip, consdata, var, oldlb, newlb, val, SCIP_BOUNDTYPE_LOWER, FALSE, checkreliability);

      assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->minactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->minactivity)));
      assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->maxactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->maxactivity)));
   }
}

/** updates minimum and maximum activity for a change in upper bound */
static
void consdataUpdateActivitiesUb(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   SCIP_VAR*             var,                /**< variable that has been changed */
   SCIP_Real             oldub,              /**< old upper bound of variable */
   SCIP_Real             newub,              /**< new upper bound of variable */
   SCIP_Real             val,                /**< coefficient of constraint entry */
   SCIP_Bool             checkreliability    /**< should the reliability of the recalculated activity be checked? */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);
   assert(var != NULL);

   if( consdata->validactivities )
   {
      consdataUpdateActivities(scip, consdata, var, oldub, newub, val, SCIP_BOUNDTYPE_UPPER, FALSE, checkreliability);

      assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->minactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->minactivity)));
      assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->maxactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->maxactivity)));
   }
}

/** updates minimum and maximum global activity for a change in the global lower bound */
static
void consdataUpdateActivitiesGlbLb(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   SCIP_Real             oldlb,              /**< old lower bound of variable */
   SCIP_Real             newlb,              /**< new lower bound of variable */
   SCIP_Real             val,                /**< coefficient of constraint entry */
   SCIP_Bool             checkreliability    /**< should the reliability of the recalculated activity be checked? */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);

   if( consdata->validactivities )
   {
      consdataUpdateActivities(scip, consdata, NULL, oldlb, newlb, val, SCIP_BOUNDTYPE_LOWER, TRUE, checkreliability);

      assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->glbminactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->glbminactivity)));
      assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->glbmaxactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->glbmaxactivity)));
   }
}

/** updates minimum and maximum global activity for a change in global upper bound */
static
void consdataUpdateActivitiesGlbUb(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   SCIP_Real             oldub,              /**< old upper bound of variable */
   SCIP_Real             newub,              /**< new upper bound of variable */
   SCIP_Real             val,                /**< coefficient of constraint entry */
   SCIP_Bool             checkreliability    /**< should the reliability of the recalculated activity be checked? */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);

   if( consdata->validactivities )
   {
      consdataUpdateActivities(scip, consdata, NULL, oldub, newub, val, SCIP_BOUNDTYPE_UPPER, TRUE, checkreliability);

      assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->glbminactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->glbminactivity)));
      assert(!SCIPisInfinity(scip, -QUAD_TO_DBL(consdata->glbmaxactivity)) && !SCIPisInfinity(scip, QUAD_TO_DBL(consdata->glbmaxactivity)));
   }
}

/** updates minimum and maximum activity and maximum absolute value for coefficient addition */
static
void consdataUpdateAddCoef(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   SCIP_VAR*             var,                /**< variable of constraint entry */
   SCIP_Real             val,                /**< coefficient of constraint entry */
   SCIP_Bool             checkreliability    /**< should the reliability of the recalculated activity be checked? */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);
   assert(var != NULL);

   /* update maximum absolute value */
   if( consdata->validmaxabsval )
   {
      SCIP_Real absval;

      assert(consdata->maxabsval < SCIP_INVALID);

      absval = REALABS(val);
      consdata->maxabsval = MAX(consdata->maxabsval, absval);
   }

   if( consdata->validminabsval )
   {
      SCIP_Real absval;

      assert(consdata->minabsval < SCIP_INVALID);

      absval = REALABS(val);
      consdata->minabsval = MIN(consdata->minabsval, absval);
   }

   /* update minimal and maximal activity */
   if( consdata->validactivities )
   {
      assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
      assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
      assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
      assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);

      consdataUpdateActivitiesLb(scip, consdata, var, 0.0, SCIPvarGetLbLocal(var), val, checkreliability);
      consdataUpdateActivitiesUb(scip, consdata, var, 0.0, SCIPvarGetUbLocal(var), val, checkreliability);
      consdataUpdateActivitiesGlbLb(scip, consdata, 0.0, SCIPvarGetLbGlobal(var), val, checkreliability);
      consdataUpdateActivitiesGlbUb(scip, consdata, 0.0, SCIPvarGetUbGlobal(var), val, checkreliability);
   }
}

/** updates minimum and maximum activity for coefficient deletion, invalidates maximum absolute value if necessary */
static
void consdataUpdateDelCoef(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   SCIP_VAR*             var,                /**< variable of constraint entry */
   SCIP_Real             val,                /**< coefficient of constraint entry */
   SCIP_Bool             checkreliability    /**< should the reliability of the recalculated activity be checked? */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);
   assert(var != NULL);

   /* invalidate maximum absolute value, if this coefficient was the maximum */
   if( consdata->validmaxabsval )
   {
      SCIP_Real absval;

      absval = REALABS(val);

      if( SCIPisEQ(scip, absval, consdata->maxabsval) )
      {
         consdata->validmaxabsval = FALSE;
         consdata->maxabsval = SCIP_INVALID;
      }
   }

   /* invalidate minimum absolute value, if this coefficient was the minimum */
   if( consdata->validminabsval )
   {
      SCIP_Real absval;

      absval = REALABS(val);

      if( SCIPisEQ(scip, absval, consdata->minabsval) )
      {
         consdata->validminabsval = FALSE;
         consdata->minabsval = SCIP_INVALID;
      }
   }

   /* update minimal and maximal activity */
   if( consdata->validactivities )
   {
      assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
      assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
      assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
      assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);

      consdataUpdateActivitiesLb(scip, consdata, var, SCIPvarGetLbLocal(var), 0.0, val, checkreliability);
      consdataUpdateActivitiesUb(scip, consdata, var, SCIPvarGetUbLocal(var), 0.0, val, checkreliability);
      consdataUpdateActivitiesGlbLb(scip, consdata, SCIPvarGetLbGlobal(var), 0.0, val, checkreliability);
      consdataUpdateActivitiesGlbUb(scip, consdata, SCIPvarGetUbGlobal(var), 0.0, val, checkreliability);
   }
}

/** updates minimum and maximum activity for coefficient change, invalidates maximum absolute value if necessary */
static
void consdataUpdateChgCoef(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   SCIP_VAR*             var,                /**< variable of constraint entry */
   SCIP_Real             oldval,             /**< old coefficient of constraint entry */
   SCIP_Real             newval,             /**< new coefficient of constraint entry */
   SCIP_Bool             checkreliability    /**< should the reliability of the recalculated activity be checked? */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);
   assert(var != NULL);

   /* old zero coefficients should be handled by consdataUpdateAddCoef() */
   assert(!SCIPisZero(scip, oldval));

   /* new zero coefficients should be handled by consdataUpdateDelCoef() */
   assert(!SCIPisZero(scip, newval));

   /* update maximum absolute value */
   if( consdata->validmaxabsval )
   {
      SCIP_Real absval;

      absval = REALABS(newval);

      if( SCIPisGE(scip, absval, consdata->maxabsval) )
      {
         consdata->maxabsval = absval;
      }
      else
      {
         absval = REALABS(oldval);

         /* invalidate maximum absolute value */
         if( SCIPisEQ(scip, absval, consdata->maxabsval) )
         {
            consdata->validmaxabsval = FALSE;
            consdata->maxabsval = SCIP_INVALID;
         }
      }
   }

   /* update minimum absolute value */
   if( consdata->validminabsval )
   {
      SCIP_Real absval;

      absval = REALABS(newval);

      if( SCIPisLE(scip, absval, consdata->minabsval) )
      {
         consdata->minabsval = absval;
      }
      else
      {
         absval = REALABS(oldval);

         /* invalidate minimum absolute value */
         if( SCIPisEQ(scip, absval, consdata->minabsval) )
         {
            consdata->validminabsval = FALSE;
            consdata->minabsval = SCIP_INVALID;
         }
      }
   }

   /* update maximum activity delta */
   if( !SCIPisInfinity(scip, consdata->maxactdelta ) )
   {
      SCIP_Real domain;
      SCIP_Real delta;

      assert(!SCIPisInfinity(scip, SCIPvarGetLbLocal(var)));
      assert(!SCIPisInfinity(scip, SCIPvarGetUbLocal(var)));

      domain = SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var);
      delta = REALABS(newval) * domain;

      if( delta > consdata->maxactdelta )
      {
         consdata->maxactdelta = delta;
         consdata->maxactdeltavar = var;
      }
      else
      {
         /* reset maximal activity delta, so that it will be recalculated on the next real propagation */
         if( consdata->maxactdeltavar == var )
            consdata->maxactdelta = SCIP_INVALID;
      }
   }

   /* @todo do something more clever here, e.g. if oldval * newval >= 0, do the update directly */
   consdataUpdateDelCoef(scip, consdata, var, oldval, checkreliability);
   consdataUpdateAddCoef(scip, consdata, var, newval, checkreliability);
}

/** returns the maximum absolute value of all coefficients in the constraint */
static
SCIP_Real consdataGetMaxAbsval(
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   assert(consdata != NULL);

   if( !consdata->validmaxabsval )
      consdataCalcMaxAbsval(consdata);
   assert(consdata->validmaxabsval);
   assert(consdata->maxabsval < SCIP_INVALID);

   return consdata->maxabsval;
}

/** returns the minimum absolute value of all coefficients in the constraint */
static
SCIP_Real consdataGetMinAbsval(
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   assert(consdata != NULL);

   if( !consdata->validminabsval )
      consdataCalcMinAbsval(consdata);
   assert(consdata->validminabsval);
   assert(consdata->minabsval < SCIP_INVALID);

   return consdata->minabsval;
}

/** calculates minimum and maximum local and global activity for constraint from scratch;
 *  additionally recalculates maximum absolute value of coefficients
 */
static
void consdataCalcActivities(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   int i;

   assert(scip != NULL);
   assert(consdata != NULL);
   assert(!consdata->validactivities);
   assert(QUAD_TO_DBL(consdata->minactivity) >= SCIP_INVALID || consdata->validminact);
   assert(QUAD_TO_DBL(consdata->maxactivity) >= SCIP_INVALID || consdata->validmaxact);
   assert(QUAD_TO_DBL(consdata->glbminactivity) >= SCIP_INVALID || consdata->validglbminact);
   assert(QUAD_TO_DBL(consdata->glbmaxactivity) >= SCIP_INVALID || consdata->validglbmaxact);

   consdata->validmaxabsval = TRUE;
   consdata->validminabsval = TRUE;
   consdata->validactivities = TRUE;
   consdata->validminact = TRUE;
   consdata->validmaxact = TRUE;
   consdata->validglbminact = TRUE;
   consdata->validglbmaxact = TRUE;
   consdata->maxabsval = 0.0;
   consdata->minabsval = (consdata->nvars == 0 ? 0.0 : REALABS(consdata->vals[0]));
   QUAD_ASSIGN(consdata->minactivity, 0.0);
   QUAD_ASSIGN(consdata->maxactivity, 0.0);
   consdata->lastminactivity = 0.0;
   consdata->lastmaxactivity = 0.0;
   consdata->minactivityneginf = 0;
   consdata->minactivityposinf = 0;
   consdata->maxactivityneginf = 0;
   consdata->maxactivityposinf = 0;
   consdata->minactivityneghuge = 0;
   consdata->minactivityposhuge = 0;
   consdata->maxactivityneghuge = 0;
   consdata->maxactivityposhuge = 0;
   QUAD_ASSIGN(consdata->glbminactivity, 0.0);
   QUAD_ASSIGN(consdata->glbmaxactivity, 0.0);
   consdata->lastglbminactivity = 0.0;
   consdata->lastglbmaxactivity = 0.0;
   consdata->glbminactivityneginf = 0;
   consdata->glbminactivityposinf = 0;
   consdata->glbmaxactivityneginf = 0;
   consdata->glbmaxactivityposinf = 0;
   consdata->glbminactivityneghuge = 0;
   consdata->glbminactivityposhuge = 0;
   consdata->glbmaxactivityneghuge = 0;
   consdata->glbmaxactivityposhuge = 0;

   for( i = 0; i < consdata->nvars; ++i )
      consdataUpdateAddCoef(scip, consdata, consdata->vars[i], consdata->vals[i], FALSE);

   consdata->lastminactivity = QUAD_TO_DBL(consdata->minactivity);
   consdata->lastmaxactivity = QUAD_TO_DBL(consdata->maxactivity);
   consdata->lastglbminactivity = QUAD_TO_DBL(consdata->glbminactivity);
   consdata->lastglbmaxactivity = QUAD_TO_DBL(consdata->glbmaxactivity);
}

/** gets minimal activity for constraint and given values of counters for infinite and huge contributions
 *  and (if needed) delta to subtract from stored finite part of activity in case of a residual activity
 */
static
void getMinActivity(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint */
   int                   posinf,             /**< number of coefficients contributing pos. infinite value */
   int                   neginf,             /**< number of coefficients contributing neg. infinite value */
   int                   poshuge,            /**< number of coefficients contributing huge pos. value */
   int                   neghuge,            /**< number of coefficients contributing huge neg. value */
   SCIP_Real             delta,              /**< value to subtract from stored minactivity
                                              *   (contribution of the variable set to zero when getting residual activity) */
   SCIP_Bool             global,             /**< should the global or local minimal activity be returned? */
   SCIP_Bool             goodrelax,          /**< should a good relaxation be computed or are relaxed acticities ignored, anyway? */
   SCIP_Real*            minactivity,        /**< pointer to store the minimal activity */
   SCIP_Bool*            isrelax,            /**< pointer to store whether the activity is a relaxation,
                                              *   i.e. is <= the exact minactivity (in case of huge contributing values) */
   SCIP_Bool*            issettoinfinity     /**< pointer to store whether minactivity was set to infinity or calculated */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);
   assert(posinf >= 0);
   assert(neginf >= 0);
   assert(poshuge >= 0);
   assert(neghuge >= 0);
   assert(minactivity != NULL);
   assert(isrelax != NULL);
   assert(issettoinfinity != NULL);

   /* if we have pos. infinite contributions, the minactivity is +infty */
   if( posinf > 0 )
   {
      *minactivity = SCIPinfinity(scip);
      *issettoinfinity = TRUE;
      *isrelax = FALSE;
   }
   /* if we have neg. (and no pos.) infinite contributions, the minactivity is -infty */
   else if( neginf > 0 )
   {
      *minactivity = -SCIPinfinity(scip);
      *issettoinfinity = TRUE;
      *isrelax = FALSE;
   }
   /* if we have neg. huge contributions, we only know that -infty is a relaxation of the minactivity */
   else if( neghuge > 0 )
   {
      *minactivity = -SCIPinfinity(scip);
      *issettoinfinity = TRUE;
      *isrelax = TRUE;
   }
   /* we do not need a good relaxation and we have positive huge contributions, so we just return -infty as activity */
   else if( !goodrelax && poshuge > 0 )
   {
      *minactivity = -SCIPinfinity(scip);
      *issettoinfinity = TRUE;
      *isrelax = TRUE;
   }
   else
   {
      SCIP_Real tmpactivity;

      /* recompute minactivity if it is not valid */
      if( global )
      {
         if( !consdata->validglbminact )
            consdataRecomputeGlbMinactivity(scip, consdata);
         assert(consdata->validglbminact);

         tmpactivity = QUAD_TO_DBL(consdata->glbminactivity);
      }
      else
      {
         if( !consdata->validminact )
            consdataRecomputeMinactivity(scip, consdata);
         assert(consdata->validminact);

         tmpactivity = QUAD_TO_DBL(consdata->minactivity);
      }

      /* we have no infinite and no neg. huge contributions, but pos. huge contributions;
       * a feasible relaxation of the minactivity is the number of positive huge contributions
       * times the minimum value counting as "huge" plus finite (and non-huge) part of minactivity - delta
       */
      if( poshuge > 0 )
      {
         *minactivity = 1.0 * poshuge * SCIPgetHugeValue(scip) + (tmpactivity - delta);
         *issettoinfinity = FALSE;
         *isrelax = TRUE;
      }
      /* all counters are zero, so the minactivity is just stored and we subtract the delta */
      else
      {
         *minactivity = tmpactivity - delta;
         *issettoinfinity = FALSE;
         *isrelax = FALSE;
      }
   }
}

/** gets maximal activity for constraint and given values of counters for infinite and huge contributions
 *  and (if needed) delta to subtract from stored finite part of activity in case of a residual activity
 */
static
void getMaxActivity(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint */
   int                   posinf,             /**< number of coefficients contributing pos. infinite value */
   int                   neginf,             /**< number of coefficients contributing neg. infinite value */
   int                   poshuge,            /**< number of coefficients contributing huge pos. value */
   int                   neghuge,            /**< number of coefficients contributing huge neg. value */
   SCIP_Real             delta,              /**< value to subtract from stored maxactivity
                                              *   (contribution of the variable set to zero when getting residual activity) */
   SCIP_Bool             global,             /**< should the global or local maximal activity be returned? */
   SCIP_Bool             goodrelax,          /**< should a good relaxation be computed or are relaxed acticities ignored, anyway? */
   SCIP_Real*            maxactivity,        /**< pointer to store the maximal activity */
   SCIP_Bool*            isrelax,            /**< pointer to store whether the activity is a relaxation,
                                              *   i.e. is >= the exact maxactivity (in case of huge contributing values) */
   SCIP_Bool*            issettoinfinity     /**< pointer to store whether maxactivity was set to infinity or calculated */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);
   assert(posinf >= 0);
   assert(neginf >= 0);
   assert(poshuge >= 0);
   assert(neghuge >= 0);
   assert(maxactivity != NULL);
   assert(isrelax != NULL);
   assert(issettoinfinity != NULL);

   /* if we have neg. infinite contributions, the maxactivity is -infty */
   if( neginf > 0 )
   {
      *maxactivity = -SCIPinfinity(scip);
      *issettoinfinity = TRUE;
      *isrelax = FALSE;
   }
   /* if we have pos. (and no neg.) infinite contributions, the maxactivity is +infty */
   else if( posinf > 0 )
   {
      *maxactivity = SCIPinfinity(scip);
      *issettoinfinity = TRUE;
      *isrelax = FALSE;
   }
   /* if we have pos. huge contributions, we only know that +infty is a relaxation of the maxactivity */
   else if( poshuge > 0 )
   {
      *maxactivity = SCIPinfinity(scip);
      *issettoinfinity = TRUE;
      *isrelax = TRUE;
   }
   /* we do not need a good relaxation and we have positve huge contributions, so we just return +infty as activity */
   else if( !goodrelax && neghuge > 0 )
   {
      *maxactivity = SCIPinfinity(scip);
      *issettoinfinity = TRUE;
      *isrelax = TRUE;
   }
   else
   {
      SCIP_Real tmpactivity;

      /* recompute maxactivity if it is not valid */
      if( global )
      {
         if( !consdata->validglbmaxact )
            consdataRecomputeGlbMaxactivity(scip, consdata);
         assert(consdata->validglbmaxact);

         tmpactivity = QUAD_TO_DBL(consdata->glbmaxactivity);
      }
      else
      {
         if( !consdata->validmaxact )
            consdataRecomputeMaxactivity(scip, consdata);
         assert(consdata->validmaxact);

         tmpactivity = QUAD_TO_DBL(consdata->maxactivity);
      }

      /* we have no infinite, and no pos. huge contributions, but neg. huge contributions;
       * a feasible relaxation of the maxactivity is minus the number of negative huge contributions
       * times the minimum value counting as "huge" plus the finite (and non-huge) part of maxactivity minus delta
       */
      if( neghuge > 0 )
      {
         *maxactivity = -1.0 * neghuge * SCIPgetHugeValue(scip) + tmpactivity - delta;
         *issettoinfinity = FALSE;
         *isrelax = TRUE;
      }
      /* all counters are zero, so the maxactivity is just stored and we subtract the delta */
      else
      {
         *maxactivity = tmpactivity - delta;
         *issettoinfinity = FALSE;
         *isrelax = FALSE;
      }
   }
}

/** gets activity bounds for constraint */
static
void consdataGetActivityBounds(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint */
   SCIP_Bool             goodrelax,          /**< if we have huge contributions, do we need a good relaxation or are
                                              *   relaxed activities ignored, anyway? */
   SCIP_Real*            minactivity,        /**< pointer to store the minimal activity */
   SCIP_Real*            maxactivity,        /**< pointer to store the maximal activity */
   SCIP_Bool*            minisrelax,         /**< pointer to store whether the returned minactivity is just a relaxation,
                                              *   i.e. <= the exact minactivity (in case of huge contributions),
                                              *   or equal to the exact minimal activity */
   SCIP_Bool*            maxisrelax,         /**< pointer to store whether the returned maxactivity is just a relaxation,
                                              *   i.e. >= the exact maxactivity (in case of huge contributions),
                                              *   or equal to the exact maximal activity */
   SCIP_Bool*            isminsettoinfinity, /**< pointer to store whether minactivity was set to infinity or calculated */
   SCIP_Bool*            ismaxsettoinfinity  /**< pointer to store whether maxactivity was set to infinity or calculated */

   )
{
   assert(scip != NULL);
   assert(consdata != NULL);
   assert(minactivity != NULL);
   assert(maxactivity != NULL);
   assert(isminsettoinfinity != NULL);
   assert(ismaxsettoinfinity != NULL);

   if( !consdata->validactivities )
   {
      consdataCalcActivities(scip, consdata);
      assert(consdata->validminact);
      assert(consdata->validmaxact);
   }
   assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
   assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
   assert(consdata->minactivityneginf >= 0);
   assert(consdata->minactivityposinf >= 0);
   assert(consdata->maxactivityneginf >= 0);
   assert(consdata->maxactivityposinf >= 0);

   getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
      consdata->minactivityposhuge, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
      minactivity, minisrelax, isminsettoinfinity);

   getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
      consdata->maxactivityposhuge, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
      maxactivity, maxisrelax, ismaxsettoinfinity);
}

/** calculates activity bounds for constraint after setting variable to zero */
static
void consdataGetReliableResidualActivity(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint */
   SCIP_VAR*             cancelvar,          /**< variable to calculate activity residual for */
   SCIP_Real*            resactivity,        /**< pointer to store the residual activity */
   SCIP_Bool             isminresact,        /**< should minimal or maximal residual activity be calculated? */
   SCIP_Bool             useglobalbounds     /**< should global or local bounds be used? */
   )
{
   SCIP_VAR* var;
   SCIP_Real val;
   SCIP_Real lb;
   SCIP_Real ub;
   int v;

   assert(scip != NULL);
   assert(consdata != NULL);
   assert(cancelvar != NULL);
   assert(resactivity != NULL);

   *resactivity = 0.0;

   for( v = 0; v < consdata->nvars; ++v )
   {
      var = consdata->vars[v];
      assert(var != NULL);
      if( var == cancelvar )
         continue;

      val = consdata->vals[v];

      if( useglobalbounds )
      {
         lb = SCIPvarGetLbGlobal(var);
         ub = SCIPvarGetUbGlobal(var);
      }
      else
      {
         lb = SCIPvarGetLbLocal(var);
         ub = SCIPvarGetUbLocal(var);
      }

      assert(!SCIPisZero(scip, val));
      assert(SCIPisLE(scip, lb, ub));

      if( val > 0.0 )
      {
         if( isminresact )
         {
            assert(!SCIPisInfinity(scip, -lb));
            assert(!SCIPisHugeValue(scip, REALABS(val*lb)));
            *resactivity += val*lb;
         }
         else
         {
            assert(!SCIPisInfinity(scip, ub));
            assert(!SCIPisHugeValue(scip, REALABS(val*ub)));
            *resactivity += val*ub;
         }
      }
      else
      {
         if( isminresact)
         {
            assert(!SCIPisInfinity(scip, ub));
            assert(!SCIPisHugeValue(scip, REALABS(val*ub)));
            *resactivity += val*ub;
         }
         else
         {
            assert(!SCIPisInfinity(scip, -lb));
            assert(!SCIPisHugeValue(scip, REALABS(val*lb)));
            *resactivity += val*lb;
         }
      }
   }
   assert(!SCIPisInfinity(scip, *resactivity) && !SCIPisInfinity(scip, -(*resactivity)));
}

/** gets activity bounds for constraint after setting variable to zero */
static
void consdataGetActivityResiduals(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint */
   SCIP_VAR*             var,                /**< variable to calculate activity residual for */
   SCIP_Real             val,                /**< coefficient value of variable in linear constraint */
   SCIP_Bool             goodrelax,          /**< if we have huge contributions, do we need a good relaxation or are
                                              *   relaxed acticities ignored, anyway? */
   SCIP_Real*            minresactivity,     /**< pointer to store the minimal residual activity */
   SCIP_Real*            maxresactivity,     /**< pointer to store the maximal residual activity */
   SCIP_Bool*            minisrelax,         /**< pointer to store whether the returned residual minactivity is just a
                                              *   relaxation, i.e. <= the exact residual minactivity (in case of huge
                                              *   contributions), or equal to the exact residual minactivity */
   SCIP_Bool*            maxisrelax,         /**< pointer to store whether the returned residual maxactivity is just a
                                              *   relaxation, i.e. <= the exact residual maxactivity (in case of huge
                                              *   contributions), or equal to the exact residual minactivity */
   SCIP_Bool*            isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
   SCIP_Bool*            ismaxsettoinfinity  /**< pointer to store whether maxresactivity was set to infinity or calculated */
   )
{
   SCIP_Real minactbound;
   SCIP_Real maxactbound;
   SCIP_Real absval;

   assert(scip != NULL);
   assert(consdata != NULL);
   assert(var != NULL);
   assert(minresactivity != NULL);
   assert(maxresactivity != NULL);
   assert(minisrelax != NULL);
   assert(maxisrelax != NULL);
   assert(isminsettoinfinity != NULL);
   assert(ismaxsettoinfinity != NULL);

   /* get activity bounds of linear constraint */
   if( !consdata->validactivities )
   {
      consdataCalcActivities(scip, consdata);
      assert(consdata->validminact);
      assert(consdata->validmaxact);
   }
   assert(QUAD_TO_DBL(consdata->minactivity) < SCIP_INVALID);
   assert(QUAD_TO_DBL(consdata->maxactivity) < SCIP_INVALID);
   assert(consdata->minactivityneginf >= 0);
   assert(consdata->minactivityposinf >= 0);
   assert(consdata->maxactivityneginf >= 0);
   assert(consdata->maxactivityposinf >= 0);
   assert(consdata->minactivityneghuge >= 0);
   assert(consdata->minactivityposhuge >= 0);
   assert(consdata->maxactivityneghuge >= 0);
   assert(consdata->maxactivityposhuge >= 0);

   if( val > 0.0 )
   {
      minactbound = SCIPvarGetLbLocal(var);
      maxactbound = SCIPvarGetUbLocal(var);
      absval = val;
   }
   else
   {
      minactbound = -SCIPvarGetUbLocal(var);
      maxactbound = -SCIPvarGetLbLocal(var);
      absval = -val;
   }

   /* get/compute minactivity by calling getMinActivity() with updated counters for infinite and huge values
    * and contribution of variable set to zero that has to be subtracted from finite part of activity
    */
   if( SCIPisInfinity(scip, minactbound) )
   {
      assert(consdata->minactivityposinf >= 1);

      getMinActivity(scip, consdata, consdata->minactivityposinf - 1, consdata->minactivityneginf,
         consdata->minactivityposhuge, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
         minresactivity, minisrelax, isminsettoinfinity);
   }
   else if( SCIPisInfinity(scip, -minactbound) )
   {
      assert(consdata->minactivityneginf >= 1);

      getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf - 1,
         consdata->minactivityposhuge, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
         minresactivity, minisrelax, isminsettoinfinity);
   }
   else if( SCIPisHugeValue(scip, minactbound * absval) )
   {
      assert(consdata->minactivityposhuge >= 1);

      getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
         consdata->minactivityposhuge - 1, consdata->minactivityneghuge, 0.0, FALSE, goodrelax,
         minresactivity, minisrelax, isminsettoinfinity);
   }
   else if( SCIPisHugeValue(scip, -minactbound * absval) )
   {
      assert(consdata->minactivityneghuge >= 1);

      getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
         consdata->minactivityposhuge, consdata->minactivityneghuge - 1, 0.0, FALSE, goodrelax,
         minresactivity, minisrelax, isminsettoinfinity);
   }
   else
   {
      getMinActivity(scip, consdata, consdata->minactivityposinf, consdata->minactivityneginf,
         consdata->minactivityposhuge, consdata->minactivityneghuge, absval * minactbound, FALSE, goodrelax,
         minresactivity, minisrelax, isminsettoinfinity);
   }

   /* get/compute maxactivity by calling getMaxActivity() with updated counters for infinite and huge values
    * and contribution of variable set to zero that has to be subtracted from finite part of activity
    */
   if( SCIPisInfinity(scip, -maxactbound) )
   {
      assert(consdata->maxactivityneginf >= 1);

      getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf - 1,
         consdata->maxactivityposhuge, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
         maxresactivity, maxisrelax, ismaxsettoinfinity);
   }
   else if( SCIPisInfinity(scip, maxactbound) )
   {
      assert(consdata->maxactivityposinf >= 1);

      getMaxActivity(scip, consdata, consdata->maxactivityposinf - 1, consdata->maxactivityneginf,
         consdata->maxactivityposhuge, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
         maxresactivity, maxisrelax, ismaxsettoinfinity);
   }
   else if( SCIPisHugeValue(scip, absval * maxactbound) )
   {
      assert(consdata->maxactivityposhuge >= 1);

      getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
         consdata->maxactivityposhuge - 1, consdata->maxactivityneghuge, 0.0, FALSE, goodrelax,
         maxresactivity, maxisrelax, ismaxsettoinfinity);
   }
   else if( SCIPisHugeValue(scip, -absval * maxactbound) )
   {
      assert(consdata->maxactivityneghuge >= 1);

      getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
         consdata->maxactivityposhuge, consdata->maxactivityneghuge - 1, 0.0, FALSE, goodrelax,
         maxresactivity, maxisrelax, ismaxsettoinfinity);
   }
   else
   {
      getMaxActivity(scip, consdata, consdata->maxactivityposinf, consdata->maxactivityneginf,
         consdata->maxactivityposhuge, consdata->maxactivityneghuge, absval * maxactbound, FALSE, goodrelax,
         maxresactivity, maxisrelax, ismaxsettoinfinity);
   }
}

/** gets global activity bounds for constraint */
static
void consdataGetGlbActivityBounds(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint */
   SCIP_Bool             goodrelax,          /**< if we have huge contributions, do we need a good relaxation or are
                                              *   relaxed acticities ignored, anyway? */
   SCIP_Real*            glbminactivity,     /**< pointer to store the minimal activity, or NULL, if not needed */
   SCIP_Real*            glbmaxactivity,     /**< pointer to store the maximal activity, or NULL, if not needed */
   SCIP_Bool*            minisrelax,         /**< pointer to store whether the returned minactivity is just a relaxation,
                                              *   i.e. <= the exact minactivity (in case of huge contributions),
                                              *   or equal to the exact minimal activity */
   SCIP_Bool*            maxisrelax,         /**< pointer to store whether the returned maxactivity is just a relaxation,
                                              *   i.e. >= the exact maxactivity (in case of huge contributions),
                                              *   or equal to the exact maximal activity */
   SCIP_Bool*            isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
   SCIP_Bool*            ismaxsettoinfinity  /**< pointer to store whether maxresactivity was set to infinity or calculated */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);
   assert((glbminactivity != NULL && minisrelax != NULL && isminsettoinfinity != NULL)
      || (glbmaxactivity != NULL && maxisrelax != NULL && ismaxsettoinfinity != NULL));

   if( !consdata->validactivities )
   {
      consdataCalcActivities(scip, consdata);
      assert(consdata->validglbminact);
      assert(consdata->validglbmaxact);
   }
   assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
   assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
   assert(consdata->glbminactivityneginf >= 0);
   assert(consdata->glbminactivityposinf >= 0);
   assert(consdata->glbmaxactivityneginf >= 0);
   assert(consdata->glbmaxactivityposinf >= 0);
   assert(consdata->glbminactivityneghuge >= 0);
   assert(consdata->glbminactivityposhuge >= 0);
   assert(consdata->glbmaxactivityneghuge >= 0);
   assert(consdata->glbmaxactivityposhuge >= 0);

   if( glbminactivity != NULL )
   {
      assert(isminsettoinfinity != NULL);
      assert(minisrelax != NULL);

      getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
         consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
         glbminactivity, minisrelax, isminsettoinfinity);
   }

   if( glbmaxactivity != NULL )
   {
      assert(ismaxsettoinfinity != NULL);
      assert(maxisrelax != NULL);

      getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
         consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
         glbmaxactivity, maxisrelax, ismaxsettoinfinity);
   }
}

/** gets global activity bounds for constraint after setting variable to zero */
static
void consdataGetGlbActivityResiduals(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint */
   SCIP_VAR*             var,                /**< variable to calculate activity residual for */
   SCIP_Real             val,                /**< coefficient value of variable in linear constraint */
   SCIP_Bool             goodrelax,          /**< if we have huge contributions, do we need a good relaxation or are
                                              *   relaxed acticities ignored, anyway? */
   SCIP_Real*            minresactivity,     /**< pointer to store the minimal residual activity, or NULL, if not needed */
   SCIP_Real*            maxresactivity,     /**< pointer to store the maximal residual activity, or NULL, if not needed */
   SCIP_Bool*            minisrelax,         /**< pointer to store whether the returned residual minactivity is just a
                                              *   relaxation, i.e. <= the exact residual minactivity (in case of huge
                                              *   contributions), or equal to the exact residual minactivity */
   SCIP_Bool*            maxisrelax,         /**< pointer to store whether the returned residual maxactivity is just a
                                              *   relaxation, i.e. <= the exact residual maxactivity (in case of huge
                                              *   contributions), or equal to the exact residual minactivity */
   SCIP_Bool*            isminsettoinfinity, /**< pointer to store whether minresactivity was set to infinity or calculated */
   SCIP_Bool*            ismaxsettoinfinity  /**< pointer to store whether maxresactivity was set to infinity or calculated */
   )
{
   SCIP_Real minactbound;
   SCIP_Real maxactbound;
   SCIP_Real absval;

   assert(scip != NULL);
   assert(consdata != NULL);
   assert(var != NULL);
   assert((minresactivity != NULL && minisrelax != NULL && isminsettoinfinity != NULL )
      || (maxresactivity != NULL && maxisrelax != NULL && ismaxsettoinfinity != NULL));

   /* get activity bounds of linear constraint */
   if( !consdata->validactivities )
      consdataCalcActivities(scip, consdata);

   assert(QUAD_TO_DBL(consdata->glbminactivity) < SCIP_INVALID);
   assert(QUAD_TO_DBL(consdata->glbmaxactivity) < SCIP_INVALID);
   assert(consdata->glbminactivityneginf >= 0);
   assert(consdata->glbminactivityposinf >= 0);
   assert(consdata->glbmaxactivityneginf >= 0);
   assert(consdata->glbmaxactivityposinf >= 0);

   if( val > 0.0 )
   {
      minactbound = SCIPvarGetLbGlobal(var);
      maxactbound = SCIPvarGetUbGlobal(var);
      absval = val;
   }
   else
   {
      minactbound = -SCIPvarGetUbGlobal(var);
      maxactbound = -SCIPvarGetLbGlobal(var);
      absval = -val;
   }

   if( minresactivity != NULL )
   {
      assert(isminsettoinfinity != NULL);
      assert(minisrelax != NULL);

      /* get/compute minactivity by calling getMinActivity() with updated counters for infinite and huge values
       * and contribution of variable set to zero that has to be subtracted from finite part of activity
       */
      if( SCIPisInfinity(scip, minactbound) )
      {
         assert(consdata->glbminactivityposinf >= 1);

         getMinActivity(scip, consdata, consdata->glbminactivityposinf - 1, consdata->glbminactivityneginf,
            consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
            minresactivity, minisrelax, isminsettoinfinity);
      }
      else if( SCIPisInfinity(scip, -minactbound) )
      {
         assert(consdata->glbminactivityneginf >= 1);

         getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf - 1,
            consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
            minresactivity, minisrelax, isminsettoinfinity);
      }
      else if( SCIPisHugeValue(scip, minactbound * absval) )
      {
         assert(consdata->glbminactivityposhuge >= 1);

         getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
            consdata->glbminactivityposhuge - 1, consdata->glbminactivityneghuge, 0.0, TRUE, goodrelax,
            minresactivity, minisrelax, isminsettoinfinity);
      }
      else if( SCIPisHugeValue(scip, -minactbound * absval) )
      {
         assert(consdata->glbminactivityneghuge >= 1);

         getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
            consdata->glbminactivityposhuge, consdata->glbminactivityneghuge - 1, 0.0, TRUE, goodrelax,
            minresactivity, minisrelax, isminsettoinfinity);
      }
      else
      {
         getMinActivity(scip, consdata, consdata->glbminactivityposinf, consdata->glbminactivityneginf,
            consdata->glbminactivityposhuge, consdata->glbminactivityneghuge, absval * minactbound, TRUE,
            goodrelax, minresactivity, minisrelax, isminsettoinfinity);
      }
   }

   if( maxresactivity != NULL )
   {
      assert(ismaxsettoinfinity != NULL);
      assert(maxisrelax != NULL);

      /* get/compute maxactivity by calling getMaxActivity() with updated counters for infinite and huge values
       * and contribution of variable set to zero that has to be subtracted from finite part of activity
       */
      if( SCIPisInfinity(scip, -maxactbound) )
      {
         assert(consdata->glbmaxactivityneginf >= 1);

         getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf - 1,
            consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
            maxresactivity, maxisrelax, ismaxsettoinfinity);
      }
      else if( SCIPisInfinity(scip, maxactbound) )
      {
         assert(consdata->glbmaxactivityposinf >= 1);

         getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf - 1, consdata->glbmaxactivityneginf,
            consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
            maxresactivity, maxisrelax, ismaxsettoinfinity);
      }
      else if( SCIPisHugeValue(scip, absval * maxactbound) )
      {
         assert(consdata->glbmaxactivityposhuge >= 1);

         getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
            consdata->glbmaxactivityposhuge - 1, consdata->glbmaxactivityneghuge, 0.0, TRUE, goodrelax,
            maxresactivity, maxisrelax, ismaxsettoinfinity);
      }
      else if( SCIPisHugeValue(scip, -absval * maxactbound) )
      {
         assert(consdata->glbmaxactivityneghuge >= 1);

         getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
            consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge - 1, 0.0, TRUE, goodrelax,
            maxresactivity, maxisrelax, ismaxsettoinfinity);
      }
      else
      {
         getMaxActivity(scip, consdata, consdata->glbmaxactivityposinf, consdata->glbmaxactivityneginf,
            consdata->glbmaxactivityposhuge, consdata->glbmaxactivityneghuge, absval * maxactbound, TRUE,
            goodrelax, maxresactivity, maxisrelax, ismaxsettoinfinity);
      }
   }
}

/** calculates the activity of the linear constraint for given solution */
static
SCIP_Real consdataGetActivity(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   SCIP_SOL*             sol                 /**< solution to get activity for, NULL to current solution */
   )
{
   SCIP_Real activity;

   assert(scip != NULL);
   assert(consdata != NULL);

   if( sol == NULL && !SCIPhasCurrentNodeLP(scip) )
      activity = consdataComputePseudoActivity(scip, consdata);
   else
   {
      SCIP_Real solval;
      int nposinf;
      int nneginf;
      SCIP_Bool negsign;
      int v;

      activity = 0.0;
      nposinf = 0;
      nneginf = 0;

      for( v = 0; v < consdata->nvars; ++v )
      {
         solval = SCIPgetSolVal(scip, sol, consdata->vars[v]);

         if( consdata->vals[v] < 0 )
            negsign = TRUE;
         else
            negsign = FALSE;

         if( (SCIPisInfinity(scip, solval) && !negsign) || (SCIPisInfinity(scip, -solval) && negsign) )
            ++nposinf;
         else if( (SCIPisInfinity(scip, solval) && negsign) || (SCIPisInfinity(scip, -solval) && !negsign) )
            ++nneginf;
         else
            activity += consdata->vals[v] * solval;
      }
      assert(nneginf >= 0 && nposinf >= 0);

      SCIPdebugMsg(scip, "activity of linear constraint: %.15g, %d positive infinity values, %d negative infinity values \n", activity, nposinf, nneginf);

      /* check for amount of infinity values and correct the activity */
      if( nposinf > 0 && nneginf > 0 )
         activity = (consdata->rhs + consdata->lhs) / 2;
      else if( nposinf > 0 )
         activity = SCIPinfinity(scip);
      else if( nneginf > 0 )
         activity = -SCIPinfinity(scip);

      SCIPdebugMsg(scip, "corrected activity of linear constraint: %.15g\n", activity);
   }

   if( activity == SCIP_INVALID ) /*lint !e777*/
      return activity;
   else if( activity < 0 )
      activity = MAX(activity, -SCIPinfinity(scip)); /*lint !e666*/
   else
      activity = MIN(activity, SCIPinfinity(scip)); /*lint !e666*/

   return activity;
}

/** calculates the feasibility of the linear constraint for given solution */
static
SCIP_Real consdataGetFeasibility(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   SCIP_SOL*             sol                 /**< solution to get feasibility for, NULL to current solution */
   )
{
   SCIP_Real activity;

   assert(scip != NULL);
   assert(consdata != NULL);

   activity = consdataGetActivity(scip, consdata, sol);

   if( activity == SCIP_INVALID ) /*lint !e777*/
      return -SCIPinfinity(scip);

   return MIN(consdata->rhs - activity, activity - consdata->lhs);
}

/** updates bit signatures after adding a single coefficient */
static
void consdataUpdateSignatures(
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   int                   pos                 /**< position of coefficient to update signatures for */
   )
{
   uint64_t varsignature;
   SCIP_Real lb;
   SCIP_Real ub;
   SCIP_Real val;

   assert(consdata != NULL);
   assert(consdata->validsignature);

   varsignature = SCIPhashSignature64(SCIPvarGetIndex(consdata->vars[pos]));
   lb = SCIPvarGetLbGlobal(consdata->vars[pos]);
   ub = SCIPvarGetUbGlobal(consdata->vars[pos]);
   val = consdata->vals[pos];
   if( (val > 0.0 && ub > 0.0) || (val < 0.0 && lb < 0.0) )
      consdata->possignature |= varsignature;
   if( (val > 0.0 && lb < 0.0) || (val < 0.0 && ub > 0.0) )
      consdata->negsignature |= varsignature;
}

/** calculates the bit signatures of the given constraint data */
static
void consdataCalcSignatures(
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   assert(consdata != NULL);

   if( !consdata->validsignature )
   {
      int i;

      consdata->validsignature = TRUE;
      consdata->possignature = 0;
      consdata->negsignature = 0;
      for( i = 0; i < consdata->nvars; ++i )
         consdataUpdateSignatures(consdata, i);
   }
}

/** index comparison method of linear constraints: compares two indices of the variable set in the linear constraint */
static
SCIP_DECL_SORTINDCOMP(consdataCompVar)
{  /*lint --e{715}*/
   SCIP_CONSDATA* consdata = (SCIP_CONSDATA*)dataptr;
   SCIP_VAR* var1;
   SCIP_VAR* var2;

   assert(consdata != NULL);
   assert(0 <= ind1 && ind1 < consdata->nvars);
   assert(0 <= ind2 && ind2 < consdata->nvars);

   var1 = consdata->vars[ind1];
   var2 = consdata->vars[ind2];

   /* exactly one variable is binary */
   if( SCIPvarIsBinary(var1) != SCIPvarIsBinary(var2) )
   {
      return (SCIPvarIsBinary(var1) ? -1 : +1);
   }
   /* both variables are binary */
   else if( SCIPvarIsBinary(var1) )
   {
      return SCIPvarCompare(var1, var2);
   }
   else
   {
      SCIP_VARTYPE vartype1 = SCIPvarGetType(var1);
      SCIP_VARTYPE vartype2 = SCIPvarGetType(var2);

      if( vartype1 < vartype2 )
         return -1;
      else if( vartype1 > vartype2 )
         return +1;
      else
         return SCIPvarCompare(var1, var2);
   }
}

/** index comparison method of linear constraints: compares two indices of the variable set in the linear constraint */
static
SCIP_DECL_SORTINDCOMP(consdataCompVarProp)
{  /*lint --e{715}*/
   SCIP_CONSDATA* consdata = (SCIP_CONSDATA*)dataptr;
   SCIP_VAR* var1;
   SCIP_VAR* var2;

   assert(consdata != NULL);
   assert(0 <= ind1 && ind1 < consdata->nvars);
   assert(0 <= ind2 && ind2 < consdata->nvars);

   var1 = consdata->vars[ind1];
   var2 = consdata->vars[ind2];

   /* exactly one variable is binary */
   if( SCIPvarIsBinary(var1) != SCIPvarIsBinary(var2) )
   {
      return (SCIPvarIsBinary(var1) ? -1 : +1);
   }
   /* both variables are binary */
   else if( SCIPvarIsBinary(var1) )
   {
      SCIP_Real abscoef1 = REALABS(consdata->vals[ind1]);
      SCIP_Real abscoef2 = REALABS(consdata->vals[ind2]);

      if( EPSGT(abscoef1, abscoef2, 1e-9) )
         return -1;
      else if( EPSGT(abscoef2, abscoef1, 1e-9) )
         return +1;
      else
         return (SCIPvarGetProbindex(var1) - SCIPvarGetProbindex(var2));
   }
   else
   {
      SCIP_VARTYPE vartype1 = SCIPvarGetType(var1);
      SCIP_VARTYPE vartype2 = SCIPvarGetType(var2);

      if( vartype1 < vartype2 )
      {
         return -1;
      }
      else if( vartype1 > vartype2 )
      {
         return +1;
      }
      else
      {
         /* both variables are continuous */
         if( !SCIPvarIsIntegral(var1) )
         {
            assert(!SCIPvarIsIntegral(var2));
            return (SCIPvarGetProbindex(var1) - SCIPvarGetProbindex(var2));
         }
         else
         {
            SCIP_Real abscont1 = REALABS(consdata->vals[ind1] * (SCIPvarGetUbGlobal(var1) - SCIPvarGetLbGlobal(var1)));
            SCIP_Real abscont2 = REALABS(consdata->vals[ind2] * (SCIPvarGetUbGlobal(var2) - SCIPvarGetLbGlobal(var2)));

            if( EPSGT(abscont1, abscont2, 1e-9) )
               return -1;
            else if( EPSGT(abscont2, abscont1, 1e-9) )
               return +1;
            else
               return (SCIPvarGetProbindex(var1) - SCIPvarGetProbindex(var2));
         }
      }
   }
}

/** permutes the constraint's variables according to a given permutation. */
static
void permSortConsdata(
   SCIP_CONSDATA*        consdata,           /**< the constraint data */
   int*                  perm,               /**< the target permutation */
   int                   nvars               /**< the number of variables */
   )
{  /*lint --e{715}*/
   SCIP_VAR* varv;
   SCIP_EVENTDATA* eventdatav;
   SCIP_Real valv;
   int v;
   int i;
   int nexti;

   assert(perm != NULL);
   assert(consdata != NULL);

   /* permute the variables in the linear constraint according to the target permutation */
   eventdatav = NULL;
   for( v = 0; v < nvars; ++v )
   {
      if( perm[v] != v )
      {
         varv = consdata->vars[v];
         valv = consdata->vals[v];
         if( consdata->eventdata != NULL )
            eventdatav = consdata->eventdata[v];
         i = v;
         do
         {
            assert(0 <= perm[i] && perm[i] < nvars);
            assert(perm[i] != i);
            consdata->vars[i] = consdata->vars[perm[i]];
            consdata->vals[i] = consdata->vals[perm[i]];
            if( consdata->eventdata != NULL )
            {
               consdata->eventdata[i] = consdata->eventdata[perm[i]];
               consdata->eventdata[i]->varpos = i;
            }
            nexti = perm[i];
            perm[i] = i;
            i = nexti;
         }
         while( perm[i] != v );
         consdata->vars[i] = varv;
         consdata->vals[i] = valv;
         if( consdata->eventdata != NULL )
         {
            consdata->eventdata[i] = eventdatav;
            consdata->eventdata[i]->varpos = i;
         }
         perm[i] = i;
      }
   }
#ifdef SCIP_DEBUG
   /* check sorting */
   for( v = 0; v < nvars; ++v )
   {
      assert(perm[v] == v);
      assert(consdata->eventdata == NULL || consdata->eventdata[v]->varpos == v);
   }
#endif
}

/** sorts linear constraint's variables depending on the stage of the solving process:
 * - during PRESOLVING
 *       sorts variables by binaries, integers, implicit integers, and continuous variables,
 *       and the variables of the same type by non-decreasing variable index
 *
 * - during SOLVING
 *       sorts variables of the remaining problem by binaries, integers, implicit integers, and continuous variables,
 *       and binary and integer variables by their global max activity delta (within each group),
 *       ties within a group are broken by problem index of the variable.
 *
 *       This fastens the propagation time of the constraint handler.
 */
static
SCIP_RETCODE consdataSort(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);

   /* check if there are variables for sorting */
   if( consdata->nvars <= 1 )
   {
      consdata->indexsorted = TRUE;
      consdata->coefsorted = TRUE;
      consdata->nbinvars = (consdata->nvars == 1 ? (int)SCIPvarIsBinary(consdata->vars[0]) : 0);
   }
   else if( (!consdata->indexsorted && SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE)
      || (!consdata->coefsorted && SCIPgetStage(scip) >= SCIP_STAGE_INITSOLVE) )
   {
      int* perm;
      int v;

      /* get temporary memory to store the sorted permutation */
      SCIP_CALL( SCIPallocBufferArray(scip, &perm, consdata->nvars) );

      /* call sorting method  */
      if( SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE )
         SCIPsort(perm, consdataCompVar, (void*)consdata, consdata->nvars);
      else
         SCIPsort(perm, consdataCompVarProp, (void*)consdata, consdata->nvars);

      permSortConsdata(consdata, perm, consdata->nvars);

      /* free temporary memory */
      SCIPfreeBufferArray(scip, &perm);

      if( SCIPgetStage(scip) >= SCIP_STAGE_INITSOLVE )
      {
         consdata->indexsorted = FALSE;
         consdata->coefsorted = TRUE;

         /* count binary variables in the sorted vars array */
         consdata->nbinvars = 0;
         for( v = 0; v < consdata->nvars; ++v )
         {
            if( SCIPvarIsBinary(consdata->vars[v]) )
               ++consdata->nbinvars;
            else
               break;
         }
      }
      else
      {
         consdata->indexsorted = TRUE;
         consdata->coefsorted = FALSE;
      }
   }

   return SCIP_OKAY;
}


/*
 * local linear constraint handler methods
 */

/** sets left hand side of linear constraint */
static
SCIP_RETCODE chgLhs(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   SCIP_Real             lhs                 /**< new left hand side */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_Bool locked;
   int i;

   assert(scip != NULL);
   assert(cons != NULL);
   assert(!SCIPisInfinity(scip, lhs));

   /* adjust value to not be smaller than -inf */
   if ( SCIPisInfinity(scip, -lhs) )
      lhs = -SCIPinfinity(scip);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(consdata->nvars == 0 || (consdata->vars != NULL && consdata->vals != NULL));
   assert(!SCIPisInfinity(scip, consdata->lhs));

   /* check whether the side is not changed */
   if( SCIPisEQ(scip, consdata->lhs, lhs) )
      return SCIP_OKAY;

   /* ensure that rhs >= lhs is satisfied without numerical tolerance */
   if( SCIPisEQ(scip, lhs, consdata->rhs) )
   {
      consdata->rhs = lhs;
      assert(consdata->row == NULL);
   }

   locked = FALSE;
   for( i = 0; i < NLOCKTYPES && !locked; i++ )
      locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);

   /* if necessary, update the rounding locks of variables */
   if( locked )
   {
      if( SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, -lhs) )
      {
         SCIP_VAR** vars;
         SCIP_Real* vals;
         int v;

         /* the left hand side switched from -infinity to a non-infinite value -> install rounding locks */
         vars = consdata->vars;
         vals = consdata->vals;

         for( v = 0; v < consdata->nvars; ++v )
         {
            assert(vars[v] != NULL);
            assert(!SCIPisZero(scip, vals[v]));

            if( SCIPisPositive(scip, vals[v]) )
            {
               SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
            }
            else
            {
               SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
            }
         }
      }
      else if( !SCIPisInfinity(scip, -consdata->lhs) && SCIPisInfinity(scip, -lhs) )
      {
         SCIP_VAR** vars;
         SCIP_Real* vals;
         int v;

         /* the left hand side switched from a non-infinite value to -infinity -> remove rounding locks */
         vars = consdata->vars;
         vals = consdata->vals;

         for( v = 0; v < consdata->nvars; ++v )
         {
            assert(vars[v] != NULL);
            assert(!SCIPisZero(scip, vals[v]));

            if( SCIPisPositive(scip, vals[v]) )
            {
               SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
            }
            else
            {
               SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
            }
         }
      }
   }

   /* check whether the left hand side is increased, if and only if that's the case we maybe can propagate, tighten and add more cliques */
   if( !SCIPisInfinity(scip, -lhs) && SCIPisGT(scip, lhs, consdata->lhs) )
   {
      consdata->boundstightened = 0;
      consdata->presolved = FALSE;
      consdata->cliquesadded = FALSE;
      consdata->implsadded = FALSE;

      /* mark the constraint for propagation */
      if( SCIPconsIsTransformed(cons) )
      {
         SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
      }
   }

   /* set new left hand side and update constraint data */
   consdata->lhs = lhs;
   consdata->changed = TRUE;
   consdata->normalized = FALSE;
   consdata->upgradetried = FALSE;
   consdata->rangedrowpropagated = 0;

   /* update the lhs of the LP row */
   if( consdata->row != NULL )
   {
      SCIP_CALL( SCIPchgRowLhs(scip, consdata->row, lhs) );
   }

   return SCIP_OKAY;
}

/** sets right hand side of linear constraint */
static
SCIP_RETCODE chgRhs(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   SCIP_Real             rhs                 /**< new right hand side */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_Bool locked;
   int i;

   assert(scip != NULL);
   assert(cons != NULL);
   assert(!SCIPisInfinity(scip, -rhs));

   /* adjust value to not be larger than inf */
   if ( SCIPisInfinity(scip, rhs) )
      rhs = SCIPinfinity(scip);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(consdata->nvars == 0 || (consdata->vars != NULL && consdata->vals != NULL));
   assert(!SCIPisInfinity(scip, -consdata->rhs));

   /* check whether the side is not changed */
   if( SCIPisEQ(scip, consdata->rhs, rhs) )
      return SCIP_OKAY;

   /* ensure that rhs >= lhs is satisfied without numerical tolerance */
   if( SCIPisEQ(scip, rhs, consdata->lhs) )
   {
      consdata->lhs = rhs;
      assert(consdata->row == NULL);
   }

   locked = FALSE;
   for( i = 0; i < NLOCKTYPES && !locked; i++ )
      locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);

   /* if necessary, update the rounding locks of variables */
   if( locked )
   {
      assert(SCIPconsIsTransformed(cons));

      if( SCIPisInfinity(scip, consdata->rhs) && !SCIPisInfinity(scip, rhs) )
      {
         SCIP_VAR** vars;
         SCIP_Real* vals;
         int v;

         /* the right hand side switched from infinity to a non-infinite value -> install rounding locks */
         vars = consdata->vars;
         vals = consdata->vals;

         for( v = 0; v < consdata->nvars; ++v )
         {
            assert(vars[v] != NULL);
            assert(!SCIPisZero(scip, vals[v]));

            if( SCIPisPositive(scip, vals[v]) )
            {
               SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
            }
            else
            {
               SCIP_CALL( SCIPlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
            }
         }
      }
      else if( !SCIPisInfinity(scip, consdata->rhs) && SCIPisInfinity(scip, rhs) )
      {
         SCIP_VAR** vars;
         SCIP_Real* vals;
         int v;

         /* the right hand side switched from a non-infinite value to infinity -> remove rounding locks */
         vars = consdata->vars;
         vals = consdata->vals;

         for( v = 0; v < consdata->nvars; ++v )
         {
            assert(vars[v] != NULL);
            assert(!SCIPisZero(scip, vals[v]));

            if( SCIPisPositive(scip, vals[v]) )
            {
               SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, FALSE, TRUE) );
            }
            else
            {
               SCIP_CALL( SCIPunlockVarCons(scip, vars[v], cons, TRUE, FALSE) );
            }
         }
      }
   }

   /* check whether the right hand side is decreased, if and only if that's the case we maybe can propagate, tighten and add more cliques */
   if( !SCIPisInfinity(scip, rhs) && SCIPisLT(scip, rhs, consdata->rhs) )
   {
      consdata->boundstightened = 0;
      consdata->presolved = FALSE;
      consdata->cliquesadded = FALSE;
      consdata->implsadded = FALSE;

      /* mark the constraint for propagation */
      if( SCIPconsIsTransformed(cons) )
      {
         SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
      }
   }

   /* set new right hand side and update constraint data */
   consdata->rhs = rhs;
   consdata->changed = TRUE;
   consdata->normalized = FALSE;
   consdata->upgradetried = FALSE;
   consdata->rangedrowpropagated = 0;

   /* update the rhs of the LP row */
   if( consdata->row != NULL )
   {
      SCIP_CALL( SCIPchgRowRhs(scip, consdata->row, rhs) );
   }

   return SCIP_OKAY;
}

/** adds coefficient in linear constraint */
static
SCIP_RETCODE addCoef(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   SCIP_VAR*             var,                /**< variable of constraint entry */
   SCIP_Real             val                 /**< coefficient of constraint entry */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_Bool transformed;

   assert(scip != NULL);
   assert(cons != NULL);
   assert(var != NULL);

   /* relaxation-only variables must not be used in checked or enforced constraints */
   assert(!SCIPvarIsRelaxationOnly(var) || (!SCIPconsIsChecked(cons) && !SCIPconsIsEnforced(cons)));

   /* ignore coefficient if it is nearly zero */
   if( SCIPisZero(scip, val) )
      return SCIP_OKAY;

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);

   /* are we in the transformed problem? */
   transformed = SCIPconsIsTransformed(cons);

   /* always use transformed variables in transformed constraints */
   if( transformed )
   {
      SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
   }
   assert(var != NULL);
   assert(transformed == SCIPvarIsTransformed(var));

   SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1) );
   consdata->vars[consdata->nvars] = var;
   consdata->vals[consdata->nvars] = val;
   consdata->nvars++;

   /* capture variable */
   SCIP_CALL( SCIPcaptureVar(scip, var) );

   /* if we are in transformed problem, the variable needs an additional event data */
   if( transformed )
   {
      if( consdata->eventdata != NULL )
      {
         SCIP_CONSHDLR* conshdlr;
         SCIP_CONSHDLRDATA* conshdlrdata;

         /* check for event handler */
         conshdlr = SCIPconsGetHdlr(cons);
         conshdlrdata = SCIPconshdlrGetData(conshdlr);
         assert(conshdlrdata != NULL);
         assert(conshdlrdata->eventhdlr != NULL);

         /* initialize eventdata array */
         consdata->eventdata[consdata->nvars-1] = NULL;

         /* catch bound change events of variable */
         SCIP_CALL( consCatchEvent(scip, cons, conshdlrdata->eventhdlr, consdata->nvars-1) );
      }

      /* update minimum and maximum activities */
      consdataUpdateAddCoef(scip, consdata, var, val, FALSE);

      /* update maximum activity delta */
      if( !SCIPisInfinity(scip, consdata->maxactdelta ) )
      {
         SCIP_Real lb;
         SCIP_Real ub;

         lb = SCIPvarGetLbLocal(var);
         ub = SCIPvarGetUbLocal(var);

         if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
         {
            consdata->maxactdelta = SCIPinfinity(scip);
            consdata->maxactdeltavar = var;
         }
         else
         {
            SCIP_Real domain = ub - lb;
            SCIP_Real delta = REALABS(val) * domain;

            if( delta > consdata->maxactdelta )
            {
               consdata->maxactdelta = delta;
               consdata->maxactdeltavar = var;
            }
         }
      }
   }

   /* install rounding locks for new variable */
   SCIP_CALL( lockRounding(scip, cons, var, val) );

   /* mark the constraint for propagation */
   if( transformed )
   {
      SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
   }

   consdata->boundstightened = 0;
   consdata->presolved = FALSE;
   consdata->removedfixings = consdata->removedfixings && SCIPvarIsActive(var);

   if( consdata->validsignature )
      consdataUpdateSignatures(consdata, consdata->nvars-1);

   consdata->changed = TRUE;
   consdata->normalized = FALSE;
   consdata->upgradetried = FALSE;
   consdata->cliquesadded = FALSE;
   consdata->implsadded = FALSE;
   consdata->rangedrowpropagated = 0;

   if( consdata->nvars == 1 )
   {
      consdata->indexsorted = TRUE;
      consdata->coefsorted = TRUE;
      consdata->merged = TRUE;
   }
   else
   {
      consdata->merged = FALSE;

      if( SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE )
      {
         consdata->indexsorted = consdata->indexsorted && (consdataCompVar((void*)consdata, consdata->nvars-2, consdata->nvars-1) <= 0);
         consdata->coefsorted = FALSE;
      }
      else
      {
         consdata->indexsorted = FALSE;
         consdata->coefsorted = consdata->coefsorted && (consdataCompVarProp((void*)consdata, consdata->nvars-2, consdata->nvars-1) <= 0);
      }
   }

   /* update hascontvar and hasnonbinvar flags */
   if( consdata->hasnonbinvalid && !consdata->hascontvar )
   {
      SCIP_VARTYPE vartype = SCIPvarGetType(var);

      if( vartype != SCIP_VARTYPE_BINARY )
      {
         consdata->hasnonbinvar = TRUE;

         if( vartype == SCIP_VARTYPE_CONTINUOUS )
            consdata->hascontvar = TRUE;
      }
   }

   /* add the new coefficient to the LP row */
   if( consdata->row != NULL )
   {
      SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, val) );
   }

   return SCIP_OKAY;
}

/** deletes coefficient at given position from linear constraint data */
static
SCIP_RETCODE delCoefPos(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   int                   pos                 /**< position of coefficient to delete */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR* var;
   SCIP_Real val;

   assert(scip != NULL);
   assert(cons != NULL);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(0 <= pos && pos < consdata->nvars);

   var = consdata->vars[pos];
   val = consdata->vals[pos];
   assert(var != NULL);

   /* remove rounding locks for deleted variable */
   SCIP_CALL( unlockRounding(scip, cons, var, val) );

   /* if we are in transformed problem, delete the event data of the variable */
   if( SCIPconsIsTransformed(cons) )
   {
      SCIP_CONSHDLR* conshdlr;
      SCIP_CONSHDLRDATA* conshdlrdata;

      /* check for event handler */
      conshdlr = SCIPconsGetHdlr(cons);
      conshdlrdata = SCIPconshdlrGetData(conshdlr);
      assert(conshdlrdata != NULL);
      assert(conshdlrdata->eventhdlr != NULL);

      /* drop bound change events of variable */
      if( consdata->eventdata != NULL )
      {
         SCIP_CALL( consDropEvent(scip, cons, conshdlrdata->eventhdlr, pos) );
         assert(consdata->eventdata[pos] == NULL);
      }
   }

   /* move the last variable to the free slot */
   if( pos != consdata->nvars - 1 )
   {
      consdata->vars[pos] = consdata->vars[consdata->nvars-1];
      consdata->vals[pos] = consdata->vals[consdata->nvars-1];

      if( consdata->eventdata != NULL )
      {
         consdata->eventdata[pos] = consdata->eventdata[consdata->nvars-1];
         assert(consdata->eventdata[pos] != NULL);
         consdata->eventdata[pos]->varpos = pos;
      }

      consdata->indexsorted = consdata->indexsorted && (pos + 2 >= consdata->nvars);
      consdata->coefsorted = consdata->coefsorted && (pos + 2 >= consdata->nvars);
   }
   consdata->nvars--;

   /* if at most one variable is left, the activities should be recalculated (to correspond exactly to the bounds
    * of the remaining variable, or give exactly 0.0)
    */
   if( consdata->nvars <= 1 )
      consdataInvalidateActivities(consdata);
   else
   {
      if( SCIPconsIsTransformed(cons) )
      {
         /* if we are in transformed problem, update minimum and maximum activities */
         consdataUpdateDelCoef(scip, consdata, var, val, TRUE);

         /* if the variable defining the maximal activity delta was removed from the constraint, the maximal activity
          * delta needs to be recalculated on the next real propagation
          */
         if( consdata->maxactdeltavar == var )
         {
            consdata->maxactdelta = SCIP_INVALID;
            consdata->maxactdeltavar = NULL;
         }
      }
   }

   /* mark the constraint for propagation */
   if( SCIPconsIsTransformed(cons) )
   {
      SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
   }

   consdata->boundstightened = 0;
   consdata->presolved = FALSE;
   consdata->validsignature = FALSE;
   consdata->changed = TRUE;
   consdata->normalized = FALSE;
   consdata->upgradetried = FALSE;
   consdata->cliquesadded = FALSE;
   consdata->implsadded = FALSE;
   consdata->rangedrowpropagated = 0;

   /* check if hasnonbinvar flag might be incorrect now */
   if( consdata->hasnonbinvar && SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
   {
      consdata->hasnonbinvalid = FALSE;
   }

   /* delete coefficient from the LP row */
   if( consdata->row != NULL )
   {
      SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, -val) );
   }

   /* release variable */
   SCIP_CALL( SCIPreleaseVar(scip, &var) );

   return SCIP_OKAY;
}

/** changes coefficient value at given position of linear constraint data */
static
SCIP_RETCODE chgCoefPos(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   int                   pos,                /**< position of coefficient to delete */
   SCIP_Real             newval              /**< new value of coefficient */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR* var;
   SCIP_Real val;
   SCIP_Bool locked;
   int i;

   assert(scip != NULL);
   assert(cons != NULL);
   assert(!SCIPisZero(scip, newval));

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(0 <= pos && pos < consdata->nvars);
   assert(!SCIPisZero(scip, newval));

   var = consdata->vars[pos];
   val = consdata->vals[pos];
   assert(var != NULL);
   assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(var));

   locked = FALSE;
   for( i = 0; i < NLOCKTYPES && !locked; i++ )
      locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);

   /* if necessary, update the rounding locks of the variable */
   if( locked && newval * val < 0.0 )
   {
      assert(SCIPconsIsTransformed(cons));

      /* remove rounding locks for variable with old coefficient */
      SCIP_CALL( unlockRounding(scip, cons, var, val) );

      /* install rounding locks for variable with new coefficient */
      SCIP_CALL( lockRounding(scip, cons, var, newval) );
   }

   /* change the value */
   consdata->vals[pos] = newval;

   if( consdata->coefsorted )
   {
      if( pos > 0 )
         consdata->coefsorted = (consdataCompVarProp((void*)consdata, pos - 1, pos) <= 0);
      if( consdata->coefsorted && pos < consdata->nvars - 1 )
         consdata->coefsorted = (consdataCompVarProp((void*)consdata, pos, pos + 1) <= 0);
   }

   /* update minimum and maximum activities */
   if( SCIPconsIsTransformed(cons) )
      consdataUpdateChgCoef(scip, consdata, var, val, newval, TRUE);

   /* mark the constraint for propagation */
   if( SCIPconsIsTransformed(cons) )
   {
      SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
   }

   consdata->boundstightened = 0;
   consdata->presolved = FALSE;
   consdata->validsignature = consdata->validsignature && (newval * val > 0.0);
   consdata->changed = TRUE;
   consdata->normalized = FALSE;
   consdata->upgradetried = FALSE;
   consdata->cliquesadded = FALSE;
   consdata->implsadded = FALSE;
   consdata->rangedrowpropagated = 0;

   return SCIP_OKAY;
}

/** scales a linear constraint with a constant scalar */
static
SCIP_RETCODE scaleCons(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint to scale */
   SCIP_Real             scalar              /**< value to scale constraint with */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_Real newval;
   SCIP_Real absscalar;
   int i;

   assert(scip != NULL);
   assert(cons != NULL);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(consdata->row == NULL);
   assert(!SCIPisEQ(scip, scalar, 1.0));

   if( (!SCIPisInfinity(scip, -consdata->lhs) && SCIPisInfinity(scip, -consdata->lhs * scalar))
      || (!SCIPisInfinity(scip, consdata->rhs) && SCIPisInfinity(scip, consdata->rhs * scalar)) )
   {
      SCIPwarningMessage(scip, "skipped scaling for linear constraint <%s> to avoid numerical troubles (scalar: %.15g)\n",
         SCIPconsGetName(cons), scalar);

      return SCIP_OKAY;
   }

   /* scale the coefficients */
   for( i = consdata->nvars - 1; i >= 0; --i )
   {
      newval = scalar * consdata->vals[i];

      /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasFloor, we add an additional 0.5 before
       * flooring down our new value
       */
      if( SCIPisScalingIntegral(scip, consdata->vals[i], scalar) )
         newval = SCIPfeasFloor(scip, newval + 0.5);

      if( SCIPisZero(scip, newval) )
      {
         SCIPwarningMessage(scip, "coefficient %.15g of variable <%s> in linear constraint <%s> scaled to zero (scalar: %.15g)\n",
            consdata->vals[i], SCIPvarGetName(consdata->vars[i]), SCIPconsGetName(cons), scalar);
         SCIP_CALL( delCoefPos(scip, cons, i) );
      }
      else
         consdata->vals[i] = newval;
   }

   /* scale the sides */
   if( scalar < 0.0 )
   {
      SCIP_Real lhs;

      lhs = consdata->lhs;
      consdata->lhs = -consdata->rhs;
      consdata->rhs = -lhs;
   }
   absscalar = REALABS(scalar);
   if( !SCIPisInfinity(scip, -consdata->lhs) )
   {
      newval = absscalar * consdata->lhs;

      /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasFloor, we add an additional 0.5 before
       * flooring down our new value
       */
      if( SCIPisScalingIntegral(scip, consdata->lhs, absscalar) )
         consdata->lhs = SCIPfeasFloor(scip, newval + 0.5);
      else
         consdata->lhs = newval;
   }
   if( !SCIPisInfinity(scip, consdata->rhs) )
   {
      newval = absscalar * consdata->rhs;

      /* because SCIPisScalingIntegral uses another integrality check as SCIPfeasCeil, we subtract 0.5 before ceiling up
       * our new value
       */
      if( SCIPisScalingIntegral(scip, consdata->rhs, absscalar) )
         consdata->rhs = SCIPfeasCeil(scip, newval - 0.5);
      else
         consdata->rhs = newval;
   }

   consdataInvalidateActivities(consdata);
   consdata->cliquesadded = FALSE;
   consdata->implsadded = FALSE;

   return SCIP_OKAY;
}

/** perform deletion of variables in all constraints of the constraint handler */
static
SCIP_RETCODE performVarDeletions(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLR*        conshdlr,           /**< constraint handler */
   SCIP_CONS**           conss,              /**< array of constraints */
   int                   nconss              /**< number of constraints */
   )
{
   SCIP_CONSDATA* consdata;
   int i;
   int v;

   assert(scip != NULL);
   assert(conshdlr != NULL);
   assert(conss != NULL);
   assert(nconss >= 0);
   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);

   /* iterate over all constraints */
   for( i = 0; i < nconss; i++ )
   {
      consdata = SCIPconsGetData(conss[i]);

      /* constraint is marked, that some of its variables were deleted */
      if( consdata->varsdeleted )
      {
         /* iterate over all variables of the constraint and delete them from the constraint */
         for( v = consdata->nvars - 1; v >= 0; --v )
         {
            if( SCIPvarIsDeleted(consdata->vars[v]) )
            {
               SCIP_CALL( delCoefPos(scip, conss[i], v) );
            }
         }
         consdata->varsdeleted = FALSE;
      }
   }

   return SCIP_OKAY;
}


/** normalizes a linear constraint with the following rules:
 *  - if all coefficients have them same absolute value, change them to (-)1.0
 *  - multiplication with +1 or -1:
 *      Apply the following rules in the given order, until the sign of the factor is determined. Later rules only apply,
 *      if the current rule doesn't determine the sign):
 *        1. the right hand side must not be negative
 *        2. the right hand side must not be infinite
 *        3. the absolute value of the right hand side must be greater than that of the left hand side
 *        4. the number of positive coefficients must not be smaller than the number of negative coefficients
 *        5. multiply with +1
 *  - rationals to integrals
 *      Try to identify a rational representation of the fractional coefficients, and multiply all coefficients
 *      by the smallest common multiple of all denominators to get integral coefficients.
 *      Forbid large denominators due to numerical stability.
 *  - division by greatest common divisor
 *      If all coefficients are integral, divide them by the greatest common divisor.
 */
static
SCIP_RETCODE normalizeCons(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint to normalize */
   SCIP_Bool*            infeasible          /**< pointer to store whether infeasibility was detected */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_Real* vals;
   SCIP_Longint scm;
   SCIP_Longint nominator;
   SCIP_Longint denominator;
   SCIP_Longint gcd;
   SCIP_Longint maxmult;
   SCIP_Real epsilon;
   SCIP_Real feastol;
   SCIP_Real maxabsval;
   SCIP_Real minabsval;
   SCIP_Bool success;
   SCIP_Bool onlyintegral;
   int nvars;
   int mult;
   int nposcoeffs;
   int nnegcoeffs;
   int i;
   int v;

   assert(scip != NULL);
   assert(cons != NULL);
   assert(infeasible != NULL);

   *infeasible = FALSE;

   /* we must not change a modifiable constraint in any way */
   if( SCIPconsIsModifiable(cons) )
      return SCIP_OKAY;

   /* get constraint data */
   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);

   /* check, if the constraint is already normalized */
   if( consdata->normalized )
      return SCIP_OKAY;

   /* get coefficient arrays */
   vals = consdata->vals;
   nvars = consdata->nvars;
   assert(nvars == 0 || vals != NULL);

   if( nvars == 0 )
   {
      consdata->normalized = TRUE;
      return SCIP_OKAY;
   }

   assert(vals != NULL);

   /* get maximal and minimal absolute coefficient */
   maxabsval = consdataGetMaxAbsval(consdata);
   minabsval = consdataGetMinAbsval(consdata);

   /* return if scaling by maxval will eliminate coefficients */
   if( SCIPisZero(scip, minabsval/maxabsval) )
      return SCIP_OKAY;

   /* check if all coefficients are in absolute value equal, and not 1.0 */
   if( !SCIPisEQ(scip, maxabsval, 1.0) )
   {
      SCIP_Bool abscoefsequ;

      abscoefsequ = TRUE;

      for( v = nvars - 1; v >= 0; --v )
      {
         if( !SCIPisEQ(scip, REALABS(vals[v]), maxabsval) )
         {
            abscoefsequ = FALSE;
            break;
         }
      }

      /* all coefficients are in absolute value equal, so change them to (-)1.0 */
      if( abscoefsequ )
      {
         SCIPdebugMsg(scip, "divide linear constraint with %g, because all coefficients are in absolute value the same\n", maxabsval);
         SCIPdebugPrintCons(scip, cons, NULL);
         SCIP_CALL( scaleCons(scip, cons, 1/maxabsval) );

         if( consdata->validmaxabsval )
         {
            if( !SCIPisEQ(scip, consdata->maxabsval, 1.0) )
               consdata->maxabsval = 1.0;
            if( !SCIPisEQ(scip, consdata->minabsval, 1.0) )
               consdata->minabsval = 1.0;

            maxabsval = 1.0;
         }
         else
         {
            /* get maximal absolute coefficient */
            maxabsval = consdataGetMaxAbsval(consdata);
         }

         /* get new consdata information, because scaleCons() might have deleted variables */
         vals = consdata->vals;
         nvars = consdata->nvars;

         assert(nvars == 0 || vals != NULL);
      }
   }

   /* nvars might have changed */
   if( nvars == 0 )
   {
      consdata->normalized = TRUE;
      return SCIP_OKAY;
   }

   assert(vals != NULL);

   /* calculate the maximal multiplier for common divisor calculation:
    *   |p/q - val| < epsilon  and  q < feastol/epsilon  =>  |p - q*val| < feastol
    * which means, a value of feastol/epsilon should be used as maximal multiplier;
    * additionally, we don't want to scale the constraint if this would lead to too
    * large coefficients
    */
   epsilon = SCIPepsilon(scip) * 0.9;  /* slightly decrease epsilon to be safe in rational conversion below */
   feastol = SCIPfeastol(scip);
   maxmult = (SCIP_Longint)(feastol/epsilon + feastol);

   if( !consdata->hasnonbinvalid )
      consdataCheckNonbinvar(consdata);

   /* if all variables are of integral type we will allow a greater multiplier */
   if( !consdata->hascontvar )
      maxmult = MIN(maxmult, (SCIP_Longint) (MAXSCALEDCOEFINTEGER / MAX(maxabsval, 1.0))); /*lint !e835*/
   else
      maxmult = MIN(maxmult, (SCIP_Longint) (MAXSCALEDCOEF / MAX(maxabsval, 1.0))); /*lint !e835*/

   /*
    * multiplication with +1 or -1
    */
   mult = 0;

   /* 1. the right hand side must not be negative */
   if( SCIPisPositive(scip, consdata->lhs) )
      mult = +1;
   else if( SCIPisNegative(scip, consdata->rhs) )
      mult = -1;

   if( mult == 0 )
   {
      /* 2. the right hand side must not be infinite */
      if( SCIPisInfinity(scip, -consdata->lhs) )
         mult = +1;
      else if( SCIPisInfinity(scip, consdata->rhs) )
         mult = -1;
   }

   if( mult == 0 )
   {
      /* 3. the absolute value of the right hand side must be greater than that of the left hand side */
      if( SCIPisGT(scip, REALABS(consdata->rhs), REALABS(consdata->lhs)) )
         mult = +1;
      else if( SCIPisLT(scip, REALABS(consdata->rhs), REALABS(consdata->lhs)) )
         mult = -1;
   }

   if( mult == 0 )
   {
      /* 4. the number of positive coefficients must not be smaller than the number of negative coefficients */
      nposcoeffs = 0;
      nnegcoeffs = 0;
      for( i = 0; i < nvars; ++i )
      {
         if( vals[i] > 0.0 )
            nposcoeffs++;
         else
            nnegcoeffs++;
      }
      if( nposcoeffs > nnegcoeffs )
         mult = +1;
      else if( nposcoeffs < nnegcoeffs )
         mult = -1;
   }

   if( mult == 0 )
   {
      /* 5. multiply with +1 */
      mult = +1;
   }

   assert(mult == +1 || mult == -1);
   if( mult == -1 )
   {
      /* scale the constraint with -1 */
      SCIPdebugMsg(scip, "multiply linear constraint with -1.0\n");
      SCIPdebugPrintCons(scip, cons, NULL);
      SCIP_CALL( scaleCons(scip, cons, -1.0) );

      /* scalecons() can delete variables, but scaling with -1 should not do that */
      assert(nvars == consdata->nvars);
   }

   /*
    * rationals to integrals
    *
    * @todo try scaling only on behalf of non-continuous variables
    */
   success = TRUE;
   scm = 1;
   for( i = 0; i < nvars && success && scm <= maxmult; ++i )
   {
      if( !SCIPisIntegral(scip, vals[i]) )
      {
         /* epsilon has been slightly decreased above - to be on the safe side */
         success = SCIPrealToRational(vals[i], -epsilon, epsilon , maxmult, &nominator, &denominator);
         if( success )
            scm = SCIPcalcSmaComMul(scm, denominator);
      }
   }
   assert(scm >= 1);

   /* it might be that we have really big coefficients, but all are integral, in that case we want to divide them by
    * their greatest common divisor
    */
   onlyintegral = TRUE;
   if( scm == 1 )
   {
      for( i = nvars - 1; i >= 0; --i )
      {
         if( !SCIPisIntegral(scip, vals[i]) )
         {
            onlyintegral = FALSE;
            break;
         }
      }
   }

   success = success && (scm <= maxmult || (scm == 1 && onlyintegral));
   if( success && scm != 1 )
   {
      /* scale the constraint with the smallest common multiple of all denominators */
      SCIPdebugMsg(scip, "scale linear constraint with %" SCIP_LONGINT_FORMAT " to make coefficients integral\n", scm);
      SCIPdebugPrintCons(scip, cons, NULL);
      SCIP_CALL( scaleCons(scip, cons, (SCIP_Real)scm) );

      if( consdata->validmaxabsval )
      {
         consdata->maxabsval *= REALABS((SCIP_Real)scm);
         if( !SCIPisIntegral(scip, consdata->maxabsval) )
         {
            consdata->validmaxabsval = FALSE;
            consdata->maxabsval = SCIP_INVALID;
            consdataCalcMaxAbsval(consdata);
         }
      }

      if( consdata->validminabsval )
      {
         consdata->minabsval *= REALABS((SCIP_Real)scm);
         if( !SCIPisIntegral(scip, consdata->minabsval) )
         {
            consdata->validminabsval = FALSE;
            consdata->minabsval = SCIP_INVALID;
            consdataCalcMinAbsval(consdata);
         }
      }

      /* get new consdata information, because scalecons() might have deleted variables */
      vals = consdata->vals;
      nvars = consdata->nvars;
      assert(nvars == 0 || vals != NULL);
   }

   /*
    * division by greatest common divisor
    */
   if( success && nvars >= 1 )
   {
      /* all coefficients are integral: divide them by their greatest common divisor */
      assert(SCIPisIntegral(scip, vals[0]));

      gcd = (SCIP_Longint)(REALABS(vals[0]) + feastol);
      for( i = 1; i < nvars && gcd > 1; ++i )
      {
         assert(SCIPisIntegral(scip, vals[i]));
         gcd = SCIPcalcGreComDiv(gcd, (SCIP_Longint)(REALABS(vals[i]) + feastol));
      }

      if( gcd > 1 )
      {
         /* since the lhs/rhs is not respected for gcd calculation it can happen that we detect infeasibility */
         if( !consdata->hascontvar && onlyintegral )
         {
            if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) && !SCIPisFeasIntegral(scip, consdata->rhs / gcd) )
            {
               *infeasible = TRUE;

               SCIPdebugMsg(scip, "detected infeasibility of constraint after scaling with gcd=%" SCIP_LONGINT_FORMAT ":\n", gcd);
               SCIPdebugPrintCons(scip, cons, NULL);

               return SCIP_OKAY;
            }
         }

         /* divide the constraint by the greatest common divisor of the coefficients */
         SCIPdebugMsg(scip, "divide linear constraint by greatest common divisor %" SCIP_LONGINT_FORMAT "\n", gcd);
         SCIPdebugPrintCons(scip, cons, NULL);
         SCIP_CALL( scaleCons(scip, cons, 1.0/(SCIP_Real)gcd) );

         if( consdata->validmaxabsval )
         {
            consdata->maxabsval /= REALABS((SCIP_Real)gcd);
         }
         if( consdata->validminabsval )
         {
            consdata->minabsval /= REALABS((SCIP_Real)gcd);
         }
      }
   }

   /* mark constraint to be normalized */
   consdata->normalized = TRUE;

   SCIPdebugMsg(scip, "normalized constraint:\n");
   SCIPdebugPrintCons(scip, cons, NULL);

   return SCIP_OKAY;
}

/** replaces multiple occurrences of a variable by a single coefficient */
static
SCIP_RETCODE mergeMultiples(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons                /**< linear constraint */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR* var;
   SCIP_Real valsum;
   int v;

   assert(scip != NULL);
   assert(cons != NULL);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);

   if( consdata->merged )
      return SCIP_OKAY;

   /* sort the constraint */
   SCIP_CALL( consdataSort(scip, consdata) );

   /* go backwards through the constraint looking for multiple occurrences of the same variable;
    * backward direction is necessary, since delCoefPos() modifies the given position and
    * the subsequent ones
    */
   v = consdata->nvars-1;
   while( v >= 1 )
   {
      var = consdata->vars[v];
      if( consdata->vars[v-1] == var )
      {
         valsum = consdata->vals[v];
         do
         {
            SCIP_CALL( delCoefPos(scip, cons, v) );
            --v;
            valsum += consdata->vals[v];
         }
         while( v >= 1 && consdata->vars[v-1] == var );

         /* modify the last existing occurrence of the variable */
         assert(consdata->vars[v] == var);
         if( SCIPisZero(scip, valsum) )
         {
            SCIP_CALL( delCoefPos(scip, cons, v) );

            /* if the variable defining the maximal activity delta was removed from the constraint, the maximal activity
             * delta needs to be recalculated on the next real propagation
             */
            if( consdata->maxactdeltavar == var )
            {
               consdata->maxactdelta = SCIP_INVALID;
               consdata->maxactdeltavar = NULL;
            }
         }
         else
         {
            SCIP_CALL( chgCoefPos(scip, cons, v, valsum) );
         }
      }
      --v;
   }

   consdata->merged = TRUE;

   return SCIP_OKAY;
}

/** replaces all fixed and aggregated variables by their non-fixed counterparts */
static
SCIP_RETCODE applyFixings(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   SCIP_Bool*            infeasible          /**< pointer to store if infeasibility is detected; or NULL if this
                                              *   information is not needed; in this case, we apply all fixings
                                              *   instead of stopping after the first infeasible one */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR* var;
   SCIP_VAR** aggrvars;
   SCIP_Real val;
   SCIP_Real* aggrscalars;
   SCIP_Real fixedval;
   SCIP_Real aggrconst;
   int v;
   int naggrvars;
   int i;

   assert(scip != NULL);
   assert(cons != NULL);

   if( infeasible != NULL )
      *infeasible = FALSE;

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);

   if( consdata->eventdata == NULL )
   {
      SCIP_CONSHDLR* conshdlr;
      SCIP_CONSHDLRDATA* conshdlrdata;

      conshdlr = SCIPconsGetHdlr(cons);
      assert(conshdlr != NULL);

      conshdlrdata = SCIPconshdlrGetData(conshdlr);
      assert(conshdlrdata != NULL);

      /* catch bound change events of variables */
      SCIP_CALL( consCatchAllEvents(scip, cons, conshdlrdata->eventhdlr) );
      assert(consdata->eventdata != NULL);
   }

   if( !consdata->removedfixings )
   {
      SCIP_Real lhssubtrahend;
      SCIP_Real rhssubtrahend;

      /* if an unmodifiable row has been added to the LP, then we cannot apply fixing anymore (cannot change a row)
       * this should not happen, as applyFixings is called in addRelaxation() before creating and adding a row
       */
      assert(consdata->row == NULL || !SCIProwIsInLP(consdata->row) || SCIProwIsModifiable(consdata->row));

      lhssubtrahend = 0.0;
      rhssubtrahend = 0.0;

      SCIPdebugMsg(scip, "applying fixings:\n");
      SCIPdebugPrintCons(scip, cons, NULL);

      v = 0;
      while( v < consdata->nvars )
      {
         var = consdata->vars[v];
         val = consdata->vals[v];
         assert(SCIPvarIsTransformed(var));

         switch( SCIPvarGetStatus(var) )
         {
         case SCIP_VARSTATUS_ORIGINAL:
            SCIPerrorMessage("original variable in transformed linear constraint\n");
            return SCIP_INVALIDDATA;

         case SCIP_VARSTATUS_LOOSE:
         case SCIP_VARSTATUS_COLUMN:
            ++v;
            break;

         case SCIP_VARSTATUS_FIXED:
            assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)));
            fixedval = SCIPvarGetLbGlobal(var);
            if( !SCIPisInfinity(scip, -consdata->lhs) )
            {
               if( SCIPisInfinity(scip, ABS(fixedval)) )
               {
                  if( val * fixedval > 0.0 )
                  {
                     SCIP_CALL( chgLhs(scip, cons, -SCIPinfinity(scip)) );
                  }
                  else
                  {
                     if( infeasible != NULL )
                     {
                        /* if lhs gets infinity it means that the problem is infeasible */
                        *infeasible = TRUE;
                        return SCIP_OKAY;
                     }
                     else
                     {
                        SCIP_CALL( chgLhs(scip, cons, SCIPinfinity(scip)) );
                     }
                  }
               }
               else
                  lhssubtrahend += val * fixedval;
            }
            if( !SCIPisInfinity(scip, consdata->rhs) )
            {
               if( SCIPisInfinity(scip, ABS(fixedval)) )
               {
                  if( val * fixedval > 0.0 )
                  {
                     if( infeasible != NULL )
                     {
                        /* if rhs gets -infinity it means that the problem is infeasible */
                        *infeasible = TRUE;
                        return SCIP_OKAY;
                     }
                     else
                     {
                        SCIP_CALL( chgRhs(scip, cons, -SCIPinfinity(scip)) );
                     }
                  }
                  else
                  {
                     SCIP_CALL( chgRhs(scip, cons, SCIPinfinity(scip)) );
                  }
               }
               else
                  rhssubtrahend += val * fixedval;
            }
            SCIP_CALL( delCoefPos(scip, cons, v) );
            break;

         case SCIP_VARSTATUS_AGGREGATED:
         {
            SCIP_VAR* activevar = SCIPvarGetAggrVar(var);
            SCIP_Real activescalar = val * SCIPvarGetAggrScalar(var);
            SCIP_Real activeconstant = val * SCIPvarGetAggrConstant(var);

            assert(activevar != NULL);
            SCIP_CALL( SCIPgetProbvarSum(scip, &activevar, &activescalar, &activeconstant) );
            assert(activevar != NULL);

            if( !SCIPisZero(scip, activescalar) )
            {
               SCIP_CALL( addCoef(scip, cons, activevar, activescalar) );
            }

            if( !SCIPisZero(scip, activeconstant) )
            {
               if( !SCIPisInfinity(scip, -consdata->lhs) )
                  lhssubtrahend += activeconstant;
               if( !SCIPisInfinity(scip, consdata->rhs) )
                  rhssubtrahend += activeconstant;
            }

            SCIP_CALL( delCoefPos(scip, cons, v) );
            break;
         }
         case SCIP_VARSTATUS_MULTAGGR:
            SCIP_CALL( SCIPflattenVarAggregationGraph(scip, var) );
            naggrvars = SCIPvarGetMultaggrNVars(var);
            aggrvars = SCIPvarGetMultaggrVars(var);
            aggrscalars = SCIPvarGetMultaggrScalars(var);
            for( i = 0; i < naggrvars; ++i )
            {
               SCIP_CALL( addCoef(scip, cons, aggrvars[i], val * aggrscalars[i]) );
            }
            aggrconst = SCIPvarGetMultaggrConstant(var);

            if( !SCIPisInfinity(scip, -consdata->lhs) )
               lhssubtrahend += val * aggrconst;
            if( !SCIPisInfinity(scip, consdata->rhs) )
               rhssubtrahend += val * aggrconst;

            SCIP_CALL( delCoefPos(scip, cons, v) );
            break;

         case SCIP_VARSTATUS_NEGATED:
            SCIP_CALL( addCoef(scip, cons, SCIPvarGetNegationVar(var), -val) );
            aggrconst = SCIPvarGetNegationConstant(var);

            if( !SCIPisInfinity(scip, -consdata->lhs) )
               lhssubtrahend += val * aggrconst;
            if( !SCIPisInfinity(scip, consdata->rhs) )
               rhssubtrahend += val * aggrconst;

            SCIP_CALL( delCoefPos(scip, cons, v) );
            break;

         default:
            SCIPerrorMessage("unknown variable status\n");
            SCIPABORT();
            return SCIP_INVALIDDATA;  /*lint !e527*/
         }
      }

      if( !SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->lhs) )
      {
         /* for large numbers that are relatively equal, substraction can lead to cancellation,
          * causing wrong fixings of other variables --> better use a real zero here;
          * for small numbers, polishing the difference might lead to wrong results -->
          * better use the exact difference in this case
          */
         if( SCIPisEQ(scip, lhssubtrahend, consdata->lhs) && SCIPisFeasGE(scip, REALABS(lhssubtrahend), 1.0) )
         {
            SCIP_CALL( chgLhs(scip, cons, 0.0) );
         }
         else
         {
            SCIP_CALL( chgLhs(scip, cons, consdata->lhs - lhssubtrahend) );
         }
      }
      if( !SCIPisInfinity(scip, consdata->rhs) && !SCIPisInfinity(scip, -consdata->rhs))
      {
         /* for large numbers that are relatively equal, substraction can lead to cancellation,
          * causing wrong fixings of other variables --> better use a real zero here;
          * for small numbers, polishing the difference might lead to wrong results -->
          * better use the exact difference in this case
          */
         if( SCIPisEQ(scip, rhssubtrahend, consdata->rhs ) && SCIPisFeasGE(scip, REALABS(rhssubtrahend), 1.0) )
         {
            SCIP_CALL( chgRhs(scip, cons, 0.0) );
         }
         else
         {
            SCIP_CALL( chgRhs(scip, cons, consdata->rhs - rhssubtrahend) );
         }
      }
      consdata->removedfixings = TRUE;

      SCIPdebugMsg(scip, "after fixings:\n");
      SCIPdebugPrintCons(scip, cons, NULL);

      /* if aggregated variables have been replaced, multiple entries of the same variable are possible and we have
       * to clean up the constraint
       */
      SCIP_CALL( mergeMultiples(scip, cons) );

      SCIPdebugMsg(scip, "after merging:\n");
      SCIPdebugPrintCons(scip, cons, NULL);
   }
   assert(consdata->removedfixings);

#ifndef NDEBUG
   /* check, if all fixings are applied */
   for( v = 0; v < consdata->nvars; ++v )
      assert(SCIPvarIsActive(consdata->vars[v]));
#endif

   return SCIP_OKAY;
}

/** for each variable in the linear constraint, except the inferred variable, adds one bound to the conflict analysis'
 *  candidate store (bound depends on sign of coefficient and whether the left or right hand side was the reason for the
 *  inference variable's bound change); the conflict analysis can be initialized with the linear constraint being the
 *  conflict detecting constraint by using NULL as inferred variable
 */
static
SCIP_RETCODE addConflictBounds(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< constraint that inferred the bound change */
   SCIP_VAR*             infervar,           /**< variable that was deduced, or NULL */
   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index (time stamp of bound change), or NULL for current time */
   int                   inferpos,           /**< position of the inferred variable in the vars array */
   SCIP_Bool             reasonisrhs         /**< is the right hand side responsible for the bound change? */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR** vars;
   SCIP_Real* vals;
   int nvars;
   int i;

   assert(scip != NULL);
   assert(cons != NULL);

   consdata = SCIPconsGetData(cons);

   assert(consdata != NULL);

   vars = consdata->vars;
   vals = consdata->vals;
   nvars = consdata->nvars;

   assert(vars != NULL || nvars == 0);
   assert(vals != NULL || nvars == 0);

   assert(-1 <= inferpos && inferpos < nvars);
   assert((infervar == NULL) == (inferpos == -1));
   assert(inferpos == -1 || vars[inferpos] == infervar); /*lint !e613*/

   /* for each variable, add the bound to the conflict queue, that is responsible for the minimal or maximal
    * residual value, depending on whether the left or right hand side is responsible for the bound change:
    *  - if the right hand side is the reason, the minimal residual activity is responsible
    *  - if the left hand side is the reason, the maximal residual activity is responsible
    */

   /* if the variable is integral we only need to add reason bounds until the propagation could be applied */
   if( infervar == NULL || SCIPvarIsIntegral(infervar) )
   {
      SCIP_Real minresactivity;
      SCIP_Real maxresactivity;
      SCIP_Bool minisrelax;
      SCIP_Bool maxisrelax;
      SCIP_Bool isminsettoinfinity;
      SCIP_Bool ismaxsettoinfinity;

      minresactivity = -SCIPinfinity(scip);
      maxresactivity = SCIPinfinity(scip);

      /* calculate the minimal and maximal global activity of all other variables involved in the constraint */
      if( infervar != NULL )
      {
         assert(vals != NULL); /* for flexelint */
         if( reasonisrhs )
            consdataGetGlbActivityResiduals(scip, consdata, infervar, vals[inferpos], FALSE, &minresactivity, NULL,
               &minisrelax, NULL, &isminsettoinfinity, NULL);
         else
            consdataGetGlbActivityResiduals(scip, consdata, infervar, vals[inferpos], FALSE, NULL, &maxresactivity,
               NULL, &maxisrelax, NULL, &ismaxsettoinfinity);
      }
      else
      {
         if( reasonisrhs )
            consdataGetGlbActivityBounds(scip, consdata, FALSE, &minresactivity, NULL,
               &minisrelax, NULL, &isminsettoinfinity, NULL);
         else
            consdataGetGlbActivityBounds(scip, consdata, FALSE, NULL, &maxresactivity,
               NULL, &maxisrelax, NULL, &ismaxsettoinfinity);
      }

      /* we can only do something clever, if the residual activity is finite and not relaxed */
      if( (reasonisrhs && !isminsettoinfinity && !minisrelax) || (!reasonisrhs && !ismaxsettoinfinity && !maxisrelax) ) /*lint !e644*/
      {
         SCIP_Real rescap;
         SCIP_Bool resactisinf;

         resactisinf = FALSE;

         /* calculate the residual capacity that would be left, if the variable would be set to one more / one less
          * than its inferred bound
          */
         if( infervar != NULL )
         {
            assert(vals != NULL); /* for flexelint */

            if( reasonisrhs )
            {
               if( SCIPisUpdateUnreliable(scip, minresactivity, consdata->lastglbminactivity) )
               {
                  consdataGetReliableResidualActivity(scip, consdata, infervar, &minresactivity, TRUE, TRUE);
                  if( SCIPisInfinity(scip, -minresactivity) )
                     resactisinf = TRUE;
               }
               rescap = consdata->rhs - minresactivity;
            }
            else
            {
               if( SCIPisUpdateUnreliable(scip, maxresactivity, consdata->lastglbmaxactivity) )
               {
                  consdataGetReliableResidualActivity(scip, consdata, infervar, &maxresactivity, FALSE, TRUE);
                  if( SCIPisInfinity(scip, maxresactivity) )
                     resactisinf = TRUE;
               }
               rescap = consdata->lhs - maxresactivity;
            }

            if( reasonisrhs == (vals[inferpos] > 0.0) )
               rescap -= vals[inferpos] * (SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) + 1.0);
            else
               rescap -= vals[inferpos] * (SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) - 1.0);
         }
         else
            rescap = (reasonisrhs ? consdata->rhs - minresactivity : consdata->lhs - maxresactivity);

         if( !resactisinf )
         {
            /* now add bounds as reasons until the residual capacity is exceeded */
            for( i = 0; i < nvars; ++i )
            {
               assert( vars != NULL && vals != NULL ); /* for lint */

               /* zero coefficients and the inferred variable can be ignored */
               if( vars[i] == infervar || SCIPisZero(scip, vals[i]) )
                  continue;

               /* check if the residual capacity is exceeded */
               if( (reasonisrhs && SCIPisFeasNegative(scip, rescap))
                  || (!reasonisrhs && SCIPisFeasPositive(scip, rescap)) )
                  break;

               /* update the residual capacity due to the local bound of this variable */
               if( reasonisrhs == (vals[i] > 0.0) )
               {
                  /* rhs is reason and coeff is positive, or lhs is reason and coeff is negative -> lower bound */
                  SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
                  rescap -= vals[i] * (SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) - SCIPvarGetLbGlobal(vars[i]));
               }
               else
               {
                  /* lhs is reason and coeff is positive, or rhs is reason and coeff is negative -> upper bound */
                  SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
                  rescap -= vals[i] * (SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) - SCIPvarGetUbGlobal(vars[i]));
               }
            }
            return SCIP_OKAY;
         }
      }
   }

   /* for a bound change on a continuous variable, all locally changed bounds are responsible */
   for( i = 0; i < nvars; ++i )
   {
      assert(vars != NULL); /* for flexelint */
      assert(vals != NULL); /* for flexelint */

      /* zero coefficients and the inferred variable can be ignored */
      if( vars[i] == infervar || SCIPisZero(scip, vals[i]) )
         continue;

      if( reasonisrhs == (vals[i] > 0.0) )
      {
         /* rhs is reason and coeff is positive, or lhs is reason and coeff is negative -> lower bound is responsible */
         SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
      }
      else
      {
         /* lhs is reason and coeff is positive, or rhs is reason and coeff is negative -> upper bound is responsible */
         SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
      }
   }

   return SCIP_OKAY;
}

/** for each variable in the linear ranged row constraint, except the inferred variable, adds the bounds of all fixed
 *  variables to the conflict analysis' candidate store; the conflict analysis can be initialized
 *  with the linear constraint being the conflict detecting constraint by using NULL as inferred variable
 */
static
SCIP_RETCODE addConflictFixedVars(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< constraint that inferred the bound change */
   SCIP_VAR*             infervar,           /**< variable that was deduced, or NULL */
   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index (time stamp of bound change), or NULL for current time */
   int                   inferpos            /**< position of the inferred variable in the vars array, or -1 */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR** vars;
   int nvars;
   int v;

   assert(scip != NULL);
   assert(cons != NULL);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   vars = consdata->vars;
   nvars = consdata->nvars;
   assert(vars != NULL || nvars == 0);
   assert(-1 <= inferpos && inferpos < nvars);
   assert((infervar == NULL) == (inferpos == -1));
   assert(inferpos == -1 || vars != NULL);
   assert(inferpos == -1 || vars[inferpos] == infervar); /*lint !e613*/

   /* collect all fixed variables */
   for( v = nvars - 1; v >= 0; --v )
   {
      assert(vars != NULL); /* for flexelint */

      /* need to add old bounds before propagation of inferrence variable */
      if( vars[v] == infervar )
      {
         assert(vars[v] != NULL);

         if( !SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPvarGetLbGlobal(vars[v])) )
         {
            /* @todo get boundchange index before this last boundchange and correct the index */
            SCIP_CALL( SCIPaddConflictLb(scip, vars[v], bdchgidx) );
         }

         if( !SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPvarGetUbGlobal(vars[v])) )
         {
            /* @todo get boundchange index before this last boundchange and correct the index */
            SCIP_CALL( SCIPaddConflictUb(scip, vars[v], bdchgidx) );
         }

         continue;
      }

      /* check for fixed variables */
      if( SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[v], bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, vars[v], bdchgidx, FALSE)) )
      {
         /* add all bounds of fixed variables which lead to the boundchange of the given inference variable */
         SCIP_CALL( SCIPaddConflictLb(scip, vars[v], bdchgidx) );
         SCIP_CALL( SCIPaddConflictUb(scip, vars[v], bdchgidx) );
      }
   }

   return SCIP_OKAY;
}

/** add reasoning variables to conflict candidate queue which led to the conflict */
static
SCIP_RETCODE addConflictReasonVars(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_VAR**            vars,               /**< variables reasoning the infeasibility */
   int                   nvars,              /**< number of variables reasoning the infeasibility */
   SCIP_VAR*             var,                /**< variable which was tried to fix/tighten, or NULL */
   SCIP_Real             bound               /**< bound of variable which was tried to apply, or SCIP_INVALID */
   )
{
   int v;

   assert(scip != NULL);

   /* collect all variables for which the local bounds differ from their global bounds */
   for( v = nvars - 1; v >= 0; --v )
   {
      assert(vars != NULL);

      /* check for local bound changes variables */
      if( !SCIPisEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetLbGlobal(vars[v])) )
      {
         /* add conflict bound */
         SCIP_CALL( SCIPaddConflictLb(scip, vars[v], 0) );
      }

      if( !SCIPisEQ(scip, SCIPvarGetUbLocal(vars[v]), SCIPvarGetUbGlobal(vars[v])) )
      {
         SCIP_CALL( SCIPaddConflictUb(scip, vars[v], 0) );
      }
   }

   if( var != NULL )
   {
      if( bound < SCIPvarGetLbLocal(var) )
      {
         SCIP_CALL( SCIPaddConflictLb(scip, var, 0) );
      }

      if( bound > SCIPvarGetUbLocal(var) )
      {
         SCIP_CALL( SCIPaddConflictUb(scip, var, 0) );
      }
   }

   return SCIP_OKAY;
}

/** resolves a propagation on the given variable by supplying the variables needed for applying the corresponding
 *  propagation rule (see propagateCons()):
 *   (1) activity residuals of all other variables tighten bounds of single variable
 */
static
SCIP_RETCODE resolvePropagation(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< constraint that inferred the bound change */
   SCIP_VAR*             infervar,           /**< variable that was deduced */
   INFERINFO             inferinfo,          /**< inference information */
   SCIP_BOUNDTYPE        boundtype,          /**< the type of the changed bound (lower or upper bound) */
   SCIP_BDCHGIDX*        bdchgidx,           /**< bound change index (time stamp of bound change), or NULL for current time */
   SCIP_RESULT*          result              /**< pointer to store the result of the propagation conflict resolving call */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR** vars;
#ifndef NDEBUG
   SCIP_Real* vals;
#endif
   int nvars;
   int inferpos;

   assert(scip != NULL);
   assert(cons != NULL);
   assert(result != NULL);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   vars = consdata->vars;
   nvars = consdata->nvars;
#ifndef NDEBUG
   vals = consdata->vals;
   assert(vars != NULL);
   assert(vals != NULL);
#endif

   /* get the position of the inferred variable in the vars array */
   inferpos = inferInfoGetPos(inferinfo);
   if( inferpos >= nvars || vars[inferpos] != infervar )
   {
      /* find inference variable in constraint */
      /**@todo use a binary search here; the variables can be sorted by variable index */
      for( inferpos = 0; inferpos < nvars && vars[inferpos] != infervar; ++inferpos )
      {}
   }
   assert(inferpos < nvars);
   assert(vars[inferpos] == infervar);
   assert(!SCIPisZero(scip, vals[inferpos]));

   switch( inferInfoGetProprule(inferinfo) )
   {
   case PROPRULE_1_RHS:
      /* the bound of the variable was tightened, because the minimal or maximal residual activity of the linear
       * constraint (only taking the other variables into account) didn't leave enough space for a larger
       * domain in order to not exceed the right hand side of the inequality
       */
      assert((vals[inferpos] > 0.0) == (boundtype == SCIP_BOUNDTYPE_UPPER));
      SCIP_CALL( addConflictBounds(scip, cons, infervar, bdchgidx, inferpos, TRUE) );
      *result = SCIP_SUCCESS;
      break;

   case PROPRULE_1_LHS:
      /* the bound of the variable was tightened, because the minimal or maximal residual activity of the linear
       * constraint (only taking the other variables into account) didn't leave enough space for a larger
       * domain in order to not fall below the left hand side of the inequality
       */
      assert((vals[inferpos] > 0.0) == (boundtype == SCIP_BOUNDTYPE_LOWER));
      SCIP_CALL( addConflictBounds(scip, cons, infervar, bdchgidx, inferpos, FALSE) );
      *result = SCIP_SUCCESS;
      break;

   case PROPRULE_1_RANGEDROW:
      /* the bound of the variable was tightened, because some variables were already fixed and the leftover only allow
       * the given inference variable to their bounds in this given ranged row
       */

      /* check that we really have a ranged row here */
      assert(!SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->rhs));
      SCIP_CALL( addConflictFixedVars(scip, cons, infervar, bdchgidx, inferpos) );
      *result = SCIP_SUCCESS;
      break;

   case PROPRULE_INVALID:
   default:
      SCIPerrorMessage("invalid inference information %d in linear constraint <%s> at position %d for %s bound of variable <%s>\n",
         inferInfoGetProprule(inferinfo), SCIPconsGetName(cons), inferInfoGetPos(inferinfo),
         boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", SCIPvarGetName(infervar));
      SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
      SCIPinfoMessage(scip, NULL, ";\n");
      return SCIP_INVALIDDATA;
   }

   return SCIP_OKAY;
}

/** analyzes conflicting bounds on given constraint, and adds conflict constraint to problem */
static
SCIP_RETCODE analyzeConflict(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< conflict detecting constraint */
   SCIP_Bool             reasonisrhs         /**< is the right hand side responsible for the conflict? */
   )
{
   /* conflict analysis can only be applied in solving stage and if it is turned on */
   if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
      return SCIP_OKAY;

   /* initialize conflict analysis */
   SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );

   /* add the conflicting bound for each variable of infeasible constraint to conflict candidate queue */
   SCIP_CALL( addConflictBounds(scip, cons, NULL, NULL, -1, reasonisrhs) );

   /* analyze the conflict */
   SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );

   return SCIP_OKAY;
}

/** check if there is any hope of tightening some bounds */
static
SCIP_Bool canTightenBounds(
   SCIP_CONS*            cons                /**< linear constraint */
   )
{
   SCIP_CONSDATA* consdata;
   int infcountmin;
   int infcountmax;

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);

   infcountmin = consdata->minactivityneginf
      + consdata->minactivityposinf
      + consdata->minactivityneghuge
      + consdata->minactivityposhuge;
   infcountmax = consdata->maxactivityneginf
      + consdata->maxactivityposinf
      + consdata->maxactivityneghuge
      + consdata->maxactivityposhuge;

   if( infcountmin > 1 && infcountmax > 1 )
      return FALSE;

   return TRUE;
}

/** tighten upper bound */
static
SCIP_RETCODE tightenVarUb(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   int                   pos,                /**< variable position */
   PROPRULE              proprule,           /**< propagation rule that deduced the value */
   SCIP_Real             newub,              /**< new upper bound */
   SCIP_Real             oldub,              /**< old upper bound */
   SCIP_Bool*            cutoff,             /**< pointer to store whether the node can be cut off */
   int*                  nchgbds,            /**< pointer to count the total number of tightened bounds */
   SCIP_Bool             force               /**< should a possible bound change be forced even if below bound strengthening tolerance */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR* var;
   SCIP_Real lb;
   SCIP_Bool infeasible;
   SCIP_Bool tightened;

   assert(cons != NULL);
   assert(!SCIPisInfinity(scip, newub));

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   var = consdata->vars[pos];
   assert(var != NULL);

   lb = SCIPvarGetLbLocal(var);
   newub = SCIPadjustedVarUb(scip, var, newub);

   if( force || SCIPisUbBetter(scip, newub, lb, oldub) )
   {
      SCIP_VARTYPE vartype;

      SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, old bds=[%.15g,%.15g], val=%.15g, activity=[%.15g,%.15g], sides=[%.15g,%.15g] -> newub=%.15g\n",
         SCIPconsGetName(cons), SCIPvarGetName(var), lb, oldub, consdata->vals[pos],
         QUAD_TO_DBL(consdata->minactivity), QUAD_TO_DBL(consdata->maxactivity), consdata->lhs, consdata->rhs, newub);

      vartype = SCIPvarGetType(var);

      /* tighten upper bound */
      SCIP_CALL( SCIPinferVarUbCons(scip, var, newub, cons, getInferInt(proprule, pos), force, &infeasible, &tightened) );

      if( infeasible )
      {
         SCIPdebugMsg(scip, "linear constraint <%s>: cutoff  <%s>, new bds=[%.15g,%.15g]\n",
            SCIPconsGetName(cons), SCIPvarGetName(var), lb, newub);

         /* analyze conflict */
         SCIP_CALL( analyzeConflict(scip, cons, TRUE) );

         *cutoff = TRUE;
      }
      else if( tightened )
      {
         assert(SCIPisFeasLE(scip, SCIPvarGetUbLocal(var), oldub));
         SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, new bds=[%.15g,%.15g]\n",
            SCIPconsGetName(cons), SCIPvarGetName(var), lb, SCIPvarGetUbLocal(var));

         (*nchgbds)++;

         /* if variable type was changed we might be able to upgrade the constraint */
         if( vartype != SCIPvarGetType(var) )
            consdata->upgradetried = FALSE;
      }
   }
   return SCIP_OKAY;
}

/** tighten lower bound */
static
SCIP_RETCODE tightenVarLb(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   int                   pos,                /**< variable position */
   PROPRULE              proprule,           /**< propagation rule that deduced the value */
   SCIP_Real             newlb,              /**< new lower bound */
   SCIP_Real             oldlb,              /**< old lower bound */
   SCIP_Bool*            cutoff,             /**< pointer to store whether the node can be cut off */
   int*                  nchgbds,            /**< pointer to count the total number of tightened bounds */
   SCIP_Bool             force               /**< should a possible bound change be forced even if below bound strengthening tolerance */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR* var;
   SCIP_Real ub;
   SCIP_Bool infeasible;
   SCIP_Bool tightened;

   assert(cons != NULL);
   assert(!SCIPisInfinity(scip, newlb));

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   var = consdata->vars[pos];
   assert(var != NULL);

   ub = SCIPvarGetUbLocal(var);
   newlb = SCIPadjustedVarLb(scip, var, newlb);

   if( force || SCIPisLbBetter(scip, newlb, oldlb, ub) )
   {
      SCIP_VARTYPE vartype;

      SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, old bds=[%.15g,%.15g], val=%.15g, activity=[%.15g,%.15g], sides=[%.15g,%.15g] -> newlb=%.15g\n",
         SCIPconsGetName(cons), SCIPvarGetName(var), oldlb, ub, consdata->vals[pos],
         QUAD_TO_DBL(consdata->minactivity), QUAD_TO_DBL(consdata->maxactivity), consdata->lhs, consdata->rhs, newlb);

      vartype = SCIPvarGetType(var);

      /* tighten lower bound */
      SCIP_CALL( SCIPinferVarLbCons(scip, var, newlb, cons, getInferInt(proprule, pos), force, &infeasible, &tightened) );

      if( infeasible )
      {
         SCIPdebugMsg(scip, "linear constraint <%s>: cutoff  <%s>, new bds=[%.15g,%.15g]\n",
            SCIPconsGetName(cons), SCIPvarGetName(var), newlb, ub);

         /* analyze conflict */
         SCIP_CALL( analyzeConflict(scip, cons, FALSE) );

         *cutoff = TRUE;
      }
      else if( tightened )
      {
         assert(SCIPisFeasGE(scip, SCIPvarGetLbLocal(var), oldlb));
         SCIPdebugMsg(scip, "linear constraint <%s>: tighten <%s>, new bds=[%.15g,%.15g]\n",
            SCIPconsGetName(cons), SCIPvarGetName(var), SCIPvarGetLbLocal(var), ub);

         (*nchgbds)++;

         /* if variable type was changed we might be able to upgrade the constraint */
         if( vartype != SCIPvarGetType(var) )
            consdata->upgradetried = FALSE;
      }
   }
   return SCIP_OKAY;
}

/** tightens bounds of a single variable due to activity bounds (easy case) */
static
SCIP_RETCODE tightenVarBoundsEasy(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   int                   pos,                /**< position of the variable in the vars array */
   SCIP_Bool*            cutoff,             /**< pointer to store whether the node can be cut off */
   int*                  nchgbds,            /**< pointer to count the total number of tightened bounds */
   SCIP_Bool             force               /**< should a possible bound change be forced even if below bound strengthening tolerance */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR* var;
   SCIP_Real val;
   SCIP_Real lb;
   SCIP_Real ub;
   SCIP_Real lhs;
   SCIP_Real rhs;

   assert(scip != NULL);
   assert(cons != NULL);
   assert(cutoff != NULL);
   assert(nchgbds != NULL);

   /* we cannot tighten variables' bounds, if the constraint may be not complete */
   if( SCIPconsIsModifiable(cons) )
      return SCIP_OKAY;

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(0 <= pos && pos < consdata->nvars);

   *cutoff = FALSE;

   var = consdata->vars[pos];
   assert(var != NULL);

   /* we cannot tighten bounds of multi-aggregated variables */
   if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
      return SCIP_OKAY;

   val = consdata->vals[pos];
   lhs = consdata->lhs;
   rhs = consdata->rhs;
   assert(!SCIPisZero(scip, val));
   assert(!SCIPisInfinity(scip, lhs));
   assert(!SCIPisInfinity(scip, -rhs));

   lb = SCIPvarGetLbLocal(var);
   ub = SCIPvarGetUbLocal(var);
   assert(SCIPisLE(scip, lb, ub));

   /* recompute activities if needed */
   if( !consdata->validactivities )
      consdataCalcActivities(scip, consdata);
   assert(consdata->validactivities);
   if( !consdata->validminact )
      consdataRecomputeMinactivity(scip, consdata);
   assert(consdata->validminact);

   if( val > 0.0 )
   {
      /* check, if we can tighten the variable's upper bound */
      if( !SCIPisInfinity(scip, rhs) )
      {
         SCIP_Real slack;
         SCIP_Real alpha;

         /* min activity should be valid at this point (if this is not true, then some decisions might be wrong!) */
         assert(consdata->validminact);

         /* if the minactivity is larger than the right hand side by feasibility epsilon, the constraint is infeasible */
         if( SCIPisFeasLT(scip, rhs, QUAD_TO_DBL(consdata->minactivity)) )
         {
            SCIPdebugMsg(scip, "linear constraint <%s>: cutoff  <%s>, minactivity=%.15g > rhs=%.15g\n",
               SCIPconsGetName(cons), SCIPvarGetName(var), QUAD_TO_DBL(consdata->minactivity), rhs);

            *cutoff = TRUE;
            return SCIP_OKAY;
         }

         slack = rhs - QUAD_TO_DBL(consdata->minactivity);

         /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
          * it to zero
          */
         if( !SCIPisPositive(scip, slack) )
            slack = 0.0;

         alpha = val * (ub - lb);
         assert(!SCIPisNegative(scip, alpha));

         if( SCIPisSumGT(scip, alpha, slack)  || (force && SCIPisGT(scip, alpha, slack)) )
         {
            SCIP_Real newub;

            /* compute new upper bound */
            newub = lb + (slack / val);

            SCIP_CALL( tightenVarUb(scip, cons, pos, PROPRULE_1_RHS, newub, ub, cutoff, nchgbds, force) );

            if( *cutoff )
            {
               SCIPdebugMsg(scip, "linear constraint <%s>: cutoff  <%s>, new bds=[%.15g,%.15g]\n",
                  SCIPconsGetName(cons), SCIPvarGetName(var), lb, newub);

               return SCIP_OKAY;
            }

            /* collect the new upper bound which is needed for the lower bound computation */
            ub = SCIPvarGetUbLocal(var);
         }
      }

      /* check, if we can tighten the variable's lower bound */
      if( !SCIPisInfinity(scip, -lhs) )
      {
         SCIP_Real slack;
         SCIP_Real alpha;

         /* make sure the max activity is reliable */
         if( !consdata->validmaxact )
         {
            consdataRecomputeMaxactivity(scip, consdata);
         }
         assert(consdata->validmaxact);

         /* if the maxactivity is smaller than the left hand side by feasibility epsilon, the constraint is infeasible */
         if( SCIPisFeasLT(scip, QUAD_TO_DBL(consdata->maxactivity), lhs) )
         {
            SCIPdebugMsg(scip, "linear constraint <%s>: cutoff  <%s>, maxactivity=%.15g < lhs=%.15g\n",
               SCIPconsGetName(cons), SCIPvarGetName(var), QUAD_TO_DBL(consdata->maxactivity), lhs);

            *cutoff = TRUE;
            return SCIP_OKAY;
         }

         slack = QUAD_TO_DBL(consdata->maxactivity) - lhs;

         /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
          * it to zero
          */
         if( !SCIPisPositive(scip, slack) )
            slack = 0.0;

         alpha = val * (ub - lb);
         assert(!SCIPisNegative(scip, alpha));

         if( SCIPisSumGT(scip, alpha, slack) || (force && SCIPisGT(scip, alpha, slack)) )
         {
            SCIP_Real newlb;

            /* compute new lower bound */
            newlb = ub - (slack / val);

            SCIP_CALL( tightenVarLb(scip, cons, pos, PROPRULE_1_LHS, newlb, lb, cutoff, nchgbds, force) );

            if( *cutoff )
            {
               SCIPdebugMsg(scip, "linear constraint <%s>: cutoff  <%s>, new bds=[%.15g,%.15g]\n",
                  SCIPconsGetName(cons), SCIPvarGetName(var), newlb, ub);

               return SCIP_OKAY;
            }
         }
      }
   }
   else
   {
      /* check, if we can tighten the variable's lower bound */
      if( !SCIPisInfinity(scip, rhs) )
      {
         SCIP_Real slack;
         SCIP_Real alpha;

         /* min activity should be valid at this point (if this is not true, then some decisions might be wrong!) */
         assert(consdata->validminact);

         /* if the minactivity is larger than the right hand side by feasibility epsilon, the constraint is infeasible */
         if( SCIPisFeasLT(scip, rhs, QUAD_TO_DBL(consdata->minactivity)) )
         {
            SCIPdebugMsg(scip, "linear constraint <%s>: cutoff  <%s>, minactivity=%.15g > rhs=%.15g\n",
               SCIPconsGetName(cons), SCIPvarGetName(var), QUAD_TO_DBL(consdata->minactivity), rhs);

            *cutoff = TRUE;
            return SCIP_OKAY;
         }

         slack = rhs - QUAD_TO_DBL(consdata->minactivity);

         /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
          * it to zero
          */
         if( !SCIPisPositive(scip, slack) )
            slack = 0.0;

         alpha = val * (lb - ub);
         assert(!SCIPisNegative(scip, alpha));

         if( SCIPisSumGT(scip, alpha, slack) || (force && SCIPisGT(scip, alpha, slack)) )
         {
            SCIP_Real newlb;

            /* compute new lower bound */
            newlb = ub + slack / val;

            SCIP_CALL( tightenVarLb(scip, cons, pos, PROPRULE_1_RHS, newlb, lb, cutoff, nchgbds, force) );

            if( *cutoff )
            {
               SCIPdebugMsg(scip, "linear constraint <%s>: cutoff  <%s>, new bds=[%.15g,%.15g]\n",
                  SCIPconsGetName(cons), SCIPvarGetName(var), newlb, ub);

               return SCIP_OKAY;
            }
            /* collect the new lower bound which is needed for the upper bound computation */
            lb = SCIPvarGetLbLocal(var);
         }
      }

      /* check, if we can tighten the variable's upper bound */
      if( !SCIPisInfinity(scip, -lhs) )
      {
         SCIP_Real slack;
         SCIP_Real alpha;

         /* make sure the max activity is reliable */
         if( !consdata->validmaxact )
         {
            consdataRecomputeMaxactivity(scip, consdata);
         }
         assert(consdata->validmaxact);

         /* if the maxactivity is smaller than the left hand side by feasibility epsilon, the constraint is infeasible */
         if( SCIPisFeasLT(scip, QUAD_TO_DBL(consdata->maxactivity), lhs) )
         {
            SCIPdebugMsg(scip, "linear constraint <%s>: cutoff  <%s>, maxactivity=%.15g < lhs=%.15g\n",
               SCIPconsGetName(cons), SCIPvarGetName(var), QUAD_TO_DBL(consdata->maxactivity), lhs);

            *cutoff = TRUE;
            return SCIP_OKAY;
         }

         slack = QUAD_TO_DBL(consdata->maxactivity) - lhs;

         /* if the slack is zero in tolerances (or negative, but not enough to make the constraint infeasible), we set
          * it to zero
          */
         if( !SCIPisPositive(scip, slack) )
            slack = 0.0;

         alpha = val * (lb - ub);
         assert(!SCIPisNegative(scip, alpha));

         if( SCIPisSumGT(scip, alpha, slack) || (force && SCIPisGT(scip, alpha, slack)) )
         {
            SCIP_Real newub;

            /* compute new upper bound */
            newub = lb - (slack / val);

            SCIP_CALL( tightenVarUb(scip, cons, pos, PROPRULE_1_LHS, newub, ub, cutoff, nchgbds, force) );

            if( *cutoff )
            {
               SCIPdebugMsg(scip, "linear constraint <%s>: cutoff  <%s>, new bds=[%.15g,%.15g]\n",
                  SCIPconsGetName(cons), SCIPvarGetName(var), lb, newub);

               return SCIP_OKAY;
            }
         }
      }
   }

   return SCIP_OKAY;
}

/** analyzes conflicting bounds on given ranged row constraint, and adds conflict constraint to problem */
static
SCIP_RETCODE analyzeConflictRangedRow(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< conflict detecting constraint */
   SCIP_VAR**            vars,               /**< variables reasoning the infeasibility */
   int                   nvars,              /**< number of variables reasoning the infeasibility */
   SCIP_VAR*             var,                /**< variable which was tried to fix/tighten, or NULL */
   SCIP_Real             bound               /**< bound of variable which was tried to apply, or SCIP_INVALID */
   )
{
#ifndef NDEBUG
   SCIP_CONSDATA* consdata;

   assert(scip != NULL);
   assert(cons != NULL);

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(!SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->rhs));
#endif

   /* conflict analysis can only be applied in solving stage and if it is turned on */
   if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
      return SCIP_OKAY;

   /* initialize conflict analysis */
   SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );

   /* add the conflicting fixed variables of this ranged row constraint to conflict candidate queue */
   SCIP_CALL( addConflictFixedVars(scip, cons, NULL, NULL, -1) );

   /* add reasoning variables to conflict candidate queue which led to the conflict */
   SCIP_CALL( addConflictReasonVars(scip, vars, nvars, var, bound) );

   /* analyze the conflict */
   SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );

   return SCIP_OKAY;
}

/** propagate ranged rows
 *
 *  Check ranged rows for possible solutions, possibly detect infeasibility, fix variables due to having only one possible
 *  solution, tighten bounds if having only two possible solutions or add constraints which propagate a subset of
 *  variables better.
 *
 *  Example:
 *  c1: 12 x1 + 9  x2 - x3 = 0  with x1, x2 free and 1 <= x3 <= 2
 *
 *  x3 needs to be a multiple of 3, so the instance is infeasible.
 *
 *  Example:
 *  c1: 12 x1 + 9  x2 - x3 = 1  with x1, x2 free and 1 <= x3 <= 2
 *
 *  The only possible value for x3 is 2, so the variable will be fixed.
 *
 *  @todo add holes if possible
 */
static
SCIP_RETCODE rangedRowPropagation(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< linear constraint */
   SCIP_Bool*            cutoff,             /**< pointer to store TRUE, if a cutoff was found */
   int*                  nfixedvars,         /**< pointer to count number of fixed variables */
   int*                  nchgbds,            /**< pointer to count the number of bound changes */
   int*                  naddconss           /**< pointer to count number of added constraints */
   )
{
   SCIP_CONSHDLRDATA* conshdlrdata;
   SCIP_CONSHDLR* conshdlr;
   SCIP_CONSDATA* consdata;
   SCIP_VAR** infcheckvars;
   SCIP_Real* infcheckvals;
   SCIP_Real minactinfvars;
   SCIP_Real maxactinfvars;
   SCIP_Real lb;
   SCIP_Real ub;
   SCIP_Real feastol;
   SCIP_Real fixedact;
   SCIP_Real lhs;
   SCIP_Real rhs;
   SCIP_Real absminbincoef;
   SCIP_Longint gcd;
   SCIP_Longint gcdtmp;
   SCIP_Bool minactinfvarsinvalid;
   SCIP_Bool maxactinfvarsinvalid;
   SCIP_Bool possiblegcd;
   SCIP_Bool gcdisone;
   SCIP_Bool addartconss;
   int ninfcheckvars;
   int nunfixedvars;
   int nfixedconsvars;
   int ncontvars;
   int pos;
   int v;

   assert(scip != NULL);
   assert(cons != NULL);
   assert(cutoff != NULL);
   assert(nfixedvars != NULL);
   assert(nchgbds != NULL);
   assert(naddconss != NULL);

   /* modifiable constraint can be changed so we do not have all necessary information */
   if( SCIPconsIsModifiable(cons) )
      return SCIP_OKAY;

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);

   /* we already did full ranged row propagation */
   if( consdata->rangedrowpropagated == 2 )
      return SCIP_OKAY;

   /* at least three variables are needed */
   if( consdata->nvars < 3 )
      return SCIP_OKAY;

   /* do nothing on normal inequalities */
   if( SCIPisInfinity(scip, -consdata->lhs) || SCIPisInfinity(scip, consdata->rhs) )
      return SCIP_OKAY;

   /* get constraint handler data */
   conshdlr = SCIPconsGetHdlr(cons);
   assert(conshdlr != NULL);
   conshdlrdata = SCIPconshdlrGetData(conshdlr);
   assert(conshdlrdata != NULL);

   addartconss = conshdlrdata->rangedrowartcons && SCIPgetDepth(scip) < 1 && !SCIPinProbing(scip) && !SCIPinRepropagation(scip);

   /* we may add artificial constraints */
   if( addartconss )
      consdata->rangedrowpropagated = 2;
   /* we are not allowed to add artificial constraints during propagation; if nothing changed on this constraint since
    * the last rangedrowpropagation, we can stop; otherwise, we mark this constraint to be rangedrowpropagated without
    * artificial constraints
    */
   else
   {
      if( consdata->rangedrowpropagated > 0 )
         return SCIP_OKAY;

      consdata->rangedrowpropagated = 1;
   }
   fixedact = 0;
   nfixedconsvars = 0;
   /* calculate fixed activity and number of fixed variables */
   for( v = consdata->nvars - 1; v >= 0; --v )
   {
      /* all zero coefficients should be eliminated */
      assert(!SCIPisZero(scip, consdata->vals[v]));

      if( SCIPisEQ(scip, SCIPvarGetLbLocal(consdata->vars[v]), SCIPvarGetUbLocal(consdata->vars[v])) )
      {
         fixedact += SCIPvarGetLbLocal(consdata->vars[v]) * consdata->vals[v];
         ++nfixedconsvars;
      }
   }

   /* do not work with huge fixed activities */
   if( SCIPisHugeValue(scip, REALABS(fixedact)) )
      return SCIP_OKAY;

   /* compute lhs and rhs for unfixed variables only and get number of unfixed variables */
   assert(!SCIPisInfinity(scip, -fixedact) && !SCIPisInfinity(scip, fixedact));
   lhs = consdata->lhs - fixedact;
   rhs = consdata->rhs - fixedact;
   nunfixedvars = consdata->nvars - nfixedconsvars;

   /* allocate temporary memory for variables and coefficients which may lead to infeasibility */
   SCIP_CALL( SCIPallocBufferArray(scip, &infcheckvars, nunfixedvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &infcheckvals, nunfixedvars) );

   absminbincoef = SCIP_REAL_MAX;
   ncontvars = 0;
   gcdisone = TRUE;
   possiblegcd = TRUE;

   /* we now partition all unfixed variables in two groups:
    *
    * the first one contains all integral variable with integral
    * coefficient so that all variables in this group will have a gcd greater than 1, this group will be implicitly
    * given
    *