Scippy

SCIP

Solving Constraint Integer Programs

cons_linear.h File Reference

Detailed Description

Constraint handler for linear constraints in their most general form, $lhs <= a^T x <= rhs$.

Author
Tobias Achterberg
Timo Berthold
Marc Pfetsch
Kati Wolter

This constraint handler handles linear constraints in their most general form. That is,

\[ lhs \leq \sum_{i=1}^n a_i x_i \leq rhs \]

with $a_i \in Q, i = 1,\dots,n$, $lhs\in Q \cup \{-\infty\}$, $rhs\in Q \cup \{\infty\}$, and decision variables $x_i, i = 1,\dots,n$ which can be binary, integer, or continuous.

Furthermore, this header offers the upgrade functionality of a general linear constraint into a more specific constraint, such as a knapsack constraint, via SCIP_DECL_LINCONSUPGD() and SCIPincludeLinconsUpgrade()

Definition in file cons_linear.h.

#include "scip/scip.h"

Go to the source code of this file.

Macros

#define SCIP_DECL_LINCONSUPGD(x)
 

Typedefs

typedef struct SCIP_LinConsUpgrade SCIP_LINCONSUPGRADE
 

Functions

SCIP_RETCODE SCIPincludeConshdlrLinear (SCIP *scip)
 
SCIP_RETCODE SCIPincludeLinconsUpgrade (SCIP *scip, SCIP_DECL_LINCONSUPGD((*linconsupgd)), int priority, const char *conshdlrname)
 
SCIP_RETCODE SCIPcreateConsLinear (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, 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 SCIPcreateConsBasicLinear (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
 
SCIP_RETCODE SCIPcopyConsLinear (SCIP *scip, SCIP_CONS **cons, SCIP *sourcescip, const char *name, int nvars, SCIP_VAR **sourcevars, SCIP_Real *sourcecoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, 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_Bool global, SCIP_Bool *valid)
 
SCIP_RETCODE SCIPaddCoefLinear (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
 
SCIP_RETCODE SCIPchgCoefLinear (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
 
SCIP_RETCODE SCIPdelCoefLinear (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
 
SCIP_Real SCIPgetLhsLinear (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real SCIPgetRhsLinear (SCIP *scip, SCIP_CONS *cons)
 
SCIP_RETCODE SCIPchgLhsLinear (SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
 
SCIP_RETCODE SCIPchgRhsLinear (SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
 
int SCIPgetNVarsLinear (SCIP *scip, SCIP_CONS *cons)
 
SCIP_VAR ** SCIPgetVarsLinear (SCIP *scip, SCIP_CONS *cons)
 
SCIP_RealSCIPgetValsLinear (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real SCIPgetActivityLinear (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
 
SCIP_Real SCIPgetFeasibilityLinear (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
 
SCIP_Real SCIPgetDualsolLinear (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real SCIPgetDualfarkasLinear (SCIP *scip, SCIP_CONS *cons)
 
SCIP_ROWSCIPgetRowLinear (SCIP *scip, SCIP_CONS *cons)
 
SCIP_RETCODE SCIPupgradeConsLinear (SCIP *scip, SCIP_CONS *cons, SCIP_CONS **upgdcons)
 

Macro Definition Documentation

#define SCIP_DECL_LINCONSUPGD (   x)
Value:
SCIP_RETCODE x (SCIP* scip, SCIP_CONS* cons, int nvars, SCIP_VAR** vars, SCIP_Real* vals, SCIP_Real lhs, SCIP_Real rhs, \
int nposbin, int nnegbin, int nposint, int nnegint, int nposimpl, int nnegimpl, int nposimplbin, int nnegimplbin, int nposcont, int nnegcont, \
int ncoeffspone, int ncoeffsnone, int ncoeffspint, int ncoeffsnint, int ncoeffspfrac, int ncoeffsnfrac, \
SCIP_Real poscoeffsum, SCIP_Real negcoeffsum, SCIP_Bool integral, SCIP_CONS** upgdcons)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIP_Bool
Definition: def.h:53
#define SCIP_Real
Definition: def.h:127

upgrading method for linear constraints into more specific constraints

input:

  • scip : SCIP main data structure
  • cons : the linear constraint to upgrade
  • nvars : number of variables in the constraint
  • vars : array with constraint variables
  • vals : array with constraint coefficients
  • lhs : left hand side of linear constraint
  • rhs : right hand side of linear constraint
  • nposbin : number of binary variables with positive coefficient
  • nnegbin : number of binary variables with negative coefficient
  • nposint : number of integer variables with positive coefficient
  • nnegint : number of integer variables with negative coefficient
  • nposimpl : number of implicit integer variables with positive coefficient (including implicit binary variables)
  • nnegimpl : number of implicit integer variables with negative coefficient (including implicit binary variables)
  • nposimplbin : number of implicit binary variables with positive coefficient
  • nnegimplbin : number of implicit binary variables with negative coefficient
  • nposcont : number of continuous variables with positive coefficient
  • nnegcont : number of continuous variables with negative coefficient
  • ncoeffspone : number of +1 coefficients
  • ncoeffsnone : number of -1 coefficients
  • ncoeffspint : number of positive integral coefficients other than +1
  • ncoeffsnint : number of negative integral coefficients other than -1
  • ncoeffspfrac : number of positive fractional coefficients
  • ncoeffsnfrac : number of negative fractional coefficients
  • poscoeffsum : sum of all positive coefficients
  • negcoeffsum : sum of all negative coefficients
  • integral : TRUE iff constraints activity value is always integral
  • upgdcons : pointer to store the upgraded constraint

Definition at line 81 of file cons_linear.h.

Typedef Documentation

linear constraint update method

Definition at line 46 of file cons_linear.h.

Function Documentation

SCIP_RETCODE SCIPincludeConshdlrLinear ( SCIP scip)

creates the handler for linear constraints and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 15871 of file cons_linear.c.

Referenced by SCIP_DECL_NONLINCONSUPGD(), and SCIPincludeDefaultPlugins().

SCIP_RETCODE SCIPincludeLinconsUpgrade ( SCIP scip,
SCIP_DECL_LINCONSUPGD((*linconsupgd))  ,
int  priority,
const char *  conshdlrname 
)

includes a linear constraint update method into the linear constraint handler

Parameters
scipSCIP data structure
prioritypriority of upgrading method
conshdlrnamename of the constraint handler

Definition at line 16047 of file cons_linear.c.

Referenced by SCIPincludeConshdlrIndicator(), SCIPincludeConshdlrLogicor(), SCIPincludeConshdlrVarbound(), and SCIPincludeConshdlrXor().

SCIP_RETCODE SCIPcreateConsLinear ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
int  nvars,
SCIP_VAR **  vars,
SCIP_Real vals,
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 linear constraint

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
nvarsnumber of nonzeros in the constraint
varsarray with variables of constraint entries
valsarray with coefficients of constraint entries
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.

Definition at line 16099 of file cons_linear.c.

References consCatchAllEvents(), consdataCreate(), CONSHDLR_NAME, FALSE, needEvents(), NULL, REALABS, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_Real, SCIP_STAGE_EXITPRESOLVE, SCIPABORT, SCIPconshdlrGetData(), SCIPcreateCons(), SCIPcreateConsBasicLinear(), SCIPcreateConsLinear(), SCIPduplicateBufferArray, SCIPerrorMessage, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetProbvarLinearSum(), SCIPgetStage(), SCIPinfinity(), SCIPisInfinity(), SCIPisTransformed(), SCIPreallocBufferArray, and TRUE.

Referenced by addBranchingComplementaritiesSOS1(), addExtendedAsymmetricFormulation(), addExtendedFlowFormulation(), addLocalBranchingConstraint(), aggregateConstraints(), applyFixings(), consdataLinearize(), copyCuts(), CREATE_CONSTRAINT(), createAndAddLinearCons(), createConstraints(), createCoveringProblem(), createLinearCons(), createNAryBranch(), createRows(), createSubproblem(), createSubSCIP(), createSubscip(), dualPresolve(), fixDeleteOrUpgradeCons(), fixVariableZeroNode(), forbidCover(), getFixedVariable(), preprocessConstraintPairs(), presolveCreateBenTalNemirovskiApproxDim3(), presolveCreateGlineurApproxDim3(), presolveFindDuplicates(), presolveFindDuplicatesUpgradeCons(), presolveRemoveFixedVariables(), presolveTryAddLinearReform(), propIndicator(), readCnf(), readConstraints(), readOPBFile(), readRows(), replaceByLinearConstraints(), replaceViolatedByLinearConstraints(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSINITPRE(), SCIP_DECL_CONSPRESOL(), SCIP_DECL_NONLINCONSUPGD(), SCIP_DECL_QUADCONSUPGD(), SCIPapplyZeroobj(), SCIPcopyConsLinear(), SCIPcreateConsIndicator(), SCIPcreateConsLinear(), SCIPgetVarCopy(), selectVarMultAggrBranching(), tightenBounds(), tryUpgradingLogicor(), tryUpgradingSetppc(), and upgradeLinearSuperindicator().

SCIP_RETCODE SCIPcreateConsBasicLinear ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
int  nvars,
SCIP_VAR **  vars,
SCIP_Real vals,
SCIP_Real  lhs,
SCIP_Real  rhs 
)

creates and captures a linear constraint in its most basic version, i. e., all constraint flags are set to their basic value as explained for the method SCIPcreateConsLinear(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h

See also
SCIPcreateConsLinear() for information about the basic 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
nvarsnumber of nonzeros in the constraint
varsarray with variables of constraint entries
valsarray with coefficients of constraint entries
lhsleft hand side of constraint
rhsright hand side of constraint

Definition at line 16291 of file cons_linear.c.

Referenced by createMIP(), SCIPapplyProximity(), SCIPcreateConsLinear(), and SCIPcreateFiniteSolCopy().

SCIP_RETCODE SCIPcopyConsLinear ( SCIP scip,
SCIP_CONS **  cons,
SCIP sourcescip,
const char *  name,
int  nvars,
SCIP_VAR **  sourcevars,
SCIP_Real sourcecoefs,
SCIP_Real  lhs,
SCIP_Real  rhs,
SCIP_HASHMAP varmap,
SCIP_HASHMAP consmap,
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_Bool  global,
SCIP_Bool valid 
)

creates by copying and captures a linear constraint

Parameters
sciptarget SCIP data structure
conspointer to store the created target constraint
sourcescipsource SCIP data structure
namename of constraint
nvarsnumber of variables in source variable array
sourcevarssource variables of the linear constraints
sourcecoefscoefficient array of the linear constraint, or NULL if all coefficients are one
lhsleft hand side of the linear constraint
rhsright hand side of the linear constraint
varmapa SCIP_HASHMAP mapping variables of the source SCIP to corresponding variables of the target SCIP
consmapa hashmap to store the mapping of source constraints to the corresponding target constraints
initialshould the LP relaxation of constraint be in the initial LP?
separateshould the constraint be separated during LP processing?
enforceshould the constraint be enforced during node processing?
checkshould the constraint be checked for feasibility?
propagateshould the constraint be propagated during node processing?
localis constraint only valid locally?
modifiableis constraint modifiable (subject to column generation)?
dynamicis constraint subject to aging?
removableshould the relaxation be removed from the LP due to aging or cleanup?
stickingatnodeshould the constraint always be kept at the node where it was added, even if it may be moved to a more global node?
globalcreate a global or a local copy?
validpointer to store if the copying was valid

Definition at line 16311 of file cons_linear.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPallocBufferArray, SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPcreateConsLinear(), SCIPduplicateBufferArray, SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetProbvarLinearSum(), SCIPgetVarCopy(), SCIPisGT(), SCIPisInfinity(), SCIPreallocBufferArray, SCIPvarGetOrigvarSum(), SCIPvarIsOriginal(), and TRUE.

Referenced by SCIP_DECL_CONSCOPY().

SCIP_RETCODE SCIPchgCoefLinear ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var,
SCIP_Real  val 
)

changes coefficient of variable in linear constraint; deletes the variable if coefficient is zero; adds variable if not yet contained in the constraint

Note
This method may only be called during problem creation stage for an original constraint and variable.
This method requires linear time to search for occurences of the variable in the constraint data.
Parameters
scipSCIP data structure
consconstraint data
varvariable of constraint entry
valnew coefficient of constraint entry

Definition at line 16597 of file cons_linear.c.

References chgCoefPos(), delCoefPos(), FALSE, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_STAGE_PROBLEM, SCIPaddCoefLinear(), SCIPchgCoefLinear(), SCIPconsGetData(), SCIPconsIsOriginal(), SCIPdelCoefLinear(), SCIPerrorMessage, SCIPgetStage(), SCIPisZero(), SCIPvarIsOriginal(), and TRUE.

Referenced by SCIPaddCoefLinear(), and SCIPchgCoefLinear().

SCIP_RETCODE SCIPdelCoefLinear ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var 
)

deletes variable from linear constraint

Note
This method may only be called during problem creation stage for an original constraint and variable.
This method requires linear time to search for occurences of the variable in the constraint data.
Parameters
scipSCIP data structure
consconstraint data
varvariable of constraint entry

Definition at line 16665 of file cons_linear.c.

References CONSHDLR_NAME, NULL, SCIP_INVALID, SCIPABORT, SCIPconsGetHdlr(), SCIPconshdlrGetName(), and SCIPerrorMessage.

Referenced by SCIPchgCoefLinear().

SCIP_RETCODE SCIPchgLhsLinear ( SCIP scip,
SCIP_CONS cons,
SCIP_Real  lhs 
)

changes left hand side of linear constraint

Parameters
scipSCIP data structure
consconstraint data
lhsnew left hand side

Definition at line 16729 of file cons_linear.c.

References chgRhs(), CONSHDLR_NAME, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconshdlrGetName(), and SCIPerrorMessage.

Referenced by applyFixings(), chgLhsLinearCons(), fixDiscreteVars(), readIndicators(), readRanges(), readRhs(), SCIP_DECL_PRESOLEXEC(), and tryUpgradingLogicor().

SCIP_RETCODE SCIPchgRhsLinear ( SCIP scip,
SCIP_CONS cons,
SCIP_Real  rhs 
)

changes right hand side of linear constraint

Parameters
scipSCIP data structure
consconstraint data
rhsnew right hand side

Definition at line 16750 of file cons_linear.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetHdlr(), SCIPconshdlrGetName(), and SCIPerrorMessage.

Referenced by applyFixings(), chgRhsLinearCons(), fixDiscreteVars(), readRanges(), readRhs(), SCIP_DECL_PRESOLEXEC(), SCIPapplyHeurDualval(), SCIPapplyProximity(), and tryUpgradingSetppc().

SCIP_Real SCIPgetActivityLinear ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol 
)

gets the activity of the linear constraint in the given solution

Note
if the solution contains values at infinity, this method will return SCIP_INVALID in case the activity comprises positive and negative infinity contributions
Parameters
scipSCIP data structure
consconstraint data
solsolution, or NULL to use current node's solution

Definition at line 16844 of file cons_linear.c.

SCIP_Real SCIPgetFeasibilityLinear ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol 
)

gets the feasibility of the linear constraint in the given solution

Parameters
scipSCIP data structure
consconstraint data
solsolution, or NULL to use current node's solution

Definition at line 16872 of file cons_linear.c.

SCIP_Real SCIPgetDualsolLinear ( SCIP scip,
SCIP_CONS cons 
)

gets the dual solution of the linear constraint in the current LP

Parameters
scipSCIP data structure
consconstraint data

Definition at line 16900 of file cons_linear.c.

Referenced by printDualSol(), and SCIP_DECL_EVENTEXEC().

SCIP_Real SCIPgetDualfarkasLinear ( SCIP scip,
SCIP_CONS cons 
)

gets the dual Farkas value of the linear constraint in the current infeasible LP

Parameters
scipSCIP data structure
consconstraint data

Definition at line 16927 of file cons_linear.c.

SCIP_ROW* SCIPgetRowLinear ( SCIP scip,
SCIP_CONS cons 
)

returns the linear relaxation of the given linear constraint; may return NULL if no LP row was yet created; the user must not modify the row!

Parameters
scipSCIP data structure
consconstraint data

Definition at line 16956 of file cons_linear.c.

SCIP_RETCODE SCIPupgradeConsLinear ( SCIP scip,
SCIP_CONS cons,
SCIP_CONS **  upgdcons 
)

tries to automatically convert a linear constraint into a more specific and more specialized constraint

Parameters
scipSCIP data structure
conssource constraint to try to convert
upgdconspointer to store upgraded constraint, or NULL if not successful

Definition at line 16980 of file cons_linear.c.