Detailed Description

problem data for vertex coloring algorithm

Author: Gerald Gamrath

This file implements the problem data for the coloring algorithm.

The problem data contains the original graph, preprocessing information, the preprocessed graph, the array with the node-constraints, and an array with all stable sets and corresponding variables.

The preprocessing deletes nodes that have a lower degree than the size of a maximum clique. Additionally, it also deletes nodes that have a dominated neighborhood. For further information, look at the documentation for the method preprocessGraph().

The deleted nodes and the relation between the nodes of the original graph and the nodes of the preprocessed graph are stored in order to convert a solution of the preprocessed problem to a solution for the original graph and vice versa.

Each variable has a pointer of type SCIP_VARDATA* that is used in this case to store an integer representing the number of the stable set. With the aid of this, the corresponding stable set can be found in the array returned by COLORprobGetStableSets(). This array contains all stable sets and is also used to check whether a stable set found by the pricer is really new. This can be done by calling COLORprobStableSetIsNew(). All sets are sorted decreasingly with respect to the indices of the nodes. New candidates should also be sorted that way.

Definition in file probdata_coloring.c.

#include "probdata_coloring.h"

Go to the source code of this file.

Macros
#define	EVENTHDLR_NAME "probdatavardeleted"

#define	EVENTHDLR_DESC "event handler for variable deleted event"

Functions
static SCIP_RETCODE	preprocessGraph (SCIP *scip)

static	SCIP_DECL_PROBTRANS (probtransColoring)

static	SCIP_DECL_PROBDELTRANS (probdeltransColoring)

static	SCIP_DECL_PROBDELORIG (probdelorigColoring)

static	SCIP_DECL_EVENTEXEC (eventExecProbdatavardeleted)

SCIP_RETCODE	SCIPcreateProbColoring (SCIP scip, const char name, int nnodes, int nedges, int **edges)

int	COLORprobGetNStableSets (SCIP *scip)

void	COLORprobPrintStableSets (SCIP *scip)

void	COLORprobPrintStableSet (SCIP *scip, int setnumber)

SCIP_RETCODE	COLORprobAddVarForStableSet (SCIP scip, int setindex, SCIP_VAR var)

SCIP_VAR *	COLORprobGetVarForStableSet (SCIP *scip, int setindex)

SCIP_Bool	COLORprobIsNodeInStableSet (SCIP *scip, int setindex, int node)

SCIP_Bool	COLORprobStableSetsAreEqual (SCIP scip, int set1, int nset1nodes, int *set2, int nset2nodes)

SCIP_Bool	COLORprobStableSetIsNew (SCIP scip, int stablesetnodes, int nstablesetnodes)

SCIP_RETCODE	COLORprobAddNewStableSet (SCIP scip, int stablesetnodes, int nstablesetnodes, int *setindex)

void	COLORprobGetStableSet (SCIP scip, int setindex, int stableset, int nelements)

void	COLORprobGetStableSets (SCIP scip, int stablesets, int nelements, int *nstablesets)

int	COLORprobGetNNodes (SCIP *scip)

int	COLORprobGetOriginalNNodes (SCIP *scip)

TCLIQUE_GRAPH *	COLORprobGetGraph (SCIP *scip)

TCLIQUE_GRAPH *	COLORprobGetOriginalGraph (SCIP *scip)

int *	COLORprobGetDeletedNodes (SCIP *scip)

int *	COLORprobGetOriginalNodesForNewNodes (SCIP *scip)

int	COLORprobGetNewNodeForOriginalNode (SCIP *scip, int node)

SCIP_CONS **	COLORprobGetConstraints (SCIP *scip)

SCIP_CONS *	COLORprobGetConstraint (SCIP *scip, int node)

SCIP_RETCODE	COLORprobGetComplementaryGraph (SCIP scip, TCLIQUE_GRAPH graph, TCLIQUE_GRAPH *cgraph)

SCIP_RETCODE	COLORprobSetUpArrayOfCons (SCIP *scip)

SCIP_Bool	COLORprobIsNodeInArray (int node, int *arraynodes, int narraynodes)

SCIP_Bool	COLORprobEqualSortedArrays (int array1nodes, int narray1nodes, int array2nodes, int narray2nodes)

Macro Definition Documentation

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME "probdatavardeleted"

Definition at line 45 of file probdata_coloring.c.

Referenced by COLORprobAddVarForStableSet(), and SCIPcreateProbColoring().

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC "event handler for variable deleted event"

Definition at line 46 of file probdata_coloring.c.

Referenced by SCIPcreateProbColoring().

Function Documentation

◆ preprocessGraph()

static SCIP_RETCODE preprocessGraph ( SCIP * scip )

static

Preprocessing of the graph, using 2 methods in order to find redundant nodes that can be deleted and easily colored later.

Foundation of these methods is the computation of a maximum clique C with M nodes. After this computation, the following two steps are repeated until no node was deleted in the last iteration:

1: Low-Degree: Iterativly delete all nodes v in the graph G with degree d(v) < M ( don't delete nodes of C )

2: Dominated Neighbourhood: If the neighbourhood of one node v is part of the neighbourhood of another node w, v can be deleted, since it can later get the same color as w.

Parameters

scip	SCIP data structure

Definition at line 88 of file probdata_coloring.c.

References COLORprobGetOriginalNNodes(), COLORprobIsNodeInArray(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetProbData(), TCLIQUE_OPTIMAL, tcliqueAddEdge(), tcliqueAddNode(), tcliqueChangeWeight(), tcliqueCreate(), tcliqueFlush(), tcliqueFree(), tcliqueGetDegrees(), tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), tcliqueMaxClique(), and TRUE.

Referenced by SCIPcreateProbColoring().

◆ SCIP_DECL_PROBTRANS()

static SCIP_DECL_PROBTRANS ( probtransColoring )

static

transforms the problem

Definition at line 456 of file probdata_coloring.c.

References NULL, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPerrorMessage, SCIPtransformConss(), SCIPtransformVar(), tcliqueAddEdge(), tcliqueAddNode(), tcliqueCreate(), tcliqueFlush(), tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().

◆ SCIP_DECL_PROBDELTRANS()

static SCIP_DECL_PROBDELTRANS ( probdeltransColoring )

static

deletes the transformed problem

Definition at line 550 of file probdata_coloring.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPreleaseCons(), SCIPreleaseVar(), and tcliqueFree().

◆ SCIP_DECL_PROBDELORIG()

static SCIP_DECL_PROBDELORIG ( probdelorigColoring )

static

Definition at line 583 of file probdata_coloring.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPreleaseCons(), SCIPreleaseVar(), and tcliqueFree().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecProbdatavardeleted )

static

execution method of event handler

Definition at line 626 of file probdata_coloring.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_VARDELETED, SCIP_OKAY, SCIPdebugMessage, SCIPeventGetType(), SCIPeventGetVar(), SCIPfreeBlockMemoryArray, SCIPreleaseVar(), SCIPvarGetData(), SCIPvarGetName(), and SCIPvarSetData().

◆ SCIPcreateProbColoring()

SCIP_RETCODE SCIPcreateProbColoring	(	SCIP *	scip,
		const char *	name,
		int	nnodes,
		int	nedges,
		int **	edges
	)

sets up the problem data

Parameters

scip	SCIP data structure
name	problem name
nnodes	number of nodes
nedges	number of edges
edges	array with start- and endpoints of the edges

Definition at line 671 of file probdata_coloring.c.

References EVENTHDLR_DESC, EVENTHDLR_NAME, nnodes, NULL, preprocessGraph(), SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcreateProb(), SCIPerrorMessage, SCIPincludeEventhdlrBasic(), tcliqueAddEdge(), tcliqueAddNode(), tcliqueCreate(), and tcliqueFlush().

Referenced by readCol().

◆ COLORprobGetNStableSets()

int COLORprobGetNStableSets ( SCIP * scip )

returns the number of stable sets / variables

Parameters

scip	SCIP data structure

Definition at line 753 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by COLORprobStableSetIsNew(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERINITSOL(), and SCIP_DECL_PRICERREDCOST().

◆ COLORprobPrintStableSets()

void COLORprobPrintStableSets ( SCIP * scip )

prints all stable sets to standard output

Parameters

scip	SCIP data structure

Definition at line 768 of file probdata_coloring.c.

References NULL, SCIPgetProbData(), SCIPvarGetUbLocal(), and SCIPvarIsInLP().

◆ COLORprobPrintStableSet()

void COLORprobPrintStableSet	(	SCIP *	scip,
		int	setnumber
	)

prints the requested stable set to standard output

Parameters

scip	SCIP data structure
setnumber	the number of the requested set

Definition at line 795 of file probdata_coloring.c.

References NULL, SCIPgetProbData(), and SCIPvarGetUbLocal().

◆ COLORprobAddVarForStableSet()

SCIP_RETCODE COLORprobAddVarForStableSet	(	SCIP *	scip,
		int	setindex,
		SCIP_VAR *	var
	)

adds a variable that belongs to a given stable set

Parameters

scip	SCIP data structure
setindex	index of the stable set
var	pointer to the variable

Definition at line 823 of file probdata_coloring.c.

References EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_VARDELETED, SCIP_OKAY, SCIPcatchVarEvent(), SCIPfindEventhdlr(), and SCIPgetProbData().

Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERFARKAS(), SCIP_DECL_PRICERREDCOST(), and SCIP_DECL_READERREAD().

◆ COLORprobGetVarForStableSet()

SCIP_VAR* COLORprobGetVarForStableSet	(	SCIP *	scip,
		int	setindex
	)

gets the variable belonging to a given stable set

Parameters

scip	SCIP data structure
setindex	index of the stable set

Definition at line 847 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_CONSPROP(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERFARKAS(), and SCIP_DECL_READERWRITE().

◆ COLORprobIsNodeInStableSet()

SCIP_Bool COLORprobIsNodeInStableSet	(	SCIP *	scip,
		int	setindex,
		int	node
	)

checks whether a node is in a given stable set, returns true iff it is

Parameters

scip	SCIP data structure
setindex	index of the stable set
node	number of the node

Definition at line 864 of file probdata_coloring.c.

References FALSE, NULL, SCIPgetProbData(), and TRUE.

Referenced by computeBranchingPriorities(), and SCIP_DECL_CONSPROP().

◆ COLORprobStableSetsAreEqual()

SCIP_Bool COLORprobStableSetsAreEqual	(	SCIP *	scip,
		int *	set1,
		int	nset1nodes,
		int *	set2,
		int	nset2nodes
	)

checks whether the first set is equal to the second set, both sets have to be sorted in a decreasing way

Parameters

scip	SCIP data structure
set1	array of nodes in the first set
nset1nodes	number of nodes in the first set
set2	array of nodes in the second set
nset2nodes	number of nodes in the second set

Definition at line 902 of file probdata_coloring.c.

References FALSE, NULL, and TRUE.

Referenced by COLORprobStableSetIsNew().

◆ COLORprobStableSetIsNew()

SCIP_Bool COLORprobStableSetIsNew	(	SCIP *	scip,
		int *	stablesetnodes,
		int	nstablesetnodes
	)

checks whether the given stable set is new returns TRUE if the stable is new, FALSE if it is equal to an already existing stable set

Parameters

scip	SCIP data structure
stablesetnodes	array of nodes in the stable set
nstablesetnodes	number of nodes in the stable set

Definition at line 936 of file probdata_coloring.c.

References COLORprobGetNStableSets(), COLORprobStableSetsAreEqual(), FALSE, NULL, SCIPgetProbData(), SCIPsortDownInt(), and TRUE.

Referenced by SCIP_DECL_PRICERREDCOST(), and TCLIQUE_NEWSOL().

◆ COLORprobAddNewStableSet()

SCIP_RETCODE COLORprobAddNewStableSet	(	SCIP *	scip,
		int *	stablesetnodes,
		int	nstablesetnodes,
		int *	setindex
	)

adds a new stable set, the set must be sorted in descending order;

Note: you need to check whether it is new before adding it

Parameters

scip	SCIP data structure
stablesetnodes	array of nodes in the stable set
nstablesetnodes	number of nodes in the stable set
setindex	return value: index of the stable set

Definition at line 969 of file probdata_coloring.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPdebugMessage, SCIPgetProbData(), and SCIPreallocBlockMemoryArray.

Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERFARKAS(), SCIP_DECL_PRICERREDCOST(), and SCIP_DECL_READERREAD().

◆ COLORprobGetStableSet()

void COLORprobGetStableSet	(	SCIP *	scip,
		int	setindex,
		int **	stableset,
		int *	nelements
	)

returns the stable set with the given index

Parameters

scip	SCIP data structure
setindex	index of the stable set
stableset	return value: pointer to the stable set
nelements	return value: number of elements in the stable set

Definition at line 1023 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by computeBranchingPriorities(), and SCIP_DECL_BRANCHEXECLP().

◆ COLORprobGetStableSets()

void COLORprobGetStableSets	(	SCIP *	scip,
		int ***	stablesets,
		int **	nelements,
		int *	nstablesets
	)

returns all stable sets

Parameters

scip	SCIP data structure
stablesets	return value: pointer to the stable sets
nelements	return value: number of elements in the stable sets
nstablesets	return value: number of sets

Definition at line 1042 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_CONSPROP(), SCIP_DECL_PRICERFARKAS(), and SCIP_DECL_READERWRITE().

◆ COLORprobGetNNodes()

int COLORprobGetNNodes ( SCIP * scip )

returns the number of nodes in the (preprocessed) graph

Parameters

scip	SCIP data structure

Definition at line 1062 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by COLORprobGetComplementaryGraph(), COLORprobSetUpArrayOfCons(), computeBranchingPriorities(), greedyInitialColoring(), index2nodes(), nodes2index(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECPS(), SCIP_DECL_BRANCHINIT(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PARAMCHGD(), SCIP_DECL_PRICEREXITSOL(), SCIP_DECL_PRICERFARKAS(), SCIP_DECL_PRICERINITSOL(), and SCIP_DECL_READERREAD().

◆ COLORprobGetOriginalNNodes()

int COLORprobGetOriginalNNodes ( SCIP * scip )

returns the number of nodes in the original graph

Parameters

scip	SCIP data structure

Definition at line 1077 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by COLORprobGetNewNodeForOriginalNode(), preprocessGraph(), SCIP_DECL_READERREAD(), and SCIP_DECL_READERWRITE().

◆ COLORprobGetGraph()

TCLIQUE_GRAPH* COLORprobGetGraph ( SCIP * scip )

returns the (preprocessed) graph

Parameters

scip	SCIP data structure

Definition at line 1092 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_CONSINITSOL(), SCIP_DECL_HEUREXEC(), and SCIP_DECL_READERREAD().

◆ COLORprobGetOriginalGraph()

TCLIQUE_GRAPH* COLORprobGetOriginalGraph ( SCIP * scip )

returns the original graph

Parameters

scip	SCIP data structure

Definition at line 1108 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_READERWRITE().

◆ COLORprobGetDeletedNodes()

int* COLORprobGetDeletedNodes ( SCIP * scip )

returns the array of nodes deleted during preprocessing, length = COLORprobGetOriginalNNodes(), filled with -1 at the end

Parameters

scip	SCIP data structure

Definition at line 1123 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_READERWRITE().

◆ COLORprobGetOriginalNodesForNewNodes()

int* COLORprobGetOriginalNodesForNewNodes ( SCIP * scip )

returns the array in which for every node in the preprocessed graph, the related node in the original graph is saved

Parameters

scip	SCIP data structure

Definition at line 1138 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_READERWRITE().

◆ COLORprobGetNewNodeForOriginalNode()

int COLORprobGetNewNodeForOriginalNode	(	SCIP *	scip,
		int	node
	)

returns the node in the preprocessed graph, that belongs to the given node, returns -1 if node was deleted

Parameters

scip	SCIP data structure
node	a node in the original graph

Definition at line 1154 of file probdata_coloring.c.

References COLORprobGetOriginalNNodes(), NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_READERREAD().

◆ COLORprobGetConstraints()

SCIP_CONS** COLORprobGetConstraints ( SCIP * scip )

returns all node-constraints

Parameters

scip	SCIP data structure

Definition at line 1181 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by COLORprobSetUpArrayOfCons(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PRICERFARKAS(), SCIP_DECL_PRICERREDCOST(), and SCIP_DECL_READERREAD().

◆ COLORprobGetConstraint()

SCIP_CONS* COLORprobGetConstraint	(	SCIP *	scip,
		int	node
	)

returns the node-constraint belonging to a given node

Parameters

scip	SCIP data structure
node	number of the node, for which this constraint assures coloring

Definition at line 1196 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ COLORprobGetComplementaryGraph()

SCIP_RETCODE COLORprobGetComplementaryGraph	(	SCIP *	scip,
		TCLIQUE_GRAPH *	graph,
		TCLIQUE_GRAPH *	cgraph
	)

computes the complementary graph for a given graph and stores it in the given pointer

Parameters

scip	SCIP data structure
graph	the given graph
cgraph	the complementary graph is saved in here

Definition at line 1213 of file probdata_coloring.c.

References COLORprobGetNNodes(), nnodes, NULL, SCIP_ERROR, SCIP_OKAY, SCIPerrorMessage, tcliqueAddEdge(), tcliqueAddNode(), tcliqueFlush(), tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().

Referenced by createConsStoreGraphAtRoot(), and SCIP_DECL_CONSACTIVE().

◆ COLORprobSetUpArrayOfCons()

SCIP_RETCODE COLORprobSetUpArrayOfCons ( SCIP * scip )

creates all node-constraints and saves them in an array

Parameters

scip	SCIP data structure

Definition at line 1296 of file probdata_coloring.c.

References COLORprobGetConstraints(), COLORprobGetNNodes(), FALSE, nnodes, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsSetcover(), and TRUE.

Referenced by readCol().

◆ COLORprobIsNodeInArray()

SCIP_Bool COLORprobIsNodeInArray	(	int	node,
		int *	arraynodes,
		int	narraynodes
	)

checks whether the given node is in the given array

Parameters

node	the number of the node
arraynodes	the nodes of the maximum stableset
narraynodes	number of nodes in the maximum stableset

Definition at line 1325 of file probdata_coloring.c.

References FALSE, NULL, and TRUE.

Referenced by preprocessGraph().

◆ COLORprobEqualSortedArrays()

SCIP_Bool COLORprobEqualSortedArrays	(	int *	array1nodes,
		int	narray1nodes,
		int *	array2nodes,
		int	narray2nodes
	)

checks whether the given two given arrays are equal

Parameters

array1nodes	the nodes of the first set
narray1nodes	number of nodes in the first set
array2nodes	the nodes of the second set
narray2nodes	number of nodes in the second set

Definition at line 1346 of file probdata_coloring.c.

References FALSE, NULL, and TRUE.

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ EVENTHDLR_NAME

◆ EVENTHDLR_DESC

Function Documentation

◆ preprocessGraph()

◆ SCIP_DECL_PROBTRANS()

◆ SCIP_DECL_PROBDELTRANS()

◆ SCIP_DECL_PROBDELORIG()

◆ SCIP_DECL_EVENTEXEC()

◆ SCIPcreateProbColoring()

◆ COLORprobGetNStableSets()

◆ COLORprobPrintStableSets()

◆ COLORprobPrintStableSet()

◆ COLORprobAddVarForStableSet()

◆ COLORprobGetVarForStableSet()

◆ COLORprobIsNodeInStableSet()

◆ COLORprobStableSetsAreEqual()

◆ COLORprobStableSetIsNew()

◆ COLORprobAddNewStableSet()

◆ COLORprobGetStableSet()

◆ COLORprobGetStableSets()

◆ COLORprobGetNNodes()

◆ COLORprobGetOriginalNNodes()

◆ COLORprobGetGraph()

◆ COLORprobGetOriginalGraph()

◆ COLORprobGetDeletedNodes()

◆ COLORprobGetOriginalNodesForNewNodes()

◆ COLORprobGetNewNodeForOriginalNode()

◆ COLORprobGetConstraints()

◆ COLORprobGetConstraint()

◆ COLORprobGetComplementaryGraph()

◆ COLORprobSetUpArrayOfCons()

◆ COLORprobIsNodeInArray()

◆ COLORprobEqualSortedArrays()