Scippy

SCIP

Solving Constraint Integer Programs

cons_symresack.c File Reference

Detailed Description

constraint handler for symresack constraints

Author
Christopher Hojny

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

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

Fundamental Domains for Integer Programs with Symmetries
Eric J. Friedman,
Combinatorial Optimization, volume 4616 of LNCS, 146-153 (2007)

This paper describes an inequality to handle symmetries of a single permutation. This so-called FD-inequality is the basic for the propagation routine of our implementation.

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

This paper describes an almost linear time separation routine for so-called cove inequalities of symresacks. In our implementation, however, we use a separation routine with quadratic worst case running time.

Packing, Partitioning, and Covering Symresacks
Christopher Hojny,
(2017), preprint available at http://www.optimization-online.org/DB_HTML/2017/05/5990.html

This paper introduces linearly many inequalities with ternary coefficients that suffice to characterize the binary points contained in a packing and partitioning symresack completely.

Definition in file cons_symresack.c.

#include "blockmemshell/memory.h"
#include "scip/cons_orbisack.h"
#include "scip/cons_setppc.h"
#include "scip/cons_symresack.h"
#include "scip/pub_cons.h"
#include "scip/pub_message.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_conflict.h"
#include "scip/scip_cons.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_var.h"
#include <string.h>

Go to the source code of this file.

Macros

#define CONSHDLR_NAME   "symresack"
 
#define CONSHDLR_DESC   "symmetry breaking constraint handler relying on symresacks"
 
#define CONSHDLR_SEPAPRIORITY   +40100
 
#define CONSHDLR_ENFOPRIORITY   -1005200
 
#define CONSHDLR_CHECKPRIORITY   -1005200
 
#define CONSHDLR_SEPAFREQ   5
 
#define CONSHDLR_PROPFREQ   5
 
#define CONSHDLR_EAGERFREQ   -1
 
#define CONSHDLR_MAXPREROUNDS   -1
 
#define CONSHDLR_DELAYSEPA   FALSE
 
#define CONSHDLR_DELAYPROP   FALSE
 
#define CONSHDLR_NEEDSCONS   TRUE
 
#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
 
#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_EXHAUSTIVE
 
#define DEFAULT_PPSYMRESACK   TRUE
 
#define DEFAULT_CHECKALWAYSFEAS   TRUE
 
#define ISFIXED0(x)   (SCIPvarGetUbLocal(x) < 0.5 ? TRUE : FALSE)
 
#define ISFIXED1(x)   (SCIPvarGetLbLocal(x) > 0.5 ? TRUE : FALSE)
 

Functions

static SCIP_RETCODE consdataFree (SCIP *scip, SCIP_CONSDATA **consdata)
 
static SCIP_RETCODE packingUpgrade (SCIP *scip, SCIP_CONSDATA **consdata, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool *upgrade)
 
static SCIP_RETCODE consdataCreate (SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR *const *inputvars, int inputnvars, int *inputperm)
 
static SCIP_RETCODE initLP (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible)
 
static SCIP_RETCODE propVariables (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *ngen)
 
static SCIP_RETCODE addSymresackInequality (SCIP *scip, SCIP_CONS *cons, int nvars, SCIP_VAR **vars, int *coeffs, SCIP_Real rhs, SCIP_Bool *infeasible)
 
static SCIP_RETCODE separateSymresackCovers (SCIP *scip, SCIP_CONS *cons, const SCIP_CONSDATA *consdata, SCIP_Real *vals, int *ngen, SCIP_Bool *infeasible)
 
static SCIP_RETCODE checkSymresackSolution (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool printreason)
 
static SCIP_RETCODE orbisackUpgrade (SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **inputvars, int nvars, SCIP_Bool *upgrade, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
SCIP_RETCODE SCIPcreateSymbreakCons (SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
static SCIP_DECL_CONSDELETE (consDeleteSymresack)
 
static SCIP_DECL_CONSFREE (consFreeSymresack)
 
static SCIP_DECL_CONSTRANS (consTransSymresack)
 
static SCIP_DECL_CONSINITLP (consInitlpSymresack)
 
static SCIP_DECL_CONSINITSOL (consInitsolSymresack)
 
static SCIP_DECL_CONSSEPALP (consSepalpSymresack)
 
static SCIP_DECL_CONSSEPASOL (consSepasolSymresack)
 
static SCIP_DECL_CONSENFOLP (consEnfolpSymresack)
 
static SCIP_DECL_CONSENFOPS (consEnfopsSymresack)
 
static SCIP_DECL_CONSENFORELAX (consEnforelaxSymresack)
 
static SCIP_DECL_CONSCHECK (consCheckSymresack)
 
static SCIP_DECL_CONSPROP (consPropSymresack)
 
static SCIP_DECL_CONSPRESOL (consPresolSymresack)
 
static SCIP_DECL_CONSRESPROP (consRespropSymresack)
 
static SCIP_DECL_CONSLOCK (consLockSymresack)
 
static SCIP_DECL_CONSPRINT (consPrintSymresack)
 
static SCIP_DECL_CONSGETVARS (consGetVarsSymresack)
 
static SCIP_DECL_CONSGETNVARS (consGetNVarsSymresack)
 
SCIP_RETCODE SCIPincludeConshdlrSymresack (SCIP *scip)
 
SCIP_RETCODE SCIPcreateConsSymresack (SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
SCIP_RETCODE SCIPcreateConsBasicSymresack (SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "symmetry breaking constraint handler relying on symresacks"

Definition at line 73 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   +40100

priority of the constraint handler for separation

Definition at line 74 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   -1005200

priority of the constraint handler for constraint enforcing

Definition at line 75 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -1005200

priority of the constraint handler for checking feasibility

Definition at line 76 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ   5

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

Definition at line 77 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   5

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 78 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ   -1

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

Definition at line 79 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS   -1

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

Definition at line 82 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA   FALSE

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

Definition at line 83 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   FALSE

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

Definition at line 84 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   TRUE

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

Definition at line 85 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 87 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_EXHAUSTIVE

Definition at line 88 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ DEFAULT_PPSYMRESACK

#define DEFAULT_PPSYMRESACK   TRUE

whether we allow upgrading to packing/partitioning symresacks

Definition at line 90 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ DEFAULT_CHECKALWAYSFEAS

#define DEFAULT_CHECKALWAYSFEAS   TRUE

whether check routine returns always SCIP_FEASIBLE

Definition at line 91 of file cons_symresack.c.

Referenced by SCIPincludeConshdlrSymresack().

◆ ISFIXED0

#define ISFIXED0 (   x)    (SCIPvarGetUbLocal(x) < 0.5 ? TRUE : FALSE)

Definition at line 94 of file cons_symresack.c.

Referenced by propVariables().

◆ ISFIXED1

#define ISFIXED1 (   x)    (SCIPvarGetLbLocal(x) > 0.5 ? TRUE : FALSE)

Definition at line 95 of file cons_symresack.c.

Referenced by propVariables().

Function Documentation

◆ consdataFree()

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

frees a symresack constraint data

Parameters
scipSCIP data structure
consdatapointer to symresack constraint data

Definition at line 135 of file cons_symresack.c.

References NULL, packingUpgrade(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseVar().

Referenced by SCIP_DECL_CONSDELETE().

◆ packingUpgrade()

static SCIP_RETCODE packingUpgrade ( SCIP scip,
SCIP_CONSDATA **  consdata,
int *  perm,
SCIP_VAR **  vars,
int  nvars,
SCIP_Bool upgrade 
)
static

check whether constraint can be upgraded to packing/partitioning symresack

Parameters
scipSCIP data structure
consdatapointer to store constraint data
permpermutation
varsvariables affected by permutation
nvarslength of permutation
upgradepointer to store whether upgrade was successful

Definition at line 181 of file cons_symresack.c.

References consdataCreate(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPerrorMessage, SCIPfindConshdlr(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), SCIPvarGetProbindex(), SCIPvarIsNegated(), and TRUE.

Referenced by consdataCreate(), and consdataFree().

◆ consdataCreate()

static SCIP_RETCODE consdataCreate ( SCIP scip,
SCIP_CONSDATA **  consdata,
SCIP_VAR *const *  inputvars,
int  inputnvars,
int *  inputperm 
)
static

creates symresack constraint data

If the input data contain non-binary variables of fixed points, we delete these variables in a preprocessing step.

Parameters
scipSCIP data structure
consdatapointer to store constraint data
inputvarsinput variables of the constraint handler
inputnvarsinput number of variables of the constraint handler
inputperminput permutation of the constraint handler

Definition at line 414 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, initLP(), NULL, packingUpgrade(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcaptureVar(), SCIPconshdlrGetData(), SCIPerrorMessage, SCIPfindConshdlr(), SCIPfreeBufferArrayNull, SCIPgetTransformedVar(), SCIPisTransformed(), SCIPmarkDoNotMultaggrVar(), and SCIPvarIsBinary().

Referenced by packingUpgrade(), and SCIPcreateConsSymresack().

◆ initLP()

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

generate initial LP cut

We generate the ordering inequality for the pair \((1, \gamma^{-1}(1))\), i.e., the inequality \(-x_{1} + x_{\gamma^{-1}(1)} \leq 0\). This inequality is valid, because we guaranteed in a preprocessing step that all variables are binary.

Furthermore, we add facet inequalities of packing/partitioning symresacks if we deal with packing/partitioning symresacks.

Parameters
scipSCIP pointer
consconstraint
infeasiblepointer to store whether we detected infeasibility

Definition at line 550 of file cons_symresack.c.

References FALSE, NULL, propVariables(), SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarsToRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPcreateEmptyRowCons(), SCIPfreeBufferArray, SCIPinfinity(), SCIPreleaseRow(), SCIPsnprintf(), and TRUE.

Referenced by consdataCreate(), and SCIP_DECL_CONSINITLP().

◆ propVariables()

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

perform propagation of symresack constraint

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

Definition at line 675 of file cons_symresack.c.

References addSymresackInequality(), FALSE, ISFIXED0, ISFIXED1, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIPaddConflictBinvar(), SCIPanalyzeConflictCons(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

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

◆ addSymresackInequality()

static SCIP_RETCODE addSymresackInequality ( SCIP scip,
SCIP_CONS cons,
int  nvars,
SCIP_VAR **  vars,
int *  coeffs,
SCIP_Real  rhs,
SCIP_Bool infeasible 
)
static

add symresack cover inequality

Parameters
scipSCIP pointer
consconstraint
nvarsnumber of variables
varsvariables
coeffscoefficient vector of inequality to be added
rhsright-hand side of inequality to be added
infeasiblepointer to store whether we detected infeasibility

Definition at line 811 of file cons_symresack.c.

References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPcreateEmptyRowCons(), SCIPflushRowExtensions(), SCIPinfinity(), SCIPreleaseRow(), SCIPsnprintf(), separateSymresackCovers(), and TRUE.

Referenced by propVariables(), and separateSymresackCovers().

◆ separateSymresackCovers()

static SCIP_RETCODE separateSymresackCovers ( SCIP scip,
SCIP_CONS cons,
const SCIP_CONSDATA consdata,
SCIP_Real vals,
int *  ngen,
SCIP_Bool infeasible 
)
static

separate symresack cover inequalities

We currently do NOT enter cuts into the pool.

Parameters
scipSCIP pointer
consconstraint
consdataconstraint data
valssolution values of variables
ngenpointer to store the number of separated covers
infeasiblepointer to store whether we detected infeasibility

Definition at line 867 of file cons_symresack.c.

References addSymresackInequality(), checkSymresackSolution(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArrayNull, SCIPisEfficacious(), and SCIPisGT().

Referenced by addSymresackInequality(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFORELAX(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

◆ checkSymresackSolution()

static SCIP_RETCODE checkSymresackSolution ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_RESULT result,
SCIP_Bool  printreason 
)
static
Parameters
scipSCIP pointer
consconstrained for which we check the solution
solsolution to be checked
resultpointer to store whether we detected infeasibility
printreasonwhether reason for infeasibility should be printed

Definition at line 1123 of file cons_symresack.c.

References NULL, orbisackUpgrade(), SCIP_INFEASIBLE, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPinfoMessage(), and SCIPisFeasIntegral().

Referenced by SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSENFOPS(), and separateSymresackCovers().

◆ orbisackUpgrade()

static SCIP_RETCODE orbisackUpgrade ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
int *  perm,
SCIP_VAR **  inputvars,
int  nvars,
SCIP_Bool upgrade,
SCIP_Bool  initial,
SCIP_Bool  separate,
SCIP_Bool  enforce,
SCIP_Bool  check,
SCIP_Bool  propagate,
SCIP_Bool  local,
SCIP_Bool  modifiable,
SCIP_Bool  dynamic,
SCIP_Bool  removable,
SCIP_Bool  stickingatnode 
)
static

Upgrade symresack constraints to orbisacks

Parameters
scipSCIP pointer
conspointer to hold the created constraint
namename of constraint
permpermutation
inputvarspermuted variables array
nvarssize of perm array
upgradewhether constraint was upgraded
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiableis constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removableshould the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnodeshould the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.

Definition at line 1203 of file cons_symresack.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcreateConsOrbisack(), SCIPcreateSymbreakCons(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPvarIsBinary(), and TRUE.

Referenced by checkSymresackSolution(), and SCIPcreateSymbreakCons().

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteSymresack  )
static

frees specific constraint data

Definition at line 1366 of file cons_symresack.c.

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

Referenced by SCIPcreateSymbreakCons().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeSymresack  )
static

frees constraint handler

Definition at line 1381 of file cons_symresack.c.

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

Referenced by SCIP_DECL_CONSDELETE().

◆ SCIP_DECL_CONSTRANS()

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpSymresack  )
static

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

Definition at line 1484 of file cons_symresack.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 ( consInitsolSymresack  )
static

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

Definition at line 1514 of file cons_symresack.c.

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

Referenced by SCIP_DECL_CONSINITLP().

◆ SCIP_DECL_CONSSEPALP()

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolSymresack  )
static

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpSymresack  )
static

constraint enforcing method of constraint handler for LP solutions.

To check feasibility, we separate cover inequalities.

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

Definition at line 1693 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSENFOPS(), SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPBranchCands(), SCIPgetSolVals(), and separateSymresackCovers().

Referenced by SCIP_DECL_CONSSEPASOL().

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsSymresack  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 1763 of file cons_symresack.c.

References checkSymresackSolution(), CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSENFORELAX(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconshdlrGetName(), and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSENFOLP().

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxSymresack  )
static

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckSymresack  )
static

feasibility check method of constraint handler for integral solutions

Definition at line 1866 of file cons_symresack.c.

References checkSymresackSolution(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSPROP(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSENFORELAX().

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropSymresack  )
static

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolSymresack  )
static

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropSymresack  )
static

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockSymresack  )
static

lock variables

We assume we have only one global (void) constraint and lock all binary variables which do not correspond to fixed points of the permutation.

  • Symresack constraints may get violated if the variables with a negative coefficient in the FD inequality are rounded down, we therefor call SCIPaddVarLocksType(..., nlockspos, nlocksneg).
  • Symresack constraints may get violated if the variables with a positive coefficient in the FD inequality are rounded up, we therefor call SCIPaddVarLocksType(..., nlocksneg, nlockspo ).

Definition at line 2127 of file cons_symresack.c.

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

Referenced by SCIP_DECL_CONSRESPROP().

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintSymresack  )
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 2181 of file cons_symresack.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSGETVARS(), SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPinfoMessage(), SCIPvarGetName(), and TRUE.

Referenced by SCIP_DECL_CONSLOCK().

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsSymresack  )
static

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

Definition at line 2251 of file cons_symresack.c.

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

Referenced by SCIP_DECL_CONSPRINT().

◆ SCIP_DECL_CONSGETNVARS()

static SCIP_DECL_CONSGETNVARS ( consGetNVarsSymresack  )
static

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

Definition at line 2280 of file cons_symresack.c.

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

Referenced by SCIP_DECL_CONSGETVARS().