1 #ifndef __MINLCA_MINLCA_MIP_MODEL_HH
2 #define __MINLCA_MINLCA_MIP_MODEL_HH
7 #include <lemon/core.h>
8 #include <lemon/smart_graph.h>
29 template<
typename Graph = lemon::SmartGraph>
33 TEMPLATE_GRAPH_TYPEDEFS(Graph);
45 typename Graph::template NodeMap<vector<Mip::Col>>
47 typename Graph::template NodeMap<Mip::Expr> _vertex_c;
49 typename Graph::template EdgeMap<Mip::Col>
65 _used_colours(static_cast<size_t>(
_max_k)),
79 _model.
getEnv().set(GRB_IntParam_LogToConsole, 1);
82 _model.
getEnv().set(GRB_IntParam_LogToConsole, 0);
88 _model.addColSet(_used_colours);
90 for (NodeIt v(
_g); v != lemon::INVALID; ++v) {
95 _model.addColSet(_dist);
99 for (
int c = 0; c <
_max_k; ++c) {
100 _model.colType(_used_colours[c], Mip::INTEGER);
101 _model.colBounds(_used_colours[c], 0, 1);
104 _model.addRow(1, _used_colours[0], 1);
106 for (NodeIt v(
_g); v != lemon::INVALID; ++v) {
107 Mip::Expr oneColourPerVertex = 0;
109 for (
int c = 0; c <
_max_k; ++c) {
111 _model.colType(nodeColour, Mip::INTEGER);
112 _model.colBounds(nodeColour, 0, 1);
114 oneColourPerVertex += nodeColour;
115 _vertex_c[v] += c * nodeColour;
116 _model.addRow(nodeColour - _used_colours[c] <= 0.0);
119 _vertex_c[v].simplify();
120 _model.addRow(1, oneColourPerVertex, 1);
123 for (EdgeIt e(
_g); e != lemon::INVALID; ++e) {
124 Node u =
_g.u(e), v =
_g.v(e);
126 for (
int c = 0; c <
_max_k; ++c) {
130 _model.colType(_dist[e], Mip::INTEGER);
131 _model.colBounds(_dist[e], 1, _max_k - 1);
132 _model.addRow(_vertex_c[u] - _vertex_c[v] <= _dist[e]);
133 _model.addRow(_vertex_c[v] - _vertex_c[u] <= _dist[e]);
135 _lca_expr += _dist[e];
139 _model.obj(_lca_expr);
149 _model.
getEnv().set(GRB_DoubleParam_TimeLimit, t);
165 lemon::LpBase::SolveExitStatus
status = _model.solve();
167 int grbStatus = _model.
getModel().get(GRB_IntAttr_Status);
169 if (_model.type() == Mip::OPTIMAL
170 or (status == Mip::UNSOLVED and grbStatus == GRB_TIME_LIMIT)) {
173 for (NodeIt v(
_g); v != lemon::INVALID; ++v) {
174 this->
setColour(v, static_cast<int>(_model.sol(_vertex_c[v])));
186 for (NodeIt v(
_g); v != lemon::INVALID; ++v) {
187 for (
int i = 0; i <
_max_k; ++i)
207 return _model.solValue();
MinLCAStatus _s
The status of the solution.
Header of the LEMON-Gurobi solver interface.
MinLCAOptMip(const Graph &g, int maxK=0, bool vrb=false)
Constructor.
virtual void setColour(const Node &v, int vColour)
Set the colour of a vertex.
Graph::template EdgeMap< Mip::Col > _dist
Map of expressions to calculate the colour of a vertex.
virtual MinLCAStatus run()
Run the algorithm.
MinLCAStatus
Possible status for MinLCA solution.
Mip::Expr _lca_expr
Expression with the objective function (the cost)
const Graph & _g
A const reference to the graph we want to arrange.
Graph::template NodeMap< vector< Mip::Col > > _vertex_colours
Model variables for vertex colours.
int _k
Largest index of the colours used.
Colouring _c
The vertex colouring.
Solution has been found after running.
Mip _model
The internal Mip (mixed integer programming) model.
Default namespace Default namespace for MinLCA algorithms.
void forceModelUpdate()
Force model update.
Functions for reading graphs and getting graph properties.
int _max_k
Maximum number of colours allowed.
GRBEnv getEnv() const
Get the environment of the underlying Gurobi model.
Class defining a relaxed linear programming model and algorithm for MinLCA.
Base class for defining optimisation MinLCA algorithms.
void verbose(bool vrb=true)
Change verbosity of Gurobi.
Solution has not been found after running.
Defines the base class for MinLCA optimisation algorithms.
double getValue()
Retrieve the value of the objective function.
IntNodeMap Colouring
Type for graph colourings.
lemon::GrbMip & model()
Retrieve the internal model.
Interface for the Gurobi MIP solver.
std::vector< Mip::Col > _used_colours
Model variables for used colours.
MinLCAStatus status() const
Status of the solution.
virtual void init()
Reset the data structures of the algorithm.
int maxK()
Maximum number of allowed colours.
GRBModel & getModel()
Get the underlying Gurobi model.
void initialMipValue(LpBase::Col col, Value val)
Set initial value.
long long _lca
Cost of the current solution.
void timeLimit(double t)
Set a time limit for Gurobi.
virtual void initialSolution(const typename MinLCA< Graph >::Colouring &c)
Set the initial solution for the algorithm.