branch_coloring.h File Reference

Detailed Description

default branching rule for the vertex coloring problem

Author

Gerald Gamrath

This file implements the standard branching rule for the coloring algorithm.

As we use column generation, we may not branch on the variables themselves, but on some sort of constraints that we introduce in the pricing problem.

In our case, we choose 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). SAME(v,w) requires that both nodes v and w get the same color, whereas DIFFER(v,w) forbids this. For each pair of nodes, each feasible solution fulfills exactly one of these constraints. Hence, splitting the solution space into two parts, one fulfilling SAME(v,w) and the other DIFFER(v,w), does not cut off any feasible solution and can therefore be used as the branching rule.

The branching is done as follows: Given the optimal (fractional) solution of the current branch-and-bound node, choose the most fractional variable and the corresponding stable set s1. Now choose two nodes v, w and another stable set s2, such that v is part of both stable sets, whereas w is part of exactly one of the stable sets. Create two children of the current node, one with the restriction SAME(v,w), the other one with restriction DIFFER(v,w). Therefore, each node gets a constraint of type cons_storeGraph, which enforces the branching decision and assures that each coloring of the nodes in the respective subgraph assigns to both nodes the same color/different colors by fixing stable sets to 0 that violate this constraint.

Definition in file branch_coloring.h.

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

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeBranchruleColoring (SCIP *scip)

Function Documentation

SCIPincludeBranchruleColoring()

SCIP_RETCODE SCIPincludeBranchruleColoring

(

SCIP *

scip

)

creates the coloring branching rule and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 351 of file branch_coloring.c.

References BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeBranchruleBasic(), SCIPsetBranchruleCopy(), SCIPsetBranchruleExecLp(), and SCIPsetBranchruleExecPs().

Referenced by SCIPincludeColoringPlugins().