Detailed Description

variable pricer for the vertex coloring problem

Author: 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.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 1000LL

#define	MINDELTA 1e-03

#define	MAXDELTA 1e-09

#define	MAXSCALE 1000.0

#define	DEFAULT_MAXVARSROUND 0

#define	DEFAULT_USETCLIQUE TRUE

#define	DEFAULT_USEGREEDY TRUE

#define	DEFAULT_ONLYBEST TRUE

#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_Bool	isIntegralScalar (SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta)

static SCIP_Longint	getIntegralVal (SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta)

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 47 of file pricer_coloring.c.

Referenced by SCIP_DECL_PRICERCOPY(), and SCIPincludePricerColoring().

◆ PRICER_DESC

#define PRICER_DESC "pricer for coloring"

Definition at line 48 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ PRICER_PRIORITY

#define PRICER_PRIORITY 5000000

Definition at line 49 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 50 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ MAXDNOM

#define MAXDNOM 1000LL

Definition at line 53 of file pricer_coloring.c.

Referenced by SCIP_DECL_PRICERREDCOST().

◆ MINDELTA

#define MINDELTA 1e-03

Definition at line 54 of file pricer_coloring.c.

Referenced by buildFlowCover(), and SCIP_DECL_PRICERREDCOST().

◆ MAXDELTA

#define MAXDELTA 1e-09

Definition at line 55 of file pricer_coloring.c.

Referenced by buildFlowCover(), and SCIP_DECL_PRICERREDCOST().

◆ MAXSCALE

#define MAXSCALE 1000.0

Definition at line 56 of file pricer_coloring.c.

Referenced by SCIP_DECL_PRICERREDCOST().

◆ DEFAULT_MAXVARSROUND

#define DEFAULT_MAXVARSROUND 0

Definition at line 60 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ DEFAULT_USETCLIQUE

#define DEFAULT_USETCLIQUE TRUE

Definition at line 61 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ DEFAULT_USEGREEDY

#define DEFAULT_USEGREEDY TRUE

Definition at line 62 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ DEFAULT_ONLYBEST

#define DEFAULT_ONLYBEST TRUE

Definition at line 63 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT -1

Definition at line 64 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ DEFAULT_MAXROUNDSNODE

#define DEFAULT_MAXROUNDSNODE -1

Definition at line 65 of file pricer_coloring.c.

Referenced by SCIPincludePricerColoring().

◆ DEFAULT_MAXTCLIQUENODES

#define DEFAULT_MAXTCLIQUENODES INT_MAX

Definition at line 66 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

graph	the graph that should be colored
colored	array of booleans, colored[i] == TRUE iff node i is colored

Definition at line 109 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

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 132 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

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

◆ isIntegralScalar()

static SCIP_Bool isIntegralScalar	(	SCIP_Real	val,
		SCIP_Real	scalar,
		SCIP_Real	mindelta,
		SCIP_Real	maxdelta
	)

static

checks, whether the given scalar scales the given value to an integral number with error in the given bounds

Parameters

val	value that should be scaled to an integral value
scalar	scalar that should be tried
mindelta	minimal relative allowed difference of scaled coefficient s*c and integral i
maxdelta	maximal relative allowed difference of scaled coefficient s*c and integral i

Definition at line 235 of file pricer_coloring.c.

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

Referenced by SCIP_DECL_PRICERREDCOST().

◆ getIntegralVal()

static SCIP_Longint getIntegralVal	(	SCIP_Real	val,
		SCIP_Real	scalar,
		SCIP_Real	mindelta,
		SCIP_Real	maxdelta
	)

static

get integral number with error in the bounds which corresponds to given value scaled by a given scalar; should be used in connection with isIntegralScalar()

Parameters

val	value that should be scaled to an integral value
scalar	scalar that should be tried
mindelta	minimal relative allowed difference of scaled coefficient s*c and integral i
maxdelta	maximal relative allowed difference of scaled coefficient s*c and integral i

Definition at line 260 of file pricer_coloring.c.

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

Referenced by buildFlowCover(), and 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 293 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 354 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 366 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 389 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 415 of file pricer_coloring.c.

References COLORprobGetNNodes(), NULL, SCIP_OKAY, SCIPfreeBlockMemoryArray, and SCIPpricerGetData().

◆ SCIP_DECL_PRICERREDCOST()

static SCIP_DECL_PRICERREDCOST ( pricerRedcostColoring )

static

reduced cost pricing method of variable pricer for feasible LPs

Definition at line 443 of file pricer_coloring.c.

References COLORconsGetComplementaryGraph(), COLORconsGetCurrentGraph(), COLORprobAddNewStableSet(), COLORprobAddVarForStableSet(), COLORprobGetConstraints(), COLORprobGetNStableSets(), COLORprobStableSetIsNew(), FALSE, getIntegralVal(), isIntegralScalar(), MAX, MAXDELTA, MAXDNOM, MAXSCALE, MINDELTA, nnodes, NULL, TCLIQUE_Data::scip, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIP_VARTYPE_BINARY, SCIPaddCoefSetppc(), SCIPaddPricedVar(), SCIPallocBufferArray, SCIPcalcIntegralScalar(), SCIPchgVarUbLazy(), SCIPcreateVar(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetDualsolSetppc(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNVars(), SCIPgetPrimalbound(), SCIPinfinity(), SCIPisFeasGT(), SCIPpricerGetData(), SCIPvarMarkDeletable(), sortNodes(), TCLIQUE_OPTIMAL, tcliqueChangeWeight(), tcliqueMaxClique(), and TRUE.

◆ SCIP_DECL_PRICERFARKAS()

static SCIP_DECL_PRICERFARKAS ( pricerFarkasColoring )

static

farkas pricing method of variable pricer for infeasible LPs

Definition at line 733 of file pricer_coloring.c.

References BMSclearMemoryArray, COLORconsGetCurrentGraph(), COLORprobAddNewStableSet(), COLORprobAddVarForStableSet(), COLORprobGetConstraints(), COLORprobGetNNodes(), COLORprobGetStableSets(), COLORprobGetVarForStableSet(), greedyStableSet(), hasUncoloredNode(), 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(), and TRUE.

◆ 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 822 of file pricer_coloring.c.

References COLORprobGetNNodes(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPdebugMessage, SCIPfreeBlockMemoryArray, and SCIPparamGetData().

◆ SCIPincludePricerColoring()

SCIP_RETCODE SCIPincludePricerColoring ( SCIP * scip )

creates the coloring variable pricer and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 875 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().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PRICER_NAME

◆ PRICER_DESC

◆ PRICER_PRIORITY

◆ PRICER_DELAY

◆ MAXDNOM

◆ MINDELTA

◆ MAXDELTA

◆ MAXSCALE

◆ DEFAULT_MAXVARSROUND

◆ DEFAULT_USETCLIQUE

◆ DEFAULT_USEGREEDY

◆ DEFAULT_ONLYBEST

◆ DEFAULT_MAXROUNDSROOT

◆ DEFAULT_MAXROUNDSNODE

◆ DEFAULT_MAXTCLIQUENODES

Function Documentation

◆ hasUncoloredNode()

◆ sortNodes()

◆ greedyStableSet()

◆ isIntegralScalar()

◆ getIntegralVal()

◆ TCLIQUE_NEWSOL()

◆ SCIP_DECL_PRICERCOPY()

◆ SCIP_DECL_PRICERFREE()

◆ SCIP_DECL_PRICERINITSOL()

◆ SCIP_DECL_PRICEREXITSOL()

◆ SCIP_DECL_PRICERREDCOST()

◆ SCIP_DECL_PRICERFARKAS()

◆ SCIP_DECL_PARAMCHGD()

◆ SCIPincludePricerColoring()