Detailed Description

branching rule performing strong branching for the vertex coloring problem

Author: Gerald Gamrath

This file implements an additional branching rule for the coloring algorithm.

We are looking for two nodes v and w, which are not adjacent in the current graph, and consider the following two constraints: SAME(v,w) and DIFFER(v,w). More information about the meaning of these constraints can be found in the documentation of the branching rule in branch_coloring.c.

This branching rule puts some more effort into the choice of the two nodes and performs a strongbranching. This means that for every possible choice of two nodes, it solves the LPs of the created children and computes a score with respect to the increase of the lower bound in both nodes. After that, it takes the combination of nodes yielding the best score. The interesting point is that the strongbranching is not performed for each variable, as it is done in some default branching rules of SCIP and supported by the LP-solver, but is done for a constraint, since we are branching on constraints. Look at executeStrongBranching() to see how it is done. There are also some improvements, since testing all possible combination of nodes is very expensive. The first possibility to avoid this is to stop the computation of scores once a possible branching is found that has only one feasible child. This results in more restrictions in this child without increasing the number of unprocessed nodes.

The second improvement is to compute a priority for all possible combinations, w.r.t. the fractional values of the variables. Then, only the first best k combinations are investigated by strongbranching.

This code is not optimized and in most cases inferior to the standard branching rule. It is only a demonstration of how to perform strongbranching on constraints!

Definition in file branch_strongcoloring.c.

#include <assert.h>
#include <string.h>
#include "branch_strongcoloring.h"
#include "pricer_coloring.h"

Go to the source code of this file.

Macros
#define	BRANCHRULE_NAME "strongcoloring"

#define	BRANCHRULE_DESC "branching rule template"

#define	BRANCHRULE_PRIORITY 15000

#define	BRANCHRULE_MAXDEPTH -1

#define	BRANCHRULE_MAXBOUNDDIST 1.0

#define	DEFAULT_BRANCHINGMODE 2

#define	DEFAULT_FIXINGSSCOREMODE 3

#define	DEFAULT_MAXPRICINGROUNDS -1

#define	DEFAULT_USETCLIQUE TRUE

#define	DEFAULT_LOOKAHEAD 10

Functions
static double	computeScore (SCIP_Real val1, SCIP_Real val2)

static SCIP_Real	computeFixingsScore (SCIP_Real samevalue, SCIP_Real differvalue, SCIP_BRANCHRULEDATA *branchruledata)

static int	nodes2index (SCIP *scip, int node1, int node2)

static void	index2nodes (SCIP scip, int ind, int node1, int *node2)

static SCIP_RETCODE	computeBranchingPriorities (SCIP scip, SCIP_BRANCHRULEDATA branchruledata)

static SCIP_RETCODE	executeStrongBranching (SCIP scip, COLOR_CONSTYPE constype, int node1, int node2, SCIP_BRANCHRULEDATA branchruledata, SCIP_Real *newlb)

static	SCIP_DECL_SORTINDCOMP (consdataCompValues)

static	SCIP_DECL_BRANCHCOPY (branchCopyStrongcoloring)

static	SCIP_DECL_BRANCHEXECLP (branchExeclpStrongcoloring)

static	SCIP_DECL_BRANCHFREE (branchFreeStrongcoloring)

static	SCIP_DECL_BRANCHINIT (branchInitStrongcoloring)

static	SCIP_DECL_BRANCHEXIT (branchExitStrongcoloring)

SCIP_RETCODE	SCIPincludeBranchruleStrongcoloring (SCIP *scip)

Macro Definition Documentation

◆ BRANCHRULE_NAME

#define BRANCHRULE_NAME "strongcoloring"

Definition at line 53 of file branch_strongcoloring.c.

Referenced by SCIP_DECL_BRANCHCOPY(), SCIP_DECL_BRANCHEXECLP(), and SCIPincludeBranchruleStrongcoloring().

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC "branching rule template"

Definition at line 54 of file branch_strongcoloring.c.

Referenced by SCIPincludeBranchruleStrongcoloring().

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY 15000

Definition at line 55 of file branch_strongcoloring.c.

Referenced by SCIPincludeBranchruleStrongcoloring().

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH -1

Definition at line 56 of file branch_strongcoloring.c.

Referenced by SCIPincludeBranchruleStrongcoloring().

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST 1.0

Definition at line 57 of file branch_strongcoloring.c.

Referenced by SCIPincludeBranchruleStrongcoloring().

◆ DEFAULT_BRANCHINGMODE

#define DEFAULT_BRANCHINGMODE 2

Definition at line 60 of file branch_strongcoloring.c.

Referenced by SCIPincludeBranchruleStrongcoloring().

◆ DEFAULT_FIXINGSSCOREMODE

#define DEFAULT_FIXINGSSCOREMODE 3

Definition at line 61 of file branch_strongcoloring.c.

Referenced by SCIPincludeBranchruleStrongcoloring().

◆ DEFAULT_MAXPRICINGROUNDS

#define DEFAULT_MAXPRICINGROUNDS -1

Definition at line 62 of file branch_strongcoloring.c.

Referenced by SCIPincludeBranchruleStrongcoloring().

◆ DEFAULT_USETCLIQUE

#define DEFAULT_USETCLIQUE TRUE

Definition at line 63 of file branch_strongcoloring.c.

Referenced by SCIPincludeBranchruleStrongcoloring().

◆ DEFAULT_LOOKAHEAD

#define DEFAULT_LOOKAHEAD 10

Definition at line 64 of file branch_strongcoloring.c.

Referenced by SCIPincludeBranchruleStrongcoloring().

Function Documentation

◆ computeScore()

static double computeScore	(	SCIP_Real	val1,
		SCIP_Real	val2
	)

static

computes a score for the two improvements that are achieved in the two sons for a branching decision

Parameters

val1	the first value
val2	the second value

Definition at line 99 of file branch_strongcoloring.c.

References MAX.

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ computeFixingsScore()

static SCIP_Real computeFixingsScore	(	SCIP_Real	samevalue,
		SCIP_Real	differvalue,
		SCIP_BRANCHRULEDATA *	branchruledata
	)

static

computes a score for the fractional values of the variables that would be fixed to zero for a same- or differ-branching

Parameters

samevalue	value of the fractional variables fixed to 0 for a same-branching
differvalue	value of the fractional variables fixed to 0 for a differ-branching
branchruledata	branching rule data

Definition at line 109 of file branch_strongcoloring.c.

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ nodes2index()

static int nodes2index	(	SCIP *	scip,
		int	node1,
		int	node2
	)

static

for given nodes node1, node2, compute the corresponding index in the arrays branchruledata->same-/differvalue

Parameters

scip	SCIP data structure
node1	the first node
node2	the second node

Definition at line 138 of file branch_strongcoloring.c.

References COLORprobGetNNodes(), nnodes, and NULL.

Referenced by computeBranchingPriorities().

◆ index2nodes()

static void index2nodes	(	SCIP *	scip,
		int	ind,
		int *	node1,
		int *	node2
	)

static

for given index of the arrays branchruledata->same-/differvalue, compute the two nodes, the index represents

Parameters

scip	SCIP data structure
ind	the given index in the arrays
node1	return value: the first node
node2	return value: the second node

Definition at line 169 of file branch_strongcoloring.c.

References COLORprobGetNNodes(), nnodes, and NULL.

Referenced by computeBranchingPriorities(), and SCIP_DECL_BRANCHEXECLP().

◆ computeBranchingPriorities()

static SCIP_RETCODE computeBranchingPriorities	(	SCIP *	scip,
		SCIP_BRANCHRULEDATA *	branchruledata
	)

static

computes for each pair of nodes (i,j) two values, one for same (i,j), the other for differ(i,j) which are the sum of the values of variables with fractional parts, that would be fixed for this decision asd

Parameters

scip	SCIP data structure
branchruledata	the data of the branching rule

Definition at line 197 of file branch_strongcoloring.c.

References COLORconsGetCurrentGraph(), COLORconsGetRepresentative(), COLORprobGetNNodes(), COLORprobGetStableSet(), COLORprobIsNodeInStableSet(), index2nodes(), nnodes, nodes2index(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetLPBranchCands(), SCIPisFeasPositive(), and SCIPvarGetData().

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ executeStrongBranching()

static SCIP_RETCODE executeStrongBranching	(	SCIP *	scip,
		COLOR_CONSTYPE	constype,
		int	node1,
		int	node2,
		SCIP_BRANCHRULEDATA *	branchruledata,
		SCIP_Real *	newlb
	)

static

computes the lower bound that would a child node with the given branching decision would have

Parameters

scip	SCIP data structure
constype	the type of the contraint: SAME or DIFFER
node1	the first node for the branching constraint
node2	the second node for the branching constraint
branchruledata	the data of the branching rule
newlb	pointer to store the resulting value

Definition at line 307 of file branch_strongcoloring.c.

References COLORconsGetActiveStoreGraphCons(), COLORcreateConsStoreGraph(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddConsNode(), SCIPdelCons(), SCIPendProbing(), SCIPgetCurrentNode(), SCIPgetLPObjval(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPreleaseCons(), SCIPsolveProbingLPWithPricing(), and SCIPstartProbing().

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ SCIP_DECL_SORTINDCOMP()

static SCIP_DECL_SORTINDCOMP ( consdataCompValues )

static

index comparison method two values in a real array

Definition at line 355 of file branch_strongcoloring.c.

References NULL, and SCIP_Real.

◆ SCIP_DECL_BRANCHCOPY()

static SCIP_DECL_BRANCHCOPY ( branchCopyStrongcoloring )

static

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

Definition at line 381 of file branch_strongcoloring.c.

References BRANCHRULE_NAME, NULL, SCIP_OKAY, and SCIPbranchruleGetName().

◆ SCIP_DECL_BRANCHEXECLP()

static SCIP_DECL_BRANCHEXECLP ( branchExeclpStrongcoloring )

static

branching execution method for fractional LP solutions

Definition at line 393 of file branch_strongcoloring.c.

References BMSclearMemoryArray, BRANCHRULE_NAME, COLOR_CONSTYPE_DIFFER, COLOR_CONSTYPE_SAME, COLORconsGetActiveStoreGraphCons(), COLORconsGetCurrentGraph(), COLORconsGetRepresentative(), COLORcreateConsStoreGraph(), COLORprobGetNNodes(), computeBranchingPriorities(), computeFixingsScore(), computeScore(), executeStrongBranching(), FALSE, index2nodes(), nnodes, NULL, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIPaddConsNode(), SCIPallocBufferArray, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPcreateChild(), SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLocalTransEstimate(), SCIPgetLPObjval(), SCIPisFeasZero(), SCIPisSumNegative(), SCIPreleaseCons(), SCIPsetBoolParam(), SCIPsort(), and TRUE.

◆ SCIP_DECL_BRANCHFREE()

static SCIP_DECL_BRANCHFREE ( branchFreeStrongcoloring )

static

destructor of branching rule to free user data (called when SCIP is exiting)

Definition at line 675 of file branch_strongcoloring.c.

References NULL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleSetData(), and SCIPfreeBlockMemory.

◆ SCIP_DECL_BRANCHINIT()

static SCIP_DECL_BRANCHINIT ( branchInitStrongcoloring )

static

initialization method of branching rule (called after problem was transformed)

Definition at line 689 of file branch_strongcoloring.c.

References COLORprobGetNNodes(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, and SCIPbranchruleGetData().

◆ SCIP_DECL_BRANCHEXIT()

static SCIP_DECL_BRANCHEXIT ( branchExitStrongcoloring )

static

deinitialization method of branching rule (called before transformed problem is freed)

Definition at line 709 of file branch_strongcoloring.c.

References NULL, SCIP_OKAY, SCIPbranchruleGetData(), and SCIPfreeBlockMemoryArray.

◆ SCIPincludeBranchruleStrongcoloring()

SCIP_RETCODE SCIPincludeBranchruleStrongcoloring ( SCIP * scip )

creates the coloring branching rule and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 731 of file branch_strongcoloring.c.

References BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, DEFAULT_BRANCHINGMODE, DEFAULT_FIXINGSSCOREMODE, DEFAULT_LOOKAHEAD, DEFAULT_MAXPRICINGROUNDS, DEFAULT_USETCLIQUE, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocBlockMemory, SCIPincludeBranchruleBasic(), SCIPsetBranchruleCopy(), SCIPsetBranchruleExecLp(), SCIPsetBranchruleExit(), SCIPsetBranchruleFree(), SCIPsetBranchruleInit(), and TRUE.

Referenced by SCIPincludeColoringPlugins().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ BRANCHRULE_NAME

◆ BRANCHRULE_DESC

◆ BRANCHRULE_PRIORITY

◆ BRANCHRULE_MAXDEPTH

◆ BRANCHRULE_MAXBOUNDDIST

◆ DEFAULT_BRANCHINGMODE

◆ DEFAULT_FIXINGSSCOREMODE

◆ DEFAULT_MAXPRICINGROUNDS

◆ DEFAULT_USETCLIQUE

◆ DEFAULT_LOOKAHEAD

Function Documentation

◆ computeScore()

◆ computeFixingsScore()

◆ nodes2index()

◆ index2nodes()

◆ computeBranchingPriorities()

◆ executeStrongBranching()

◆ SCIP_DECL_SORTINDCOMP()

◆ SCIP_DECL_BRANCHCOPY()

◆ SCIP_DECL_BRANCHEXECLP()

◆ SCIP_DECL_BRANCHFREE()

◆ SCIP_DECL_BRANCHINIT()

◆ SCIP_DECL_BRANCHEXIT()

◆ SCIPincludeBranchruleStrongcoloring()