Detailed Description

constraint handler for symresack constraints

Author: Christopher Hojny; Jasper van Doornmalen

The type of constraints of this constraint handler is described in cons_symresack.h.

The details of the method implemented here are described in the following papers:

Fundamental Domains for Integer Programs with Symmetries
Eric J. Friedman,
Combinatorial Optimization, volume 4616 of LNCS, 146-153 (2007)

This paper describes an inequality to handle symmetries of a single permutation. This so-called FD-inequality is the basic for the propagation routine of our implementation.

Polytopes Associated with Symmetry Handling
Christopher Hojny and Marc E. Pfetsch,
Mathematical Programming 175, No. 1, 197-240, 2019

This paper describes an almost linear time separation routine for so-called cover inequalities of symresacks. A slight modification of this algorithm allows for a linear running time, which is used in this implementation.

Packing, Partitioning, and Covering Symresacks
Christopher Hojny,
(2020), available at https://doi.org/10.1016/j.dam.2020.03.002 Discrete Applied Mathematics, volume 283, 689-717 (2020)

This paper introduces linearly many inequalities with ternary coefficients that suffice to characterize the binary points contained in a packing and partitioning symresack completely.

Definition in file cons_symresack.c.

#include "blockmemshell/memory.h"
#include "scip/cons_orbisack.h"
#include "scip/cons_setppc.h"
#include "scip/cons_symresack.h"
#include "scip/pub_cons.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_var.h"
#include "scip/scip.h"
#include "scip/scip_branch.h"
#include "scip/scip_conflict.h"
#include "scip/scip_cons.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_var.h"

Go to the source code of this file.

Macros
#define	CONSHDLR_NAME "symresack"

#define	CONSHDLR_DESC "symmetry breaking constraint handler relying on symresacks"

#define	CONSHDLR_SEPAPRIORITY +40100

#define	CONSHDLR_ENFOPRIORITY -1005200

#define	CONSHDLR_CHECKPRIORITY -1005200

#define	CONSHDLR_SEPAFREQ 5

#define	CONSHDLR_PROPFREQ 5

#define	CONSHDLR_EAGERFREQ -1

#define	CONSHDLR_MAXPREROUNDS -1

#define	CONSHDLR_DELAYSEPA FALSE

#define	CONSHDLR_DELAYPROP FALSE

#define	CONSHDLR_NEEDSCONS TRUE

#define	CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

#define	CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE

#define	DEFAULT_PPSYMRESACK TRUE

#define	DEFAULT_CHECKMONOTONICITY TRUE

#define	DEFAULT_FORCECONSCOPY FALSE

#define	FIXED0 1 /* When a variable is fixed to 0. */

#define	FIXED1 2 /* When a variable is fixed to 1. */

#define	UNFIXED 3 /* When a variable is neither fixed to 0 or to 1. */

#define	NOINIT

#define	ISFIXED(x, bdchgidx) (SCIPvarGetUbAtIndex(x, bdchgidx, FALSE) - SCIPvarGetLbAtIndex(x, bdchgidx, FALSE) < 0.5)

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

static SCIP_RETCODE	packingUpgrade (SCIP scip, SCIP_CONSDATA consdata, int perm, SCIP_VAR *vars, int nvars, SCIP_Bool checkmonotonicity, SCIP_Bool upgrade)

static SCIP_RETCODE	consdataCreate (SCIP scip, SCIP_CONSHDLR conshdlr, SCIP_CONSDATA *consdata, SCIP_VAR const inputvars, int inputnvars, int inputperm, SCIP_Bool ismodelcons)

static SCIP_RETCODE	initLP (SCIP scip, SCIP_CONS cons, SCIP_Bool checkmonotonicity, SCIP_Bool *infeasible)

static SCIP_RETCODE	checkFeasible (SCIP scip, SCIP_VAR vars, int invperm, int nvars, int start, int tempfixings, int tempfixentries, int numfixentriesinit, SCIP_Bool infeasible, int infeasibleentry)

static SCIP_RETCODE	propVariables (SCIP scip, SCIP_CONS cons, SCIP_Bool infeasible, int ngen)

static SCIP_RETCODE	addSymresackInequality (SCIP scip, SCIP_CONS cons, int nvars, SCIP_VAR *vars, int coeffs, SCIP_Real rhs, SCIP_Bool *infeasible)

static SCIP_RETCODE	maximizeObjectiveSymresackStrict (SCIP scip, int nvars, SCIP_Real objective, int perm, int invperm, int maxcrit, SCIP_Real maxsoluval)

static SCIP_RETCODE	maximizeObjectiveSymresackCriticalEntry (SCIP scip, int nvars, SCIP_Real objective, int perm, int invperm, int crit, int *maxsolu)

static SCIP_RETCODE	separateSymresackCovers (SCIP scip, SCIP_CONS cons, const SCIP_CONSDATA consdata, SCIP_Real vals, int ngen, SCIP_Bool infeasible)

static SCIP_RETCODE	checkSymresackSolution (SCIP scip, SCIP_CONS cons, SCIP_SOL sol, SCIP_RESULT result, SCIP_Bool printreason)

static SCIP_RETCODE	orbisackUpgrade (SCIP scip, SCIP_CONS cons, const char name, int perm, SCIP_VAR inputvars, int nvars, SCIP_Bool upgrade, SCIP_Bool ismodelcons, 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	SCIPcreateSymbreakCons (SCIP scip, SCIP_CONS cons, const char name, int perm, SCIP_VAR *vars, int nvars, SCIP_Bool ismodelcons, 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_CONSHDLRCOPY (conshdlrCopySymresack)

static	SCIP_DECL_CONSDELETE (consDeleteSymresack)

static	SCIP_DECL_CONSFREE (consFreeSymresack)

static	SCIP_DECL_CONSTRANS (consTransSymresack)

static	SCIP_DECL_CONSINITLP (consInitlpSymresack)

static	SCIP_DECL_CONSINITSOL (consInitsolSymresack)

static	SCIP_DECL_CONSSEPALP (consSepalpSymresack)

static	SCIP_DECL_CONSSEPASOL (consSepasolSymresack)

static	SCIP_DECL_CONSENFOLP (consEnfolpSymresack)

static	SCIP_DECL_CONSENFOPS (consEnfopsSymresack)

static	SCIP_DECL_CONSENFORELAX (consEnforelaxSymresack)

static	SCIP_DECL_CONSCHECK (consCheckSymresack)

static	SCIP_DECL_CONSPROP (consPropSymresack)

static	SCIP_DECL_CONSPRESOL (consPresolSymresack)

static	SCIP_DECL_CONSRESPROP (consRespropSymresack)

static	SCIP_DECL_CONSLOCK (consLockSymresack)

static	SCIP_DECL_CONSCOPY (consCopySymresack)

static	SCIP_DECL_CONSPARSE (consParseSymresack)

static	SCIP_DECL_CONSPRINT (consPrintSymresack)

static	SCIP_DECL_CONSGETVARS (consGetVarsSymresack)

static	SCIP_DECL_CONSGETNVARS (consGetNVarsSymresack)

SCIP_RETCODE	SCIPincludeConshdlrSymresack (SCIP *scip)

SCIP_RETCODE	SCIPcreateConsSymresack (SCIP scip, SCIP_CONS cons, const char name, int perm, SCIP_VAR *vars, int nvars, SCIP_Bool ismodelcons, 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	SCIPcreateConsBasicSymresack (SCIP scip, SCIP_CONS cons, const char name, int perm, SCIP_VAR *vars, int nvars, SCIP_Bool ismodelcons)

Macro Definition Documentation

◆ CONSHDLR_NAME

#define CONSHDLR_NAME "symresack"

◆ CONSHDLR_DESC

#define CONSHDLR_DESC "symmetry breaking constraint handler relying on symresacks"

Definition at line 87 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY +40100

priority of the constraint handler for separation

Definition at line 88 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY -1005200

priority of the constraint handler for constraint enforcing

Definition at line 89 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY -1005200

priority of the constraint handler for checking feasibility

Definition at line 90 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ 5

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

Definition at line 91 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ 5

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 92 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ -1

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 93 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS -1

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

Definition at line 96 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA FALSE

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

Definition at line 97 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP FALSE

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

Definition at line 98 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS TRUE

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

Definition at line 99 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

Definition at line 101 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE

Definition at line 102 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ DEFAULT_PPSYMRESACK

#define DEFAULT_PPSYMRESACK TRUE

whether we allow upgrading to packing/partitioning symresacks

Definition at line 104 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ DEFAULT_CHECKMONOTONICITY

#define DEFAULT_CHECKMONOTONICITY TRUE

check whether permutation is monotone when upgrading to packing/partitioning symresacks

Definition at line 105 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ DEFAULT_FORCECONSCOPY

#define DEFAULT_FORCECONSCOPY FALSE

whether symresack constraints should be forced to be copied to sub SCIPs

Definition at line 106 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ FIXED0

#define FIXED0 1 /* When a variable is fixed to 0. */

Definition at line 109 of file cons_symresack.c.

Referenced by checkFeasible(), and propVariables().

◆ FIXED1

#define FIXED1 2 /* When a variable is fixed to 1. */

Definition at line 110 of file cons_symresack.c.

Referenced by checkFeasible(), and propVariables().

◆ UNFIXED

#define UNFIXED 3 /* When a variable is neither fixed to 0 or to 1. */

Definition at line 111 of file cons_symresack.c.

Referenced by checkFeasible(), and propVariables().

◆ NOINIT

#define NOINIT

Value:

0 /* A dummy entry for non-initialized variables.

* Must have value 0 because of SCIPallocCleanBufferArray. */

Definition at line 112 of file cons_symresack.c.

Referenced by checkFeasible(), and propVariables().

◆ ISFIXED

#define ISFIXED	(	x,
		bdchgidx
	)	(SCIPvarGetUbAtIndex(x, bdchgidx, FALSE) - SCIPvarGetLbAtIndex(x, bdchgidx, FALSE) < 0.5)

Definition at line 115 of file cons_symresack.c.

Referenced by SCIP_DECL_CONSRESPROP().

Function Documentation

◆ consdataFree()

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

static

frees a symresack constraint data

Parameters

scip	SCIP data structure
consdata	pointer to symresack constraint data

Definition at line 160 of file cons_symresack.c.

References NULL, packingUpgrade(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseVar().

Referenced by SCIP_DECL_CONSDELETE().

◆ packingUpgrade()

static SCIP_RETCODE packingUpgrade	(	SCIP *	scip,
		SCIP_CONSDATA **	consdata,
		int *	perm,
		SCIP_VAR **	vars,
		int	nvars,
		SCIP_Bool	checkmonotonicity,
		SCIP_Bool *	upgrade
	)

static

check whether constraint can be upgraded to packing/partitioning symresack

Parameters

scip	SCIP data structure
consdata	pointer to store constraint data
perm	permutation
vars	variables affected by permutation
nvars	length of permutation
checkmonotonicity	check whether permutation is monotone
upgrade	pointer to store whether upgrade was successful

Definition at line 219 of file cons_symresack.c.

References consdataCreate(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPdebugMsg, SCIPerrorMessage, SCIPfindConshdlr(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), SCIPvarGetProbindex(), SCIPvarIsNegated(), and TRUE.

Referenced by consdataCreate(), and consdataFree().

◆ consdataCreate()

static SCIP_RETCODE consdataCreate	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_CONSDATA **	consdata,
		SCIP_VAR const	inputvars,
		int	inputnvars,
		int *	inputperm,
		SCIP_Bool	ismodelcons
	)

static

creates symresack constraint data

If the input data contains non-binary variables or fixed points, we delete these variables in a preprocessing step.

Parameters

scip	SCIP data structure
conshdlr	symresack constraint handler
consdata	pointer to store constraint data
inputvars	input variables of the constraint handler
inputnvars	input number of variables of the constraint handler
inputperm	input permutation of the constraint handler
ismodelcons	whether the symresack is a model constraint

Definition at line 473 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, initLP(), NULL, packingUpgrade(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcaptureVar(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBufferArrayNull, SCIPgetTransformedVar(), SCIPisTransformed(), SCIPmarkDoNotMultaggrVar(), and SCIPvarIsBinary().

Referenced by packingUpgrade(), and SCIPcreateConsSymresack().

◆ initLP()

static SCIP_RETCODE initLP	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_Bool	checkmonotonicity,
		SCIP_Bool *	infeasible
	)

static

generate initial LP cut

We generate the ordering inequality for the pair \((1, \gamma^{-1}(1))\), i.e., the inequality \(-x_{1} + x_{\gamma^{-1}(1)} \leq 0\). This inequality is valid, because we guaranteed in a preprocessing step that all variables are binary.

Furthermore, we add facet inequalities of packing/partitioning symresacks if we deal with packing/partitioning symresacks.

Parameters

scip	SCIP pointer
cons	constraint
checkmonotonicity	has it been checked whether permutation is monotone for packing/partitioning symresacks?
infeasible	pointer to store whether we detected infeasibility

Definition at line 614 of file cons_symresack.c.

References checkFeasible(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarsToRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPcreateEmptyRowCons(), SCIPfreeBufferArray, SCIPinfinity(), SCIPreleaseRow(), SCIPsnprintf(), SCIPsortIntInt(), and TRUE.

Referenced by consdataCreate(), and SCIP_DECL_CONSINITLP().

◆ checkFeasible()

static SCIP_RETCODE checkFeasible	(	SCIP *	scip,
		SCIP_VAR **	vars,
		int *	invperm,
		int	nvars,
		int	start,
		int *	tempfixings,
		int *	tempfixentries,
		int	numfixentriesinit,
		SCIP_Bool *	infeasible,
		int *	infeasibleentry
	)

static

Determines if a vector with additional fixings could exist that is lexicographically larger than its image.

Given a vector of variables, a permutation, and a set of additional (virtual) fixings. If a vector adhering to the local variable bounds (local fixings) and to the virtual fixings exists, then infeasible is FALSE, otherwise TRUE.

Parameters

scip	SCIP pointer
vars	array of variables affected by permutation
invperm	inverse of permutation
nvars	number of variables
start	at which position to start (assuming previous positions are equal)
tempfixings	array with at entry i the virtual fixing of variable vars[i]
tempfixentries	the entries i that are virtually fixed until numfixentriesinit
numfixentriesinit	the number of virtually fixed entries
infeasible	pointer to store whether infeasibility is detected in these fixings
infeasibleentry	pointer to store at which entry a (0, 1) pattern is found

Definition at line 818 of file cons_symresack.c.

References FALSE, FIXED0, FIXED1, NOINIT, NULL, propVariables(), SCIP_OKAY, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and UNFIXED.

Referenced by initLP(), and propVariables().

◆ propVariables()

static SCIP_RETCODE propVariables	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_Bool *	infeasible,
		int *	ngen
	)

static

perform propagation of symresack constraint

Parameters

scip	SCIP pointer
cons	constraint to be propagated
infeasible	pointer to store whether it was detected that the node is infeasible
ngen	pointer to store number of generated bound strengthenings

Definition at line 939 of file cons_symresack.c.

References addSymresackInequality(), checkFeasible(), FALSE, FIXED0, FIXED1, NOINIT, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIPaddConflictBinvar(), SCIPallocCleanBufferArray, SCIPanalyzeConflictCons(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPfreeCleanBufferArray, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and UNFIXED.

Referenced by checkFeasible(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().

◆ addSymresackInequality()

static SCIP_RETCODE addSymresackInequality	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int	nvars,
		SCIP_VAR **	vars,
		int *	coeffs,
		SCIP_Real	rhs,
		SCIP_Bool *	infeasible
	)

static

add symresack cover inequality

Parameters

scip	SCIP pointer
cons	constraint
nvars	number of variables
vars	variables
coeffs	coefficient vector of inequality to be added
rhs	right-hand side of inequality to be added
infeasible	pointer to store whether we detected infeasibility

Definition at line 1164 of file cons_symresack.c.

References FALSE, maximizeObjectiveSymresackStrict(), NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetName(), SCIPcreateEmptyRowCons(), SCIPflushRowExtensions(), SCIPinfinity(), SCIPreleaseRow(), SCIPsnprintf(), and TRUE.

Referenced by propVariables(), and separateSymresackCovers().

◆ maximizeObjectiveSymresackStrict()

static SCIP_RETCODE maximizeObjectiveSymresackStrict	(	SCIP *	scip,
		int	nvars,
		SCIP_Real *	objective,
		int *	perm,
		int *	invperm,
		int *	maxcrit,
		SCIP_Real *	maxsoluval
	)

static

Maximize a linear function on a "strict" symresack, that is a symresack where we do not allow the solution x = gamma(x).

Parameters

scip	SCIP pointer
nvars	number of variables in symresack
objective	the objective vector
perm	the permutation (without fixed points) as an array
invperm	the inverse permutation as an array
maxcrit	pointer to the critical entry where optimality is found at
maxsoluval	pointer to store the optimal objective value

Definition at line 1219 of file cons_symresack.c.

References maximizeObjectiveSymresackCriticalEntry(), NULL, SCIP_CALL, SCIP_DEFAULT_INFINITY, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), and SCIPisLT().

Referenced by addSymresackInequality(), and separateSymresackCovers().

◆ maximizeObjectiveSymresackCriticalEntry()

static SCIP_RETCODE maximizeObjectiveSymresackCriticalEntry	(	SCIP *	scip,
		int	nvars,
		SCIP_Real *	objective,
		int *	perm,
		int *	invperm,
		int	crit,
		int *	maxsolu
	)

static

For a symresack, determine a maximizer for optimizing linear function over a symresack, where the critical entry is fixed.

Parameters

scip	SCIP pointer
nvars	number of variables in symresack
objective	the objective vector
perm	the permutation (without fixed points) as an array
invperm	the inverse permutation as an array
crit	critical entry where optimality is found at
maxsolu	pointer to the optimal objective array

Definition at line 1340 of file cons_symresack.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGT(), and separateSymresackCovers().

Referenced by maximizeObjectiveSymresackStrict(), and separateSymresackCovers().

◆ separateSymresackCovers()

static SCIP_RETCODE separateSymresackCovers	(	SCIP *	scip,
		SCIP_CONS *	cons,
		const SCIP_CONSDATA *	consdata,
		SCIP_Real *	vals,
		int *	ngen,
		SCIP_Bool *	infeasible
	)

static

separate symresack cover inequalities

We currently do NOT enter cuts into the pool.

Parameters

scip	SCIP pointer
cons	constraint
consdata	constraint data
vals	solution values of variables
ngen	pointer to store the number of separated covers
infeasible	pointer to store whether we detected infeasibility

Definition at line 1449 of file cons_symresack.c.

References addSymresackInequality(), checkSymresackSolution(), FALSE, maximizeObjectiveSymresackCriticalEntry(), maximizeObjectiveSymresackStrict(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArrayNull, and SCIPisEfficacious().

Referenced by maximizeObjectiveSymresackCriticalEntry(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFORELAX(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

◆ checkSymresackSolution()

static SCIP_RETCODE checkSymresackSolution	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol,
		SCIP_RESULT *	result,
		SCIP_Bool	printreason
	)

static

check whether solution is feasible for symresacks

Parameters

scip	SCIP pointer
cons	constrained for which we check the solution
sol	solution to be checked
result	pointer to store whether we detected infeasibility
printreason	whether reason for infeasibility should be printed

Definition at line 1548 of file cons_symresack.c.

References NULL, orbisackUpgrade(), SCIP_INFEASIBLE, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPinfoMessage(), and SCIPisFeasIntegral().

Referenced by SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSENFOPS(), and separateSymresackCovers().

◆ orbisackUpgrade()

static SCIP_RETCODE orbisackUpgrade	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int *	perm,
		SCIP_VAR **	inputvars,
		int	nvars,
		SCIP_Bool *	upgrade,
		SCIP_Bool	ismodelcons,
		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

Upgrade symresack constraints to orbisacks

Parameters

scip	SCIP pointer
cons	pointer to hold the created constraint
name	name of constraint
perm	permutation
inputvars	permuted variables array
nvars	size of perm array
upgrade	whether constraint was upgraded
ismodelcons	whether the symresack is a model 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 1628 of file cons_symresack.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcreateConsOrbisack(), SCIPcreateSymbreakCons(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPvarIsBinary(), and TRUE.

Referenced by checkSymresackSolution(), and SCIPcreateSymbreakCons().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopySymresack )

static

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

Definition at line 1793 of file cons_symresack.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSDELETE(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrSymresack(), and TRUE.

Referenced by SCIPcreateSymbreakCons().

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteSymresack )

static

frees specific constraint data

Definition at line 1810 of file cons_symresack.c.

References consdataFree(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, and SCIPconshdlrGetName().

Referenced by SCIP_DECL_CONSHDLRCOPY().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeSymresack )

static

frees constraint handler

Definition at line 1825 of file cons_symresack.c.

References CONSHDLR_NAME, NULL, SCIP_DECL_CONSTRANS(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPfreeBlockMemory.

Referenced by SCIP_DECL_CONSDELETE().

◆ SCIP_DECL_CONSTRANS()

static SCIP_DECL_CONSTRANS ( consTransSymresack )

static

transforms constraint data into data belonging to the transformed problem

Definition at line 1844 of file cons_symresack.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSINITLP(), SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcaptureVar(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateCons(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPgetTransformedVar(), SCIPgetTransformedVars(), and SCIPmarkDoNotMultaggrVar().

Referenced by SCIP_DECL_CONSFREE().

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpSymresack )

static

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

Definition at line 1955 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, initLP(), NULL, SCIP_CALL, SCIP_DECL_CONSINITSOL(), SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSTRANS().

◆ SCIP_DECL_CONSINITSOL()

static SCIP_DECL_CONSINITSOL ( consInitsolSymresack )

static

solving process initialization method of constraint handler (called when branch and bound process is about to begin)

Definition at line 1989 of file cons_symresack.c.

References CONSHDLR_NAME, NULL, SCIP_DECL_CONSSEPALP(), SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetData(), and SCIPconshdlrGetName().

Referenced by SCIP_DECL_CONSINITLP().

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpSymresack )

static

separation method of constraint handler for LP solution

Definition at line 2025 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSSEPASOL(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPBranchCands(), SCIPgetSolVals(), and separateSymresackCovers().

Referenced by SCIP_DECL_CONSINITSOL().

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolSymresack )

static

separation method of constraint handler for arbitrary primal solution

Definition at line 2099 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSENFOLP(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSolVals(), and separateSymresackCovers().

Referenced by SCIP_DECL_CONSSEPALP().

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpSymresack )

static

constraint enforcing method of constraint handler for LP solutions.

To check feasibility, we separate cover inequalities.

Precondition: It is assumed that the solution is integral (this can be ensured by appropriate priorities).

Definition at line 2174 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSENFOPS(), SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPBranchCands(), SCIPgetSolVals(), and separateSymresackCovers().

Referenced by SCIP_DECL_CONSSEPASOL().

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsSymresack )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 2252 of file cons_symresack.c.

References checkSymresackSolution(), CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSENFORELAX(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSENFOLP().

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxSymresack )

static

constraint enforcing method of constraint handler for relaxation solutions

To check feasibility, we separate cover inequalities.

Definition at line 2295 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSCHECK(), SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPBranchCands(), SCIPgetSolVals(), and separateSymresackCovers().

Referenced by SCIP_DECL_CONSENFOPS().

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckSymresack )

static

feasibility check method of constraint handler for integral solutions

Definition at line 2371 of file cons_symresack.c.

References checkSymresackSolution(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSPROP(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSENFORELAX().

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropSymresack )

static

domain propagation method of constraint handler

Definition at line 2408 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, NULL, propVariables(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSPRESOL(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPconshdlrGetName(), and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSCHECK().

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolSymresack )

static

presolving method of constraint handler

Definition at line 2455 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, NULL, propVariables(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSRESPROP(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPdelCons(), and TRUE.

Referenced by SCIP_DECL_CONSPROP().

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropSymresack )

static

Propagation resolution for conflict analysis

Definition at line 2518 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, ISFIXED, NULL, REALABS, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_DECL_CONSLOCK(), SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconsGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPvarGetLbAtIndex(), and SCIPvarGetUbAtIndex().

Referenced by SCIP_DECL_CONSPRESOL().

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockSymresack )

static

lock variables

We assume we have only one global (void) constraint and lock all binary variables which do not correspond to fixed points of the permutation.

Symresack constraints may get violated if the variables with a negative coefficient in the FD inequality are rounded down, we therefor call SCIPaddVarLocksType(..., nlockspos, nlocksneg).
Symresack constraints may get violated if the variables with a positive coefficient in the FD inequality are rounded up, we therefor call SCIPaddVarLocksType(..., nlocksneg, nlockspo ).

Definition at line 2687 of file cons_symresack.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSCOPY(), SCIP_OKAY, SCIPaddVarLocksType(), SCIPconsGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSRESPROP().

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopySymresack )

static

constraint copying method of constraint handler

Definition at line 2738 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSPARSE(), SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPcreateConsSymresack(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetVarCopy(), and TRUE.

Referenced by SCIP_DECL_CONSLOCK().

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseSymresack )

static

constraint parsing method of constraint handler

Definition at line 2807 of file cons_symresack.c.

References FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSPRINT(), SCIP_OKAY, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPcreateConsBasicSymresack(), SCIPerrorMessage, SCIPfreeBufferArray, SCIPparseVarName(), SCIPreallocBufferArray, SCIPskipSpace(), SCIPstrToIntValue(), and TRUE.

Referenced by SCIP_DECL_CONSCOPY().

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintSymresack )

static

constraint display method of constraint handler

The constraint handler should output a representation of the constraint into the given text file.

Definition at line 2988 of file cons_symresack.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSGETVARS(), SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPinfoMessage(), SCIPwriteVarName(), and TRUE.

Referenced by SCIP_DECL_CONSPARSE().

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsSymresack )

static

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

Definition at line 3036 of file cons_symresack.c.

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

Referenced by SCIP_DECL_CONSPRINT().

◆ SCIP_DECL_CONSGETNVARS()

static SCIP_DECL_CONSGETNVARS ( consGetNVarsSymresack )

static

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

Definition at line 3065 of file cons_symresack.c.

References NULL, SCIP_OKAY, SCIPconsGetData(), SCIPincludeConshdlrSymresack(), and TRUE.

Referenced by SCIP_DECL_CONSGETVARS().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

◆ CONSHDLR_SEPAPRIORITY

◆ CONSHDLR_ENFOPRIORITY

◆ CONSHDLR_CHECKPRIORITY

◆ CONSHDLR_SEPAFREQ

◆ CONSHDLR_PROPFREQ

◆ CONSHDLR_EAGERFREQ

◆ CONSHDLR_MAXPREROUNDS

◆ CONSHDLR_DELAYSEPA

◆ CONSHDLR_DELAYPROP

◆ CONSHDLR_NEEDSCONS

◆ CONSHDLR_PROP_TIMING

◆ CONSHDLR_PRESOLTIMING

◆ DEFAULT_PPSYMRESACK

◆ DEFAULT_CHECKMONOTONICITY

◆ DEFAULT_FORCECONSCOPY

◆ FIXED0

◆ FIXED1

◆ UNFIXED

◆ NOINIT

◆ ISFIXED

Function Documentation

◆ consdataFree()

◆ packingUpgrade()

◆ consdataCreate()

◆ initLP()

◆ checkFeasible()

◆ propVariables()

◆ addSymresackInequality()

◆ maximizeObjectiveSymresackStrict()

◆ maximizeObjectiveSymresackCriticalEntry()

◆ separateSymresackCovers()

◆ checkSymresackSolution()

◆ orbisackUpgrade()

◆ SCIP_DECL_CONSHDLRCOPY()

◆ SCIP_DECL_CONSDELETE()

◆ SCIP_DECL_CONSFREE()

◆ SCIP_DECL_CONSTRANS()

◆ SCIP_DECL_CONSINITLP()

◆ SCIP_DECL_CONSINITSOL()

◆ SCIP_DECL_CONSSEPALP()

◆ SCIP_DECL_CONSSEPASOL()

◆ SCIP_DECL_CONSENFOLP()

◆ SCIP_DECL_CONSENFOPS()

◆ SCIP_DECL_CONSENFORELAX()

◆ SCIP_DECL_CONSCHECK()

◆ SCIP_DECL_CONSPROP()

◆ SCIP_DECL_CONSPRESOL()

◆ SCIP_DECL_CONSRESPROP()

◆ SCIP_DECL_CONSLOCK()

◆ SCIP_DECL_CONSCOPY()

◆ SCIP_DECL_CONSPARSE()

◆ SCIP_DECL_CONSPRINT()

◆ SCIP_DECL_CONSGETVARS()

◆ SCIP_DECL_CONSGETNVARS()