SCIP

Solving Constraint Integer Programs

branch_coloring.c File Reference

Detailed Description

default branching rule for the vertex coloring problem

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

#include <assert.h>
#include <string.h>
#include "branch_coloring.h"

Go to the source code of this file.

Macros

#define BRANCHRULE_NAME   "coloring"

#define BRANCHRULE_DESC   "branching rule template"

#define BRANCHRULE_PRIORITY   50000

#define BRANCHRULE_MAXDEPTH   -1

#define BRANCHRULE_MAXBOUNDDIST   1.0

Functions

static SCIP_DECL_BRANCHCOPY (branchCopyColoring)

static SCIP_DECL_BRANCHEXECLP (branchExeclpColoring)

static SCIP_DECL_BRANCHEXECPS (branchExecpsColoring)

SCIP_RETCODE SCIPincludeBranchruleColoring (SCIP *scip)

◆ BRANCHRULE_NAME

 #define BRANCHRULE_NAME   "coloring"

Definition at line 57 of file branch_coloring.c.

◆ BRANCHRULE_DESC

 #define BRANCHRULE_DESC   "branching rule template"

Definition at line 58 of file branch_coloring.c.

Referenced by SCIPincludeBranchruleColoring().

◆ BRANCHRULE_PRIORITY

 #define BRANCHRULE_PRIORITY   50000

Definition at line 59 of file branch_coloring.c.

Referenced by SCIPincludeBranchruleColoring().

◆ BRANCHRULE_MAXDEPTH

 #define BRANCHRULE_MAXDEPTH   -1

Definition at line 60 of file branch_coloring.c.

Referenced by SCIPincludeBranchruleColoring().

◆ BRANCHRULE_MAXBOUNDDIST

 #define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 61 of file branch_coloring.c.

Referenced by SCIPincludeBranchruleColoring().

◆ SCIP_DECL_BRANCHCOPY()

 static SCIP_DECL_BRANCHCOPY ( branchCopyColoring )
static

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

Definition at line 69 of file branch_coloring.c.

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

◆ SCIP_DECL_BRANCHEXECLP()

 static SCIP_DECL_BRANCHEXECLP ( branchExeclpColoring )
static

branching execution method for fractional LP solutions

Definition at line 80 of file branch_coloring.c.

◆ SCIP_DECL_BRANCHEXECPS()

 static SCIP_DECL_BRANCHEXECPS ( branchExecpsColoring )
static

branching execution method for not completely fixed pseudo solutions

Definition at line 279 of file branch_coloring.c.

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

Referenced by SCIPincludeColoringPlugins().