Method TSP

examples/tsp.cpp:237–271

Actual model

public:
  /// Actual model
  TSP(const SizeOptions& opt)
    : IntMinimizeScript(opt),
      p(ps[opt.size()]),
      succ(*this, p.size(), 0, p.size()-1),
      total(*this, 0, p.max()) {
    int n = p.size();

    // Cost matrix
    IntArgs c(n*n, p.d());

    // Disallow disconnected nodes
    for (int i=0; i<n; i++)
      for (int j=0; j<n; j++)
        if (p.d(i,j) == 0)
          rel(*this, succ[i], IRT_NQ, j);

    // Cost of each edge
    IntVarArgs costs(*this, n, Int::Limits::min, Int::Limits::max);

    // Enforce that the successors yield a tour with appropriate costs
    circuit(*this, c, succ, costs, total, opt.ipl());

    // Just assume that the circle starts forwards
    {
      IntVar p0(*this, 0, n-1);
      element(*this, succ, p0, 0);
      rel(*this, p0, IRT_LE, succ[0]);
    }

    // First enumerate cost values, prefer those that maximize cost reduction
    branch(*this, costs, INT_VAR_REGRET_MAX_MAX(), INT_VAL_MIN());

    // Then fix the remaining successors
    branch(*this, succ,  INT_VAR_MIN_MIN(), INT_VAL_MIN());
  }
  /// Return solution cost
  virtual IntVar cost(void) const {
    return total;