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 54 of file probdata_coloring.c.

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC "event handler for variable deleted event"

Definition at line 55 of file probdata_coloring.c.

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 97 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 465 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 559 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 592 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 635 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 680 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 762 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 777 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 804 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 832 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 856 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 873 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 911 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 945 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 978 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 1032 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 1051 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 1071 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 1086 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 1101 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 1117 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 1132 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 1147 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 1163 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 1190 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 1205 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_CONSACTIVE().

◆ 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 1222 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 1305 of file probdata_coloring.c.

References COLORprobGetConstraints(), COLORprobGetNNodes(), FALSE, nnodes, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsSetcover(), SCIPsnprintf(), 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 1334 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 1355 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()