class LogicTools::SmallestSumTerm

Class for applying branch and bound for extracting from a product of sums the smallest term of the corresponding sum of products.

Attributes:

product

the product to extract the term from.

cur_term

the current term.

best_term

the best term found.

best_cost

the best cost.

deadline

time before returning the current best solution.

time

initial time.

Public Class Methods

new(product, deadline = Float::INFINITY) click to toggle source

Creates the solver for a product.

# File lib/logic_tools/minimal_column_covers.rb, line 85
def initialize(product, deadline = Float::INFINITY)
    @product = product
    @cur_term = []
    # @cur_term = HashCounter.new
    @best_term = nil
    @best_cost = @cur_cost = Float::INFINITY
    @deadline = deadline
end

Public Instance Methods

bound(term) click to toggle source

Bounds a partial term.

# NOTE: may modify term through uniq! (for performance purpose.) NOTE: It is assumed that term is hash-like

# File lib/logic_tools/minimal_column_covers.rb, line 105
def bound(term)
    # if Time.now - @time >= @deadline and
    #    @best_cost < Float::INFINITY then
    #     # Time over, force a high cost.
    #     return Float::INFINITY
    # end
    if (term.size >= @best_cost) then
        return term.uniq.size
    else
        return term.size
    end
    # return term.size
end
branch(pi) click to toggle source

Branch in the branch and bound algorithm.

# File lib/logic_tools/minimal_column_covers.rb, line 144
def branch(pi)
    # # Start the timer if required.
    # @time = Time.now if (pi == 0)
    # # Check the deadline.
    # if Time.now - @time >= @deadline and
    #    @best_cost < Float::INFINITY then
    #     # Time over, end here.
    #     return @best_term
    # end
    # Bound the current term.
    if (self.bound(@cur_term) < @best_cost)
        # Better bound, can go on with the current solution.
        if pi == @product.size then
            # But this is the end, so update the best term.
            make_best(@cur_term)
        else
            # Still a possible solution, recurse.
            @product[pi].each do |elem|
                @cur_term.push(elem)
                # @cur_term.inc(elem)
                # solve(pi+1)
                branch(pi+1)
                @cur_term.pop
                # @cur_term.dec(elem)
            end
        end
    end
    return @best_term
end
make_best(term) click to toggle source

Selects a term for solution.

# File lib/logic_tools/minimal_column_covers.rb, line 95
def make_best(term)
    # print "make_best\n"
    @best_term = term.uniq
    @best_cost = @best_term.size
end
solve() click to toggle source

Solves the problem using branch and bound.

# File lib/logic_tools/minimal_column_covers.rb, line 120
def solve()
    # Solve the problem throughly.
    begin
        if @deadline != Float::INFINITY then
            Timeout::timeout(@deadline) {
                self.branch(0)
            }
        else
                self.branch(0)
        end
    rescue Timeout::Error
        # Time out, is there a solution?
        # print "Timeout!\n"
        unless @best_term
            # No, quickly create one including the first element
            # of each factor.
            @best_term = @product.map {|fact| fact[0] }
            @best_term.uniq!
        end
    end
    return @best_term
end