Scippy

SCIP

Solving Constraint Integer Programs

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

Macro Definition Documentation

◆ BRANCHRULE_NAME

#define BRANCHRULE_NAME   "coloring"

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

Function Documentation

◆ 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()

◆ SCIP_DECL_BRANCHEXECPS()

◆ SCIPincludeBranchruleColoring()

SCIP_RETCODE SCIPincludeBranchruleColoring ( SCIP scip)

creates the coloring branching rule and includes it in SCIP

Parameters
scipSCIP 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().