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(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" |
Definition at line 86 of file cons_symresack.c.
Referenced by consdataCreate(), SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), SCIP_DECL_CONSENFORELAX(), SCIP_DECL_CONSFREE(), SCIP_DECL_CONSHDLRCOPY(), SCIP_DECL_CONSINITLP(), SCIP_DECL_CONSINITSOL(), SCIP_DECL_CONSLOCK(), SCIP_DECL_CONSPRESOL(), SCIP_DECL_CONSPRINT(), SCIP_DECL_CONSPROP(), SCIP_DECL_CONSRESPROP(), SCIP_DECL_CONSSEPALP(), SCIP_DECL_CONSSEPASOL(), SCIP_DECL_CONSTRANS(), SCIPcreateConsSymresack(), and SCIPincludeConshdlrSymresack().
◆ 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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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().