RhodeCode

#include <iostream>

#include <lemon/lp.h>

#include <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include <utility>

#include <fstream>

#include <string>

#include <vector>

#include <iterator>

#include <map>

using namespace lemon;

using namespace std;

//LP(opt)/IP(opt)

double IP_gap(lemon::ListGraph & g,

	      lemon::ListGraph::NodeMap < int > & set) {

  Mip mip;

  //column

  lemon::ListGraph::EdgeMap < Mip::Col > x(g);

  for (lemon::ListGraph::EdgeIt e(g); e != lemon::INVALID; ++e) {

    Mip::Col xi = mip.addCol();

    x[e] = xi;

  }

  //row

  for (lemon::ListGraph::NodeIt v(g); v != lemon::INVALID; ++v) {

    if (set[v] == -1) {

      Mip::Expr exprS1;

      Mip::Expr exprS2;

      for (lemon::ListGraph::IncEdgeIt e(g, v); e != lemon::INVALID; ++e) {

        if (set[g.oppositeNode(v, e)] == 1) {

          exprS1 += x[e];

        }

        if (set[g.oppositeNode(v, e)] == 2) {

          exprS2 += x[e];

        }

        if (set[g.oppositeNode(v, e)] == 0) {

          exprS1 += x[e];

          exprS2 += x[e];

        }

      }

      mip.addRow(exprS1 <= 1);

      mip.addRow(exprS2 <= 1);

    }

    else {

      Mip::Expr expr;

      for (lemon::ListGraph::IncEdgeIt e(g, v); e != lemon::INVALID; ++e) {

        expr += x[e];

      }

      mip.addRow(expr <= 1);

    }

  }

  //solve IP

  double ip;

  mip.max();

  Mip::Expr sum_ip;

  for (lemon::ListGraph::EdgeIt e(g); e != lemon::INVALID; ++e) {

    mip.colType(x[e], Mip::INTEGER);

    mip.colLowerBound(x[e], 0);

    mip.colUpperBound(x[e], 1);

    sum_ip += x[e];

  }

  mip.obj(sum_ip);

  mip.solve();

  if (mip.type() == Mip::OPTIMAL) {

    ip = mip.solValue();

  }

  else {

    ip = -1;

  }

  //solve LP

  double lp;

  mip.max();

  Mip::Expr sum_lp;

  for (lemon::ListGraph::EdgeIt e(g); e != lemon::INVALID; ++e) {

    mip.colType(x[e], Mip::REAL);

    mip.colLowerBound(x[e], 0);

    mip.colUpperBound(x[e], 1);

    sum_lp += x[e];

  }

  mip.obj(sum_lp);

  mip.solve();

  if (mip.type() == Mip::OPTIMAL) {

    lp = mip.solValue();

  }

  else {

    lp = 0;

  }

  //calculate gap

  double gap = lp / ip;

  if (gap > 0) {

    return gap;

  }

  else {

    return 0;

  }

}

//IP gap for partition(k)

double k_to_IP_gap(lemon::ListGraph & g,

		   lemon::ListGraph::NodeMap < int > & STmap,

		   int l,

		   int p,

		   int firstnode,

		   int G) {

  //create partition

  bool b = 1; //not seen any nodes in S

  lemon::ListGraph::NodeMap < int > set(g); //1:S1, 2:S2, 0:S1,S2, -1:T

  lemon::ListGraph::Node first = g.nodeFromId(0);

  for (int j = 0; j < G; j++) {

    lemon::ListGraph::Node n = g.nodeFromId(j);

    if (STmap[n] == 1) {

      if (b == 0) {

        int x = l / p;

        set[n] = x;

        l = l - x * p;

        p = p / 3;

      }

      if (b == 1) {

        first = n;

        b = 0; //seen the first node in S

      }

    }

    else {

      set[n] = -1;

    }

  }

  //first node in firstnode(=0,1)

  set[first] = firstnode;

  //calculate gap

  double gap = IP_gap(g, set);

  return gap;

}

int main() {

  //variables for maximum search

  double max = 0; //max value

  int max_first = 0; //where is the first node (0,1)

  int max_k = 0; //partition

  std::string max_graph; //graph's line

  int cnt = 0; //line counter

  //input

  std::string line;

  istream & f = std::cin;

  //graph parameters

  int N = 7; // |S|

  int G = 11; // |V(g)|

  //calculate greatest and pow

  int greatest = 0; //the greatest number of N-1 digits in ternary number system

  int pow = 1; //3^(N-2)

  for (int i = 0; i < N - 1; i++) {

    greatest += 2 * pow;

    pow = pow * 3;

  }

  pow = pow / 3;

  //read

  while (std::getline(std::cin, line)) {

    std::vector < std::string > lines;

    lines.push_back(line);

    for (int i = 0; i < 10000 && std::getline(std::cin, line); ++i) {

      lines.push_back(line);

    }

    //parallel

    #pragma omp parallel for schedule(dynamic, 1)

    for (int i = 0; i < lines.size(); ++i) {

      std::string line = lines[i];

      lemon::ListGraph g;

      lemon::ListGraph::NodeMap < int > STmap(g); //1:S, 0:T

      lemon::ListGraph::Node n;

      //create STmap

      for (int i = 0; i < G; i++) {

        n = g.addNode();

        if (i < N) {

          STmap[n] = 1; //set S

        }

	else {

          STmap[n] = 0; //set T

        }

      }

      //create g

      lemon::ListGraph::Node v = g.nodeFromId(N);

      int i = 0;

      while (line[i] != '.') {

        if (line[i] == ',') {

          v = g.nodeFromId(g.id(v) + 1);

        } else {

          g.addEdge(v, g.nodeFromId(line[i] - '1'));

        }

        i++;

      }

      //k_to_IP_gap for k=0..greatest and maximum search

      #pragma omp critical

      std::cout << ++cnt << std::endl;

      for (int k = 0; k < greatest + 1; k++) {

	//maximum search

        double gap = k_to_IP_gap(g, STmap, k, pow, 0, G); //set[first node]=0

        if (gap > max) {

          max = gap;

          max_k = k;

          max_first = 0;

          max_graph = line;

          std::cout << "max: " << max << std::endl;

          std::cout << "max_graph: " << max_graph << std::endl;

          std::cout << "max_first: " << max_first << std::endl;

          std::cout << "max_k: " << max_k << std::endl;

        }

        gap = k_to_IP_gap(g, STmap, k, pow, 1, G); //set[first node]=1

        if (gap > max) {

          max = gap;

          max_k = k;

          max_first = 1;

          max_graph = line;

          std::cout << "max: " << max << std::endl;

          std::cout << "max_graph: " << max_graph << std::endl;

          std::cout << "max_first: " << max_first << std::endl;

          std::cout << "max_k: " << max_k << std::endl;

        }

      }

    }

  }

  //print the answer

  std::cout << "max: " << max << std::endl;

  std::cout << "max_graph: " << max_graph << std::endl;

  std::cout << "max_first: " << max_first << std::endl;

  std::cout << "max_k: " << max_k << std::endl;

  return 0;

}

binaries = 	gap

#path of CPLEX

CPLEXDIR   = /opt/ibm/ILOG/CPLEX_Studio1263/cplex

#path of CPLEX concert

CONCERTDIR = /opt/ibm/ILOG/CPLEX_Studio1263/concert

#cpp compiler

CCC = g++

EXTRAFLAGS = -fopenmp

CCOPT = -O4 -fPIC -fno-strict-aliasing -fexceptions \

	-march=native -funroll-loops -std=c++11 -DNDEBUG -DIL_STD

LFLAGS = -L$(CPLEXDIR)/lib/x86-64_linux/static_pic/ \

	 -L$(CONCERTDIR)/lib/x86-64_linux/static_pic/

IFLAGS = -I$(CPLEXDIR)/include -I$(CONCERTDIR)/include

LIBFLAGS = -lemon -lconcert -lilocplex -lcplex -lm -ldl -lpthread 

.PHONY: all clean

all:	$(binaries)

%: %.cc

	$(CCC) $(CCOPT) $(IFLAGS) $(LFLAGS) -o$@ $< $(LIBFLAGS) $(EXTRAFLAGS)

dm2: locOptDM.h

clean:

	rm -f $(binaries) *.o

	rm -f $(binaries) *.d

-include *.d