SCIP
Solving Constraint Integer Programs
cons_symresack.c File Reference
Detailed Description
constraint handler for symresack constraints
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(scip, x, bdchgidx) (SCIPgetVarUbAtIndex(scip, x, bdchgidx, FALSE) - SCIPgetVarLbAtIndex(scip, 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_RETCODE | replaceAggregatedVarsSymresack (SCIP *scip, SCIP_CONS *cons) |
| 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_CONSEXITPRE (consExitpreSymresack) |
| 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" |
Definition at line 86 of file cons_symresack.c.
◆ CONSHDLR_DESC
| #define CONSHDLR_DESC "symmetry breaking constraint handler relying on symresacks" |
Definition at line 87 of file cons_symresack.c.
◆ CONSHDLR_SEPAPRIORITY
| #define CONSHDLR_SEPAPRIORITY +40100 |
priority of the constraint handler for separation
Definition at line 88 of file cons_symresack.c.
◆ CONSHDLR_ENFOPRIORITY
| #define CONSHDLR_ENFOPRIORITY -1005200 |
priority of the constraint handler for constraint enforcing
Definition at line 89 of file cons_symresack.c.
◆ CONSHDLR_CHECKPRIORITY
| #define CONSHDLR_CHECKPRIORITY -1005200 |
priority of the constraint handler for checking feasibility
Definition at line 90 of file cons_symresack.c.
◆ 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.
◆ CONSHDLR_PROPFREQ
| #define CONSHDLR_PROPFREQ 5 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 92 of file cons_symresack.c.
◆ 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 94 of file cons_symresack.c.
◆ CONSHDLR_MAXPREROUNDS
| #define CONSHDLR_MAXPREROUNDS -1 |
maximal number of presolving rounds the constraint handler participates in (-1: no limit)
Definition at line 95 of file cons_symresack.c.
◆ CONSHDLR_DELAYSEPA
| #define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 96 of file cons_symresack.c.
◆ CONSHDLR_DELAYPROP
| #define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 97 of file cons_symresack.c.
◆ CONSHDLR_NEEDSCONS
| #define CONSHDLR_NEEDSCONS TRUE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 98 of file cons_symresack.c.
◆ CONSHDLR_PROP_TIMING
| #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
Definition at line 100 of file cons_symresack.c.
◆ CONSHDLR_PRESOLTIMING
| #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE |
Definition at line 101 of file cons_symresack.c.
◆ DEFAULT_PPSYMRESACK
| #define DEFAULT_PPSYMRESACK TRUE |
whether we allow upgrading to packing/partitioning symresacks
Definition at line 103 of file cons_symresack.c.
◆ DEFAULT_CHECKMONOTONICITY
| #define DEFAULT_CHECKMONOTONICITY TRUE |
check whether permutation is monotone when upgrading to packing/partitioning symresacks
Definition at line 104 of file cons_symresack.c.
◆ DEFAULT_FORCECONSCOPY
| #define DEFAULT_FORCECONSCOPY FALSE |
whether symresack constraints should be forced to be copied to sub SCIPs
Definition at line 105 of file cons_symresack.c.
◆ FIXED0
| #define FIXED0 1 /* When a variable is fixed to 0. */ |
Definition at line 108 of file cons_symresack.c.
◆ FIXED1
| #define FIXED1 2 /* When a variable is fixed to 1. */ |
Definition at line 109 of file cons_symresack.c.
◆ UNFIXED
| #define UNFIXED 3 /* When a variable is neither fixed to 0 or to 1. */ |
Definition at line 110 of file cons_symresack.c.
◆ NOINIT
| #define NOINIT |
Value:
0 /* A dummy entry for non-initialized variables.
* Must have value 0 because of SCIPallocCleanBufferArray. */
Definition at line 111 of file cons_symresack.c.
◆ ISFIXED
| #define ISFIXED | ( | scip, | |
| x, | |||
| bdchgidx | |||
| ) | (SCIPgetVarUbAtIndex(scip, x, bdchgidx, FALSE) - SCIPgetVarLbAtIndex(scip, x, bdchgidx, FALSE) < 0.5) |
Definition at line 113 of file cons_symresack.c.
Function Documentation
◆ consdataFree()
|
static |
frees a symresack constraint data
- Parameters
-
scip SCIP data structure consdata pointer to symresack constraint data
Definition at line 158 of file cons_symresack.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseVar().
Referenced by SCIP_DECL_CONSDELETE().
◆ packingUpgrade()
|
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 217 of file cons_symresack.c.
References 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().
◆ consdataCreate()
|
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 471 of file cons_symresack.c.
References CONSHDLR_NAME, FALSE, NULL, packingUpgrade(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcaptureVar(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBufferArrayNull, SCIPgetTransformedVar(), SCIPisTransformed(), SCIPmarkDoNotMultaggrVar(), and SCIPvarIsBinary().
Referenced by SCIPcreateConsSymresack().
◆ initLP()
|
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 612 of file cons_symresack.c.
References 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 SCIP_DECL_CONSINITLP().
◆ checkFeasible()
|
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 816 of file cons_symresack.c.
References FALSE, FIXED0, FIXED1, NOINIT, NULL, SCIP_OKAY, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and UNFIXED.
Referenced by propVariables().
◆ propVariables()
|
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 937 of file cons_symresack.c.
References 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 SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().
◆ addSymresackInequality()
|
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 1162 of file cons_symresack.c.
References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetName(), SCIPcreateEmptyRowCons(), SCIPflushRowExtensions(), SCIPinfinity(), SCIPreleaseRow(), SCIPsnprintf(), and TRUE.
Referenced by separateSymresackCovers().
◆ maximizeObjectiveSymresackStrict()
|
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 1217 of file cons_symresack.c.
References NULL, SCIP_CALL, SCIP_DEFAULT_INFINITY, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), and SCIPisLT().
Referenced by separateSymresackCovers().
◆ maximizeObjectiveSymresackCriticalEntry()
|
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 1338 of file cons_symresack.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPisGT().
Referenced by separateSymresackCovers().
◆ separateSymresackCovers()
|
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 1447 of file cons_symresack.c.
References addSymresackInequality(), FALSE, maximizeObjectiveSymresackCriticalEntry(), maximizeObjectiveSymresackStrict(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArrayNull, and SCIPisEfficacious().
Referenced by SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFORELAX(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().
◆ checkSymresackSolution()
|
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 1546 of file cons_symresack.c.
References NULL, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPinfoMessage(), and SCIPisFeasIntegral().
Referenced by SCIP_DECL_CONSCHECK(), and SCIP_DECL_CONSENFOPS().
◆ orbisackUpgrade()
|
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 1626 of file cons_symresack.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcreateConsOrbisack(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPvarIsBinary(), separate(), and TRUE.
Referenced by SCIPcreateSymbreakCons().
◆ replaceAggregatedVarsSymresack()
|
static |
replace aggregated variables by active variables
- Parameters
-
scip SCIP data structure cons constraint to be processed
Definition at line 1787 of file cons_symresack.c.
References NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_UNUSED, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIP_VARSTATUS_NEGATED, SCIPcaptureVar(), SCIPconsGetData(), SCIPgetBinvarRepresentative(), SCIPreleaseVar(), SCIPvarGetStatus(), and SCIPvarIsActive().
Referenced by SCIP_DECL_CONSEXITPRE().
◆ SCIP_DECL_CONSHDLRCOPY()
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 1837 of file cons_symresack.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrSymresack(), and TRUE.
◆ SCIP_DECL_CONSDELETE()
|
static |
frees specific constraint data
Definition at line 1854 of file cons_symresack.c.
References consdataFree(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().
◆ SCIP_DECL_CONSFREE()
|
static |
frees constraint handler
Definition at line 1869 of file cons_symresack.c.
References CONSHDLR_NAME, NULL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPfreeBlockMemory.
◆ SCIP_DECL_CONSTRANS()
|
static |
transforms constraint data into data belonging to the transformed problem
Definition at line 1888 of file cons_symresack.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, 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().
◆ SCIP_DECL_CONSINITLP()
|
static |
LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)
Definition at line 1999 of file cons_symresack.c.
References CONSHDLR_NAME, FALSE, initLP(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.
◆ SCIP_DECL_CONSINITSOL()
|
static |
solving process initialization method of constraint handler (called when branch and bound process is about to begin)
Definition at line 2033 of file cons_symresack.c.
References CONSHDLR_NAME, NULL, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetData(), and SCIPconshdlrGetName().
◆ SCIP_DECL_CONSSEPALP()
|
static |
separation method of constraint handler for LP solution
Definition at line 2069 of file cons_symresack.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPBranchCands(), SCIPgetSolVals(), and separateSymresackCovers().
◆ SCIP_DECL_CONSSEPASOL()
|
static |
separation method of constraint handler for arbitrary primal solution
Definition at line 2143 of file cons_symresack.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSolVals(), and separateSymresackCovers().
◆ SCIP_DECL_CONSENFOLP()
|
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 2218 of file cons_symresack.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPBranchCands(), SCIPgetSolVals(), and separateSymresackCovers().
◆ SCIP_DECL_CONSENFOPS()
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 2296 of file cons_symresack.c.
References checkSymresackSolution(), CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.
◆ SCIP_DECL_CONSENFORELAX()
|
static |
constraint enforcing method of constraint handler for relaxation solutions
To check feasibility, we separate cover inequalities.
Definition at line 2339 of file cons_symresack.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPBranchCands(), SCIPgetSolVals(), and separateSymresackCovers().
◆ SCIP_DECL_CONSCHECK()
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 2415 of file cons_symresack.c.
References checkSymresackSolution(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.
◆ SCIP_DECL_CONSPROP()
|
static |
domain propagation method of constraint handler
Definition at line 2452 of file cons_symresack.c.
References CONSHDLR_NAME, FALSE, NULL, propVariables(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPconshdlrGetName(), and SCIPdebugMsg.
◆ SCIP_DECL_CONSPRESOL()
|
static |
presolving method of constraint handler
Definition at line 2499 of file cons_symresack.c.
References CONSHDLR_NAME, FALSE, NULL, propVariables(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPdelCons(), and TRUE.
◆ SCIP_DECL_CONSRESPROP()
|
static |
Propagation resolution for conflict analysis
Definition at line 2562 of file cons_symresack.c.
References CONSHDLR_NAME, FALSE, ISFIXED, NULL, REALABS, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconsGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetVarLbAtIndex(), and SCIPgetVarUbAtIndex().
◆ SCIP_DECL_CONSEXITPRE()
|
static |
presolving deinitialization method of constraint handler (called after presolving has been finished)
Definition at line 2720 of file cons_symresack.c.
References CONSHDLR_NAME, NULL, replaceAggregatedVarsSymresack(), SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetName().
◆ SCIP_DECL_CONSLOCK()
|
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 2750 of file cons_symresack.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPconsGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.
◆ SCIP_DECL_CONSCOPY()
|
static |
constraint copying method of constraint handler
Definition at line 2801 of file cons_symresack.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPcreateConsSymresack(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetVarCopy(), separate(), and TRUE.
◆ SCIP_DECL_CONSPARSE()
|
static |
constraint parsing method of constraint handler
Definition at line 2870 of file cons_symresack.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPcreateConsBasicSymresack(), SCIPerrorMessage, SCIPfreeBufferArray, SCIPparseVarName(), SCIPreallocBufferArray, SCIPskipSpace(), SCIPstrToIntValue(), and TRUE.
◆ SCIP_DECL_CONSPRINT()
|
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 3051 of file cons_symresack.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPinfoMessage(), SCIPwriteVarName(), and TRUE.
◆ SCIP_DECL_CONSGETVARS()
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 3099 of file cons_symresack.c.
References FALSE, NULL, SCIP_OKAY, SCIPconsGetData(), and TRUE.
◆ SCIP_DECL_CONSGETNVARS()
|
static |
constraint method of constraint handler which returns the number of variables (if possible)
Definition at line 3128 of file cons_symresack.c.
References NULL, SCIP_OKAY, SCIPconsGetData(), and TRUE.