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...bility_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