constraint handler for acyclicity constraints More...

#include "cons_dagcluster.h"
#include <string.h>
#include <ctype.h>
#include <assert.h>
#include "scip/scipdefplugins.h"
#include "parent_set_data.h"
#include "solution_info.h"
#include "circuit_cuts.h"
#include "fractional_circuit_cuts.h"
#include "convex4_cuts.h"
#include "set_packing_cuts.h"
#include "subip_cuts.h"
#include "matroid_cuts.h"
#include "utils.h"

Include dependency graph for cons_dagcluster.c:

Macros
#define	CHECK_WITH_ARROWS TRUE

#define	consActiveDagcluster NULL
	constraint activation notification method of constraint handler

#define	consCopyDagcluster NULL
	constraint copying method of constraint handler

#define	consDeactiveDagcluster NULL
	constraint deactivation notification method of constraint handler

#define	consDelvarsDagcluster NULL
	variable deletion of constraint handler

#define	consDisableDagcluster NULL
	constraint disabling notification method of constraint handler

#define	consEnableDagcluster NULL
	constraint enabling notification method of constraint handler

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

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

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

#define	consGetNVarsDagcluster NULL

#define	consGetVarsDagcluster NULL

#define	CONSHDLR_CHECKPRIORITY -900000
	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 FALSE
	should separation method be delayed, if other separators found cuts?,

#define	CONSHDLR_DESC "DAG cluster-based acyclicity constraint handler"
	Description of the constraint handler. More...

#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 90
	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 "dagcluster"
	Name of the constraint handler. More...

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

#define	CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS

#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 10
	frequency for separating cuts; zero means to separate only in the root node

#define	CONSHDLR_SEPAPRIORITY 100000000
	priority of the constraint handler for separation

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

#define	consInitDagcluster NULL

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

#define	consPresolDagcluster NULL
	presolving method of constraint handler

#define	DEFAULT_CIRCUIT_SIZE_LIM 3

#define	DEFAULT_CLUSTERCUTS_ADDTOPOOL TRUE

#define	DEFAULT_CONSSEPALPSUBIPABSGAPLIMIT 0

#define	DEFAULT_CONSSEPALPSUBIPGAPLIMIT 0

#define	DEFAULT_CONSSEPALPSUBIPTIMELIMIT 10 /1e+20/

#define	DEFAULT_CONSSEPASOLSUBIPABSGAPLIMIT 0

#define	DEFAULT_CONSSEPASOLSUBIPGAPLIMIT 0

#define	DEFAULT_CONSSEPASOLSUBIPTIMELIMIT 10 /1e+20/

#define	DEFAULT_EXTRAPROPS FALSE

#define	DEFAULT_FORCECUTS TRUE

#define	DEFAULT_FRACTIONALALWAYS FALSE

#define	DEFAULT_FRACTIONALEVER FALSE

#define	DEFAULT_GROUND_SET_SIZE_LIM 8

#define	DEFAULT_KMAX 1

#define	DEFAULT_KMAX_ROOT 1

#define	DEFAULT_MATROIDCUTS FALSE

#define	DEFAULT_MATROIDPAIRCUTS FALSE

#define	DEFAULT_MATROIDPAIRCUTSLIMIT 6

#define	DEFAULT_MATROIDPAIRMAXCUTS 20

#define	DEFAULT_PROPAGATESPC TRUE

#define	DEFAULT_ROOTGAPSEPALIMIT 0.001

#define	DEFAULT_SEPASOL_USECONVEX4 FALSE

#define	DEFAULT_SUBIPALWAYS TRUE

#define	DEFAULT_SUBIPDEPTHLIMIT -1

#define	DEFAULT_SUBIPEVER TRUE

#define	DEFAULT_USEINCUMBENTCONS FALSE

#define	EPSILON 0.0001

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

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

Functions
static SCIP_Bool	areFeasible (SCIP scip, SCIP_CONS conss, int nconss, SCIP_SOL sol)
	Checks whether a solution is feasible for a given set of constraints. More...

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

static SCIP_RETCODE	DagClusterSeparate (SCIP scip, SCIP_CONSDATA consdata, SCIP_SOL sol, int nGen, int k_lb, int k_ub, 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, SCIP_Bool incumbent_cons, SolutionInfo solinfo, SCIP_Bool cutoff)

SCIP_RETCODE	DC_createCons (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 dagcluster constraint More...

SCIP_RETCODE	DC_includeConshdlr (SCIP *scip)
	creates the handler for dagcluster constraints and includes it in SCIP

SCIP_RETCODE	DC_tryToSplit (SCIP *scip)
	Try to split each of the locally active constraints into multiple constraints locally by looking for strongly connected components in the data. More...

static SCIP_Bool	isFeasible_arrows (SCIP scip, SCIP_CONS cons, SCIP_SOL *sol)
	Checks whether a solution is feasible for a given constraint. More...

static SCIP_Bool	isFeasible_fvs (SCIP scip, SCIP_CONS cons, SCIP_SOL *sol)
	Checks whether a solution is feasible for a given constraint. More...

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

static	SCIP_DECL_CONSDELETE (consDeleteDagcluster)
	frees specific constraint data

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

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

static	SCIP_DECL_CONSFREE (consFreeDagcluster)
	Transformation initialisation method of constraint handler. More...

static	SCIP_DECL_CONSINITLP (consInitlpDagcluster)
	LP initialization method of constraint handler.

static	SCIP_DECL_CONSINITPRE (consInitpreDagcluster)
	presolving initialization method of constraint handler (called when presolving is about to begin)

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

static	SCIP_DECL_CONSPARSE (consParseDagcluster)
	constraint parsing method of constraint handler

static	SCIP_DECL_CONSPRINT (consPrintDagcluster)
	constraint display method of constraint handler

static	SCIP_DECL_CONSPROP (consPropDagcluster)
	domain propagation method of constraint handler

static	SCIP_DECL_CONSRESPROP (consRespropDagcluster)
	propagation conflict resolving method of constraint handler

static	SCIP_DECL_CONSSEPALP (consSepalpDagcluster)
	separation method of constraint handler for DAG solutions

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

static	SCIP_DECL_CONSTRANS (consTransDagcluster)
	Transformation method of constraint handler.

static SCIP_Bool	shouldTryFractionalCircuitCuts (SCIP_CONSHDLRDATA *conshdlrdata, int nGen)

static SCIP_Bool	shouldTryMatroidCuts (SCIP_CONSHDLRDATA *conshdlrdata)

static SCIP_Bool	shouldTrySubIPCuts (SCIP_CONSHDLRDATA *conshdlrdata, int nGen, int depth)

Detailed Description

constraint handler for acyclicity constraints

Author: James Cussens; Mark Bartlett

Implements a constraint for preventing cycles in the graph.

The constraint states that for any group of k nodes, at least one node must have no parents in that cluster. This generalises such that there must also be at least two nodes with at most one parent, at least three with at most two parents and so on.

As there are exponentially many of these constraints, it is implemented as a series of cutting planes.

In the price-and-cut loop, cluster cutting planes are sought first (due to high SEPAPRIORITY), then other separators e.g. Gomory may kick in. Once the price-and-cut loop is finished, cluster cutting planes are looked for again (due to high ENFOPRIORITY). This may succeed since eg Gomory cuts will have 'moved' the LP solution. If one is found then LP solving is re-invoked (p35 Achterberg) which may lead to yet more cluster cutting planes.

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.

Macro Definition Documentation

◆ CONSHDLR_DESC

#define CONSHDLR_DESC "DAG cluster-based acyclicity constraint handler"

Description of the constraint handler.

Referenced by DC_includeConshdlr().

◆ CONSHDLR_NAME

#define CONSHDLR_NAME "dagcluster"

Name of the constraint handler.

Referenced by DC_createCons(), DC_includeConshdlr(), DC_tryToSplit(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSINITLP(), SCIP_DECL_CONSINITPRE(), SCIP_DECL_CONSLOCK(), SCIP_DECL_CONSPROP(), SCIP_DECL_CONSRESPROP(), SCIP_DECL_CONSSEPALP(), SCIP_DECL_CONSSEPASOL(), and SCIP_DECL_CONSTRANS().

Function Documentation

◆ areFeasible()

static SCIP_Bool areFeasible	(	SCIP *	scip,
		SCIP_CONS **	conss,
		int	nconss,
		SCIP_SOL *	sol
	)

static

Checks whether a solution is feasible for a given set of constraints.

A solution is feasible for a constraint if

it has no more than 1 parent set for each node involved in the constraint, and
there are no cycles formed by the nodes involved in the constraint.

Parameters

scip	The SCIP instance conatining the constraints and solution.
conss	The acyclicity constraints to check.
nconss	The number of acyclicity constraints to check.
sol	The solution to check for feasibility. If NULL is given, then the current solution will be used.

Returns: TRUE if the solution is feasible for all the constraints, or FALSE otherwise.

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

◆ 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 CC_initialise(), and PS_copyParentSetData().

Referenced by DC_createCons(), and SCIP_DECL_CONSTRANS().

Here is the call graph for this function:

◆ DagClusterSeparate()

static SCIP_RETCODE DagClusterSeparate	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		SCIP_SOL *	sol,
		int *	nGen,
		int	k_lb,
		int	k_ub,
		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,
		SCIP_Bool	incumbent_cons,
		SolutionInfo *	solinfo,
		SCIP_Bool *	cutoff
	)

static

Parameters

scip	SCIP data structure
consdata	constraint data
sol	solution to be separated
nGen	*nGen is number of cutting planes added ( even non-efficacious ones are added )
k_lb	lowerbound on 'k' values for k-cluster searching, always positive
k_ub	upperbound on 'k' values for k-cluster searching
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
incumbent_cons	whether to consider only cutting planes on which the incumbent lies
cutoff	output: pointer to store whether we detected a cutoff

References CC_findCuts().

Referenced by SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

Here is the call graph for this function:

◆ DC_createCons()

SCIP_RETCODE DC_createCons	(	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 dagcluster constraint

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 seperated 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, and createConsData().

Referenced by addAcyclicityConstraints(), DC_tryToSplit(), and SCIP_DECL_CONSPARSE().

Here is the call graph for this function:

◆ DC_tryToSplit()

SCIP_RETCODE DC_tryToSplit ( SCIP * scip )

Try to split each of the locally active constraints into multiple constraints locally by looking for strongly connected components in the data.

Parameters

scip	The SCIP instance that the constraints belong to.

Returns: SCIP_OKAY if the operation succeeded or an appropriate error otherwise.

References CONSHDLR_NAME, DC_createCons(), PS_deallocateParentSetData(), and PS_splitToComponents().

Referenced by SCIP_DECL_EVENTEXEC().

Here is the call graph for this function:

◆ isFeasible_arrows()

static SCIP_Bool isFeasible_arrows	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol
	)

static

Checks whether a solution is feasible for a given constraint.

Uses arrow variables only to check for acyclicity Solution is infeasible only if there is a cycle involving arrows with positive values in the solution

Parameters

scip	The SCIP instance conatining the constraint and solution.
cons	The acyclicity constraint to check.
The	solution to check for feasibility. If NULL is given, then the current solution will be used.

Returns: TRUE if the solution is feasible for this constraint, or FALSE otherwise.

References get_arrow().

Here is the call graph for this function:

◆ isFeasible_fvs()

static SCIP_Bool isFeasible_fvs	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol
	)

static

Checks whether a solution is feasible for a given constraint.

Uses family variables only to check for acyclicity The graph to check is is constructed by finding, for each vertex, the first parent set with positive value in the solution. This function gives the same answer as isFeasible_arrows if there is no more than one positive parent set for each vertex

Parameters

scip	The SCIP instance conatining the constraint and solution.
cons	The acyclicity constraint to check.
The	solution to check for feasibility. If NULL is given, then the current solution will be used.

Returns: TRUE if the solution is feasible for this constraint, or FALSE otherwise.

References ParentSetData::nParents, ParentSetData::nParentSets, ParentSetData::ParentSets, and ParentSetData::PaVars.

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeDagcluster )

static

Transformation initialisation method of constraint handler.

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

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ CONSHDLR_DESC

◆ CONSHDLR_NAME

Function Documentation

◆ areFeasible()

◆ createConsData()

◆ DagClusterSeparate()

◆ DC_createCons()

◆ DC_tryToSplit()

◆ isFeasible_arrows()

◆ isFeasible_fvs()

◆ SCIP_DECL_CONSFREE()