minlca::MinLCALpModel< Graph > Class Template Reference

Class defining a relaxed linear programming model for MinLCA. More...

#include <lp-model.hh>

Collaboration diagram for minlca::MinLCALpModel< Graph >:

Public Member Functions
	MinLCALpModel (const Graph &g, int maxK, bool silent=true)
	Constructor. More...
double	solve ()
	Solve the linear model. More...
double	getValue ()
	Retrieve the value of the objective function. More...
std::vector< int >	getColourOrder (const Node &v)
	Get the colour preference induced by the solution. More...

Protected Types
typedef lemon::GrbLp	Lp

Protected Member Functions
	TEMPLATE_GRAPH_TYPEDEFS (Graph)

Protected Attributes
int	_k
	Index of the largest colour.
std::vector< Lp::Col >	_used_colours
	Model variables for used colours.
Graph::template NodeMap< vector< Lp::Col > >	_vertex_colours
	Model variables for vertex colours.
Graph::template NodeMap< Lp::Expr >	_vertex_c
	Map of expressions to calculate the colour of a vertex.
Graph::template EdgeMap< Lp::Col >	_dist
	Map of expressions to calculate the cost of an edge.
Lp::Expr	_lca_expr
	Expression with the objective function (the cost)
Lp	_model
	The internal Lp model.

Detailed Description

template<typename Graph = lemon::SmartGraph>
class minlca::MinLCALpModel< Graph >

Class defining a relaxed linear programming model for MinLCA.

Read the report of Bachelor's Thesis Algorithms for the linear colouring arrangement problem for more information.

Note

This model adds variables and constraints in order to know explicitly which colours are used. These variables are superfluous and Gurobi solves the model without them, but they ease the later work.

Definition at line 27 of file lp-model.hh.

Constructor & Destructor Documentation

template<typename Graph = lemon::SmartGraph>

minlca::MinLCALpModel< Graph >::MinLCALpModel ( const Graph &  g, int  maxK, bool  silent = true  )

inline

Constructor.

Parameters

g	Graph for which to build the model
maxK	Maximum number of allowed colours
silent	Hide Gurobi output from console?

Definition at line 46 of file lp-model.hh.

Member Function Documentation

template<typename Graph = lemon::SmartGraph>

std::vector<int> minlca::MinLCALpModel< Graph >::getColourOrder ( const Node &  v )

inline

Get the colour preference induced by the solution.

Returns

The colour preference induced by the solution for the given vertex

See also

MinLCAGreedyLp

Parameters

v	Vertex for which we want the colour preferences

Definition at line 137 of file lp-model.hh.

template<typename Graph = lemon::SmartGraph>

double minlca::MinLCALpModel< Graph >::getValue ( )

inline

Retrieve the value of the objective function.

Returns

The value of the objective function

Definition at line 127 of file lp-model.hh.

template<typename Graph = lemon::SmartGraph>

double minlca::MinLCALpModel< Graph >::solve ( )

inline

Solve the linear model.

Returns

The value of the objective function

Definition at line 118 of file lp-model.hh.

---

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

• minlca/lp-model.hh