[ANN] NP

[Lou Vanek]

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

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

 

[Gregory Seidman]

On Wed, Feb 08, 2006 at 10:36:01PM +0900, Lou Vanek wrote:
} 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)

So does this mean there won't be any more Ruby Quizzes based on NP-complete
problems? Please? I mean, if you've solved one, you've solved them all.

--Greg

 

[Lou Vanek]

On Wed, Feb 08, 2006 at 10:36:01PM +0900, Lou Vanek wrote:
} 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)

So does this mean there won't be any more Ruby Quizzes based on NP-complete
problems? Please? I mean, if you've solved one, you've solved them all.

--Greg

The algorithms are fast, but still exponential. The knee in the curve,
however, is far off to the right compared to traditional branch-and-bound
algorithms. For small and medium-sized problems though, yes, if you can
discover a mapping from your problem to one of these four algorithms, your
problem is (quickly) solved.

-lv

 

[ara.t.howard]

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

very cool lou - thanks for this contribution!

-a

 

[Edgardo Hames]

On Wed, Feb 08, 2006 at 10:36:01PM +0900, Lou Vanek wrote:
} If anybody else finds NP-complete problems interesting then you may wan= t
} to check out my new Ruby extension. You can find the extension, ext_np,= at
} http://rubyforge.org/frs/?group_id=3D835
}
} 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 fo= ur
} optimized NP-complete algorithms:
}
} o Multiple Knapsack 0-1
} o Subset Sum
} o Symmetric Subset Sum
} o Satisfiability (SAT)

So does this mean there won't be any more Ruby Quizzes based on NP-comple= te
problems? Please? I mean, if you've solved one, you've solved them all.

One implementation to solve them all ;-)

Now, what other programming language has this feature?

Cheers,
Ed
--
Encontr=E1 a "Tu psic=F3pata favorito" http://tuxmaniac.blogspot.com
=09
Thou shalt study thy libraries and strive not to reinvent them without caus=
e,
that thy code may be short and readable and thy days pleasant and productiv=
e.
-- Seventh commandment for C programmers

 

[Phil Tomson]

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

Cool. Though I was hoping that perhaps you were going to announce that P=NP
;-)

Phil