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