<p>I think I found the solution. When in <code>PR(W)</code>, <code>D=∅</code>, the weight is:</p>

<p><code>b[i] = 0          for { i | w[i]&lt;max(w) }</code>, </p>

<p>and</p>

<p><code>b[i] = 1.0/max(w) for { i | w[i]==max(w) }</code>.</p>

CC BY-SA 3.0
2017-02-18T11:38:34.770Z
2017-10-03T21:24:09.727Z
2017-10-03T21:24:09.727Z
stustd
<p>How does in the (famous Zilberstein) <code>PR</code>(uning) algorithm below the <code>LP-dominate</code> function get started: the first time it's called, <code>D=∅</code> and the linear program deteriorates (i.e. no constraint equations)? </p>

<pre><code>procedure POINTWISE-DOMINATE(w, U)
...
3. return false
procedure LP-DOMINATE(w, U)
4. solve the following linear program variables: d, b(s) ∀s ∈ S
      maximize d
      subject to the constraints
        b · (w − u) ≥ d, ∀u ∈ U
        sum(b) = 1
5. if d ≥ 0 then return b
6. else return nil
procedure BEST(b, U )
...
12. return w
procedure PR(W)
13. D ← ∅
14. while W = ∅
15.   w ← any element in W
16.   if POINTWISE-DOMINATE(w, D) = true
17.      W ← W − {w}
18.   else
19.      b ← LP-DOMINATE(w, D)
20.      if b = nil then
21.         W ← W − {w}
22.      else
23.         w ← BEST(b, W)
24.         D ← D ∪ {w}
25.         W ← W − {w}
26. return D
</code></pre>

CC BY-SA 3.0
2018-04-13T23:56:21.490Z
check a book about algorithms heuristics using python. good luck!
Youness Abdus Salam
<decision-theory>
Zilberstein's "LP-dominate" pruning explained?
stustd
# Zilberstein's "LP-dominate" pruning explained?

(Asked by: username_0 on 2017-02-16)

How does in the (famous Zilberstein) PR(uning) algorithm below the LP-dominate function get started: the first time it's called, D=∅ and the linear program deteriorates (i.e. no constraint equations)? 
procedure POINTWISE-DOMINATE(w, U)
...
3. return false
procedure LP-DOMINATE(w, U)
4. solve the following linear program variables: d, b(s) ∀s ∈ S
      maximize d
      subject to the constraints
        b · (w − u) ≥ d, ∀u ∈ U
        sum(b) = 1
5. if d ≥ 0 then return b
6. else return nil
procedure BEST(b, U )
...
12. return w
procedure PR(W)
13. D ← ∅
14. while W = ∅
15.   w ← any element in W
16.   if POINTWISE-DOMINATE(w, D) = true
17.      W ← W − {w}
18.   else
19.      b ← LP-DOMINATE(w, D)
20.      if b = nil then
21.         W ← W − {w}
22.      else
23.         w ← BEST(b, W)
24.         D ← D ∪ {w}
25.         W ← W − {w}
26. return D

**Tags:** decision-theory

> **Comments:**
> **username_1**: check a book about algorithms heuristics using python. good luck!  

---

## 1 answers

### Answer by username_0 on 2017-02-18. Score: 1

I think I found the solution. When in `PR(W)`, `D=∅`, the weight is:

`b[i] = 0 for { i | w[i],`

and

`b[i] = 1.0/max(w) for { i | w[i]==max(w) }`.


---

