Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Constraint handler for the set partitioning / packing / covering constraints \(1^T x\ \{=, \le, \ge\}\ 1\).

Author
Tobias Achterberg
Michael Winkler

Definition in file cons_setppc.c.

#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 <ctype.h>
#include <string.h>

Go to the source code of this file.

Macros

#define CONSHDLR_NAME   "setppc"
 
#define CONSHDLR_DESC   "set partitioning / packing / covering constraints"
 
#define CONSHDLR_SEPAPRIORITY   +700000
 
#define CONSHDLR_ENFOPRIORITY   -700000
 
#define CONSHDLR_CHECKPRIORITY   -700000
 
#define CONSHDLR_SEPAFREQ   0
 
#define CONSHDLR_PROPFREQ   1
 
#define CONSHDLR_EAGERFREQ   100
 
#define CONSHDLR_MAXPREROUNDS   -1
 
#define CONSHDLR_DELAYSEPA   FALSE
 
#define CONSHDLR_DELAYPROP   FALSE
 
#define CONSHDLR_NEEDSCONS   TRUE
 
#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_ALWAYS
 
#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
 
#define LINCONSUPGD_PRIORITY   +700000
 
#define NONLINCONSUPGD_PRIORITY   +700000
 
#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
 
#define HASHSIZE_SETPPCCONS   500
 
#define DEFAULT_PRESOLUSEHASHING   TRUE
 
#define NMINCOMPARISONS   200000
 
#define MINGAINPERNMINCOMPARISONS   1e-06
 
#define DEFAULT_RANDSEED   3
 
#define DEFAULT_NPSEUDOBRANCHES   2
 
#define DEFAULT_DUALPRESOLVING   TRUE
 
#define DEFAULT_CLIQUELIFTING   FALSE
 
#define DEFAULT_ADDVARIABLESASCLIQUES   FALSE
 
#define DEFAULT_CLIQUESHRINKING   TRUE
 

Functions

static int setppcCompare (SCIP_CONS *const cons1, SCIP_CONS *const cons2)
 
static SCIP_DECL_SORTPTRCOMP (setppcConssSort)
 
static int setppcCompare2 (SCIP_CONS *const cons1, SCIP_CONS *const cons2)
 
static SCIP_DECL_SORTPTRCOMP (setppcConssSort2)
 
static SCIP_RETCODE lockRounding (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
 
static SCIP_RETCODE unlockRounding (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
 
static SCIP_RETCODE conshdlrdataCreate (SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
 
static SCIP_RETCODE conshdlrdataFree (SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
 
static SCIP_RETCODE consdataEnsureVarsSize (SCIP *scip, SCIP_CONSDATA *consdata, int num)
 
static SCIP_RETCODE consdataCreate (SCIP *scip, SCIP_CONSDATA **consdata, int nvars, SCIP_VAR **vars, SCIP_SETPPCTYPE setppctype)
 
static SCIP_RETCODE consdataCreateTransformed (SCIP *scip, SCIP_CONSDATA **consdata, int nvars, SCIP_VAR **vars, SCIP_SETPPCTYPE setppctype)
 
static SCIP_RETCODE consdataFree (SCIP *scip, SCIP_CONSDATA **consdata)
 
static SCIP_RETCODE consdataPrint (SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
 
static uint64_t consdataGetSignature (SCIP_CONSDATA *consdata)
 
static void consdataSort (SCIP_CONSDATA *consdata)
 
static SCIP_RETCODE setSetppcType (SCIP *scip, SCIP_CONS *cons, SCIP_SETPPCTYPE setppctype)
 
static SCIP_RETCODE catchEvent (SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
 
static SCIP_RETCODE dropEvent (SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
 
static SCIP_RETCODE catchAllEvents (SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr)
 
static SCIP_RETCODE dropAllEvents (SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr)
 
static SCIP_RETCODE addCoef (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
 
static SCIP_RETCODE delCoefPos (SCIP *scip, SCIP_CONS *cons, int pos)
 
static SCIP_RETCODE dualPresolving (SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, SCIP_RESULT *result)
 
static SCIP_RETCODE mergeMultiples (SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, int *nchgcoefs, SCIP_Bool *cutoff)
 
static SCIP_RETCODE applyFixings (SCIP *scip, SCIP_CONS *cons, int *naddconss, int *ndelconss, int *nfixedvars, SCIP_Bool *cutoff)
 
static SCIP_RETCODE analyzeConflictZero (SCIP *scip, SCIP_CONS *cons)
 
static SCIP_RETCODE analyzeConflictOne (SCIP *scip, SCIP_CONS *cons)
 
static SCIP_RETCODE processFixings (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nfixedvars, SCIP_Bool *addcut, SCIP_Bool *mustcheck)
 
static SCIP_Bool checkCons (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol)
 
static SCIP_RETCODE createRow (SCIP *scip, SCIP_CONS *cons)
 
static SCIP_RETCODE addCut (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
 
static SCIP_RETCODE addNlrow (SCIP *scip, SCIP_CONS *cons)
 
static SCIP_RETCODE separateCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool lpfeas, SCIP_Bool *cutoff, SCIP_Bool *separated, SCIP_Bool *reduceddom)
 
static SCIP_RETCODE enforcePseudo (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, SCIP_Bool *infeasible, SCIP_Bool *reduceddom, SCIP_Bool *solvelp)
 
static SCIP_DECL_HASHGETKEY (hashGetKeySetppccons)
 
static SCIP_DECL_HASHKEYEQ (hashKeyEqSetppccons)
 
static SCIP_DECL_HASHKEYVAL (hashKeyValSetppccons)
 
static SCIP_RETCODE addExtraCliques (SCIP *const scip, SCIP_VAR **const binvars, int const nbinvars, int *const cliquepartition, int const ncliques, SCIP_CONS **const usefulconss, int *const nusefulconss, int const nrounds, int *const nfixedvars, int *const naddconss, int *const ndelconss, int *const nchgcoefs, SCIP_Bool *const cutoff)
 
static SCIP_RETCODE collectCliqueConss (SCIP *const scip, SCIP_CONS **const conss, int const nconss, SCIP_CONS **const usefulconss, int *const nusefulconss, int *const nfixedvars, int *const ndelconss, int *const nchgcoefs, SCIP_Bool *const cutoff)
 
static SCIP_RETCODE collectCliqueData (SCIP *const scip, SCIP_CONS **const usefulconss, int const nusefulconss, SCIP_VAR **const usefulvars, int *const nusefulvars, SCIP_HASHMAP *const vartoindex, int *const varnconss, int *const maxnvarconsidx, int **const varconsidxs, int *const maxnvars)
 
static void deleteCliqueDataEntry (SCIP_VAR *const var, int const considx, SCIP_HASHMAP *const vartoindex, int *const varnconss, int **const varconsidxs)
 
static SCIP_RETCODE addCliqueDataEntry (SCIP *const scip, SCIP_VAR *const addvar, int const considx, SCIP_Bool const maybenew, SCIP_VAR **const usefulvars, int *const nusefulvars, SCIP_HASHMAP *const vartoindex, int *const varnconss, int *const maxnvarconsidx, int **const varconsidxs)
 
static SCIP_RETCODE presolvePropagateCons (SCIP *const scip, SCIP_CONS *const cons, SCIP_Bool const aggregate, SCIP_VAR **undoneaggrvars, SCIP_Bool *undoneaggrtypes, int *const naggregations, int *const saggregations, int *const nfixedvars, int *const naggrvars, int *const ndelconss, SCIP_Bool *const cutoff)
 
static SCIP_RETCODE checkForOverlapping (SCIP *const scip, SCIP_CONS *const cons, int const considx, int const endidx, SCIP_CONS **const usefulconss, int const nusefulconss, SCIP_VAR **const usefulvars, int *const nusefulvars, SCIP_HASHMAP *const vartoindex, int *const varnconss, int *const maxnvarconsidx, int **const varconsidxs, int *const countofoverlapping, SCIP_Bool const shrinking, SCIP_Bool *const chgcons, SCIP_VAR **undoneaggrvars, SCIP_Bool *undoneaggrtypes, int *const naggregations, int *const saggregations, int *const nfixedvars, int *const naggrvars, int *const nchgcoefs, int *const ndelconss, SCIP_Bool *const cutoff)
 
static SCIP_RETCODE liftCliqueVariables (SCIP *const scip, SCIP_CONS *const cons, int const arraypos, SCIP_VAR **const usefulvars, int *const nusefulvars, int const endidx, SCIP_Bool **cliquevalues, SCIP_HASHMAP *const vartoindex, int *const varnconss, int *const maxnvarconsidx, int **const varconsidxs, int *const maxnvars, int *const nadded, SCIP_Bool *const chgcons, int *const nfixedvars, int *const ndelconss, SCIP_Bool *const cutoff)
 
static SCIP_RETCODE performAggregations (SCIP *const scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR **const undoneaggrvars, SCIP_Bool *const undoneaggrtypes, int const naggregations, int *const naggrvars, SCIP_Bool *const cutoff)
 
static SCIP_RETCODE preprocessCliques (SCIP *const scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **const conss, int const nconss, int const nrounds, int *const firstchange, int *const firstclique, int *const lastclique, int *const nfixedvars, int *const naggrvars, int *const ndelconss, int *const nchgcoefs, SCIP_Bool *const cutoff)
 
static SCIP_RETCODE addCliques (SCIP *scip, SCIP_CONS **conss, int nconss, int firstclique, int lastclique, int *naddconss, int *ndelconss, int *nchgbds, SCIP_Bool *cutoff)
 
static SCIP_RETCODE multiAggregateBinvar (SCIP *scip, SCIP_Bool linearconshdlrexist, SCIP_VAR **vars, int nvars, int pos, SCIP_Bool *infeasible, SCIP_Bool *aggregated)
 
static SCIP_RETCODE removeDoubleAndSingletonsAndPerformDualpresolve (SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool dualpresolvingenabled, SCIP_Bool linearconshdlrexist, int *nfixedvars, int *naggrvars, int *ndelconss, int *nchgcoefs, int *nchgsides, SCIP_Bool *cutoff)
 
static SCIP_RETCODE detectRedundantConstraints (SCIP *scip, BMS_BLKMEM *blkmem, SCIP_CONS **conss, int nconss, int *firstchange, int *ndelconss, int *nchgsides)
 
static SCIP_RETCODE removeRedundantCons (SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1, int *ndelconss)
 
static SCIP_RETCODE fixAdditionalVars (SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1, SCIP_Bool *cutoff, int *nfixedvars)
 
static SCIP_RETCODE processContainedCons (SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1, SCIP_Bool *cutoff, int *nfixedvars, int *ndelconss, int *nchgsides)
 
static SCIP_RETCODE removeRedundantConstraints (SCIP *scip, SCIP_CONS **conss, int firstchange, int chkind, SCIP_Bool *cutoff, int *nfixedvars, int *ndelconss, int *nchgsides)
 
static SCIP_RETCODE performVarDeletions (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss)
 
static SCIP_RETCODE enforceConstraint (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result)
 
static SCIP_RETCODE createConsSetppc (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_SETPPCTYPE setppctype, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
static SCIP_RETCODE createNormalizedSetppc (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, int mult, SCIP_SETPPCTYPE setppctype, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
static SCIP_DECL_LINCONSUPGD (linconsUpgdSetppc)
 
static SCIP_DECL_NONLINCONSUPGD (nonlinUpgdSetppc)
 
static SCIP_DECL_CONSHDLRCOPY (conshdlrCopySetppc)
 
static SCIP_DECL_CONSFREE (consFreeSetppc)
 
static SCIP_DECL_CONSINIT (consInitSetppc)
 
static SCIP_DECL_CONSEXITPRE (consExitpreSetppc)
 
static SCIP_DECL_CONSINITSOL (consInitsolSetppc)
 
static SCIP_DECL_CONSEXITSOL (consExitsolSetppc)
 
static SCIP_DECL_CONSDELETE (consDeleteSetppc)
 
static SCIP_DECL_CONSTRANS (consTransSetppc)
 
static SCIP_DECL_CONSINITLP (consInitlpSetppc)
 
static SCIP_DECL_CONSSEPALP (consSepalpSetppc)
 
static SCIP_DECL_CONSSEPASOL (consSepasolSetppc)
 
static SCIP_DECL_CONSENFOLP (consEnfolpSetppc)
 
static SCIP_DECL_CONSENFORELAX (consEnforelaxSetppc)
 
static SCIP_DECL_CONSENFOPS (consEnfopsSetppc)
 
static SCIP_DECL_CONSCHECK (consCheckSetppc)
 
static SCIP_DECL_CONSPROP (consPropSetppc)
 
static SCIP_DECL_CONSPRESOL (consPresolSetppc)
 
static SCIP_DECL_CONSRESPROP (consRespropSetppc)
 
static SCIP_DECL_CONSLOCK (consLockSetppc)
 
static SCIP_DECL_CONSACTIVE (consActiveSetppc)
 
static SCIP_DECL_CONSDEACTIVE (consDeactiveSetppc)
 
static SCIP_DECL_CONSDELVARS (consDelvarsSetppc)
 
static SCIP_DECL_CONSPRINT (consPrintSetppc)
 
static SCIP_DECL_CONSCOPY (consCopySetppc)
 
static SCIP_DECL_CONSPARSE (consParseSetppc)
 
static SCIP_DECL_CONSGETVARS (consGetVarsSetppc)
 
static SCIP_DECL_CONSGETNVARS (consGetNVarsSetppc)
 
static SCIP_DECL_EVENTEXEC (eventExecSetppc)
 
static SCIP_DECL_CONFLICTEXEC (conflictExecSetppc)
 
SCIP_RETCODE SCIPincludeConshdlrSetppc (SCIP *scip)
 
SCIP_RETCODE SCIPcreateConsSetpart (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
SCIP_RETCODE SCIPcreateConsBasicSetpart (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
 
SCIP_RETCODE SCIPcreateConsSetpack (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
SCIP_RETCODE SCIPcreateConsBasicSetpack (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
 
SCIP_RETCODE SCIPcreateConsSetcover (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
SCIP_RETCODE SCIPcreateConsBasicSetcover (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
 
SCIP_RETCODE SCIPaddCoefSetppc (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
 
int SCIPgetNVarsSetppc (SCIP *scip, SCIP_CONS *cons)
 
SCIP_VAR ** SCIPgetVarsSetppc (SCIP *scip, SCIP_CONS *cons)
 
SCIP_SETPPCTYPE SCIPgetTypeSetppc (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real SCIPgetDualsolSetppc (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real SCIPgetDualfarkasSetppc (SCIP *scip, SCIP_CONS *cons)
 
SCIP_ROWSCIPgetRowSetppc (SCIP *scip, SCIP_CONS *cons)
 
int SCIPgetNFixedonesSetppc (SCIP *scip, SCIP_CONS *cons)
 
int SCIPgetNFixedzerosSetppc (SCIP *scip, SCIP_CONS *cons)
 
SCIP_RETCODE SCIPcleanupConssSetppc (SCIP *scip, SCIP_Bool onlychecked, SCIP_Bool *infeasible, int *naddconss, int *ndelconss, int *nchgcoefs, int *nfixedvars)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "set partitioning / packing / covering constraints"

Definition at line 59 of file cons_setppc.c.

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   +700000

priority of the constraint handler for separation

Definition at line 60 of file cons_setppc.c.

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   -700000

priority of the constraint handler for constraint enforcing

Definition at line 61 of file cons_setppc.c.

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -700000

priority of the constraint handler for checking feasibility

Definition at line 62 of file cons_setppc.c.

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ   0

frequency for separating cuts; zero means to separate only in the root node

Definition at line 63 of file cons_setppc.c.

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 64 of file cons_setppc.c.

◆ CONSHDLR_EAGERFREQ

#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

Definition at line 65 of file cons_setppc.c.

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS   -1

maximal number of presolving rounds the constraint handler participates in (-1: no limit)

Definition at line 68 of file cons_setppc.c.

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 69 of file cons_setppc.c.

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 70 of file cons_setppc.c.

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   TRUE

should the constraint handler be skipped, if no constraints are available?

Definition at line 71 of file cons_setppc.c.

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_ALWAYS

Definition at line 73 of file cons_setppc.c.

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 74 of file cons_setppc.c.

◆ LINCONSUPGD_PRIORITY

#define LINCONSUPGD_PRIORITY   +700000

priority of the constraint handler for upgrading of linear constraints

Definition at line 76 of file cons_setppc.c.

◆ NONLINCONSUPGD_PRIORITY

#define NONLINCONSUPGD_PRIORITY   +700000

priority of the constraint handler for upgrading of nonlinear constraints

Definition at line 77 of file cons_setppc.c.

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "setppc"

Definition at line 79 of file cons_setppc.c.

◆ EVENTHDLR_DESC

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

Definition at line 80 of file cons_setppc.c.

◆ CONFLICTHDLR_NAME

#define CONFLICTHDLR_NAME   "setppc"

Definition at line 82 of file cons_setppc.c.

◆ CONFLICTHDLR_DESC

#define CONFLICTHDLR_DESC   "conflict handler creating set covering constraints"

Definition at line 83 of file cons_setppc.c.

◆ CONFLICTHDLR_PRIORITY

#define CONFLICTHDLR_PRIORITY   LINCONSUPGD_PRIORITY

Definition at line 84 of file cons_setppc.c.

◆ DEFAULT_PRESOLPAIRWISE

#define DEFAULT_PRESOLPAIRWISE   TRUE

should pairwise constraint comparison be performed in presolving?

Definition at line 86 of file cons_setppc.c.

◆ HASHSIZE_SETPPCCONS

#define HASHSIZE_SETPPCCONS   500

minimal size of hash table in setppc constraint tables

Definition at line 88 of file cons_setppc.c.

Referenced by detectRedundantConstraints().

◆ DEFAULT_PRESOLUSEHASHING

#define DEFAULT_PRESOLUSEHASHING   TRUE

should hash table be used for detecting redundant constraints in advance

Definition at line 89 of file cons_setppc.c.

◆ NMINCOMPARISONS

#define NMINCOMPARISONS   200000

number for minimal pairwise presolving comparisons

Definition at line 90 of file cons_setppc.c.

◆ MINGAINPERNMINCOMPARISONS

#define MINGAINPERNMINCOMPARISONS   1e-06

minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round

Definition at line 91 of file cons_setppc.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   3

Definition at line 93 of file cons_setppc.c.

◆ DEFAULT_NPSEUDOBRANCHES

#define DEFAULT_NPSEUDOBRANCHES   2

number of children created in pseudo branching (0: disable branching)

Definition at line 101 of file cons_setppc.c.

◆ DEFAULT_DUALPRESOLVING

#define DEFAULT_DUALPRESOLVING   TRUE

should dual presolving steps be performed?

Definition at line 102 of file cons_setppc.c.

◆ DEFAULT_CLIQUELIFTING

#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

Definition at line 104 of file cons_setppc.c.

◆ DEFAULT_ADDVARIABLESASCLIQUES

#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

Definition at line 111 of file cons_setppc.c.

◆ DEFAULT_CLIQUESHRINKING

#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

Definition at line 116 of file cons_setppc.c.

Function Documentation

◆ setppcCompare()

static int setppcCompare ( SCIP_CONS *const  cons1,
SCIP_CONS *const  cons2 
)
static

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
Parameters
cons1first problem variable
cons2second problem variable

Definition at line 197 of file cons_setppc.c.

◆ SCIP_DECL_SORTPTRCOMP() [1/2]

static SCIP_DECL_SORTPTRCOMP ( setppcConssSort  )
static

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

Definition at line 237 of file cons_setppc.c.

◆ setppcCompare2()

static int setppcCompare2 ( SCIP_CONS *const  cons1,
SCIP_CONS *const  cons2 
)
static

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
Parameters
cons1first problem variable
cons2second problem variable

Definition at line 253 of file cons_setppc.c.

◆ SCIP_DECL_SORTPTRCOMP() [2/2]

static SCIP_DECL_SORTPTRCOMP ( setppcConssSort2  )
static

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

Definition at line 302 of file cons_setppc.c.

◆ lockRounding()

static SCIP_RETCODE lockRounding ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var 
)
static

installs rounding locks for the given variable in the given setppc constraint

Parameters
scipSCIP data structure
conssetppc constraint
varvariable of constraint entry

Definition at line 310 of file cons_setppc.c.

◆ unlockRounding()

static SCIP_RETCODE unlockRounding ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var 
)
static

removes rounding locks for the given variable in the given setppc constraint

Parameters
scipSCIP data structure
conssetppc constraint
varvariable of constraint entry

Definition at line 342 of file cons_setppc.c.

◆ conshdlrdataCreate()

static SCIP_RETCODE conshdlrdataCreate ( SCIP scip,
SCIP_CONSHDLRDATA **  conshdlrdata,
SCIP_EVENTHDLR eventhdlr 
)
static

creates constraint handler data for set partitioning / packing / covering constraint handler

Parameters
scipSCIP data structure
conshdlrdatapointer to store the constraint handler data
eventhdlrevent handler

Definition at line 374 of file cons_setppc.c.

◆ conshdlrdataFree()

static SCIP_RETCODE conshdlrdataFree ( SCIP scip,
SCIP_CONSHDLRDATA **  conshdlrdata 
)
static

frees constraint handler data for set partitioning / packing / covering constraint handler

Parameters
scipSCIP data structure
conshdlrdatapointer to the constraint handler data

Definition at line 403 of file cons_setppc.c.

◆ consdataEnsureVarsSize()

static SCIP_RETCODE consdataEnsureVarsSize ( SCIP scip,
SCIP_CONSDATA consdata,
int  num 
)
static

ensures, that the vars array can store at least num entries

Parameters
scipSCIP data structure
consdatasetppc constraint data
numminimum number of entries to store

Definition at line 543 of file cons_setppc.c.

References consdataCreate(), SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.

◆ consdataCreate()

static SCIP_RETCODE consdataCreate ( SCIP scip,
SCIP_CONSDATA **  consdata,
int  nvars,
SCIP_VAR **  vars,
SCIP_SETPPCTYPE  setppctype 
)
static

creates a set partitioning / packing / covering constraint data object

Parameters
scipSCIP data structure
consdatapointer to store the set partitioning / packing / covering constraint
nvarsnumber of variables in the constraint
varsvariables of the constraint
setppctypetype of constraint: set partitioning, packing, or covering constraint

Definition at line 567 of file cons_setppc.c.

Referenced by consdataEnsureVarsSize(), and createConsSetppc().

◆ consdataCreateTransformed()

static SCIP_RETCODE consdataCreateTransformed ( SCIP scip,
SCIP_CONSDATA **  consdata,
int  nvars,
SCIP_VAR **  vars,
SCIP_SETPPCTYPE  setppctype 
)
static

creates a transformed set partitioning / packing / covering constraint data object

Parameters
scipSCIP data structure
consdatapointer to store the set partitioning / packing / covering constraint
nvarsnumber of variables in the constraint
varsvariables of the constraint
setppctypetype of constraint: set partitioning, packing, or covering constraint

Definition at line 684 of file cons_setppc.c.

Referenced by createConsSetppc().

◆ consdataFree()

static SCIP_RETCODE consdataFree ( SCIP scip,
SCIP_CONSDATA **  consdata 
)
static

frees a set partitioning / packing / covering constraint data

Parameters
scipSCIP data structure
consdatapointer to store the set partitioning / packing / covering constraint

Definition at line 706 of file cons_setppc.c.

◆ consdataPrint()

static SCIP_RETCODE consdataPrint ( SCIP scip,
SCIP_CONSDATA consdata,
FILE *  file 
)
static

prints set partitioning / packing / covering constraint to file stream

Parameters
scipSCIP data structure
consdataset partitioning / packing / covering constraint data
fileoutput file (or NULL for standard output)

Definition at line 743 of file cons_setppc.c.

◆ consdataGetSignature()

static uint64_t consdataGetSignature ( SCIP_CONSDATA consdata)
static

returns the bit signature of the given constraint data

Parameters
consdataset partitioning / packing / covering constraint data

Definition at line 780 of file cons_setppc.c.

References NULL.

Referenced by removeRedundantConstraints().

◆ consdataSort()

static void consdataSort ( SCIP_CONSDATA consdata)
static

sorts setppc constraint's variables by non-decreasing variable index

Parameters
consdatalinear constraint data

Definition at line 801 of file cons_setppc.c.

References SCIPsortPtr(), SCIPvarCompare(), setSetppcType(), and TRUE.

Referenced by removeRedundantConstraints().

◆ setSetppcType()

static SCIP_RETCODE setSetppcType ( SCIP scip,
SCIP_CONS cons,
SCIP_SETPPCTYPE  setppctype 
)
static

changes the type of a setppc constraint

Parameters
scipSCIP data structure
conssetppc constraint
setppctypenew type of constraint

Definition at line 833 of file cons_setppc.c.

Referenced by consdataSort(), detectRedundantConstraints(), processContainedCons(), removeDoubleAndSingletonsAndPerformDualpresolve(), and removeRedundantConstraints().

◆ catchEvent()

static SCIP_RETCODE catchEvent ( SCIP scip,
SCIP_CONS cons,
SCIP_EVENTHDLR eventhdlr,
int  pos 
)
static

catches events for variable at given position

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint
eventhdlrevent handler to call for the event processing
posarray position of variable to catch bound change events for

Definition at line 906 of file cons_setppc.c.

◆ dropEvent()

static SCIP_RETCODE dropEvent ( SCIP scip,
SCIP_CONS cons,
SCIP_EVENTHDLR eventhdlr,
int  pos 
)
static

drops events for variable at given position

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint
eventhdlrevent handler to call for the event processing
posarray position of variable to catch bound change events for

Definition at line 976 of file cons_setppc.c.

◆ catchAllEvents()

static SCIP_RETCODE catchAllEvents ( SCIP scip,
SCIP_CONS cons,
SCIP_EVENTHDLR eventhdlr 
)
static

catches bound change events for all variables in transformed setppc constraint

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint
eventhdlrevent handler to call for the event processing

Definition at line 1012 of file cons_setppc.c.

Referenced by createConsSetppc().

◆ dropAllEvents()

static SCIP_RETCODE dropAllEvents ( SCIP scip,
SCIP_CONS cons,
SCIP_EVENTHDLR eventhdlr 
)
static

drops bound change events for all variables in transformed setppc constraint

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint
eventhdlrevent handler to call for the event processing

Definition at line 1040 of file cons_setppc.c.

◆ addCoef()

static SCIP_RETCODE addCoef ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var 
)
static

adds coefficient in setppc constraint

Parameters
scipSCIP data structure
conssetppc constraint
varvariable to add to the constraint

Definition at line 1068 of file cons_setppc.c.

Referenced by addExtraCliques(), applyFixings(), checkForOverlapping(), liftCliqueVariables(), and SCIPaddCoefSetppc().

◆ delCoefPos()

static SCIP_RETCODE delCoefPos ( SCIP scip,
SCIP_CONS cons,
int  pos 
)
static

deletes coefficient at given position from setppc constraint data

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint
posposition of coefficient to delete

Definition at line 1152 of file cons_setppc.c.

Referenced by applyFixings(), checkForOverlapping(), mergeMultiples(), and removeDoubleAndSingletonsAndPerformDualpresolve().

◆ dualPresolving()

static SCIP_RETCODE dualPresolving ( SCIP scip,
SCIP_CONS cons,
int *  nfixedvars,
int *  ndelconss,
SCIP_RESULT result 
)
static

in case a part (more than one variable) in the setppc constraint is independent of every 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 cause the pairwise comparison of columns is only done heuristically (and here it should be even cheaper) we perform them here (too)

Parameters
scipSCIP data structure
conssetppc constraint
nfixedvarspointer to count number of fixings
ndelconsspointer to count number of deleted constraints
resultpointer to store the result SCIP_SUCCESS, if presolving was performed

Definition at line 1278 of file cons_setppc.c.

◆ mergeMultiples()

static SCIP_RETCODE mergeMultiples ( SCIP scip,
SCIP_CONS cons,
int *  nfixedvars,
int *  ndelconss,
int *  nchgcoefs,
SCIP_Bool cutoff 
)
static

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

Parameters
scipSCIP data structure
consknapsack constraint
nfixedvarspointer to store number of fixed variables
ndelconsspointer to store number of deleted constraints
nchgcoefspointer to store number of changed coefficients
cutoffpointer to store whether a fixing leads to a cutoff

Definition at line 1579 of file cons_setppc.c.

References applyFixings(), delCoefPos(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_NEGATED, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsDeleted(), SCIPdebugMsg, SCIPdelCons(), SCIPfixVar(), SCIPsortPtr(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetStatus(), SCIPvarIsActive(), SCIPvarIsBinary(), and TRUE.

Referenced by addExtraCliques(), collectCliqueConss(), removeDoubleAndSingletonsAndPerformDualpresolve(), and SCIPcleanupConssSetppc().

◆ applyFixings()

static SCIP_RETCODE applyFixings ( SCIP scip,
SCIP_CONS cons,
int *  naddconss,
int *  ndelconss,
int *  nfixedvars,
SCIP_Bool cutoff 
)
static

deletes all zero-fixed variables and replace aggregated variables

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint
naddconsspointer to count number of added constraints, or NULL indicating we can not resolve multi-aggregations
ndelconsspointer to count number of deleted constraints, or NULL indicating we can not resolve multi-aggregations
nfixedvarspointer to store number of fixed variables, or NULL indicating we can not resolve multi-aggregations
cutoffpointer to store whether a fixing leads to a cutoff, or NULL indicating we can not resolve multi-aggregations

Definition at line 1723 of file cons_setppc.c.

References addCoef(), analyzeConflictZero(), delCoefPos(), FALSE, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIP_VARSTATUS_MULTAGGR, SCIP_VARSTATUS_NEGATED, SCIPaddCons(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsAdded(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelCons(), SCIPfixVar(), SCIPfreeBufferArray, SCIPgetBinvarRepresentative(), SCIPgetProbvarLinearSum(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisZero(), SCIPreallocBufferArray, SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetNegationVar(), SCIPvarGetProbvar(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), SCIPvarIsBinary(), SCIPwarningMessage(), and TRUE.

Referenced by addCliques(), collectCliqueConss(), mergeMultiples(), removeDoubleAndSingletonsAndPerformDualpresolve(), SCIP_DECL_CONSEXITPRE(), and SCIPcleanupConssSetppc().

◆ analyzeConflictZero()

static SCIP_RETCODE analyzeConflictZero ( SCIP scip,
SCIP_CONS cons 
)
static

analyzes conflicting assignment on given constraint where all of the variables where assigned to zero, and adds conflict constraint to problem

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint that detected the conflict

Definition at line 2030 of file cons_setppc.c.

Referenced by applyFixings(), and processFixings().

◆ analyzeConflictOne()

static SCIP_RETCODE analyzeConflictOne ( SCIP scip,
SCIP_CONS cons 
)
static

analyzes conflicting assignment on given constraint where two of the variables where assigned to one, and adds conflict constraint to problem

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint that detected the conflict

Definition at line 2065 of file cons_setppc.c.

Referenced by processFixings().

◆ processFixings()

static SCIP_RETCODE processFixings ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool cutoff,
int *  nfixedvars,
SCIP_Bool addcut,
SCIP_Bool mustcheck 
)
static

checks constraint for violation only looking at the fixed variables, applies further fixings if possible

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint to be processed
cutoffpointer to store TRUE, if the node can be cut off
nfixedvarspointer to count number of deleted variables
addcutpointer to store whether this constraint must be added as a cut
mustcheckpointer to store whether this constraint must be checked for feasibility

Definition at line 2105 of file cons_setppc.c.

References analyzeConflictOne(), analyzeConflictZero(), checkCons(), CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPinferBinvarCons(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by collectCliqueConss(), enforcePseudo(), removeDoubleAndSingletonsAndPerformDualpresolve(), and separateCons().

◆ checkCons()

static SCIP_Bool checkCons ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_SOL sol 
)
static

checks constraint for violation, returns TRUE iff constraint is feasible

Parameters
scipSCIP data structure
consdataset partitioning / packing / covering constraint to be checked
solprimal CIP solution

Definition at line 2341 of file cons_setppc.c.

References createRow(), FALSE, NULL, REALABS, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPABORT, SCIPerrorMessage, SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPrelDiff(), SCIPupdateSolLPConsViolation(), and SCIPvarIsBinary().

Referenced by enforcePseudo(), processFixings(), and separateCons().

◆ createRow()

static SCIP_RETCODE createRow ( SCIP scip,
SCIP_CONS cons 
)
static

creates an LP row in a set partitioning / packing / covering constraint data object

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint

Definition at line 2406 of file cons_setppc.c.

Referenced by checkCons().

◆ addCut()

static SCIP_RETCODE addCut ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool cutoff 
)
static

adds setppc constraint as cut to the LP

Parameters
scipSCIP data structure
conssetppc constraint
cutoffwhether a cutoff has been detected

Definition at line 2448 of file cons_setppc.c.

Referenced by separateCons().

◆ addNlrow()

static SCIP_RETCODE addNlrow ( SCIP scip,
SCIP_CONS cons 
)
static

adds setppc constraint as row to the NLP, if not added yet

Parameters
scipSCIP data structure
conssetppc constraint

Definition at line 2481 of file cons_setppc.c.

Referenced by SCIP_DECL_CONSACTIVE(), and SCIP_DECL_CONSINITSOL().

◆ separateCons()

static SCIP_RETCODE separateCons ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_Bool  lpfeas,
SCIP_Bool cutoff,
SCIP_Bool separated,
SCIP_Bool reduceddom 
)
static

checks constraint for violation, and adds it as a cut if possible

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint to be separated
solprimal CIP solution, NULL for current LP solution
lpfeasis the given solution feasible for the current LP ?
cutoffpointer to store TRUE, if the node can be cut off
separatedpointer to store TRUE, if a cut was found
reduceddompointer to store TRUE, if a domain reduction was found

Definition at line 2546 of file cons_setppc.c.

References addCut(), checkCons(), CONSHDLR_NAME, enforcePseudo(), FALSE, NULL, processFixings(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetRowSolFeasibility(), SCIPincConsAge(), SCIPisFeasNegative(), SCIPresetConsAge(), SCIProwIsInLP(), and TRUE.

Referenced by enforceConstraint().

◆ enforcePseudo()

static SCIP_RETCODE enforcePseudo ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool cutoff,
SCIP_Bool infeasible,
SCIP_Bool reduceddom,
SCIP_Bool solvelp 
)
static

enforces the pseudo solution on the given constraint

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint to be separated
cutoffpointer to store TRUE, if the node can be cut off
infeasiblepointer to store TRUE, if the constraint was infeasible
reduceddompointer to store TRUE, if a domain reduction was found
solvelppointer to store TRUE, if the LP has to be solved

Definition at line 2632 of file cons_setppc.c.

References checkCons(), CONSHDLR_NAME, NULL, processFixings(), SCIP_Bool, SCIP_CALL, SCIP_DECL_HASHGETKEY(), SCIP_OKAY, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPhasCurrentNodeLP(), SCIPincConsAge(), SCIPresetConsAge(), and TRUE.

Referenced by separateCons().

◆ SCIP_DECL_HASHGETKEY()

static SCIP_DECL_HASHGETKEY ( hashGetKeySetppccons  )
static

gets the key of the given element

Definition at line 2693 of file cons_setppc.c.

References SCIP_Bool.

Referenced by enforcePseudo().

◆ SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( hashKeyEqSetppccons  )
static

returns TRUE iff both keys are equal; two constraints are equal if they have the same variables

Definition at line 2701 of file cons_setppc.c.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( hashKeyValSetppccons  )
static

returns the hash value of the key

Definition at line 2744 of file cons_setppc.c.

◆ addExtraCliques()

static SCIP_RETCODE addExtraCliques ( SCIP *const  scip,
SCIP_VAR **const  binvars,
int const  nbinvars,
int *const  cliquepartition,
int const  ncliques,
SCIP_CONS **const  usefulconss,
int *const  nusefulconss,
int const  nrounds,
int *const  nfixedvars,
int *const  naddconss,
int *const  ndelconss,
int *const  nchgcoefs,
SCIP_Bool *const  cutoff 
)
static

add extra clique-constraints resulting from a given cliquepartition to SCIP

Parameters
scipSCIP data structure
binvarsbinary variables to create clique constraints
nbinvarsnumber of binary variables to create clique constraints
cliquepartitionclique partition of binary variables
ncliquesnumber of cliques in cliquepartition
usefulconssstorage for created constraints
nusefulconsspointer to store number of useful created constraints
nroundsactual presolving round
nfixedvarspointer to count number of deleted variables
naddconsspointer to count number of added constraints
ndelconsspointer to count number of deleted constraints
nchgcoefspointer to count number of deleted coefficients
cutoffpointer to store if the problem is infeasible due to a fixing

Definition at line 2774 of file cons_setppc.c.

References addCoef(), collectCliqueConss(), FALSE, mergeMultiples(), NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPconsGetData(), SCIPconsIsDeleted(), SCIPcreateConsSetpack(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPreleaseCons(), SCIPsnprintf(), and TRUE.

Referenced by preprocessCliques().

◆ collectCliqueConss()

static SCIP_RETCODE collectCliqueConss ( SCIP *const  scip,
SCIP_CONS **const  conss,
int const  nconss,
SCIP_CONS **const  usefulconss,
int *const  nusefulconss,
int *const  nfixedvars,
int *const  ndelconss,
int *const  nchgcoefs,
SCIP_Bool *const  cutoff 
)
static

start to collect setpartitioning and setpacking constraints, and try to remove fixed variables and merged these constraints

Parameters
scipSCIP data structure
conssconstraint set
nconssnumber of constraints in constraint set
usefulconssstorage for created constraints
nusefulconsspointer to store number of useful created constraints
nfixedvarspointer to count number of deleted variables
ndelconsspointer to count number of deleted constraints
nchgcoefspointer to count number of deleted coefficients
cutoffpointer to store if the problem is infeasible due to a fixing

Definition at line 2894 of file cons_setppc.c.

References applyFixings(), collectCliqueData(), mergeMultiples(), NULL, processFixings(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPconsGetData(), SCIPconsIsActive(), SCIPconsIsDeleted(), and SCIPconsIsModifiable().

Referenced by addExtraCliques(), and preprocessCliques().

◆ collectCliqueData()

static SCIP_RETCODE collectCliqueData ( SCIP *const  scip,
SCIP_CONS **const  usefulconss,
int const  nusefulconss,
SCIP_VAR **const  usefulvars,
int *const  nusefulvars,
SCIP_HASHMAP *const  vartoindex,
int *const  varnconss,
int *const  maxnvarconsidx,
int **const  varconsidxs,
int *const  maxnvars 
)
static

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
Parameters
scipSCIP data structure
usefulconssclique constraints
nusefulconssnumber of clique constraints
usefulvarsstorage for all found variables
nusefulvarspointer to store number of added variables
vartoindexhashmap mapping variables to indices
varnconssstorage for remembering the number of constraints a variable occurs
maxnvarconsidxstorage for the maximal number of occurrences of a variable
varconsidxsstorage for constraint indices in which the corresponding variable exists
maxnvarspointer to store maximal number of variables of a constraint

Definition at line 2986 of file cons_setppc.c.

References deleteCliqueDataEntry(), NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPconsGetData(), SCIPconsIsActive(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPreallocBufferArray, SCIPvarGetLbLocal(), SCIPvarGetNegatedVar(), SCIPvarGetNegationVar(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetUbLocal(), SCIPvarIsActive(), and SCIPvarIsNegated().

Referenced by collectCliqueConss(), and preprocessCliques().

◆ deleteCliqueDataEntry()

static void deleteCliqueDataEntry ( SCIP_VAR *const  var,
int const  considx,
SCIP_HASHMAP *const  vartoindex,
int *const  varnconss,
int **const  varconsidxs 
)
static

correct clique data due to an aggregation

Parameters
varvariable which appears less
considxconstraint index which to remove
vartoindexhashmap mapping variables to indices
varnconssstorage for remembering the number of constraints a variable occurs
varconsidxsstorage for constraint indices in which the corresponding variable exists

Definition at line 3094 of file cons_setppc.c.

Referenced by checkForOverlapping(), and collectCliqueData().

◆ addCliqueDataEntry()

static SCIP_RETCODE addCliqueDataEntry ( SCIP *const  scip,
SCIP_VAR *const  addvar,
int const  considx,
SCIP_Bool const  maybenew,
SCIP_VAR **const  usefulvars,
int *const  nusefulvars,
SCIP_HASHMAP *const  vartoindex,
int *const  varnconss,
int *const  maxnvarconsidx,
int **const  varconsidxs 
)
static
Parameters
scipSCIP data structure
addvarvariable which was added
considxconstraint index which to add
maybenewcould be a new variables, a negated of an already existing
usefulvarsstorage for all found variables
nusefulvarspointer to store number of added variables
vartoindexhashmap mapping variables to indices
varnconssstorage for remembering the number of constraints a variable occurs
maxnvarconsidxstorage for the maximal number of occurrences of a variable
varconsidxsstorage for constraint indices in which the corresponding variable exists

Definition at line 3136 of file cons_setppc.c.

References NULL, presolvePropagateCons(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPreallocBufferArray, SCIPsortedvecInsertDownPtr(), SCIPvarGetLbLocal(), SCIPvarGetNegatedVar(), SCIPvarGetUbLocal(), SCIPvarIsActive(), and SCIPvarIsNegated().

Referenced by checkForOverlapping(), and liftCliqueVariables().

◆ presolvePropagateCons()

static SCIP_RETCODE presolvePropagateCons ( SCIP *const  scip,
SCIP_CONS *const  cons,
SCIP_Bool const  aggregate,
SCIP_VAR **  undoneaggrvars,
SCIP_Bool undoneaggrtypes,
int *const  naggregations,
int *const  saggregations,
int *const  nfixedvars,
int *const  naggrvars,
int *const  ndelconss,
SCIP_Bool *const  cutoff 
)
static

check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if possible

Parameters
scipSCIP data structure
consconstraint
aggregatetry to aggregate if possible
undoneaggrvarsarray to store aggregation variables, if aggregation is not performed yet; both variables are standing next to each other; or NULL if aggregate == TRUE
undoneaggrtypesarray 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
naggregationspointer to store number of aggregations which are not yet performed; or NULL if aggregate == TRUE
saggregationspointer 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
nfixedvarspointer to count number of deleted variables
naggrvarspointer to count number of aggregated variables
ndelconsspointer to count number of deleted constraints
cutoffpointer to store if the problem is infeasible due to a fixing

Definition at line 3205 of file cons_setppc.c.

References BMSclearMemoryArray, checkForOverlapping(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPaggregateVars(), SCIPcalcMemGrowSize(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsActive(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelCons(), SCIPdoNotAggr(), SCIPfixVar(), SCIPreallocBufferArray, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by addCliqueDataEntry(), checkForOverlapping(), and preprocessCliques().

◆ checkForOverlapping()

static SCIP_RETCODE checkForOverlapping ( SCIP *const  scip,
SCIP_CONS *const  cons,
int const  considx,
int const  endidx,
SCIP_CONS **const  usefulconss,
int const  nusefulconss,
SCIP_VAR **const  usefulvars,
int *const  nusefulvars,
SCIP_HASHMAP *const  vartoindex,
int *const  varnconss,
int *const  maxnvarconsidx,
int **const  varconsidxs,
int *const  countofoverlapping,
SCIP_Bool const  shrinking,
SCIP_Bool *const  chgcons,
SCIP_VAR **  undoneaggrvars,
SCIP_Bool undoneaggrtypes,
int *const  naggregations,
int *const  saggregations,
int *const  nfixedvars,
int *const  naggrvars,
int *const  nchgcoefs,
int *const  ndelconss,
SCIP_Bool *const  cutoff 
)
static

check for overlapping constraint

Parameters
scipSCIP data structure
consconstraint which may overlap
considxconstraint index to avoid checking against itself
endidxend index to check against given constraint
usefulconssclique constraints
nusefulconssnumber of clique constraints
usefulvarsstorage for all found variables
nusefulvarspointer to store number of added variables
vartoindexhashmap mapping variables to indices
varnconssstorage for remembering the number of constraints a variable occurs
maxnvarconsidxstorage for the maximal number of occurrences of a variable
varconsidxsstorage for constraint indices in which the corresponding variable exists
countofoverlappingthe amount of variables of cons which overlap in all other constraint
shrinkingtry to replace some variables with one variable
chgconspointer to store if the given constraint was changed, due to added/deleted variables
undoneaggrvarsarray to store aggregation variables, if aggregation is not performed yet; both variables are standing next to each other;
undoneaggrtypesarray 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;
naggregationspointer to store number of aggregations which are not yet performed;
saggregationspointer 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;
nfixedvarspointer to count number of deleted variables
naggrvarspointer to count number of aggregated variables
nchgcoefspointer to count number of changed coefficients
ndelconsspointer to count number of deleted constraints
cutoffpointer to store if the problem is infeasible due to a fixing

Definition at line 3548 of file cons_setppc.c.

References addCliqueDataEntry(), addCoef(), BMSclearMemoryArray, delCoefPos(), deleteCliqueDataEntry(), FALSE, liftCliqueVariables(), NULL, presolvePropagateCons(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIP_VARSTATUS_NEGATED, SCIPcalcMemGrowSize(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsActive(), SCIPdebugMsg, SCIPdelCons(), SCIPdoNotAggr(), SCIPfixVar(), SCIPgetNegatedVar(), SCIPreallocBufferArray, SCIPsortDownPtr(), SCIPupdateConsFlags(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNegationVar(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsActive(), and TRUE.

Referenced by preprocessCliques(), and presolvePropagateCons().

◆ liftCliqueVariables()

static SCIP_RETCODE liftCliqueVariables ( SCIP *const  scip,
SCIP_CONS *const  cons,
int const  arraypos,
SCIP_VAR **const  usefulvars,
int *const  nusefulvars,
int const  endidx,
SCIP_Bool **  cliquevalues,
SCIP_HASHMAP *const  vartoindex,
int *const  varnconss,
int *const  maxnvarconsidx,
int **const  varconsidxs,
int *const  maxnvars,
int *const  nadded,
SCIP_Bool *const  chgcons,
int *const  nfixedvars,
int *const  ndelconss,
SCIP_Bool *const  cutoff 
)
static

try to lift variables to given constraint

Parameters
scipSCIP data structure
consconstraint which may overlap
arrayposposition of constraint in global array
usefulvarspossible variables to lift
nusefulvarspointer to store number of added variables
endidxend index for possible lifting variables
cliquevaluespointer 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
Parameters
vartoindexhashmap mapping variables to indices
varnconssarray with number of constraints a variable occurs
maxnvarconsidxarray with the maximal number of occurrences of a variable
varconsidxsarray with constraint indices in which the corresponding variable exists
maxnvarspointer to store maximal number of variables of a constraint
naddedpointer to store number of possible added variables
chgconspointer to store if the constraint was changed, due to added variables
nfixedvarspointer to count number of deleted variables
ndelconsspointer to count number of deleted constraints
cutoffpointer to store if the problem is infeasible due to a fixing

Definition at line 4414 of file cons_setppc.c.

References addCliqueDataEntry(), addCoef(), FALSE, NULL, performAggregations(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_PARTITIONING, SCIP_VARSTATUS_NEGATED, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsActive(), SCIPdebugMsg, SCIPdelCons(), SCIPfixVar(), SCIPhashmapExists(), SCIPhaveVarsCommonClique(), SCIPreallocBufferArray, SCIPvarCompareActiveAndNegated(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNegationVar(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarsHaveCommonClique(), and TRUE.

Referenced by checkForOverlapping(), and preprocessCliques().

◆ performAggregations()

static SCIP_RETCODE performAggregations ( SCIP *const  scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_VAR **const  undoneaggrvars,
SCIP_Bool *const  undoneaggrtypes,
int const  naggregations,
int *const  naggrvars,
SCIP_Bool *const  cutoff 
)
static

perform all collected aggregations

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data
undoneaggrvarsaggregation variables storage
undoneaggrtypesaggregation 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;
naggregationsnumber of aggregations to performed
naggrvarspointer to count number of aggregated variables
cutoffpointer to store if the problem is infeasible due to a fixing

Definition at line 4888 of file cons_setppc.c.

References a, NULL, preprocessCliques(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaggregateVars(), SCIPdebugMsg, and SCIPvarGetName().

Referenced by liftCliqueVariables(), and preprocessCliques().

◆ preprocessCliques()

static SCIP_RETCODE preprocessCliques ( SCIP *const  scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_CONS **const  conss,
int const  nconss,
int const  nrounds,
int *const  firstchange,
int *const  firstclique,
int *const  lastclique,
int *const  nfixedvars,
int *const  naggrvars,
int *const  ndelconss,
int *const  nchgcoefs,
SCIP_Bool *const  cutoff 
)
static

check whether we can combine or grow cliques so some constraints become redundant or we can fix variables

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data
conssconstraint set
nconssnumber of constraints in constraint set
nroundsactual presolving round
firstchangepointer to store first changed constraint
firstcliquepointer to store first constraint to start adding clique again
lastcliquepointer to store last constraint to add cliques again
nfixedvarspointer to count number of deleted variables
naggrvarspointer to count number of aggregated variables
ndelconsspointer to count number of deleted constraints
nchgcoefspointer to count number of deleted coefficients
cutoffpointer to store if the problem is infeasible due to a fixing

Definition at line 4969 of file cons_setppc.c.

References addCliques(), addExtraCliques(), BMSclearMemoryArray, checkForOverlapping(), collectCliqueConss(), collectCliqueData(), FALSE, liftCliqueVariables(), MAX, NULL, performAggregations(), presolvePropagateCons(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_PARTITIONING, SCIP_VARSTATUS_NEGATED, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcCliquePartition(), SCIPconsGetData(), SCIPconsIsActive(), SCIPdoNotAggr(), SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetNBinVars(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImageInt(), SCIPisStopped(), SCIPrandomPermuteArray(), SCIPreallocBufferArray, SCIPsortDownPtr(), SCIPsortedvecFindDownPtr(), SCIPvarGetLbLocal(), SCIPvarGetNegatedVar(), SCIPvarGetNegationVar(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarIsNegated(), and TRUE.

Referenced by performAggregations().

◆ addCliques()

static SCIP_RETCODE addCliques ( SCIP scip,
SCIP_CONS **  conss,
int  nconss,
int  firstclique,
int  lastclique,
int *  naddconss,
int *  ndelconss,
int *  nchgbds,
SCIP_Bool cutoff 
)
static

add cliques to SCIP

Parameters
scipSCIP data structure
conssconstraint set
nconssnumber of constraints in constraint set
firstcliquefirst constraint to start to add cliques
lastcliquelast constraint to start to add cliques
naddconsspointer to count number of added constraints
ndelconsspointer to count number of deleted constraints
nchgbdspointer to count number of changed bounds
cutoffpointer to store if the problem is infeasible due to a fixing

Definition at line 5413 of file cons_setppc.c.

References applyFixings(), FALSE, multiAggregateBinvar(), NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPaddClique(), SCIPaddVarImplication(), SCIPconsGetData(), SCIPconsIsActive(), SCIPconsIsDeleted(), SCIPconsIsModifiable(), and TRUE.

Referenced by preprocessCliques().

◆ multiAggregateBinvar()

static SCIP_RETCODE multiAggregateBinvar ( SCIP scip,
SCIP_Bool  linearconshdlrexist,
SCIP_VAR **  vars,
int  nvars,
int  pos,
SCIP_Bool infeasible,
SCIP_Bool aggregated 
)
static

perform multi-aggregation on variables resulting from a set-partitioning/-packing constraint

Parameters
scipSCIP data structure
linearconshdlrexistdoes the linear constraint handler exist, necessary for multi-aggregations
varsall variables including the variable to which will be multi-aggregated
nvarsnumber of all variables
posposition of variable for multi-aggregation
infeasiblepointer to store infeasibility status of aggregation
aggregatedpointer to store aggregation status

Definition at line 5496 of file cons_setppc.c.

References FALSE, NULL, removeDoubleAndSingletonsAndPerformDualpresolve(), scalars, SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPaggregateVars(), SCIPallocBufferArray, SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPmultiaggregateVar(), SCIPvarGetName(), SCIPvarGetNLocksDownType(), and SCIPvarGetNLocksUpType().

Referenced by addCliques(), and removeDoubleAndSingletonsAndPerformDualpresolve().

◆ removeDoubleAndSingletonsAndPerformDualpresolve()

static SCIP_RETCODE removeDoubleAndSingletonsAndPerformDualpresolve ( SCIP scip,
SCIP_CONS **  conss,
int  nconss,
SCIP_Bool  dualpresolvingenabled,
SCIP_Bool  linearconshdlrexist,
int *  nfixedvars,
int *  naggrvars,
int *  ndelconss,
int *  nchgcoefs,
int *  nchgsides,
SCIP_Bool cutoff 
)
static

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

  1. f1: x + y <= 1, uplocks(x) = 1, obj(x) <= 0 => x = 1 - y and delete f1
  x + y + z = 1
  ~x + u + v <=/= 1
  ~x + w <= 1
Parameters
scipSCIP data structure
conssconstraint set
nconssnumber of constraints in constraint set
dualpresolvingenabledis dual presolving enabled
linearconshdlrexistdoes the linear constraint handler exist, necessary for multi-aggregations
nfixedvarspointer to count number of deleted variables
naggrvarspointer to count number of aggregated variables
ndelconsspointer to count number of deleted constraints
nchgcoefspointer to count number of changed coefficients
nchgsidespointer to count number of changed left hand sides
cutoffpointer to store if a cut off was detected

Definition at line 5600 of file cons_setppc.c.

References applyFixings(), BMSclearMemoryArray, delCoefPos(), detectRedundantConstraints(), FALSE, mergeMultiples(), multiAggregateBinvar(), NULL, processFixings(), SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_LOOSE, SCIP_VARSTATUS_NEGATED, SCIP_VARTYPE_CONTINUOUS, SCIPaggregateVars(), SCIPallocBufferArray, SCIPblkmem(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelCons(), SCIPdoNotAggr(), SCIPdoNotMultaggr(), SCIPduplicateBufferArray, SCIPfixVar(), SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPhashmapRemove(), SCIPisNegative(), SCIPsortPtr(), SCIPvarGetAggregatedObj(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarIsBinary(), setSetppcType(), and TRUE.

Referenced by multiAggregateBinvar().

◆ detectRedundantConstraints()

static SCIP_RETCODE detectRedundantConstraints ( SCIP scip,
BMS_BLKMEM blkmem,
SCIP_CONS **  conss,
int  nconss,
int *  firstchange,
int *  ndelconss,
int *  nchgsides 
)
static

compares each constraint with all other constraints for possible redundancy and removes or changes constraint accordingly; in contrast to removeRedundantConstraints(), it uses a hash table

Parameters
scipSCIP data structure
blkmemblock memory
conssconstraint set
nconssnumber of constraints in constraint set
firstchangepointer to store first changed constraint
ndelconsspointer to count number of deleted constraints
nchgsidespointer to count number of changed left/right hand sides

Definition at line 6357 of file cons_setppc.c.

References HASHSIZE_SETPPCCONS, MAX, NULL, removeRedundantCons(), SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_PARTITIONING, SCIPconsGetData(), SCIPconsGetName(), SCIPconsGetPos(), SCIPconsIsActive(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelCons(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPupdateConsFlags(), and setSetppcType().

Referenced by removeDoubleAndSingletonsAndPerformDualpresolve().

◆ removeRedundantCons()

static SCIP_RETCODE removeRedundantCons ( SCIP scip,
SCIP_CONS cons0,
SCIP_CONS cons1,
int *  ndelconss 
)
static

removes the redundant second constraint and updates the flags of the first one

Parameters
scipSCIP data structure
cons0constraint that should stay
cons1constraint that should be deleted
ndelconsspointer to count number of deleted constraints

Definition at line 6466 of file cons_setppc.c.

Referenced by detectRedundantConstraints(), processContainedCons(), and removeRedundantConstraints().

◆ fixAdditionalVars()

static SCIP_RETCODE fixAdditionalVars ( SCIP scip,
SCIP_CONS cons0,
SCIP_CONS cons1,
SCIP_Bool cutoff,
int *  nfixedvars 
)
static

for cons0 contained in cons1, fixes variables of cons1 that are not in cons0 to zero

Parameters
scipSCIP data structure
cons0constraint that is contained in the other
cons1constraint that is a superset of the other
cutoffpointer to store whether a cutoff was found
nfixedvarspointer to count number of fixed variables

Definition at line 6492 of file cons_setppc.c.

Referenced by processContainedCons().

◆ processContainedCons()

static SCIP_RETCODE processContainedCons ( SCIP scip,
SCIP_CONS cons0,
SCIP_CONS cons1,
SCIP_Bool cutoff,
int *  nfixedvars,
int *  ndelconss,
int *  nchgsides 
)
static

applies reductions for cons0 being contained in cons1

Parameters
scipSCIP data structure
cons0constraint that is contained in the other
cons1constraint that is a superset of the other
cutoffpointer to store whether a cutoff was found
nfixedvarspointer to count number of fixed variables
ndelconsspointer to count number of deleted constraints
nchgsidespointer to count number of changed left/right hand sides

Definition at line 6564 of file cons_setppc.c.

References FALSE, fixAdditionalVars(), NULL, removeRedundantCons(), removeRedundantConstraints(), SCIP_Bool, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPconsGetData(), SCIPconsGetName(), SCIPerrorMessage, and setSetppcType().

Referenced by removeRedundantConstraints().

◆ removeRedundantConstraints()

static SCIP_RETCODE removeRedundantConstraints ( SCIP scip,
SCIP_CONS **  conss,
int  firstchange,
int  chkind,
SCIP_Bool cutoff,
int *  nfixedvars,
int *  ndelconss,
int *  nchgsides 
)
static

deletes redundant constraints

Parameters
scipSCIP data structure
conssconstraint set
firstchangefirst constraint that changed since last pair preprocessing round
chkindindex of constraint to check against all prior indices up to startind
cutoffpointer to store whether a cutoff was found
nfixedvarspointer to count number of fixed variables
ndelconsspointer to count number of deleted constraints
nchgsidespointer to count number of changed left/right hand sides

Definition at line 6680 of file cons_setppc.c.

References consdataGetSignature(), consdataSort(), FALSE, NULL, performVarDeletions(), processContainedCons(), removeRedundantCons(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsActive(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPvarGetIndex(), and setSetppcType().

Referenced by processContainedCons().

◆ performVarDeletions()

static SCIP_RETCODE performVarDeletions ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS **  conss,
int  nconss 
)
static
Parameters
scipSCIP data structure
conshdlrconstraint handler
conssarray of constraints
nconssnumber of constraints

Definition at line 6852 of file cons_setppc.c.

Referenced by removeRedundantConstraints().

◆ enforceConstraint()

static SCIP_RETCODE enforceConstraint ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS **  conss,
int  nconss,
int  nusefulconss,
SCIP_SOL sol,
SCIP_RESULT result 
)
static

helper function to enforce constraints

Parameters
scipSCIP data structure
conshdlrconstraint handler
conssconstraints to process
nconssnumber of constraints
nusefulconssnumber of useful (non-obsolete) constraints to process
solsolution to enforce (NULL for the LP solution)
resultpointer to store the result of the enforcing call

Definition at line 6894 of file cons_setppc.c.

References CONSHDLR_NAME, createConsSetppc(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIPconshdlrGetName(), SCIPdebugMsg, separateCons(), and TRUE.

Referenced by SCIP_DECL_CONSENFOLP().

◆ createConsSetppc()

static SCIP_RETCODE createConsSetppc ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
int  nvars,
SCIP_VAR **  vars,
SCIP_SETPPCTYPE  setppctype,
SCIP_Bool  initial,
SCIP_Bool  separate,
SCIP_Bool  enforce,
SCIP_Bool  check,
SCIP_Bool  propagate,
SCIP_Bool  local,
SCIP_Bool  modifiable,
SCIP_Bool  dynamic,
SCIP_Bool  removable,
SCIP_Bool  stickingatnode 
)
static

creates and captures a set partitioning / packing / covering constraint

Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables in the constraint
varsarray with variables of constraint entries
setppctypetype of constraint: set partitioning, packing, or covering constraint
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiableis constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removableshould the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnodeshould the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.

Definition at line 6966 of file cons_setppc.c.

References catchAllEvents(), consdataCreate(), consdataCreateTransformed(), CONSHDLR_NAME, createNormalizedSetppc(), NULL, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_PARTITIONING, SCIP_STAGE_PROBLEM, SCIPconshdlrGetData(), SCIPcreateCons(), SCIPerrorMessage, SCIPfindConshdlr(), SCIPgetStage(), and SCIPisTransformed().

Referenced by createNormalizedSetppc(), enforceConstraint(), SCIPcreateConsSetcover(), SCIPcreateConsSetpack(), and SCIPcreateConsSetpart().

◆ createNormalizedSetppc()

static SCIP_RETCODE createNormalizedSetppc ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
int  nvars,
SCIP_VAR **  vars,
SCIP_Real vals,
int  mult,
SCIP_SETPPCTYPE  setppctype,
SCIP_Bool  initial,
SCIP_Bool  separate,
SCIP_Bool  enforce,
SCIP_Bool  check,
SCIP_Bool  propagate,
SCIP_Bool  local,
SCIP_Bool  modifiable,
SCIP_Bool  dynamic,
SCIP_Bool  removable,
SCIP_Bool  stickingatnode 
)
static

creates and captures a normalized (with all coefficients +1) setppc constraint

Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables in the constraint
varsarray with variables of constraint entries
valsarray with coefficients (+1.0 or -1.0)
multmultiplier on the coefficients(+1 or -1)
setppctypetype of constraint: set partitioning, packing, or covering constraint
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiableis constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removableshould the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnodeshould the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.

Definition at line 7051 of file cons_setppc.c.

References createConsSetppc(), NULL, SCIP_CALL, SCIP_DECL_LINCONSUPGD(), SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPfreeBufferArray, and SCIPgetNegatedVar().

Referenced by createConsSetppc(), and SCIP_DECL_LINCONSUPGD().

◆ SCIP_DECL_LINCONSUPGD()

◆ SCIP_DECL_NONLINCONSUPGD()

static SCIP_DECL_NONLINCONSUPGD ( nonlinUpgdSetppc  )
static

tries to upgrade a nonlinear constraint to a setpacking constraint

Definition at line 7200 of file cons_setppc.c.

Referenced by SCIP_DECL_LINCONSUPGD().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopySetppc  )
static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 7344 of file cons_setppc.c.

References CONSHDLR_NAME, NULL, and SCIPconshdlrGetName().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeSetppc  )
static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 7360 of file cons_setppc.c.

◆ SCIP_DECL_CONSINIT()

static SCIP_DECL_CONSINIT ( consInitSetppc  )
static

initialization method of constraint handler (called after problem was transformed)

Definition at line 7381 of file cons_setppc.c.

◆ SCIP_DECL_CONSEXITPRE()

static SCIP_DECL_CONSEXITPRE ( consExitpreSetppc  )
static

presolving deinitialization method of constraint handler (called after presolving has been finished)

Definition at line 7407 of file cons_setppc.c.

References applyFixings(), NULL, SCIP_CALL, SCIP_DECL_CONSINITSOL(), SCIP_OKAY, SCIPconsIsDeleted(), and SCIPisNLPConstructed().

◆ SCIP_DECL_CONSINITSOL()

static SCIP_DECL_CONSINITSOL ( consInitsolSetppc  )
static

solving process deinitialization method of constraint handler (called before branch and bound process data is freed)

Definition at line 7428 of file cons_setppc.c.

References addNlrow(), SCIP_CALL, SCIP_DECL_CONSEXITSOL(), and SCIP_OKAY.

Referenced by SCIP_DECL_CONSEXITPRE().

◆ SCIP_DECL_CONSEXITSOL()

static SCIP_DECL_CONSEXITSOL ( consExitsolSetppc  )
static

solving process deinitialization method of constraint handler (called before branch and bound process data is freed)

Definition at line 7446 of file cons_setppc.c.

Referenced by SCIP_DECL_CONSINITSOL().

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteSetppc  )
static

frees specific constraint data

Definition at line 7474 of file cons_setppc.c.

◆ SCIP_DECL_CONSTRANS()

static SCIP_DECL_CONSTRANS ( consTransSetppc  )
static

transforms constraint data into data belonging to the transformed problem

Definition at line 7510 of file cons_setppc.c.

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpSetppc  )
static

LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)

Definition at line 7559 of file cons_setppc.c.

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpSetppc  )
static

separation method of constraint handler for LP solutions

Definition at line 7577 of file cons_setppc.c.

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolSetppc  )
static

separation method of constraint handler for arbitrary primal solutions

Definition at line 7620 of file cons_setppc.c.

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpSetppc  )
static

constraint enforcing method of constraint handler for LP solutions

Definition at line 7972 of file cons_setppc.c.

References enforceConstraint(), SCIP_CALL, and SCIP_OKAY.

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxSetppc  )
static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 7982 of file cons_setppc.c.

References SCIP_Bool.

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsSetppc  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 7992 of file cons_setppc.c.

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckSetppc  )
static

feasibility check method of constraint handler for integral solutions

Definition at line 8054 of file cons_setppc.c.

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropSetppc  )
static

domain propagation method of constraint handler

Definition at line 8105 of file cons_setppc.c.

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolSetppc  )
static

presolving method of constraint handler

Definition at line 8169 of file cons_setppc.c.

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropSetppc  )
static

propagation conflict resolving method of constraint handler

Definition at line 8451 of file cons_setppc.c.

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockSetppc  )
static

variable rounding lock method of constraint handler

Definition at line 8533 of file cons_setppc.c.

◆ SCIP_DECL_CONSACTIVE()

static SCIP_DECL_CONSACTIVE ( consActiveSetppc  )
static

◆ SCIP_DECL_CONSDEACTIVE()

static SCIP_DECL_CONSDEACTIVE ( consDeactiveSetppc  )
static

constraint deactivation notification method of constraint handler

Definition at line 8610 of file cons_setppc.c.

Referenced by SCIP_DECL_CONSACTIVE().

◆ SCIP_DECL_CONSDELVARS()

static SCIP_DECL_CONSDELVARS ( consDelvarsSetppc  )
static

variable deletion method of constraint handler

Definition at line 8658 of file cons_setppc.c.

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintSetppc  )
static

constraint display method of constraint handler

Definition at line 8676 of file cons_setppc.c.

References SCIP_Real.

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopySetppc  )
static

constraint copying method of constraint handler

Definition at line 8689 of file cons_setppc.c.

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseSetppc  )
static

constraint parsing method of constraint handler

Definition at line 8740 of file cons_setppc.c.

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsSetppc  )
static

constraint method of constraint handler which returns the variables (if possible)

Definition at line 8834 of file cons_setppc.c.

References BMScopyMemoryArray, NULL, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), and TRUE.

◆ SCIP_DECL_CONSGETNVARS()

static SCIP_DECL_CONSGETNVARS ( consGetNVarsSetppc  )
static

constraint method of constraint handler which returns the number of variables (if possible)

Definition at line 8856 of file cons_setppc.c.

References NULL.

Referenced by SCIP_DECL_CONSGETVARS().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecSetppc  )
static

Definition at line 8874 of file cons_setppc.c.

◆ SCIP_DECL_CONFLICTEXEC()

static SCIP_DECL_CONFLICTEXEC ( conflictExecSetppc  )
static

conflict processing method of conflict handler (called when conflict was found)

Definition at line 8970 of file cons_setppc.c.