Assign random values to x_ij and consider the matrix as follows.
Hence it is a sum of multiples of 2^c* with c* optimal cost among perfect matchings. If optimal matching is unique then det is an odd multiple of 2^c* .
From det, c* can be computed by taking the largest power of 2 for which det is an odd multiple.