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_Real *	SCIPgetValsLinear (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_ROW *	SCIPgetRowLinear (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)

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

typedef struct SCIP_LinConsUpgrade SCIP_LINCONSUPGRADE

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

scip	SCIP data structure

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

scip	SCIP data structure
priority	priority of upgrading method
conshdlrname	name of the constraint handler

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

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of nonzeros in the constraint
vars	array with variables of constraint entries
vals	array with coefficients of constraint entries
lhs	left hand side of constraint
rhs	right hand side of constraint
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separate	should the constraint be separated during LP processing? Usually set to TRUE.
enforce	should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
check	should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagate	should the constraint be propagated during node processing? Usually set to TRUE.
local	is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiable	is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamic	is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removable	should 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'.
stickingatnode	should 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 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

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of nonzeros in the constraint
vars	array with variables of constraint entries
vals	array with coefficients of constraint entries
lhs	left hand side of constraint
rhs	right hand side of constraint

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

scip	target SCIP data structure
cons	pointer to store the created target constraint
sourcescip	source SCIP data structure
name	name of constraint
nvars	number of variables in source variable array
sourcevars	source variables of the linear constraints
sourcecoefs	coefficient array of the linear constraint, or NULL if all coefficients are one
lhs	left hand side of the linear constraint
rhs	right hand side of the linear constraint
varmap	a SCIP_HASHMAP mapping variables of the source SCIP to corresponding variables of the target SCIP
consmap	a hashmap to store the mapping of source constraints to the corresponding target constraints
initial	should the LP relaxation of constraint be in the initial LP?
separate	should the constraint be separated during LP processing?
enforce	should the constraint be enforced during node processing?
check	should the constraint be checked for feasibility?
propagate	should the constraint be propagated during node processing?
local	is constraint only valid locally?
modifiable	is constraint modifiable (subject to column generation)?
dynamic	is constraint subject to aging?
removable	should the relaxation be removed from the LP due to aging or cleanup?
stickingatnode	should the constraint always be kept at the node where it was added, even if it may be moved to a more global node?
global	create a global or a local copy?
valid	pointer to store if the copying was valid

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

adds coefficient to linear constraint (if it is not zero)

Parameters

scip	SCIP data structure
cons	constraint data
var	variable of constraint entry
val	coefficient of constraint entry

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

scip	SCIP data structure
cons	constraint data
var	variable of constraint entry
val	new coefficient of constraint entry

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

scip	SCIP data structure
cons	constraint data
var	variable of constraint entry

SCIP_Real SCIPgetLhsLinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets left hand side of linear constraint

Parameters

scip	SCIP data structure
cons	constraint data

SCIP_Real SCIPgetRhsLinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets right hand side of linear constraint

Parameters

scip	SCIP data structure
cons	constraint data

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

changes left hand side of linear constraint

Parameters

scip	SCIP data structure
cons	constraint data
lhs	new left hand side

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

changes right hand side of linear constraint

Parameters

scip	SCIP data structure
cons	constraint data
rhs	new right hand side

int SCIPgetNVarsLinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the number of variables in the linear constraint

Parameters

scip	SCIP data structure
cons	constraint data

SCIP_VAR** SCIPgetVarsLinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the array of variables in the linear constraint; the user must not modify this array!

Parameters

scip	SCIP data structure
cons	constraint data

SCIP_Real* SCIPgetValsLinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the array of coefficient values in the linear constraint; the user must not modify this array!

Parameters

scip	SCIP data structure
cons	constraint data

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

scip	SCIP data structure
cons	constraint data
sol	solution, or NULL to use current node's solution

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

gets the feasibility of the linear constraint in the given solution

Parameters

scip	SCIP data structure
cons	constraint data
sol	solution, or NULL to use current node's solution

SCIP_Real SCIPgetDualsolLinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

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

Parameters

scip	SCIP data structure
cons	constraint data

SCIP_Real SCIPgetDualfarkasLinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

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

Parameters

scip	SCIP data structure
cons	constraint data

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

scip	SCIP data structure
cons	constraint data

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

scip	SCIP data structure
cons	source constraint to try to convert
upgdcons	pointer to store upgraded constraint, or NULL if not successful

SCIP

Detailed Description

Macros

Typedefs

Functions

Macro Definition Documentation

Typedef Documentation

Function Documentation