MinLCA algorithms
mip-model.hh
Go to the documentation of this file.
1 #ifndef __MINLCA_MINLCA_MIP_MODEL_HH
2 #define __MINLCA_MINLCA_MIP_MODEL_HH
3 
4 #include <vector>
5 #include <algorithm>
6 #include <utility>
7 #include <lemon/core.h>
8 #include <lemon/smart_graph.h>
9 #include <lemon/grb.h>
10 #include <utils/graph_utils.hh>
11 #include <minlca/optimisation.hh>
12 
13 
16 
17 namespace minlca
18 {
19 
29 template<typename Graph = lemon::SmartGraph>
30 class MinLCAOptMip : public MinLCAOpt<Graph>
31 {
32 protected:
33  TEMPLATE_GRAPH_TYPEDEFS(Graph);
34  typedef lemon::GrbMip Mip;
35 
36  typedef MinLCAOpt<Graph> Base;
37  using Base::_g;
38  using Base::_s;
39  using Base::_k;
40  using Base::_lca;
41  using Base::_max_k;
42  using Base::_c;
43 
44  std::vector<Mip::Col> _used_colours;
45  typename Graph::template NodeMap<vector<Mip::Col>>
47  typename Graph::template NodeMap<Mip::Expr> _vertex_c;
48  ;
49  typename Graph::template EdgeMap<Mip::Col>
50  _dist;
51  Mip::Expr _lca_expr;
52  Mip _model;
53 
54 public:
60  const Graph &g,
61  int maxK = 0,
62  bool vrb = false
63  )
64  : Base(g, maxK),
65  _used_colours(static_cast<size_t>(_max_k)),
67  _vertex_c(_g),
68  _dist(_g)
69  {
70  verbose(vrb);
71  }
72 
74  void verbose(
75  bool vrb = true
76  )
77  {
78  if (vrb) {
79  _model.getEnv().set(GRB_IntParam_LogToConsole, 1);
80  }
81  else {
82  _model.getEnv().set(GRB_IntParam_LogToConsole, 0);
83  }
84  }
85 
86  virtual void init()
87  {
88  _model.addColSet(_used_colours);
89 
90  for (NodeIt v(_g); v != lemon::INVALID; ++v) {
91  _vertex_colours[v] = vector<Mip::Col>(_max_k);
92  _model.addColSet(_vertex_colours[v]);
93  }
94 
95  _model.addColSet(_dist);
96 
97  _model.forceModelUpdate();
98 
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);
102  }
103 
104  _model.addRow(1, _used_colours[0], 1);
105 
106  for (NodeIt v(_g); v != lemon::INVALID; ++v) {
107  Mip::Expr oneColourPerVertex = 0;
108 
109  for (int c = 0; c < _max_k; ++c) {
110  Mip::Col &nodeColour = _vertex_colours[v][c];
111  _model.colType(nodeColour, Mip::INTEGER);
112  _model.colBounds(nodeColour, 0, 1);
113 
114  oneColourPerVertex += nodeColour;
115  _vertex_c[v] += c * nodeColour;
116  _model.addRow(nodeColour - _used_colours[c] <= 0.0);
117  }
118 
119  _vertex_c[v].simplify();
120  _model.addRow(1, oneColourPerVertex, 1);
121  }
122 
123  for (EdgeIt e(_g); e != lemon::INVALID; ++e) {
124  Node u = _g.u(e), v = _g.v(e);
125 
126  for (int c = 0; c < _max_k; ++c) {
127  _model.addRow(_vertex_colours[u][c] + _vertex_colours[v][c] <= 1);
128  }
129 
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]);
134 
135  _lca_expr += _dist[e];
136  }
137 
138  _model.min();
139  _model.obj(_lca_expr);
140 
141  _model.forceModelUpdate();
142  }
143 
145  void timeLimit(
146  double t
147  )
148  {
149  _model.getEnv().set(GRB_DoubleParam_TimeLimit, t);
150  }
151 
159  {
160  return _model;
161  }
162 
163  virtual MinLCAStatus run()
164  {
165  lemon::LpBase::SolveExitStatus status = _model.solve();
166 
167  int grbStatus = _model.getModel().get(GRB_IntAttr_Status);
168 
169  if (_model.type() == Mip::OPTIMAL
170  or (status == Mip::UNSOLVED and grbStatus == GRB_TIME_LIMIT)) {
171  _s = SOLUTION_FOUND;
172 
173  for (NodeIt v(_g); v != lemon::INVALID; ++v) {
174  this->setColour(v, static_cast<int>(_model.sol(_vertex_c[v])));
175  }
176  }
177  else {
179  }
180 
181  return this->status();
182  }
183 
184  virtual void initialSolution(const typename MinLCA<Graph>::Colouring &c)
185  {
186  for (NodeIt v(_g); v != lemon::INVALID; ++v) {
187  for (int i = 0; i < _max_k; ++i)
188  if (c[v] == i) {
189  _model.initialMipValue(_vertex_colours[v][i], 1);
190  }
191  else {
192  _model.initialMipValue(_vertex_colours[v][i], 0);
193  }
194  }
195 
196  _model.forceModelUpdate();
197  }
198 
204  // #lcaValue()
205  double getValue()
206  {
207  return _model.solValue();
208  }
209 };
210 }
211 
212 #endif
MinLCAStatus _s
The status of the solution.
Definition: base.hh:41
Header of the LEMON-Gurobi solver interface.
MinLCAOptMip(const Graph &g, int maxK=0, bool vrb=false)
Constructor.
Definition: mip-model.hh:59
virtual void setColour(const Node &v, int vColour)
Set the colour of a vertex.
Definition: base.hh:60
Graph::template EdgeMap< Mip::Col > _dist
Map of expressions to calculate the colour of a vertex.
Definition: mip-model.hh:48
virtual MinLCAStatus run()
Run the algorithm.
Definition: mip-model.hh:163
MinLCAStatus
Possible status for MinLCA solution.
Definition: base.hh:20
Mip::Expr _lca_expr
Expression with the objective function (the cost)
Definition: mip-model.hh:51
const Graph & _g
A const reference to the graph we want to arrange.
Definition: base.hh:36
Graph::template NodeMap< vector< Mip::Col > > _vertex_colours
Model variables for vertex colours.
Definition: mip-model.hh:46
int _k
Largest index of the colours used.
Definition: base.hh:37
Colouring _c
The vertex colouring.
Definition: base.hh:40
Solution has been found after running.
Definition: base.hh:22
Mip _model
The internal Mip (mixed integer programming) model.
Definition: mip-model.hh:52
Default namespace Default namespace for MinLCA algorithms.
Definition: base.hh:15
void forceModelUpdate()
Force model update.
Definition: grb.cc:71
Functions for reading graphs and getting graph properties.
int _max_k
Maximum number of colours allowed.
Definition: base.hh:38
GRBEnv getEnv() const
Get the environment of the underlying Gurobi model.
Definition: grb.cc:45
Class defining a relaxed linear programming model and algorithm for MinLCA.
Definition: mip-model.hh:30
Base class for defining optimisation MinLCA algorithms.
Definition: optimisation.hh:24
void verbose(bool vrb=true)
Change verbosity of Gurobi.
Definition: mip-model.hh:74
Solution has not been found after running.
Definition: base.hh:23
Defines the base class for MinLCA optimisation algorithms.
double getValue()
Retrieve the value of the objective function.
Definition: mip-model.hh:205
IntNodeMap Colouring
Type for graph colourings.
Definition: base.hh:33
lemon::GrbMip & model()
Retrieve the internal model.
Definition: mip-model.hh:158
Interface for the Gurobi MIP solver.
Definition: grb.h:307
std::vector< Mip::Col > _used_colours
Model variables for used colours.
Definition: mip-model.hh:44
MinLCAStatus status() const
Status of the solution.
Definition: base.hh:126
virtual void init()
Reset the data structures of the algorithm.
Definition: mip-model.hh:86
int maxK()
Maximum number of allowed colours.
Definition: base.hh:205
GRBModel & getModel()
Get the underlying Gurobi model.
Definition: grb.cc:55
void initialMipValue(LpBase::Col col, Value val)
Set initial value.
Definition: grb.cc:608
long long _lca
Cost of the current solution.
Definition: base.hh:39
void timeLimit(double t)
Set a time limit for Gurobi.
Definition: mip-model.hh:145
virtual void initialSolution(const typename MinLCA< Graph >::Colouring &c)
Set the initial solution for the algorithm.
Definition: mip-model.hh:184