Detailed Description

constraint handler for symresack constraints

Author: Christopher Hojny

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,
(2017), preprint available at http://www.optimization-online.org/DB_HTML/2017/01/5835.html

This paper describes an almost linear time separation routine for so-called cove inequalities of symresacks. In our implementation, however, we use a separation routine with quadratic worst case running time.

Packing, Partitioning, and Covering Symresacks
Christopher Hojny,
(2017), preprint available at http://www.optimization-online.org/DB_HTML/2017/05/5990.html

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 <assert.h>
#include <string.h>
#include <ctype.h>
#include "scip/cons_orbisack.h"
#include "scip/cons_setppc.h"
#include "scip/cons_symresack.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 FALSE

#define	DEFAULT_CHECKALWAYSFEAS TRUE

#define	ISFIXED0(x) (SCIPvarGetUbLocal(x) < 0.5 ? TRUE : FALSE)

#define	ISFIXED1(x) (SCIPvarGetLbLocal(x) > 0.5 ? TRUE : FALSE)

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 upgrade)

static SCIP_RETCODE	consdataCreate (SCIP scip, SCIP_CONSDATA consdata, SCIP_VAR const inputvars, int inputnvars, int inputperm)

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

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	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 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 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_CONSDELETE (consDeleteSymresack)

static	SCIP_DECL_CONSFREE (consFreeSymresack)

static	SCIP_DECL_CONSTRANS (consTransSymresack)

static	SCIP_DECL_CONSINITLP (consInitlpSymresack)

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_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 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)

Macro Definition Documentation

◆ CONSHDLR_NAME

#define CONSHDLR_NAME "symresack"

◆ CONSHDLR_DESC

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

Definition at line 59 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY +40100

priority of the constraint handler for separation

Definition at line 60 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 61 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 62 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 63 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 64 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 65 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 68 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 69 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 70 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 71 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

Definition at line 73 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE

Definition at line 74 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ DEFAULT_PPSYMRESACK

#define DEFAULT_PPSYMRESACK FALSE

whether we allow upgrading to packing/partitioning symresacks

Definition at line 76 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ DEFAULT_CHECKALWAYSFEAS

#define DEFAULT_CHECKALWAYSFEAS TRUE

whether check routine returns always SCIP_FEASIBLE

Definition at line 77 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ ISFIXED0

#define ISFIXED0 ( x ) (SCIPvarGetUbLocal(x) < 0.5 ? TRUE : FALSE)

Definition at line 80 of file cons_symresack.c.

Referenced by propVariables().

◆ ISFIXED1

#define ISFIXED1 ( x ) (SCIPvarGetLbLocal(x) > 0.5 ? TRUE : FALSE)

Definition at line 81 of file cons_symresack.c.

Referenced by propVariables().

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

References packingUpgrade(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, 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 *	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
upgrade	pointer to store whether upgrade was successful

Definition at line 166 of file cons_symresack.c.

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

Referenced by consdataCreate(), and consdataFree().

◆ consdataCreate()

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

static

creates symresack constraint data

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

Parameters

scip	SCIP data structure
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

Definition at line 399 of file cons_symresack.c.

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

Referenced by packingUpgrade(), and SCIPcreateConsSymresack().

◆ initLP()

static SCIP_RETCODE initLP	(	SCIP *	scip,
		SCIP_CONS *	cons,
		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
infeasible	pointer to store whether we detected infeasibility

Definition at line 535 of file cons_symresack.c.

References FALSE, propVariables(), SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarsToRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPcreateEmptyRowCons(), SCIPfreeBufferArray, SCIPinfinity(), SCIPreleaseRow(), SCIPsnprintf(), and TRUE.

Referenced by consdataCreate(), and SCIP_DECL_CONSINITLP().

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

References addSymresackInequality(), FALSE, ISFIXED0, ISFIXED1, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIPaddConflictBinvar(), SCIPanalyzeConflictCons(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by initLP(), 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 796 of file cons_symresack.c.

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

Referenced by propVariables(), 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 852 of file cons_symresack.c.

References addSymresackInequality(), checkSymresackSolution(), FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArrayNull, SCIPisEfficacious(), and SCIPisGT().

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

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

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

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

Referenced by checkSymresackSolution(), and SCIPcreateSymbreakCons().

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteSymresack )

static

frees specific constraint data

Definition at line 1352 of file cons_symresack.c.

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

Referenced by SCIPcreateSymbreakCons().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeSymresack )

static

frees constraint handler

Definition at line 1367 of file cons_symresack.c.

References CONSHDLR_NAME, 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 1386 of file cons_symresack.c.

References CONSHDLR_NAME, 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, and SCIPgetTransformedVars().

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

References CONSHDLR_NAME, FALSE, initLP(), SCIP_CALL, SCIP_DECL_CONSSEPALP(), SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetName(), and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSTRANS().

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpSymresack )

static

separation method of constraint handler for LP solution

Definition at line 1500 of file cons_symresack.c.

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

Referenced by SCIP_DECL_CONSINITLP().

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolSymresack )

static

separation method of constraint handler for arbitrary primal solution

Definition at line 1565 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSENFOLP(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNVars(), 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 1632 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSENFOPS(), SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPBranchCands(), SCIPgetNVars(), 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 1696 of file cons_symresack.c.

References checkSymresackSolution(), CONSHDLR_NAME, FALSE, SCIP_CALL, SCIP_DECL_CONSENFORELAX(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, 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 1731 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSCHECK(), SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPBranchCands(), SCIPgetNVars(), 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 1793 of file cons_symresack.c.

References checkSymresackSolution(), CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSPROP(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), 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 1829 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, 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 1876 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, 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 1939 of file cons_symresack.c.

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

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 SCIPaddVarLocks(..., nlockspos, nlocksneg).
Symresack constraints may get violated if the variables with a positive coefficient in the FD inequality are rounded up, we therefor call SCIPaddVarLocks(..., nlocksneg, nlockspo ).

Definition at line 2054 of file cons_symresack.c.

References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSPRINT(), SCIP_OKAY, SCIPaddVarLocks(), SCIPconsGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSRESPROP().

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

References CONSHDLR_NAME, FALSE, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSGETVARS(), SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPinfoMessage(), SCIPvarGetName(), and TRUE.

Referenced by SCIP_DECL_CONSLOCK().

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsSymresack )

static

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

Definition at line 2179 of file cons_symresack.c.

References FALSE, 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 2208 of file cons_symresack.c.

References 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_CHECKALWAYSFEAS

◆ ISFIXED0

◆ ISFIXED1

Function Documentation

◆ consdataFree()

◆ packingUpgrade()

◆ consdataCreate()

◆ initLP()

◆ propVariables()

◆ addSymresackInequality()

◆ separateSymresackCovers()

◆ checkSymresackSolution()

◆ orbisackUpgrade()

◆ SCIP_DECL_CONSDELETE()

◆ SCIP_DECL_CONSFREE()

◆ SCIP_DECL_CONSTRANS()

◆ SCIP_DECL_CONSINITLP()

◆ 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_CONSPRINT()

◆ SCIP_DECL_CONSGETVARS()

◆ SCIP_DECL_CONSGETNVARS()