Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

constraint handler for orbisack constraints

Author
Christopher Hojny
Jasper van Doornmalen

The type of constraints of this constraint handler is described in cons_orbisack.h.

The details of the method implemented here are described in the following papers:

Describing Orbitopes by Linear Inequalities and Projection Based Tools
Andreas Loos,
PhD thesis, Otto-von-Guericke-Universitaet Magdeburg (2010).

This thesis provides a complete linear description of orbisacks and a separation routine for its inequalities.

Polytopes Associated with Symmetry Handling
Christopher Hojny and Marc E. Pfetsch,
(2017), preprint available at http://www.optimization-online.org/DB_HTML/2017/01/5835.html

This paper describes a linear time separation routine for so-called cover inequalities of orbisacks.

Definition in file cons_orbisack.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_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_sol.h"
#include "scip/scip_var.h"
#include "scip/symmetry.h"
#include <ctype.h>
#include <string.h>

Go to the source code of this file.

Macros

#define CONSHDLR_NAME   "orbisack"
 
#define CONSHDLR_DESC   "symmetry breaking constraint handler for orbisacks"
 
#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_ORBISEPARATION   FALSE
 
#define DEFAULT_COVERSEPARATION   TRUE
 
#define DEFAULT_COEFFBOUND   1000000.0
 
#define DEFAULT_PPORBISACK   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. */
 

Functions

static SCIP_RETCODE consdataFree (SCIP *scip, SCIP_CONSDATA **consdata)
 
static SCIP_RETCODE consdataCreate (SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, int nrows, SCIP_Bool ismodelcons)
 
static SCIP_RETCODE packingUpgrade (SCIP *scip, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, int nrows, SCIP_Bool *success, SCIP_Bool *isparttype)
 
static SCIP_RETCODE initLP (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible)
 
static SCIP_RETCODE addOrbisackCover (SCIP *scip, SCIP_CONS *cons, int nrows, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, SCIP_Real *coeffs1, SCIP_Real *coeffs2, SCIP_Real rhs, SCIP_Bool *infeasible)
 
static SCIP_RETCODE separateOrbisackCovers (SCIP *scip, SCIP_CONS *cons, int nrows, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, SCIP_Real *vals1, SCIP_Real *vals2, int *ngen, SCIP_Bool *infeasible)
 
static SCIP_RETCODE addOrbisackInequality (SCIP *scip, SCIP_CONS *cons, int nrows, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, SCIP_Real *coeffs1, SCIP_Real *coeffs2, SCIP_Real rhs, SCIP_Bool *infeasible)
 
static SCIP_RETCODE separateOrbisack (SCIP *scip, SCIP_CONS *cons, int nrows, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, SCIP_Real *vals1, SCIP_Real *vals2, SCIP_Bool coverseparation, SCIP_Real coeffbound, int *ngen, SCIP_Bool *infeasible)
 
static SCIP_RETCODE checkFeasible (SCIP *scip, SCIP_VAR **vars1, SCIP_VAR **vars2, int nrows, int start, SCIP_Bool *infeasible, int *infeasiblerow)
 
static SCIP_RETCODE propVariables (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, SCIP_Bool *found, int *ngen)
 
static SCIP_RETCODE separateInequalities (SCIP *scip, SCIP_RESULT *result, SCIP_CONS *cons, int nrows, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, SCIP_Real *vals1, SCIP_Real *vals2)
 
static SCIP_DECL_CONSHDLRCOPY (conshdlrCopyOrbisack)
 
static SCIP_DECL_CONSDELETE (consDeleteOrbisack)
 
static SCIP_DECL_CONSFREE (consFreeOrbisack)
 
static SCIP_DECL_CONSTRANS (consTransOrbisack)
 
static SCIP_DECL_CONSINITLP (consInitlpOrbisack)
 
static SCIP_DECL_CONSINITSOL (consInitsolOrbisack)
 
static SCIP_DECL_CONSSEPALP (consSepalpOrbisack)
 
static SCIP_DECL_CONSSEPASOL (consSepasolOrbisack)
 
static SCIP_DECL_CONSENFOLP (consEnfolpOrbisack)
 
static SCIP_DECL_CONSENFOPS (consEnfopsOrbisack)
 
static SCIP_DECL_CONSENFORELAX (consEnforelaxOrbisack)
 
static SCIP_DECL_CONSCHECK (consCheckOrbisack)
 
static SCIP_DECL_CONSPROP (consPropOrbisack)
 
static SCIP_DECL_CONSPRESOL (consPresolOrbisack)
 
static SCIP_DECL_CONSRESPROP (consRespropOrbisack)
 
static SCIP_DECL_CONSLOCK (consLockOrbisack)
 
static SCIP_DECL_CONSCOPY (consCopyOrbisack)
 
static SCIP_DECL_CONSPARSE (consParseOrbisack)
 
static SCIP_DECL_CONSPRINT (consPrintOrbisack)
 
SCIP_RETCODE SCIPcheckSolutionOrbisack (SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars1, SCIP_VAR **vars2, int nrows, SCIP_Bool printreason, SCIP_Bool *feasible)
 
static SCIP_DECL_CONSGETVARS (consGetVarsOrbisack)
 
static SCIP_DECL_CONSGETNVARS (consGetNVarsOrbisack)
 
SCIP_RETCODE SCIPincludeConshdlrOrbisack (SCIP *scip)
 
SCIP_RETCODE SCIPcreateConsOrbisack (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, int nrows, SCIP_Bool ispporbisack, SCIP_Bool isparttype, 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 SCIPcreateConsBasicOrbisack (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR **vars1, SCIP_VAR **vars2, int nrows, SCIP_Bool ispporbisack, SCIP_Bool isparttype, SCIP_Bool ismodelcons)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "symmetry breaking constraint handler for orbisacks"

Definition at line 79 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   +40100

priority of the constraint handler for separation

Definition at line 80 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   -1005200

priority of the constraint handler for constraint enforcing

Definition at line 81 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -1005200

priority of the constraint handler for checking feasibility

Definition at line 82 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ   5

frequency for separating cuts; zero means to separate only in the root node

Definition at line 83 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   5

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 84 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ   -1

frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only

Definition at line 85 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS   -1

maximal number of presolving rounds the constraint handler participates in (-1: no limit)

Definition at line 88 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 89 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 90 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   TRUE

should the constraint handler be skipped, if no constraints are available?

Definition at line 91 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 93 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_EXHAUSTIVE

Definition at line 94 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ DEFAULT_ORBISEPARATION

#define DEFAULT_ORBISEPARATION   FALSE

whether orbisack inequalities should be separated

Definition at line 97 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ DEFAULT_COVERSEPARATION

#define DEFAULT_COVERSEPARATION   TRUE

whether cover inequalities should be separated

Definition at line 98 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ DEFAULT_COEFFBOUND

#define DEFAULT_COEFFBOUND   1000000.0

maximum size of coefficients in orbisack inequalities

Definition at line 101 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ DEFAULT_PPORBISACK

#define DEFAULT_PPORBISACK   TRUE

whether we allow upgrading to packing/partitioning orbisacks

Definition at line 102 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ DEFAULT_FORCECONSCOPY

#define DEFAULT_FORCECONSCOPY   FALSE

whether orbisack constraints should be forced to be copied to sub SCIPs

Definition at line 103 of file cons_orbisack.c.

Referenced by SCIPincludeConshdlrOrbisack().

◆ FIXED0

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

Definition at line 106 of file cons_orbisack.c.

Referenced by checkFeasible(), and propVariables().

◆ FIXED1

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

Definition at line 107 of file cons_orbisack.c.

Referenced by checkFeasible(), and propVariables().

◆ UNFIXED

#define UNFIXED   3 /* When a variable is neither fixed to 0 or to 1. */

Definition at line 108 of file cons_orbisack.c.

Referenced by checkFeasible(), and propVariables().

Function Documentation

◆ consdataFree()

static SCIP_RETCODE consdataFree ( SCIP scip,
SCIP_CONSDATA **  consdata 
)
static

frees orbisack constraint data

Parameters
scipSCIP data structure
consdatapointer to orbisack constraint data

Definition at line 142 of file cons_orbisack.c.

References consdataCreate(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArrayNull.

Referenced by SCIP_DECL_CONSDELETE().

◆ consdataCreate()

static SCIP_RETCODE consdataCreate ( SCIP scip,
SCIP_CONSDATA **  consdata,
SCIP_VAR *const *  vars1,
SCIP_VAR *const *  vars2,
int  nrows,
SCIP_Bool  ismodelcons 
)
static

creates orbisack constraint data

Parameters
scipSCIP data structure
consdatapointer to store constraint data
vars1first column of variable matrix
vars2second column of variable matrix
nrowsnumber of rows in variable matrix
ismodelconswhether the orbisack is a model constraint

Definition at line 164 of file cons_orbisack.c.

References NULL, packingUpgrade(), SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPduplicateBlockMemoryArray, SCIPgetTransformedVar(), SCIPisTransformed(), SCIPmarkDoNotMultaggrVar(), and SCIPvarIsBinary().

Referenced by consdataFree(), SCIP_DECL_CONSTRANS(), and SCIPcreateConsOrbisack().

◆ packingUpgrade()

static SCIP_RETCODE packingUpgrade ( SCIP scip,
SCIP_VAR *const *  vars1,
SCIP_VAR *const *  vars2,
int  nrows,
SCIP_Bool success,
SCIP_Bool isparttype 
)
static

check wether an orbisack is even a packing/partitioning orbisack

Parameters
scipSCIP pointer
vars1first column of matrix of variables on which the symmetry acts
vars2variables of second column
nrowsnumber of rows of orbisack
successmemory address to store whether constraint can be upgraded
isparttypememory address to store whether upgraded orbisack is partitioning orbisack

Definition at line 216 of file cons_orbisack.c.

References FALSE, initLP(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_ORBITOPETYPE_PACKING, SCIP_ORBITOPETYPE_PARTITIONING, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisPackingPartitioningOrbitope(), and TRUE.

Referenced by consdataCreate(), and SCIPcreateConsOrbisack().

◆ initLP()

static SCIP_RETCODE initLP ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool infeasible 
)
static

generate initial LP cut

We generate the inequality of the orbisack on the elements of the first row, i.e., the inequality \(-x_{1,1} + x_{1,2} \leq 0\).

Parameters
scipSCIP pointer
consconstraint
infeasiblepointer to store whether we detected infeasibility

Definition at line 272 of file cons_orbisack.c.

References addOrbisackCover(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddRow(), SCIPaddVarToRow(), SCIPconsGetData(), SCIPcreateEmptyRowCons(), SCIPinfinity(), SCIPprintRow(), SCIPreleaseRow(), and TRUE.

Referenced by packingUpgrade(), and SCIP_DECL_CONSINITLP().

◆ addOrbisackCover()

static SCIP_RETCODE addOrbisackCover ( SCIP scip,
SCIP_CONS cons,
int  nrows,
SCIP_VAR *const *  vars1,
SCIP_VAR *const *  vars2,
SCIP_Real coeffs1,
SCIP_Real coeffs2,
SCIP_Real  rhs,
SCIP_Bool infeasible 
)
static

add orbisack cover inequality

Parameters
scipSCIP pointer
consconstraint
nrowsnumber of rows of orbisack
vars1first column of matrix of variables on which the symmetry acts
vars2variables of second column
coeffs1coefficients of the variables of the first column of the inequality to be added
coeffs2coefficients of the variables of the second column of the inequality to be added
rhsright-hand side of inequality to be added
infeasiblepointer to store whether we detected infeasibility

Definition at line 318 of file cons_orbisack.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowCons(), SCIPflushRowExtensions(), SCIPinfinity(), SCIPprintRow(), SCIPreleaseRow(), separateOrbisackCovers(), and TRUE.

Referenced by initLP(), and separateOrbisackCovers().

◆ separateOrbisackCovers()

static SCIP_RETCODE separateOrbisackCovers ( SCIP scip,
SCIP_CONS cons,
int  nrows,
SCIP_VAR *const *  vars1,
SCIP_VAR *const *  vars2,
SCIP_Real vals1,
SCIP_Real vals2,
int *  ngen,
SCIP_Bool infeasible 
)
static

Separate lifted orbisack cover inequalities

We currently do NOT enter cuts into the pool.

We iterate over the nrows-many cover inequalities which are potentially maximal w.r.t. their violation.

Parameters
scipSCIP pointer
consconstraint
nrowsnumber of rows of orbisack
vars1first column of matrix of variables on which the symmetry acts
vars2variables of second column
vals1LP-solution for those variables in first column
vals2LP-solution for those variables in second column
ngennumber of separated covers
infeasiblepointer to store whether we detected infeasibility

Definition at line 370 of file cons_orbisack.c.

References addOrbisackCover(), addOrbisackInequality(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPisEfficacious().

Referenced by addOrbisackCover(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFORELAX(), separateInequalities(), and separateOrbisack().

◆ addOrbisackInequality()

static SCIP_RETCODE addOrbisackInequality ( SCIP scip,
SCIP_CONS cons,
int  nrows,
SCIP_VAR *const *  vars1,
SCIP_VAR *const *  vars2,
SCIP_Real coeffs1,
SCIP_Real coeffs2,
SCIP_Real  rhs,
SCIP_Bool infeasible 
)
static

add orbisack inequality

Parameters
scipSCIP pointer
consconstraint
nrowsnumber of rows of orbisack
vars1first column of matrix of variables on which the symmetry acts
vars2variables of second column
coeffs1first column of coefficient matrix of inequality to be added
coeffs2second column of coefficient matrix of inequality to be added
rhsright-hand side of inequality to be added
infeasiblepointer to store whether we detected infeasibility

Definition at line 470 of file cons_orbisack.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowCons(), SCIPflushRowExtensions(), SCIPinfinity(), SCIPprintRow(), SCIPreleaseRow(), separateOrbisack(), and TRUE.

Referenced by separateOrbisack(), and separateOrbisackCovers().

◆ separateOrbisack()

static SCIP_RETCODE separateOrbisack ( SCIP scip,
SCIP_CONS cons,
int  nrows,
SCIP_VAR *const *  vars1,
SCIP_VAR *const *  vars2,
SCIP_Real vals1,
SCIP_Real vals2,
SCIP_Bool  coverseparation,
SCIP_Real  coeffbound,
int *  ngen,
SCIP_Bool infeasible 
)
static

separate orbisack inequalities

We currently do NOT enter cuts into the pool.

We stop if we checked for each possible basement row, whether a cut could be added. If the coefficients grow too large, we start separating cover inequalities.

We implement the separation algorithm for orbisacks described in
A. Loos. Describing Orbitopes by Linear Inequalities and Projection Based Tools. PhD thesis, Otto-von-Guericke-Universitaet Magdeburg, 2010.

Parameters
scipSCIP pointer
consconstraint
nrowsnumber of rows of orbisack
vars1first column of matrix of variables on which the symmetry acts
vars2variables of second column
vals1LP-solution for those variables in first column
vals2LP-solution for those variables in second column
coverseparationwhether we separate cover inequalities
coeffboundmaximum size of coefficients in orbisack inequalities
ngenpointer to store the number of generated cuts
infeasiblepointer to store whether we detected infeasibility

Definition at line 527 of file cons_orbisack.c.

References addOrbisackInequality(), checkFeasible(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEfficacious(), and separateOrbisackCovers().

Referenced by addOrbisackInequality(), and separateInequalities().

◆ checkFeasible()

static SCIP_RETCODE checkFeasible ( SCIP scip,
SCIP_VAR **  vars1,
SCIP_VAR **  vars2,
int  nrows,
int  start,
SCIP_Bool infeasible,
int *  infeasiblerow 
)
static

Determines if a vector with additional fixings could exist that is lexicographically larger than another vector.

Given two vectors of variables with local lower and upper bounds, and a set of additional (virtual) fixings. Assuming that the entries of both vectors are equal until entry "start", this function determines if there exists a vector where the left vector is lexicographically larger or equal to the right vector. If a vector exsits, infeasible is set to FALSE, otherwise TRUE.

Parameters
scipSCIP pointer
vars1array of variables in first vector
vars2array of variables in second vector
nrowsnumber of rows
startat which row to start (assuming previous rows are equal)
infeasiblepointer to store whether infeasibility is detected in these fixings
infeasiblerowpointer to store at which row a (0, 1) pattern is found

Definition at line 681 of file cons_orbisack.c.

References FALSE, FIXED0, FIXED1, NULL, propVariables(), SCIP_OKAY, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and UNFIXED.

Referenced by propVariables(), and separateOrbisack().

◆ propVariables()

static SCIP_RETCODE propVariables ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool infeasible,
SCIP_Bool found,
int *  ngen 
)
static

propagation

Parameters
scipSCIP pointer
consconstraint to be propagated
infeasiblepointer to store whether it was detected that the node is infeasible
foundpointer to store whether a new propagation could be found
ngenpointer to store the number of generated bound strengthenings

Definition at line 755 of file cons_orbisack.c.

References checkFeasible(), FALSE, FIXED0, FIXED1, NULL, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIPaddConflictBinvar(), SCIPanalyzeConflictCons(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), separateInequalities(), TRUE, and UNFIXED.

Referenced by checkFeasible(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().

◆ separateInequalities()

static SCIP_RETCODE separateInequalities ( SCIP scip,
SCIP_RESULT result,
SCIP_CONS cons,
int  nrows,
SCIP_VAR *const *  vars1,
SCIP_VAR *const *  vars2,
SCIP_Real vals1,
SCIP_Real vals2 
)
static

separate orbisack and cover inequalities

Parameters
scippointer to scip
resultpointer to store the result of separation
consconstraint
nrowsnumber of rows of orbisack
vars1first column of matrix of variables on which the symmetry acts
vars2variables of second column
vals1LP-solution for those variables in first column
vals2LP-solution for those variables in second column

Definition at line 955 of file cons_orbisack.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSHDLRCOPY(), SCIP_OKAY, SCIP_SEPARATED, SCIPconsGetHdlr(), SCIPconshdlrGetData(), separateOrbisack(), and separateOrbisackCovers().

Referenced by propVariables(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyOrbisack  )
static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 1011 of file cons_orbisack.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSDELETE(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrOrbisack(), and TRUE.

Referenced by separateInequalities().

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteOrbisack  )
static

frees specific constraint data

Definition at line 1027 of file cons_orbisack.c.

References consdataFree(), CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, and SCIPconshdlrGetName().

Referenced by SCIP_DECL_CONSHDLRCOPY().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeOrbisack  )
static

frees constraint handler

Definition at line 1042 of file cons_orbisack.c.

References CONSHDLR_NAME, NULL, SCIP_DECL_CONSTRANS(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPfreeBlockMemory.

Referenced by SCIP_DECL_CONSDELETE().

◆ SCIP_DECL_CONSTRANS()

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpOrbisack  )
static

LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)

Definition at line 1095 of file cons_orbisack.c.

References CONSHDLR_NAME, FALSE, initLP(), NULL, SCIP_CALL, SCIP_DECL_CONSINITSOL(), SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetName(), and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSTRANS().

◆ SCIP_DECL_CONSINITSOL()

static SCIP_DECL_CONSINITSOL ( consInitsolOrbisack  )
static

solving process initialization method of constraint handler (called when branch and bound process is about to begin)

Definition at line 1126 of file cons_orbisack.c.

References CONSHDLR_NAME, NULL, SCIP_DECL_CONSSEPALP(), SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetData(), and SCIPconshdlrGetName().

Referenced by SCIP_DECL_CONSINITLP().

◆ SCIP_DECL_CONSSEPALP()

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolOrbisack  )
static

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpOrbisack  )
static

constraint enforcing method of constraint handler for LP solutions

Precondition
It is assumed that the solution is integral (this can be ensured by appropriate priorities).

Definition at line 1286 of file cons_orbisack.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 separateOrbisackCovers().

Referenced by SCIP_DECL_CONSSEPASOL().

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsOrbisack  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 1367 of file cons_orbisack.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSENFORELAX(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPcheckSolutionOrbisack(), SCIPconsGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, and TRUE.

Referenced by SCIP_DECL_CONSENFOLP().

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxOrbisack  )
static

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckOrbisack  )
static

feasibility check method of constraint handler for integral solutions

Definition at line 1496 of file cons_orbisack.c.

References CONSHDLR_NAME, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSPROP(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPcheckSolutionOrbisack(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, and TRUE.

Referenced by SCIP_DECL_CONSENFORELAX().

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropOrbisack  )
static

domain propagation method of constraint handler

Definition at line 1545 of file cons_orbisack.c.

References CONSHDLR_NAME, FALSE, NULL, propVariables(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSPRESOL(), SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPconshdlrGetName(), and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSCHECK().

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolOrbisack  )
static

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropOrbisack  )
static

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockOrbisack  )
static

Lock variables

We assume we have only one global (void) constraint and lock all variables.

  • Orbisack constraints may get violated if the variables of the first column are rounded down, we therefor call SCIPaddVarLocksType(..., nlockspos, nlocksneg).
  • Orbisack constraints may get violated if the variables of the second column are rounded up , we therefor call SCIPaddVarLocksType(..., nlocksneg, nlockspo ).

Definition at line 1749 of file cons_orbisack.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSCOPY(), SCIP_OKAY, SCIPaddVarLocksType(), SCIPconsGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSRESPROP().

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopyOrbisack  )
static

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseOrbisack  )
static

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintOrbisack  )
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 1987 of file cons_orbisack.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPcheckSolutionOrbisack(), SCIPconsGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPinfoMessage(), SCIPwriteVarName(), and TRUE.

Referenced by SCIP_DECL_CONSPARSE().

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsOrbisack  )
static

constraint method of constraint handler which returns the variables (if possible)

Definition at line 2086 of file cons_orbisack.c.

References FALSE, NULL, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), and TRUE.

Referenced by SCIPcheckSolutionOrbisack().

◆ SCIP_DECL_CONSGETNVARS()

static SCIP_DECL_CONSGETNVARS ( consGetNVarsOrbisack  )
static

constraint method of constraint handler which returns the number of variables (if possible)

Definition at line 2118 of file cons_orbisack.c.

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

Referenced by SCIP_DECL_CONSGETVARS().