MinLCA algorithms
|
Class defining a relaxed linear programming model and algorithm for MinLCA. More...
#include <mip-model.hh>
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::GrbMip & | model () |
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... | |
![]() | |
TEMPLATE_GRAPH_TYPEDEFS (Graph) | |
MinLCAStatus | status () const |
Status of the solution. | |
const Colouring & | colouring () 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 |
![]() | |
typedef MinLCA< Graph > | Base |
Protected Member Functions | |
TEMPLATE_GRAPH_TYPEDEFS (Graph) | |
![]() | |
MinLCAOpt (const Graph &g, int maxK=0) | |
Constructor for derived classes to use. More... | |
![]() | |
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. | |
![]() | |
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 | |
![]() | |
typedef IntNodeMap | Colouring |
Type for graph colourings. | |
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.
Definition at line 30 of file mip-model.hh.
|
inline |
Constructor.
vrb | Show Gurobi output on console? |
Definition at line 59 of file mip-model.hh.
|
inline |
Retrieve the value of the objective function.
Definition at line 205 of file mip-model.hh.
|
inlinevirtual |
Reset the data structures of the algorithm.
Resets the data structures of the algorithm. Must be called before its execution with run().
Reimplemented from minlca::MinLCA< Graph >.
Definition at line 86 of file mip-model.hh.
|
inline |
Retrieve the internal model.
Definition at line 158 of file mip-model.hh.
|
inlinevirtual |
Run the algorithm.
Runs the algorithm and returns its status. Need to call init() before executing.
Reimplemented from minlca::MinLCA< Graph >.
Definition at line 163 of file mip-model.hh.
|
inline |
Set a time limit for Gurobi.
t | Time limit in seconds |
Definition at line 145 of file mip-model.hh.
|
inline |
Change verbosity of Gurobi.
vrb | Show Gurobi output on console? |
Definition at line 74 of file mip-model.hh.
|
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.