lp-model.hh

Go to the documentation of this file.

#ifndef __MINLCA_MINLCA_LP_MODEL_HH
#define __MINLCA_MINLCA_LP_MODEL_HH

#include <vector>
#include <algorithm>
#include <utility>
#include <lemon/core.h>
#include <lemon/smart_graph.h>
#include <lemon/grb.h>
#include <utils/graph_utils.hh>


namespace minlca
{

template<typename Graph = lemon::SmartGraph>
class MinLCALpModel
{
protected:
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
  typedef lemon::GrbLp Lp;

  int _k; 
  std::vector<Lp::Col> _used_colours; 
  typename Graph::template NodeMap<vector<Lp::Col>>
  _vertex_colours; 
  typename Graph::template NodeMap<Lp::Expr>
  _vertex_c; 
  typename Graph::template EdgeMap<Lp::Col>
  _dist; 
  Lp::Expr _lca_expr; 
  Lp _model; 
public:
  MinLCALpModel(
    const Graph &g, 
    int maxK, 
    bool silent = true 
  )
    : _k(maxK),
      _used_colours(_k),
      _vertex_colours(g),
      _vertex_c(g),
      _dist(g)
  {
    if (silent) {
      _model.getEnv().set(GRB_IntParam_LogToConsole, 0);
    }
    else {
      _model.getEnv().set(GRB_IntParam_LogToConsole, 1);
    }

    _model.addColSet(_used_colours);

    for (NodeIt v(g); v != lemon::INVALID; ++v) {
      _vertex_colours[v] = vector<Lp::Col>(_k);
      _model.addColSet(_vertex_colours[v]);
    }

    _model.addColSet(_dist);

    _model.forceModelUpdate();

    for (int c = 0; c < _k; ++c) {
      _model.colBounds(_used_colours[c], 0, 1);
    }

    for (NodeIt v(g); v != lemon::INVALID; ++v) {
      Lp::Expr oneColourPerVertex = 0;

      for (int c = 0; c < _k; ++c) {
        Lp::Col &nodeColour = _vertex_colours[v][c];
        _model.colBounds(nodeColour, 0, 1);

        oneColourPerVertex += nodeColour;
        _vertex_c[v] += c * nodeColour;
        _model.addRow(nodeColour - _used_colours[c] <= 0);
      }

      _vertex_c[v].simplify();
      _model.addRow(1, oneColourPerVertex, 1);
    }

    for (EdgeIt e(g); e != lemon::INVALID; ++e) {
      Node u = g.u(e), v = g.v(e);

      for (int c = 0; c < _k; ++c) {
        _model.addRow(_vertex_colours[u][c] + _vertex_colours[v][c] <= 1);
      }

      _model.colBounds(_dist[e], 1, _k - 1);
      _model.addRow(_vertex_c[u] - _vertex_c[v] <= _dist[e]);
      _model.addRow(_vertex_c[v] - _vertex_c[u] <= _dist[e]);

      _lca_expr += _dist[e];
    }

    _model.min();
    _model.obj(_lca_expr);

    _model.forceModelUpdate();
  }

  double solve()
  {
    _model.solve();
    return _model.primal();
  }

  double getValue()
  {
    return _model.primal();
  }

  std::vector<int> getColourOrder(
    const Node &v 
  )
  {
    std::vector<std::pair<double, int>> colourAndPrecedence(_k);

    for (int c = 0; c < _k; ++c) {
      colourAndPrecedence[c] = std::make_pair(-_model.primal(_vertex_colours[v][c]),
                                              c);
    }

    std::sort(colourAndPrecedence.begin(), colourAndPrecedence.end());

    std::vector<int> colourOrder(_k);

    for (int i = 0; i < _k; ++i) {
      colourOrder[i] = colourAndPrecedence[i].second;
    }

    return colourOrder;
  }
};
}

#endif