Optimization Craft

# Progress Solving NP-Complete Problems

You do this every day:  You have three errands: Bakery, Library and Store.  You pick the order with the shortest travel distance (Store -> Bakery -> Library) or (Library -> Store -> Bakery), etc.  Congratulations:  You just solved the NP-Complete problem called “Traveling Salesman”.

Any NP-Complete problem can be solved by comparing all possible answers, and picking the best.  With three destinations, there are six answers to compare (abc, acb, bac, bca, cab, cba).  A human could compare all the answers for up to seven destinations.  A computer:  About 15 destinations.  With 60 destinations, there are more answers than there are atoms in the universe.   This kind of analysis leads many to classify NP-Complete problems as intractable.

Yet, a team in 2004 found the optimal tour of the 24,978 cities in Sweden with (only) 8 years of computation time.   In 2006, they cracked a 85,900 destination problem using 136 computer-years.  A plot of the history of these breakthroughs hints at a 10x improvement in solvable destinations every decade.  This is surprisingly good progress for an “intractable” problem.

Some of this improvement can be credited to faster and more abundant computers.  But, most comes from clever algorithms that eliminate sub-optimal answers without exhaustively checking them.

Can we declare victory?  In many fields, we can solve the NP-Complete problems that are important to everyday life.  That is why people make up fanciful problems like visiting all the cities in Sweden.  But, Integrated Circuit (IC) design presents real problems that remain past the reach of optimal algorithms.

For example,  ICs have millions of registers each placed at a different location on a rectangle of silicon.  IC designers must find an order to connect these registers in a chain using as little wire as possible.  (Oh, and they want an answer in a few minutes, not years.)  This is the same problem as finding the best order to visit cities, so IC optimality is beyond our reach for now.    In another decade or two, we’ll probably solve million destination problems, but then ICs will have 100s of millions of registers.  NP-Complete is not quite solved yet.

Traveling Salesman is one of many NP-Complete problems faced by IC design software every day.  At Synopsys, we solve some optimally, and others with close-to-optimum algorithms.  There’s fascinating work to increase the pool of problems we solve optimally and narrow the gap for problems we’ve not yet licked.   The work is both interesting and a good business because IC designers want the best possible ICs, and so will buy the software that delivers the best results.  Interested?

Share and Enjoy: