MinLCA algorithms
Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | List of all members
minlca::MinLCAOptMip< Graph > Class Template Reference

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

#include <mip-model.hh>

Inheritance diagram for minlca::MinLCAOptMip< Graph >:
[legend]
Collaboration diagram for minlca::MinLCAOptMip< Graph >:
[legend]

Public Member Functions

 MinLCAOptMip (const Graph &g, int maxK=0, bool vrb=false)
 Constructor. More...
 
void verbose (bool vrb=true)
 Change verbosity of Gurobi. More...
 
virtual void init ()
 Reset the data structures of the algorithm. More...
 
void timeLimit (double t)
 Set a time limit for Gurobi. More...
 
lemon::GrbMipmodel ()
 Retrieve the internal model. More...
 
virtual MinLCAStatus run ()
 Run the algorithm. More...
 
virtual void initialSolution (const typename MinLCA< Graph >::Colouring &c)
 Set the initial solution for the algorithm.
 
double getValue ()
 Retrieve the value of the objective function. More...
 
- Public Member Functions inherited from minlca::MinLCA< Graph >
 TEMPLATE_GRAPH_TYPEDEFS (Graph)
 
MinLCAStatus status () const
 Status of the solution.
 
const Colouringcolouring () const
 Current colouring. More...
 
int operator[] (const Node &v) const
 Colour of a vertex. More...
 
int operator[] (const Edge &e) const
 Cost of an edge. More...
 
long long lcaValue () const
 Value (cost) of the current solution. More...
 
int totalColours () const
 Total number of colours used. More...
 
long long recalculateLca ()
 Force a recalculation of the cost for the current solution. More...
 
int maxK ()
 Maximum number of allowed colours. More...
 

Protected Types

typedef lemon::GrbMip Mip
 
typedef MinLCAOpt< Graph > Base
 
- Protected Types inherited from minlca::MinLCAOpt< Graph >
typedef MinLCA< Graph > Base
 

Protected Member Functions

 TEMPLATE_GRAPH_TYPEDEFS (Graph)
 
- Protected Member Functions inherited from minlca::MinLCAOpt< Graph >
 MinLCAOpt (const Graph &g, int maxK=0)
 Constructor for derived classes to use. More...
 
- Protected Member Functions inherited from minlca::MinLCA< Graph >
void setSolutionNotFound ()
 Auxiliary function to set solution status to not found.
 
void setSolutionFound ()
 Auxiliary function to set solution status to found.
 
virtual void setColour (const Node &v, int vColour)
 Set the colour of a vertex. More...
 
 MinLCA (const Graph &g, int maxK=0)
 Constructor for derived classes to use. More...
 

Protected Attributes

std::vector< Mip::Col > _used_colours
 Model variables for used colours.
 
Graph::template NodeMap< vector< Mip::Col > > _vertex_colours
 Model variables for vertex colours.
 
Graph::template NodeMap< Mip::Expr > _vertex_c
 
Graph::template EdgeMap< Mip::Col > _dist
 Map of expressions to calculate the colour of a vertex. More...
 
Mip::Expr _lca_expr
 Expression with the objective function (the cost)
 
Mip _model
 The internal Mip (mixed integer programming) model.
 
- Protected Attributes inherited from minlca::MinLCA< Graph >
const Graph & _g
 A const reference to the graph we want to arrange.
 
int _k
 Largest index of the colours used.
 
int _max_k
 Maximum number of colours allowed.
 
long long _lca
 Cost of the current solution.
 
Colouring _c
 The vertex colouring.
 
MinLCAStatus _s
 The status of the solution.
 

Additional Inherited Members

- Public Types inherited from minlca::MinLCA< Graph >
typedef IntNodeMap Colouring
 Type for graph colourings.
 

Detailed Description

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

Class defining a relaxed linear programming model and algorithm 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 30 of file mip-model.hh.

Constructor & Destructor Documentation

template<typename Graph = lemon::SmartGraph>
minlca::MinLCAOptMip< Graph >::MinLCAOptMip ( const Graph &  g,
int  maxK = 0,
bool  vrb = false 
)
inline

Constructor.

See also
MinLCAGreedy::MinLCAGreedy(const Graph&, int)
MinLCA::MinLCA(const Graph&, int)
Parameters
vrbShow Gurobi output on console?

Definition at line 59 of file mip-model.hh.

Member Function Documentation

template<typename Graph = lemon::SmartGraph>
double minlca::MinLCAOptMip< Graph >::getValue ( )
inline

Retrieve the value of the objective function.

Returns
The value of the objective function
Note
This value should be the same as that obtained when calling

Definition at line 205 of file mip-model.hh.

template<typename Graph = lemon::SmartGraph>
virtual void minlca::MinLCAOptMip< Graph >::init ( )
inlinevirtual

Reset the data structures of the algorithm.

Resets the data structures of the algorithm. Must be called before its execution with run().

See also
run()

Reimplemented from minlca::MinLCA< Graph >.

Definition at line 86 of file mip-model.hh.

template<typename Graph = lemon::SmartGraph>
lemon::GrbMip& minlca::MinLCAOptMip< Graph >::model ( )
inline

Retrieve the internal model.

Warning
Modifying the model can lead to unexpected problems. Use at your own risk!
Note
Useful when trying to modify the Gurobi environment parameters.

Definition at line 158 of file mip-model.hh.

template<typename Graph = lemon::SmartGraph>
virtual MinLCAStatus minlca::MinLCAOptMip< Graph >::run ( )
inlinevirtual

Run the algorithm.

Runs the algorithm and returns its status. Need to call init() before executing.

Returns
Status of the solution
See also
init()

Reimplemented from minlca::MinLCA< Graph >.

Definition at line 163 of file mip-model.hh.

template<typename Graph = lemon::SmartGraph>
void minlca::MinLCAOptMip< Graph >::timeLimit ( double  t)
inline

Set a time limit for Gurobi.

Parameters
tTime limit in seconds

Definition at line 145 of file mip-model.hh.

template<typename Graph = lemon::SmartGraph>
void minlca::MinLCAOptMip< Graph >::verbose ( bool  vrb = true)
inline

Change verbosity of Gurobi.

Parameters
vrbShow Gurobi output on console?

Definition at line 74 of file mip-model.hh.

Member Data Documentation

template<typename Graph = lemon::SmartGraph>
Graph::template EdgeMap<Mip::Col> minlca::MinLCAOptMip< Graph >::_dist
protected

Map of expressions to calculate the colour of a vertex.

Map of expressions to calculate the cost of an edge

Definition at line 48 of file mip-model.hh.


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