Detailed Description
variable pricer for the vertex coloring problem
This file implements the pricer for the coloring algorithm.
It computes maximal stable sets in the current graph whose corresponding variables can improve the current LP solution. This is done by computing a maximum weighted stable set in the current graph with dualvariables of the node constraints as weights. A variable can improve the solution, if the weight of the corresponding stable set is larger than 1, since it then has negative reduced costs, which are given by (1  weight of the set).
The pricer first tries to compute such a stable set using a a greedymethod. If it fails, the tcliquealgorithm is used on the complementary graph. This is a branchandbound based algorithm for maximal cliques, included in SCIP. In this case, not only the best solution is added to the LP, but also all other stable sets found during the branchandbound process that could improve the current LP solution are added, limited to a maximal number that can be changed by a parameter.
Definition in file pricer_coloring.h.
#include "probdata_coloring.h"
Go to the source code of this file.
Functions  
SCIP_RETCODE  SCIPincludePricerColoring (SCIP *scip) 
void  COLORpricerUseOnlyBestStableSets (SCIP *scip, SCIP_Bool onlybest) 
void  COLORpricerUseGreedy (SCIP *scip, SCIP_Bool usegreedy) 
void  COLORpricerUseTclique (SCIP *scip, SCIP_Bool usetclique) 
void  COLORpricerSetNVarsCreatedPerRound (SCIP *scip, int nvars) 
Function Documentation
◆ SCIPincludePricerColoring()
SCIP_RETCODE SCIPincludePricerColoring  (  SCIP *  scip  ) 
creates the healthcare variable pricer and includes it in SCIP
creates the coloring variable pricer and includes it in SCIP
 Parameters

scip SCIP data structure
Definition at line 849 of file pricer_coloring.c.
References DEFAULT_MAXROUNDSNODE, DEFAULT_MAXROUNDSROOT, DEFAULT_MAXTCLIQUENODES, DEFAULT_MAXVARSROUND, DEFAULT_ONLYBEST, DEFAULT_USEGREEDY, DEFAULT_USETCLIQUE, FALSE, NULL, PRICER_DELAY, PRICER_DESC, PRICER_NAME, PRICER_PRIORITY, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocBlockMemory, SCIPincludePricerBasic(), SCIPsetPricerCopy(), SCIPsetPricerExitsol(), SCIPsetPricerFree(), SCIPsetPricerInitsol(), and TRUE.
Referenced by SCIPincludeColoringPlugins().
◆ COLORpricerUseOnlyBestStableSets()
sets the way, the pricer handles variables with negative reduced costs found during the tcliquealgorithm if onlybest is true, only the best n variables are added to the lp, while onlybest = false means, that the first n variables with negative reduced costs are added Here, n is the value set by setNVarsCreatedPerRound
 Parameters

scip SCIP data structure onlybest true, if only the best vars should be used
◆ COLORpricerUseGreedy()
 Parameters

scip SCIP data structure usegreedy true, if the greedy should be used
◆ COLORpricerUseTclique()
 Parameters

scip SCIP data structure usetclique true, if the tcliquealgorithm should be used
◆ COLORpricerSetNVarsCreatedPerRound()
void COLORpricerSetNVarsCreatedPerRound  (  SCIP *  scip, 
int  nvars  
) 
 Parameters

scip SCIP data structure nvars maximal number of variables that should be created in one round