branch_strongcoloring.h File Reference

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.h.

#include "scip/scip.h"
#include "probdata_coloring.h"
#include "cons_storeGraph.h"
#include "scip/cons_linear.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeBranchruleStrongcoloring (SCIP *scip)

Function Documentation

SCIPincludeBranchruleStrongcoloring()

SCIP_RETCODE SCIPincludeBranchruleStrongcoloring

(

SCIP *

scip

)

creates the coloring branching rule and includes it in SCIP

Parameters

scip	SCIP data structure

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