From: Kirt Undercoffer
Subject: Satisfiability program available, common lisp
Date:
Message-ID: <721425616.AA00000@blkcat.UUCP>
DP> I'm very interested in "in practice" kinds of instances. I wonder how
DP> hard the NP-complete instances that actually arise in areas outside of
DP> CS theory really are.
DP> If you'd like to trade "hard" instances, let me know.
A real project at the Department of Agriculture gave rise to the Traveling
Salesman Problem. The project was a dBase or Clipper implementation of a
varient of TSP - given n people and x locations and z,c,v constraints what is
the optimum path during their day they need to take to visit a series of points?
Even with a realtively low number of constraints this problem was practically
unsolveable as originally formulated (obviously - the program churned for three
days or so to produce a path for one person - later the problem was
simplified).