Scippy

SCIP

Solving Constraint Integer Programs

probdata_coloring.h 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.h.

#include <assert.h>
#include "scip/scip.h"
#include "tclique/tclique.h"
#include "scip/cons_setppc.h"
#include "reader_col.h"

Go to the source code of this file.

Functions

int COLORprobGetNStableSets (SCIP *scip)
 
void COLORprobGetStableSet (SCIP *scip, int setindex, int **stableset, int *nelements)
 
void COLORprobGetStableSets (SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
 
SCIP_RETCODE COLORprobAddNewStableSet (SCIP *scip, int *cliquenodes, int ncliquenodes, int *setindex)
 
SCIP_RETCODE COLORprobAddVarForStableSet (SCIP *scip, int setindex, SCIP_VAR *var)
 
SCIP_VARCOLORprobGetVarForStableSet (SCIP *scip, int setindex)
 
SCIP_Bool COLORprobStableSetIsNew (SCIP *scip, int *stablesetnodes, int nstablesetnodes)
 
SCIP_Bool COLORprobStableSetsAreEqual (SCIP *scip, int *set1, int nset1nodes, int *set2, int nset2nodes)
 
void COLORprobPrintStableSets (SCIP *scip)
 
void COLORprobPrintStableSet (SCIP *scip, int setnumber)
 
SCIP_Bool COLORprobIsNodeInStableSet (SCIP *scip, int setindex, int node)
 
SCIP_RETCODE COLORprobSetUpArrayOfCons (SCIP *scip)
 
SCIP_CONS ** COLORprobGetConstraints (SCIP *scip)
 
SCIP_CONSCOLORprobGetConstraint (SCIP *scip, int node)
 
TCLIQUE_GRAPHCOLORprobGetGraph (SCIP *scip)
 
TCLIQUE_GRAPHCOLORprobGetOriginalGraph (SCIP *scip)
 
SCIP_RETCODE COLORprobGetComplementaryGraph (SCIP *scip, TCLIQUE_GRAPH *graph, TCLIQUE_GRAPH *cgraph)
 
int COLORprobGetNNodes (SCIP *scip)
 
int COLORprobGetOriginalNNodes (SCIP *scip)
 
int * COLORprobGetDeletedNodes (SCIP *scip)
 
int * COLORprobGetOriginalNodesForNewNodes (SCIP *scip)
 
int COLORprobGetNewNodeForOriginalNode (SCIP *scip, int node)
 
SCIP_Bool COLORprobIsNodeInArray (int node, int *arrayNodes, int narraynodes)
 
SCIP_Bool COLORprobEqualSortedArrays (int *array1nodes, int narray1nodes, int *array2nodes, int narray2nodes)
 
SCIP_RETCODE SCIPcreateProbColoring (SCIP *scip, const char *name, int nnodes, int nedges, int **edges)
 

Function Documentation

◆ COLORprobGetNStableSets()

int COLORprobGetNStableSets ( SCIP scip)

returns the number of stable sets / variables

Parameters
scipSCIP 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().

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

References NULL, and SCIPgetProbData().

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

◆ COLORprobAddNewStableSet()

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

adds a new stable set, the set must be sorted descendingly, attention: you need to check whether it is new before adding it

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 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().

◆ 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 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
scipSCIP data structure
setindexindex 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().

◆ 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 and FALSE if it is part of or equal to an already existing stable set

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

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

Referenced by SCIP_DECL_PRICERREDCOST(), and TCLIQUE_NEWSOL().

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

References FALSE, NULL, and TRUE.

Referenced by COLORprobStableSetIsNew().

◆ COLORprobPrintStableSets()

void COLORprobPrintStableSets ( SCIP scip)

prints all stable sets to standart output

prints all stable sets to standard output

Parameters
scipSCIP 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 standart output

prints the requested stable set to standard output

Parameters
scipSCIP data structure
setnumberthe number of the requested set

Definition at line 795 of file probdata_coloring.c.

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

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

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

Referenced by computeBranchingPriorities(), and SCIP_DECL_CONSPROP().

◆ COLORprobSetUpArrayOfCons()

SCIP_RETCODE COLORprobSetUpArrayOfCons ( SCIP scip)

creates all node-constraints and saves them in an array

Parameters
scipSCIP 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().

◆ COLORprobGetConstraints()

SCIP_CONS** COLORprobGetConstraints ( SCIP scip)

returns all node-constraints

Parameters
scipSCIP 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
scipSCIP data structure
nodenumber 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().

◆ COLORprobGetGraph()

TCLIQUE_GRAPH* COLORprobGetGraph ( SCIP scip)

returns the (preprocessed) graph

Parameters
scipSCIP 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
scipSCIP data structure

Definition at line 1108 of file probdata_coloring.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_READERWRITE().

◆ 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 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().

◆ COLORprobGetNNodes()

◆ COLORprobGetOriginalNNodes()

int COLORprobGetOriginalNNodes ( SCIP scip)

returns the number of nodes in the original graph

Parameters
scipSCIP 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().

◆ 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 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
scipSCIP 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
scipSCIP data structure
nodea node in the original graph

Definition at line 1154 of file probdata_coloring.c.

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

Referenced by SCIP_DECL_READERREAD().

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

References FALSE, NULL, and TRUE.

◆ 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 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().