tsp_grb.cpp

Go to the documentation of this file.

 
#include <boost/program_options.hpp>
 
#include "qbpp.hpp"
#include "qbpp_grb.hpp"
#include "qbpp_misc.hpp"
#include "qbpp_tsp.hpp"
 
namespace po = boost::program_options;
 
class GRB_Callback : public qbpp_grb::Callback {
  const qbpp::tsp::TSPQuadModel &tsp_quad_model;
  std::optional<qbpp::energy_t> target_energy;
 
 public:
  GRB_Callback(const qbpp::tsp::TSPQuadModel &tsp_quad_model,
               qbpp::energy_t target_energy)
      : qbpp_grb::Callback(tsp_quad_model),
        tsp_quad_model(tsp_quad_model),
        target_energy(target_energy) {}
 
  void callback() override {
    if (where == GRB_CB_MIPSOL) {
      auto sol = get_sol();
      qbpp::tsp::TSPSol tsp_sol(tsp_quad_model, sol);
      std::cout << "TTS = " << std::fixed << std::setprecision(3)
                << std::setfill('0') << qbpp::get_time() << "s ";
      tsp_sol.print();
      if (target_energy.has_value() && sol.get_energy() <= target_energy) {
        abort();
      }
    }
  }
};
 
int main(int argc, char **argv) {
  // clang-format off
  po::options_description desc(
      "Solving the randomly generated TSP using QUBO++ Easy Solver");
  desc.add_options()("help,h", "produce help message")
     ("nodes,n", po::value<uint32_t>()->default_value(10),"set the number of nodes in the TSP map")
     ("time,t", po::value<uint32_t>()->default_value(10), "set time limit in seconds")
     ("tsp_seed,s", po::value<uint32_t>(), "set the random seed for the TSP map")
     ("output,o", po::value<std::string>(), "set the output file (png, svg, etc) to save the TSP solution")
     ("fix,f", "fix node 0 as the starting node");
  // clang-format on
 
  po::variables_map vm;
  try {
    po::store(po::parse_command_line(argc, argv, desc), vm);
  } catch (const std::exception &e) {
    std::cout << "Wrong arguments. Please use -h/--help option to see the "
                 "usage.\n";
    return 1;
  }
  po::notify(vm);
 
  if (vm.count("help")) {
    std::cout << desc << std::endl;
    return 0;
  }
 
  uint32_t nodes = vm["nodes"].as<uint32_t>();
  uint32_t time_limit = vm["time"].as<uint32_t>();
  bool fix_first = vm.count("fix");
 
  // Set the random seed for deterministic behavior if seed is provided.
  if (vm.count("tsp_seed")) {
    qbpp::misc::RandomGenerator::set_seed(vm["tsp_seed"].as<uint32_t>());
  } else {
    qbpp::misc::RandomGenerator::rd_seed();
  }
 
  std::cout << "Generating random TSP Map with " << nodes << " nodes"
            << std::endl;
  qbpp::tsp::TSPMap tsp_map;
  tsp_map.gen_random_map(nodes);
 
  std::cout << "Generating a TSP QUBO model" << std::endl;
  qbpp::tsp::TSPQuadModel tsp_quad_model(tsp_map, fix_first);
 
  std::cout << "Variables = " << tsp_quad_model.var_count()
            << " Linear Terms = " << tsp_quad_model.term_count(1)
            << " Quadratic Terms = " << tsp_quad_model.term_count(2)
            << std::endl;
 
  qbpp_grb::QuadModel grb_model(tsp_quad_model);
  grb_model.set_time_limit(time_limit);
  GRB_Callback grb_callback(tsp_quad_model, 0);
  grb_model.set(grb_callback);
 
  std::cout << "Solving the TSP" << std::endl;
  auto sol = grb_model.optimize();
 
  qbpp::tsp::TSPSol tsp_sol(tsp_quad_model, sol);
  tsp_sol.print();
 
  if (vm.count("output")) {
    qbpp::tsp::DrawSimpleGraph graph;
    for (uint32_t i = 0; i < nodes; ++i) graph.add_node(tsp_map[i]);
 
    for (uint32_t i = 0; i < nodes; ++i)
      graph.add_edge(tsp_sol[i], tsp_sol[(i + 1) % nodes]);
 
    graph.draw(vm["output"].as<std::string>());
  }
}