Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric group

Author
Timo Berthold
Marc Pfetsch
Christopher Hojny

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.

translation table
herepaper
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

◆ 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 SCIP_RETCODE consdataFree ( SCIP scip,
SCIP_CONSDATA **  consdata,
SCIP_Bool  usedynamicprop 
)
static

frees an orbitope constraint data

Parameters
scipSCIP data structure
consdatapointer to orbitope constraint data
usedynamicpropwhether 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 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

creates orbitope constraint data

Parameters
scipSCIP data structure
consdatapointer to store constraint data
varsvariables array, must have size nspcons x nblocks
nspconsnumber of set partitioning (packing) constraints <=> p
nblocksnumber of symmetric variable blocks <=> q
orbitopetypetype of orbitope constraint
resolvepropshould propagation be resolved?
usedynamicpropwhether we use a dynamic version of the propagation routine
ismodelconswhether 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 SCIP_RETCODE strengthenOrbitopeConstraint ( SCIP scip,
SCIP_VAR ***  vars,
int *  nrows,
int  ncols,
SCIP_ORBITOPETYPE type 
)
static

strengthen full orbitopes to packing/partitioning orbitopes if possible

Parameters
scipSCIP data structure
varsvariable matrix of orbitope constraint
nrowspointer to number of rows of variable matrix
ncolsnumber of columns of variable matrix
typepointer 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 void copyValues ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_SOL sol 
)
static

copies the variables values from the solution to the constraint data structure

Parameters
scipthe SCIP data structure
consdatathe constraint data
sola 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 void computeSCTable ( SCIP scip,
int  nspcons,
int  nblocks,
SCIP_Real **  weights,
int **  cases,
SCIP_Real **  vals 
)
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
scipSCIP pointer
nspconsnumber of set partitioning (packing) constraints <=> p
nblocksnumber of symmetric variable blocks <=> q
weightsSC weight table
casesindicator of the SC cases
valscurrent 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 SCIP_RETCODE fixTriangle ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool infeasible,
int *  nfixedvars 
)
static

fix upper right triangle if necessary

Parameters
scipSCIP data structure
consconstraint to be processed
infeasiblepointer to store TRUE, if the node can be cut off
nfixedvarspointer 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 SCIP_RETCODE separateSCIs ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS cons,
SCIP_CONSDATA consdata,
SCIP_Bool infeasible,
int *  nfixedvars,
int *  ncuts 
)
static

separates shifted column inequalities according to the solution stored in consdata->vals

Parameters
scipthe SCIP data structure
conshdlrconstraint handler
consconstraint
consdatathe constraint data
infeasiblewhether we detected infeasibility
nfixedvarspointer to store the number of variables fixed
ncutspointer 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 SCIP_RETCODE propagatePackingPartitioningCons ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool infeasible,
int *  nfixedvars 
)
static

propagation method for a single packing or partitioning orbitope constraint

Parameters
scipSCIP data structure
consconstraint to be processed
infeasiblepointer to store TRUE, if the node can be cut off
nfixedvarspointer 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 SCIP_RETCODE computeDynamicRowOrder ( SCIP scip,
SCIP_HASHMAP rowindexmap,
SCIP_Bool rowused,
int *  roworder,
int  nrows,
int  ncols,
int *  maxrowlabel 
)
static
Parameters
scipSCIP pointer
rowindexmapmap of variables to indices in orbitope vars matrix
rowusedbitset marking whether a row has been considered in the new order
roworderreordering of the rows w.r.t. branching decisions
nrowsnumber of rows in orbitope
ncolsnumber of columns in orbitope
maxrowlabelmaximum 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 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
Parameters
varsvariable matrix
lexminfixesfixings characterzing lex-min face
roworderdynamic row order
minfixedrowlexminindex of minimum fixed row for each column or NULL (if in prop)
infeasiblepointer to store whether infeasibility has been detected or NULL (if in resprop)
mnumber of rows in vars
nnumber of columns in vars
nrowsusednumber of rows considered in propagation
bdchgidxbdchgidx in resprop or NULL (if not in resprop)
respropwhether 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 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
Parameters
varsvariable matrix
lexmaxfixesfixings characterzing lex-max face
roworderdynamic row order
minfixedrowlexmaxindex of minimum fixed row for each column or NULL (if in prop)
infeasiblepointer to store whether infeasibility has been detected or NULL (if in resprop)
mnumber of rows in vars
nnumber of columns in vars
nrowsusednumber of rows considered in propagation
bdchgidxbdchgidx in resprop or NULL (if not in resprop)
respropwhether 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 SCIP_RETCODE propagateFullOrbitopeCons ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool infeasible,
int *  nfixedvars,
SCIP_Bool  dynamic 
)
static

propagation method for a single packing or partitioning orbitope constraint

Parameters
scipSCIP data structure
consconstraint to be processed
infeasiblepointer to store TRUE, if the node can be cut off
nfixedvarspointer to add up the number of found domain reductions
dynamicwhether 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 SCIP_RETCODE propagateCons ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool infeasible,
int *  nfixedvars,
SCIP_Bool  usedynamicprop 
)
static

propagation method for a single orbitope constraint

Parameters
scipSCIP data structure
consconstraint to be processed
infeasiblepointer to store TRUE, if the node can be cut off
nfixedvarspointer to add up the number of found domain reductions
usedynamicpropwhether 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 SCIP_RETCODE resolvePropagationFullOrbitope ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS cons,
int  inferinfo,
SCIP_BDCHGIDX bdchgidx,
SCIP_RESULT result 
)
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
scipSCIP data structure
conshdlrconstraint handler of the corresponding constraint
consconstraint that inferred the bound change
inferinfoinference information
bdchgidxbound change index (time stamp of bound change), or NULL for current time
resultpointer 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 SCIP_RETCODE resolvePropagation ( SCIP scip,
SCIP_CONS cons,
int  inferinfo,
SCIP_BDCHGIDX bdchgidx,
SCIP_RESULT result 
)
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
scipSCIP data structure
consconstraint that inferred the bound change
inferinfoinference information
bdchgidxbound change index (time stamp of bound change), or NULL for current time
resultpointer 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 SCIP_RETCODE enfopsPackingPartitioningOrbitopeSolution ( SCIP scip,
SCIP_CONS cons,
SCIP_RESULT result 
)
static

check packing/partitioning orbitope solution for feasibility

Parameters
scipSCIP data structure
conspointer to orbitope constraint
resultpointer 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 SCIP_RETCODE checkPackingPartitioningOrbitopeSolution ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_RESULT result,
SCIP_Bool  printreason 
)
static

check packing/partitioning orbitope solution for feasibility

Parameters
scipSCIP data structure
conspointer to orbitope constraint
solsolution to be checked
resultpointer to store the result of the enforcing call
printreasonwhether 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 SCIP_RETCODE checkFullOrbitopeSolution ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_Bool  printreason,
SCIP_Bool feasible 
)
static

check full orbitope solution for feasibility

Parameters
scipSCIP data structure
consconstraint to process
solsolution to be checked
printreasonwhether reason for infeasibility should be printed
feasiblememory 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 SCIP_RETCODE separateCoversOrbisack ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_Bool  dynamic,
int *  ngen,
SCIP_Bool infeasible 
)
static

separate orbisack cover inequalities

Parameters
scipSCIP data structure
consconstraint to process
solsolution to separate (NULL for the LP solution)
dynamicwhether we use a dynamic row order
ngenpointer to store number of generated cuts
infeasiblepointer 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 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

separate or enforce constraints

Parameters
scipSCIP data structure
conshdlrconstraint handler
conssconstraints to process
nconssnumber of constraints
nusefulconssnumber of useful (non-obsolete) constraints to process
solsolution to separate (NULL for the LP solution)
resultpointer to store the result (should be initialized)
enforcewhether 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 SCIP_RETCODE checkRedundantCons ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool redundant 
)
static

check whether all variables in an orbitope constraint are fixed

Parameters
scipSCIP data structure
consconstraint to be processed
redundantpointer 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 SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyOrbitope  )
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 SCIP_DECL_CONSFREE ( consFreeOrbitope  )
static

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteOrbitope  )
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()

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpOrbitope  )
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 SCIP_DECL_CONSSEPASOL ( consSepasolOrbitope  )
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 SCIP_DECL_CONSENFOLP ( consEnfolpOrbitope  )
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 SCIP_DECL_CONSENFORELAX ( consEnforelaxOrbitope  )
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 SCIP_DECL_CONSENFOPS ( consEnfopsOrbitope  )
static

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckOrbitope  )
static

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropOrbitope  )
static

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolOrbitope  )
static

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropOrbitope  )
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 SCIP_DECL_CONSLOCK ( consLockOrbitope  )
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 SCIP_DECL_CONSPRINT ( consPrintOrbitope  )
static

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopyOrbitope  )
static

◆ SCIP_DECL_CONSPARSE()

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsOrbitope  )
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 SCIP_DECL_CONSGETNVARS ( consGetNVarsOrbitope  )
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().