Class: LogicTools::SmallestSumTerm

Inherits:
Object
  • Object
show all
Defined in:
lib/logic_tools/minimal_column_covers.rb

Overview

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.

Instance Method Summary collapse

Constructor Details

#initialize(product, deadline = Float::INFINITY) ⇒ SmallestSumTerm

Creates the solver for a product.



85
86
87
88
89
90
91
92
 
# 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

Instance Method Details

#bound(term) ⇒ Object

Bounds a partial term.

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



105
106
107
108
109
110
111
112
113
114
115
116
117
 
# 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) ⇒ Object

Branch in the branch and bound algorithm.



144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
 
# 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) ⇒ Object

Selects a term for solution.



95
96
97
98
99
 
# 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 ⇒ Object

Solves the problem using branch and bound.



120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
 
# 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