Functions for finding matroid cuts. More...

#include "matroid_cuts.h"
#include "scip/scipdefplugins.h"
#include <string.h>

Include dependency graph for matroid_cuts.c:

Data Structures
struct	MATROID_AUXIPDATA
	Data for subIP for searching for matroid cuts. More...

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

Functions
static SCIP_RETCODE	AuxIPDataFree (SCIP scip, MATROID_AUXIPDATA auxipdata, int n, int circuit_size_lim)
	Frees sub-IP data. More...

static int	choose (int n, int k)
	Computes n-choose-k. More...

static SCIP_Bool	element_of (int n_a, int *a, int elt)
	is 'elt' a member of set 'a'? More...

SCIP_RETCODE	Matroid_findCuts (SCIP scip, ParentSetData psd, SolutionInfo solinfo, SCIP_SOL sol, int nGen, SCIP_CONSHDLR conshdlr, SCIP_Bool addtopool, SCIP_Bool forcecuts, SCIP_Bool found_efficacious_ptr, SCIP_Real limits_time, SCIP_Real limits_gap, SCIP_Real limits_absgap, int circuit_size_lim, int ground_set_size_lim, int must_be_included, int n_must_be_included, int must_be_excluded, int n_must_be_excluded, SCIP_Bool cutoff)
	Main function for finding matroid cuts. More...

static int	mypow2 (int i)
	computes 2^i More...

static int	myunioni (int i, int n_a, int a, int n_b, int b, int *both)
	both = $a \cup b \setminus \{i\}$ . More...

static SCIP_Bool	subset_of (int n_a, int a, int n_b, int b)
	is 'a' a subset_of of 'b' ? More...

static SCIP_Bool	subseti (int i, int n_a, int a, int n_b, int b)
	is a subset of $b \cup \{i\}$ ? More...

Detailed Description

Functions for finding matroid cuts.

Function Documentation

◆ AuxIPDataFree()

static SCIP_RETCODE AuxIPDataFree	(	SCIP *	scip,
		MATROID_AUXIPDATA *	auxipdata,
		int	n,
		int	circuit_size_lim
	)

static

Frees sub-IP data.

Parameters

scip	(Main) SCIP instance
auxipdata	Data for the sub-IP (to be freed)
n	Number of BN variables in the acyclicity (dagcluster) constraint
circuit_size_lim	The limit on the size of circuits

References MATROID_AUXIPDATA::circuit_vars, MATROID_AUXIPDATA::circuits_i, MATROID_AUXIPDATA::full_graph, MATROID_AUXIPDATA::in_ground_set, MATROID_AUXIPDATA::n_circuits_i, and MATROID_AUXIPDATA::subscip.

◆ choose()

static int choose	(	int	n,
		int	k
	)

static

Computes n-choose-k.

Parameters

n	number of elements to choose from
k	size of chosen sets

Referenced by Matroid_findCuts().

◆ element_of()

static SCIP_Bool element_of	(	int	n_a,
		int *	a,
		int	elt
	)

static

is 'elt' a member of set 'a'?

Parameters

n_a	size of set a
a	set a
elt	an element

Referenced by Matroid_findCuts().

◆ Matroid_findCuts()

SCIP_RETCODE Matroid_findCuts	(	SCIP *	scip,
		ParentSetData *	psd,
		SolutionInfo *	solinfo,
		SCIP_SOL *	sol,
		int *	nGen,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_Bool	addtopool,
		SCIP_Bool	forcecuts,
		SCIP_Bool *	found_efficacious_ptr,
		SCIP_Real	limits_time,
		SCIP_Real	limits_gap,
		SCIP_Real	limits_absgap,
		int	circuit_size_lim,
		int	ground_set_size_lim,
		int *	must_be_included,
		int	n_must_be_included,
		int *	must_be_excluded,
		int	n_must_be_excluded,
		SCIP_Bool *	cutoff
	)

Main function for finding matroid cuts.

Parameters

scip	SCIP data structure
psd	family variable information
solinfo	information about the solution to be separated
sol	solution to be separated
nGen	*nGen is number of cutting planes added ( even non-efficacious ones are added )
conshdlr	constraint handler
addtopool	whether to add any found cut to the global cut pool
forcecuts	whether to force cuts to be added
found_efficacious_ptr	to return whether an efficacious cutting plane was found
limits_time	limit on how long to spend sub-IP solving
limits_gap	limit on size of gap in sub-IP
limits_absgap	limit on size of the absolute gap in sub-IP
circuit_size_lim	upper bound on size of circuits
ground_set_size_lim	upper bound on size of ground set
must_be_included	set of nodes which must be included in any found matroid
n_must_be_included	size of the set of nodes which must be included in any matroid
must_be_excluded	set of nodes which must be excluded from any matroid
n_must_be_excluded	size of the set of nodes which must be excluded from any found matroid
cutoff	cutoff = TRUE if a cut is added which leads to a cutoff ( set by SCIPaddRow )

References choose(), MATROID_AUXIPDATA::circuit_vars, MATROID_AUXIPDATA::circuits_i, element_of(), MATROID_AUXIPDATA::full_graph, MATROID_AUXIPDATA::in_ground_set, mypow2(), myunioni(), ParentSetData::n, MATROID_AUXIPDATA::n_circuits_i, ParentSetData::nodeNames, MATROID_AUXIPDATA::subscip, and subset_of().

Here is the call graph for this function:

◆ mypow2()

static int mypow2 ( int i )

static

computes 2^i

Parameters

i	Function returns 2^i

Referenced by Matroid_findCuts().

◆ myunioni()

static int myunioni	(	int	i,
		int	n_a,
		int *	a,
		int	n_b,
		int *	b,
		int *	both
	)

static

both = $a \cup b \setminus \{i\}$ .

Both a and b are assumed to contain i. Sufficient space must have already been allocated for 'both' before calling this function

Parameters

n_a	an element (of both a and b)
a	size of set a
n_b	set a
b	size of set b
both	set b set both (output)

Referenced by Matroid_findCuts().

◆ subset_of()

static SCIP_Bool subset_of	(	int	n_a,
		int *	a,
		int	n_b,
		int *	b
	)

static

is 'a' a subset_of of 'b' ?

Parameters

n_a	size of set a
a	set a
n_b	size of set b
b	set b

Referenced by Matroid_findCuts().

◆ subseti()

static SCIP_Bool subseti	(	int	i,
		int	n_a,
		int *	a,
		int	n_b,
		int *	b
	)

static

is $a$ a subset of $b \cup \{i\}$ ?

Parameters

i	an element
n_a	size of set a
a	set a
n_b	size of set b
b	set b

Data Structures

Macros

Functions

Detailed Description

Function Documentation

◆ AuxIPDataFree()

◆ choose()

◆ element_of()

◆ Matroid_findCuts()

◆ mypow2()

◆ myunioni()

◆ subset_of()

◆ subseti()