My favorite NP-complete cheat: You want to solve an integer programming problem, something like max sum_i x_i f_i Where the x_i are restricted to be binary.

My favorite NP-complete cheat: You want to solve an integer programming problem, something like max sum_i x_i f_i Where the x_i are restricted to be binary. The cheat: Just let the x_i be real numbers in the [0,1] interval, and solve the problem through a super-efficient linear programming solver. If you happen to end up with a solution where all the x_i are binary, you have successfully found a solution to the original problem. If you aren't so lucky, well... This is simple, fast, and works amazingly well amazingly often.