branch_coloring.c File Reference

Detailed Description

default branching rule for the vertex coloring problem

Author

Gerald Gamrath

Julian Meffert

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 least/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
#define	BRANCHRULE_STRATEGIES   "ml"
#define	BRANCHRULE_STRATEGY_DEFAULT   'l'

Functions
static	SCIP_DECL_BRANCHEXECLP (branchExeclpColoring)
static	SCIP_DECL_BRANCHEXECPS (branchExecpsColoring)
static	SCIP_DECL_BRANCHCOPY (branchCopyColoring)
static	SCIP_DECL_BRANCHFREE (branchFreeColoring)
SCIP_RETCODE	SCIPincludeBranchruleColoring (SCIP *scip)

Macro Definition Documentation

BRANCHRULE_NAME

#define BRANCHRULE_NAME   "coloring"

Definition at line 58 of file branch_coloring.c.

BRANCHRULE_DESC

#define BRANCHRULE_DESC   "branching rule template"

Definition at line 59 of file branch_coloring.c.

BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY   50000

Definition at line 60 of file branch_coloring.c.

BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 61 of file branch_coloring.c.

BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 62 of file branch_coloring.c.

BRANCHRULE_STRATEGIES

#define BRANCHRULE_STRATEGIES   "ml"

possible variable selection strategies m=most fractional, l=least fractional

Definition at line 64 of file branch_coloring.c.

BRANCHRULE_STRATEGY_DEFAULT

#define BRANCHRULE_STRATEGY_DEFAULT   'l'

default variable selection strategy

Definition at line 65 of file branch_coloring.c.

Function Documentation

SCIP_DECL_BRANCHEXECLP()

static SCIP_DECL_BRANCHEXECLP ( branchExeclpColoring  )

static

branching execution method for fractional LP solutions

Definition at line 87 of file branch_coloring.c.

References BRANCHRULE_NAME, COLOR_CONSTYPE_DIFFER, COLOR_CONSTYPE_SAME, COLORconsGetActiveStoreGraphCons(), COLORconsGetCurrentGraph(), COLORconsGetRepresentative(), COLORcreateConsStoreGraph(), COLORprobGetConstraint(), COLORprobGetStableSet(), MIN, NULL, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIPABORT, SCIPaddConsNode(), SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPconsIsEnabled(), SCIPcreateChild(), SCIPgetLocalTransEstimate(), SCIPgetLPBranchCands(), SCIPgetNVarsSetppc(), SCIPgetVarsSetppc(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPreleaseCons(), SCIPvarGetData(), and SCIPvarGetUbLocal().

SCIP_DECL_BRANCHEXECPS()

static SCIP_DECL_BRANCHEXECPS ( branchExecpsColoring  )

static

branching execution method for not completely fixed pseudo solutions

Definition at line 316 of file branch_coloring.c.

References BRANCHRULE_NAME, COLOR_CONSTYPE_DIFFER, COLOR_CONSTYPE_SAME, COLORconsGetActiveStoreGraphCons(), COLORconsGetCurrentGraph(), COLORconsGetRepresentative(), COLORcreateConsStoreGraph(), COLORprobGetNNodes(), NULL, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPaddConsNode(), SCIPbranchruleGetName(), SCIPcreateChild(), SCIPgetLocalTransEstimate(), and SCIPreleaseCons().

SCIP_DECL_BRANCHCOPY()

static SCIP_DECL_BRANCHCOPY ( branchCopyColoring  )

static

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

Definition at line 386 of file branch_coloring.c.

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

SCIP_DECL_BRANCHFREE()

static SCIP_DECL_BRANCHFREE ( branchFreeColoring  )

static

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

Definition at line 398 of file branch_coloring.c.

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

SCIPincludeBranchruleColoring()

SCIP_RETCODE SCIPincludeBranchruleColoring

(

SCIP *

scip

)

creates the coloring branching rule and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 417 of file branch_coloring.c.

References BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, BRANCHRULE_STRATEGIES, BRANCHRULE_STRATEGY_DEFAULT, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddCharParam(), SCIPallocBlockMemory, SCIPincludeBranchruleBasic(), SCIPsetBranchruleCopy(), SCIPsetBranchruleExecLp(), SCIPsetBranchruleExecPs(), and SCIPsetBranchruleFree().

Referenced by SCIPincludeColoringPlugins().