Scippy

SCIP

Solving Constraint Integer Programs

probdata_coloring.c File Reference

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.

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_VARCOLORprobGetVarForStableSet (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_GRAPHCOLORprobGetGraph (SCIP *scip)
 
TCLIQUE_GRAPHCOLORprobGetOriginalGraph (SCIP *scip)
 
int * COLORprobGetDeletedNodes (SCIP *scip)
 
int * COLORprobGetOriginalNodesForNewNodes (SCIP *scip)
 
int COLORprobGetNewNodeForOriginalNode (SCIP *scip, int node)
 
SCIP_CONS ** COLORprobGetConstraints (SCIP *scip)
 
SCIP_CONSCOLORprobGetConstraint (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
scipSCIP 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()

◆ 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

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecProbdatavardeleted  )
static

◆ SCIPcreateProbColoring()

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

sets up the problem data

Parameters
scipSCIP data structure
nameproblem name
nnodesnumber of nodes
nedgesnumber of edges
edgesarray 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
scipSCIP 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
scipSCIP 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
scipSCIP data structure
setnumberthe 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
scipSCIP data structure
setindexindex of the stable set
varpointer 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
scipSCIP data structure
setindexindex 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
scipSCIP data structure
setindexindex of the stable set
nodenumber 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
scipSCIP data structure
set1array of nodes in the first set
nset1nodesnumber of nodes in the first set
set2array of nodes in the second set
nset2nodesnumber 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
scipSCIP data structure
stablesetnodesarray of nodes in the stable set
nstablesetnodesnumber 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
scipSCIP data structure
stablesetnodesarray of nodes in the stable set
nstablesetnodesnumber of nodes in the stable set
setindexreturn 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
scipSCIP data structure
setindexindex of the stable set
stablesetreturn value: pointer to the stable set
nelementsreturn 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
scipSCIP data structure
stablesetsreturn value: pointer to the stable sets
nelementsreturn value: number of elements in the stable sets
nstablesetsreturn 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()

◆ COLORprobGetOriginalNNodes()

int COLORprobGetOriginalNNodes ( SCIP scip)

returns the number of nodes in the original graph

Parameters
scipSCIP 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
scipSCIP 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
scipSCIP 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
scipSCIP 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
scipSCIP 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
scipSCIP data structure
nodea 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
scipSCIP 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
scipSCIP data structure
nodenumber 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
scipSCIP data structure
graphthe given graph
cgraphthe 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
scipSCIP 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
nodethe number of the node
arraynodesthe nodes of the maximum stableset
narraynodesnumber 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
array1nodesthe nodes of the first set
narray1nodesnumber of nodes in the first set
array2nodesthe nodes of the second set
narray2nodesnumber of nodes in the second set

Definition at line 1355 of file probdata_coloring.c.

References FALSE, NULL, and TRUE.