Scippy

SCIP

Solving Constraint Integer Programs

pricer_coloring.c File Reference

Detailed Description

variable pricer for the vertex coloring problem

Author
Gerald Gamrath
Rolf van der Hulst

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)
 

Macro Definition Documentation

◆ PRICER_NAME

#define PRICER_NAME   "coloring"

Definition at line 57 of file pricer_coloring.c.

Referenced by SCIP_DECL_PRICERCOPY(), and SCIPincludePricerColoring().

◆ PRICER_DESC

#define PRICER_DESC   "pricer for coloring"

Definition at line 58 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ PRICER_PRIORITY

#define PRICER_PRIORITY   5000000

Definition at line 59 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ PRICER_DELAY

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

◆ MAXDNOM

#define MAXDNOM   10000LL

Definition at line 63 of file pricer_coloring.c.

Referenced by calculateScalingValue().

◆ MINDELTA

#define MINDELTA   1e-12

◆ MAXDELTA

#define MAXDELTA   1e-09

Definition at line 65 of file pricer_coloring.c.

Referenced by buildFlowCover(), and calculateScalingValue().

◆ DEFAULT_MAXVARSROUND

#define DEFAULT_MAXVARSROUND   1

Definition at line 69 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ DEFAULT_USETCLIQUE

#define DEFAULT_USETCLIQUE   TRUE

Definition at line 70 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ DEFAULT_USEGREEDY

#define DEFAULT_USEGREEDY   TRUE

Definition at line 71 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ DEFAULT_ONLYBEST

#define DEFAULT_ONLYBEST   FALSE

Definition at line 72 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT   -1

Definition at line 73 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ DEFAULT_MAXROUNDSNODE

#define DEFAULT_MAXROUNDSNODE   -1

Definition at line 74 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ DEFAULT_MAXTCLIQUENODES

#define DEFAULT_MAXTCLIQUENODES   INT_MAX

Definition at line 75 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

Function Documentation

◆ hasUncoloredNode()

static SCIP_Bool hasUncoloredNode ( TCLIQUE_GRAPH graph,
SCIP_Bool colored 
)
static

returns whether the graph has an uncolored node

Parameters
graphthe graph that should be colored
coloredarray of booleans, colored[i] == TRUE iff node i is colored

Definition at line 117 of file pricer_coloring.c.

References FALSE, NULL, and TRUE.

Referenced by SCIP_DECL_PRICERFARKAS().

◆ sortNodes()

static SCIP_RETCODE sortNodes ( SCIP scip,
SCIP_Real weights,
int  nnodes,
int *  sortednodes 
)
static

sorts the nodes from 0 to nnodes-1 w.r.t. the given weights

Parameters
scipSCIP data structure
weightsthe weights for sorting
nnodesthe number of nodes
sortednodesthe array that will be overwritten with the sorted node numbers

Definition at line 140 of file pricer_coloring.c.

References nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortDownRealInt().

Referenced by SCIP_DECL_PRICERREDCOST().

◆ greedyStableSet()

static SCIP_RETCODE greedyStableSet ( SCIP scip,
TCLIQUE_GRAPH graph,
SCIP_Bool colored,
int *  maxstablesetnodes,
int *  nmaxstablesetnodes 
)
static

computes a stable set with a greedy-method. attention: the weight of the maximum stable set is not computed!

Parameters
scipSCIP data structure
graphpointer to graph data structure
coloredarray for marking yet colored nodes
maxstablesetnodespointer to store nodes of the maximum weight stableset
nmaxstablesetnodespointer to store number of nodes in the maximum weight stableset

Definition at line 170 of file pricer_coloring.c.

References FALSE, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownRealInt(), tcliqueGetDegrees(), and TRUE.

Referenced by SCIP_DECL_PRICERFARKAS().

◆ calculateScalingValue()

static SCIP_RETCODE calculateScalingValue ( SCIP_PRICERDATA pricerdata,
int  nnodes 
)
static

Calculates a good scalar value to use in order to scale the dual weights to integer values without large loss of precision

Parameters
pricerdatapricer data
nnodesnumber of nodes

Definition at line 243 of file pricer_coloring.c.

References MAXDELTA, MAXDNOM, MINDELTA, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPcalcIntegralScalar().

Referenced by SCIP_DECL_PRICERREDCOST().

◆ getScaledDualWeight()

static TCLIQUE_WEIGHT getScaledDualWeight ( SCIP_Real  val,
SCIP_Real  scalefactor,
SCIP_Real  mindelta 
)
static

get scaled weight

Parameters
valvalue to be scaled
scalefactorscaling factor
mindeltaminimal delta value

Definition at line 276 of file pricer_coloring.c.

References EPSCEIL, EPSFLOOR, SCIP_Real, and SCIPrelDiff().

Referenced by SCIP_DECL_PRICERREDCOST().

◆ TCLIQUE_NEWSOL()

static TCLIQUE_NEWSOL ( tcliqueNewsolPricer  )
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 COLORprobStableSetIsNew(), FALSE, NULL, and TRUE.

◆ SCIP_DECL_PRICERCOPY()

static SCIP_DECL_PRICERCOPY ( pricerCopyColoring  )
static

copy method for pricer plugins (called when SCIP copies plugins)

Definition at line 349 of file pricer_coloring.c.

References NULL, PRICER_NAME, SCIP_OKAY, and SCIPpricerGetName().

◆ SCIP_DECL_PRICERFREE()

static SCIP_DECL_PRICERFREE ( pricerFreeColoring  )
static

destructor of variable pricer to free user data (called when SCIP is exiting)

Definition at line 361 of file pricer_coloring.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpricerGetData(), and SCIPpricerSetData().

◆ SCIP_DECL_PRICERINITSOL()

static SCIP_DECL_PRICERINITSOL ( pricerInitsolColoring  )
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 COLORprobGetNNodes(), COLORprobGetNStableSets(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPpricerGetData(), and SCIPsetIntParam().

◆ SCIP_DECL_PRICEREXITSOL()

static SCIP_DECL_PRICEREXITSOL ( pricerExitsolColoring  )
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 COLORprobGetNNodes(), NULL, SCIP_OKAY, SCIPfreeBlockMemoryArray, and SCIPpricerGetData().

◆ SCIP_DECL_PRICERREDCOST()

◆ SCIP_DECL_PRICERFARKAS()

◆ SCIP_DECL_PARAMCHGD()

static SCIP_DECL_PARAMCHGD ( paramChgdMaxvarsround  )
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 COLORprobGetNNodes(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPdebugMessage, SCIPfreeBlockMemoryArray, and SCIPparamGetData().

◆ SCIPincludePricerColoring()