cons_setppc.c

Go to the documentation of this file.

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

/**@file   cons_setppc.c
 * @ingroup DEFPLUGINS_CONS
 * @brief  Constraint handler for the set partitioning / packing / covering constraints \f$1^T x\ \{=, \le, \ge\}\ 1\f$.
 * @author Tobias Achterberg
 * @author Michael Winkler
 */

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

#include "blockmemshell/memory.h"
#include "scip/cons_nonlinear.h"
#include "scip/cons_linear.h"
#include "scip/cons_setppc.h"
#include "scip/pub_conflict.h"
#include "scip/pub_cons.h"
#include "scip/pub_event.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_conflict.h"
#include "scip/scip_cons.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_nlp.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_var.h"
#include "scip/symmetry_graph.h"
#include "symmetry/struct_symmetry.h"
#include <string.h>


#define CONSHDLR_NAME          "setppc"
#define CONSHDLR_DESC          "set partitioning / packing / covering constraints"
#define CONSHDLR_SEPAPRIORITY   +700000 /**< priority of the constraint handler for separation */
#define CONSHDLR_ENFOPRIORITY   -700000 /**< priority of the constraint handler for constraint enforcing */
#define CONSHDLR_CHECKPRIORITY  -700000 /**< 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_ALWAYS
#define CONSHDLR_PROP_TIMING             SCIP_PROPTIMING_BEFORELP

#define LINCONSUPGD_PRIORITY    +700000 /**< priority of the constraint handler for upgrading of linear constraints */
#define NONLINCONSUPGD_PRIORITY +700000 /**< priority of the constraint handler for upgrading of nonlinear constraints */

#define EVENTHDLR_NAME         "setppc"
#define EVENTHDLR_DESC         "bound change event handler for set partitioning / packing / covering constraints"

#define CONFLICTHDLR_NAME      "setppc"
#define CONFLICTHDLR_DESC      "conflict handler creating set covering constraints"
#define CONFLICTHDLR_PRIORITY  LINCONSUPGD_PRIORITY

#define DEFAULT_PRESOLPAIRWISE     TRUE /**< should pairwise constraint comparison be performed in presolving? */

#define HASHSIZE_SETPPCCONS         500 /**< minimal size of hash table in setppc constraint tables */
#define DEFAULT_PRESOLUSEHASHING   TRUE /**< should hash table be used for detecting redundant constraints in advance */
#define NMINCOMPARISONS          200000 /**< number for minimal pairwise presolving comparisons */
#define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */

#define DEFAULT_RANDSEED              3

/*#define VARUSES*/  /* activate variable usage counting, that is necessary for LP and pseudo branching */
/*#define BRANCHLP*/ /* BRANCHLP is only useful if the ENFOPRIORITY is set to a positive value */
#ifdef BRANCHLP
#define MINBRANCHWEIGHT             0.3 /**< minimum weight of both sets in binary set branching */
#define MAXBRANCHWEIGHT             0.7 /**< maximum weight of both sets in binary set branching */
#endif
#define DEFAULT_NPSEUDOBRANCHES       2 /**< number of children created in pseudo branching (0: disable branching) */
#define DEFAULT_DUALPRESOLVING     TRUE /**< should dual presolving steps be performed? */

#define DEFAULT_CLIQUELIFTING     FALSE /**< should we try to lift variables into other clique constraints, fix
                                         *   variables, aggregate them, and also shrink the amount of variables in
                                         *   clique constraints
                                         */
#define DEFAULT_ADDVARIABLESASCLIQUES FALSE/**< should we try to generate extra clique constraint out of all binary
                                            *   variables to hopefully fasten the detection of redundant clique
                                            *   constraints */
#define DEFAULT_CLIQUESHRINKING    TRUE /**< should we try to shrink the number of variables in a clique constraints, by
                                         *   replacing more than one variable by only one
                                         */

/* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */

/*
 * Data structures
 */

/** constraint handler data */
struct SCIP_ConshdlrData
{
   SCIP_EVENTHDLR*       eventhdlr;          /**< event handler for bound change events */
   SCIP_CONSHDLR*        conshdlrlinear;     /**< pointer to linear constraint handler or NULL if not included */
#ifdef VARUSES
   SCIP_INTARRAY*        varuses;            /**< number of times a var is used in the active setppc constraints */
#endif
   SCIP_Longint          nsetpart;           /**< number of set partitioning constraints in transformed problem */
   int                   npseudobranches;    /**< number of children created in pseudo branching (0 to disable branching) */
   int                   noldfixedvars;      /**< number of fixed variables after last clique lifting run */
   int                   noldimpls;          /**< number of implication before last clique lifting run */
   int                   noldcliques;        /**< number of cliques before last clique lifting run */
   int                   noldupgrs;          /**< number of setppc constraints since the last clique lifting run */
   int                   nclqpresolve;       /**< number of setppc clique lifting runs */
   SCIP_Bool             updatedsetppctype;  /**< remember whether we upgraded a constraint type */
   SCIP_Bool             cliquelifting;      /**< should we perform the clique lifting procedure */
   SCIP_Bool             enablecliquelifting;/**< check whether we have enough changes to run the lifting procedure again */
   SCIP_Bool             cliqueshrinking;    /**< should we try to shrink the number of variables in a clique
                                              *   constraints, by replacing more than one variable by only one
                                              */
   SCIP_Bool             addvariablesascliques;/**< should we try to generate extra clique constraint out of all binary
                                                *   variables to hopefully fasten the detection of redundant clique
                                                *   constraints */
   SCIP_RANDNUMGEN*      randnumgen;         /**< random number generator */
   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             dualpresolving;     /**< should dual presolving steps be performed? */
};

/** constraint data for set partitioning / packing / covering constraints */
struct SCIP_ConsData
{
   uint64_t              signature;          /**< bit signature of vars array */
   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 the constraint */
   int                   varssize;           /**< size of vars array */
   int                   nvars;              /**< number of variables in the constraint */
   int                   nfixedzeros;        /**< current number of variables fixed to zero in the constraint */
   int                   nfixedones;         /**< current number of variables fixed to one in the constraint */
   unsigned int          setppctype:2;       /**< type of constraint: set partitioning, packing or covering */
   unsigned int          sorted:1;           /**< are the constraint's variables sorted? */
   unsigned int          cliqueadded:1;      /**< was the set partitioning / packing constraint already added as clique? */
   unsigned int          validsignature:1;   /**< is the bit signature valid? */
   unsigned int          changed:1;          /**< was constraint changed since last redundancy round in preprocessing? */
   unsigned int          varsdeleted:1;      /**< were variables deleted after last cleanup? */
   unsigned int          merged:1;           /**< are the constraint's equal/negated variables already merged? */
   unsigned int          presolpropagated:1; /**< was the constraint already propagated in presolving w.r.t. the current domains? */
   unsigned int          existmultaggr:1;    /**< does this constraint contain aggregations */
   unsigned int          catchevents:1;      /**< are events installed for this constraint? */
};




/*
 * Local methods
 */

/** compares two active constraints of type set partitioning or set packing such that a "-1" is return if
 *    1. the first constraint is a set partitioning constraint and the second is a set packing or
 *    2. both constraints are set partitioning constraints and the second has more! variables than the first or
 *    3. both constraints are set packing constraints and the second has less! variables than the first
 *  a "0" is return if
 *    1. both constraint are of the same type and have the amount of variables or
 *  and a "1" is returned otherwise
 */
static
int setppcCompare(
   SCIP_CONS*const       cons1,              /**< first problem variable */
   SCIP_CONS*const       cons2               /**< second problem variable */
   )
{
   SCIP_CONSDATA* consdata1;
   SCIP_CONSDATA* consdata2;

   assert(cons1 != NULL);
   assert(cons2 != NULL);
   assert(SCIPconsIsActive(cons1));
   assert(SCIPconsIsActive(cons2));

   /* the partitioning type should be the smallest value and the packing the second smallest */
   assert(SCIP_SETPPCTYPE_PARTITIONING < SCIP_SETPPCTYPE_PACKING); /*lint !e506*/

   consdata1 = SCIPconsGetData(cons1);
   assert(consdata1 != NULL);
   assert(consdata1->setppctype != SCIP_SETPPCTYPE_COVERING); /*lint !e641*/
   consdata2 = SCIPconsGetData(cons2);
   assert(consdata2 != NULL);
   assert(consdata2->setppctype != SCIP_SETPPCTYPE_COVERING); /*lint !e641*/

   if( consdata1->setppctype < consdata2->setppctype ||
      (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars < consdata2->nvars) || /*lint !e641*/
      (consdata2->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars > consdata2->nvars) ) /*lint !e641*/
      return -1;
   else if( (consdata1->setppctype == consdata2->setppctype && consdata1->nvars == consdata2->nvars) ) /*lint !e641*/
      return 0;
   else
   {
      assert(consdata1->setppctype > consdata2->setppctype || (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->setppctype == consdata2->setppctype && consdata1->nvars > consdata2->nvars) || (consdata1->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->setppctype == consdata2->setppctype && consdata1->nvars < consdata2->nvars)); /*lint !e641*/
      return +1;
   }
}

/** sort constraints first after type (partitioning before packing before covering) and second after number of
 *  variables such that the partitioning constraints have increasing number of variables and the packing constraints
 *  have decreasing number of variables */
static
SCIP_DECL_SORTPTRCOMP(setppcConssSort)
{
   return setppcCompare((SCIP_CONS*)elem1, (SCIP_CONS*)elem2);
}

/** compares two setppc constraints such that a "-1" is return if the first constraint is active and
 *    1. the second constraint is deleted
 *    2. the first constraint is a set partitioning constraint and the second is a set packing or
 *    3. both constraints are set partitioning constraints and the second has more! variables than the first or
 *    4. both constraints are set packing constraints and the second has less! variables than the first
 *  a "0" is return if
 *    1. both constraint are set-covering constraints
 *    2. both constraint are of the same type and have the amount of variables or
 *  and a "1" is returned otherwise
 */
static
int setppcCompare2(
   SCIP_CONS*const       cons1,              /**< first problem variable */
   SCIP_CONS*const       cons2               /**< second problem variable */
   )
{
   SCIP_CONSDATA* consdata1;
   SCIP_CONSDATA* consdata2;

   assert(cons1 != NULL);
   assert(cons2 != NULL);

   if( SCIPconsIsDeleted(cons1) )
   {
      if( SCIPconsIsDeleted(cons2) )
         return 0;
      else
         return +1;
   }
   else if( SCIPconsIsDeleted(cons2) )
      return -1;

   consdata1 = SCIPconsGetData(cons1);
   assert(consdata1 != NULL);
   consdata2 = SCIPconsGetData(cons2);
   assert(consdata2 != NULL);

   /* the partitioning type should be the smallest value and the packing the second smallest */
   assert(SCIP_SETPPCTYPE_PARTITIONING < SCIP_SETPPCTYPE_PACKING && SCIP_SETPPCTYPE_PACKING < SCIP_SETPPCTYPE_COVERING); /*lint !e506*//*lint !e1564*/

   if( consdata1->setppctype < consdata2->setppctype ||
      ((SCIP_SETPPCTYPE)consdata1->setppctype != SCIP_SETPPCTYPE_COVERING &&
         (((SCIP_SETPPCTYPE)consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars < consdata2->nvars) ||
            ((SCIP_SETPPCTYPE)consdata2->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars > consdata2->nvars))) )
      return -1;
   else if( ((SCIP_SETPPCTYPE)consdata2->setppctype == SCIP_SETPPCTYPE_COVERING || (consdata1->setppctype == consdata2->setppctype && consdata1->nvars == consdata2->nvars)) )
      return 0;
   else
   {
      assert(consdata1->setppctype > consdata2->setppctype || ((consdata1->setppctype == consdata2->setppctype) &&
            ((consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars > consdata2->nvars)
               || (consdata1->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars < consdata2->nvars)))); /*lint !e641*/
      return +1;
   }
}

/** sort constraints first after type (partitioning before packing before covering) and second after number of
 *  variables such that the partitioning constraints have increasing number of variables and the packing constraints
 *  have decreasing number of variables */
static
SCIP_DECL_SORTPTRCOMP(setppcConssSort2)
{
   return setppcCompare2((SCIP_CONS*)elem1, (SCIP_CONS*)elem2);
}


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

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

   switch( consdata->setppctype )
   {
   case SCIP_SETPPCTYPE_PARTITIONING:
      SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, TRUE) );
      break;
   case SCIP_SETPPCTYPE_PACKING:
      SCIP_CALL( SCIPlockVarCons(scip, var, cons, FALSE, TRUE) );
      break;
   case SCIP_SETPPCTYPE_COVERING:
      SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, FALSE) );
      break;
   default:
      SCIPerrorMessage("unknown setppc type\n");
      return SCIP_INVALIDDATA;
   }

   return SCIP_OKAY;
}

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

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

   switch( consdata->setppctype )
   {
   case SCIP_SETPPCTYPE_PARTITIONING:
      SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, TRUE) );
      break;
   case SCIP_SETPPCTYPE_PACKING:
      SCIP_CALL( SCIPunlockVarCons(scip, var, cons, FALSE, TRUE) );
      break;
   case SCIP_SETPPCTYPE_COVERING:
      SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, FALSE) );
      break;
   default:
      SCIPerrorMessage("unknown setppc type\n");
      return SCIP_INVALIDDATA;
   }

   return SCIP_OKAY;
}

/** creates constraint handler data for set partitioning / packing / covering 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) );
#ifdef VARUSES
   SCIP_CALL( SCIPcreateIntarray(scip, &(*conshdlrdata)->varuses) );
#endif
   (*conshdlrdata)->npseudobranches = DEFAULT_NPSEUDOBRANCHES;

   /* set event handler for bound change events */
   (*conshdlrdata)->eventhdlr = eventhdlr;
   (*conshdlrdata)->nsetpart = 0;

   /* create a random number generator */
   SCIP_CALL( SCIPcreateRandom(scip, &(*conshdlrdata)->randnumgen,
         DEFAULT_RANDSEED, TRUE) );

   return SCIP_OKAY;
}

/** frees constraint handler data for set partitioning / packing / covering constraint handler */
static
SCIP_RETCODE conshdlrdataFree(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA**   conshdlrdata        /**< pointer to the constraint handler data */
   )
{
   assert(conshdlrdata != NULL);
   assert(*conshdlrdata != NULL);

#ifdef VARUSES
   SCIP_CALL( SCIPfreeIntarray(scip, &(*conshdlrdata)->varuses) );
#endif

   /* free random number generator */
   SCIPfreeRandom(scip, &(*conshdlrdata)->randnumgen);

   SCIPfreeBlockMemory(scip, conshdlrdata);

   return SCIP_OKAY;
}

#ifdef VARUSES
/** adds the given value to the usage counter of the given variable */
static
SCIP_RETCODE conshdlrdataAddVaruses(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   SCIP_VAR*             var,                /**< variable to increase usage counter for */
   int                   addval              /**< value to add to the usage counter */
   )
{
   SCIP_INTARRAY* varuses;

   assert(conshdlrdata != NULL);
   assert(var != NULL);

   varuses = conshdlrdata->varuses;
   assert(varuses != NULL);

   /* if the variable is the negation of a problem variable, count the varuses in the problem variable */
   if( SCIPvarIsNegated(var) )
   {
      SCIP_VAR* negvar;
      int varindex;

      /* move the varuses value of the negated variable to the active problem variable */
      varindex = SCIPvarGetIndex(var);
      addval += SCIPgetIntarrayVal(scip, varuses, varindex);
      SCIP_CALL( SCIPsetIntarrayVal(scip, varuses, varindex, 0) );
      SCIP_CALL( SCIPgetNegatedVar(scip, var, &negvar) );
      var = negvar;
   }

   /* increase varuses counter */
   SCIP_CALL( SCIPincIntarrayVal(scip, varuses, SCIPvarGetIndex(var), addval) );

   SCIPdebugMsg(scip, "added %d to varuses of <%s>: %d\n",
      addval, SCIPvarGetName(var), SCIPgetIntarrayVal(scip, varuses, SCIPvarGetIndex(var)));

   return SCIP_OKAY;
}

/** increases the usage counter of the given variable */
static
SCIP_RETCODE conshdlrdataIncVaruses(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   SCIP_VAR*             var                 /**< variable to increase usage counter for */
   )
{
   assert(conshdlrdata != NULL);

   SCIPdebugMsg(scip, "increasing varuses of <%s>: %d\n",
      SCIPvarGetName(var), SCIPgetIntarrayVal(scip, conshdlrdata->varuses, SCIPvarGetIndex(var)));

   SCIP_CALL( conshdlrdataAddVaruses(scip, conshdlrdata, var, +1) );

   return SCIP_OKAY;
}

/** decreases the usage counter of the given variable */
static
SCIP_RETCODE conshdlrdataDecVaruses(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   SCIP_VAR*             var                 /**< variable to increase usage counter for */
   )
{
   assert(conshdlrdata != NULL);

   SCIPdebugMsg(scip, "decreasing varuses of <%s>: %d\n",
      SCIPvarGetName(var), SCIPgetIntarrayVal(scip, conshdlrdata->varuses, SCIPvarGetIndex(var)));

   SCIP_CALL( conshdlrdataAddVaruses(scip, conshdlrdata, var, -1) );

   return SCIP_OKAY;
}

/** increases the usage counter of all variable in the constraint */
static
SCIP_RETCODE consdataIncVaruses(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   SCIP_CONSDATA*        consdata            /**< setppc constraint data */
   )
{
   int v;

   assert(consdata != NULL);

   for( v = 0; v < consdata->nvars; ++v )
   {
      SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, consdata->vars[v]) );
   }

   return SCIP_OKAY;
}

/** decreases the usage counter of all variable in the constraint */
static
SCIP_RETCODE consdataDecVaruses(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   SCIP_CONSDATA*        consdata            /**< setppc constraint data */
   )
{
   int v;

   assert(consdata != NULL);

   for( v = 0; v < consdata->nvars; ++v )
   {
      SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, consdata->vars[v]) );
   }

   return SCIP_OKAY;
}
#endif

/** ensures, that the vars array can store at least num entries */
static
SCIP_RETCODE consdataEnsureVarsSize(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< setppc constraint data */
   int                   num                 /**< minimum number of entries to store */
   )
{
   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) );
      consdata->varssize = newsize;
   }
   assert(num <= consdata->varssize);

   return SCIP_OKAY;
}

/** creates a set partitioning / packing / covering constraint data object */
static
SCIP_RETCODE consdataCreate(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA**       consdata,           /**< pointer to store the set partitioning / packing / covering constraint */
   int                   nvars,              /**< number of variables in the constraint */
   SCIP_VAR**            vars,               /**< variables of the constraint */
   SCIP_SETPPCTYPE       setppctype          /**< type of constraint: set partitioning, packing, or covering constraint */
   )
{
   assert(consdata != NULL);
   assert(nvars == 0 || vars != NULL);

   SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );

   (*consdata)->signature = 0;
   (*consdata)->row = NULL;
   (*consdata)->nlrow = NULL;
   (*consdata)->existmultaggr = FALSE;
   (*consdata)->catchevents = FALSE;
   (*consdata)->nfixedzeros = 0;
   (*consdata)->nfixedones = 0;

   if( nvars > 0 )
   {
      int v;

      /* @todo the setppc constraint handler does not remove fixed variables from its var array; removing those
       * variables is only possible if we consider the values of nfixedones and nfixedzeros in all propagation methods
       */
#ifdef SCIP_DISABLED_CODE

      if( SCIPisConsCompressionEnabled(scip) )
      {
         SCIP_VAR** varsbuffer;
         int k;

         /* allocate temporary buffer storage for active variables */
         SCIP_CALL( SCIPallocBufferArray(scip, &varsbuffer, nvars) );

         k = 0;
         /* collect fixed variables to compress the required memory */
         for( v = 0; v < nvars; ++v )
         {
            assert(SCIPvarIsBinary(vars[v]));

            /* already fixed variables account as fixed ones or zero, only unfixed are appended */
            if( SCIPvarGetLbGlobal(vars[v]) > 0.5 )
               (*consdata)->nfixedones++;
            else if( SCIPvarGetUbGlobal(vars[v]) < 0.5 )
               (*consdata)->nfixedzeros++;
            else
               varsbuffer[k++] = vars[v];
         }

         (*consdata)->varssize = k;
         (*consdata)->nvars = k;
         /* copy unfixed variables into constraint data */
         if( k > 0 )
         {
            SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, varsbuffer, k) );
         }

         /* free temporary storage */
         SCIPfreeBufferArray(scip, &varsbuffer);
      }
      else
#endif
      {
         /* for uncompressed copies, simply duplicate the whole array */
         SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
         (*consdata)->varssize = nvars;
         (*consdata)->nvars = nvars;
      }

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

         /* check for multi-aggregations and capture variables */
         for( v = 0; v < (*consdata)->nvars; v++ )
         {
            SCIP_VAR* var = SCIPvarGetProbvar((*consdata)->vars[v]);
            assert(var != NULL);
            (*consdata)->existmultaggr = (*consdata)->existmultaggr || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
            SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
         }
      }
      else
      {
         /* capture variables */
         for( v = 0; v < (*consdata)->nvars; v++ )
         {
            assert((*consdata)->vars[v] != NULL);
            SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
         }
      }
   }
   else
   {
      (*consdata)->vars = NULL;
      (*consdata)->varssize = 0;
      (*consdata)->nvars = 0;
   }
   (*consdata)->setppctype = setppctype; /*lint !e641*/
   (*consdata)->sorted = (nvars <= 1);
   (*consdata)->cliqueadded = FALSE;
   (*consdata)->validsignature = FALSE;
   (*consdata)->changed = TRUE;
   (*consdata)->varsdeleted = FALSE;
   (*consdata)->merged = FALSE;
   (*consdata)->presolpropagated = FALSE;

   return SCIP_OKAY;
}

/** creates a transformed set partitioning / packing / covering constraint data object */
static
SCIP_RETCODE consdataCreateTransformed(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA**       consdata,           /**< pointer to store the set partitioning / packing / covering constraint */
   int                   nvars,              /**< number of variables in the constraint */
   SCIP_VAR**            vars,               /**< variables of the constraint */
   SCIP_SETPPCTYPE       setppctype          /**< type of constraint: set partitioning, packing, or covering constraint */
   )
{
   assert(consdata != NULL);
   assert(nvars == 0 || vars != NULL);

   /* create constraint data */
   SCIP_CALL( consdataCreate(scip, consdata, nvars, vars, setppctype) );

   /* transform the variables */
   SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );

   return SCIP_OKAY;
}

/** frees a set partitioning / packing / covering constraint data */
static
SCIP_RETCODE consdataFree(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA**       consdata            /**< pointer to store the set partitioning / packing / covering constraint */
   )
{
   int v;

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

   /* 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);
      SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->vars[v])) );
   }

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

   return SCIP_OKAY;
}

/** prints set partitioning / packing / covering constraint to file stream */
static
SCIP_RETCODE consdataPrint(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< set partitioning / packing / covering constraint data */
   FILE*                 file                /**< output file (or NULL for standard output) */
   )
{
   assert(consdata != NULL);

   /* print coefficients */
   if( consdata->nvars == 0 )
      SCIPinfoMessage(scip, file, "0 ");

   /* write linear sum */
   SCIP_CALL( SCIPwriteVarsLinearsum(scip, file, consdata->vars, NULL, consdata->nvars, TRUE) );

   /* print right hand side */
   switch( consdata->setppctype )
   {
   case SCIP_SETPPCTYPE_PARTITIONING:
      SCIPinfoMessage(scip, file, " == 1");
      break;
   case SCIP_SETPPCTYPE_PACKING:
      SCIPinfoMessage(scip, file, " <= 1");
      break;
   case SCIP_SETPPCTYPE_COVERING:
      SCIPinfoMessage(scip, file, " >= 1");
      break;
   default:
      SCIPerrorMessage("unknown setppc type\n");
      return SCIP_ERROR;
   }

   return SCIP_OKAY;
}

/** returns the bit signature of the given constraint data */
static
uint64_t consdataGetSignature(
   SCIP_CONSDATA*        consdata            /**< set partitioning / packing / covering constraint data */
   )
{
   assert(consdata != NULL);

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

      consdata->signature = 0;
      for( i = 0; i < consdata->nvars; ++i )
         consdata->signature |= SCIPhashSignature64(SCIPvarGetIndex(consdata->vars[i]));
      consdata->validsignature = TRUE;
   }

   return consdata->signature;
}

/** sorts setppc constraint's variables by non-decreasing variable index */
static
void consdataSort(
   SCIP_CONSDATA*        consdata            /**< linear constraint data */
   )
{
   assert(consdata != NULL);

   if( !consdata->sorted )
   {
      if( consdata->nvars <= 1 )
         consdata->sorted = TRUE;
      else
      {
         SCIPsortPtr((void**)consdata->vars, SCIPvarComp, consdata->nvars);
         consdata->sorted = TRUE;
      }
   }
   assert(consdata->sorted);
#ifdef SCIP_DEBUG
   /* check sorting */
   {
      int v;

      for( v = 0; v < consdata->nvars; ++v )
      {
         assert(v == consdata->nvars-1 || SCIPvarCompare(consdata->vars[v], consdata->vars[v+1]) <= 0);
      }
   }
#endif
}

/** changes the type of a setppc constraint */
static
SCIP_RETCODE setSetppcType(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< setppc constraint */
   SCIP_SETPPCTYPE       setppctype          /**< new type of constraint */
   )
{
   SCIP_CONSHDLR* conshdlr;
   SCIP_CONSHDLRDATA* conshdlrdata;
   SCIP_CONSDATA* consdata;
   SCIP_Bool locked;
   int i;

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

   if( (SCIP_SETPPCTYPE)consdata->setppctype == setppctype )
      return SCIP_OKAY;

   SCIPdebugMsg(scip, " -> converting <%s> into setppc type %d\n", SCIPconsGetName(cons), setppctype);

   /* remove rounding locks */
   locked = FALSE;
   for( i = 0; i < NLOCKTYPES && !locked; i++ )
      locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);

   if( locked )
   {
      for( i = 0; i < consdata->nvars; ++i )
      {
         SCIP_CALL( unlockRounding(scip, cons, consdata->vars[i]) );
      }
   }

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

   if( SCIPisTransformed(scip) )
   {
      if( setppctype == SCIP_SETPPCTYPE_PARTITIONING )
      {
         ++(conshdlrdata->nsetpart);
         assert(conshdlrdata->nsetpart >= 0);
      }
      else if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING )
      {
         --(conshdlrdata->nsetpart);
         assert(conshdlrdata->nsetpart >= 0);
      }
   }

   /* change the constraint type */
   consdata->setppctype = setppctype; /*lint !e641*/

   /* reinstall rounding locks again */
   if( locked )
   {
      for( i = 0; i < consdata->nvars; ++i )
      {
         SCIP_CALL( lockRounding(scip, cons, consdata->vars[i]) );
      }
   }

   /* remember that we changed a constraint type for clique lifting procedure */
   if( setppctype != SCIP_SETPPCTYPE_COVERING )
      conshdlrdata->updatedsetppctype = TRUE;

   return SCIP_OKAY;
}

/** catches events for variable at given position */
static
SCIP_RETCODE catchEvent(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< set partitioning / packing / covering 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;
   SCIP_EVENTTYPE eventtype;
   SCIP_VAR* var;

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

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

   /* we are catching the following events:
    *
    * - SCIP_EVENTTYPE_BOUNDCHANGED: Is used to count the number of variable fixed locally to zero and one. That helps
    *                                to speed up the propagation
    *
    * - SCIP_EVENTTYPE_VARDELETED: Is caught to remove a deleted variable from the constraint
    *
    * - SCIP_EVENTTYPE_VARFIXED: Is used to get informed if a variable of the constraint was aggregated which means was
    *                            detected to be equal or a negated variable of on other variable. in case of a negation
    *                            this could lead to a redundant constraint if the (other) active variable is also part
    *                            of the constraint.
    */
   eventtype =  SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_VARDELETED | SCIP_EVENTTYPE_VARFIXED;

   /* catch bound change events on variable */
   SCIP_CALL( SCIPcatchVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*)cons, NULL) );

   /* update the fixed variables counters for this variable */
   if( SCIPisEQ(scip, SCIPvarGetUbLocal(var), 0.0) )
   {
      consdata->nfixedzeros++;

      /* during presolving, we may fix the last unfixed variable or do an aggregation if there are two unfixed variables */
      if( SCIPconsIsActive(cons) && ((SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE) && (consdata->nfixedzeros >= consdata->nvars - 2)) )
      {
         consdata->presolpropagated = FALSE;

         /* during solving, we only propagate again if there is only one unfixed variable left */
         if( consdata->nfixedzeros >= consdata->nvars - 1 )
         {
            SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
         }
      }
   }
   else if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), 1.0) )
   {
      consdata->nfixedones++;

      if( SCIPconsIsActive(cons) )
      {
         consdata->presolpropagated = FALSE;
         SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
      }
   }

   return SCIP_OKAY;
}

/** drops events for variable at given position */
static
SCIP_RETCODE dropEvent(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< set partitioning / packing / covering 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;
   SCIP_EVENTTYPE eventtype;
   SCIP_VAR* var;

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

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

   eventtype =  SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_VARDELETED | SCIP_EVENTTYPE_VARFIXED;

   /* drop events on variable */
   SCIP_CALL( SCIPdropVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*)cons, -1) );

   /* update the fixed variables counters for this variable */
   if( SCIPisEQ(scip, SCIPvarGetUbLocal(var), 0.0) )
      consdata->nfixedzeros--;
   else if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), 1.0) )
      consdata->nfixedones--;

   return SCIP_OKAY;
}

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

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

   if( consdata->catchevents == TRUE )
      return SCIP_OKAY;

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

   consdata->catchevents = TRUE;

   return SCIP_OKAY;
}

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

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

   if( consdata->catchevents == FALSE )
      return SCIP_OKAY;

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

   consdata->catchevents = FALSE;

   return SCIP_OKAY;
}

/** adds coefficient in setppc constraint */
static
SCIP_RETCODE addCoef(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< setppc constraint */
   SCIP_VAR*             var                 /**< variable to add to the constraint */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_Bool transformed;

   assert(var != NULL);

   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->nvars++;
   if( consdata->validsignature )
      consdata->signature |= SCIPhashSignature64(SCIPvarGetIndex(var));
   consdata->sorted = (consdata->nvars == 1);
   consdata->changed = TRUE;

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

   /* if we are in transformed problem, catch the variable's events */
   if( transformed )
   {
      SCIP_CONSHDLR* conshdlr;
      SCIP_CONSHDLRDATA* conshdlrdata;

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

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

      if( !consdata->existmultaggr && SCIPvarGetStatus(SCIPvarGetProbvar(var)) == SCIP_VARSTATUS_MULTAGGR )
         consdata->existmultaggr = TRUE;

#ifdef VARUSES
      /* if the constraint is currently active, increase the variable usage counter */
      if( SCIPconsIsActive(cons) )
      {
         SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, var) );
      }
#endif
   }

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

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

   consdata->merged = FALSE;
   consdata->cliqueadded = FALSE;

   return SCIP_OKAY;
}

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

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

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

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

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

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

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

      /* drop bound change events of variable */
      if( consdata->catchevents )
      {
         SCIP_CALL( dropEvent(scip, cons, conshdlrdata->eventhdlr, pos) );
      }

      /* the last variable of the constraint was deleted; mark it for propagation (so that it can be deleted) */
      if( consdata->nvars == 1 )
      {
         consdata->presolpropagated = FALSE;
      }
   }

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

   /* move the last variable to the free slot */
   if( pos != consdata->nvars - 1 )
   {
      consdata->vars[pos] = consdata->vars[consdata->nvars-1];
      consdata->sorted = FALSE;
   }
   consdata->nvars--;
   consdata->validsignature = FALSE;
   consdata->changed = TRUE;

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

   return SCIP_OKAY;
}

/** preform dual presolving
 *
 *  In case a part (more than one variable) in the setppc constraint is independent of everything else (is locked only by
 *  this constraint), we can perform dual reductions:
 *
 *  (1) set covering
 *
 *      - fix all independent variables with negative object coefficient to one
 *      - fix all remaining independent variables to zero
 *
 *      (i) all variables are independent and the constraint is not modifiable
 *
 *          - fix the variable with the smallest object coefficient to one
 *
 *     (ii) a variable x has exactly 0 uplocks and arbitrary downlocks and a variable y has exactly 1 downlock and
 *          arbitrary uplocks and obj(x) <= obj(y) and obj(y) >= 0
 *
 *          - fix y to 0, because it is dominated by x
 *
 *  (2) set partitioning
 *
 *      (i) all variables are independent and the constraint is not modifiable
 *
 *          - fix the variable with the smallest object coefficient to one
 *          - fix all remaining independent variables to zero
 *
 *     (ii) a variable x has exactly 1 uplock and arbitrary downlocks and a variable y has exactly 1 downlock and
 *          arbitrary uplocks and obj(x) <= obj(y)
 *
 *          - fix y to 0, because it is dominated by x
 *
 *  (3) set packing
 *
 *      (i) all variables are independent and the constraint is not modifiable
 *
 *          - fix the variable with the smallest object coefficient to one if the object coefficient is negative or zero
 *          - fix all remaining independent variables to zero
 *
 *     (ii) a variable x has exactly 1 uplock and arbitrary downlocks and a variable y has exactly 0 downlocks and
 *          arbitrary uplocks and obj(x) <= obj(y)
 *
 *          - fix y to 0, because it is dominated by x
 *
 *
 *  Note: the following dual reduction for set covering and set packing constraints is already performed by the presolver
 *       "dualfix"
 *       (1) in case of a set covering constraint the following dual reduction can be performed:
 *           - if a variable in a set covering constraint is only locked by that constraint and has negative or zero
 *             objective coefficient than it can be fixed to one
 *       (2) in case of a set packing constraint the following dual reduction can be performed:
 *           - if a variable in a set packing constraint is only locked by that constraint and has positive or zero
 *             objective coefficient than it can be fixed to zero
 *
 *  Note: all dual reduction (ii) could also be performed by the "domcol" presolver, but because the pairwise comparison of
 *       columns is only done heuristically (and here it should be even cheaper) we perform them here (too).
 *
 *  Moreover, if there exists a variable that is only locked by a covering or packing constraint with two variables, one
 *  can aggregate variables.
 */
static
SCIP_RETCODE dualPresolving(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< setppc constraint */
   int*                  nfixedvars,         /**< pointer to count number of fixings */
   int*                  ndelconss,          /**< pointer to count number of deleted constraints  */
   int*                  naggrvars,          /**< pointer to count number of variables aggregated */
   SCIP_RESULT*          result              /**< pointer to store the result SCIP_SUCCESS, if presolving was performed */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_SETPPCTYPE setppctype;
   SCIP_VAR** vars;
   SCIP_VAR* activevar;
   SCIP_VAR* var;
   SCIP_Real bestobjval;
   SCIP_Real objval;
   SCIP_Real objsign;
   SCIP_Real fixval;
   SCIP_Bool infeasible;
   SCIP_Bool fixed;
   SCIP_Bool negated;
   int noldfixed;
   int nposfixings;
   int nlockdowns;
   int nlockups;
   int nvars;
   int indepidx = -1;
   int idx;
   int v;

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

   /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
    * use the locks to decide for a dual reduction using this constraint; for example after a restart the cuts which are
    * added to the problems have the check flag set to FALSE
    */
   if( !SCIPconsIsChecked(cons) )
      return SCIP_OKAY;

   assert(SCIPconsIsActive(cons));

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

   /* modifiable non-covering constraints cannot be deleted if one variable is fixed to one, because the propagation for
    * newly inserted variables must be considered later
    */
   if( consdata->nfixedones == 1 && SCIPconsIsModifiable(cons) )
      return SCIP_OKAY;

   /* all fixed variables should be removed at that point */
   assert(consdata->nfixedones == 0);
   assert(consdata->nfixedzeros == 0);

   nvars = consdata->nvars;

   /* we don't want to consider small constraints (note that the constraints can be modifiable, so we can't delete this
    * constraint)
    */
   if( nvars < 2 )
      return SCIP_OKAY;

   setppctype = (SCIP_SETPPCTYPE)consdata->setppctype;
   vars = consdata->vars;
   idx = -1;
   bestobjval = SCIP_INVALID;

   /* collect the rounding locks depending on the setppc type */
   switch( setppctype )
   {
   case SCIP_SETPPCTYPE_PARTITIONING:
      nlockdowns = 1;
      nlockups = 1;
      objsign = 0.0;
      break;
   case SCIP_SETPPCTYPE_PACKING:
      nlockdowns = 0;
      nlockups = 1;
      objsign = -1.0;
      break;
   case SCIP_SETPPCTYPE_COVERING:
      nlockdowns = 1;
      nlockups = 0;
      objsign = 1.0;
      break;
   default:
      SCIPerrorMessage("unknown setppc type\n");
      SCIPABORT();
      return SCIP_INVALIDDATA; /*lint !e527*/
   }

   nposfixings = 0;

   /* check if we can apply the dual reduction; therefore count the number of variables where the setppc has the only
    * locks on this constraint
    */
   for( v = 0; v < nvars; ++v )
   {
      var = vars[v];
      assert(var != NULL);

      /* the variable should not be (globally) fixed */
      assert(SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5);

      if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) >= nlockdowns
         && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == nlockups )
      {
         activevar = var;
         negated = FALSE;

         /* get the active variable */
         SCIP_CALL( SCIPvarGetProbvarBinary(&activevar, &negated) );
         assert(SCIPvarIsActive(activevar));

         if( negated )
            objval = -SCIPvarGetObj(activevar);
         else
            objval = SCIPvarGetObj(activevar);

         /* check if the current variable has a smaller objective coefficient */
         if( idx == -1 || objval < bestobjval )
         {
            idx = v;
            bestobjval = objval;
         }

         /* determine independent variable, i.e., only locked by the current constraint */
         if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == nlockdowns )
         {
            assert(SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == nlockups);

            /* store variables that have the right objective sign */
            if ( objval * objsign >= 0.0 )
               indepidx = v;
         }
      }

      /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
       * variables
       */
      if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == nlockdowns
         && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) >= nlockups )
         ++nposfixings;
   }

   if( idx == -1 || nposfixings == 0 )
      return SCIP_OKAY;

   SCIPdebugMsg(scip, "dual fixing constraint: \n");
   SCIPdebug( SCIP_CALL( SCIPprintCons(scip, cons, NULL) ) );
   SCIPdebug( SCIPinfoMessage(scip, NULL, "\n") );

   assert(idx >= 0 && idx < nvars);
   assert(bestobjval < SCIPinfinity(scip));

   noldfixed = *nfixedvars;

   /* In the special case of two variables, where one variable is independent and will be minimized for covering or
    * maximized for packing or does not appear in the objective, we can aggregate variables:
    *  - Covering: var1 + var2 >= 1 and the objective of var1 is non-negative.
    *  - Packing:  var1 + var2 <= 1 and the objective of var1 is non-positive.
    * In both cases, var1 + var2 = 1 holds in every optimal solution.
    */
   if( setppctype != SCIP_SETPPCTYPE_PARTITIONING && nvars == 2 && indepidx >= 0 )
   {
      SCIP_Bool redundant;
      SCIP_Bool aggregated;
      int idx2;

      idx2 = 1 - indepidx;
      assert( 0 <= idx2 && idx2 < 2 );

      SCIP_CALL( SCIPaggregateVars(scip, vars[indepidx], vars[idx2], 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) );
      assert(!infeasible);
      assert(redundant);
      assert(aggregated);
      ++(*naggrvars);

      /* remove constraint since it is redundant */
      SCIP_CALL( SCIPdelCons(scip, cons) );
      ++(*ndelconss);

      *result = SCIP_SUCCESS;

      return SCIP_OKAY;
   }

   /* in case of set packing and set partitioning we fix the dominated variables to zero */
   if( setppctype != SCIP_SETPPCTYPE_COVERING )
   {
      /* first part of all variables */
      for( v = nvars - 1; v >= 0; --v )
      {
         if( v == idx )
            continue;

         var = vars[v];
         assert(var != NULL);

         /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
          * variables
          */
         if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == nlockdowns
            && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) >= nlockups )
         {
            activevar = var;
            negated = FALSE;

            /* get the active variable */
            SCIP_CALL( SCIPvarGetProbvarBinary(&activevar, &negated) );
            assert(SCIPvarIsActive(activevar));

            if( negated )
               objval = -SCIPvarGetObj(activevar);
            else
               objval = SCIPvarGetObj(activevar);

            if( objval >= bestobjval )
            {
               SCIP_CALL( SCIPfixVar(scip, var, 0.0, &infeasible, &fixed) );
               assert(!infeasible);
               assert(fixed);

               SCIPdebugMsg(scip, " -> dual-fixed dominated variable <%s> == 0.0\n", SCIPvarGetName(var));
               ++(*nfixedvars);
            }
         }
      }
   }
   /* if we got a set covering constraint and not all variables are locked from this constraint it might not get
    * redundant (which is case if it is not possible to fix at least one variable to one), we fix all redundant
    * variables to their best bound
    */
   else
   {
      /* first part of all variables */
      for( v = nvars - 1; v >= 0; --v )
      {
         if( v == idx )
            continue;

         var = vars[v];
         assert(var != NULL);

         /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
          * variables
          */
         if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == nlockdowns
            && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) >= nlockups )
         {
            activevar = var;
            negated = FALSE;

            /* get the active variable */
            SCIP_CALL( SCIPvarGetProbvarBinary(&activevar, &negated) );
            assert(SCIPvarIsActive(activevar));
            assert(negated
               || (SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == SCIPvarGetNLocksDownType(activevar, SCIP_LOCKTYPE_MODEL)
                  && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == SCIPvarGetNLocksUpType(activevar, SCIP_LOCKTYPE_MODEL)));
            assert(!negated
               || (SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == SCIPvarGetNLocksUpType(activevar, SCIP_LOCKTYPE_MODEL)
                  && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == SCIPvarGetNLocksDownType(activevar, SCIP_LOCKTYPE_MODEL)));

            if( negated )
               objval = -SCIPvarGetObj(activevar);
            else
               objval = SCIPvarGetObj(activevar);

            if( objval > 0.0 )
               fixval = 0.0;
            else
               fixval = 1.0;

            /* if variables has a negative objective contribution, and is uplocked by another constraint we cannot fix
             * the variables to 1
             */
            if( (fixval == 1.0 && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) > nlockups) || objval < bestobjval )
               continue;

            SCIP_CALL( SCIPfixVar(scip, var, fixval, &infeasible, &fixed) );
            assert(!infeasible);
            assert(fixed);

            SCIPdebugMsg(scip, " -> dual-fixed dominated variable <%s> == %g\n", SCIPvarGetName(var), fixval);
            ++(*nfixedvars);
         }
      }
   }

   /* if all variables but the domination variable is fixed and the constraint is not modifiable or the constraint is a
    * covering constraint and the bestobjval is less than or equal to zero, we can fix the domination variable (with best
    * objective coefficient) and the constraint gets redundant
    */
   if( ((*nfixedvars - noldfixed == nvars - 1) && !SCIPconsIsModifiable(cons)) || (setppctype == SCIP_SETPPCTYPE_COVERING && bestobjval <= 0.0) )
   {
      /* in case of a set packing constraint with positive objective values, all variables can be fixed to zero; in all
       * other cases the variable with the smallest objective values is fixed to one
       */
      if( (setppctype == SCIP_SETPPCTYPE_PACKING && bestobjval > 0.0
         && SCIPvarGetNLocksDownType(vars[idx], SCIP_LOCKTYPE_MODEL) == 0)
         || setppctype != SCIP_SETPPCTYPE_PACKING || bestobjval <= 0.0 )
      {
         if( setppctype == SCIP_SETPPCTYPE_PACKING && bestobjval > 0.0 )
            fixval = 0.0;
         else
            fixval = 1.0;

         SCIP_CALL( SCIPfixVar(scip, vars[idx], fixval, &infeasible, &fixed) );
         assert(!infeasible);
         assert(fixed);

         SCIPdebugMsg(scip, " -> dual-fixed best variable <%s> == %g\n", SCIPvarGetName(vars[idx]), fixval);
         ++(*nfixedvars);
      }

      /* check that we really have a non-violated constraint in hand before deleting */
      assert((setppctype == SCIP_SETPPCTYPE_PACKING && consdata->nfixedones <= 1) ||
         (setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedones == 1) ||
         (setppctype == SCIP_SETPPCTYPE_COVERING && consdata->nfixedones >= 1));

      /* remove constraint since it is redundant */
      SCIP_CALL( SCIPdelCons(scip, cons) );
      ++(*ndelconss);
   }

   assert(*nfixedvars >= noldfixed);

   /* set result pointer to SCIP_SUCCESS, if variables could be fixed */
   if( *nfixedvars != noldfixed )
      *result = SCIP_SUCCESS;

   return SCIP_OKAY;
}

/** find pairs of negated variables in constraint:
 *  partitioning/packing: all other variables must be zero, constraint is redundant
 *  covering: constraint is redundant
 *
 *  find sets of equal variables in constraint:
 *  partitioning/packing: variable must be zero
 *  covering: multiple entries of variable can be replaced by single entry
 */
static
SCIP_RETCODE mergeMultiples(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< knapsack constraint */
   int*                  nfixedvars,         /**< pointer to store number of fixed variables */
   int*                  ndelconss,          /**< pointer to store number of deleted constraints */
   int*                  nchgcoefs,          /**< pointer to store number of changed coefficients */
   SCIP_Bool*            cutoff              /**< pointer to store whether a fixing leads to a cutoff */
   )
{
   SCIP_CONSDATA* consdata;
   int v;

   assert(scip != NULL);
   assert(cons != NULL);
   assert(nfixedvars != NULL);
   assert(ndelconss != NULL);
   assert(nchgcoefs != NULL);
   assert(cutoff != NULL);

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

   if( consdata->merged || SCIPconsIsDeleted(cons) )
      return SCIP_OKAY;

   if( consdata->nvars <= 1 )
   {
      consdata->merged = TRUE;
      return SCIP_OKAY;
   }

   assert(consdata->vars != NULL || consdata->nvars == 0);

   /* sorting array after indices of variables, that's only for faster merging */
   SCIPsortPtr((void**)consdata->vars, SCIPvarCompActiveAndNegated, consdata->nvars);
   /* setppc sorting now lost */
   consdata->sorted = FALSE;

   /* loop backwards through the items: deletion only affects rear items */
   for( v = consdata->nvars - 1; v > 0; --v )
   {
      SCIP_VAR* var1;
      SCIP_VAR* var2;
      SCIP_Bool negated1;
      SCIP_Bool negated2;

      negated1 = FALSE;
      negated2 = FALSE;

      var1 = consdata->vars[v];
      assert(SCIPvarIsBinary(var1));
      assert(SCIPvarIsActive(var1) || SCIPvarGetStatus(var1) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var1) == SCIP_VARSTATUS_FIXED);
      if( SCIPvarGetStatus(var1) == SCIP_VARSTATUS_NEGATED )
      {
         var1 = SCIPvarGetNegatedVar(var1);
         negated1 = TRUE;
      }
      assert(var1 != NULL);

      var2 = consdata->vars[v-1];
      assert(SCIPvarIsBinary(var2));
      assert(SCIPvarIsActive(var2) || SCIPvarGetStatus(var2) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var2) == SCIP_VARSTATUS_FIXED);
      if( SCIPvarGetStatus(var2) == SCIP_VARSTATUS_NEGATED )
      {
         var2 = SCIPvarGetNegatedVar(var2);
         negated2 = TRUE;
      }
      assert(var2 != NULL);

      if( var1 == var2 )
      {
         SCIP_Bool infeasible;
         SCIP_Bool fixed;

         /* one variables is active and the other is the same negated variable */
         if( negated1 != negated2  )
         {
            /* all other variable have to be zero if it's a partitioning or packing constraint */
            if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
            {
               int i;

               assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING
                  || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/

               for( i = consdata->nvars - 1; i >= 0; --i )
                  if( i != v && i != (v-1) )
                  {
                     SCIP_CALL( SCIPfixVar(scip, consdata->vars[i], 0.0, &infeasible, &fixed) );
                     if( infeasible )
                     {
                        SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == 0\n",
                           SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[i]));
                        *cutoff = TRUE;
                        return SCIP_OKAY;
                     }

                     if( fixed )
                        ++(*nfixedvars);
                  }
            }
            /* all setppc-type constraints are redundant */
            SCIP_CALL( SCIPdelCons(scip, cons) );
            ++(*ndelconss);
            return SCIP_OKAY;
         }
         /* both variables are either active or negated */
         else
         {
            /* this variable can be fixed to zero if it's a partitioning or packing constraint */
            if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
            {
               assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING
                  || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/

               SCIP_CALL( SCIPfixVar(scip, var1, negated1 ? 1.0 : 0.0, &infeasible, &fixed) );
               if( infeasible )
               {
                  SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == %g\n",
                     SCIPconsGetName(cons), SCIPvarGetName(var1), negated1 ? 1.0 : 0.0);
                  *cutoff = TRUE;
                  return SCIP_OKAY;
               }

               if( fixed )
                  ++(*nfixedvars);
            }
            /* multiple entries of variable can be replaced by single entry */
            else
            {
               SCIP_CALL( delCoefPos(scip, cons, v) ); /* only some changed behind position v-1, so it's okay */
               ++(*nchgcoefs);
            }
         }
         consdata->changed = TRUE;
      }
   }
   consdata->merged = TRUE;

   return SCIP_OKAY;
}

/** deletes all zero-fixed variables and replace aggregated variables */
static
SCIP_RETCODE applyFixings(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< set partitioning / packing / covering constraint */
   int*                  naddconss,          /**< pointer to count number of added constraints, or NULL indicating we
                                              *   can not resolve multi-aggregations
                                              */
   int*                  ndelconss,          /**< pointer to count number of deleted constraints, or NULL indicating we
                                              *   can not resolve multi-aggregations
                                              */
   int*                  nfixedvars,         /**< pointer to store number of fixed variables, or NULL indicating we can
                                              *   not resolve multi-aggregations
                                              */
   SCIP_Bool*            cutoff              /**< pointer to store whether a fixing leads to a cutoff, or NULL
                                              *   indicating we can not resolve multi-aggregations
                                              */
   )
{
   SCIP_CONSDATA* consdata;
   int v;

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

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

   /* all multi-aggregations should be resolved */
   consdata->existmultaggr = FALSE;

   v = 0;
   while( v < consdata->nvars )
   {
      SCIP_VAR* var;

      var = consdata->vars[v];
      assert(SCIPvarIsBinary(var));

      if( SCIPvarGetUbGlobal(var) < 0.5 )
      {
         assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), 0.0));
         SCIP_CALL( delCoefPos(scip, cons, v) );
      }
      else
      {
         SCIP_VAR* repvar;
         SCIP_Bool negated;

         /* get binary representative of variable */
         SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &repvar, &negated) );

         /* resolve multi-aggregation */
         if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR || (SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_NEGATED && SCIPvarGetStatus(SCIPvarGetNegatedVar(repvar)) == SCIP_VARSTATUS_MULTAGGR) )
         {
            SCIP_VAR** consvars;
            SCIP_Real* consvals;
            SCIP_Real constant = 0.0;
            SCIP_Bool easycase;
            int nconsvars;
            int requiredsize;
            int v2;

            nconsvars = 1;
            SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 1) );
            SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 1) );
            consvars[0] = repvar;
            consvals[0] = 1.0;

            /* get active variables for new constraint */
            SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, nconsvars, &constant, &requiredsize, TRUE) );
            /* if space was not enough we need to resize the buffers */
            if( requiredsize > nconsvars )
            {
               SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, requiredsize) );
               SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, requiredsize) );

               SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
               assert(requiredsize <= nconsvars);
            }

            easycase = FALSE;

            if( SCIPisZero(scip, constant) )
            {
               /* add active representation */
               for( v2 = nconsvars - 1; v2 >= 0; --v2 )
               {
                  if( !SCIPvarIsBinary(consvars[v2]) )
                     break;

                  if( !SCIPisEQ(scip, consvals[v2], 1.0) )
                     break;
               }

               if( v2 < 0 )
                  easycase = TRUE;
            }
            else if( SCIPisFeasEQ(scip, constant, 1.0) )
            {
               /* check for another multi-aggregation */
               for( v2 = consdata->nvars - 1; v2 > v; --v2 )
               {
                  if( SCIPvarGetStatus(SCIPvarGetProbvar(consdata->vars[v])) == SCIP_VARSTATUS_MULTAGGR )
                     break;
               }

               /* constraint is redundant */
               if( v2 == v && nconsvars == 0 )
               {
                  /* we can fix */
                  if( consdata->nvars > 1 && (SCIP_SETPPCTYPE)consdata->setppctype != SCIP_SETPPCTYPE_COVERING )
                  {
                     if( nfixedvars != NULL )
                     {
                        SCIP_Bool fixed;

                        assert(cutoff != NULL);

                        for( v2 = consdata->nvars - 1; v2 >= 0; --v2 )
                        {
                           if( consdata->vars[v2] != var )
                           {
                              SCIPdebugMsg(scip, "trying to fix <%s> to 0 due to at least one variable is already fixed to 1\n", SCIPvarGetName(consdata->vars[v2]));

                              /* fix all remaining variables to zero, constraint is already feasible or infeasible */
                              SCIP_CALL( SCIPfixVar(scip, consdata->vars[v2], 0.0, cutoff, &fixed) );
                              if( *cutoff )
                              {
                                 SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == 0\n",
                                    SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[v2]));

                                 SCIPfreeBufferArray(scip, &consvals);
                                 SCIPfreeBufferArray(scip, &consvars);

                                 goto TERMINATE;
                              }

                              if( fixed )
                                 ++(*nfixedvars);
                           }
                        }
                     }
                  }

                  if( ndelconss != NULL && (nfixedvars != NULL || consdata->nvars == 1 || (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING) )
                  {
                     /* delete old constraint */
                     SCIP_CALL( SCIPdelCons(scip, cons) );
                     ++(*ndelconss);
                  }
                  SCIPfreeBufferArray(scip, &consvals);
                  SCIPfreeBufferArray(scip, &consvars);

                  goto TERMINATE;
               }
            }

            /* we can easily add the coefficients and still have a setppc constraint */
            if( easycase )
            {
               /* delete old (multi-aggregated) variable */
               SCIP_CALL( delCoefPos(scip, cons, v) );

               /* add active representation */
               for( v2 = nconsvars - 1; v2 >= 0; --v2 )
               {
                  assert(SCIPvarIsBinary(consvars[v2]));
                  assert(SCIPvarIsActive(consvars[v2]) || (SCIPvarGetStatus(consvars[v2]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(consvars[v2]))));

                  SCIP_CALL( addCoef(scip, cons, consvars[v2]) );
               }
            }
            /* we need to degrade this setppc constraint to a linear constraint */
            else if( (ndelconss != NULL && naddconss != NULL) || SCIPconsIsAdded(cons) )
            {
               char name[SCIP_MAXSTRLEN];
               SCIP_CONS* newcons;
               SCIP_Real lhs;
               SCIP_Real rhs;
               int size;
               int k;

               /* it might happen that there are more than one multi-aggregated variable, so we need to get the whole
                * probvar sum over all variables
                */

               size = MAX(nconsvars, 1) + consdata->nvars - 1;

               /* memory needed is at least old number of variables - 1 + number of variables in first multi-aggregation */
               SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, size) );
               SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, size) );

               nconsvars = consdata->nvars;

               /* add constraint variables to new linear variables */
               for( k = consdata->nvars - 1; k >= 0; --k )
               {
                  consvars[k] = consdata->vars[k];
                  consvals[k] = 1.0;
               }

               constant = 0.0;

               /* get active variables for new constraint */
               SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, size, &constant, &requiredsize, TRUE) );

               /* if space was not enough (we found another multi-aggregation), we need to resize the buffers */
               if( requiredsize > nconsvars )
               {
                  SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, requiredsize) );
                  SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, requiredsize) );

                  SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
                  assert(requiredsize <= nconsvars);
               }

               /* compute sides */
               if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING )
               {
                  lhs = -SCIPinfinity(scip);
                  rhs = 1.0 - constant;
               }
               else if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING )
               {
                  lhs = 1.0 - constant;
                  rhs = 1.0 - constant;
               }
               else
               {
                  assert((SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING);
                  lhs = 1.0 - constant;
                  rhs = SCIPinfinity(scip);
               }

               /* create linear constraint */
               (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s", SCIPconsGetName(cons));
               SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, nconsvars, consvars, consvals, lhs, rhs,
                  SCIPconsIsInitial(cons),
                  SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons),
                  SCIPconsIsPropagated(cons),  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
                  SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
               SCIP_CALL( SCIPaddCons(scip, newcons) );

               SCIPdebugMsg(scip, "added linear constraint: ");
               SCIPdebugPrintCons(scip, newcons, NULL);
               SCIP_CALL( SCIPreleaseCons(scip, &newcons) );

               SCIPfreeBufferArray(scip, &consvals);
               SCIPfreeBufferArray(scip, &consvars);

               /* delete old constraint */
               SCIP_CALL( SCIPdelCons(scip, cons) );
               if( ndelconss != NULL && naddconss != NULL )
               {
                  ++(*ndelconss);
                  ++(*naddconss);
               }

               goto TERMINATE;
            }
            /* we need to degrade this setppc constraint to a linear constraint*/
            else
            {
               /* check, if the variable should be replaced with the representative */
               if( repvar != var )
               {
                  /* delete old (aggregated) variable */
                  SCIP_CALL( delCoefPos(scip, cons, v) );

                  /* add representative instead */
                  SCIP_CALL( addCoef(scip, cons, repvar) );
               }

               SCIPwarningMessage(scip, "setppc constraint <%s> has a multi-aggregated variable, which was not resolved and therefore could lead to aborts\n", SCIPconsGetName(cons));
               ++v;
            }

            SCIPfreeBufferArray(scip, &consvals);
            SCIPfreeBufferArray(scip, &consvars);
         }
         else
         {
            /* check, if the variable should be replaced with the representative */
            if( repvar != var )
            {
               /* delete old (aggregated) variable */
               SCIP_CALL( delCoefPos(scip, cons, v) );

               /* add representative instead */
               SCIP_CALL( addCoef(scip, cons, repvar) );
            }
            else
               ++v;
         }
      }
   }

 TERMINATE:
   /* all multi-aggregations should be resolved */
   consdata->existmultaggr = FALSE;

   return SCIP_OKAY;
}

/** analyzes conflicting assignment on given constraint where all of the variables where assigned to zero,
 *  and adds conflict constraint to problem
 */
static
SCIP_RETCODE analyzeConflictZero(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons                /**< set partitioning / packing / covering constraint that detected the conflict */
   )
{
   SCIP_CONSDATA* consdata;
   int v;

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

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING
      || consdata->setppctype == SCIP_SETPPCTYPE_COVERING); /*lint !e641*/

   /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
   SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );

   for( v = 0; v < consdata->nvars; ++v )
   {
      SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
   }

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

   return SCIP_OKAY;
}

/** analyzes conflicting assignment on given constraint where two of the variables where assigned to one,
 *  and adds conflict constraint to problem
 */
static
SCIP_RETCODE analyzeConflictOne(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons                /**< set partitioning / packing / covering constraint that detected the conflict */
   )
{
   SCIP_CONSDATA* consdata;
   int v;
   int n;

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

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING
      || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/

   /* initialize conflict analysis, and add the two variables assigned to one to conflict candidate queue */
   SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );

   n = 0;
   for( v = 0; v < consdata->nvars && n < 2; ++v )
   {
      if( SCIPvarGetLbLocal(consdata->vars[v]) > 0.5 )
      {
         SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
         n++;
      }
   }
   assert(n == 2);

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

   return SCIP_OKAY;
}

/** checks constraint for violation only looking at the fixed variables, applies further fixings if possible */
static
SCIP_RETCODE processFixings(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< set partitioning / packing / covering constraint to be processed */
   SCIP_Bool*            cutoff,             /**< pointer to store TRUE, if the node can be cut off */
   int*                  nfixedvars,         /**< pointer to count number of deleted variables */
   SCIP_Bool*            addcut,             /**< pointer to store whether this constraint must be added as a cut */
   SCIP_Bool*            mustcheck           /**< pointer to store whether this constraint must be checked for feasibility */
   )
{
   SCIP_CONSDATA* consdata;
#ifndef NDEBUG
   int oldnfixedvars;
#endif

   assert(cons != NULL);
   assert(SCIPconsGetHdlr(cons) != NULL);
   assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
   assert(cutoff != NULL);
   assert(nfixedvars != NULL);
   assert(addcut != NULL);
   assert(mustcheck != NULL);

#ifndef NDEBUG
   oldnfixedvars = *nfixedvars;
#endif

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(consdata->nvars == 0 || consdata->vars != NULL);
   assert(0 <= consdata->nfixedzeros && consdata->nfixedzeros <= consdata->nvars);
   assert(0 <= consdata->nfixedones && consdata->nfixedones <= consdata->nvars);

   *addcut = FALSE;
   *mustcheck = TRUE;

   /*SCIPdebugMsg(scip, "processing constraint <%s> with respect to fixed variables (%d fixed to 0.0, %d fixed to 1.0)\n",
     SCIPconsGetName(cons), consdata->nfixedzeros, consdata->nfixedones);*/

   if( consdata->nfixedones == 1 )
   {
      /* exactly one variable is fixed to 1:
       * - a set covering constraint is feasible anyway and can be disabled
       * - all other variables in a set partitioning or packing constraint must be zero
       */
      if( consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
      {
         SCIPdebugMsg(scip, " -> disabling set covering constraint <%s>\n", SCIPconsGetName(cons));
         SCIP_CALL( SCIPdelConsLocal(scip, cons) );
      }
      else
      {
         if( consdata->nfixedzeros < consdata->nvars - 1 )
         {
            SCIP_VAR** vars;
            SCIP_VAR* var;
#ifndef NDEBUG
            SCIP_Bool fixedonefound;
#endif
            SCIP_Bool infeasible;
            SCIP_Bool tightened;
            int nvars;
            int v;
            int oneidx = -1;

            SCIPdebugMsg(scip, " -> fixing all other variables to zero in set packing/partitioning constraint <%s>\n",
               SCIPconsGetName(cons));

            /* unfixed variables exist: fix them to zero;
             * this could result in additional variables fixed to one due to aggregations; in this case, the
             * constraint is infeasible in local bounds
             */
            vars = consdata->vars;
            nvars = consdata->nvars;
#ifndef NDEBUG
            fixedonefound = FALSE;
#endif
            for( v = 0; v < nvars && consdata->nfixedones == 1; ++v )
            {
               var = vars[v];
               assert(SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), 1.0));
               if( SCIPvarGetLbLocal(var) < 0.5 )
               {
                  SCIP_CALL( SCIPinferBinvarCons(scip, var, FALSE, cons, oneidx, &infeasible, &tightened) );
                  assert(!infeasible);

                  if( tightened )
                     ++(*nfixedvars);

                  SCIPdebugMsg(scip, "   -> fixed <%s> to zero (tightened=%u)\n", SCIPvarGetName(var), tightened);
               }
               else
               {
#ifndef NDEBUG
                  fixedonefound = TRUE;
#endif
                  oneidx = v;
               }
            }
            /* the fixed to one variable must have been found, and at least one variable must have been fixed */
            assert(consdata->nfixedones >= 2 || (fixedonefound && *nfixedvars > oldnfixedvars));

            SCIP_CALL( SCIPresetConsAge(scip, cons) );
         }

         /* now all other variables are fixed to zero:
          * the constraint is feasible, and if it's not modifiable, it is redundant
          */
         if( !SCIPconsIsModifiable(cons) && consdata->nfixedones == 1 )
         {
            SCIPdebugMsg(scip, " -> disabling set packing/partitioning constraint <%s>\n", SCIPconsGetName(cons));
            SCIP_CALL( SCIPdelConsLocal(scip, cons) );
         }
      }
      *mustcheck = FALSE;
   }

   if( consdata->nfixedones >= 2 )
   {
      /* at least two variables are fixed to 1:
       * - a set covering constraint is feasible anyway and can be disabled
       * - a set partitioning or packing constraint is infeasible
       */
      if( consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
      {
         SCIPdebugMsg(scip, " -> disabling set covering constraint <%s>\n", SCIPconsGetName(cons));
         SCIP_CALL( SCIPdelConsLocal(scip, cons) );
      }
      else
      {
         SCIPdebugMsg(scip, " -> conflict on set packing/partitioning constraint <%s>\n", SCIPconsGetName(cons));

         SCIP_CALL( SCIPresetConsAge(scip, cons) );

         /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
         SCIP_CALL( analyzeConflictOne(scip, cons) );

         *cutoff = TRUE;
      }
      *mustcheck = FALSE;
   }
   else if( consdata->nfixedzeros == consdata->nvars )
   {
      /* all variables are fixed to zero:
       * - a set packing constraint is feasible anyway, and if it's unmodifiable, it can be disabled
       * - a set partitioning or covering constraint is infeasible, and if it's unmodifiable, the node
       *   can be cut off -- otherwise, the constraint must be added as a cut and further pricing must
       *   be performed
       */
      assert(consdata->nfixedones == 0);

      if( consdata->setppctype == SCIP_SETPPCTYPE_PACKING ) /*lint !e641*/
      {
         if( !SCIPconsIsModifiable(cons) )
         {
            SCIPdebugMsg(scip, " -> disabling set packing constraint <%s>\n", SCIPconsGetName(cons));
            SCIP_CALL( SCIPdelConsLocal(scip, cons) );
         }
      }
      else
      {
         SCIPdebugMsg(scip, " -> set covering/partitioning constraint <%s> is infeasible\n", SCIPconsGetName(cons));

         SCIP_CALL( SCIPresetConsAge(scip, cons) );
         if( SCIPconsIsModifiable(cons) )
            *addcut = TRUE;
         else
         {
            /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
            SCIP_CALL( analyzeConflictZero(scip, cons) );

            *cutoff = TRUE;
         }
      }
      *mustcheck = FALSE;
   }
   else if( consdata->nfixedzeros == consdata->nvars - 1 && consdata->nfixedones == 0 )
   {
      /* all variables except one are fixed to zero:
       * - a set packing constraint is feasible anyway, and if it's unmodifiable, it can be disabled
       * - an unmodifiable set partitioning or covering constraint is feasible and can be disabled after the
       *   remaining variable is fixed to one
       * - a modifiable set partitioning or covering constraint must be checked manually
       */
      if( consdata->setppctype == SCIP_SETPPCTYPE_PACKING ) /*lint !e641*/
      {
         if( !SCIPconsIsModifiable(cons) )
         {
            SCIPdebugMsg(scip, " -> disabling set packing constraint <%s>\n", SCIPconsGetName(cons));
            SCIP_CALL( SCIPdelConsLocal(scip, cons) );
         }
         *mustcheck = FALSE;
      }
      else if( !SCIPconsIsModifiable(cons) )
      {
         SCIP_VAR** vars;
         SCIP_VAR* var;
         SCIP_Bool infeasible;
         SCIP_Bool tightened;
         int nvars;
         int v;

         /* search the single variable that can be fixed */
         vars = consdata->vars;
         nvars = consdata->nvars;
         for( v = 0; v < nvars; ++v )
         {
            var = vars[v];
            assert(SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)));
            assert(SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), 1.0));
            if( SCIPvarGetUbLocal(var) > 0.5 )
            {
               SCIPdebugMsg(scip, " -> fixing remaining variable <%s> to one in set covering/partitioning constraint <%s>\n",
                  SCIPvarGetName(var), SCIPconsGetName(cons));
               SCIP_CALL( SCIPinferBinvarCons(scip, var, TRUE, cons, 0, &infeasible, &tightened) );
               assert(!infeasible);
               assert(tightened);

               ++(*nfixedvars);
               break;
            }
         }
         assert(v < nvars);
         assert(consdata->nfixedzeros == consdata->nvars - 1);
         assert(consdata->nfixedones == 1);

         SCIP_CALL( SCIPdelConsLocal(scip, cons) );
         *mustcheck = FALSE;
      }
   }
   assert(consdata->nfixedzeros + consdata->nfixedones <= consdata->nvars);

   return SCIP_OKAY;
}

/** checks constraint for violation, returns TRUE iff constraint is feasible */
static
SCIP_Bool checkCons(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< set partitioning / packing / covering constraint to be checked */
   SCIP_SOL*             sol                 /**< primal CIP solution */
   )
{
   SCIP_VAR** vars;
   SCIP_Real solval;
   SCIP_Real sum;
   SCIP_Real sumbound;
   SCIP_Real absviol;
   SCIP_Real relviol;
   SCIP_Bool check;
   int nvars;
   int v;

   /* calculate the constraint's activity */
   vars = consdata->vars;
   nvars = consdata->nvars;
   sum = 0.0;
   sumbound = ((SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING ? 1.0 : 1.0 + 2*SCIPfeastol(scip));
   for( v = 0; v < nvars && sum < sumbound; ++v )  /* if sum >= sumbound, the feasibility is clearly decided */
   {
      assert(SCIPvarIsBinary(vars[v]));

      solval = SCIPgetSolVal(scip, sol, vars[v]);
      assert(SCIPisFeasGE(scip, solval, 0.0) && SCIPisFeasLE(scip, solval, 1.0));

      sum += solval;
   }

   absviol = sum - 1.0;
   relviol = SCIPrelDiff(sum, 1.0);
   switch( consdata->setppctype )
   {
   case SCIP_SETPPCTYPE_PARTITIONING:
      /* in case of partitioning, the violation is equal to the absolute difference between sum and 1 */
      absviol = REALABS(absviol);
      relviol = REALABS(relviol);
      check = SCIPisFeasEQ(scip, sum, 1.0);
      break;
   case SCIP_SETPPCTYPE_PACKING:
      /* in case of packing, the violation is equal to how much sum exceeds 1 */
      check = SCIPisFeasLE(scip, sum, 1.0);
      break;
   case SCIP_SETPPCTYPE_COVERING:
      /* in case of covering, the violation is equal to how much 1 exceeds sum */
      absviol = -absviol;
      relviol = -relviol;
      check = SCIPisFeasGE(scip, sum, 1.0);
      break;
   default:
      SCIPerrorMessage("unknown setppc type\n");
      SCIPABORT();
      return FALSE; /*lint !e527*/
   }

   if( sol != NULL )
      SCIPupdateSolLPConsViolation(scip, sol, absviol, relviol);

   return check;
}

/** creates an LP row in a set partitioning / packing / covering constraint data object */
static
SCIP_RETCODE createRow(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons                /**< set partitioning / packing / covering constraint */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_Real lhs;
   SCIP_Real rhs;

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

   switch( consdata->setppctype )
   {
   case SCIP_SETPPCTYPE_PARTITIONING:
      lhs = 1.0;
      rhs = 1.0;
      break;
   case SCIP_SETPPCTYPE_PACKING:
      lhs = -SCIPinfinity(scip);
      rhs = 1.0;
      break;
   case SCIP_SETPPCTYPE_COVERING:
      lhs = 1.0;
      rhs = SCIPinfinity(scip);
      break;
   default:
      SCIPerrorMessage("unknown setppc type\n");
      return SCIP_INVALIDDATA;
   }

   SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row, cons, SCIPconsGetName(cons), lhs, rhs,
         SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsRemovable(cons)) );

   SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->row, consdata->nvars, consdata->vars, 1.0) );

   return SCIP_OKAY;
}

/** adds setppc constraint as cut to the LP */
static
SCIP_RETCODE addCut(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< setppc constraint */
   SCIP_Bool*            cutoff              /**< whether a cutoff has been detected */
   )
{
   SCIP_CONSDATA* consdata;

   assert( cutoff != NULL );
   *cutoff = FALSE;

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

   if( consdata->row == NULL )
   {
      /* convert set partitioning constraint data into LP row */
      SCIP_CALL( createRow(scip, cons) );
   }
   assert(consdata->row != NULL);

   /* insert LP row as cut */
   if( !SCIProwIsInLP(consdata->row) )
   {
      SCIPdebugMsg(scip, "adding constraint <%s> as cut to the LP\n", SCIPconsGetName(cons));
      SCIP_CALL( SCIPaddRow(scip, consdata->row, FALSE, cutoff) );
   }

   return SCIP_OKAY;
}

/** adds setppc constraint as row to the NLP, if not added yet */
static
SCIP_RETCODE addNlrow(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons                /**< setppc constraint */
   )
{
   SCIP_CONSDATA* consdata;

   assert(SCIPisNLPConstructed(scip));

   /* skip deactivated, redundant, or local constraints (the NLP does not allow for local rows at the moment) */
   if( !SCIPconsIsActive(cons) || !SCIPconsIsChecked(cons) || SCIPconsIsLocal(cons) )
      return SCIP_OKAY;

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

   if( consdata->nlrow == NULL )
   {
      SCIP_Real lhs, rhs;
      SCIP_Real* coefs;
      int i;

      SCIP_CALL( SCIPallocBufferArray(scip, &coefs, consdata->nvars) );
      for( i = 0; i < consdata->nvars; ++i )
         coefs[i] = 1.0;

      switch( SCIPgetTypeSetppc(scip, cons) )
      {
      case SCIP_SETPPCTYPE_PARTITIONING:
         lhs = 1.0;
         rhs = 1.0;
         break;

      case SCIP_SETPPCTYPE_PACKING:
         lhs = -SCIPinfinity(scip);
         rhs = 1.0;
         break;

      case SCIP_SETPPCTYPE_COVERING:
         lhs = 1.0;
         rhs = SCIPinfinity(scip);
         break;

      default:
         SCIPerrorMessage("unexpected setppc type\n");
         return SCIP_ERROR;
      }

      SCIP_CALL( SCIPcreateNlRow(scip, &consdata->nlrow, SCIPconsGetName(cons),
         0.0, consdata->nvars, consdata->vars, coefs, NULL, lhs, rhs, SCIP_EXPRCURV_LINEAR) );
      assert(consdata->nlrow != NULL);

      SCIPfreeBufferArray(scip, &coefs);
   }

   if( !SCIPnlrowIsInNLP(consdata->nlrow) )
   {
      SCIP_CALL( SCIPaddNlRow(scip, consdata->nlrow) );
   }

   return SCIP_OKAY;
}

/** checks constraint for violation, and adds it as a cut if possible */
static
SCIP_RETCODE separateCons(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< set partitioning / packing / covering constraint to be separated */
   SCIP_SOL*             sol,                /**< primal CIP solution, NULL for current LP solution */
   SCIP_Bool             lpfeas,             /**< is the given solution feasible for the current LP ? */
   SCIP_Bool*            cutoff,             /**< pointer to store TRUE, if the node can be cut off */
   SCIP_Bool*            separated,          /**< pointer to store TRUE, if a cut was found */
   SCIP_Bool*            reduceddom          /**< pointer to store TRUE, if a domain reduction was found */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_Bool addcut;
   SCIP_Bool mustcheck;

   assert(cons != NULL);
   assert(SCIPconsGetHdlr(cons) != NULL);
   assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
   assert(cutoff != NULL);
   assert(separated != NULL);
   assert(reduceddom != NULL);

   *cutoff = FALSE;

   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
   assert(consdata->nvars == 0 || consdata->vars != NULL);
   assert(0 <= consdata->nfixedzeros && consdata->nfixedzeros <= consdata->nvars);
   assert(0 <= consdata->nfixedones && consdata->nfixedones <= consdata->nvars);

   /* skip constraints already in the LP */
   if( lpfeas && consdata->row != NULL && SCIProwIsInLP(consdata->row) )
      return SCIP_OKAY;

   SCIPdebugMsg(scip, "separating constraint <%s>\n", SCIPconsGetName(cons));

   /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
   if( lpfeas )
   {
      int nfixedvars = 0;

      SCIP_CALL( processFixings(scip, cons, cutoff, &nfixedvars, &addcut, &mustcheck) );

      *reduceddom = (nfixedvars > 0);
   }
   else
   {
      mustcheck = TRUE;
      addcut = FALSE;
   }

   if( mustcheck )
   {
      assert(!addcut);

      /* variable's fixings didn't give us any information -> we have to check the constraint */
      if( lpfeas && consdata->row != NULL )
      {
         SCIP_Real feasibility;

         assert(!SCIProwIsInLP(consdata->row));
         feasibility = SCIPgetRowSolFeasibility(scip, consdata->row, sol);
         addcut = SCIPisFeasNegative(scip, feasibility);
      }
      else
         addcut = !checkCons(scip, consdata, sol);

      if( !addcut )
      {
         /* constraint was feasible -> increase age */
         SCIP_CALL( SCIPincConsAge(scip, cons) );
      }
   }

   if( addcut )
   {
      /* insert LP row as cut */
      SCIP_CALL( addCut(scip, cons, cutoff) );
      SCIP_CALL( SCIPresetConsAge(scip, cons) );
      *separated = TRUE;
   }

   return SCIP_OKAY;
}

/** enforces the pseudo solution on the given constraint */
static
SCIP_RETCODE enforcePseudo(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< set partitioning / packing / covering constraint to be separated */
   SCIP_Bool*            cutoff,             /**< pointer to store TRUE, if the node can be cut off */
   SCIP_Bool*            infeasible,         /**< pointer to store TRUE, if the constraint was infeasible */
   SCIP_Bool*            reduceddom,         /**< pointer to store TRUE, if a domain reduction was found */
   SCIP_Bool*            solvelp             /**< pointer to store TRUE, if the LP has to be solved */
   )
{
   SCIP_Bool addcut;
   SCIP_Bool mustcheck;
   int nfixedvars = 0;

   assert(!SCIPhasCurrentNodeLP(scip));
   assert(cons != NULL);
   assert(SCIPconsGetHdlr(cons) != NULL);
   assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
   assert(cutoff != NULL);
   assert(infeasible != NULL);
   assert(reduceddom != NULL);
   assert(solvelp != NULL);

   /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
   SCIP_CALL( processFixings(scip, cons, cutoff, &nfixedvars, &addcut, &mustcheck) );

   *reduceddom = (nfixedvars > 0);

   if( mustcheck )
   {
      SCIP_CONSDATA* consdata;

      assert(!addcut);

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

      if( checkCons(scip, consdata, NULL) )
      {
         /* constraint was feasible -> increase age */
         SCIP_CALL( SCIPincConsAge(scip, cons) );
      }
      else
      {
         /* constraint was infeasible -> reset age */
         SCIP_CALL( SCIPresetConsAge(scip, cons) );
         *infeasible = TRUE;
      }
   }

   if( addcut )
   {
      /* a cut must be added to the LP -> we have to solve the LP immediately */
      SCIP_CALL( SCIPresetConsAge(scip, cons) );
      *solvelp = TRUE;
   }

   return SCIP_OKAY;
}

/** gets the key of the given element */
static
SCIP_DECL_HASHGETKEY(hashGetKeySetppccons)
{  /*lint --e{715}*/
   /* the key is the element itself */
   return elem;
}

/** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
static
SCIP_DECL_HASHKEYEQ(hashKeyEqSetppccons)
{
#ifndef NDEBUG
   SCIP* scip;
#endif
   SCIP_CONSDATA* consdata1;
   SCIP_CONSDATA* consdata2;
   SCIP_Bool coefsequal;
   int i;

   consdata1 = SCIPconsGetData((SCIP_CONS*)key1);
   consdata2 = SCIPconsGetData((SCIP_CONS*)key2);
   assert(consdata1->sorted);
   assert(consdata2->sorted);
#ifndef NDEBUG
   scip = (SCIP*)userptr;
   assert(scip != NULL);
#endif

   /* checks trivial case */
   if( consdata1->nvars != consdata2->nvars )
      return FALSE;

   coefsequal = TRUE;

   for( i = 0; i < consdata1->nvars; ++i )
   {
      /* tests if variables are equal */
      if( consdata1->vars[i] != consdata2->vars[i] )
      {
         assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
            SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == -1);
         coefsequal = FALSE;
         break;
      }
      assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 0);
   }

   return coefsequal;
}

/** returns the hash value of the key */
static
SCIP_DECL_HASHKEYVAL(hashKeyValSetppccons)
{
   SCIP_CONSDATA* consdata;
   int minidx;
   int mididx;
   int maxidx;
#ifndef NDEBUG
   SCIP* scip;

   scip = (SCIP*)userptr;
   assert(scip != NULL);
#endif

   consdata = SCIPconsGetData((SCIP_CONS*)key);
   assert(consdata != NULL);
   assert(consdata->nvars > 0);

   /* sorts the constraints */
   consdataSort(consdata);

   minidx = SCIPvarGetIndex(consdata->vars[0]);
   mididx = SCIPvarGetIndex(consdata->vars[consdata->nvars / 2]);
   maxidx = SCIPvarGetIndex(consdata->vars[consdata->nvars - 1]);
   assert(minidx >= 0 && minidx <= maxidx);

   return SCIPhashFour(consdata->nvars, minidx, mididx, maxidx);
}

/** add extra clique-constraints resulting from a given cliquepartition to SCIP */
static
SCIP_RETCODE addExtraCliques(
   SCIP*const            scip,               /**< SCIP data structure */
   SCIP_VAR**const       binvars,            /**< binary variables to create clique constraints */
   int const             nbinvars,           /**< number of binary variables to create clique constraints */
   int*const             cliquepartition,    /**< clique partition of binary variables */
   int const             ncliques,           /**< number of cliques in cliquepartition */
   SCIP_CONS**const      usefulconss,        /**< storage for created constraints */
   int*const             nusefulconss,       /**< pointer to store number of useful created constraints */
   int const             nrounds,            /**< actual presolving round */
   int*const             nfixedvars,         /**< pointer to count number of deleted variables */
   int*const             naddconss,          /**< pointer to count number of added constraints */
   int*const             ndelconss,          /**< pointer to count number of deleted constraints */
   int*const             nchgcoefs,          /**< pointer to count number of deleted coefficients */
   SCIP_Bool*const       cutoff              /**< pointer to store if the problem is infeasible due to a fixing */
   )
{
   SCIP_CONS* cliquecons;
   char name[SCIP_MAXSTRLEN];
   int lastclqidx;
   int nadded;
   int c;
   int v;

   assert(scip != NULL);
   assert(binvars != NULL || nbinvars == 0);
   assert(cliquepartition != NULL || nbinvars == 0);
   assert(ncliques >= 0 && ncliques <= nbinvars);
   assert(usefulconss != NULL);
   assert(nusefulconss != NULL);
   assert(nfixedvars != NULL);
   assert(naddconss != NULL);
   assert(ndelconss != NULL);
   assert(nchgcoefs != NULL);
   assert(cutoff != NULL);

   /* no given binary variables */
   if( nbinvars == 0 || ncliques == 0 )
      return SCIP_OKAY;

   assert(binvars != NULL);
   assert(cliquepartition != NULL);

   /* no useful clique information */
   if( ncliques == nbinvars )
      return SCIP_OKAY;

   lastclqidx = 0;

   /* @todo: maybe sort cliques and accordingly the variables so it will be faster to add the constraints */
   for( c = 0; c < ncliques - 1; ++c )
   {
      if( lastclqidx >= cliquepartition[c] )
         continue;

      nadded = 0;

      /* name the clique constraint */
      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "extra_clq_%d_round_%d", cliquepartition[c], nrounds);
      SCIP_CALL( SCIPcreateConsSetpack(scip, &cliquecons, name, 0, NULL,
            TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );

      /* add variables to clique constraint */
      for( v = c; v < nbinvars - 1; ++v )
      {
         if( cliquepartition[c] == cliquepartition[v] )
         {
            SCIP_CALL( addCoef(scip, cliquecons, binvars[v]) );
            ++nadded;
         }
      }

      /* @todo: try to find a good value for what are enough variables to create this constraint, maybe at least
       *        (nmaxvars(over all conss)-nminvars(over all conss))/2 */
      if( nadded >= 2 )
      {
         SCIP_CONSDATA* cliqueconsdata;

         SCIPdebugMsg(scip, " -> adding clique constraint: ");
         SCIPdebugPrintCons(scip, cliquecons, NULL);
         SCIP_CALL( SCIPaddCons(scip, cliquecons) );
         ++(*naddconss);

         /* we only want to consider merged constraints */
         SCIP_CALL( mergeMultiples(scip, cliquecons, nfixedvars, ndelconss, nchgcoefs, cutoff) );
         if( *cutoff )
         {
            SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );

            return SCIP_OKAY;
         }

         cliqueconsdata = SCIPconsGetData(cliquecons);
         assert(cliqueconsdata != NULL);

         /* the artificial constraints could be deleted while merging */
         if( !SCIPconsIsDeleted(cliquecons) && nadded - cliqueconsdata->nfixedzeros >= 2 )
         {
            assert(cliqueconsdata->nfixedones == 0);

            /* save the type and constraint */
            usefulconss[*nusefulconss] = cliquecons;
            ++(*nusefulconss);
         }
         SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
      }
      else
      {
         SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
      }
      lastclqidx = cliquepartition[c];
   }

   return SCIP_OKAY;
}


/** start to collect setpartitioning and setpacking constraints, and try to remove fixed variables and merged these
 *  constraints
 */
static
SCIP_RETCODE collectCliqueConss(
   SCIP*const            scip,               /**< SCIP data structure */
   SCIP_CONS**const      conss,              /**< constraint set */
   int const             nconss,             /**< number of constraints in constraint set */
   SCIP_CONS**const      usefulconss,        /**< storage for created constraints */
   int*const             nusefulconss,       /**< pointer to store number of useful created constraints */
   int*const             nfixedvars,         /**< pointer to count number of deleted variables */
   int*const             ndelconss,          /**< pointer to count number of deleted constraints */
   int*const             nchgcoefs,          /**< pointer to count number of deleted coefficients */
   SCIP_Bool*const       cutoff              /**< pointer to store if the problem is infeasible due to a fixing */
   )
{
   SCIP_CONS* cons;
   SCIP_CONSDATA* consdata;
   SCIP_Bool addcut;
   SCIP_Bool mustcheck;
   int nlocaladdconss = 0;
   int c;

   assert(scip != NULL);
   assert(conss != NULL || nconss == 0);
   assert(usefulconss != NULL);
   assert(nusefulconss != NULL);
   assert(nfixedvars != NULL);
   assert(ndelconss != NULL);
   assert(nchgcoefs != NULL);
   assert(cutoff != NULL);

   if( nconss == 0 )
      return SCIP_OKAY;

   assert(conss != NULL);

   for( c = nconss - 1; c >= 0; --c )
   {
      cons = conss[c];

      /* we only want to consider constraints with either active or negated of active variables, applyfixings removes
       * aggregated and fixed variables to zero, processFixings removes fixings to one but no aggregation
       *
       * @todo: maybe write a new method for deleting aggregations and all fixings
       */
      SCIP_CALL( applyFixings(scip, cons, &nlocaladdconss, ndelconss, nfixedvars, cutoff) );
      if( *cutoff )
         return SCIP_OKAY;

      if( SCIPconsIsDeleted(cons) )
      {
         /* reset nlocaladdconss and continue */
         nlocaladdconss = 0;
         continue;
      }
      assert(nlocaladdconss == 0);

      SCIP_CALL( processFixings(scip, cons, cutoff, nfixedvars, &addcut, &mustcheck) );
      if( *cutoff )
         return SCIP_OKAY;

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

      /* we only want to consider merged constraints */
      SCIP_CALL( mergeMultiples(scip, cons, nfixedvars, ndelconss, nchgcoefs, cutoff) );
      if( *cutoff )
         return SCIP_OKAY;

      if( SCIPconsIsModifiable(cons) || !SCIPconsIsActive(cons) )
         continue;

      assert(consdata->nfixedones == 0);

      if( consdata->nvars == 0 )
         continue;

      /* @todo: check for covering constraints with only two variables which are equal to a packing constraint with
       * negated variables */
      if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
      {
         assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/

         usefulconss[*nusefulconss] = cons;
         ++(*nusefulconss);
      }
   }

   return SCIP_OKAY;  /*lint !e438*/
}

/** creating all necessary data in array structure, collect all clique constraint variables and occurrences,
 *  @note works only with merged and active not set-covering constraints
 */
static
SCIP_RETCODE collectCliqueData(
   SCIP*const            scip,               /**< SCIP data structure */
   SCIP_CONS**const      usefulconss,        /**< clique constraints */
   int const             nusefulconss,       /**< number of clique constraints */
   SCIP_VAR**const       usefulvars,         /**< storage for all found variables */
   int*const             nusefulvars,        /**< pointer to store number of added variables */
   SCIP_HASHMAP*const    vartoindex,         /**< hashmap mapping variables to indices */
   int*const             varnconss,          /**< storage for remembering the number of constraints a variable occurs */
   int*const             maxnvarconsidx,     /**< storage for the maximal number of occurrences of a variable */
   int**const            varconsidxs,        /**< storage for constraint indices in which the corresponding variable exists */
   int*const             maxnvars            /**< pointer to store maximal number of variables of a constraint */
   )
{
   SCIP_CONS* cons;
   SCIP_CONSDATA* consdata;
   int varindex;
   int c;
   int v;

   assert(scip != NULL);
   assert(usefulconss != NULL || nusefulconss == 0);
   assert(usefulvars != NULL);
   assert(nusefulvars != NULL);
   assert(vartoindex != NULL);
   assert(varnconss != NULL);
   assert(maxnvarconsidx != NULL);
   assert(varconsidxs != NULL);
   assert(maxnvars != NULL);

   if( nusefulconss == 0 )
      return SCIP_OKAY;

   assert(usefulconss != NULL);

   for( c = nusefulconss - 1; c >= 0; --c )
   {
      cons = usefulconss[c];

      assert(SCIPconsIsActive(cons));

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

      /* here we should have no covering constraints anymore and the constraint data should be merged */
      assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
      assert(consdata->merged);

      /* save maximal number of vars */
      if( consdata->nvars > *maxnvars )
         *maxnvars = consdata->nvars;

      /* adding variables and information about occurrences to local data structure */
      for( v = consdata->nvars - 1; v >= 0; --v )
      {
         SCIP_VAR* var;

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

         /* don't remember fixed vars */
         if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
            continue;

         /* only collect active or negated active variables */
         assert(SCIPvarIsActive(var) || (SCIPvarIsNegated(var) && SCIPvarIsActive(SCIPvarGetNegationVar(var))));

         if( !SCIPhashmapExists(vartoindex, (void*) var) )
         {
            SCIP_VAR* tmpvar;

            usefulvars[*nusefulvars] = var;
            ++(*nusefulvars);
            varindex = *nusefulvars;
            SCIP_CALL( SCIPhashmapInsertInt(vartoindex, (void*) var, varindex) );

            /* get the maximal number of occurrences of this variable, if this variables  */
            tmpvar = SCIPvarIsNegated(var) ? SCIPvarGetNegatedVar(var) : var;
            maxnvarconsidx[varindex] = SCIPvarGetNLocksDownType(tmpvar, SCIP_LOCKTYPE_MODEL)
               + SCIPvarGetNLocksUpType(tmpvar, SCIP_LOCKTYPE_MODEL);
            SCIP_CALL( SCIPallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) );  /*lint !e866*/
         }
         else
         {
            assert(SCIPhashmapExists(vartoindex, (void*) var));
            varindex = SCIPhashmapGetImageInt(vartoindex, (void*) var);
         }

         /* the number of occurrences of a variable is not limited by the locks (so maybe we have to increase memory),
          * because for examples converted cuts are not check and therefore they have no locks on their variables */
         if( varnconss[varindex] == maxnvarconsidx[varindex] )
         {
            maxnvarconsidx[varindex] = SCIPcalcMemGrowSize(scip, maxnvarconsidx[varindex] + 1);
            SCIP_CALL( SCIPreallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
         }

         assert(varnconss[varindex] < maxnvarconsidx[varindex]);
         /* add the constraint number to the variable list */
         varconsidxs[varindex][varnconss[varindex]] = c;
         /* increase number of occurrences for variables */
         ++(varnconss[varindex]);
      }
   } /* data structure created */

   return SCIP_OKAY;
}

/** correct clique data due to an aggregation */
static
void deleteCliqueDataEntry(
   SCIP_VAR*const        var,                /**< variable which appears less */
   int const             considx,            /**< constraint index which to remove */
   SCIP_HASHMAP*const    vartoindex,         /**< hashmap mapping variables to indices */
   int*const             varnconss,          /**< storage for remembering the number of constraints a variable occurs */
   int**const            varconsidxs         /**< storage for constraint indices in which the corresponding variable exists */
   )
{
   int varindex;
   int i;
#ifndef NDEBUG
   SCIP_Bool found = FALSE;
#endif

   assert(var != NULL);
   assert(SCIPvarGetLbLocal(var) < 0.5 && SCIPvarGetUbLocal(var) > 0.5);
   assert(considx >= 0);
   assert(vartoindex != NULL);
   assert(varnconss != NULL);
   assert(varconsidxs != NULL);

   assert(SCIPhashmapExists(vartoindex, (void*) var));
   varindex = SCIPhashmapGetImageInt(vartoindex, (void*) var);

   /* remove entry of variable at the given position */
   for( i = 0; i < varnconss[varindex]; ++i )
   {
      if( varconsidxs[varindex][i] == considx )
      {
         varconsidxs[varindex][i] = varconsidxs[varindex][varnconss[varindex] - 1];
#ifndef NDEBUG
         found = TRUE;
#endif
         --(varnconss[varindex]);
         break;
      }
   }
   assert(found);
}

/* correct local data structure, add constraint entry to variable data  */
static
SCIP_RETCODE addCliqueDataEntry(
   SCIP*const            scip,               /**< SCIP data structure */
   SCIP_VAR*const        addvar,             /**< variable which was added */
   int const             considx,            /**< constraint index which to add */
   SCIP_Bool const       maybenew,           /**< could be a new variables, a negated of an already existing */
   SCIP_VAR**const       usefulvars,         /**< storage for all found variables */
   int*const             nusefulvars,        /**< pointer to store number of added variables */
   SCIP_HASHMAP*const    vartoindex,         /**< hashmap mapping variables to indices */
   int*const             varnconss,          /**< storage for remembering the number of constraints a variable occurs */
   int*const             maxnvarconsidx,     /**< storage for the maximal number of occurrences of a variable */
   int**const            varconsidxs         /**< storage for constraint indices in which the corresponding variable exists */
   )
{
   int varindex;

   assert(scip != NULL);
   assert(addvar != NULL);
   assert(SCIPvarGetLbLocal(addvar) < 0.5 && SCIPvarGetUbLocal(addvar) > 0.5);
   assert(usefulvars != NULL);
   assert(nusefulvars != NULL);
   assert(vartoindex != NULL);
   assert(varnconss != NULL);
   assert(maxnvarconsidx != NULL);
   assert(varconsidxs != NULL);

   /* we add the variable to the hashmap if its new */
   if( maybenew && !SCIPhashmapExists(vartoindex, (void*) addvar) )
   {
      assert(SCIPvarIsActive(addvar) || SCIPvarIsNegated(addvar));
      assert(SCIPvarGetNegatedVar(addvar) != NULL && SCIPhashmapExists(vartoindex, (void*) SCIPvarGetNegatedVar(addvar)));

      /* @note because we can only have created a negated variable, and we already allocated enough memory for
       * all (even not existing) negated variables the usefulvars array should be big enough
       */
      SCIPsortedvecInsertDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, addvar, nusefulvars, NULL);
      varindex = *nusefulvars;
      SCIP_CALL( SCIPhashmapInsertInt(vartoindex, (void*) addvar, varindex) );

      assert(varconsidxs[varindex] == NULL);

      maxnvarconsidx[varindex] = 1;
      SCIP_CALL( SCIPallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
      varnconss[varindex] = 0;
   }
   else
   {
      varindex = SCIPhashmapGetImageInt(vartoindex, (void*) addvar);

      /* grow the needed memory if we added a variable */
      if( varnconss[varindex] == maxnvarconsidx[varindex] )
      {
         maxnvarconsidx[varindex] = SCIPcalcMemGrowSize(scip, maxnvarconsidx[varindex] + 1);
         SCIP_CALL( SCIPreallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
      }
   }
   assert(varnconss[varindex] < maxnvarconsidx[varindex]);
   varconsidxs[varindex][varnconss[varindex]] = considx;

   /* increase number of occurrences for variables */
   ++(varnconss[varindex]);

   return SCIP_OKAY;
}


/** check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
 *  possible
 */
static
SCIP_RETCODE presolvePropagateCons(
   SCIP*const            scip,               /**< SCIP data structure */
   SCIP_CONS*const       cons,               /**< constraint */
   SCIP_Bool const       aggregate,          /**< try to aggregate if possible */
   SCIP_VAR**            undoneaggrvars,     /**< array to store aggregation variables, if aggregation is not performed
                                              *   yet; both variables are standing next to each other; or NULL if
                                              *   aggregate == TRUE
                                              */
   SCIP_Bool*            undoneaggrtypes,    /**< array to store aggregation type, if aggregation is not performed yet;
                                              *   type FALSE means the aggregation is of the form x + y = 1; type TRUE means
                                              *   the aggregation is of the form x = y; or NULL if aggregate == TRUE
                                              */
   int*const             naggregations,      /**< pointer to store number of aggregations which are not yet performed;
                                              *   or NULL if aggregate == TRUE
                                              */
   int*const             saggregations,      /**< pointer to store size of the array for aggregation type and two times
                                              *   the value is the size of the array for the aggregation variables which
                                              *   are not yet performed; or NULL if aggregate == TRUE
                                              */
   int*const             nfixedvars,         /**< pointer to count number of deleted variables */
   int*const             naggrvars,          /**< pointer to count number of aggregated variables */
   int*const             ndelconss,          /**< pointer to count number of deleted constraints */
   SCIP_Bool*const       cutoff              /**< pointer to store if the problem is infeasible due to a fixing */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR** vars;
   int nvars;
   int v;
   SCIP_Bool fixed;

   assert(scip != NULL);
   assert(cons != NULL);
   assert(nfixedvars != NULL);
   assert(naggrvars != NULL);
   assert(ndelconss != NULL);
   assert(cutoff != NULL);

   if( !SCIPconsIsActive(cons) )
      return SCIP_OKAY;

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

   if( consdata->presolpropagated )
      return SCIP_OKAY;

   consdata->presolpropagated = TRUE;

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

   /* no variables left */
   if( nvars == 0 && !SCIPconsIsModifiable(cons) )
   {
      if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
      {
         SCIPdebugMsg(scip, "empty set-partition/-covering constraint <%s> found -> cutoff\n", SCIPconsGetName(cons));
         *cutoff = TRUE;

         return SCIP_OKAY;
      }
      else
      {
         assert(consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/

         /* delete constraint */
         SCIPdebugMsg(scip, " -> deleting constraint <%s>, no variables left\n", SCIPconsGetName(cons));
         SCIP_CALL( SCIPdelCons(scip, cons) );
         ++(*ndelconss);

         return SCIP_OKAY;
      }
   }

   /* more then two variables are fixed */
   if( consdata->nfixedones > 1 )
   {
      /* at least two variables are fixed to 1:
       * - a set covering constraint is feasible anyway and can be deleted
       * - a set partitioning or packing constraint is infeasible
       */
      if( consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
      {
         /* delete constraint */
         SCIPdebugMsg(scip, " -> deleting set-covering constraint <%s>, at least two variables are fixed to 1\n", SCIPconsGetName(cons));
         SCIP_CALL( SCIPdelCons(scip, cons) );
         ++(*ndelconss);

         return SCIP_OKAY;
      }

      SCIPdebugMsg(scip, "set partitioning / packing constraint <%s> is infeasible, %d variables fixed to one\n", SCIPconsGetName(cons), consdata->nfixedones);
      *cutoff = TRUE;

      return SCIP_OKAY;
   }

   if( consdata->nfixedones == 1 )
   {
      /* exactly one variable is fixed to 1:
       * - a set covering constraint is feasible anyway and can be disabled
       * - all other variables in a set partitioning or packing constraint must be zero
       */
      if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING && consdata->nfixedzeros < nvars - 1 ) /*lint !e641*/
      {
         assert(vars != NULL);

         for( v = nvars - 1; v >= 0; --v )
         {
            if( SCIPvarGetLbLocal(vars[v]) + 0.5 < SCIPvarGetUbLocal(vars[v]) )
            {
               SCIPdebugMsg(scip, "trying to fix <%s> to 0 due to at least one variable is already fixed to 1\n", SCIPvarGetName(vars[v]));

               /* fix all remaining variables to zero, constraint is already feasible or infeasible */
               SCIP_CALL( SCIPfixVar(scip, vars[v], 0.0, cutoff, &fixed) );
               if( *cutoff )
               {
                  SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == 0\n",
                     SCIPconsGetName(cons), SCIPvarGetName(vars[v]));

                  return SCIP_OKAY;
               }

               assert(fixed);
               ++(*nfixedvars);
            }
         }
      }

      if( !SCIPconsIsModifiable(cons) || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
      {
         /* delete constraint */
         SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
         assert(SCIPconsIsActive(cons));
         SCIP_CALL( SCIPdelCons(scip, cons) );
         ++(*ndelconss);
      }

      return SCIP_OKAY;
   }

   /* other propagations can only be done on not modifiable constraints */
   if( SCIPconsIsModifiable(cons) )
      return SCIP_OKAY;

   assert(vars != NULL);

   /* all variables were fixed to zero then either delete the constraint or stop with infeasibility */
   if( consdata->nfixedzeros == nvars )
   {
      assert(consdata->nfixedones == 0);

      /* all variables are fixed to zero:
       * - a set packing constraint is feasible anyway and can be deleted
       * - a set partitioning or covering constraint is infeasible, and so is the whole problem
       */
      if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
      {
         SCIPdebugMsg(scip, "set partitioning / covering constraint <%s> is infeasible\n", SCIPconsGetName(cons));
         *cutoff = TRUE;

         return SCIP_OKAY;
      }

      /* delete constraint */
      SCIPdebugMsg(scip, " -> deleting set-packing constraint <%s>, all variables are fixed to zero\n", SCIPconsGetName(cons));
      assert(SCIPconsIsActive(cons));
      SCIP_CALL( SCIPdelCons(scip, cons) );
      ++(*ndelconss);

      return SCIP_OKAY;
   }

   /* all but one variable were fixed to zero then delete the constraint and for setpartition fix the remaining variable to 1 */
   if( consdata->nfixedzeros + 1 == nvars )
   {
      assert(consdata->nfixedones == 0);

      /* all variables except one are fixed to zero:
       * - a set packing constraint is feasible anyway, and can be deleted
       * - a set partitioning or covering constraint is feasible and can be deleted after the
       *   remaining variable is fixed to one
       */
      if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
      {
         fixed = FALSE;
         for( v = nvars - 1; v >= 0; --v )
         {
            assert(SCIPvarGetLbLocal(vars[v]) < 0.5);
            if( SCIPvarGetUbLocal(vars[v]) > 0.5 )
            {
               SCIPdebugMsg(scip, "trying to fix <%s> to 1 due to it's the last unfixed variable is the set-partitioning/covering constraint\n", SCIPvarGetName(vars[v]));

               /* fix the remaining set partition variable */
               SCIP_CALL( SCIPfixVar(scip, vars[v], 1.0, cutoff, &fixed) );
               if( *cutoff )
               {
                  SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == 1\n",
                     SCIPconsGetName(cons), SCIPvarGetName(vars[v]));

                  return SCIP_OKAY;
               }

               assert(fixed);
               ++(*nfixedvars);
               break;
            }
         }
         assert(fixed);
      }

      /* delete constraint */
      SCIPdebugMsg(scip, " -> deleting constraint <%s>, all %svariables are fixed\n", SCIPconsGetName(cons), consdata->setppctype == (int) SCIP_SETPPCTYPE_PACKING ? "but one " : "");
      assert(SCIPconsIsActive(cons));
      SCIP_CALL( SCIPdelCons(scip, cons) );
      ++(*ndelconss);

      return SCIP_OKAY;
   }

   /* all but two variable were fixed to zero in a setpartitioning constraint then delete the constraint and
    * aggregate the remaining two variables
    */
   if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedzeros + 2 == nvars ) /*lint !e641*/
   {
      SCIP_VAR* var;

      var = NULL;
      for( v = nvars - 1; v >= 0; --v )
      {
         assert(SCIPvarGetLbLocal(vars[v]) < 0.5);

         if( SCIPvarGetUbLocal(vars[v]) > 0.5 )
         {
            if( var == NULL )
               var = vars[v];
            else
            {
               SCIP_Bool redundant;
               SCIP_Bool aggregated;
#ifdef VARUSES
               SCIP_CONSHDLR* conshdlr;
               SCIP_CONSHDLRDATA* conshdlrdata;

               /* get event handler and event handler data */
               conshdlr = SCIPconsGetHdlr(cons);
               assert(conshdlr != NULL);
               conshdlrdata = SCIPconshdlrGetData(conshdlr);
               assert(conshdlrdata != NULL);
#endif
               if( aggregate )
               {
                  SCIPdebugMsg(scip, "trying to aggregate <%s> and <%s> due to they are the last two unfixed variables in the set partitionning constraint <%s>\n", SCIPvarGetName(var), SCIPvarGetName(vars[v]), SCIPconsGetName(cons));

#ifdef VARUSES
                  /* in order to not mess up the variable usage counting, we have to decrease usage counting, aggregate,
                   * and increase usage counting again
                   */
                  SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, var) );
                  SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, vars[v]) );
#endif

                  /* aggregate last remaining variables in the set partitioning constraint */
                  SCIP_CALL( SCIPaggregateVars(scip, var, vars[v], 1.0, 1.0, 1.0, cutoff, &redundant, &aggregated) );
                  if( *cutoff )
                  {
                     SCIPdebugMsg(scip, "set partitioning constraint <%s>: aggregate <%s> + <%s> == 1\n",
                        SCIPconsGetName(cons), SCIPvarGetName(var), SCIPvarGetName(vars[v]));

                     return SCIP_OKAY;
                  }

#ifdef VARUSES
                  /* increase variable usage counting again */
                  SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, var) );
                  SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, vars[v]) );
#endif

                  if( aggregated )
                     ++(*naggrvars);

                  if( redundant )
                  {
                     /* delete constraint */
                     SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
                     assert(SCIPconsIsActive(cons));
                     SCIP_CALL( SCIPdelCons(scip, cons) );
                     ++(*ndelconss);
                  }
               }
               else
               {
                  assert(undoneaggrvars != NULL);
                  assert(undoneaggrtypes != NULL);
                  assert(naggregations != NULL);
                  assert(saggregations != NULL);

                  SCIPdebugMsg(scip, "memorize the aggregation of <%s> + <%s> = 1, because they are the last two unfixed variable in the set partitioning constraints <%s>\n", SCIPvarGetName(var), SCIPvarGetName(vars[v]), SCIPconsGetName(cons));

                  /* resize the aggregation arrays if necessary */
                  if( *saggregations == *naggregations )
                  {
                     *saggregations = SCIPcalcMemGrowSize(scip, *naggregations + 1);
                     assert(*saggregations > *naggregations);
                     SCIP_CALL( SCIPreallocBufferArray(scip, &undoneaggrtypes, *saggregations) );
                     SCIP_CALL( SCIPreallocBufferArray(scip, &undoneaggrvars, 2 * (*saggregations)) );

                     /* clear the aggregation type array to set the default to the aggregation of the form x + y = 1 */
                     BMSclearMemoryArray(&(undoneaggrtypes[*naggregations]), *saggregations - *naggregations); /*lint !e866*/
                  }

                  /* memorize aggregation variables*/
                  assert(undoneaggrtypes[*naggregations] == FALSE);
                  undoneaggrvars[2 * (*naggregations)] = var;
                  undoneaggrvars[2 * (*naggregations) + 1] = vars[v];
                  ++(*naggregations);

                  if( !SCIPdoNotAggr(scip) )
                  {
                     /* delete constraint */
                     SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
                     assert(SCIPconsIsActive(cons));
                     SCIP_CALL( SCIPdelCons(scip, cons) );
                     ++(*ndelconss);
                  }
               }

               return SCIP_OKAY;
            }
         }
      }
      /* we should never be here, because the last to unfixed variables should have been either aggregated or a cutoff
       * should be applied
       */
      assert(FALSE); /*lint !e506*/
   }

   return SCIP_OKAY;
}

/** check for overlapping constraint */
static
SCIP_RETCODE checkForOverlapping(
   SCIP*const            scip,               /**< SCIP data structure */
   SCIP_CONS*const       cons,               /**< constraint which may overlap */
   int const             considx,            /**< constraint index to avoid checking against itself */
   int const             endidx,             /**< end index to check against given constraint */
   SCIP_CONS**const      usefulconss,        /**< clique constraints */
   int const             nusefulconss,       /**< number of clique constraints */
   SCIP_VAR**const       usefulvars,         /**< storage for all found variables */
   int*const             nusefulvars,        /**< pointer to store number of added variables */
   SCIP_HASHMAP*const    vartoindex,         /**< hashmap mapping variables to indices */
   int*const             varnconss,          /**< storage for remembering the number of constraints a variable occurs */
   int*const             maxnvarconsidx,     /**< storage for the maximal number of occurrences of a variable */
   int**const            varconsidxs,        /**< storage for constraint indices in which the corresponding variable exists */
   int*const             countofoverlapping, /**< the amount of variables of cons which overlap in all other constraint */
   SCIP_Bool const       shrinking,          /**< try to replace some variables with one variable */
   SCIP_Bool*const       chgcons,            /**< pointer to store if the given constraint was changed, due to
                                              *   added/deleted variables
                                              */
   SCIP_VAR**            undoneaggrvars,     /**< array to store aggregation variables, if aggregation is not performed
                                              *   yet; both variables are standing next to each other;
                                              */
   SCIP_Bool*            undoneaggrtypes,    /**< array to store aggregation type, if aggregation is not performed yet;
                                              *   type FALSE means the aggregation is of the form x + y = 1; type TRUE means
                                              *   the aggregation is of the form x = y;
                                              */
   int*const             naggregations,      /**< pointer to store number of aggregations which are not yet performed; */
   int*const             saggregations,      /**< pointer to store size of the array for aggregation type and two times
                                              *   the value is the size of the array for the aggregation variables which
                                              *   are not yet performed;
                                              */
   int*const             nfixedvars,         /**< pointer to count number of deleted variables */
   int*const             naggrvars,          /**< pointer to count number of aggregated variables */
   int*const             nchgcoefs,          /**< pointer to count number of changed coefficients */
   int*const             ndelconss,          /**< pointer to count number of deleted constraints */
   SCIP_Bool*const       cutoff              /**< pointer to store if the problem is infeasible due to a fixing */
   )
{
   SCIP_CONS* cons1;
   SCIP_CONSDATA* consdata1;
   SCIP_CONSDATA* consdata;
   SCIP_VAR** vars;
   SCIP_VAR** vars1;
   SCIP_VAR* var;
   SCIP_VAR* var1;
   SCIP_Bool fixed;
   SCIP_Bool overlapdestroyed;
   int nvars;
   int nvars1;
   int oldnfixedzeros;
   int c;
   int v;
   int v1;
#ifndef NDEBUG
   int oldnaggrvars;
#endif

   assert(scip != NULL);
   assert(cons != NULL);
   assert(usefulconss != NULL && nusefulconss > 0);
   assert(0 <= considx && considx < nusefulconss);
   assert(usefulconss[considx] == cons);
   assert(0 <= endidx && endidx <= nusefulconss);
   assert(countofoverlapping != NULL);
   assert(chgcons != NULL);
   assert(undoneaggrvars != NULL);
   assert(undoneaggrtypes != NULL);
   assert(naggregations != NULL);
   assert(saggregations != NULL);
   assert(nfixedvars != NULL);
   assert(naggrvars != NULL);
   assert(nchgcoefs != NULL);
   assert(ndelconss != NULL);
   assert(cutoff != NULL);

   if( !SCIPconsIsActive(cons) )
      return SCIP_OKAY;

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

   nvars = consdata->nvars;

   if( nvars == 0 )
      return SCIP_OKAY;

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

   oldnfixedzeros = consdata->nfixedzeros;
   overlapdestroyed = FALSE;

   /* first check for redundancy for all unprocessed constraints with cons */
   for( c = endidx - 1; c >= 0; --c )
   {
      cons1 = usefulconss[c];

      if( !SCIPconsIsActive(cons1) )
         continue;

      /* avoid checking constraint against itself */
      if( considx == c )
         continue;

      assert(usefulconss[c] != cons);

#ifndef NDEBUG
      oldnaggrvars = *naggrvars;
#endif

      /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
       * possible
       */
      SCIP_CALL( presolvePropagateCons(scip, cons1, FALSE, undoneaggrvars, undoneaggrtypes, naggregations, saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );

      if( *cutoff )
         return SCIP_OKAY;

      /* we can't handle aggregated variables later on so we should have saved them for later */
      assert(*naggrvars == oldnaggrvars);

      if( !SCIPconsIsActive(cons1) )
         continue;

      consdata1 = SCIPconsGetData(cons1);
      assert(consdata1 != NULL);

      nvars1 = consdata1->nvars;

      if( nvars1 == 0 )
         continue;

      /* no more variables from cons as nvars1 can overlap */
      assert(countofoverlapping[c] <= nvars1);

      /* constraint should not be redundant or infeasible */
      assert(consdata1->nfixedones == 0);

      SCIPdebugMsg(scip, "constraint <%s> overlaps with constraint <%s> by %d variables\n", SCIPconsGetName(cons), SCIPconsGetName(cons1), countofoverlapping[c]);

      /* cons1 includes cons */
      if( !overlapdestroyed && countofoverlapping[c] == nvars - consdata->nfixedzeros )
      {
         if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
         {
            if( nvars - consdata->nfixedzeros < nvars1 )
            {
#ifndef NDEBUG
               SCIP_Bool negated0;
               SCIP_Bool negated1;
#endif

               /* both constraints should stay merged */
               assert(consdata->merged);
               assert(consdata1->merged);

               vars1 = consdata1->vars;
               assert(vars1 != NULL);

               /* sorting array after indices of variables, negated and active counterparts would stand side by side */
               SCIPsortDownPtr((void**)vars1, SCIPvarCompActiveAndNegated, nvars1);
               /* standard setppc-sorting now lost */
               consdata1->sorted = FALSE;

               /* iterate over the both cliques variables the "same" time */
               for( v = nvars - 1, v1 = nvars1 - 1; v >= 0 && v1 >= 0; )
               {
                  if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
                  {
                     --v1;
                     continue;
                  }
                  if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
                  {
                     --v;
                     continue;
                  }

                  /* all variables inside the second clique constraint should be either active or negated of an active one */
                  assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));

                  /* get not negated variable and clique value in cons */
                  if( SCIPvarGetStatus(vars[v]) != SCIP_VARSTATUS_NEGATED )
                  {
                     var = vars[v];
#ifndef NDEBUG
                     negated0 = FALSE;
#endif
                  }
                  else
                  {
                     var = SCIPvarGetNegationVar(vars[v]);
#ifndef NDEBUG
                     negated0 = TRUE;
#endif
                  }

                  /* get active variable and clique value of next variable */
                  if( SCIPvarIsActive(vars1[v1]) )
                  {
                     var1 = vars1[v1];
#ifndef NDEBUG
                     negated1 = FALSE;
#endif
                  }
                  else
                  {
                     assert(SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1])));
                     var1 = SCIPvarGetNegationVar(vars1[v1]);
#ifndef NDEBUG
                     negated1 = TRUE;
#endif
                  }

                  /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
                  if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1)  )
                     --v;
                  /* variable index in the constraint is greater than the other one, so fix this variable */
                  else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1)  )
                  {
                     SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars1[v1]));

                     /* fix all variables except the one which has the negated var in the clique to zero */
                     SCIP_CALL( SCIPfixVar(scip, vars1[v1], 0.0, cutoff, &fixed) );
                     if( *cutoff )
                     {
                        SCIPdebugMsg(scip, "fixing led to cutoff\n");

                        return SCIP_OKAY;
                     }

                     assert(fixed);
                     ++(*nfixedvars);
                     --v1;
                  }
                  else
                  {
                     /* because the constraint's are merged it is not possible that one constraint contains a negated
                      * variable of another and because all variables in cons are in cons1 this should be really the
                      * same variable here; so we can decrease v and v1
                      */
                     assert(negated0 == negated1);

                     --v;
                     --v1;
                  }
               }
               /* maybe we ended because of cons(v reached -1) so try to add rest of cons1 to cons */
               for( ; v1 >= 0; --v1)
               {
                  if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
                     continue;

                  SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars1[v1]));

                  /* fix all variables except the one which has the negated var in the clique to zero */
                  SCIP_CALL( SCIPfixVar(scip, vars1[v1], 0.0, cutoff, &fixed) );
                  if( *cutoff )
                  {
                     SCIPdebugMsg(scip, "fixing led to cutoff\n");

                     return SCIP_OKAY;
                  }

                  assert(fixed);
                  ++(*nfixedvars);
               }
            }

            /* if caused by all fixings now this set partitioning constraint doesn't have any variable which was
             * fixed to one, it's infeasible */
            if( consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nfixedzeros == nvars1 && consdata1->nfixedones != 1 ) /*lint !e641*/
            {
               SCIPdebugMsg(scip, "all variables in the set-partitioning constraint <%s> are fixed to zero, this leads to a cutoff\n", SCIPconsGetName(cons1));
               *cutoff = TRUE;

               return SCIP_OKAY;
            }

            assert(SCIPconsIsActive(cons1));
            /* delete second constraint */
            SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it includes the setpartitioning constraint <%s> number <%d>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons), considx);

            SCIP_CALL( SCIPupdateConsFlags(scip, cons, cons1) );
            SCIP_CALL( SCIPdelCons(scip, cons1) );
            ++(*ndelconss);
         }
         /* could already be deleted because the constraint was included in another set partition constraint */
         else if( SCIPconsIsActive(cons) )
         {
            /* delete cons due to redundancy to cons1 */
            SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to inclusion in constraint <%s> number <%d>\n", SCIPconsGetName(cons), considx, SCIPconsGetName(cons1), c);

            SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons) );
            SCIP_CALL( SCIPdelCons(scip, cons) );
            ++(*ndelconss);
         }
      }
      /* cons includes cons1
       *
       * @note that zero fixations from above can only appear through a set-partitioning constraint, this means if
       *       cons was the set-partitioning constraint only variables which are not in this constraint could be fixed
       *       to zero, and this also means that the overlapping variables in this particular case are still active or
       *       fixed to 1
       *       later on it could be possible that even variables in cons are fixed to zero, which can lead to wrong
       *       results when checking if countofoverlapping[c] + consdata1->nfixedzeros == nvars1, because a fixed
       *       variable could be counted twice
       */
      else if( (!overlapdestroyed && countofoverlapping[c] + consdata1->nfixedzeros == nvars1) || countofoverlapping[c] == nvars1 )
      {
         /* even in deleted constraints we may fix unfixed variables */
         if( consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
         {
            const int oldnfixedvars = *nfixedvars;
#ifndef NDEBUG
            SCIP_Bool negated0;
            SCIP_Bool negated1;
#endif
            /* both constraints should stay merged */
            assert(consdata->merged);
            assert(consdata1->merged);

            vars1 = consdata1->vars;

            /* sorting array after indices of variables, negated and active counterparts would stand side by side */
            SCIPsortDownPtr((void**)vars1, SCIPvarCompActiveAndNegated, nvars1);
            /* standard setppc-sorting now lost */
            consdata1->sorted = FALSE;

            /* iterate over the both cliques variables the "same" time */
            for( v = nvars - 1, v1 = nvars1 - 1; v >= 0 && v1 >= 0; )
            {
               if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
               {
                  --v1;
                  continue;
               }
               if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
               {
                  --v;
                  continue;
               }

               /* all variables inside the second clique constraint should be either active or negated of an active one */
               assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
               /* all variables inside the first clique constraint should be either active or negated of an active one */
               assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));

               /* get not negated variable and clique value in cons */
               if( SCIPvarIsActive(vars[v]) )
               {
                  var = vars[v];
#ifndef NDEBUG
                  negated0 = FALSE;
#endif
               }
               else
               {
                  assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v])));
                  var = SCIPvarGetNegationVar(vars[v]);
#ifndef NDEBUG
                  negated0 = TRUE;
#endif
               }

               /* get active variable and clique value of next variable */
               if( SCIPvarIsActive(vars1[v1]) )
               {
                  var1 = vars1[v1];
#ifndef NDEBUG
                  negated1 = FALSE;
#endif
               }
               else
               {
                  assert(SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1])));
                  var1 = SCIPvarGetNegationVar(vars1[v1]);
#ifndef NDEBUG
                  negated1 = TRUE;
#endif
               }

               /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
               if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1)  )
               {
                  SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(var));

                  /* fix all variables except the one which has the negated var in the clique to zero */
                  SCIP_CALL( SCIPfixVar(scip, vars[v], 0.0, cutoff, &fixed) );
                  if( *cutoff )
                  {
                     SCIPdebugMsg(scip, "fixing led to cutoff\n");

                     return SCIP_OKAY;
                  }

                  assert(fixed);
                  ++(*nfixedvars);

                  --v;
               }
               /* variable index in the constraint is greater than the other one, so fix this variable */
               else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1)  )
                  --v1;
               else
               {
                  /* because the constraint's are merged it is not possible that one constraint contains a negated
                   * variable of another and because all variables in cons1 are in cons this should be really the same
                   * variable here; so we can decrease v and v1
                   */
                  assert(negated0 == negated1);

                  --v;
                  --v1;
               }
            }

            /* maybe we ended because of cons1(v1 reached -1) so try to add rest of cons to cons1 */
            for( ; v >= 0; --v)
            {
               if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
                  continue;

               SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars[v]));

               /* fix all variables except the one which has the negated var in the clique to zero */
               SCIP_CALL( SCIPfixVar(scip, vars[v], 0.0, cutoff, &fixed) );
               if( *cutoff )
               {
                  SCIPdebugMsg(scip, "fixing led to cutoff\n");

                  return SCIP_OKAY;
               }

               assert(fixed);
               ++(*nfixedvars);
            }

            /* if caused by all fixings now this set partitioning constraint doesn't have any variable which was
             * fixed to one, it's infeasible */
            if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedzeros == nvars && consdata->nfixedones != 1 ) /*lint !e641*/
            {
               SCIPdebugMsg(scip, "all variables in the set-partitioning constraint <%s> are fixed to zero, this leads to a cutoff\n", SCIPconsGetName(cons1));
               *cutoff = TRUE;

               return SCIP_OKAY;
            }

            /* could already be deleted because the constraint was included in another set partition constraint */
            if( SCIPconsIsActive(cons) )
            {
               /* delete cons because it include another set partitioning constraint */
               SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it includes the setpartitioning constraint <%s> number <%d>\n", SCIPconsGetName(cons), considx, SCIPconsGetName(cons1), c);
               assert(SCIPconsIsActive(cons));

               SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons) );
               SCIP_CALL( SCIPdelCons(scip, cons) );
               ++(*ndelconss);
            }

            /* due to fixings in cons0 mark overlapping invalid for checking with fixedzero variables together */
            if( oldnfixedvars < *nfixedvars )
               overlapdestroyed = TRUE;
         }
         else
         {
            assert(consdata1->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/

            /* delete cons1 due to redundancy to cons */
            SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to inclusion in constraint <%s> number <%d>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons), considx);
            assert(SCIPconsIsActive(cons1));

            SCIP_CALL( SCIPupdateConsFlags(scip, cons, cons1) );
            SCIP_CALL( SCIPdelCons(scip, cons1) );
            ++(*ndelconss);
         }
      }
      /* if cons has only one unfixed variable which is not in cons1 and cons1 has one variable which does not appear in
       * cons and both constraints are setpartitioning constraints we might aggregate both not overlapping variables and
       * delete one constraint
       */
      else if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1 && countofoverlapping[c] == nvars1 - 1 ) /*lint !e641*/
      {
         SCIP_VAR* aggvar1;
         SCIP_VAR* aggvar2;
         SCIP_Bool negated0;
         SCIP_Bool negated1;

         aggvar1 = NULL;
         aggvar2 = NULL;

         /* both constraints should stay merged */
         assert(consdata->merged);
         assert(consdata1->merged);

         vars1 = consdata1->vars;

         /* sorting array after indices of variables, negated and active counterparts would stand side by side */
         SCIPsortDownPtr((void**)vars1, SCIPvarCompActiveAndNegated, nvars1);
         /* standard setppc-sorting now lost */
         consdata1->sorted = FALSE;

         /* iterate over the both cliques variables the "same" time */
         for( v = nvars - 1, v1 = nvars1 - 1; v >= 0 && v1 >= 0; )
         {
            if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
            {
               --v1;
               continue;
            }
            if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
            {
               --v;
               continue;
            }

            /* all variables inside the second clique constraint should be either active or negated of an active one */
            assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
            /* all variables inside the first clique constraint should be either active or negated of an active one */
            assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));

            /* get not negated variable and clique value in cons */
            if( SCIPvarIsActive(vars[v]) )
            {
               var = vars[v];
               negated0 = FALSE;
            }
            else
            {
               assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v])));
               var = SCIPvarGetNegationVar(vars[v]);
               negated0 = TRUE;
            }

            /* get active variable and clique value of next variable */
            if( SCIPvarIsActive(vars1[v1]) )
            {
               var1 = vars1[v1];
               negated1 = FALSE;
            }
            else
            {
               assert(SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1])));
               var1 = SCIPvarGetNegationVar(vars1[v1]);
               negated1 = TRUE;
            }

            /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
            if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1)  )
            {
               assert(aggvar1 == NULL);
               aggvar1 = vars[v];

               if( aggvar2 != NULL )
                  break;

               --v;
            }
            /* variable index in the constraint is greater than the other one, so fix this variable */
            else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1)  )
            {
               assert(aggvar2 == NULL);
               aggvar2 = vars1[v1];

               if( aggvar1 != NULL )
                  break;

               --v1;
            }
            else
            {
               /* because the constraint's are merged it is not possible that one constraint contains a negated variable
                * of another, but both variables in both constraints still can be negated to each other
                */
               if( negated0 != negated1 )
               {
                  /* cons is except for one variable equal to cons1 and the unequal variable in cons is negated
                   * to the one in cons1, so the problem is infeasible
                   */
                  SCIPdebugMsg(scip, "two set-partitioning constraint <%s> and <%s> have only one variable not in common, but this variable <%s> appears in one constraint as the negated version as in the other constraint\n", SCIPconsGetName(cons), SCIPconsGetName(cons1), SCIPvarGetName(vars[v]));
                  *cutoff = TRUE;

                  return SCIP_OKAY;
               }
               --v;
               --v1;
            }
         }

         /* due to fixings, it is possible that there are no active variables left, we we did not recognize which variables we could aggregate */
         if( aggvar1 == NULL && aggvar2 == NULL )
            continue;

         /* determine second aggregation var, if not yet done */
         if( aggvar2 == NULL )
         {
            for( ; v1 >= 0; --v1)
            {
               if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
                  continue;

               aggvar2 = vars1[v1];
               break;
            }
         }
         /* determine first aggregation var, if not yet done */
         else if( aggvar1 == NULL )
         {
            /* maybe we ended because of cons1(v1 reached -1) so find the aggvar1 in cons */
            for( ; v >= 0; --v)
            {
               if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
                  continue;

               aggvar1 = vars[v];
               break;
            }
         }

         /* due to fixings, it is possible that there are no active variables left, we we did not recognize which variables we could aggregate */
         if( aggvar1 == NULL || aggvar2 == NULL )
            continue;

         SCIPdebugMsg(scip, "memorize the aggregation of <%s> == <%s>, because they are the last two variable which are different in these two set partitioning constraints <%s> <%s>\n", SCIPvarGetName(aggvar1), SCIPvarGetName(aggvar2), SCIPconsGetName(cons), SCIPconsGetName(cons1));

         /* resize the aggregation arrays if necessary */
         if( *saggregations == *naggregations )
         {
            *saggregations = SCIPcalcMemGrowSize(scip, *naggregations + 1);
            assert(*saggregations > *naggregations);
            SCIP_CALL( SCIPreallocBufferArray(scip, &undoneaggrtypes, *saggregations) );
            SCIP_CALL( SCIPreallocBufferArray(scip, &undoneaggrvars, 2 * (*saggregations)) );

            /* clear the aggregation type array to set the default to the aggregation of the form x + y = 1 */
            BMSclearMemoryArray(&(undoneaggrtypes[*naggregations]), *saggregations - *naggregations); /*lint !e866*/
         }

         /* memorize aggregation variables*/
         undoneaggrtypes[*naggregations] = TRUE;
         undoneaggrvars[2 * (*naggregations)] = aggvar1;
         undoneaggrvars[2 * (*naggregations) + 1] = aggvar2;
         ++(*naggregations);

         if( !SCIPdoNotAggr(scip) )
         {
            /* delete constraint */
            SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it is dominated by constraint <%s>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons));
            assert(SCIPconsIsActive(cons1));

            SCIP_CALL( SCIPupdateConsFlags(scip, cons, cons1) );
            SCIP_CALL( SCIPdelCons(scip, cons1) );
            ++(*ndelconss);
         }
      }
      /* w.l.o.g. cons is a setpartitioning constraint and countofoverlapping == nvars - oldnfixedzeros - 1 we can
       * delete all overlapping variables in cons1 and add the negated variable of the not overlapped variable to cons
       * 1; the result should be a shorter constraint with the same impact
       */
      else if( shrinking && !overlapdestroyed && countofoverlapping[c] > 1 && ((consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1) || (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars1 - 1)) ) /*lint !e641*/
      {
         SCIP_CONSDATA* consdatachange;
         SCIP_VAR** varstostay;
         SCIP_VAR** varstochange;
         SCIP_CONS* constochange;
         SCIP_CONS* constostay;
         SCIP_VAR* addvar;
         SCIP_Bool negated0;
         SCIP_Bool negated1;
         int nvarstostay;
         int nvarstochange;
         int constochangeidx;
#ifndef NDEBUG
         const int oldnchgcoefs = *nchgcoefs;
#endif

         addvar = NULL;

         assert((consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING) != (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING) || countofoverlapping[c] != nvars - 1 || countofoverlapping[c] != nvars1 - 1); /*lint !e641*/

         /* both constraints should stay merged */
         assert(consdata->merged);
         assert(consdata1->merged);

         /* sorting array after indices of variables, negated and active counterparts would stand side by side */
         SCIPsortDownPtr((void**)(consdata1->vars), SCIPvarCompActiveAndNegated, nvars1);
         /* standard setppc-sorting now lost */
         consdata1->sorted = FALSE;

         /* initialize variables */
         if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1) /*lint !e641*/
         {
            varstostay = vars;
            varstochange = consdata1->vars;
            nvarstostay = nvars;
            nvarstochange = nvars1;
            constostay = cons;
            constochange = cons1;
            consdatachange = consdata1;
            constochangeidx = c;
         }
         else
         {
            varstostay = consdata1->vars;
            varstochange = vars;
            nvarstostay = nvars1;
            nvarstochange = nvars;
            constostay = cons1;
            constochange = cons;
            consdatachange = consdata;
            constochangeidx = considx;

            *chgcons = TRUE;
         }

         /* iterate over the both cliques variables the "same" time, here we need the backward loop, because we
          * delete some variables and we don not want to loose order
          */
         for( v = nvarstostay - 1, v1 = nvarstochange - 1; v >= 0 && v1 >= 0; )
         {
            if( SCIPvarGetLbLocal(varstochange[v1]) > 0.5 || SCIPvarGetUbLocal(varstochange[v1]) < 0.5 )
            {
               --v1;
               continue;
            }
            if( SCIPvarGetLbLocal(varstostay[v]) > 0.5 || SCIPvarGetUbLocal(varstostay[v]) < 0.5 )
            {
               --v;
               continue;
            }

            /* all variables inside the second clique constraint should be either active or negated of an active one */
            assert(SCIPvarIsActive(varstochange[v1]) || (SCIPvarGetStatus(varstochange[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstochange[v1]))));
            /* all variables inside the first clique constraint should be either active or negated of an active one */
            assert(SCIPvarIsActive(varstostay[v]) || (SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v]))));

            /* get not negated variable and clique value in constostay */
            if( SCIPvarIsActive(varstostay[v]) )
            {
               var = varstostay[v];
               negated0 = FALSE;
            }
            else
            {
               assert(SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v])));
               var = SCIPvarGetNegationVar(varstostay[v]);
               negated0 = TRUE;
            }

            /* get active variable and clique value of in constochange*/
            if( SCIPvarIsActive(varstochange[v1]) )
            {
               var1 = varstochange[v1];
               negated1 = FALSE;
            }
            else
            {
               assert(SCIPvarGetStatus(varstochange[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstochange[v1])));
               var1 = SCIPvarGetNegationVar(varstochange[v1]);
               negated1 = TRUE;
            }

            /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
            if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1)  )
            {
               assert(addvar == NULL);
               addvar = varstostay[v];
               --v;
            }
            /* variable index in the constraint is greater than the other one, so fix this variable */
            else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1)  )
            {
               --v1;
            }
            else
            {
               /* because the constraint's are merged it is not possible that one constraint contains a negated variable
                * of another, but both constraint might have a variable in negated form of the other
                */
               if( negated0 != negated1 )
               {
                  assert(addvar == NULL);

                  SCIPdebugMsg(scip, "-> trying to fix <%s> to 0 because it would exist twice in a constraint\n", SCIPvarGetName(varstochange[v1]));

                  /* fix variable to zero */
                  SCIP_CALL( SCIPfixVar(scip, varstochange[v1], 0.0, cutoff, &fixed) );
                  if( *cutoff )
                  {
                     SCIPdebugMsg(scip, "fixing led to cutoff\n");

                     return SCIP_OKAY;
                  }

                  assert(fixed);
                  ++(*nfixedvars);

                  /* the above fixing is equal to the fixation of varstostay[v] to 1, so we can call presolvePropagateCons() for consstay */
                  SCIP_CALL( presolvePropagateCons(scip, constostay, FALSE, NULL, NULL, NULL, NULL, nfixedvars, naggrvars, ndelconss, cutoff) );

                  return SCIP_OKAY;
               }
               else
               {
                  /* correct local data structure, remove variable from constraint entry where it will be removed */
                  deleteCliqueDataEntry(varstochange[v1], constochangeidx, vartoindex, varnconss, varconsidxs);

                  SCIPdebugMsg(scip, " -> deleting variable <%s> in constraint <%s> number %d, because it will be replaced\n", SCIPvarGetName(varstochange[v1]), SCIPconsGetName(constochange), constochangeidx);
                  /* delete overlapping variables in constochange */
                  SCIP_CALL( delCoefPos(scip, constochange, v1) );
                  ++(*nchgcoefs);
               }

               --v;
               --v1;
            }
         }
         assert(addvar != NULL || v >= 0);
         /* we should have removed exactly countofoverlapping[c] variables from the constochange */
         assert(*nchgcoefs - oldnchgcoefs == countofoverlapping[c]);

         /* determine addvar if not yet found */
         if( addvar == NULL )
         {
            for( ; v >= 0; --v)
            {
               if( SCIPvarGetLbLocal(varstostay[v]) > 0.5 || SCIPvarGetUbLocal(varstostay[v]) < 0.5 )
                  continue;

               /* all variables inside the first clique constraint should be either active or negated of an active one */
               assert(SCIPvarIsActive(varstostay[v]) || (SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v]))));

               addvar = varstostay[v];
               break;
            }
         }
         assert(addvar != NULL);

         /* get representative variable for all deleted variables */
         SCIP_CALL( SCIPgetNegatedVar(scip, addvar, &addvar) );
         assert(addvar != NULL);

         SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(addvar), SCIPconsGetName(constochange), constochangeidx);
         /* add representative for overlapping instead */
         SCIP_CALL( addCoef(scip, constochange, addvar) );
         ++(*nchgcoefs);

         /* constraint should be still merged because this added variable is new in this constraint */
         consdatachange->merged = TRUE;
         assert(constochangeidx == (cons == constochange ? considx : c));

         /* correct local data structure, add constraint entry to variable data  */
         SCIP_CALL( addCliqueDataEntry(scip, addvar, constochangeidx, TRUE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );

         /* cons changed so much, that it cannot be used for more overlapping checks */
         if( *chgcons )
            return SCIP_OKAY;
      }
   }

   return SCIP_OKAY;
}

/** try to lift variables to given constraint */
/** @todo try another variant by determine lifting variables as the intersection of all cliques variables of the
 *        constraint variables, note that the intersection changes after one variable was added
 */
static
SCIP_RETCODE liftCliqueVariables(
   SCIP*const            scip,               /**< SCIP data structure */
   SCIP_CONS*const       cons,               /**< constraint which may overlap */
   int const             arraypos,           /**< position of constraint in global array */
   SCIP_VAR**const       usefulvars,         /**< possible variables to lift */
   int*const             nusefulvars,        /**< pointer to store number of added variables */
   int const             endidx,             /**< end index for possible lifting variables */
   SCIP_Bool**           cliquevalues,       /**< pointer to clique values of constraint-variables, either one if the
                                              *   variable is active or zero if the variable is negated
                                              *   @note this array can be resized in this method
                                              */
   SCIP_HASHMAP*const    vartoindex,         /**< hashmap mapping variables to indices */
   int*const             varnconss,          /**< array with number of constraints a variable occurs */
   int*const             maxnvarconsidx,     /**< array with the maximal number of occurrences of a variable */
   int**const            varconsidxs,        /**< array with constraint indices in which the corresponding variable
                                              *   exists
                                              */
   int*const             maxnvars,           /**< pointer to store maximal number of variables of a constraint */
   int*const             nadded,             /**< pointer to store number of possible added variables */
   SCIP_Bool*const       chgcons,            /**< pointer to store if the constraint was changed, due to added
                                              *   variables
                                              */
   int*const             nfixedvars,         /**< pointer to count number of deleted variables */
   int*const             ndelconss,          /**< pointer to count number of deleted constraints */
   SCIP_Bool*const       cutoff              /**< pointer to store if the problem is infeasible due to a fixing */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR** vars;
   SCIP_VAR* var;
   SCIP_VAR* var1;
   SCIP_Bool fixed;
   SCIP_Bool value;
   int nvars;
   int nottocheck; /* will be the position for a variable in cons0 which is in negated form in the same clique */
   int v;
   int v1;
   int k;

   assert(scip != NULL);
   assert(cons != NULL);
   assert(usefulvars != NULL);
   assert(cliquevalues != NULL);
   assert(*cliquevalues != NULL);
   assert(vartoindex != NULL);
   assert(varnconss != NULL);
   assert(maxnvarconsidx != NULL);
   assert(varconsidxs != NULL);
   assert(maxnvars != NULL);
   assert(nadded != NULL);
   assert(chgcons != NULL);
   assert(nfixedvars != NULL);
   assert(ndelconss != NULL);
   assert(cutoff != NULL);

   if( !SCIPconsIsActive(cons) )
      return SCIP_OKAY;

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

   nvars = consdata->nvars;

   if( nvars == 0 )
      return SCIP_OKAY;

   assert(nvars <= *maxnvars);

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

   v1 = endidx;

   /* now we try to add variables with index prior to endidx to cons */
   for( v = nvars - 1; v >= 0 && v1 >= 0; )
   {
      if( SCIPvarGetLbLocal(usefulvars[v1]) > 0.5 || SCIPvarGetUbLocal(usefulvars[v1]) < 0.5 )
      {
         --v1;
         continue;
      }
      if( SCIPvarGetUbLocal(vars[v]) < 0.5 )
      {
         --v;
         continue;
      }

      /* check that constraint variables are still correctly sorted, indices of active variables should be decreasing */
      assert(v == 0 || SCIPvarCompareActiveAndNegated(vars[v], vars[v - 1]) <= 0);

      /* there should no variables fixed to one occur in our constraint */
      assert(SCIPvarGetLbLocal(vars[v]) < 0.5 && SCIPvarGetUbLocal(vars[v]) > 0.5);
      assert(SCIPvarGetLbLocal(usefulvars[v1]) < 0.5 && SCIPvarGetUbLocal(usefulvars[v1]) > 0.5);

      /* all variables which we have inside the clique constraint and which can possibly be added should be either active or negated */
      assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
      assert(SCIPvarIsActive(usefulvars[v1]) || (SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1]))));

      /* constraint should during adding of variables stay merged, because for each variable which is added holds that
       * the index of this corresponding active variable is pairwise different to all indices of all active
       * corresponding variables inside the constraint
       * @note it should not happen that we add one variable and the corresponding counterpart to the same constraint */
      assert(consdata->merged);

      /* get active variable and clique value in cons */
      if( (*cliquevalues)[v] )
         var = vars[v];
      else
      {
         assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v])));
         var = SCIPvarGetNegationVar(vars[v]);
      }

      /* get active variable and clique value of next variable */
      if( SCIPvarIsActive(usefulvars[v1]) )
      {
         var1 = usefulvars[v1];
         value = TRUE;
      }
      else
      {
         assert(SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1])));
         var1 = SCIPvarGetNegationVar(usefulvars[v1]);
         value = FALSE;
      }

      nottocheck = -1;
      k = 0;

      /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
      if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1)  )
      {
         --v;
         continue;
      }
      /* variable index in the constraint is greater than the other one, so check for possible inclusion of the variable */
      else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1)  )
      {
         assert(consdata == SCIPconsGetData(cons));

         /* check if every variable in the actual clique is in clique with the new variable */
         for( k = nvars - 1; k >= 0; --k )
         {
            if( SCIPvarGetUbLocal(vars[k]) > 0.5 )
            {
               /* there should no variables fixed to one occur in our constraint */
               assert(SCIPvarGetLbLocal(vars[k]) < 0.5);
               assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));

               if( (*cliquevalues)[k] )
               {
                  assert(SCIPvarIsActive(vars[k]));
                  var = vars[k];
               }
               else
               {
                  assert(SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k])));
                  var = SCIPvarGetNegationVar(vars[k]);
               }
               if( !SCIPhaveVarsCommonClique(scip, var1, value, var, (*cliquevalues)[k], TRUE) )
                  break;
            }
         }
         --v1;
      }
      /* variable index in the constraint is equal to the index of the other variable, check if these variables are
       * negated of each other so memorize the position and check for possible inclusion of the new variable and if
       * possible decrease indices
       */
      else
      {
         /* one clique contains the negated and the other clique the corresponding active var */
         if( value != (*cliquevalues)[v] )
         {
            nottocheck = v;

            assert(consdata == SCIPconsGetData(cons));
            assert(nvars <= consdata->nvars);

            /* check if every variable in the actual clique is in clique with the new variable */
            for( k = nvars - 1; k >= 0; --k )
            {
               if( SCIPvarGetUbLocal(vars[k]) > 0.5 )
               {
                  /* there should no variables fixed to one occur in our constraint */
                  assert(SCIPvarGetLbLocal(vars[k]) < 0.5);

                  assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));

                  if( k == nottocheck )
                     continue;

                  if( (*cliquevalues)[k] )
                  {
                     assert(SCIPvarIsActive(vars[k]));
                     var = vars[k];
                  }
                  else
                  {
                     assert(SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k])));
                     var = SCIPvarGetNegationVar(vars[k]);
                  }

                  if( !SCIPhaveVarsCommonClique(scip, var1, value, var, (*cliquevalues)[k], TRUE) )
                     break;
               }
            }
         }
         /* don't decrease v because it might happen that the corresponding negated variable of var is next in
          * usefulvars
          */
         --v1;
      }

      /* if k is smaller than 0 than the possible new variables is in the same clique with all variables of cons,
       * so we add the new variable to clique constraint or fix some variables */
      if( k < 0 )
      {
         ++(*nadded);

         /* we found a variable which is the negated variable of another one in this clique so we can fix all
          * other variable to zero and if it's a partitioning constraint we can also fix the variable of the
          * negated to one and we can delete the constraint too */
         if( nottocheck >= 0 )
         {
            assert(consdata == SCIPconsGetData(cons));
            assert(nvars <= consdata->nvars);
            assert(consdata->merged);

            /* process all vars for possible fixing */
            for( k = consdata->nvars - 1; k >= 0; --k )
            {
               if( SCIPvarGetUbLocal(vars[k]) > 0.5 )
               {
                  /* there should no variables fixed to one occur in our constraint */
                  assert(SCIPvarGetLbLocal(vars[v]) < 0.5);

                  assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));

                  if( k != nottocheck )
                  {
                     SCIPdebugMsg(scip, "trying to fix <%s> to 0 because we could lift a negated variable of another constraint variable\n", SCIPvarGetName(vars[k]));
                     /* fix variable to zero */
                     SCIP_CALL( SCIPfixVar(scip, vars[k], 0.0, cutoff, &fixed) );

                     if( *cutoff )
                     {
                        SCIPdebugMsg(scip, "fixing led to cutoff\n");

                        return SCIP_OKAY;
                     }

                     assert(fixed);

                     ++(*nfixedvars);
                  }
               }
            }
            if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
            {
               assert(SCIPvarIsActive(vars[nottocheck]) || (SCIPvarGetStatus(vars[nottocheck]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[nottocheck]))));

               SCIPdebugMsg(scip, "trying to fix <%s> to 1 due to this setpartitioning variable is with its negated in the same clique\n", SCIPvarGetName(vars[nottocheck]));
               /* fix the remaining variable to one, due to it's the only one left to satisfy the constraint */
               SCIP_CALL( SCIPfixVar(scip, vars[nottocheck], 1.0, cutoff, &fixed) );
               if( *cutoff )
               {
                  SCIPdebugMsg(scip, "fixing led to cutoff\n");

                  return SCIP_OKAY;
               }

               assert(fixed);
               ++(*nfixedvars);
            }

            /* delete constraint */
            SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to active and negated variable in the same clique constraint\n", SCIPconsGetName(cons), arraypos);
            assert(SCIPconsIsActive(cons));
            SCIP_CALL( SCIPdelCons(scip, cons) );
            ++(*ndelconss);

            break;
         }
         /* we found a variable which could be added to a partitioning constraint so we can fix it to zero */
         else if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
         {
            SCIPdebugMsg(scip, "trying to fix <%s> to 0 because this variable is in the same clique with a set partition\n", SCIPvarGetName(usefulvars[v1 + 1]));
            /* fix variable to zero */
            SCIP_CALL( SCIPfixVar(scip, usefulvars[v1 + 1], 0.0, cutoff, &fixed) );

            if( *cutoff )
            {
               SCIPdebugMsg(scip, "fixing led to cutoff\n");

               return SCIP_OKAY;
            }

            assert(fixed);

            ++(*nfixedvars);
         }
         /* we have found a new variable for a set packing constraint cons, so add the found variable to the first constraint */
         else
         {
            SCIP_VAR* addvar;

            assert(SCIPconsIsActive(cons));

            addvar = usefulvars[v1 + 1];

            assert(SCIPvarGetLbLocal(addvar) < 0.5 && SCIPvarGetUbLocal(addvar) > 0.5);

            /* add representative instead */
            SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(usefulvars[v1 + 1]), SCIPconsGetName(cons), arraypos);
            SCIP_CALL( addCoef(scip, cons, addvar) );
            assert(consdata == SCIPconsGetData(cons));
            /* we know that this constraint stays merged but later on we have to resort */
            consdata->merged = TRUE;

            /* second we add the constraint index to the list of indices where this variable occurs */
            assert(SCIPhashmapExists(vartoindex, (void*) addvar));

            /* correct local data structure, add constraint entry to variable data  */
            SCIP_CALL( addCliqueDataEntry(scip, addvar, arraypos, FALSE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );

            /* we need the new pointer to the variables, because due to adding variables it is possible that we
             * did reallocate the variables array inside the constraint, the index v should stay the same because the
             * added variable was inserted at the end and we are decreasing v in our for loop
             */
            vars = consdata->vars;
            nvars = consdata->nvars;

            /* we need to update our data structure */

            /* resize clique array if necessary, due to adding variables */
            if( (*maxnvars) < nvars )
            {
               while( (*maxnvars) < nvars )
                  (*maxnvars) *= 2 ;
               SCIP_CALL( SCIPreallocBufferArray(scip, cliquevalues, (*maxnvars)) );
            }
            (*cliquevalues)[nvars - 1] = SCIPvarIsActive(addvar) ? TRUE : FALSE;

            (*chgcons) = TRUE;
         }
      }
   }

   if( !SCIPconsIsActive(cons) )
      return SCIP_OKAY;

   /* maybe we stopped because of cons(v reached -1) so try to add rest in usefulvars */
   for( ; v1 >= 0; --v1)
   {
      if( SCIPvarGetLbLocal(usefulvars[v1]) > 0.5 || SCIPvarGetUbLocal(usefulvars[v1]) < 0.5 )
         continue;

      /* get active variable and clique value */
      if( SCIPvarIsActive(usefulvars[v1]) )
      {
         var1 = usefulvars[v1];
         value = TRUE;
      }
      else
      {
         assert(SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1])));
         var1 = SCIPvarGetNegationVar(usefulvars[v1]);
         value = FALSE;
      }

      assert(consdata == SCIPconsGetData(cons));
      assert(nvars <= consdata->nvars);

      /* check if every variable in the actual clique is in clique with the new variable */
      for( k = nvars - 1; k >= 0; --k )
      {
         if( SCIPvarGetUbLocal(vars[k]) > 0.5 )
         {
            /* there should no variables fixed to one occur in our constraint */
            assert(SCIPvarGetLbLocal(vars[k]) < 0.5);

            assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));

            if( (*cliquevalues)[k] )
            {
               assert(SCIPvarIsActive(vars[k]));
               var = vars[k];
            }
            else
            {
               assert(SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k])));
               var = SCIPvarGetNegationVar(vars[k]);
            }

            if( !SCIPvarsHaveCommonClique(var1, value, var, (*cliquevalues)[k], TRUE) )
               break;
         }
      }

      /* add new variable to clique constraint or fix some variables */
      if( k < 0 )
      {
         /* we found a variable which could be added to a partitioning constraint so we can fix it to zero */
         if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
         {
            SCIPdebugMsg(scip, "trying to fix <%s> to 0 because this variable is in the same clique with a set partition\n", SCIPvarGetName(usefulvars[v1]));

            /* fix variable to zero */
            SCIP_CALL( SCIPfixVar(scip, usefulvars[v1], 0.0, cutoff, &fixed) );
            if( *cutoff )
            {
               SCIPdebugMsg(scip, "fixing led to cutoff\n");

               return SCIP_OKAY;
            }
            assert(fixed);

            ++(*nfixedvars);
            ++(*nadded);
         }
         /* add the found variable to the first constraint */
         else
         {
            SCIP_VAR* addvar;

            assert(SCIPconsIsActive(cons));

            addvar = usefulvars[v1];

            assert(SCIPvarGetLbLocal(addvar) < 0.5 && SCIPvarGetUbLocal(addvar) > 0.5);

            /* add representative instead */
            SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(addvar), SCIPconsGetName(cons), arraypos);
            SCIP_CALL( addCoef(scip, cons, addvar) );
            assert(consdata == SCIPconsGetData(cons));
            /* we know that this constraint stays merged but later on we have to resort */
            consdata->merged = TRUE;

            /* second we add the constraint index to the list of indices where this variable occurs */
            assert(SCIPhashmapExists(vartoindex, (void*) addvar));

            /* correct local data structure, add constraint entry to variable data  */
            SCIP_CALL( addCliqueDataEntry(scip, addvar, arraypos, FALSE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );

            /* we need the new pointer to the variables, because due to adding variables it is possible that we
             * did reallocate the variables array inside the constraint, the index v should stay the same because the
             * added variable was inserted at the end and we are decreasing v in our for loop
             */
            vars = consdata->vars;
            nvars = consdata->nvars;

            /* we need to update our data structure */

            /* resize clique array if necessary, due to adding variables */
            if( (*maxnvars) < nvars )
            {
               while( (*maxnvars) < nvars )
                  (*maxnvars) *= 2 ;
               SCIP_CALL( SCIPreallocBufferArray(scip, cliquevalues, (*maxnvars)) );
            }
            (*cliquevalues)[nvars - 1] = SCIPvarIsActive(addvar) ? TRUE : FALSE;

            ++(*nadded);
            (*chgcons) = TRUE;
         }
      }
   }

   return SCIP_OKAY;
}

/** perform all collected aggregations */
static
SCIP_RETCODE performAggregations(
   SCIP*const            scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   SCIP_VAR**const       undoneaggrvars,     /**< aggregation variables storage */
   SCIP_Bool*const       undoneaggrtypes,    /**< aggregation type storage, type FALSE means the aggregation is of the
                                              *   form x + y = 1; type TRUE means the aggregation is of the form x = y;
                                              */
   int const             naggregations,      /**< number of aggregations to performed */
   int*const             naggrvars,          /**< pointer to count number of aggregated variables */
   SCIP_Bool*const       cutoff              /**< pointer to store if the problem is infeasible due to a fixing */
   )
{  /*lint --e{715}*/
   SCIP_VAR* var1;
   SCIP_VAR* var2;
   SCIP_Bool aggregated;
   SCIP_Bool redundant;
   int a;

   assert(scip != NULL);
   assert(conshdlrdata != NULL);
   assert(undoneaggrvars != NULL);
   assert(undoneaggrtypes != NULL);
   assert(naggregations > 0);
   assert(naggrvars != NULL);
   assert(cutoff != NULL);

   /* loop over all open aggregations and try to aggregate them */
   for( a = 0; a < naggregations; ++a  )
   {
      var1 = undoneaggrvars[2 * a];
      var2 = undoneaggrvars[2 * a + 1];
      assert(var1 != NULL);
      assert(var2 != NULL);

      SCIPdebugMsg(scip, "trying to aggregate <%s> %s <%s>%s\n", SCIPvarGetName(var1), undoneaggrtypes[a] ? "=" : "+", SCIPvarGetName(var2), undoneaggrtypes[a] ? "" : " = 1");

#ifdef VARUSES
      /* in order to not mess up the variable usage counting, we have to decrease usage counting, aggregate,
       * and increase usage counting again
       */
      SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, var1) );
      SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, var2) );
#endif

      /* aggregate last remaining variables in the set partitioning constraint */
      if( undoneaggrtypes[a] )
      {
         SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, -1.0, 0.0, cutoff, &redundant, &aggregated) );
      }
      else
      {
         SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, 1.0, 1.0, cutoff, &redundant, &aggregated) );
      }

      if( *cutoff )
      {
         SCIPdebugMsg(scip, "aggregation was infeasible\n");

         return SCIP_OKAY;
      }
      /* binary variables should always be aggregated, or due to fixation the aggregation is redundant */
      assert(redundant);

      if( aggregated )
         ++(*naggrvars);

#ifdef VARUSES
      /* increase variable usage counting again */
      SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, var1) );
      SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, var2) );
#endif
   }

   return SCIP_OKAY;
}

/** check whether we can combine or grow cliques so some constraints become redundant or we can fix variables */
/** @todo try another variant, by building up the clique graph and delete unnecessary (transitive closure) edges and do
 *        a bfs search to search for common ancestors to get all possible lifting variables
 */
static
SCIP_RETCODE preprocessCliques(
   SCIP*const            scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   SCIP_CONS**const      conss,              /**< constraint set */
   int const             nconss,             /**< number of constraints in constraint set */
   int const             nrounds,            /**< actual presolving round */
   int*const             firstchange,        /**< pointer to store first changed constraint */
   int*const             firstclique,        /**< pointer to store first constraint to start adding clique again */
   int*const             lastclique,         /**< pointer to store last constraint to add cliques again */
   int*const             nfixedvars,         /**< pointer to count number of deleted variables */
   int*const             naggrvars,          /**< pointer to count number of aggregated variables */
   int*const             ndelconss,          /**< pointer to count number of deleted constraints */
   int*const             nchgcoefs,          /**< pointer to count number of deleted coefficients */
   SCIP_Bool*const       cutoff              /**< pointer to store if the problem is infeasible due to a fixing */
   )
{
   /* extend cliques/constraints by checking whether some variables are in the same clique, no pairwise clique lifting
    * which would be slower
    */
   SCIP_CONS** usefulconss;                  /* array with pointers of constraint of setpartitioning and setpacking type */
   SCIP_VAR** usefulvars;                    /* array with pointers of variables in setpartitioning and setpacking constraints */
   int** varconsidxs;                        /* array consisting of constraint indices in which the corresponding variable exists */
   int* varnconss;                           /* array consisting of number of constraints the variable occurs */
   int* maxnvarconsidx;                      /* maximal number of occurrences of a variable */
   int* countofoverlapping = NULL;           /* the amount of variables which are in another constraint */
   SCIP_Bool* cliquevalues = NULL;           /* values of clique-variables, either one if the variable is active or zero if the variable is negated */

   SCIP_HASHMAP* vartoindex;                 /* mapping of SCIP variables to indices */
   SCIP_CONSDATA* consdata;

   SCIP_Bool chgcons0;
   int nvars;
   int c;
   int v;
   int nusefulconss;
   int nusefulvars;
   int susefulvars;
   int maxnvars;
   int varindex;

   SCIP_VAR** undoneaggrvars;                /* storage for not yet performed aggregations */
   SCIP_Bool* undoneaggrtypes;               /* storage for not yet performed aggregation type (x = y or x + y = 1) */
   int saggregations;
   int naggregations;

   assert(scip != NULL);
   assert(conshdlrdata != NULL);
   assert(conss != NULL || nconss == 0);
   assert(firstchange != NULL);
   assert(firstclique != NULL);
   assert(lastclique != NULL);
   assert(nfixedvars != NULL);
   assert(naggrvars != NULL);
   assert(ndelconss != NULL);
   assert(nchgcoefs != NULL);
   assert(cutoff != NULL);

   *cutoff = FALSE;

   if( nconss == 0 )
      return SCIP_OKAY;

   nvars = SCIPgetNVars(scip);

   if( nvars == 0 )
      return SCIP_OKAY;

   susefulvars = 2 * nvars; /* two times because of negated vars, maybe due to deleted variables we need to increase this */

   /* a hashmap from varindex to postion in varconsidxs array, because above is still too small */
   SCIP_CALL( SCIPhashmapCreate(&vartoindex, SCIPblkmem(scip), nvars) );

   /* get temporary memory for the aggregation storage, to memorize aggregations which will be performed later, otherwise we would destroy our local data structures */
   saggregations = nvars;
   SCIP_CALL( SCIPallocBufferArray(scip, &undoneaggrvars, 2 * saggregations) );
   SCIP_CALL( SCIPallocBufferArray(scip, &undoneaggrtypes, saggregations) );
   BMSclearMemoryArray(undoneaggrtypes, saggregations);
   naggregations = 0;

   /* get temporary memory for all clique constraints, all appearing variables and the mapping from variables to constraints */
   SCIP_CALL( SCIPallocBufferArray(scip, &usefulconss, nconss) );
   SCIP_CALL( SCIPallocBufferArray(scip, &usefulvars, susefulvars) );
   BMSclearMemoryArray(usefulvars, susefulvars);
   SCIP_CALL( SCIPallocBufferArray(scip, &varnconss, susefulvars + 1) );
   BMSclearMemoryArray(varnconss, susefulvars + 1);
   SCIP_CALL( SCIPallocBufferArray(scip, &maxnvarconsidx, susefulvars + 1) );
   SCIP_CALL( SCIPallocBufferArray(scip, &varconsidxs, susefulvars + 1) );
   BMSclearMemoryArray(varconsidxs, susefulvars + 1);
   nusefulvars = 0;
   nusefulconss = 0;
   maxnvars = 0;

   /* @todo: check for round limit for adding extra clique constraints */
   /* adding clique constraints which arises from global clique information */
   if( conshdlrdata->nclqpresolve == 0 && conshdlrdata->addvariablesascliques )
   {
      SCIP_VAR** vars = SCIPgetVars(scip);
      SCIP_VAR** binvars;
      int* cliquepartition;
      int ncliques;
      int nbinvars;
      int naddconss;

      nbinvars = SCIPgetNBinVars(scip);
      SCIP_CALL( SCIPduplicateBufferArray(scip, &binvars, vars, nbinvars) );
      SCIP_CALL( SCIPallocBufferArray(scip, &cliquepartition, nbinvars) );

      /* @todo: check for better permutations/don't permute the first round
       * @todo: take binary variables which are not of vartype SCIP_VARTYPE_BINARY into account
       */
      SCIPrandomPermuteArray(conshdlrdata->randnumgen, (void**)binvars, 0, nbinvars);

      /* try to create a clique-partition over all binary variables and create these cliques as new setppc constraints
       * and add them to the usefulconss array and adjust all necessary data this will hopefully lead to faster
       * detection of redundant constraints
       */
      SCIP_CALL( SCIPcalcCliquePartition(scip, binvars, nbinvars, cliquepartition, &ncliques) );

      /* resize usefulconss array if necessary */
      SCIP_CALL( SCIPreallocBufferArray(scip, &usefulconss, nconss + ncliques) );

      naddconss = 0;

      /* add extra clique constraints resulting from the cliquepartition calculation to SCIP and to the local data structure */
      SCIP_CALL( addExtraCliques(scip, binvars, nbinvars, cliquepartition, ncliques, usefulconss, &nusefulconss,
            nrounds, nfixedvars, &naddconss, ndelconss, nchgcoefs, cutoff) );

      /* bad hack, we don't want to count these artificial created constraints if they got deleted, so ndelconss
       * can become negative which will be change to zero at the end of this method if it's still negative
       */
      *ndelconss -= naddconss;

      SCIPfreeBufferArray(scip, &cliquepartition);
      SCIPfreeBufferArray(scip, &binvars);

      if( *cutoff )
         goto TERMINATE;
   }

   /* start to collect setpartitioning and setpacking constraints, and try to remove fixed variables and merged these
    * constraints
    */
   SCIP_CALL( collectCliqueConss(scip, conss, nconss, usefulconss, &nusefulconss, nfixedvars, ndelconss, nchgcoefs, cutoff) );
   /* @Note: Even after the call above some constraints can have fixed variables, because it might happen that caused by
    * mergeMultiplies some variables were fixed which occurred already in previous constraints
    */
   if( *cutoff )
      goto TERMINATE;

   /* no usefulconss found */
   if( nusefulconss <= 1 )
      goto TERMINATE;

   /* @todo: maybe sort them after biggest indices too, or another variant would be to restore the order as they were
    *        read in
    */
   /* sort constraints first after type (partitioning before packing) and second after number of variables such that the
    * partitioning constraints have increasing number of variables and the packing constraints have decreasing number of
    * variables, because we loop from back to front we sort them downwards, so they are the other way around
    */
   SCIPsortDownPtr((void**)usefulconss, setppcConssSort, nusefulconss);

   /* creating all necessary data in array structure, collect all clique constraint variables and occurrences */
   SCIP_CALL( collectCliqueData(scip, usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs, &maxnvars) );
   assert(maxnvars > 0);

   /* allocate temporary memory for actual clique */
   SCIP_CALL( SCIPallocBufferArray(scip, &cliquevalues, maxnvars) );
   /* allocate temporary memory for counting an overlap of variables */
   SCIP_CALL( SCIPallocBufferArray(scip, &countofoverlapping, nusefulconss) );

   /* sort usefulvars after indices of variables, negated and active counterparts will stand side by side */
   SCIPsortDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, nusefulvars);

   /* extend cliques/constraints by checking whether some variables of a second constraint are in the same clique */
   for( c = nusefulconss - 1; c >= 0 && !SCIPisStopped(scip); --c )
   {
      SCIP_VAR** cons0vars;                  /* these are the clique variables */
      SCIP_CONS* cons0;
      int ncons0vars;
      SCIP_VAR* var0;
      int v1;
      int nadded;     /* number of possible added variables to constraint */
      int cons0fixedzeros;
      int oldnchgcoefs;
#ifndef NDEBUG
      const int oldnaggrvars = *naggrvars;
#endif
      cons0 = usefulconss[c];

      if( !SCIPconsIsActive(cons0) )
         continue;

      /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
       * possible
       */
      SCIP_CALL( presolvePropagateCons(scip, cons0, FALSE, undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );

      if( *cutoff )
         break;

      /* we can't handle aggregated variables later on so we should have saved them for later */
      assert(*naggrvars == oldnaggrvars);

      if( !SCIPconsIsActive(cons0) )
         continue;

      /* we need to determine the cliquedata in each iteration because we eventual will change it later */
      consdata = SCIPconsGetData(cons0);
      assert(consdata != NULL);

      cons0vars = consdata->vars;
      ncons0vars = consdata->nvars;

      /* sorting array after indices of variables, negated and active counterparts will stand side by side */
      SCIPsortDownPtr((void**)cons0vars, SCIPvarCompActiveAndNegated, ncons0vars);
      /* standard setppc-sorting now lost */
      consdata->sorted = FALSE;

      /* clique array should be long enough */
      assert(maxnvars >= ncons0vars);

      /* clear old entries in overlapping constraint */
      BMSclearMemoryArray(countofoverlapping, nusefulconss);

      /* calculate overlapping */
      for( v = ncons0vars - 1; v >= 0 ; --v )
      {
         var0 = cons0vars[v];

         /* fixed variables later to the count */
         if( SCIPvarGetLbLocal(var0) > 0.5 || SCIPvarGetUbLocal(var0) < 0.5 )
            continue;

         assert(SCIPhashmapExists(vartoindex, (void*) var0));

         varindex = SCIPhashmapGetImageInt(vartoindex, (void*) var0);
         for( v1 = varnconss[varindex] - 1; v1 >= 0 ; --v1 )
            ++(countofoverlapping[varconsidxs[varindex][v1]]);
      }

      oldnchgcoefs = *nchgcoefs;
      cons0fixedzeros = consdata->nfixedzeros;

      chgcons0 = FALSE;

      /* check for overlapping constraint before starting lifting */
      SCIP_CALL( checkForOverlapping(scip, cons0, c, c, usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex,
            varnconss, maxnvarconsidx, varconsidxs, countofoverlapping, conshdlrdata->cliqueshrinking, &chgcons0,
            undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations,
            nfixedvars, naggrvars, nchgcoefs, ndelconss, cutoff) );

      if( *cutoff )
         break;

      /* we can't handle aggregated variables later on so we should have saved them for later */
      assert(*naggrvars == oldnaggrvars);

      /* if cons0 changed, we need to reorder the variables  */
      if( chgcons0 && *nchgcoefs > oldnchgcoefs )
      {
         consdata = SCIPconsGetData(cons0);
         assert(consdata != NULL);

         cons0vars = consdata->vars;
         ncons0vars = consdata->nvars;

         /* sorting array after indices of variables, negated and active counterparts will stand side by side */
         SCIPsortDownPtr((void**)cons0vars, SCIPvarCompActiveAndNegated, ncons0vars);
         /* standard setppc-sorting now lost */
         consdata->sorted = FALSE;
      }

      /* check cons0 again for redundancy/fixings, because due to fixings in all other constraints it might happen that cons0 is redundant now */
      if( consdata->nfixedones > 0 || consdata->nfixedzeros > cons0fixedzeros )
      {
         /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
          * possible
          */
         SCIP_CALL( presolvePropagateCons(scip, cons0, FALSE, undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );

         if( *cutoff )
            break;

         /* we can't handle aggregated variables later on so we should have saved them for later */
         assert(*naggrvars == oldnaggrvars);

         if( !SCIPconsIsActive(cons0) )
            continue;
      }

      nadded = 0;

      /* iterate over the cliques variables and all possible new clique variables at the "same" time, determine starting
       * index
       *
       * @note: it might be better to start the first round with our computed v1, but maybe it's better to switch to
       *        trying to add all variables the second time for set packing constraints
       */

      /* we try to add all variables to the partitioning constraints, to try to fix as much as possible */
      if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
         v1 = nusefulvars - 1;
      else
      {
         /* if we already ran a presolving round we want to try to add new variables */
         if( conshdlrdata->nclqpresolve > 0 )
            v1 = nusefulvars - 1;
         else
         {
            /* find start position of variable which we will try to add to our constraint, so we will get better clique constraints */
            (void) SCIPsortedvecFindDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, (void*)cons0vars[ncons0vars - 1], nusefulvars, &v1);
            assert(v1 >= 0 && v1 < nusefulvars);
            /* if constraint is not merged and we found a variable which is negated the same as it's neighbour we have to
             * increase v1 to make sure that we don't loose this important variable */
            if( v1 + 1 < nusefulvars && ((SCIPvarIsNegated(usefulvars[v1 + 1]) && SCIPvarGetNegatedVar(usefulvars[v1 + 1]) == usefulvars[v1]) || (SCIPvarIsNegated(usefulvars[v1]) && SCIPvarGetNegatedVar(usefulvars[v1]) == usefulvars[v1 + 1])) )
               ++v1;
         }
      }

      assert(maxnvars >= ncons0vars);
      /* initialize the cliquevalues array */
      for( v = ncons0vars - 1; v >= 0; --v )
      {
         if( SCIPvarGetLbLocal(cons0vars[v]) < 0.5 && SCIPvarGetUbLocal(cons0vars[v]) > 0.5 )
         {
            /* variable has to be either active or a negated variable of an active one */
            assert(SCIPvarIsActive(cons0vars[v]) || (SCIPvarGetStatus(cons0vars[v]) == SCIP_VARSTATUS_NEGATED &&
                  SCIPvarIsActive(SCIPvarGetNegationVar(cons0vars[v]))));
            cliquevalues[v] = SCIPvarIsActive(cons0vars[v]) ? TRUE : FALSE;
         }
      }

      chgcons0 = FALSE;

      /* try to lift variables to cons0 */
      SCIP_CALL( liftCliqueVariables(scip, cons0, c, usefulvars, &nusefulvars, v1, &cliquevalues, vartoindex, varnconss,
            maxnvarconsidx, varconsidxs, &maxnvars, &nadded, &chgcons0, nfixedvars, ndelconss, cutoff) );

      if( *cutoff )
         break;

      if( !SCIPconsIsActive(cons0) )
         continue;

      /* check for redundant constraints due to changing cons0 */
      if( chgcons0 )
      {
         int i;

         *firstchange = MIN(*firstchange, c);
         *firstclique = MIN(*firstclique, c);
         *lastclique = MAX(*lastclique, c);

         /* variables array has changed due to lifting variables, so get new values */
         assert(consdata == SCIPconsGetData(cons0));
         cons0vars = consdata->vars;
         ncons0vars = consdata->nvars;

         /* resorting array, because we added new variables, in order of indices of variables, negated
          * and active counterparts would stand side by side
          */
         SCIPsortDownPtr((void**)cons0vars, SCIPvarCompActiveAndNegated, ncons0vars);
         /* standard setppc-sorting now lost */
         consdata->sorted = FALSE;

         /* clear old entries in overlapping constraint */
         BMSclearMemoryArray(countofoverlapping, nusefulconss);

         for( v = ncons0vars - 1; v >= 0 ; --v )
         {
            var0 = cons0vars[v];

            /* fixed variables later to the count */
            if( SCIPvarGetLbLocal(var0) > 0.5 || SCIPvarGetUbLocal(var0) < 0.5 )
               continue;

            assert(SCIPhashmapExists(vartoindex, (void*) var0));

            varindex = SCIPhashmapGetImageInt(vartoindex, (void*) var0);
            for( i = varnconss[varindex] - 1; i >= 0 ; --i )
               ++(countofoverlapping[varconsidxs[varindex][i]]);
         }

         chgcons0 = FALSE;

         /* check for overlapping constraint after lifting, in the first round we will only check up front */
         SCIP_CALL( checkForOverlapping(scip, cons0, c, (conshdlrdata->nclqpresolve > 0) ? nusefulconss : c,
               usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs,
               countofoverlapping, conshdlrdata->cliqueshrinking, &chgcons0,
               undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations,
               nfixedvars, naggrvars, nchgcoefs, ndelconss, cutoff) );

         if( *cutoff )
            break;

         /* we can't handle aggregated variables later on so we should have saved them for later */
         assert(*naggrvars == oldnaggrvars);
      }
   }

 TERMINATE:
   SCIPfreeBufferArrayNull(scip, &countofoverlapping);
   SCIPfreeBufferArrayNull(scip, &cliquevalues);

   /* free temporary memory for constraints, variables and the mapping between them in reverse order as they were
    * allocated
    */
   for( c = nusefulvars; c > 0; --c )
   {
      if( varconsidxs[c] != NULL )
      {
         SCIPfreeBufferArrayNull(scip, &(varconsidxs[c]));
      }
   }

   SCIPfreeBufferArray(scip, &varconsidxs);
   SCIPfreeBufferArray(scip, &maxnvarconsidx);
   SCIPfreeBufferArray(scip, &varnconss);
   SCIPfreeBufferArray(scip, &usefulvars);
   SCIPfreeBufferArray(scip, &usefulconss);

   /* perform all collected aggregations */
   if( !*cutoff && naggregations > 0 && !SCIPdoNotAggr(scip) )
   {
      SCIP_CALL( performAggregations(scip, conshdlrdata, undoneaggrvars, undoneaggrtypes, naggregations, naggrvars, cutoff) );
   }

   /* free temporary memory for the aggregation storage */
   SCIPfreeBufferArray(scip, &undoneaggrtypes);
   SCIPfreeBufferArray(scip, &undoneaggrvars);

   /* free hashmap */
   SCIPhashmapFree(&vartoindex);

   if( *ndelconss < 0 )
      *ndelconss = 0;

   return SCIP_OKAY;
}


/** add cliques to SCIP */
static
SCIP_RETCODE addCliques(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS**           conss,              /**< constraint set */
   int                   nconss,             /**< number of constraints in constraint set */
   int                   firstclique,        /**< first constraint to start to add cliques */
   int                   lastclique,         /**< last constraint to start to add cliques */
   int*                  naddconss,          /**< pointer to count number of added constraints */
   int*                  ndelconss,          /**< pointer to count number of deleted constraints */
   int*                  nchgbds,            /**< pointer to count number of changed bounds */
   SCIP_Bool*            cutoff              /**< pointer to store if the problem is infeasible due to a fixing */
   )
{
   SCIP_CONS* cons;
   SCIP_CONSDATA* consdata;
   SCIP_Bool infeasible;
   int nlocalbdchgs;
   int c;

   assert(scip != NULL);
   assert(firstclique >= 0);
   assert(lastclique <= nconss);
   assert(conss != NULL || ((nconss == 0) && (lastclique == 0)));

   /* add clique and implication information */
   for( c = firstclique; c < lastclique; ++c )
   {
      cons = conss[c]; /*lint !e613*/
      assert(cons != NULL);

      /* ignore deleted constraints */
      if( !SCIPconsIsActive(cons) )
         continue;

      nlocalbdchgs = 0;
      SCIP_CALL( applyFixings(scip, cons, naddconss, ndelconss, &nlocalbdchgs, cutoff) );
      *nchgbds += nlocalbdchgs;

      if( *cutoff )
         return SCIP_OKAY;

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

      if( SCIPconsIsDeleted(cons) )
         continue;

      if( !consdata->cliqueadded && consdata->nvars >= 2 )
      {
         /* add a set partitioning / packing constraint as clique */
         if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING )
         {
            SCIP_CALL( SCIPaddClique(scip, consdata->vars, NULL, consdata->nvars,
                  ((SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING), &infeasible, &nlocalbdchgs) );
            *nchgbds += nlocalbdchgs;

            if( infeasible )
            {
               *cutoff = TRUE;
               return SCIP_OKAY;
            }
         }
         else if( consdata->nvars == 2 && !SCIPconsIsModifiable(cons) )
         {
            /* a two-variable set covering constraint x + y >= 1 yields the implication x == 0 -> y == 1 */
            SCIP_CALL( SCIPaddVarImplication(scip, consdata->vars[0], FALSE, consdata->vars[1],
                  SCIP_BOUNDTYPE_LOWER, 1.0, &infeasible, &nlocalbdchgs) );
            *nchgbds += nlocalbdchgs;

            if( infeasible )
            {
               *cutoff = TRUE;
               return SCIP_OKAY;
            }
         }
         consdata->cliqueadded = TRUE;
      }
   }

   return SCIP_OKAY;
}

/** perform multi-aggregation on variables resulting from a set-partitioning/-packing constraint */
static
SCIP_RETCODE multiAggregateBinvar(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_Bool             linearconshdlrexist,/**< does the linear constraint handler exist, necessary for multi-aggregations */
   SCIP_VAR**            vars,               /**< all variables including the variable to which will be multi-aggregated */
   int                   nvars,              /**< number of all variables */
   int                   pos,                /**< position of variable for multi-aggregation */
   SCIP_Bool*            infeasible,         /**< pointer to store infeasibility status of aggregation */
   SCIP_Bool*            aggregated          /**< pointer to store aggregation status */
   )
{
   SCIP_VAR** tmpvars;
   SCIP_Real* scalars;
   int v;

   assert(scip != NULL);
   assert(vars != NULL);
   assert(nvars > 1);
   assert(0 <= pos && pos < nvars);
   assert(infeasible != NULL);
   assert(aggregated != NULL);

   if( nvars == 2 )
   {
      SCIP_Bool redundant;

      /* perform aggregation on variables resulting from a set-packing constraint */
      SCIP_CALL( SCIPaggregateVars(scip, vars[pos], vars[nvars - pos - 1], 1.0, 1.0, 1.0, infeasible, &redundant, aggregated) );

      if( *aggregated )
         SCIPdebugMsg(scip, "aggregated %s = 1 - %s\n", SCIPvarGetName(vars[pos]), SCIPvarGetName(vars[nvars - pos - 1]));

      return SCIP_OKAY;
   }

   if( !linearconshdlrexist )
   {
      *infeasible = FALSE;
      return SCIP_OKAY;
   }

   /* if the last variable will be multi-aggregated, we do not need to copy the variables */
   if( pos == nvars - 1 )
      tmpvars = vars;
   else
   {
      /* copy variables for aggregation */
      SCIP_CALL( SCIPduplicateBufferArray(scip, &tmpvars, vars, nvars) );
      tmpvars[pos] = tmpvars[nvars - 1];
   }

   SCIP_CALL( SCIPallocBufferArray(scip, &scalars, nvars - 1) );
   /* initialize scalars */
   for( v = nvars - 2; v >= 0; --v )
      scalars[v] = -1.0;

   SCIPdebugMsg(scip, "multi-aggregating binary variable <%s> (locks: [%d,%d]; to %d variables)\n",
      SCIPvarGetName(vars[pos]), SCIPvarGetNLocksDownType(vars[pos], SCIP_LOCKTYPE_MODEL),
      SCIPvarGetNLocksUpType(vars[pos], SCIP_LOCKTYPE_MODEL), nvars - 1);

   /* perform multi-aggregation */
   SCIP_CALL( SCIPmultiaggregateVar(scip, vars[pos], nvars - 1, tmpvars, scalars, 1.0, infeasible, aggregated) );
   assert(!(*infeasible));

   SCIPfreeBufferArray(scip, &scalars);

   if( pos < nvars - 1 )
   {
      assert(tmpvars != vars);
      SCIPfreeBufferArray(scip, &tmpvars);
   }

   return SCIP_OKAY;
}

/** determine singleton variables in set-partitioning/-packing constraints, or doubleton variables (active and negated)
 *  in any combination of set-partitioning and set-packing constraints
 *
 *  we can multi-aggregate the variable and either change the set-partitioning constraint to a set-packing constraint or
 *  even delete it
 *
 *  1. c1: x + y + z = 1,  uplocks(x) = 1, downlocks(x) = 1               =>  x = 1 - y - z and change c1 to y + z <= 1
 *
 *  2. c2: x + y + z <= 1,  uplocks(x) = 1, downlocks(x) = 0, obj(x) < 0  =>  x = 1 - y - z and change c2 to y + z <= 1
 *
 *  3. d1: x + y + z <= 1 and d2: ~x + u + v <= 1, uplocks(x) = 1, downlocks(x) = 1
 *    a)  obj(x) <= 0                                                     =>  x = 1 - y - z and delete d1
 *    b)  obj(x) > 0                                                      => ~x = 1 - u - v and delete d2
 *
 *  4. e1: x + y + z == 1 and e2: ~x + u + v (<= or ==) 1, uplocks(x) = (1 or 2), downlocks(x) = 2
 *                                                                        =>  x = 1 - y - z and delete e1
 *
 *  we can also aggregate a variable in a set-packing constraint with only two variables when the uplocks are equal to
 *  one and then delete this constraint
 *
 *  5. f1: x + y <= 1,  uplocks(x) = 1, obj(x) <= 0                       =>  x = 1 - y and delete f1
 *
 *  @todo might want to multi-aggregate variables even with more locks, when the fill in is still smaller or equal to
 *        the old number of non-zeros, e.g.
 *
 *        x + y + z = 1
 *        ~x + u + v <=/= 1
 *        ~x + w <= 1
 */
static
SCIP_RETCODE removeDoubleAndSingletonsAndPerformDualpresolve(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS**           conss,              /**< constraint set */
   int                   nconss,             /**< number of constraints in constraint set */
   SCIP_Bool             dualpresolvingenabled,/**< is dual presolving enabled */
   SCIP_Bool             linearconshdlrexist,/**< does the linear constraint handler exist, necessary for
                                              *   multi-aggregations
                                              */
   int*                  nfixedvars,         /**< pointer to count number of deleted variables */
   int*                  naggrvars,          /**< pointer to count number of aggregated variables */
   int*                  ndelconss,          /**< pointer to count number of deleted constraints */
   int*                  nchgcoefs,          /**< pointer to count number of changed coefficients */
   int*                  nchgsides,          /**< pointer to count number of changed left hand sides */
   SCIP_Bool*            cutoff              /**< pointer to store if a cut off was detected */
   )
{
   SCIP_CONS** usefulconss;
   SCIP_VAR** binvars;
   SCIP_HASHMAP* vartoindex;
   SCIP_Bool* chgtype;
   int* considxs;
   int* posincons;
   SCIP_Bool infeasible;
   SCIP_Bool aggregated;
   SCIP_Bool donotaggr;
   SCIP_Bool donotmultaggr;
   SCIP_Bool mustcheck;
   SCIP_Bool addcut;
   int nposvars;
   int ndecs;
   int nbinvars;
   int nposbinvars;
   int nuplocks;
   int ndownlocks;
#ifndef NDEBUG
   int posreplacements = 0;
#endif
   int nhashmapentries;
   int nlocaladdconss;
   int v;
   int c;

   assert(scip != NULL);
   assert(conss != NULL);
   assert(nconss > 0);
   assert(nfixedvars != NULL);
   assert(naggrvars != NULL);
   assert(ndelconss != NULL);
   assert(nchgcoefs != NULL);
   assert(nchgsides != NULL);

   nbinvars = SCIPgetNBinVars(scip);
   nposbinvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
   assert(nbinvars + SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip) == nposbinvars);

   binvars = SCIPgetVars(scip);

   /* determine number for possible multi-aggregations */
   nposvars = 0;
   for( v = nposbinvars - 1; v >= 0; --v )
   {
      assert(SCIPvarGetType(binvars[v]) != SCIP_VARTYPE_CONTINUOUS);

      if( v < nbinvars || SCIPvarIsBinary(binvars[v]) )
      {
         nuplocks = SCIPvarGetNLocksUpType(binvars[v], SCIP_LOCKTYPE_MODEL);
         ndownlocks = SCIPvarGetNLocksDownType(binvars[v], SCIP_LOCKTYPE_MODEL);

         if( (nuplocks == 1 && ndownlocks <= 1) || (nuplocks <= 1 && ndownlocks == 1) || (nuplocks <= 2 && ndownlocks <= 2 && SCIPvarGetNegatedVar(binvars[v]) != NULL) )
            ++nposvars;
      }
   }

   SCIPdebugMsg(scip, "found %d binary variables for possible multi-aggregation\n", nposvars);

   if( nposvars == 0 )
      return SCIP_OKAY;

   /* a hashmap from var to index when found in a set-partitioning constraint */
   SCIP_CALL( SCIPhashmapCreate(&vartoindex, SCIPblkmem(scip), nposvars) );

   /* get temporary memory */
   SCIP_CALL( SCIPallocBufferArray(scip, &chgtype, nconss) );
   BMSclearMemoryArray(chgtype, nconss);

   SCIP_CALL( SCIPallocBufferArray(scip, &considxs, nposbinvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &posincons, nposbinvars) );

   SCIP_CALL( SCIPduplicateBufferArray(scip, &usefulconss, conss, nconss) );
   /* sort constraints */
   SCIPsortPtr((void**)usefulconss, setppcConssSort2, nconss);

   nhashmapentries = 0;
   ndecs = 0;
   donotaggr = SCIPdoNotAggr(scip);
   donotmultaggr = SCIPdoNotMultaggr(scip);
   assert(!donotaggr || !donotmultaggr);

   /* determine singleton variables in set-partitioning/-packing constraints, or doubleton variables (active and
    * negated) in any combination of set-partitioning and set-packing constraints
    *
    * we can multi-aggregate the variable and either change the set-partitioning constraint to a set-packing constraint
    * or even delete it
    */
   for( c = 0; c < nconss; ++c )
   {
      SCIP_CONS* cons;
      SCIP_CONSDATA* consdata;
      int oldnfixedvars;
      nlocaladdconss = 0;

      cons = usefulconss[c];
      assert(cons != NULL);

      if( SCIPconsIsDeleted(cons) )
         continue;

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

      /* if we cannot find any constraint to perform a useful multi-aggregation, stop */
      if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING )
         break;

      if( !SCIPconsIsChecked(cons) )
         continue;

      if( SCIPconsIsModifiable(cons) )
         continue;

      /* update the variables */
      SCIP_CALL( applyFixings(scip, cons, &nlocaladdconss, ndelconss, nfixedvars, cutoff) );

      if( *cutoff )
         break;

      /* due to resolving multi-aggregations a constraint can become deleted */
      if( SCIPconsIsDeleted(cons) )
         continue;

      SCIP_CALL( processFixings(scip, cons, cutoff, nfixedvars, &addcut, &mustcheck) );
      assert(!addcut);

      if( *cutoff )
         break;

      if( SCIPconsIsDeleted(cons) )
         continue;

      oldnfixedvars = *nfixedvars;

      /* merging unmerged constraints */
      SCIP_CALL( mergeMultiples(scip, cons, nfixedvars, ndelconss, nchgcoefs, cutoff) );

      if( *cutoff )
         break;

      if( SCIPconsIsDeleted(cons) )
         continue;

      if( oldnfixedvars < *nfixedvars )
      {
         /* update the variables */
         SCIP_CALL( applyFixings(scip, cons, &nlocaladdconss, ndelconss, nfixedvars, cutoff) );
         assert(!SCIPconsIsDeleted(cons));
         assert(nlocaladdconss == 0);
         assert(!*cutoff);

         if( SCIPconsIsDeleted(cons) )
            continue;
      }

      /* if the constraint was not merged and consists of a variable with its negation, the constraint is redundant */
      if( consdata->nvars < 2 )
      {
         /* deleting redundant set-packing constraint */
         if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING )
         {
            SCIPdebugMsg(scip, "deleting redundant set-packing constraint <%s>\n", SCIPconsGetName(cons));

            SCIP_CALL( SCIPdelCons(scip, cons) );
            ++(*nd