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 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.c.
#include <assert.h>
#include <string.h>
#include "pricer_coloring.h"
#include "reader_col.h"
#include "cons_storeGraph.h"
#include <stdio.h>
#include <stdlib.h>
Go to the source code of this file.
Macros | |
#define | PRICER_NAME "coloring" |
#define | PRICER_DESC "pricer for coloring" |
#define | PRICER_PRIORITY 5000000 |
#define | PRICER_DELAY TRUE /* only call pricer if all problem variables have non-negative reduced costs */ |
#define | MAXDNOM 10000LL |
#define | MINDELTA 1e-12 |
#define | MAXDELTA 1e-09 |
#define | DEFAULT_MAXVARSROUND 1 |
#define | DEFAULT_USETCLIQUE TRUE |
#define | DEFAULT_USEGREEDY TRUE |
#define | DEFAULT_ONLYBEST FALSE |
#define | DEFAULT_MAXROUNDSROOT -1 |
#define | DEFAULT_MAXROUNDSNODE -1 |
#define | DEFAULT_MAXTCLIQUENODES INT_MAX |
Functions | |
static SCIP_Bool | hasUncoloredNode (TCLIQUE_GRAPH *graph, SCIP_Bool *colored) |
static SCIP_RETCODE | sortNodes (SCIP *scip, SCIP_Real *weights, int nnodes, int *sortednodes) |
static SCIP_RETCODE | greedyStableSet (SCIP *scip, TCLIQUE_GRAPH *graph, SCIP_Bool *colored, int *maxstablesetnodes, int *nmaxstablesetnodes) |
static SCIP_RETCODE | calculateScalingValue (SCIP_PRICERDATA *pricerdata, int nnodes) |
static TCLIQUE_WEIGHT | getScaledDualWeight (SCIP_Real val, SCIP_Real scalefactor, SCIP_Real mindelta) |
static | TCLIQUE_NEWSOL (tcliqueNewsolPricer) |
static | SCIP_DECL_PRICERCOPY (pricerCopyColoring) |
static | SCIP_DECL_PRICERFREE (pricerFreeColoring) |
static | SCIP_DECL_PRICERINITSOL (pricerInitsolColoring) |
static | SCIP_DECL_PRICEREXITSOL (pricerExitsolColoring) |
static | SCIP_DECL_PRICERREDCOST (pricerRedcostColoring) |
static | SCIP_DECL_PRICERFARKAS (pricerFarkasColoring) |
static | SCIP_DECL_PARAMCHGD (paramChgdMaxvarsround) |
SCIP_RETCODE | SCIPincludePricerColoring (SCIP *scip) |
#define PRICER_NAME "coloring" |
Definition at line 57 of file pricer_coloring.c.
Referenced by SCIP_DECL_PRICERCOPY(), SCIPincludePricerBinpacking(), SCIPincludePricerColoring(), SCIPincludePricerRpa(), SCIPpricerBinpackingActivate(), and SCIPpricerRpaActivate().
#define PRICER_DESC "pricer for coloring" |
Definition at line 58 of file pricer_coloring.c.
Referenced by SCIPincludePricerBinpacking(), SCIPincludePricerColoring(), and SCIPincludePricerRpa().
#define PRICER_PRIORITY 5000000 |
Definition at line 59 of file pricer_coloring.c.
Referenced by SCIPincludePricerBinpacking(), SCIPincludePricerColoring(), and SCIPincludePricerRpa().
#define PRICER_DELAY TRUE /* only call pricer if all problem variables have non-negative reduced costs */ |
Definition at line 60 of file pricer_coloring.c.
Referenced by SCIPincludePricerBinpacking(), SCIPincludePricerColoring(), and SCIPincludePricerRpa().
#define MAXDNOM 10000LL |
Definition at line 63 of file pricer_coloring.c.
#define MINDELTA 1e-12 |
Definition at line 64 of file pricer_coloring.c.
Referenced by calculateScalingValue(), and SCIP_DECL_PRICERREDCOST().
#define MAXDELTA 1e-09 |
Definition at line 65 of file pricer_coloring.c.
Referenced by calculateScalingValue().
#define DEFAULT_MAXVARSROUND 1 |
Definition at line 69 of file pricer_coloring.c.
Referenced by SCIPincludePricerColoring().
#define DEFAULT_USETCLIQUE TRUE |
Definition at line 70 of file pricer_coloring.c.
#define DEFAULT_USEGREEDY TRUE |
Definition at line 71 of file pricer_coloring.c.
Referenced by SCIPincludePricerColoring().
#define DEFAULT_ONLYBEST FALSE |
Definition at line 72 of file pricer_coloring.c.
Referenced by SCIPincludePricerColoring().
#define DEFAULT_MAXROUNDSROOT -1 |
Definition at line 73 of file pricer_coloring.c.
#define DEFAULT_MAXROUNDSNODE -1 |
Definition at line 74 of file pricer_coloring.c.
Referenced by SCIPincludePricerColoring().
#define DEFAULT_MAXTCLIQUENODES INT_MAX |
Definition at line 75 of file pricer_coloring.c.
Referenced by SCIPincludePricerColoring().
|
static |
returns whether the graph has an uncolored node
graph | the graph that should be colored |
colored | array of booleans, colored[i] == TRUE iff node i is colored |
Definition at line 117 of file pricer_coloring.c.
References assert(), FALSE, i, NULL, SCIP_Bool, and TRUE.
Referenced by SCIP_DECL_PRICERFARKAS().
|
static |
sorts the nodes from 0 to nnodes-1 w.r.t. the given weights
scip | SCIP data structure |
weights | the weights for sorting |
nnodes | the number of nodes |
sortednodes | the array that will be overwritten with the sorted node numbers |
Definition at line 140 of file pricer_coloring.c.
References assert(), i, nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortDownRealInt().
Referenced by SCIP_DECL_PRICERREDCOST().
|
static |
computes a stable set with a greedy-method. attention: the weight of the maximum stable set is not computed!
scip | SCIP data structure |
graph | pointer to graph data structure |
colored | array for marking yet colored nodes |
maxstablesetnodes | pointer to store nodes of the maximum weight stableset |
nmaxstablesetnodes | pointer to store number of nodes in the maximum weight stableset |
Definition at line 170 of file pricer_coloring.c.
References assert(), FALSE, i, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownRealInt(), tcliqueGetDegrees(), and TRUE.
Referenced by SCIP_DECL_PRICERFARKAS().
|
static |
Calculates a good scalar value to use in order to scale the dual weights to integer values without large loss of precision
pricerdata | pricer data |
nnodes | number of nodes |
Definition at line 243 of file pricer_coloring.c.
References i, MAXDELTA, MAXDNOM, MINDELTA, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPcalcIntegralScalar().
Referenced by SCIP_DECL_PRICERREDCOST().
|
static |
get scaled weight
val | value to be scaled |
scalefactor | scaling factor |
mindelta | minimal delta value |
Definition at line 276 of file pricer_coloring.c.
References EPSCEIL, EPSFLOOR, SCIP_Real, and SCIPrelDiff().
Referenced by SCIP_DECL_PRICERREDCOST().
|
static |
generates improving variables using a stable set found by the algorithm for maximum weight clique, decides whether to stop generating cliques with the algorithm for maximum weight clique
Definition at line 303 of file pricer_coloring.c.
References assert(), COLORprobStableSetIsNew(), FALSE, i, NULL, and TRUE.
|
static |
copy method for pricer plugins (called when SCIP copies plugins)
Definition at line 349 of file pricer_coloring.c.
References assert(), NULL, PRICER_NAME, SCIP_OKAY, and SCIPpricerGetName().
|
static |
destructor of variable pricer to free user data (called when SCIP is exiting)
Definition at line 361 of file pricer_coloring.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpricerGetData(), and SCIPpricerSetData().
|
static |
solving process initialization method of variable pricer (called when branch and bound process is about to begin)
Definition at line 384 of file pricer_coloring.c.
References assert(), COLORprobGetNNodes(), COLORprobGetNStableSets(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPpricerGetData(), and SCIPsetIntParam().
|
static |
solving process deinitialization method of variable pricer (called before branch and bound process data is freed)
Definition at line 410 of file pricer_coloring.c.
References assert(), COLORprobGetNNodes(), i, NULL, SCIP_OKAY, SCIPfreeBlockMemoryArray, and SCIPpricerGetData().
|
static |
reduced cost pricing method of variable pricer for feasible LPs
Definition at line 438 of file pricer_coloring.c.
References assert(), calculateScalingValue(), COLORconsGetComplementaryGraph(), COLORconsGetCurrentGraph(), COLORprobAddNewStableSet(), COLORprobAddVarForStableSet(), COLORprobGetConstraints(), COLORprobGetNStableSets(), COLORprobStableSetIsNew(), FALSE, getScaledDualWeight(), i, MAX, MIN, MINDELTA, nnodes, NULL, result, TCLIQUE_Data::scip, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIP_VARTYPE_BINARY, SCIPaddCoefSetppc(), SCIPaddPricedVar(), SCIPallocBufferArray, SCIPchgVarUbLazy(), SCIPcreateVar(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetDualsolSetppc(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNVars(), SCIPinfinity(), SCIPisFeasGT(), SCIPpricerGetData(), SCIPupdateLocalLowerbound(), SCIPvarMarkDeletable(), sortNodes(), TCLIQUE_OPTIMAL, TCLIQUE_USERABORT, tcliqueChangeWeight(), tcliqueMaxClique(), TRUE, and var.
|
static |
farkas pricing method of variable pricer for infeasible LPs
Definition at line 707 of file pricer_coloring.c.
References assert(), BMSclearMemoryArray, COLORconsGetCurrentGraph(), COLORprobAddNewStableSet(), COLORprobAddVarForStableSet(), COLORprobGetConstraints(), COLORprobGetNNodes(), COLORprobGetStableSets(), COLORprobGetVarForStableSet(), greedyStableSet(), hasUncoloredNode(), i, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPaddCoefSetppc(), SCIPaddPricedVar(), SCIPallocBufferArray, SCIPchgVarUbLazy(), SCIPcreateVar(), SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetNNodes(), SCIPgetRootNode(), SCIPisFeasZero(), SCIPsortDownInt(), SCIPvarGetUbLocal(), SCIPvarIsInLP(), SCIPvarMarkDeletable(), TRUE, and var.
|
static |
method to call, when the maximal number of variables priced in each round is changed
Definition at line 796 of file pricer_coloring.c.
References assert(), COLORprobGetNNodes(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPdebugMessage, SCIPfreeBlockMemoryArray, and SCIPparamGetData().
SCIP_RETCODE SCIPincludePricerColoring | ( | SCIP * | scip | ) |
creates the coloring variable pricer and includes it in SCIP
scip | SCIP data structure |
Definition at line 849 of file pricer_coloring.c.
References assert(), 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().