Solving Constraint Integer Programs

pricer_coloring.h File Reference

Detailed Description

variable pricer for the vertex coloring problem

Gerald Gamrath

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 dual-variables 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 greedy-method. If it fails, the tclique-algorithm is used on the complementary graph. This is a branch-and-bound 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 branch-and-bound 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.

Go to the source code of this file.


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)

◆ COLORpricerUseOnlyBestStableSets()

void COLORpricerUseOnlyBestStableSets ( SCIP scip,
SCIP_Bool  onlybest 

sets the way, the pricer handles variables with negative reduced costs found during the tclique-algorithm 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

scipSCIP data structure
onlybesttrue, if only the best vars should be used

◆ COLORpricerUseGreedy()

void COLORpricerUseGreedy ( SCIP scip,
SCIP_Bool  usegreedy 
scipSCIP data structure
usegreedytrue, if the greedy should be used

◆ COLORpricerUseTclique()

void COLORpricerUseTclique ( SCIP scip,
SCIP_Bool  usetclique 
scipSCIP data structure
usetcliquetrue, if the tclique-algorithm should be used

◆ COLORpricerSetNVarsCreatedPerRound()

void COLORpricerSetNVarsCreatedPerRound ( SCIP scip,
int  nvars 
scipSCIP data structure
nvarsmaximal number of variables that should be created in one round