SCIP
Solving Constraint Integer Programs
cons_orbitope.c File Reference
Detailed Description
constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric group
The type of constraints of this constraint handler is described in cons_orbitope.h.
The details of the method implemented here are described in the following papers.
Packing and Partitioning Orbitopes
Volker Kaibel and Marc E. Pfetsch,
Math. Program. 114, No. 1, 1-36 (2008)
Among other things, this paper describes so-called shifted column inequalities of the following form \(x(S) \leq x(B)\), where \(S\) is a so-called shifted column and \(B\) is a so-called bar. These inequalities can be used to handle symmetry and they are separated in this constraint handler. We use the linear time separation algorithm of the paper.
Orbitopal Fixing
Volker Kaibel, Matthias Peinhardt, and Marc E. Pfetsch,
Discrete Optimization 8, No. 4, 595-610 (2011) (A preliminary version appears in Proc. IPCO 2007.)
In this paper a linear time propagation algorithm is described, a variant of which is implemented here. The implemented variant does not run in linear time, but is very fast in practice.
| here | paper |
| nspcons | p |
| nblocks | q |
| vars | x |
| vals | A^\star |
| weights | \omega |
| cases | \tau |
| fixtriangle | – |
| resolveprop | – |
| firstnonzeros | \mu |
| lastones | \alpha |
| frontiersteps | \Gamma |
Orbitopal fixing for the full (sub-)orbitope and application to the Unit Commitment Problem
Pascale Bendotti, Pierre Fouilhoux, and Cecile Rottner,
Optimization Online: http://www.optimization-online.org/DB_HTML/2017/10/6301.html
Two linear time propagation algorithms for full orbitopes are described in this paper, a static version and a dynamic one. While the static version uses a fixed variable order, the dynamic version determines the variable order during the solving process via branching descisions. We implemented the static version as well as a modified version of the dynamic one. The reason for the latter is to simplify the compatibility with full orbitope cutting planes.
Note, however, that the dynamic version may lead to conflicts if orbitopes are copied to subSCIPs. Since the dynamic version is based on branching decisions, which may be different in main SCIP and subSCIPs, orbitopes using the dynamic algorithm are not allowed to be copied. However, as a user might use orbitopes to enforce a certain variable ordering in a solution, we distinguish whether an orbitope is a model constraint or not. If it is a model constraint, we assume that a variable order has already been fixed and disable the dynamic algorithm. In this case, orbitope constraints are copied to subSCIPs. If it is not a model constraint, the orbitope was added to handle symmetries but not to enforce a solution to have a certain structure. In this case, the dynamic algorithm can be used and we do not copy orbitope constraints to subSCIPs.
Polytopes associated with symmetry handling
Christopher Hojny and Marc E. Pfetsch,
Math. Program. (2018)
In this paper, a linear time separation algorithm for orbisacks (full orbitopes with two columnes) is described. We use this algorithm for every pair of adjacent columns within the orbitope as well as a version that is adapted to the reordering based on the dynamic full orbitope propagation algorithm to ensure validity of binary points via cutting planes.
Definition in file cons_orbitope.c.
#include "blockmemshell/memory.h"#include "scip/cons_orbisack.h"#include "scip/cons_orbitope.h"#include "scip/cons_setppc.h"#include "scip/pub_cons.h"#include "scip/pub_message.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_copy.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_probing.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 "orbitope" |
| #define | CONSHDLR_DESC "symmetry breaking constraint handler relying on (partitioning/packing) orbitopes" |
| #define | CONSHDLR_SEPAPRIORITY +40100 |
| #define | CONSHDLR_ENFOPRIORITY -1005200 |
| #define | CONSHDLR_CHECKPRIORITY -1005200 |
| #define | CONSHDLR_SEPAFREQ -1 |
| #define | CONSHDLR_PROPFREQ 1 |
| #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_MEDIUM |
| #define | DEFAULT_PPORBITOPE TRUE |
| #define | DEFAULT_SEPAFULLORBITOPE FALSE |
| #define | DEFAULT_USEDYNAMICPROP TRUE |
| #define | DEFAULT_FORCECONSCOPY FALSE |
Functions | |
| static SCIP_RETCODE | consdataFree (SCIP *scip, SCIP_CONSDATA **consdata, SCIP_Bool usedynamicprop) |
| static SCIP_RETCODE | consdataCreate (SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR ***vars, int nspcons, int nblocks, SCIP_ORBITOPETYPE orbitopetype, SCIP_Bool resolveprop, SCIP_Bool usedynamicprop, SCIP_Bool ismodelcons) |
| static SCIP_RETCODE | strengthenOrbitopeConstraint (SCIP *scip, SCIP_VAR ***vars, int *nrows, int ncols, SCIP_ORBITOPETYPE *type) |
| static void | copyValues (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol) |
| static void | computeSCTable (SCIP *scip, int nspcons, int nblocks, SCIP_Real **weights, int **cases, SCIP_Real **vals) |
| static SCIP_RETCODE | fixTriangle (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars) |
| static SCIP_RETCODE | separateSCIs (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *infeasible, int *nfixedvars, int *ncuts) |
| static SCIP_RETCODE | propagatePackingPartitioningCons (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars) |
| static SCIP_RETCODE | computeDynamicRowOrder (SCIP *scip, SCIP_HASHMAP *rowindexmap, SCIP_Bool *rowused, int *roworder, int nrows, int ncols, int *maxrowlabel) |
| static SCIP_RETCODE | findLexMinFace (SCIP_VAR ***vars, int **lexminfixes, int *roworder, int *minfixedrowlexmin, SCIP_Bool *infeasible, int m, int n, int nrowsused, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool resprop) |
| static SCIP_RETCODE | findLexMaxFace (SCIP_VAR ***vars, int **lexmaxfixes, int *roworder, int *minfixedrowlexmax, SCIP_Bool *infeasible, int m, int n, int nrowsused, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool resprop) |
| static SCIP_RETCODE | propagateFullOrbitopeCons (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars, SCIP_Bool dynamic) |
| static SCIP_RETCODE | propagateCons (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars, SCIP_Bool usedynamicprop) |
| static SCIP_RETCODE | resolvePropagationFullOrbitope (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, int inferinfo, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result) |
| static SCIP_RETCODE | resolvePropagation (SCIP *scip, SCIP_CONS *cons, int inferinfo, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result) |
| static SCIP_RETCODE | enfopsPackingPartitioningOrbitopeSolution (SCIP *scip, SCIP_CONS *cons, SCIP_RESULT *result) |
| static SCIP_RETCODE | checkPackingPartitioningOrbitopeSolution (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool printreason) |
| static SCIP_RETCODE | checkFullOrbitopeSolution (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool *feasible) |
| static SCIP_RETCODE | separateCoversOrbisack (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool dynamic, int *ngen, SCIP_Bool *infeasible) |
| static SCIP_RETCODE | separateConstraints (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool enforce) |
| static SCIP_RETCODE | checkRedundantCons (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *redundant) |
| static | SCIP_DECL_CONSHDLRCOPY (conshdlrCopyOrbitope) |
| static | SCIP_DECL_CONSFREE (consFreeOrbitope) |
| static | SCIP_DECL_CONSDELETE (consDeleteOrbitope) |
| static | SCIP_DECL_CONSTRANS (consTransOrbitope) |
| static | SCIP_DECL_CONSSEPALP (consSepalpOrbitope) |
| static | SCIP_DECL_CONSSEPASOL (consSepasolOrbitope) |
| static | SCIP_DECL_CONSENFOLP (consEnfolpOrbitope) |
| static | SCIP_DECL_CONSENFORELAX (consEnforelaxOrbitope) |
| static | SCIP_DECL_CONSENFOPS (consEnfopsOrbitope) |
| static | SCIP_DECL_CONSCHECK (consCheckOrbitope) |
| static | SCIP_DECL_CONSPROP (consPropOrbitope) |
| static | SCIP_DECL_CONSPRESOL (consPresolOrbitope) |
| static | SCIP_DECL_CONSRESPROP (consRespropOrbitope) |
| static | SCIP_DECL_CONSLOCK (consLockOrbitope) |
| static | SCIP_DECL_CONSPRINT (consPrintOrbitope) |
| static | SCIP_DECL_CONSCOPY (consCopyOrbitope) |
| static | SCIP_DECL_CONSPARSE (consParseOrbitope) |
| static | SCIP_DECL_CONSGETVARS (consGetVarsOrbitope) |
| static | SCIP_DECL_CONSGETNVARS (consGetNVarsOrbitope) |
| SCIP_RETCODE | SCIPincludeConshdlrOrbitope (SCIP *scip) |
| SCIP_RETCODE | SCIPcreateConsOrbitope (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nspcons, int nblocks, SCIP_Bool resolveprop, 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 | SCIPcreateConsBasicOrbitope (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nspcons, int nblocks, SCIP_Bool resolveprop, SCIP_Bool ismodelcons) |
Macro Definition Documentation
◆ CONSHDLR_NAME
| #define CONSHDLR_NAME "orbitope" |
Definition at line 120 of file cons_orbitope.c.
Referenced by SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSENFOPS(), SCIP_DECL_CONSFREE(), SCIP_DECL_CONSHDLRCOPY(), SCIP_DECL_CONSLOCK(), SCIP_DECL_CONSPRESOL(), SCIP_DECL_CONSPRINT(), SCIP_DECL_CONSPROP(), SCIP_DECL_CONSTRANS(), SCIPcreateConsOrbitope(), SCIPincludeConshdlrOrbitope(), and separateConstraints().
◆ CONSHDLR_DESC
| #define CONSHDLR_DESC "symmetry breaking constraint handler relying on (partitioning/packing) orbitopes" |
Definition at line 121 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ CONSHDLR_SEPAPRIORITY
| #define CONSHDLR_SEPAPRIORITY +40100 |
priority of the constraint handler for separation
Definition at line 122 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ CONSHDLR_ENFOPRIORITY
| #define CONSHDLR_ENFOPRIORITY -1005200 |
priority of the constraint handler for constraint enforcing
Definition at line 123 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ CONSHDLR_CHECKPRIORITY
| #define CONSHDLR_CHECKPRIORITY -1005200 |
priority of the constraint handler for checking feasibility
Definition at line 124 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ CONSHDLR_SEPAFREQ
| #define CONSHDLR_SEPAFREQ -1 |
frequency for separating cuts; zero means to separate only in the root node
Definition at line 125 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ CONSHDLR_PROPFREQ
| #define CONSHDLR_PROPFREQ 1 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 126 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ 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 127 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ CONSHDLR_MAXPREROUNDS
| #define CONSHDLR_MAXPREROUNDS -1 |
maximal number of presolving rounds the constraint handler participates in (-1: no limit)
Definition at line 130 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ CONSHDLR_DELAYSEPA
| #define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 131 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ CONSHDLR_DELAYPROP
| #define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 132 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ CONSHDLR_NEEDSCONS
| #define CONSHDLR_NEEDSCONS TRUE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 133 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ CONSHDLR_PROP_TIMING
| #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
propagation timing mask of the constraint handler
Definition at line 135 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ CONSHDLR_PRESOLTIMING
| #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM |
presolving timing of the constraint handler (fast, medium, or exhaustive)
Definition at line 136 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ DEFAULT_PPORBITOPE
| #define DEFAULT_PPORBITOPE TRUE |
whether we check if full orbitopes can be strengthened to packing/partitioning orbitopes
Definition at line 138 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ DEFAULT_SEPAFULLORBITOPE
| #define DEFAULT_SEPAFULLORBITOPE FALSE |
whether we separate inequalities for full orbitopes
Definition at line 139 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ DEFAULT_USEDYNAMICPROP
| #define DEFAULT_USEDYNAMICPROP TRUE |
whether we use a dynamic version of the propagation routine
Definition at line 140 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
◆ DEFAULT_FORCECONSCOPY
| #define DEFAULT_FORCECONSCOPY FALSE |
whether orbitope constraints should be forced to be copied to sub SCIPs
Definition at line 141 of file cons_orbitope.c.
Referenced by SCIPincludeConshdlrOrbitope().
Function Documentation
◆ consdataFree()
|
static |
frees an orbitope constraint data
- Parameters
-
scip SCIP data structure consdata pointer to orbitope constraint data usedynamicprop whether we use a dynamic version of the propagation routine
Definition at line 185 of file cons_orbitope.c.
References consdataCreate(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, and SCIPhashmapFree().
Referenced by SCIP_DECL_CONSDELETE().
◆ consdataCreate()
|
static |
creates orbitope constraint data
- Parameters
-
scip SCIP data structure consdata pointer to store constraint data vars variables array, must have size nspcons x nblocks nspcons number of set partitioning (packing) constraints <=> p nblocks number of symmetric variable blocks <=> q orbitopetype type of orbitope constraint resolveprop should propagation be resolved? usedynamicprop whether we use a dynamic version of the propagation routine ismodelcons whether the orbitope is a model constraint
Definition at line 234 of file cons_orbitope.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPduplicateBlockMemoryArray, SCIPgetTransformedVar(), SCIPhashmapCreate(), SCIPhashmapInsert(), SCIPisTransformed(), SCIPmarkDoNotMultaggrVar(), and strengthenOrbitopeConstraint().
Referenced by consdataFree(), SCIP_DECL_CONSTRANS(), and SCIPcreateConsOrbitope().
◆ strengthenOrbitopeConstraint()
|
static |
strengthen full orbitopes to packing/partitioning orbitopes if possible
- Parameters
-
scip SCIP data structure vars variable matrix of orbitope constraint nrows pointer to number of rows of variable matrix ncols number of columns of variable matrix type pointer to store type of orbitope constraint after strengthening
Definition at line 318 of file cons_orbitope.c.
References copyValues(), NULL, r, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIP_ORBITOPETYPE_PACKING, SCIP_ORBITOPETYPE_PARTITIONING, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PARTITIONING, SCIPABORT, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPerrorMessage, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetNTotalVars(), SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), SCIPinfoMessage(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by consdataCreate(), and SCIPcreateConsOrbitope().
◆ copyValues()
|
static |
copies the variables values from the solution to the constraint data structure
- Parameters
-
scip the SCIP data structure consdata the constraint data sol a primal solution or NULL for the current LP optimum
Definition at line 668 of file cons_orbitope.c.
References computeSCTable(), NULL, and SCIPgetSolVal().
Referenced by checkPackingPartitioningOrbitopeSolution(), enfopsPackingPartitioningOrbitopeSolution(), separateConstraints(), and strengthenOrbitopeConstraint().
◆ computeSCTable()
|
static |
compute the dynamic programming table for SC
Build up dynamic programming table in order to find SCs with minimum weight.
The values of the minimal SCIs are stored in weights. The array cases[i][j] stores which of the cases were applied to get weights[i][j]. Here, 3 means that we have reached the upper limit.
We assume that the upper right triangle is fixed to 0. Hence we can perform the computation a bit more efficient.
- Parameters
-
scip SCIP pointer nspcons number of set partitioning (packing) constraints <=> p nblocks number of symmetric variable blocks <=> q weights SC weight table cases indicator of the SC cases vals current solution
Definition at line 704 of file cons_orbitope.c.
References fixTriangle(), NULL, SCIP_Real, and SCIPisLT().
Referenced by checkPackingPartitioningOrbitopeSolution(), copyValues(), enfopsPackingPartitioningOrbitopeSolution(), resolvePropagation(), and separateSCIs().
◆ fixTriangle()
|
static |
fix upper right triangle if necessary
- Parameters
-
scip SCIP data structure cons constraint to be processed infeasible pointer to store TRUE, if the node can be cut off nfixedvars pointer to add up the number of found domain reductions
Definition at line 799 of file cons_orbitope.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPfixVar(), SCIPvarGetUbGlobal(), separateSCIs(), and TRUE.
Referenced by computeSCTable(), enfopsPackingPartitioningOrbitopeSolution(), propagatePackingPartitioningCons(), and separateSCIs().
◆ separateSCIs()
|
static |
separates shifted column inequalities according to the solution stored in consdata->vals
- Parameters
-
scip the SCIP data structure conshdlr constraint handler cons constraint consdata the constraint data infeasible whether we detected infeasibility nfixedvars pointer to store the number of variables fixed ncuts pointer to store number of separated SCIs
Definition at line 882 of file cons_orbitope.c.
References computeSCTable(), FALSE, fixTriangle(), NULL, propagatePackingPartitioningCons(), SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarsToRow(), SCIPcreateEmptyRowConshdlr(), SCIPinfinity(), SCIPisEfficacious(), SCIPisSumEQ(), SCIPreleaseRow(), SCIPsnprintf(), and TRUE.
Referenced by fixTriangle(), and separateConstraints().
◆ propagatePackingPartitioningCons()
|
static |
propagation method for a single packing or partitioning orbitope constraint
- Parameters
-
scip SCIP data structure cons constraint to be processed infeasible pointer to store TRUE, if the node can be cut off nfixedvars pointer to add up the number of found domain reductions
Definition at line 1042 of file cons_orbitope.c.
References computeDynamicRowOrder(), FALSE, fixTriangle(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_ORBITOPETYPE_PACKING, SCIP_ORBITOPETYPE_PARTITIONING, SCIP_STAGE_SOLVING, SCIPaddConflictBinvar(), SCIPallocBufferArray, SCIPallowStrongDualReds(), SCIPanalyzeConflictCons(), SCIPconsGetData(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetStage(), SCIPinferBinvarCons(), SCIPinitConflictAnalysis(), SCIPinProbing(), SCIPisConflictAnalysisApplicable(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propagateCons(), and separateSCIs().
◆ computeDynamicRowOrder()
|
static |
- Parameters
-
scip SCIP pointer rowindexmap map of variables to indices in orbitope vars matrix rowused bitset marking whether a row has been considered in the new order roworder reordering of the rows w.r.t. branching decisions nrows number of rows in orbitope ncols number of columns in orbitope maxrowlabel maximum row label in ordering
Definition at line 1404 of file cons_orbitope.c.
References findLexMinFace(), NULL, SCIP_BOUNDCHGTYPE_BRANCHING, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPboundchgGetBoundchgtype(), SCIPboundchgGetVar(), SCIPdomchgGetBoundchg(), SCIPdomchgGetNBoundchgs(), SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPnodeGetDepth(), SCIPnodeGetDomchg(), SCIPnodeGetParent(), SCIPvarGetType(), and TRUE.
Referenced by propagateFullOrbitopeCons(), and propagatePackingPartitioningCons().
◆ findLexMinFace()
|
static |
- Parameters
-
vars variable matrix lexminfixes fixings characterzing lex-min face roworder dynamic row order minfixedrowlexmin index of minimum fixed row for each column or NULL (if in prop) infeasible pointer to store whether infeasibility has been detected or NULL (if in resprop) m number of rows in vars n number of columns in vars nrowsused number of rows considered in propagation bdchgidx bdchgidx in resprop or NULL (if not in resprop) resprop whether we are in resprop (TRUE) or prop (FALSE)
Definition at line 1497 of file cons_orbitope.c.
References FALSE, findLexMaxFace(), NULL, SCIP_OKAY, SCIPvarGetUbAtIndex(), SCIPvarGetUbLocal(), and TRUE.
Referenced by computeDynamicRowOrder(), propagateFullOrbitopeCons(), and resolvePropagationFullOrbitope().
◆ findLexMaxFace()
|
static |
- Parameters
-
vars variable matrix lexmaxfixes fixings characterzing lex-max face roworder dynamic row order minfixedrowlexmax index of minimum fixed row for each column or NULL (if in prop) infeasible pointer to store whether infeasibility has been detected or NULL (if in resprop) m number of rows in vars n number of columns in vars nrowsused number of rows considered in propagation bdchgidx bdchgidx in resprop or NULL (if not in resprop) resprop whether we are in resprop (TRUE) or prop (FALSE)
Definition at line 1616 of file cons_orbitope.c.
References FALSE, NULL, propagateFullOrbitopeCons(), SCIP_OKAY, SCIPvarGetLbAtIndex(), SCIPvarGetLbLocal(), and TRUE.
Referenced by findLexMinFace(), propagateFullOrbitopeCons(), and resolvePropagationFullOrbitope().
◆ propagateFullOrbitopeCons()
|
static |
propagation method for a single packing or partitioning orbitope constraint
- Parameters
-
scip SCIP data structure cons constraint to be processed infeasible pointer to store TRUE, if the node can be cut off nfixedvars pointer to add up the number of found domain reductions dynamic whether we use a dynamic propagation routine
Definition at line 1732 of file cons_orbitope.c.
References computeDynamicRowOrder(), FALSE, findLexMaxFace(), findLexMinFace(), NULL, propagateCons(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIPallocBufferArray, SCIPallowStrongDualReds(), SCIPconsGetData(), SCIPfreeBufferArray, SCIPinferBinvarCons(), SCIPinProbing(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by findLexMaxFace(), and propagateCons().
◆ propagateCons()
|
static |
propagation method for a single orbitope constraint
- Parameters
-
scip SCIP data structure cons constraint to be processed infeasible pointer to store TRUE, if the node can be cut off nfixedvars pointer to add up the number of found domain reductions usedynamicprop whether we use a dynamic version of the propagation routine
Definition at line 1903 of file cons_orbitope.c.
References NULL, propagateFullOrbitopeCons(), propagatePackingPartitioningCons(), resolvePropagationFullOrbitope(), SCIP_CALL, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIP_ORBITOPETYPE_PACKING, SCIP_ORBITOPETYPE_PARTITIONING, and SCIPconsGetData().
Referenced by propagateFullOrbitopeCons(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().
◆ resolvePropagationFullOrbitope()
|
static |
Propagation conflict resolving method of propagator
In this function we use that all variable reductions that can be found by the propagation algorithm are only due to the fixed variables that are in or above the minimum fixed row of each pair of adjacent columns of the lexmin and lexmax matrices.
Since the storage of an integer is not enough to store the complete information about the fixing, we have to use the linear time algorithm for finding the lexmin and lexmax matrices and determine from this the minimum fixed rows.
- Parameters
-
scip SCIP data structure conshdlr constraint handler of the corresponding constraint cons constraint that inferred the bound change inferinfo inference information bdchgidx bound change index (time stamp of bound change), or NULL for current time result pointer to store the result of the propagation conflict resolving call
Definition at line 1949 of file cons_orbitope.c.
References FALSE, findLexMaxFace(), findLexMinFace(), MAX, NULL, resolvePropagation(), SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIP_SUCCESS, SCIPaddConflictBinvar(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPfreeBufferArray, SCIPvarGetLbAtIndex(), SCIPvarGetUbAtIndex(), and TRUE.
Referenced by propagateCons(), and SCIP_DECL_CONSRESPROP().
◆ resolvePropagation()
|
static |
Propagation conflict resolving method of propagator
In this function we use that the propagation method above implicitly propagates SCIs, i.e., every fixing can also be gotten via an SCI-fixing.
Since the storage of an integer is not enough to store the complete information about the fixing nor a complete shifted column, we have to use the linear time algorithm for SCIs.
The inferinfo integer is set as follows:
- If a shifted column is fixed to 0 and the corresponding bar does not necessarily has value 1 then we fix these entries to 0 and inferinfo is i * nblocks + j, where (i,j) is the leader of the bar. The SCI depends on whether i is in Gamma or not (see Lemma 1 in the paper and the comments above).
- If a bar has value 1 and the shifted column has one entry that is not fixed, it can be fixed to 1 and inferinfo is (nspcons*nblocks) + i * nblocks + j, where (i,j) is the leader of the bar; see Proposition 1 (2c).
- Parameters
-
scip SCIP data structure cons constraint that inferred the bound change inferinfo inference information bdchgidx bound change index (time stamp of bound change), or NULL for current time result pointer to store the result of the propagation conflict resolving call
Definition at line 2139 of file cons_orbitope.c.
References computeSCTable(), enfopsPackingPartitioningOrbitopeSolution(), FALSE, NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_ORBITOPETYPE_PARTITIONING, SCIP_Real, SCIP_SUCCESS, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconsGetData(), SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), and SCIPsnprintf().
Referenced by resolvePropagationFullOrbitope(), and SCIP_DECL_CONSRESPROP().
◆ enfopsPackingPartitioningOrbitopeSolution()
|
static |
check packing/partitioning orbitope solution for feasibility
- Parameters
-
scip SCIP data structure cons pointer to orbitope constraint result pointer to store the result of the enforcing call
Definition at line 2414 of file cons_orbitope.c.
References checkPackingPartitioningOrbitopeSolution(), computeSCTable(), copyValues(), FALSE, fixTriangle(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPisGT(), and SCIPisIntegral().
Referenced by resolvePropagation(), and SCIP_DECL_CONSENFOPS().
◆ checkPackingPartitioningOrbitopeSolution()
|
static |
check packing/partitioning orbitope solution for feasibility
- Parameters
-
scip SCIP data structure cons pointer to orbitope constraint sol solution to be checked result pointer to store the result of the enforcing call printreason whether reason for infeasibility should be printed
Definition at line 2508 of file cons_orbitope.c.
References checkFullOrbitopeSolution(), computeSCTable(), copyValues(), NULL, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPinfoMessage(), SCIPisFeasIntegral(), SCIPisFeasZero(), SCIPisGT(), and SCIPvarGetName().
Referenced by enfopsPackingPartitioningOrbitopeSolution(), and SCIP_DECL_CONSCHECK().
◆ checkFullOrbitopeSolution()
|
static |
check full orbitope solution for feasibility
- Parameters
-
scip SCIP data structure cons constraint to process sol solution to be checked printreason whether reason for infeasibility should be printed feasible memory address to store whether solution is feasible
Definition at line 2654 of file cons_orbitope.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcheckSolutionOrbisack(), SCIPconsGetData(), SCIPfreeBufferArray, separateCoversOrbisack(), and TRUE.
Referenced by checkPackingPartitioningOrbitopeSolution(), SCIP_DECL_CONSCHECK(), and SCIP_DECL_CONSENFOPS().
◆ separateCoversOrbisack()
|
static |
separate orbisack cover inequalities
- Parameters
-
scip SCIP data structure cons constraint to process sol solution to separate (NULL for the LP solution) dynamic whether we use a dynamic row order ngen pointer to store number of generated cuts infeasible pointer to store whether infeasibility has been detected
Definition at line 2713 of file cons_orbitope.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPcreateEmptyRowCons(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetSolVal(), SCIPinfinity(), SCIPisEfficacious(), SCIPprintRow(), SCIPreleaseRow(), separateConstraints(), and TRUE.
Referenced by checkFullOrbitopeSolution(), and separateConstraints().
◆ separateConstraints()
|
static |
separate or enforce constraints
- Parameters
-
scip SCIP data structure conshdlr constraint handler conss constraints to process nconss number of constraints nusefulconss number of useful (non-obsolete) constraints to process sol solution to separate (NULL for the LP solution) result pointer to store the result (should be initialized) enforce whether we enforce orbitope constraints
Definition at line 2858 of file cons_orbitope.c.
References checkRedundantCons(), CONSHDLR_NAME, copyValues(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_ORBITOPETYPE_PACKING, SCIP_ORBITOPETYPE_PARTITIONING, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, separateCoversOrbisack(), and separateSCIs().
Referenced by SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFORELAX(), SCIP_DECL_CONSSEPALP(), SCIP_DECL_CONSSEPASOL(), and separateCoversOrbisack().
◆ checkRedundantCons()
|
static |
check whether all variables in an orbitope constraint are fixed
- Parameters
-
scip SCIP data structure cons constraint to be processed redundant pointer to store whether constraint is redundant (contains no active vars)
Definition at line 2947 of file cons_orbitope.c.
References FALSE, NULL, SCIP_DECL_CONSHDLRCOPY(), SCIP_OKAY, SCIPconsGetData(), SCIPvarIsActive(), and TRUE.
Referenced by SCIP_DECL_CONSPRESOL(), and separateConstraints().
◆ SCIP_DECL_CONSHDLRCOPY()
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 2998 of file cons_orbitope.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrOrbitope(), and TRUE.
Referenced by checkRedundantCons().
◆ SCIP_DECL_CONSFREE()
|
static |
frees constraint handler
Definition at line 3014 of file cons_orbitope.c.
References CONSHDLR_NAME, NULL, SCIP_DECL_CONSDELETE(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPfreeBlockMemory.
Referenced by SCIP_DECL_CONSHDLRCOPY().
◆ SCIP_DECL_CONSDELETE()
|
static |
frees specific constraint data
Definition at line 3032 of file cons_orbitope.c.
References consdataFree(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSTRANS(), SCIP_OKAY, SCIPconshdlrGetData(), and SCIPconshdlrGetName().
Referenced by SCIP_DECL_CONSFREE().
◆ SCIP_DECL_CONSTRANS()
|
static |
transforms constraint data into data belonging to the transformed problem
Definition at line 3049 of file cons_orbitope.c.
References consdataCreate(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSSEPALP(), SCIP_OKAY, SCIP_STAGE_TRANSFORMING, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateCons(), and SCIPgetStage().
Referenced by SCIP_DECL_CONSDELETE().
◆ SCIP_DECL_CONSSEPALP()
|
static |
separation method of constraint handler for LP solutions
Definition at line 3083 of file cons_orbitope.c.
References FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSSEPASOL(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetNLPBranchCands(), and separateConstraints().
Referenced by SCIP_DECL_CONSTRANS().
◆ SCIP_DECL_CONSSEPASOL()
|
static |
separation method of constraint handler for arbitrary primal solutions
Definition at line 3106 of file cons_orbitope.c.
References FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSENFOLP(), SCIP_DIDNOTFIND, SCIP_OKAY, SCIPconshdlrGetName(), SCIPdebugMsg, and separateConstraints().
Referenced by SCIP_DECL_CONSSEPALP().
◆ SCIP_DECL_CONSENFOLP()
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 3124 of file cons_orbitope.c.
References NULL, SCIP_CALL, SCIP_DECL_CONSENFORELAX(), SCIP_FEASIBLE, SCIP_OKAY, SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetNLPBranchCands(), separateConstraints(), and TRUE.
Referenced by SCIP_DECL_CONSSEPASOL().
◆ SCIP_DECL_CONSENFORELAX()
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 3145 of file cons_orbitope.c.
References NULL, SCIP_CALL, SCIP_DECL_CONSENFOPS(), SCIP_FEASIBLE, SCIP_OKAY, SCIPconshdlrGetName(), SCIPdebugMsg, separateConstraints(), and TRUE.
Referenced by SCIP_DECL_CONSENFOLP().
◆ SCIP_DECL_CONSENFOPS()
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 3163 of file cons_orbitope.c.
References checkFullOrbitopeSolution(), CONSHDLR_NAME, enfopsPackingPartitioningOrbitopeSolution(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSCHECK(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_ORBITOPETYPE_PACKING, SCIP_ORBITOPETYPE_PARTITIONING, SCIPconsGetData(), and SCIPconshdlrGetName().
Referenced by SCIP_DECL_CONSENFORELAX().
◆ SCIP_DECL_CONSCHECK()
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 3219 of file cons_orbitope.c.
References checkFullOrbitopeSolution(), checkPackingPartitioningOrbitopeSolution(), CONSHDLR_NAME, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSPROP(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_ORBITOPETYPE_PACKING, SCIP_ORBITOPETYPE_PARTITIONING, SCIPconsGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.
Referenced by SCIP_DECL_CONSENFOPS().
◆ SCIP_DECL_CONSPROP()
|
static |
domain propagation method of constraint handler
Definition at line 3267 of file cons_orbitope.c.
References CONSHDLR_NAME, FALSE, NULL, propagateCons(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSPRESOL(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.
Referenced by SCIP_DECL_CONSCHECK().
◆ SCIP_DECL_CONSPRESOL()
|
static |
presolving method of constraint handler
Definition at line 3317 of file cons_orbitope.c.
References checkRedundantCons(), CONSHDLR_NAME, FALSE, NULL, propagateCons(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSRESPROP(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsActive(), SCIPdebugMsg, and SCIPdelCons().
Referenced by SCIP_DECL_CONSPROP().
◆ SCIP_DECL_CONSRESPROP()
|
static |
propagation conflict resolving method of constraint handler
Definition at line 3389 of file cons_orbitope.c.
References NULL, resolvePropagation(), resolvePropagationFullOrbitope(), SCIP_CALL, SCIP_DECL_CONSLOCK(), SCIP_OKAY, SCIP_ORBITOPETYPE_PACKING, SCIP_ORBITOPETYPE_PARTITIONING, and SCIPconsGetData().
Referenced by SCIP_DECL_CONSPRESOL().
◆ SCIP_DECL_CONSLOCK()
|
static |
variable rounding lock method of constraint handler
Definition at line 3421 of file cons_orbitope.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSPRINT(), SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPconsGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.
Referenced by SCIP_DECL_CONSRESPROP().
◆ SCIP_DECL_CONSPRINT()
|
static |
constraint display method of constraint handler
Definition at line 3461 of file cons_orbitope.c.
References CONSHDLR_NAME, NULL, SCIP_DECL_CONSCOPY(), SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIP_ORBITOPETYPE_PACKING, SCIP_ORBITOPETYPE_PARTITIONING, SCIPABORT, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPinfoMessage(), and SCIPvarGetName().
Referenced by SCIP_DECL_CONSLOCK().
◆ SCIP_DECL_CONSCOPY()
|
static |
constraint copying method of constraint handler
Definition at line 3523 of file cons_orbitope.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSPARSE(), SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPcreateConsOrbitope(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetVarCopy(), and TRUE.
Referenced by SCIP_DECL_CONSPRINT().
◆ SCIP_DECL_CONSPARSE()
|
static |
constraint parsing method of constraint handler
Definition at line 3605 of file cons_orbitope.c.
References FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSGETVARS(), SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIP_ORBITOPETYPE_PACKING, SCIP_ORBITOPETYPE_PARTITIONING, SCIP_VERBLEVEL_MINIMAL, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPcreateConsOrbitope(), SCIPfindVar(), SCIPfreeBufferArray, SCIPreallocBufferArray, SCIPverbMessage(), and TRUE.
Referenced by SCIP_DECL_CONSCOPY().
◆ SCIP_DECL_CONSGETVARS()
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 3733 of file cons_orbitope.c.
References FALSE, NULL, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), and TRUE.
Referenced by SCIP_DECL_CONSPARSE().
◆ SCIP_DECL_CONSGETNVARS()
|
static |
constraint method of constraint handler which returns the number of variables (if possible)
Definition at line 3766 of file cons_orbitope.c.
References NULL, SCIP_OKAY, SCIPconsGetData(), SCIPincludeConshdlrOrbitope(), and TRUE.
Referenced by SCIP_DECL_CONSGETVARS().