[ANN] NP

Discussion in 'Ruby' started by Lou Vanek, Feb 8, 2006.

  1. Lou Vanek

    Lou Vanek Guest

    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
    Lou Vanek, Feb 8, 2006
    #1
    1. Advertising

  2. 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
    Gregory Seidman, Feb 8, 2006
    #2
    1. Advertising

  3. Lou Vanek

    Lou Vanek Guest

    Gregory Seidman wrote:

    > 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
    Lou Vanek, Feb 8, 2006
    #3
  4. Lou Vanek

    Guest

    On Wed, 8 Feb 2006, 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


    very cool lou - thanks for this contribution!

    -a

    --
    happiness is not something ready-made. it comes from your own actions.
    - h.h. the 14th dali lama
    , Feb 8, 2006
    #4
  5. On 2/8/06, Gregory Seidman <> wrote:
    > 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
    Edgardo Hames, Feb 8, 2006
    #5
  6. Lou Vanek

    Phil Tomson Guest

    In article <>, 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


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

    Phil
    Phil Tomson, Feb 8, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mike Sampson [MSFT]

    [ANN]: NNTP Server slow downs.

    Mike Sampson [MSFT], Oct 7, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    410
    Mike Sampson [MSFT]
    Oct 7, 2003
  2. Mike Sampson [MSFT]

    [ANN]: NNTP Server slow downs.

    Mike Sampson [MSFT], Dec 6, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    493
    Mike Sampson [MSFT]
    Dec 6, 2003
  3. Richard Grimes [MVP]

    ANN: Free .NET Workshops

    Richard Grimes [MVP], Jul 4, 2005, in forum: ASP .Net
    Replies:
    0
    Views:
    502
    Richard Grimes [MVP]
    Jul 4, 2005
  4. Tom Hawkins

    [ANN] Confluence 0.7.1 Released

    Tom Hawkins, Oct 23, 2003, in forum: VHDL
    Replies:
    0
    Views:
    493
    Tom Hawkins
    Oct 23, 2003
  5. Michael Livsey
    Replies:
    3
    Views:
    418
    Michael Livsey
    May 27, 2004
Loading...

Share This Page