SCIL::SpanTree< Graph > Class Template Reference

The symbolic constraint for spanning trees. More...

#include <spantree.h>

Inheritance diagram for SCIL::SpanTree< Graph >:

[legend]

Collaboration diagram for SCIL::SpanTree< Graph >:

[legend]

List of all members.

Classes
class	st_cutset_inequality
Public Member Functions
	SpanTree (Graph &G_, var_map< edge_descriptor > &VM_)
void	init (subproblem &S)
status	standard_separation (subproblem &S)
status	feasible (solution &S)
void	min_cut (H_vertex u, property_map< bdGraph, edge_capacity_t >::type &C, property_map< bdGraph, edge_residual_capacity_t >::type &resC, property_map< bdGraph, vertex_reached_t >::type &R, int &k)
void	info ()

Detailed Description

template<typename Graph>
class SCIL::SpanTree< Graph >

This symbolic constraints takes as agruments an undirected graph G and a var_map<edge> X. X has to map every edge of the graph to a binary variable.

The feasible assignments of the symbolic constraint are those where the vector of the variables associated with the edges of the graph is an incidencevector of a spanning tree.

The symbolic constraint uses the cutting plane method, based on the well known subtour elimination formulation of spanning trees.

Definition at line 34 of file spantree.h.

Constructor & Destructor Documentation

template<typename Graph >

SpanTree::SpanTree	(	Graph &	G_,
		var_map< edge_descriptor > &	VM_
	)			`[inline]`

Ensures that the edges in X form a Spanning Tree.

Preconditions:

The variables associated to the edges are binary. Parameters:
SpanTree_Debug_Out true|false

Definition at line 66 of file spantree.cc.

Member Function Documentation

template<typename Graph >

SpanTree< Graph >::status SpanTree::feasible ( solution & S ) [inline, virtual]

Returns true if the induced graph is connected

Reimplemented from SCIL::sym_constraint.

Definition at line 234 of file spantree.cc.

References SCIL::subproblem::configuration(), and SCIL::solution::value().

template<typename Graph >

void SpanTree::info ( ) [inline, virtual]

Returns information on the symbolic constraints.

Reimplemented from SCIL::sym_constraint.

Definition at line 260 of file spantree.cc.

template<typename Graph >

void SpanTree::init ( subproblem & S ) [inline, virtual]

Adds the constraint $\sum_{e \in E} X_e = \| V \| -1$ for all $v \in V$ , to the LP.

Reimplemented from SCIL::sym_constraint.

Definition at line 87 of file spantree.cc.

References SCIL::subproblem::add_basic_constraint(), and SCIL::subproblem::configuration().

template<typename Graph >

void SpanTree::min_cut	(	H_vertex	u,
		property_map< bdGraph, edge_capacity_t >::type &	C,
		property_map< bdGraph, edge_residual_capacity_t >::type &	resC,
		property_map< bdGraph, vertex_reached_t >::type &	R,
		int &	k
	)			`[inline]`

Computes Minimum Cut

Definition at line 134 of file spantree.cc.

Referenced by SCIL::SpanTree< Graph >::standard_separation().

template<typename Graph >

SpanTree< Graph >::status SpanTree::standard_separation ( subproblem & S ) [inline, virtual]

Separates the subtour elimination constraints, i.e. $\sum_{e \in \gamma(S)} X_e \le \| \gamma \| -1$ for all $S \subset V$ , with an exact separation algorithm.

Reimplemented from SCIL::sym_constraint.

Definition at line 154 of file spantree.cc.

References SCIL::subproblem::add_basic_constraint(), SCIL::subproblem::configuration(), SCIL::SpanTree< Graph >::min_cut(), SCIL::row::normalize(), SCIL::row::size(), and SCIL::subproblem::value().

The documentation for this class was generated from the following files:

SCIL::SpanTree< Graph > Class Template Reference

Classes

Public Member Functions

Detailed Description

template<typename Graph> class SCIL::SpanTree< Graph >

Constructor & Destructor Documentation

Member Function Documentation

template<typename Graph>
class SCIL::SpanTree< Graph >