From: Lou Vanek Date: 2006-02-08T22:36:01+09:00 Subject: [ANN] NP If anybody else finds NP-complete problems interesting then you may want to check out my new Ruby extension. You can find the extension, ext_np, at http://rubyforge.org/frs/?group_id=835 The description follows in the README. This extension is wicked fast. -lv ---------------------------------------------------------------------------- README.txt This extension, 'NP,' is a module for the Ruby language. It includes four optimized NP-complete algorithms: o Multiple Knapsack 0-1 o Subset Sum o Symmetric Subset Sum o Satisfiability (SAT) The extension is written in two languages, C and C++, and results in a shared library called NP.so. This library can be linked into any Ruby program once it's referenced in the usual way: ruby -rNP -e "NP::subset_sum( ... )" or #!/usr/bin/env ruby require 'NP' a,b = NP::subset_sum([1,3,5,7,9],11) puts a puts b.inspect INSTALL See INSTALL.txt. There is no short way to explain installation (there are three build directories, and both a C and C++ compiler will have to be fired up via makefiles). LICENSE See LICENSE.txt, and the licenses included at the top of the source code. The short answer: this software cannot be used for commercial use. REQUIREMENTS - ruby 1.8.4 - C and C++ compilers - unixy platform with standard, unixy software utilities (Cygwin is OK, too. Would love to hear about OS X.) - moderate proficiency in makefiles TESTING In the np directory, run 'ruby test.rb'. USAGE Usage is described for each of the four algorithms. 1. Multiple Knapsack 0-1 Can n items be stuffed into m knapsacks, where each knapsack has capacity c_j, each item has weight w_i and profit p_i. Maximize profit, and don't carry items that cumulatively weigh more than any knapsack's capacity. You may stuff only up to 1 item in any one knapsack (some knapsack problems allow you to stuff an unlimited supply). Example: What is an optimal method of stuffing 2 knapsacks with 7 items which weigh 1,2,3,4,5,6,7 and have, respectively, profit 1,2,3,4,7,7,8? >ruby -rNP -e "a,b = NP::mulknap([1,2,3,4,5,6,7],[1,2,3,4,7,7,8],[7,8]); puts a; puts b.inspect" 18 [1, 0, 2, 0, 2, 1, 0] This answer is saying that a total profit of 18 is obtained by stuffing, item 1 into knapsack 1 item 3 into knapsack 2 item 5 into knapsack 2 item 6 into knapsack 1 into two knapsacks having capacities 7 and 8. Note there is more than one optimal answer to this problem, but they have the same maximal profit. Also note that the capacities array ([7,8] above) should be sorted from lowest to highest capacity. This algorithm can also be used with only 1 knapsack. This algorithm could be used to assign n tasks to m machines for even load distribution. 2. Subset Sum Is there a subset of n numbers such that the subset adds to x? Example: >ruby -rNP -e "a,b = NP::subset_sum([3,4,7,11,6,5],23); puts a; puts b.inspect" true [1, 1, 0, 1, 0, 1] This answer indicates that, indeed, the numbers 3,4,7,11,6,5 can be partitioned such that a subset adds to 23: 3 + 4 + 11 + 5 = 23 (i.e., items 1,2,4, and 6, as shown in the returned bit array) Valid domains (for most 32-bit machines): Target sum: 1,2,...,(2**31) - 1 Individual item weights: 1,2,...,(2**15) - 1 (note: items weighing less than 1 will be ignored) 3. Symmetric Subset Sum Can a set of n numbers be divided evenly into x subsets such that each subset sums to a common (previously undetermined) number? Example 1: >ruby -rNP -e "a,b = NP::symmetric_subset_sum([1,2,3,4,5,6,7,8,9],3); puts a.inspect; puts b.inspect" [15, 15, 15] [3, 3, 3, 3, 3, 2, 1, 1, 2] The numbers 1,2,3,4,5,6,7,8,9 may be partitioned into three subsets such that their sums all equal 15. partition 1: 7 + 8 = 15 partition 2: 9 + 6 = 15 partition 3: 1 + 2 + 3 + 4 + 5 = 15 Example 2: Some sets cannot be symmetrically partitioned. >ruby -rNP -e "a,b = NP::symmetric_subset_sum([1,2,3,4,5,6,7,8,9,4],3); puts a.inspect; puts b.inspect" [17, 17, 15] [3, 3, 3, 2, 3, 2, 2, 1, 1, 3] 4. Satisfiability (SAT) This is the granddaddy of NP-complete problems because many other NP-complete problems were proven to be NP-complete by mapping their problem characteristics to SAT. So, in theory, if anybody is able to devise an algorithm to solve SAT in polynomial time, all NP-complete problems henceforth run in polynomial time. Given a set of m clauses of at most n literals, can a set of boolean variables be found such that every clause evaluates to true? These are examples of clauses composed of literals ('-' is boolean negation): clause 1: a_0 clause 2: -a_0 or a_1 or -a_2 A corresponding boolean variable is assigned to each clause literal. So clause 1 is true if variable v_0 is true. And clause 2 is true if variable v_0 is false or v_1 is true or v_2 is false. BOTH clauses are true at the same time if v_0 is true and v_1 is true. There are other solutions, as well. For example: v_0 = true v_2 = false But these two clauses have no solution: clause 1: a_0 clause 2: -a_0 This is represented in Ruby using the NP module like this: >ruby -rNP -e "c,d = NP::sat([[1],[-1]]); puts c; puts d.inspect" false [-1] 'c' indicates the two clauses could not be satisfied, and 'd' indicates the last best variable guess before the algorithm gave up (-1 means variable v_0 is false). On the other hand, the first example can be solved in Ruby thusly: >ruby -rNP -e "a,b = NP::sat([[1],[-1,0,-1]]); puts a; puts b.inspect" true [1, 1, 0] Or like this: >ruby -rNP -e "a,b = NP::sat([[1,0,0],[-1,0,-1]]); puts a; puts b.inspect" true [1, 1, 0] [1,0,0] means clause 1 is defined as literal a_0, and literals a_1 and a_2 do not matter for this clause. [-1,0,-1] means clause 2 is equivalent to "-a_0 or -a_2" and a_1 is a "don't care". Likewise, the answer, [1,1,0], indicates that one solution involves the first two variables being true and the third false. It's possible to supply ill-defined clauses (see below). PERFORMANCE All of these algorithms fall into the NP-complete category. They will not run quickly on very large problems. However, a great deal of optimization has been done to make them run quickly. In fact, AFAIK, there currently are no faster algorithms that have a Ruby interface. Compared to traditional branch-and-bound algorithms, the algorithms included in this package are orders of magnitude quicker, except on small problems (n < 16) where performance is comparable. WARNINGS Turn warnings on to see additional information about possible argument problems. >ruby -W -rNP -e "NP::sat([[0,0,0], [1,0,-1]])" -e:1: warning: One of the clauses is completely composed of "don't cares (i.e. 0s)". This clause will be discarded. CREDITS The SAT algorithm included in this package was developed at Princeton University. See, http://www.princeton.edu/~chaff/zchaff.html The Multiple Knapsack 0-1 algorithm was developed by David Pisinger. See, http://www.diku.dk/~pisinger/ http://www.diku.dk/~pisinger/codes.html The Symmetric Subset Sum algorithm is largely a derivative of David Pisinger's mulknap algorithm. Lou Vanek converted Pisinger's Subset Sum to Symmetric Subset Sum. The Subset Sum algorithm is part of the Knapsack algorithm developed by David Pisinger. Ruby interface: Lou Vanek vanek at acd dot net DESCRIPTION OF ALGORITHMS http://en.wikipedia.org/wiki/Boolean_satisfiability_problem http://en.wikipedia.org/wiki/Subset_sum_problem http://en.wikipedia.org/wiki/Partition_problem http://en.wikipedia.org/wiki/Knapsack_problem CAVEATS Bignums are not supported. In fact, Fixnums are only limitedly supported: many of the weights (and profits) are restricted to an upper bound of 2**15 - 1. Turning warnings on will display a warning if bad input data is detected, or an ArgumentError will be thrown. VERSION ruby -W -rNP -e "puts NP::VERSION" FILES http://rubyforge.org/frs/?group_id=835