constraint handler for chordal graph constraints More...

#include <assert.h>
#include <string.h>
#include "cons_chordal.h"
#include "utils.h"
#include "scip/pub_misc.h"
#include "scip/scipdefplugins.h"

Include dependency graph for cons_chordal.c:

Data Structures
struct	tree
	tree of integers used for mapping sequences of integers (ie sets) to integers More...

Macros
#define	consActiveChordal NULL
	constraint activation notification method of constraint handler

#define	consCopyChordal NULL
	constraint copying method of constraint handler

#define	consDeactiveChordal NULL
	constraint deactivation notification method of constraint handler

#define	consDelvarsChordal NULL
	variable deletion of constraint handler

#define	consDisableChordal NULL
	constraint disabling notification method of constraint handler

#define	consEnableChordal NULL
	constraint enabling notification method of constraint handler

#define	consExitChordal NULL
	deinitialization method of constraint handler (called before transformed problem is freed)

#define	consExitpreChordal NULL
	presolving deinitialization method of constraint handler (called after presolving has been finished)

#define	consExitsolChordal NULL
	solving process deinitialization method of constraint handler (called before branch and bound process data is freed)

#define	consGetDiveBdChgsChordal NULL
	constraint handler method to suggest dive bound changes during the generic diving algorithm

#define	consGetNVarsChordal NULL
	constraint method of constraint handler which returns the number of variables (if possible)

#define	consGetVarsChordal NULL
	constraint method of constraint handler which returns the variables (if possible)

#define	CONSHDLR_CHECKPRIORITY -10
	priority of the constraint handler for checking feasibility

#define	CONSHDLR_DELAYPROP FALSE
	should propagation method be delayed, if other propagators found reductions?

#define	CONSHDLR_DELAYSEPA TRUE
	should separation method be delayed, if other separators found cuts?

#define	CONSHDLR_DESC "constraint handler for chordal graph constraints"
	constraint handler description

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

#define	CONSHDLR_ENFOPRIORITY -10
	priority of the constraint handler for constraint enforcing

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

#define	CONSHDLR_NAME "chordal"
	constraint handler name

#define	CONSHDLR_NEEDSCONS TRUE
	should the constraint handler be skipped, if no constraints are available?

#define	CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM
	presolving timing of the constraint handler (fast, medium, or exhaustive)

#define	CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
	propagation timing mask of the constraint handler

#define	CONSHDLR_PROPFREQ 1
	frequency for propagating domains; zero means only preprocessing propagation

#define	CONSHDLR_SEPAFREQ 1
	frequency for separating cuts; zero means to separate only in the root node

#define	CONSHDLR_SEPAPRIORITY 0
	priority of the constraint handler for separation

#define	conshdlrCopyChordal NULL
	copy method for constraint handler plugins (called when SCIP copies plugins)

#define	consInitChordal NULL
	initialization method of constraint handler (called after problem was transformed)

#define	consInitpreChordal NULL
	presolving initialization method of constraint handler (called when presolving is about to begin)

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

#define	consParseChordal NULL
	constraint parsing method of constraint handler

#define	consPrintChordal NULL
	constraint display method of constraint handler

#define	consRespropChordal NULL
	propagation conflict resolving method of constraint handler

#define	consTransChordal NULL
	transforms constraint data into data belonging to the transformed problem

#define	DEFAULT_MAXCLUTTERSIZE 4
	default value for maximal size of clutter for a cut

#define	DEFAULT_MAXCUTSROUND 500
	default value for maximum number of cuts generated in a separation round (-1 is no limit)

#define	DEFAULT_MAXCUTSROUNDSINGLETON 200
	default value for maximum number of cuts generated in a separation round for any singleton (-1 is no limit)

#define	DEFAULT_MAXSIZEINCLUTTER -1
	default value for maximal size of a subset in a clutter for a cut (-1 is no limit)

#define	DEFAULT_MINCLUTTERSIZE 3
	default value for minimal size of clutter for a cut

#define	DEFAULT_MONOLIM 3
	default value for limit on size of subset corresponding to the lower bound in a simple monotonicity constraint

#define	DEFAULT_ONESINGLETON TRUE
	default value for whether clutters for cuts should contain only one singleton

#define	DEFAULT_VANILLA FALSE
	default value for whether all chordal constraints are for 'vanilla' learning

#define	max(A, B) ((A) < (B) ? (B) : (A))

#define	min(A, B) ((A) > (B) ? (B) : (A))

Typedefs
typedef struct tree	TREE

Functions
static SCIP_RETCODE	ChordalSeparate (SCIP scip, SCIP_CONSHDLR conshdlr, SCIP_CONSDATA consdata, SCIP_SOL sol, int nGen, SCIP_Bool cutoff)
	brute force approach to separate a solution using clutter cuts More...

static SCIP_RETCODE	createConsData (SCIP scip, SCIP_CONSDATA consdata, ParentSetData psd)
	Creates the data for a constraint. More...

static void	free_children (TREE *tree)
	free memory taken up by children of a node More...

static int	get_idx (TREE tree, int size, int subset)
	return the integer ('index') associated with a set of integers More...

static void	get_union (int set1, int set2, int *uni)
	compute union of two sets a set is an ordered sequence of distinct integers space for the output set must already have been allocated! More...

static void	init_union (int size, int set, int uni)
	create a set of integers representation where the size is recorded in element 0 space for the output set must already have been allocated! More...

static SCIP_Bool	is_feasible (SCIP scip, ParentSetData psd, SCIP_SOL *sol)
	Checks whether an acyclic digraph has any immoralities. More...

static SCIP_RETCODE	makeimsetvars (SCIP scip, SCIP_CONSDATA *consdata)
	create imset variables from parent set ('family') variables More...

static int	put_index (TREE tree, int size, int subset, int idx)
	associate an integer ('index') with a set of integers More...

static	SCIP_DECL_CONSCHECK (consCheckChordal)
	feasibility check method of constraint handler for integral solutions

static	SCIP_DECL_CONSDELETE (consDeleteChordal)
	frees specific constraint data

static	SCIP_DECL_CONSENFOLP (consEnfolpChordal)
	constraint enforcing method of constraint handler for LP solutions

static	SCIP_DECL_CONSENFOPS (consEnfopsChordal)
	constraint enforcing method of constraint handler for pseudo solutions

static	SCIP_DECL_CONSFREE (consFreeChordal)
	destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

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

static	SCIP_DECL_CONSLOCK (consLockChordal)
	variable rounding lock method of constraint handler

static	SCIP_DECL_CONSPRESOL (consPresolChordal)
	presolving method of constraint handler

static	SCIP_DECL_CONSPROP (consPropChordal)
	domain propagation method of constraint handler

static	SCIP_DECL_CONSSEPALP (consSepalpChordal)
	separation method of constraint handler for LP solutions

static	SCIP_DECL_CONSSEPASOL (consSepasolChordal)
	separation method of constraint handler for arbitrary primal solutions

SCIP_RETCODE	SCIPcreateConsBasicChordal (SCIP scip, SCIP_CONS cons, const char name, ParentSetData *psd)
	creates and captures a chordal constraint with all its constraint flags set to their default values More...

SCIP_RETCODE	SCIPcreateConsChordal (SCIP scip, SCIP_CONS cons, const char name, ParentSetData *psd, 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 chordal constraint More...

SCIP_RETCODE	SCIPincludeConshdlrChordal (SCIP *scip)
	creates the handler for chordal constraints and includes it in SCIP More...

static SCIP_Real	update_cut (int size, int ci, SCIP_Real lpvals, SCIP_VAR imsetvars, SCIP_VAR cutvars, SCIP_Real cutvals, int n_cutvars_ptr, int cut_rhs, int val)
	add an imset variable to an existing clutter cut More...

Detailed Description

constraint handler for chordal graph constraints

Author: James Cussens

Implements a constraint that the graph has no immoralities (v-structures). This is equivalent to demanding that the acyclic digraph is equivalent to a chordal undirected graph (aka decomposable model)

Doxygen documentation for the locally defined structs SCIP_ConsData and SCIP_ConshdlrData is unfortunately not available since structs with the same name are defined in other constraint handlers and Doxygen cannot handle the name clash. You will have to consult the source code to view this documentation.

Function Documentation

◆ ChordalSeparate()

static SCIP_RETCODE ChordalSeparate	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_CONSDATA *	consdata,
		SCIP_SOL *	sol,
		int *	nGen,
		SCIP_Bool *	cutoff
	)

static

brute force approach to separate a solution using clutter cuts

Returns: SCIP_OKAY if successful, or an appropriate error otherwise.

Parameters

scip	SCIP pointer
conshdlr	constraint handler
consdata	constraint data
sol	solution to be separated
nGen	output: pointer to store number of added rows
cutoff	output: pointer to store whether we detected a cutoff

Referenced by get_union(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

◆ createConsData()

static SCIP_RETCODE createConsData	(	SCIP *	scip,
		SCIP_CONSDATA **	consdata,
		ParentSetData *	psd
	)

static

Creates the data for a constraint.

Parameters

scip	The SCIP instance to which the constraaint belongs.
consdata	The location to store the new constraint data.
psd	The parent set data on which the constraint is based.

Returns: SCIP_OKAY if successful, or an appropriate error otherwise.

References conshdlrCopyChordal, makeimsetvars(), SCIP_DECL_CONSHDLRCOPY(), and SCIPcreateConsChordal().

Referenced by makeimsetvars(), and SCIPcreateConsChordal().

Here is the call graph for this function:

◆ free_children()

static void free_children ( TREE * tree )

static

free memory taken up by children of a node

Parameters

tree	(pointer to) node whose children are to be deleted

References tree::children, get_idx(), and tree::nchildren.

Referenced by SCIP_DECL_CONSDELETE().

Here is the call graph for this function:

◆ get_idx()

static int get_idx	(	TREE *	tree,
		int	size,
		int *	subset
	)

static

return the integer ('index') associated with a set of integers

Returns: the index associated with the given set

Parameters

tree	tree containing mapping from sets to integers
size	size of the set
subset	set whose index is sought

References tree::children, tree::idx, tree::nchildren, and put_index().

Referenced by free_children(), and makeimsetvars().

Here is the call graph for this function:

◆ get_union()

static void get_union	(	int *	set1,
		int *	set2,
		int *	uni
	)

static

compute union of two sets a set is an ordered sequence of distinct integers space for the output set must already have been allocated!

Parameters

set1	first input set
set2	second input set
uni	union of `set1` and `set2`

References ChordalSeparate().

Referenced by init_union().

Here is the call graph for this function:

◆ init_union()

static void init_union	(	int	size,
		int *	set,
		int *	uni
	)

static

create a set of integers representation where the size is recorded in element 0 space for the output set must already have been allocated!

Parameters

size	size of input set
set	input set
uni	output set where `size` is recorded at `uni`[0]

References get_union().

Referenced by update_cut().

Here is the call graph for this function:

◆ is_feasible()

static SCIP_Bool is_feasible	(	SCIP *	scip,
		ParentSetData *	psd,
		SCIP_SOL *	sol
	)

static

Checks whether an acyclic digraph has any immoralities.

Parameters

scip	The SCIP instance to which the constraint belongs.
psd	The parent set data on which the constraint is based.
sol	The acyclic digraph to check

Returns: TRUE if digraph has no immoralities else FALSE

References get_edge(), makeimsetvars(), ParentSetData::n, ParentSetData::nParents, ParentSetData::nParentSets, ParentSetData::ParentSets, and ParentSetData::PaVars.

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

Here is the call graph for this function:

◆ makeimsetvars()

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

static

create imset variables from parent set ('family') variables

Returns: SCIP_OKAY if successful, or an appropriate error otherwise.

Parameters

scip	The SCIP instance to which the constraint belongs
consdata	Constraint data to be updated with imset variables

References allsubsets(), tree::children, createConsData(), free_allsubsets(), get_edge(), get_idx(), tree::idx, ParentSetData::n, tree::nchildren, ParentSetData::nodeNames, ParentSetData::nParents, ParentSetData::nParentSets, ParentSetData::ParentSets, ParentSetData::PaVars, and put_index().

Referenced by createConsData(), and is_feasible().

Here is the call graph for this function:

◆ put_index()

static int put_index	(	TREE *	tree,
		int	size,
		int *	subset,
		int	idx
	)

static

associate an integer ('index') with a set of integers

Parameters

tree	tree containing mapping from sets to integers
size	size of the set
subset	set whose index is sought
idx	index to associate with the set

References tree::children, tree::idx, tree::nchildren, and update_cut().

Referenced by get_idx(), and makeimsetvars().

Here is the call graph for this function:

◆ SCIPcreateConsBasicChordal()

SCIP_RETCODE SCIPcreateConsBasicChordal	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		ParentSetData *	psd
	)

creates and captures a chordal constraint with all its constraint flags set to their default values

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

References SCIPcreateConsChordal().

Referenced by addAdditionalConstraints(), and SCIPcreateConsChordal().

Here is the call graph for this function:

◆ SCIPcreateConsChordal()

SCIP_RETCODE SCIPcreateConsChordal	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		ParentSetData *	psd,
		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 chordal 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
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.

References CONSHDLR_NAME, createConsData(), and SCIPcreateConsBasicChordal().

Referenced by createConsData(), SCIPcreateConsBasicChordal(), and SCIPincludeConshdlrChordal().

Here is the call graph for this function:

◆ SCIPincludeConshdlrChordal()

SCIP_RETCODE SCIPincludeConshdlrChordal ( SCIP * scip )

creates the handler for chordal constraints and includes it in SCIP

Parameters

scip	SCIP data structure

References CONSHDLR_CHECKPRIORITY, CONSHDLR_DELAYPROP, CONSHDLR_DELAYSEPA, CONSHDLR_DESC, CONSHDLR_EAGERFREQ, CONSHDLR_ENFOPRIORITY, CONSHDLR_MAXPREROUNDS, CONSHDLR_NAME, CONSHDLR_NEEDSCONS, CONSHDLR_PRESOLTIMING, CONSHDLR_PROP_TIMING, CONSHDLR_PROPFREQ, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, DEFAULT_MAXCLUTTERSIZE, DEFAULT_MAXCUTSROUND, DEFAULT_MAXCUTSROUNDSINGLETON, DEFAULT_MAXSIZEINCLUTTER, DEFAULT_MINCLUTTERSIZE, DEFAULT_MONOLIM, DEFAULT_ONESINGLETON, DEFAULT_VANILLA, and SCIPcreateConsChordal().

Referenced by BN_includePlugins().

Here is the call graph for this function:

◆ update_cut()

static SCIP_Real update_cut	(	int	size,
		int	ci,
		SCIP_Real **	lpvals,
		SCIP_VAR ***	imsetvars,
		SCIP_VAR **	cutvars,
		SCIP_Real *	cutvals,
		int *	n_cutvars_ptr,
		int *	cut_rhs,
		int	val
	)

static

add an imset variable to an existing clutter cut

Returns: value (ie LHS) of cut for solution being separated (has to exceed RHS for cut to be useful)

Parameters

size	`size` where `imsetvars`[size][ci] is the variable to add to the cut
ci	`ci` where `imsetvars`[size][ci] is the variable to add to the cut
lpvals	values of the `imsetvars`[size][ci] in solution to be separated
imsetvars	`imsetvars`[size][ci] is the cith imsetvar of size `size`
cutvars	output: variables in the cut
cutvals	output: values for variables in the cut
n_cutvars_ptr	output: number of variables in the cut
cut_rhs	output: cut RHS (only changes if imset is of size 1)
val	coefficient for added imset variable in the cut

References init_union().

Referenced by put_index().

Here is the call graph for this function:

Data Structures

Macros

Typedefs

Functions

Detailed Description

Function Documentation

◆ ChordalSeparate()

◆ createConsData()

◆ free_children()

◆ get_idx()

◆ get_union()

◆ init_union()

◆ is_feasible()

◆ makeimsetvars()

◆ put_index()

◆ SCIPcreateConsBasicChordal()

◆ SCIPcreateConsChordal()

◆ SCIPincludeConshdlrChordal()

◆ update_cut()