Scippy

SCIP

Solving Constraint Integer Programs

cons_pseudoboolean.h File Reference

Detailed Description

constraint handler for pseudoboolean constraints

Author
Stefan Heinz
Michael Winkler

The constraint handler deals with pseudo boolean constraints. These are constraints of the form

\[ \mbox{lhs} \leq \sum_{k=0}^m c_k \cdot x_k + \sum_{i=0}^n c_i \cdot \prod_{j \in I_i} x_j \leq \mbox{rhs} \]

where all $x$ are binary and all $c$ are integer.

Definition in file cons_pseudoboolean.h.

#include "scip/scip.h"

Go to the source code of this file.

Macros

#define ARTIFICIALVARNAMEPREFIX   "andresultant_"
 

Typedefs

typedef enum SCIP_LinearConsType SCIP_LINEARCONSTYPE
 

Enumerations

enum  SCIP_LinearConsType {
  SCIP_LINEARCONSTYPE_INVALIDCONS = -1,
  SCIP_LINEARCONSTYPE_LINEAR = 0,
  SCIP_LINEARCONSTYPE_LOGICOR = 1,
  SCIP_LINEARCONSTYPE_KNAPSACK = 2,
  SCIP_LINEARCONSTYPE_SETPPC = 3
}
 

Functions

SCIP_RETCODE SCIPincludeConshdlrPseudoboolean (SCIP *scip)
 
SCIP_RETCODE SCIPcreateConsPseudobooleanWithConss (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONS *lincons, SCIP_LINEARCONSTYPE linconstype, SCIP_CONS **andconss, SCIP_Real *andcoefs, int nandconss, SCIP_VAR *indvar, SCIP_Real weight, SCIP_Bool issoftcons, SCIP_VAR *intvar, SCIP_Real lhs, SCIP_Real rhs, 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 SCIPcreateConsPseudoboolean (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR **linvars, int nlinvars, SCIP_Real *linvals, SCIP_VAR ***terms, int nterms, int *ntermvars, SCIP_Real *termvals, SCIP_VAR *indvar, SCIP_Real weight, SCIP_Bool issoftcons, SCIP_VAR *intvar, SCIP_Real lhs, SCIP_Real rhs, 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 SCIPcreateConsBasicPseudoboolean (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR **linvars, int nlinvars, SCIP_Real *linvals, SCIP_VAR ***terms, int nterms, int *ntermvars, SCIP_Real *termvals, SCIP_VAR *indvar, SCIP_Real weight, SCIP_Bool issoftcons, SCIP_VAR *intvar, SCIP_Real lhs, SCIP_Real rhs)
 
SCIP_RETCODE SCIPaddCoefPseudoboolean (SCIP *const scip, SCIP_CONS *const cons, SCIP_VAR *const var, SCIP_Real const val)
 
SCIP_RETCODE SCIPaddTermPseudoboolean (SCIP *const scip, SCIP_CONS *const cons, SCIP_VAR **const vars, int const nvars, SCIP_Real const val)
 
SCIP_VARSCIPgetIndVarPseudoboolean (SCIP *const scip, SCIP_CONS *const cons)
 
SCIP_CONSSCIPgetLinearConsPseudoboolean (SCIP *const scip, SCIP_CONS *const cons)
 
SCIP_LINEARCONSTYPE SCIPgetLinearConsTypePseudoboolean (SCIP *const scip, SCIP_CONS *const cons)
 
int SCIPgetNLinVarsWithoutAndPseudoboolean (SCIP *const scip, SCIP_CONS *const cons)
 
SCIP_RETCODE SCIPgetLinDatasWithoutAndPseudoboolean (SCIP *const scip, SCIP_CONS *const cons, SCIP_VAR **const linvars, SCIP_Real *const lincoefs, int *const nlinvars)
 
SCIP_RETCODE SCIPgetAndDatasPseudoboolean (SCIP *const scip, SCIP_CONS *const cons, SCIP_CONS **const andconss, SCIP_Real *const andcoefs, int *const nandconss)
 
int SCIPgetNAndsPseudoboolean (SCIP *const scip, SCIP_CONS *const cons)
 
SCIP_RETCODE SCIPchgLhsPseudoboolean (SCIP *const scip, SCIP_CONS *const cons, SCIP_Real const lhs)
 
SCIP_RETCODE SCIPchgRhsPseudoboolean (SCIP *const scip, SCIP_CONS *const cons, SCIP_Real const rhs)
 
SCIP_Real SCIPgetLhsPseudoboolean (SCIP *const scip, SCIP_CONS *const cons)
 
SCIP_Real SCIPgetRhsPseudoboolean (SCIP *const scip, SCIP_CONS *const cons)
 

Macro Definition Documentation

#define ARTIFICIALVARNAMEPREFIX   "andresultant_"

Definition at line 42 of file cons_pseudoboolean.h.

Typedef Documentation

Definition at line 58 of file cons_pseudoboolean.h.

Enumeration Type Documentation

solution status after solving LP

Enumerator
SCIP_LINEARCONSTYPE_INVALIDCONS 

this is no valid linear constraint type

SCIP_LINEARCONSTYPE_LINEAR 

this is the common linear constraint

SCIP_LINEARCONSTYPE_LOGICOR 

this is a logicor constraint

SCIP_LINEARCONSTYPE_KNAPSACK 

this is a knapsack constraint

SCIP_LINEARCONSTYPE_SETPPC 

this is a setppc constraint

Definition at line 45 of file cons_pseudoboolean.h.

Function Documentation

SCIP_RETCODE SCIPincludeConshdlrPseudoboolean ( SCIP scip)

creates the handler for pseudoboolean constraints and includes it in SCIP

Parameters
scipSCIP data structure
SCIP_RETCODE SCIPcreateConsPseudobooleanWithConss ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
SCIP_CONS lincons,
SCIP_LINEARCONSTYPE  linconstype,
SCIP_CONS **  andconss,
SCIP_Real andcoefs,
int  nandconss,
SCIP_VAR indvar,
SCIP_Real  weight,
SCIP_Bool  issoftcons,
SCIP_VAR intvar,
SCIP_Real  lhs,
SCIP_Real  rhs,
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 
)

creates and captures a pseudoboolean constraint, with given linear and and-constraints

Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
linconsassociated linear constraint
linconstypelinear constraint type of associated linear constraint
andconssassociated and-constraints
andcoefsassociated coefficients of and-constraints
nandconssnumber of associated and-constraints
indvarindicator variable if it's a soft constraint, or NULL
weightweight of the soft constraint, if it is one
issoftconsis this a soft constraint
intvara artificial variable which was added only for the objective function, if this variable is not NULL this constraint (without this integer variable) describes the objective funktion
lhsleft hand side of constraint
rhsright hand side of constraint
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 seperated 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.
SCIP_RETCODE SCIPcreateConsPseudoboolean ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
SCIP_VAR **  linvars,
int  nlinvars,
SCIP_Real linvals,
SCIP_VAR ***  terms,
int  nterms,
int *  ntermvars,
SCIP_Real termvals,
SCIP_VAR indvar,
SCIP_Real  weight,
SCIP_Bool  issoftcons,
SCIP_VAR intvar,
SCIP_Real  lhs,
SCIP_Real  rhs,
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 
)

creates and captures a pseudoboolean constraint

Note
linear and nonlinear terms can be added using SCIPaddCoefPseudoboolean() and SCIPaddTermPseudoboolean(), respectively
the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
linvarsvariables of the linear part, or NULL
nlinvarsnumber of variables of the linear part
linvalscoefficients of linear part, or NULL
termsnonlinear terms of variables, or NULL
ntermsnumber of terms of variables of nonlinear term
ntermvarsnumber of variables in nonlinear terms, or NULL
termvalscoefficients of nonlinear parts, or NULL
indvarindicator variable if it's a soft constraint, or NULL
weightweight of the soft constraint, if it is one
issoftconsis this a soft constraint
intvara artificial variable which was added only for the objective function, if this variable is not NULL this constraint (without this integer variable) describes the objective function
lhsleft hand side of constraint
rhsright hand side of constraint
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.
SCIP_RETCODE SCIPcreateConsBasicPseudoboolean ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
SCIP_VAR **  linvars,
int  nlinvars,
SCIP_Real linvals,
SCIP_VAR ***  terms,
int  nterms,
int *  ntermvars,
SCIP_Real termvals,
SCIP_VAR indvar,
SCIP_Real  weight,
SCIP_Bool  issoftcons,
SCIP_VAR intvar,
SCIP_Real  lhs,
SCIP_Real  rhs 
)

creates and captures a pseudoboolean constraint in its most basic variant, i. e., with all constraint flags set to their default values, which can be set afterwards using SCIPsetConsFLAGNAME() in scip.h

See also
SCIPcreateConsPseudoboolean() for the default constraint flag configuration
Note
the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
linvarsvariables of the linear part, or NULL
nlinvarsnumber of variables of the linear part
linvalscoefficients of linear part, or NULL
termsnonlinear terms of variables, or NULL
ntermsnumber of terms of variables of nonlinear term
ntermvarsnumber of variables in nonlinear terms, or NULL
termvalscoefficients of nonlinear parts, or NULL
indvarindicator variable if it's a soft constraint, or NULL
weightweight of the soft constraint, if it is one
issoftconsis this a soft constraint
intvara artificial variable which was added only for the objective function, if this variable is not NULL this constraint (without this integer variable) describes the objective function
lhsleft hand side of constraint
rhsright hand side of constraint
SCIP_RETCODE SCIPaddCoefPseudoboolean ( SCIP *const  scip,
SCIP_CONS *const  cons,
SCIP_VAR *const  var,
SCIP_Real const  val 
)

adds linear term pseudo boolean constraint (if it is not zero)

Note
you can only add a coefficient if the special type of linear constraint won't changed
Parameters
scipSCIP data structure
conspseudoboolean constraint
varvariable of constraint entry
valcoefficient of constraint entry
SCIP_RETCODE SCIPaddTermPseudoboolean ( SCIP *const  scip,
SCIP_CONS *const  cons,
SCIP_VAR **const  vars,
int const  nvars,
SCIP_Real const  val 
)

adds nonlinear term to pseudo boolean constraint (if it is not zero)

Note
you can only add a coefficient if the special type of linear constraint won't changed
Parameters
scipSCIP data structure
conspseudoboolean constraint
varsvariables of the nonlinear term
nvarsnumber of variables of the nonlinear term
valcoefficient of constraint entry
SCIP_VAR* SCIPgetIndVarPseudoboolean ( SCIP *const  scip,
SCIP_CONS *const  cons 
)

gets indicator variable of pseudoboolean constraint, or NULL if there is no

Parameters
scipSCIP data structure
conspseudoboolean constraint
SCIP_CONS* SCIPgetLinearConsPseudoboolean ( SCIP *const  scip,
SCIP_CONS *const  cons 
)

gets linear constraint of pseudoboolean constraint

Parameters
scipSCIP data structure
conspseudoboolean constraint
SCIP_LINEARCONSTYPE SCIPgetLinearConsTypePseudoboolean ( SCIP *const  scip,
SCIP_CONS *const  cons 
)

gets type of linear constraint of pseudoboolean constraint

Parameters
scipSCIP data structure
conspseudoboolean constraint
int SCIPgetNLinVarsWithoutAndPseudoboolean ( SCIP *const  scip,
SCIP_CONS *const  cons 
)

gets number of linear variables without artificial terms variables of pseudoboolean constraint

Parameters
scipSCIP data structure
conspseudoboolean constraint
SCIP_RETCODE SCIPgetLinDatasWithoutAndPseudoboolean ( SCIP *const  scip,
SCIP_CONS *const  cons,
SCIP_VAR **const  linvars,
SCIP_Real *const  lincoefs,
int *const  nlinvars 
)

gets linear constraint of pseudoboolean constraint

Parameters
scipSCIP data structure
conspseudoboolean constraint
linvarsarray to store and-constraints
lincoefsarray to store and-coefficients
nlinvarspointer to store the required array size for and-constraints, have to be initialized with size of given array
SCIP_RETCODE SCIPgetAndDatasPseudoboolean ( SCIP *const  scip,
SCIP_CONS *const  cons,
SCIP_CONS **const  andconss,
SCIP_Real *const  andcoefs,
int *const  nandconss 
)

gets and-constraints of pseudoboolean constraint

Parameters
scipSCIP data structure
conspseudoboolean constraint
andconssarray to store and-constraints
andcoefsarray to store and-coefficients
nandconsspointer to store the required array size for and-constraints, have to be initialized with size of given array
int SCIPgetNAndsPseudoboolean ( SCIP *const  scip,
SCIP_CONS *const  cons 
)

gets number of and constraints of pseudoboolean constraint

Parameters
scipSCIP data structure
conspseudoboolean constraint
SCIP_RETCODE SCIPchgLhsPseudoboolean ( SCIP *const  scip,
SCIP_CONS *const  cons,
SCIP_Real const  lhs 
)

changes left hand side of pseudoboolean constraint

Note
you can only change the left hand side if the special type of linear constraint won't changed
Parameters
scipSCIP data structure
conspseudoboolean constraint
lhsnew left hand side
SCIP_RETCODE SCIPchgRhsPseudoboolean ( SCIP *const  scip,
SCIP_CONS *const  cons,
SCIP_Real const  rhs 
)

changes right hand side of pseudoboolean constraint

Note
you can only change the right hand side if the special type of linear constraint won't changed
Parameters
scipSCIP data structure
conspseudoboolean constraint
rhsnew right hand side
SCIP_Real SCIPgetLhsPseudoboolean ( SCIP *const  scip,
SCIP_CONS *const  cons 
)

get left hand side of pseudoboolean constraint

Parameters
scipSCIP data structure
conspseudoboolean constraint
SCIP_Real SCIPgetRhsPseudoboolean ( SCIP *const  scip,
SCIP_CONS *const  cons 
)

get right hand side of pseudoboolean constraint

Parameters
scipSCIP data structure
conspseudoboolean constraint