constraint propagation engine API More...

Typedefs
typedef struct _CProp	CProp

Enumerations
enum	IGNType { EOne, EZero, Infeasible }
	Implication Graph Node Types. More...

Functions
CProp *	cprop_create (int cols, const char integer[], const double lb[], const double ub[], const char **name)
	creates a new CProp object More...

int	cprop_add_constraint (CProp *cprop, int nz, const int idx[], const double coef[], char sense, double rhs, const char rname[])
	adds a new constraint More...

int	cprop_update_bound (CProp *cprop, int j, double l, double u)
	updates the bounds of a variable More...

void	cprop_undo (CProp *cprop)
	undo the last bound changed and all its implications More...

char	cprop_feasible (const CProp *cprop)
	returns 1 if problem is still feasible, zero otherwise More...

const char *	cprop_inf_msg (const CProp *cprop)
	message explaining how infeasibility was detected More...

int	cprop_n_implications (const CProp *cprop)
	returns how many implications the last change produced More...

int	cprop_implied_var (const CProp *cprop, int i)
	returns the i-th variable which bound was implied in the last operation More...

double	cprop_get_lb (const CProp *cprop, int j)
	returns the current lower bound for column j More...

double	cprop_get_ub (const CProp *cprop, int j)
	returns the current upper bound for column j More...

enum IGNType	cprop_impl_graph_node_type (const CProp *cprop, int nodeId)
	returns the node type More...

int	cprop_impl_graph_node_var (const CProp *cprop, int nodeId)
	returns the variable which a node refers More...

int	cprop_impl_graph_node_id (const CProp *cprop, enum IGNType ntype, int col)
	returns the node id More...

int	cprop_impl_graph_in_d (const CProp *cprop, int nodeId)
	number of incident arcs in implication graph node More...

int	cprop_impl_graph_in_neigh (const CProp *cprop, int nodeId, int i)
	returns the origin of the i-th incident arc to nodeId More...

void	cprop_save_impl_graph (const CProp cprop, const char fName)
	saves the implication graph in the DOT file format (graphviz) More...

int	cprop_n_cuts (const CProp *cprop)
	returns the number of cuts found processing the last infeasible solution More...

int	cprop_cut_nz (const CProp *cprop, int idxCut)
	returns the number of variables that appear on cut idxCut More...

const int *	cprop_cut_idx (const CProp *cprop, int idxCut)
	returns a vector with all columns of cut idxCut More...

const double *	cprop_cut_coef (const CProp *cprop, int idxCut)
	returns a vector with all coefficients of cut idxCut More...

char	cprop_cut_sense (const CProp *cprop, int idxCut)
	returns the sense of cut idxCut More...

double	cprop_cut_rhs (const CProp *cprop, int idxCut)
	returns the right hand side of cut idxCut More...

void	cprop_set_verbose (CProp *cprop, char verbose)
	activates detailed printing of implications as they are discovered More...

void	cprop_free (CProp **cprop)
	frees memory of cprop object More...

Detailed Description

constraint propagation engine API

A simple, solver independent, Constraint Propagation engine for binary programs based on the technical report "Nogood Learning for Mixed Integer Programming", from Sandhol, T. and Shields, R. (2006) [https://www.cs.cmu.edu/~sandholm/nogoodsForMip.techReport06.pdf].

Definition in file cprop.h.

Enumeration Type Documentation

◆ IGNType

enum IGNType

Implication Graph Node Types.

Enumerator
EOne	variable fixed at one
EZero	variable fixed at zero
Infeasible	infeasible node

Definition at line 131 of file cprop.h.

Function Documentation

◆ cprop_add_constraint()

int cprop_add_constraint	(	CProp *	cprop,
		int	nz,
		const int	idx[],
		const double	coef[],
		char	sense,
		double	rhs,
		const char	rname[]
	)

adds a new constraint

Adds a new constraint and performs constraint propagation (CP). Returns 0 if not implication was found, -1 if CP indicates that the problem became unfeasible or >0 if new implications (changed variable bounds) were generated. Complexity is O(nz) (unless there are new implications in bounds).

Parameters

CProp	constraint propagation object
nz	non-zero variables in this constraint
idx	indice of each non-zero variable
coef	coefficient of each non-zero variable
sense	E equal G greater-or-equal L less-or-equal
rhs	right-hand-side
rname	row name

◆ cprop_create()

CProp* cprop_create	(	int	cols,
		const char	integer[],
		const double	lb[],
		const double	ub[],
		const char **	name
	)

creates a new CProp object

Creates a new Constraint Propagation object entering information about all variables.

Parameters

cols	number of variables
integer	indicates if each variable is integer or not
lb	lower bound of each variable
ub	upper bound of each variable
name	names of variables, useful for debuging

◆ cprop_cut_coef()

const double* cprop_cut_coef	(	const CProp *	cprop,
		int	idxCut
	)

returns a vector with all coefficients of cut idxCut

Parameters

cprop	constraint propagation object
idxCut	cut index

Returns: vector with coefficients of cut idxCut

◆ cprop_cut_idx()

const int* cprop_cut_idx	(	const CProp *	cprop,
		int	idxCut
	)

returns a vector with all columns of cut idxCut

Parameters

cprop	constraint propagation object
idxCut	cut index

Returns: vector with column indexes of cut idxCut

◆ cprop_cut_nz()

int cprop_cut_nz	(	const CProp *	cprop,
		int	idxCut
	)

returns the number of variables that appear on cut idxCut

Parameters

cprop	constraint propagation object
idxCut	cut index

Returns: number of non-zeros in cut idxCut

◆ cprop_cut_rhs()

double cprop_cut_rhs	(	const CProp *	cprop,
		int	idxCut
	)

returns the right hand side of cut idxCut

Parameters

cprop	constraint propagation object
idxCut	cut index

Returns: right hand size of cut idxCut

◆ cprop_cut_sense()

char cprop_cut_sense	(	const CProp *	cprop,
		int	idxCut
	)

returns the sense of cut idxCut

Parameters

cprop	constraint propagation object
idxCut	cut index

Returns: E for equal, L for less or equal and G for greater or equal

◆ cprop_feasible()

char cprop_feasible ( const CProp * cprop )

returns 1 if problem is still feasible, zero otherwise

Parameters

cprop constraint propagation object

◆ cprop_free()

void cprop_free ( CProp ** cprop )

frees memory of cprop object

Frees memory of cprop object and sets it to NULL

◆ cprop_get_lb()

double cprop_get_lb	(	const CProp *	cprop,
		int	j
	)

returns the current lower bound for column j

Parameters

cprop	constraint propagation object
j	index of variable

◆ cprop_get_ub()

double cprop_get_ub	(	const CProp *	cprop,
		int	j
	)

returns the current upper bound for column j

Parameters

cprop	constraint propagation object
j	index of variable

◆ cprop_impl_graph_in_d()

int cprop_impl_graph_in_d	(	const CProp *	cprop,
		int	nodeId
	)

number of incident arcs in implication graph node

Returns the number of incident arcs in the implication graph for a node with id nodeId col is ignored if a node of type Infeasible is informed

Parameters

cprop	Constraint Propagation Object
nodeId	nodeId

◆ cprop_impl_graph_in_neigh()

int cprop_impl_graph_in_neigh	(	const CProp *	cprop,
		int	nodeId,
		int	i
	)

returns the origin of the i-th incident arc to nodeId

Returns the nodeId of the origin of the i-th incident arc in node nodeId

Parameters

cprop	Constraint Propagation Object
nodeid	nodeId

◆ cprop_impl_graph_node_id()

int cprop_impl_graph_node_id	(	const CProp *	cprop,
		enum IGNType	ntype,
		int	col
	)

returns the node id

Returns the node id for a node of type ntype related to column col

Parameters

cprop	constraint propagation object
ntype	node type
col	variable (column) index

◆ cprop_impl_graph_node_type()

enum IGNType cprop_impl_graph_node_type	(	const CProp *	cprop,
		int	nodeId
	)

returns the node type

Returns the node type of a node in the implication graph

Parameters

cprop	constraint propagation object
nodeId	id of the node in the graph

◆ cprop_impl_graph_node_var()

int cprop_impl_graph_node_var	(	const CProp *	cprop,
		int	nodeId
	)

returns the variable which a node refers

Returns the variable thar a node in the implication graph refers to

Parameters

cprop	constraint propagation object
nodeId	id of the node in the graph

◆ cprop_implied_var()

int cprop_implied_var	(	const CProp *	cprop,
		int	i
	)

returns the i-th variable which bound was implied in the last operation

Parameters

cprop	constraint propagation object
i	the i-th variable which a bound was changed was implied in the last operation

◆ cprop_inf_msg()

const char* cprop_inf_msg ( const CProp * cprop )

message explaining how infeasibility was detected

Parameters

cprop constraint propagation object

◆ cprop_n_cuts()

int cprop_n_cuts ( const CProp * cprop )

returns the number of cuts found processing the last infeasible solution

Parameters

cprop constraint propagation object

Returns: number of cuts found

◆ cprop_n_implications()

int cprop_n_implications ( const CProp * cprop )

returns how many implications the last change produced

returns how many implications the last action (add constraint or change bound) produced

Parameters

cprop constraint propagation object

◆ cprop_save_impl_graph()

void cprop_save_impl_graph	(	const CProp *	cprop,
		const char *	fName
	)

saves the implication graph in the DOT file format (graphviz)

Parameters

cprop	constraint propagation object
fName	file name (.dot extension recommended)

◆ cprop_set_verbose()

void cprop_set_verbose	(	CProp *	cprop,
		char	verbose
	)

activates detailed printing of implications as they are discovered

Activates detailed printing of implications and bound changes as they are discovered. Useful to debug.

Parameters

cprop	Constraint Propagation Object
verbose	if messages will be printed on the screen

◆ cprop_undo()

void cprop_undo ( CProp * cprop )

undo the last bound changed and all its implications

Undo the last bound changed and all its implications. Can be called multiple times (unlimited undo)

Parameters

cprop constraint propagation object

◆ cprop_update_bound()

int cprop_update_bound	(	CProp *	cprop,
		int	j,
		double	l,
		double	u
	)

updates the bounds of a variable

Updates the bounds of variable j to [l, u] and performs Constraint Propagation. returns -1 if the problem became unfeasible, 0 if no implications were found or >0 if constraint propagation changed additional bounds all the effects of this bound change can be undone calling cprop_undo.

Parameters

CProp	constraint propagation object
j	variable index
l	lower bound
u	upper bound

Typedefs

Enumerations

Functions

Detailed Description

Enumeration Type Documentation

◆ IGNType

Function Documentation

◆ cprop_add_constraint()

◆ cprop_create()

◆ cprop_cut_coef()

◆ cprop_cut_idx()

◆ cprop_cut_nz()

◆ cprop_cut_rhs()

◆ cprop_cut_sense()

◆ cprop_feasible()

◆ cprop_free()

◆ cprop_get_lb()

◆ cprop_get_ub()

◆ cprop_impl_graph_in_d()

◆ cprop_impl_graph_in_neigh()

◆ cprop_impl_graph_node_id()

◆ cprop_impl_graph_node_type()

◆ cprop_impl_graph_node_var()

◆ cprop_implied_var()

◆ cprop_inf_msg()

◆ cprop_n_cuts()

◆ cprop_n_implications()

◆ cprop_save_impl_graph()

◆ cprop_set_verbose()

◆ cprop_undo()

◆ cprop_update_bound()