Scippy

SCIP

Solving Constraint Integer Programs

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

◆ CONSHDLR_DESC

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

Definition at line 79 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   +40100

priority of the constraint handler for separation

Definition at line 80 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 81 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 82 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 83 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 84 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 85 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 88 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 89 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 90 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 91 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 93 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_EXHAUSTIVE

Definition at line 94 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 96 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 97 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 98 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ FIXED0

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

Definition at line 101 of file cons_symresack.c.

Referenced by checkFeasible(), and propVariables().

◆ FIXED1

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

Definition at line 102 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 103 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 104 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 107 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
scipSCIP data structure
consdatapointer to symresack constraint data

Definition at line 152 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
scipSCIP data structure
consdatapointer to store constraint data
permpermutation
varsvariables affected by permutation
nvarslength of permutation
checkmonotonicitycheck whether permutation is monotone
upgradepointer to store whether upgrade was successful

Definition at line 211 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
scipSCIP data structure
conshdlrsymresack constraint handler
consdatapointer to store constraint data
inputvarsinput variables of the constraint handler
inputnvarsinput number of variables of the constraint handler
inputperminput permutation of the constraint handler
ismodelconswhether the symresack is a model constraint

Definition at line 465 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
scipSCIP pointer
consconstraint
checkmonotonicityhas it been checked whether permutation is monotone for packing/partitioning symresacks?
infeasiblepointer to store whether we detected infeasibility

Definition at line 606 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
scipSCIP pointer
varsarray of variables affected by permutation
invperminverse of permutation
nvarsnumber of variables
startat which position to start (assuming previous positions are equal)
tempfixingsarray with at entry i the virtual fixing of variable vars[i]
tempfixentriesthe entries i that are virtually fixed until numfixentriesinit
numfixentriesinitthe number of virtually fixed entries
infeasiblepointer to store whether infeasibility is detected in these fixings
infeasibleentrypointer to store at which entry a (0, 1) pattern is found

Definition at line 810 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
scipSCIP pointer
consconstraint to be propagated
infeasiblepointer to store whether it was detected that the node is infeasible
ngenpointer to store number of generated bound strengthenings

Definition at line 931 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
scipSCIP pointer
consconstraint
nvarsnumber of variables
varsvariables
coeffscoefficient vector of inequality to be added
rhsright-hand side of inequality to be added
infeasiblepointer to store whether we detected infeasibility

Definition at line 1156 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
scipSCIP pointer
nvarsnumber of variables in symresack
objectivethe objective vector
permthe permutation (without fixed points) as an array
invpermthe inverse permutation as an array
maxcritpointer to the critical entry where optimality is found at
maxsoluvalpointer to store the optimal objective value

Definition at line 1211 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
scipSCIP pointer
nvarsnumber of variables in symresack
objectivethe objective vector
permthe permutation (without fixed points) as an array
invpermthe inverse permutation as an array
critcritical entry where optimality is found at
maxsolupointer to the optimal objective array

Definition at line 1332 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
scipSCIP pointer
consconstraint
consdataconstraint data
valssolution values of variables
ngenpointer to store the number of separated covers
infeasiblepointer to store whether we detected infeasibility

Definition at line 1441 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
scipSCIP pointer
consconstrained for which we check the solution
solsolution to be checked
resultpointer to store whether we detected infeasibility
printreasonwhether reason for infeasibility should be printed

Definition at line 1540 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
scipSCIP pointer
conspointer to hold the created constraint
namename of constraint
permpermutation
inputvarspermuted variables array
nvarssize of perm array
upgradewhether constraint was upgraded
ismodelconswhether the symresack is a model constraint
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiableis constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removableshould the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnodeshould the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.

Definition at line 1620 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 1785 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 1802 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 1817 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()

◆ 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 1947 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 1981 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()

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolSymresack  )
static

◆ 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 2166 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 2244 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

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckSymresack  )
static

feasibility check method of constraint handler for integral solutions

Definition at line 2363 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

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolSymresack  )
static

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropSymresack  )
static

◆ 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 2679 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

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseSymresack  )
static

◆ 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 2955 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 3003 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 3032 of file cons_symresack.c.

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

Referenced by SCIP_DECL_CONSGETVARS().