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 <assert.h>
#include <string.h>
#include <limits.h>
#include <stdio.h>
#include <ctype.h>
#include "scip/cons_setppc.h"
#include "scip/cons_linear.h"
#include "scip/cons_quadratic.h"
#include "scip/pub_misc.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	QUADCONSUPGD_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 131101

#define	DEFAULT_PRESOLUSEHASHING TRUE

#define	NMINCOMPARISONS 200000

#define	MINGAINPERNMINCOMPARISONS 1e-06

#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 SCIP_Longint	getVarSignature (SCIP_VAR *var)

static SCIP_Longint	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_SOL sol, SCIP_Bool cutoff)

static SCIP_RETCODE	separateCons (SCIP scip, SCIP_CONS cons, SCIP_SOL sol, 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	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_QUADCONSUPGD (quadraticUpgdSetppc)

static	SCIP_DECL_CONSHDLRCOPY (conshdlrCopySetppc)

static	SCIP_DECL_CONSFREE (consFreeSetppc)

static	SCIP_DECL_CONSINIT (consInitSetppc)

static	SCIP_DECL_CONSEXITPRE (consExitpreSetppc)

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_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_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_ROW *	SCIPgetRowSetppc (SCIP scip, SCIP_CONS cons)

int	SCIPgetNFixedonesSetppc (SCIP scip, SCIP_CONS cons)

int	SCIPgetNFixedzerosSetppc (SCIP scip, SCIP_CONS cons)

Macro Definition Documentation

#define CONSHDLR_NAME "setppc"

Definition at line 36 of file cons_setppc.c.

Referenced by createConsSetppc(), enforcePseudo(), processFixings(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_CONSHDLRCOPY(), SCIPaddCoefSetppc(), SCIPgetDualfarkasSetppc(), SCIPgetDualsolSetppc(), SCIPgetNFixedonesSetppc(), SCIPgetNVarsSetppc(), SCIPgetRowSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), and separateCons().

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

Definition at line 37 of file cons_setppc.c.

#define CONSHDLR_SEPAPRIORITY +700000

priority of the constraint handler for separation

Definition at line 38 of file cons_setppc.c.

#define CONSHDLR_ENFOPRIORITY -700000

priority of the constraint handler for constraint enforcing

Definition at line 39 of file cons_setppc.c.

#define CONSHDLR_CHECKPRIORITY -700000

priority of the constraint handler for checking feasibility

Definition at line 40 of file cons_setppc.c.

#define CONSHDLR_SEPAFREQ 0

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

Definition at line 41 of file cons_setppc.c.

#define CONSHDLR_PROPFREQ 1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 42 of file cons_setppc.c.

#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 43 of file cons_setppc.c.

#define CONSHDLR_MAXPREROUNDS -1

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

Definition at line 46 of file cons_setppc.c.

#define CONSHDLR_DELAYSEPA FALSE

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

Definition at line 47 of file cons_setppc.c.

#define CONSHDLR_DELAYPROP FALSE

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

Definition at line 48 of file cons_setppc.c.

#define CONSHDLR_NEEDSCONS TRUE

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

Definition at line 49 of file cons_setppc.c.

#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS

Definition at line 51 of file cons_setppc.c.

#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

Definition at line 52 of file cons_setppc.c.

#define LINCONSUPGD_PRIORITY +700000

priority of the constraint handler for upgrading of linear constraints

Definition at line 54 of file cons_setppc.c.

#define QUADCONSUPGD_PRIORITY +700000

priority of the constraint handler for upgrading of linear constraints

Definition at line 55 of file cons_setppc.c.

#define EVENTHDLR_NAME "setppc"

Definition at line 57 of file cons_setppc.c.

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

Definition at line 58 of file cons_setppc.c.

#define CONFLICTHDLR_NAME "setppc"

Definition at line 60 of file cons_setppc.c.

#define CONFLICTHDLR_DESC "conflict handler creating set covering constraints"

Definition at line 61 of file cons_setppc.c.

#define CONFLICTHDLR_PRIORITY LINCONSUPGD_PRIORITY

Definition at line 62 of file cons_setppc.c.

#define DEFAULT_PRESOLPAIRWISE TRUE

should pairwise constraint comparison be performed in presolving?

Definition at line 64 of file cons_setppc.c.

#define HASHSIZE_SETPPCCONS 131101

minimal size of hash table in setppc constraint tables

Definition at line 66 of file cons_setppc.c.

Referenced by detectRedundantConstraints().

#define DEFAULT_PRESOLUSEHASHING TRUE

should hash table be used for detecting redundant constraints in advance

Definition at line 67 of file cons_setppc.c.

#define NMINCOMPARISONS 200000

number for minimal pairwise presolving comparisons

Definition at line 68 of file cons_setppc.c.

#define MINGAINPERNMINCOMPARISONS 1e-06

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

Definition at line 69 of file cons_setppc.c.

#define DEFAULT_NPSEUDOBRANCHES 2

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

Definition at line 77 of file cons_setppc.c.

#define DEFAULT_DUALPRESOLVING TRUE

should dual presolving steps be performed?

Definition at line 78 of file cons_setppc.c.

#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 80 of file cons_setppc.c.

#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 87 of file cons_setppc.c.

#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 92 of file cons_setppc.c.

Function Documentation

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

the first constraint is a set partitioning constraint and the second is a set packing or
both constraints are set partitioning constraints and the second has more! variables than the first or
both constraints are set packing constraints and the second has less! variables than the first a "0" is return if

both constraint are of the same type and have the amount of variables or and a "1" is returned otherwise

Parameters

cons1	first problem variable
cons2	second problem variable

Definition at line 172 of file cons_setppc.c.

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 212 of file cons_setppc.c.

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

the second constraint is deleted
the first constraint is a set partitioning constraint and the second is a set packing or
both constraints are set partitioning constraints and the second has more! variables than the first or
both constraints are set packing constraints and the second has less! variables than the first a "0" is return if

both constraint are set-covering constraints
both constraint are of the same type and have the amount of variables or and a "1" is returned otherwise

Parameters

cons1	first problem variable
cons2	second problem variable

Definition at line 228 of file cons_setppc.c.

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 277 of file cons_setppc.c.

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

scip	SCIP data structure
cons	setppc constraint
var	variable of constraint entry

Definition at line 285 of file cons_setppc.c.

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

scip	SCIP data structure
cons	setppc constraint
var	variable of constraint entry

Definition at line 320 of file cons_setppc.c.

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

scip	SCIP data structure
conshdlrdata	pointer to store the constraint handler data
eventhdlr	event handler

Definition at line 355 of file cons_setppc.c.

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

static

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

Parameters

scip	SCIP data structure
conshdlrdata	pointer to the constraint handler data

Definition at line 380 of file cons_setppc.c.

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

static

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

Parameters

scip	SCIP data structure
consdata	setppc constraint data
num	minimum number of entries to store

Definition at line 516 of file cons_setppc.c.

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

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

scip	SCIP data structure
consdata	pointer to store the set partitioning / packing / covering constraint
nvars	number of variables in the constraint
vars	variables of the constraint
setppctype	type of constraint: set partitioning, packing, or covering constraint

Definition at line 540 of file cons_setppc.c.

Referenced by consdataEnsureVarsSize(), and createConsSetppc().

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

scip	SCIP data structure
consdata	pointer to store the set partitioning / packing / covering constraint
nvars	number of variables in the constraint
vars	variables of the constraint
setppctype	type of constraint: set partitioning, packing, or covering constraint

Definition at line 612 of file cons_setppc.c.

Referenced by createConsSetppc().

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

static

frees a set partitioning / packing / covering constraint data

Parameters

scip	SCIP data structure
consdata	pointer to store the set partitioning / packing / covering constraint

Definition at line 634 of file cons_setppc.c.

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

static

prints set partitioning / packing / covering constraint to file stream

Parameters

scip	SCIP data structure
consdata	set partitioning / packing / covering constraint data
file	output file (or NULL for standard output)

Definition at line 665 of file cons_setppc.c.

static SCIP_Longint getVarSignature ( SCIP_VAR * var )

static

returns the signature bitmask for the given variable

Parameters

var variable

Definition at line 702 of file cons_setppc.c.

References NULL.

static SCIP_Longint consdataGetSignature ( SCIP_CONSDATA * consdata )

static

returns the bit signature of the given constraint data

Parameters

consdata set partitioning / packing / covering constraint data

Definition at line 714 of file cons_setppc.c.

References NULL.

Referenced by removeRedundantConstraints().

static void consdataSort ( SCIP_CONSDATA * consdata )

static

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

Parameters

consdata linear constraint data

Definition at line 735 of file cons_setppc.c.

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

Referenced by removeRedundantConstraints().

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

static

changes the type of a setppc constraint

Parameters

scip	SCIP data structure
cons	setppc constraint
setppctype	new type of constraint

Definition at line 767 of file cons_setppc.c.

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

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

static

catches events for variable at given position

Parameters

scip	SCIP data structure
cons	set partitioning / packing / covering constraint
eventhdlr	event handler to call for the event processing
pos	array position of variable to catch bound change events for

Definition at line 838 of file cons_setppc.c.

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

static

drops events for variable at given position

Parameters

scip	SCIP data structure
cons	set partitioning / packing / covering constraint
eventhdlr	event handler to call for the event processing
pos	array position of variable to catch bound change events for

Definition at line 902 of file cons_setppc.c.

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

scip	SCIP data structure
cons	set partitioning / packing / covering constraint
eventhdlr	event handler to call for the event processing

Definition at line 938 of file cons_setppc.c.

Referenced by createConsSetppc().

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

scip	SCIP data structure
cons	set partitioning / packing / covering constraint
eventhdlr	event handler to call for the event processing

Definition at line 961 of file cons_setppc.c.

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

static

adds coefficient in setppc constraint

Parameters

scip	SCIP data structure
cons	setppc constraint
var	variable to add to the constraint

Definition at line 984 of file cons_setppc.c.

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

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

static

deletes coefficient at given position from setppc constraint data

Parameters

scip	SCIP data structure
cons	set partitioning / packing / covering constraint
pos	position of coefficient to delete

Definition at line 1065 of file cons_setppc.c.

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

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 independant variables with negative object coefficient to one
- fix all remaining independant 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 independant 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 independant 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

scip	SCIP data structure
cons	setppc constraint
nfixedvars	pointer to count number of fixings
ndelconss	pointer to count number of deleted constraints
result	pointer to store the result SCIP_SUCCESS, if presolving was performed

Definition at line 1182 of file cons_setppc.c.

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

scip	SCIP data structure
cons	knapsack constraint
nfixedvars	pointer to store number of fixed variables
ndelconss	pointer to store number of deleted constraints
nchgcoefs	pointer to store number of changed coefficients
cutoff	pointer to store whether a fixing leads to a cutoff

Definition at line 1473 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(), SCIPdebugMessage, SCIPdelCons(), SCIPfixVar(), SCIPsortPtr(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetStatus(), SCIPvarIsActive(), SCIPvarIsBinary(), and TRUE.

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

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

scip	SCIP data structure
cons	set partitioning / packing / covering constraint
naddconss	pointer to count number of added constraints, or NULL indicating we can not resolve multi-aggregations
ndelconss	pointer to count number of deleted constraints, or NULL indicating we can not resolve multi-aggregations
nfixedvars	pointer to store number of fixed variables, or NULL indicating we can not resolve multi-aggregations
cutoff	pointer to store whether a fixing leads to a cutoff, or NULL indicating we can not resolve multi-aggregations

Definition at line 1617 of file cons_setppc.c.

References addCoef(), analyzeConflictZero(), delCoefPos(), FALSE, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_ERROR, 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(), SCIPdebugMessage, SCIPdebugPrintCons, SCIPdelCons(), SCIPerrorMessage, 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(), and SCIP_DECL_CONSEXITPRE().

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

scip	SCIP data structure
cons	set partitioning / packing / covering constraint that detected the conflict

Definition at line 1938 of file cons_setppc.c.

Referenced by applyFixings(), and processFixings().

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

scip	SCIP data structure
cons	set partitioning / packing / covering constraint that detected the conflict

Definition at line 1972 of file cons_setppc.c.

Referenced by 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

scip	SCIP data structure
cons	set partitioning / packing / covering constraint to be processed
cutoff	pointer to store TRUE, if the node can be cut off
nfixedvars	pointer to count number of deleted variables
addcut	pointer to store whether this constraint must be added as a cut
mustcheck	pointer to store whether this constraint must be checked for feasibility

Definition at line 2011 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(), SCIPdebugMessage, SCIPdelConsLocal(), SCIPinferBinvarCons(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

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

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

static

checks constraint for violation, returns TRUE iff constraint is feasible

Parameters

scip	SCIP data structure
consdata	set partitioning / packing / covering constraint to be checked
sol	primal CIP solution

Definition at line 2243 of file cons_setppc.c.

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

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

static SCIP_RETCODE createRow	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

static

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

Parameters

scip	SCIP data structure
cons	set partitioning / packing / covering constraint

Definition at line 2288 of file cons_setppc.c.

Referenced by checkCons().

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

static

adds setppc constraint as cut to the LP

Parameters

scip	SCIP data structure
cons	setppc constraint
sol	primal CIP solution, NULL for current LP solution
cutoff	whether a cutoff has been detected

Definition at line 2330 of file cons_setppc.c.

Referenced by separateCons().

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

static

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

Parameters

scip	SCIP data structure
cons	set partitioning / packing / covering constraint to be separated
sol	primal CIP solution, NULL for current LP solution
cutoff	pointer to store TRUE, if the node can be cut off
separated	pointer to store TRUE, if a cut was found
reduceddom	pointer to store TRUE, if a domain reduction was found

Definition at line 2364 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(), SCIPdebugMessage, SCIPgetRowLPFeasibility(), SCIPincConsAge(), SCIPisFeasNegative(), SCIPresetConsAge(), SCIProwIsInLP(), and TRUE.

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

scip	SCIP data structure
cons	set partitioning / packing / covering constraint to be separated
cutoff	pointer to store TRUE, if the node can be cut off
infeasible	pointer to store TRUE, if the constraint was infeasible
reduceddom	pointer to store TRUE, if a domain reduction was found
solvelp	pointer to store TRUE, if the LP has to be solved

Definition at line 2449 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().

static SCIP_DECL_HASHGETKEY ( hashGetKeySetppccons )

static

gets the key of the given element

Definition at line 2510 of file cons_setppc.c.

References SCIP_Bool.

Referenced by enforcePseudo().

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 2518 of file cons_setppc.c.

static SCIP_DECL_HASHKEYVAL ( hashKeyValSetppccons )

static

returns the hash value of the key

Definition at line 2561 of file cons_setppc.c.

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

scip	SCIP data structure
binvars	binary variables to create clique constraints
nbinvars	number of binary variables to create clique constraints
cliquepartition	clique partition of binary variables
ncliques	number of cliques in cliquepartition
usefulconss	storage for created constraints
nusefulconss	pointer to store number of useful created constraints
nrounds	actual presolving round
nfixedvars	pointer to count number of deleted variables
naddconss	pointer to count number of added constraints
ndelconss	pointer to count number of deleted constraints
nchgcoefs	pointer to count number of deleted coefficients
cutoff	pointer to store if the problem is infeasible due to a fixing

Definition at line 2594 of file cons_setppc.c.

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

Referenced by preprocessCliques().

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

scip	SCIP data structure
conss	constraint set
nconss	number of constraints in constraint set
usefulconss	storage for created constraints
nusefulconss	pointer to store number of useful created constraints
nfixedvars	pointer to count number of deleted variables
ndelconss	pointer to count number of deleted constraints
nchgcoefs	pointer to count number of deleted coefficients
cutoff	pointer to store if the problem is infeasible due to a fixing

Definition at line 2714 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().

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 occurances,

Note: works only with merged and active not set-covering constraints

Parameters

scip	SCIP data structure
usefulconss	clique constraints
nusefulconss	number of clique constraints
usefulvars	storage for all found variables
nusefulvars	pointer to store number of added variables
vartoindex	hashmap mapping variables to indices
varnconss	storage for remembering the number of constraints a variable occurs
maxnvarconsidx	storage for the maximal number of occurances of a variable
varconsidxs	storage for constraint indices in which the corresponding variable exists
maxnvars	pointer to store maximal number of variables of a constraint

Definition at line 2806 of file cons_setppc.c.

References deleteCliqueDataEntry(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPconsGetData(), SCIPconsIsActive(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPreallocBufferArray, SCIPvarGetLbLocal(), SCIPvarGetNegatedVar(), SCIPvarGetNegationVar(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetUbLocal(), SCIPvarIsActive(), and SCIPvarIsNegated().

Referenced by collectCliqueConss(), and preprocessCliques().

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

var	variable which appears less
considx	constraint index which to remove
vartoindex	hashmap mapping variables to indices
varnconss	storage for remembering the number of constraints a variable occurs
varconsidxs	storage for constraint indices in which the corresponding variable exists

Definition at line 2913 of file cons_setppc.c.

Referenced by checkForOverlapping(), and collectCliqueData().

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

scip	SCIP data structure
addvar	variable which was added
considx	constraint index which to add
maybenew	could be a new variables, a negated of an already existing
usefulvars	storage for all found variables
nusefulvars	pointer to store number of added variables
vartoindex	hashmap mapping variables to indices
varnconss	storage for remembering the number of constraints a variable occurs
maxnvarconsidx	storage for the maximal number of occurances of a variable
varconsidxs	storage for constraint indices in which the corresponding variable exists

Definition at line 2955 of file cons_setppc.c.

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

Referenced by checkForOverlapping(), and liftCliqueVariables().

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

scip	SCIP data structure
cons	constraint
aggregate	try to aggregate if possible
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
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
naggregations	pointer to store number of aggregations which are not yet performed; or NULL if aggregate == TRUE
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
nfixedvars	pointer to count number of deleted variables
naggrvars	pointer to count number of aggregated variables
ndelconss	pointer to count number of deleted constraints
cutoff	pointer to store if the problem is infeasible due to a fixing

Definition at line 3024 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(), SCIPdebugMessage, SCIPdelCons(), SCIPdoNotAggr(), SCIPfixVar(), SCIPreallocBufferArray, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

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

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

scip	SCIP data structure
cons	constraint which may overlap
considx	constriant index to avoid checking against itself
endidx	end index to check against given constraint
usefulconss	clique constraints
nusefulconss	number of clique constraints
usefulvars	storage for all found variables
nusefulvars	pointer to store number of added variables
vartoindex	hashmap mapping variables to indices
varnconss	storage for remembering the number of constraints a variable occurs
maxnvarconsidx	storage for the maximal number of occurances of a variable
varconsidxs	storage for constraint indices in which the corresponding variable exists
countofoverlapping	the amount of variables of cons which overlap in all other constraint
shrinking	try to replace some variables with one variable
chgcons	pointer to store if the given constraint was changed, due to added/deleted variables
undoneaggrvars	array to store aggregation variables, if aggregation is not performed yet; both variables are standing next to each other;
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;
naggregations	pointer to store number of aggregations which are not yet performed;
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;
nfixedvars	pointer to count number of deleted variables
naggrvars	pointer to count number of aggregated variables
nchgcoefs	pointer to count number of changed coefficients
ndelconss	pointer to count number of deleted constraints
cutoff	pointer to store if the problem is infeasible due to a fixing

Definition at line 3367 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(), SCIPdebugMessage, SCIPdelCons(), SCIPdoNotAggr(), SCIPfixVar(), SCIPgetNegatedVar(), SCIPreallocBufferArray, SCIPsortDownPtr(), SCIPupdateConsFlags(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNegationVar(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsActive(), and TRUE.

Referenced by preprocessCliques(), and presolvePropagateCons().

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

scip	SCIP data structure
cons	constraint which may overlap
arraypos	position of constraint in global array
usefulvars	possible variables to lift
nusefulvars	pointer to store number of added variables
endidx	end index for possible lifting variables
cliquevalues	pointer to clique values of constraint-variables, either one if the varibale is active or zero if the variable is negated

Note: this array can be resized in this method

Parameters

vartoindex	hashmap mapping variables to indices
varnconss	array with number of constraints a variable occurs
maxnvarconsidx	array with the maximal number of occurances of a variable
varconsidxs	array with constraint indices in which the corresponding variable exists
maxnvars	pointer to store maximal number of variables of a constraint
nadded	pointer to store number of possible added variables
chgcons	pointer to store if the constraint was changed, due to added variables
nfixedvars	pointer to count number of deleted variables
ndelconss	pointer to count number of deleted constraints
cutoff	pointer to store if the problem is infeasible due to a fixing

Definition at line 4233 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(), SCIPdebugMessage, SCIPdelCons(), SCIPfixVar(), SCIPhashmapExists(), SCIPhaveVarsCommonClique(), SCIPreallocBufferArray, SCIPvarCompareActiveAndNegated(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNegationVar(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarsHaveCommonClique(), and TRUE.

Referenced by checkForOverlapping(), and preprocessCliques().

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

scip	SCIP data structure
conshdlrdata	constraint handler data
undoneaggrvars	aggregation variables storage
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;
naggregations	number of aggregations to performed
naggrvars	pointer to count number of aggregated variables
cutoff	pointer to store if the problem is infeasible due to a fixing

Definition at line 4707 of file cons_setppc.c.

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

Referenced by liftCliqueVariables(), and 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

scip	SCIP data structure
conshdlrdata	constraint handler data
conss	constraint set
nconss	number of constraints in constraint set
nrounds	actual presolving round
firstchange	pointer to store first changed constraint
firstclique	pointer to store first constraint to start adding clique again
lastclique	pointer to store last constraint to add cliques again
nfixedvars	pointer to count number of deleted variables
naggrvars	pointer to count number of aggregated variables
ndelconss	pointer to count number of deleted constraints
nchgcoefs	pointer to count number of deleted coefficients
cutoff	pointer to store if the problem is infeasible due to a fixing

Definition at line 4788 of file cons_setppc.c.

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

Referenced by performAggregations().

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

scip	SCIP data structure
conss	constraint set
nconss	number of constraints in constraint set
firstclique	first constraint to start to add cliques
lastclique	last constraint to start to add cliques
naddconss	pointer to count number of added constraints
ndelconss	pointer to count number of deleted constraints
nchgbds	pointer to count number of chnaged bounds
cutoff	pointer to store if the problem is infeasible due to a fixing

Definition at line 5232 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().

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

scip	SCIP data structure
linearconshdlrexist	does the linear constraint handler exist, necessaray for multi-aggregations
vars	all variables including the variable to which will be multi-aggregated
nvars	number of all variables
pos	position of variable for multi-aggregation
infeasible	pointer to store infeasibility status of aggregation
aggregated	pointer to store aggregation status

Definition at line 5315 of file cons_setppc.c.

References NULL, removeDoubleAndSingletonsAndPerformDualpresolve(), scalars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaggregateVars(), SCIPallocBufferArray, SCIPdebugMessage, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPmultiaggregateVar(), SCIPvarGetName(), SCIPvarGetNLocksDown(), and SCIPvarGetNLocksUp().

Referenced by addCliques(), and 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

c1: x + y + z = 1, uplocks(x) = 1, downlocks(x) = 1 => x = 1 - y - z and change c1 to y + z <= 1
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
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
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

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

scip	SCIP data structure
conss	constraint set
nconss	number of constraints in constraint set
dualpresolvingenabled	is dual presolving enabled
linearconshdlrexist	does the linear constraint handler exist, necessaray for multi-aggregations
nfixedvars	pointer to count number of deleted variables
naggrvars	pointer to count number of aggregated variables
ndelconss	pointer to count number of deleted constraints
nchgcoefs	pointer to count number of changed coefficients
nchgsides	pointer to count number of changed left hand sides
cutoff	pointer to store if a cut off was detedcted

Definition at line 5414 of file cons_setppc.c.

References applyFixings(), BMSclearMemoryArray, delCoefPos(), detectRedundantConstraints(), FALSE, mergeMultiples(), multiAggregateBinvar(), NULL, processFixings(), SCIP_Bool, SCIP_CALL, 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(), SCIPcalcHashtableSize(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconsIsModifiable(), SCIPdebugMessage, SCIPdebugPrintCons, SCIPdelCons(), SCIPdoNotAggr(), SCIPdoNotMultaggr(), SCIPduplicateBufferArray, SCIPfixVar(), SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPhashmapRemove(), SCIPisNegative(), SCIPsortPtr(), SCIPvarGetAggregatedObj(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarIsBinary(), setSetppcType(), and TRUE.

Referenced by multiAggregateBinvar().

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

scip	SCIP data structure
blkmem	block memory
conss	constraint set
nconss	number of constraints in constraint set
firstchange	pointer to store first changed constraint
ndelconss	pointer to count number of deleted constraints
nchgsides	pointer to count number of changed left/right hand sides

Definition at line 6167 of file cons_setppc.c.

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

Referenced by removeDoubleAndSingletonsAndPerformDualpresolve().

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

scip	SCIP data structure
cons0	constraint that should stay
cons1	constraint that should be deleted
ndelconss	pointer to count number of deleted constraints

Definition at line 6275 of file cons_setppc.c.

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

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

scip	SCIP data structure
cons0	constraint that is contained in the other
cons1	constraint that is a superset of the other
cutoff	pointer to store whether a cutoff was found
nfixedvars	pointer to count number of fixed variables

Definition at line 6301 of file cons_setppc.c.

Referenced by 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

scip	SCIP data structure
cons0	constraint that is contained in the other
cons1	constraint that is a superset of the other
cutoff	pointer to store whether a cutoff was found
nfixedvars	pointer to count number of fixed variables
ndelconss	pointer to count number of deleted constraints
nchgsides	pointer to count number of changed left/right hand sides

Definition at line 6373 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().

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

scip	SCIP data structure
conss	constraint set
firstchange	first constraint that changed since last pair preprocessing round
chkind	index of constraint to check against all prior indices upto startind
cutoff	pointer to store whether a cutoff was found
nfixedvars	pointer to count number of fixed variables
ndelconss	pointer to count number of deleted constraints
nchgsides	pointer to count number of changed left/right hand sides

Definition at line 6489 of file cons_setppc.c.

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

Referenced by processContainedCons().

static SCIP_RETCODE performVarDeletions	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_CONS **	conss,
		int	nconss
	)

static

Parameters

scip	SCIP data structure
conshdlr	constraint handler
conss	array of constraints
nconss	number of constraints

Definition at line 6661 of file cons_setppc.c.

Referenced by removeRedundantConstraints().

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

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of variables in the constraint
vars	array with variables of constraint entries
setppctype	type of constraint: set partitioning, packing, or covering constraint
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separate	should the constraint be separated during LP processing? Usually set to TRUE.
enforce	should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
check	should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagate	should the constraint be propagated during node processing? Usually set to TRUE.
local	is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiable	is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamic	is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removable	should 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'.
stickingatnode	should 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 6710 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(), SCIPcreateConsSetcover(), SCIPcreateConsSetpack(), and SCIPcreateConsSetpart().

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

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of variables in the constraint
vars	array with variables of constraint entries
vals	array with coefficients (+1.0 or -1.0)
mult	multiplier on the coefficients(+1 or -1)
setppctype	type of constraint: set partitioning, packing, or covering constraint
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separate	should the constraint be separated during LP processing? Usually set to TRUE.
enforce	should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
check	should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagate	should the constraint be propagated during node processing? Usually set to TRUE.
local	is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiable	is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamic	is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removable	should 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'.
stickingatnode	should 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 6795 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().

static SCIP_DECL_LINCONSUPGD ( linconsUpgdSetppc )

static

check, if linear constraint can be upgraded to set partitioning, packing, or covering constraint

Definition at line 6863 of file cons_setppc.c.

References createNormalizedSetppc(), SCIP_CALL, SCIP_DECL_QUADCONSUPGD(), SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPdebugMessage, SCIPisEQ(), and SCIPisInfinity().

Referenced by createNormalizedSetppc().

static SCIP_DECL_QUADCONSUPGD ( quadraticUpgdSetppc )

static

tries to upgrade a quadratic constraint to a setpacking constraint

Definition at line 6944 of file cons_setppc.c.

Referenced by SCIP_DECL_LINCONSUPGD().

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopySetppc )

static

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

Definition at line 7059 of file cons_setppc.c.

References CONSHDLR_NAME, NULL, and SCIPconshdlrGetName().

static SCIP_DECL_CONSFREE ( consFreeSetppc )

static

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

Definition at line 7075 of file cons_setppc.c.

static SCIP_DECL_CONSINIT ( consInitSetppc )

static

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

Definition at line 7097 of file cons_setppc.c.

static SCIP_DECL_CONSEXITPRE ( consExitpreSetppc )

static

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

Definition at line 7124 of file cons_setppc.c.

References applyFixings(), NULL, SCIP_CALL, SCIP_DECL_CONSEXITSOL(), SCIP_OKAY, and SCIPconsIsDeleted().

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 7145 of file cons_setppc.c.

Referenced by SCIP_DECL_CONSEXITPRE().

static SCIP_DECL_CONSDELETE ( consDeleteSetppc )

static

frees specific constraint data

Definition at line 7168 of file cons_setppc.c.

static SCIP_DECL_CONSTRANS ( consTransSetppc )

static

transforms constraint data into data belonging to the transformed problem

Definition at line 7204 of file cons_setppc.c.

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 7253 of file cons_setppc.c.

static SCIP_DECL_CONSSEPALP ( consSepalpSetppc )

static

separation method of constraint handler for LP solutions

Definition at line 7271 of file cons_setppc.c.

static SCIP_DECL_CONSSEPASOL ( consSepasolSetppc )

static

separation method of constraint handler for arbitrary primal solutions

Definition at line 7314 of file cons_setppc.c.

static SCIP_DECL_CONSENFOLP ( consEnfolpSetppc )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 7666 of file cons_setppc.c.

static SCIP_DECL_CONSENFOPS ( consEnfopsSetppc )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 7724 of file cons_setppc.c.

static SCIP_DECL_CONSCHECK ( consCheckSetppc )

static

feasibility check method of constraint handler for integral solutions

Definition at line 7786 of file cons_setppc.c.

static SCIP_DECL_CONSPROP ( consPropSetppc )

static

domain propagation method of constraint handler

Definition at line 7838 of file cons_setppc.c.

static SCIP_DECL_CONSPRESOL ( consPresolSetppc )

static

presolving method of constraint handler

Definition at line 7900 of file cons_setppc.c.

static SCIP_DECL_CONSRESPROP ( consRespropSetppc )

static

propagation conflict resolving method of constraint handler

Definition at line 8182 of file cons_setppc.c.

static SCIP_DECL_CONSLOCK ( consLockSetppc )

static

variable rounding lock method of constraint handler

Definition at line 8264 of file cons_setppc.c.

static SCIP_DECL_CONSACTIVE ( consActiveSetppc )

static

constraint activation notification method of constraint handler

Definition at line 8304 of file cons_setppc.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSDEACTIVE, SCIP_DECL_CONSDELVARS(), SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsTransformed(), SCIPdebugMessage, and SCIPmarkConsPropagate().

static SCIP_DECL_CONSDELVARS ( consDelvarsSetppc )

static

constraint deactivation notification method of constraint handler variable deletion method of constraint handler

Definition at line 8354 of file cons_setppc.c.

Referenced by SCIP_DECL_CONSACTIVE().

static SCIP_DECL_CONSPRINT ( consPrintSetppc )

static

constraint display method of constraint handler

Definition at line 8372 of file cons_setppc.c.

References SCIP_Real.

static SCIP_DECL_CONSCOPY ( consCopySetppc )

static

constraint copying method of constraint handler

Definition at line 8386 of file cons_setppc.c.

static SCIP_DECL_CONSPARSE ( consParseSetppc )

static

constraint parsing method of constraint handler

Definition at line 8437 of file cons_setppc.c.

static SCIP_DECL_CONSGETVARS ( consGetVarsSetppc )

static

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

Definition at line 8531 of file cons_setppc.c.

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

static SCIP_DECL_CONSGETNVARS ( consGetNVarsSetppc )

static

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

Definition at line 8553 of file cons_setppc.c.

References NULL.

Referenced by SCIP_DECL_CONSGETVARS().

static SCIP_DECL_EVENTEXEC ( eventExecSetppc )

static

Definition at line 8571 of file cons_setppc.c.

static SCIP_DECL_CONFLICTEXEC ( conflictExecSetppc )

static

Definition at line 8660 of file cons_setppc.c.

SCIP_RETCODE SCIPincludeConshdlrSetppc ( SCIP * scip )

creates the handler for set partitioning / packing / covering constraints and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 8788 of file cons_setppc.c.

Referenced by SCIPincludeDefaultPlugins().

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
	)

creates and captures a set partitioning constraint

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of variables in the constraint
vars	array with variables of constraint entries
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separate	should the constraint be separated during LP processing? Usually set to TRUE.
enforce	should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
check	should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagate	should the constraint be propagated during node processing? Usually set to TRUE.
local	is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiable	is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamic	is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removable	should 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'.
stickingatnode	should 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 8890 of file cons_setppc.c.

References createConsSetppc(), SCIP_SETPPCTYPE_PARTITIONING, and SCIPcreateConsBasicSetpart().

Referenced by cliquePresolve(), consdataLinearize(), createAndAddLinearCons(), extractGates(), and processIntegerBoundChg().

SCIP_RETCODE SCIPcreateConsBasicSetpart	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars
	)

creates and captures a set partitioning constraint with all constraint flags set to their default values

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of variables in the constraint
vars	array with variables of constraint entries

Definition at line 8930 of file cons_setppc.c.

Referenced by SCIP_DECL_SOLVECUMULATIVE(), and SCIPcreateConsSetpart().

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
	)

creates and captures a set packing constraint

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of variables in the constraint
vars	array with variables of constraint entries
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separate	should the constraint be separated during LP processing? Usually set to TRUE.
enforce	should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
check	should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagate	should the constraint be propagated during node processing? Usually set to TRUE.
local	is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiable	is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamic	is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removable	should 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'.
stickingatnode	should 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 8948 of file cons_setppc.c.

References createConsSetppc(), SCIP_SETPPCTYPE_PACKING, and SCIPcreateConsBasicSetpack().

Referenced by addCliques(), addExtraCliques(), cliquePresolve(), consdataLinearize(), createAndAddLinearCons(), createCoveringProblem(), deleteRedundantVars(), detectRedundantVars(), dualWeightsTightening(), fixDeleteOrUpgradeCons(), presolRoundConsSOS1(), removeConstraintsDueToNegCliques(), tightenWeights(), upgradeCons(), and upgradeConss().

SCIP_RETCODE SCIPcreateConsBasicSetpack	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars
	)

creates and captures a set packing constraint with all constraint flags set to their default values

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of variables in the constraint
vars	array with variables of constraint entries

Definition at line 8988 of file cons_setppc.c.

Referenced by SCIPcreateConsSetpack().

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
	)

creates and captures a set covering constraint

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of variables in the constraint
vars	array with variables of constraint entries
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separate	should the constraint be separated during LP processing? Usually set to TRUE.
enforce	should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
check	should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagate	should the constraint be propagated during node processing? Usually set to TRUE.
local	is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiable	is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamic	is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removable	should 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'.
stickingatnode	should 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 9007 of file cons_setppc.c.

References createConsSetppc(), SCIP_SETPPCTYPE_COVERING, and SCIPcreateConsBasicSetcover().

Referenced by createAndAddLinearCons(), CUTOFF_CONSTRAINT(), forbidCover(), forbidFixation(), processNlRow(), and readCnf().

SCIP_RETCODE SCIPcreateConsBasicSetcover	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars
	)

creates and captures a set covering constraint with all constraint flags set to their default values

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of variables in the constraint
vars	array with variables of constraint entries

Definition at line 9047 of file cons_setppc.c.

Referenced by SCIPcreateConsSetcover().

SCIP_RETCODE SCIPaddCoefSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	var
	)

adds coefficient in set partitioning / packing / covering constraint

Parameters

scip	SCIP data structure
cons	constraint data
var	variable to add to the constraint

Definition at line 9063 of file cons_setppc.c.

References addCoef(), CONSHDLR_NAME, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetNVarsSetppc().

Referenced by addCoefTerm(), cliquePresolve(), SCIP_DECL_SOLVECUMULATIVE(), and SCIPaddCoefPseudoboolean().

int SCIPgetNVarsSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets number of variables in set partitioning / packing / covering constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9086 of file cons_setppc.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetVarsSetppc().

Referenced by addSetppcConstraints(), cleanupHashDatas(), correctPresoldata(), createPresoldata(), getLinearConsNVars(), getLinearConsVarsData(), SCIP_DECL_READERWRITE(), SCIPaddCoefSetppc(), SCIPmatrixCreate(), SCIPwriteCcg(), SCIPwriteGms(), SCIPwriteLp(), SCIPwritePbm(), SCIPwritePip(), SCIPwritePpm(), writeFzn(), writeOpbConstraints(), and writeOpbObjective().

SCIP_VAR** SCIPgetVarsSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets array of variables in set partitioning / packing / covering constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9107 of file cons_setppc.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetTypeSetppc().

Referenced by addSetppcConstraints(), correctPresoldata(), createPresoldata(), getLinearConsVarsData(), SCIP_DECL_READERWRITE(), SCIPgetNVarsSetppc(), SCIPmatrixCreate(), SCIPwriteCcg(), SCIPwriteGms(), SCIPwriteLp(), SCIPwritePbm(), SCIPwritePip(), SCIPwritePpm(), writeFzn(), writeOpbConstraints(), and writeOpbObjective().

SCIP_SETPPCTYPE SCIPgetTypeSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets type of set partitioning / packing / covering constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9128 of file cons_setppc.c.

References CONSHDLR_NAME, NULL, SCIP_Real, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetDualsolSetppc().

Referenced by addSetppcConstraints(), cleanupHashDatas(), correctPresoldata(), createPresoldata(), findAggregation(), getLinearConsSides(), SCIP_DECL_READERWRITE(), SCIPgetVarsSetppc(), SCIPmatrixCreate(), SCIPwriteGms(), SCIPwriteLp(), SCIPwritePip(), tryUpgradingSetppc(), writeFzn(), and writeOpbConstraints().

SCIP_Real SCIPgetDualsolSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the dual solution of the set partitioning / packing / covering constraint in the current LP

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9148 of file cons_setppc.c.

References CONSHDLR_NAME, NULL, SCIP_INVALID, SCIP_Real, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, SCIPgetDualfarkasSetppc(), and SCIProwGetDualsol().

Referenced by SCIPgetTypeSetppc().

SCIP_Real SCIPgetDualfarkasSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the dual Farkas value of the set partitioning / packing / covering constraint in the current infeasible LP

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9172 of file cons_setppc.c.

References CONSHDLR_NAME, NULL, SCIP_INVALID, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, SCIPgetRowSetppc(), and SCIProwGetDualfarkas().

Referenced by SCIPgetDualsolSetppc().

SCIP_ROW* SCIPgetRowSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns the linear relaxation of the given set partitioning / packing / covering constraint; may return NULL if no LP row was yet created; the user must not modify the row!

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9198 of file cons_setppc.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetNFixedonesSetppc().

Referenced by SCIPgetDualfarkasSetppc().

int SCIPgetNFixedonesSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns current number of variables fixed to one in the constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9219 of file cons_setppc.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetNFixedzerosSetppc().

Referenced by SCIPgetRowSetppc().

int SCIPgetNFixedzerosSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns current number of variables fixed to zero in the constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9241 of file cons_setppc.c.

References NULL, SCIPABORT, SCIPconsGetData(), and SCIPerrorMessage.

Referenced by SCIPgetNFixedonesSetppc().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

Function Documentation