File size: 5,024 Bytes
afaca5c | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | """Make the decomposition satisfy property (B) of Definition 1.
(B): if c(S_i) < 2 c(S_{i-1}) then 8 c(S_{i-1}) < c(S_{i+1}).
The greedy partial-cover oracle satisfies (A) but not (B), because (B) constrains
the COST GROWTH PATTERN across consecutive pieces and a cost-per-element rule
does not control it. Fix: after building the greedy pieces, repeatedly MERGE an
adjacent pair that violates (B). Merging preserves (A) -- a union of consecutive
pieces still covers at least half the remaining prediction at its start -- and
strictly reduces the piece count, so the procedure terminates.
"""
import json, numpy as np
from ice_exp import (make_instance, ilp_cover, ilp_partial, greedy_partial,
online_greedy, ice)
RES = json.load(open("ice_results.json"))
def build_pieces(A, cost, Xhat):
rem = sorted(Xhat); pieces = []
while rem:
need = int(np.ceil(len(rem)/2))
S, cov = greedy_partial(A, cost, rem, need)
if not S: break
Xi = sorted(cov & set(rem))
pieces.append({"S": list(S), "X": Xi, "c": float(cost[list(S)].sum()),
"need_at_start": need, "rem_at_start": len(rem)})
rem = [e for e in rem if e not in cov]
return pieces
def violates_B(p, i):
"""(B) applies at index i when c_i < 2 c_{i-1}; it then demands 8 c_{i-1} < c_{i+1}."""
if i < 1 or i+1 >= len(p): return False
return (p[i]["c"] < 2*p[i-1]["c"]) and not (8*p[i-1]["c"] < p[i+1]["c"])
def enforce_B(pieces, cost, max_iter=200):
p = [dict(x) for x in pieces]
for _ in range(max_iter):
bad = [i for i in range(len(p)) if violates_B(p, i)]
if not bad: break
i = bad[0]
merged = {"S": sorted(set(p[i]["S"]) | set(p[i+1]["S"])),
"X": sorted(set(p[i]["X"]) | set(p[i+1]["X"])),
"need_at_start": p[i]["need_at_start"],
"rem_at_start": p[i]["rem_at_start"]}
merged["c"] = float(cost[merged["S"]].sum())
p = p[:i] + [merged] + p[i+2:]
if len(p) <= 2: break
return p
def check(p):
okA = all(len(x["X"]) >= x["need_at_start"] for x in p)
okB = not any(violates_B(p, i) for i in range(len(p)))
return okA, okB
def run():
rows = []
for (m, n) in ((40, 60), (60, 90), (80, 120)):
for corrupt in (0.0, 0.2, 0.5, 1.0):
rng = np.random.default_rng(m*10+int(corrupt*10))
A, cost = make_instance(m, n, rng)
req = list(rng.permutation(m)[:m//2])
optcost, _ = ilp_cover(A, cost, req)
Xhat = set(req); nswap = int(corrupt*len(req))
if nswap:
drop = set(rng.choice(list(Xhat), size=min(nswap, len(Xhat)), replace=False))
Xhat -= drop
pool = [e for e in range(m) if e not in req]
Xhat |= set(rng.choice(pool, size=min(nswap, len(pool)), replace=False))
eta = min(len(req), len(set(req) ^ Xhat))
raw = build_pieces(A, cost, sorted(Xhat))
fixed = enforce_B(raw, cost)
aR, bR = check(raw); aF, bF = check(fixed)
b_ice, _ = ice(A, cost, req, [x["S"] for x in fixed], [x["c"] for x in fixed])
c_ice = float(cost[b_ice == 1].sum())
b_base, _ = online_greedy(A, cost, req, np.zeros(n, dtype=int))
c_base = float(cost[b_base == 1].sum())
# measured alpha on the merged pieces, against exact ILP partial optima
alphas = []
rem = sorted(Xhat)
for x in fixed:
C1 = ilp_partial(A, cost, rem, min(x["need_at_start"], len(rem)))
if C1 and C1 > 0: alphas.append(x["c"]/C1)
rem = [e for e in rem if e not in set(x["X"])]
if not rem: break
rows.append({"m": m, "corrupt": corrupt, "eta": eta,
"pieces_raw": len(raw), "pieces_after_merge": len(fixed),
"A_raw": aR, "B_raw": bR, "A_fixed": aF, "B_fixed": bF,
"OPT": round(optcost, 3), "ICE_ratio": round(c_ice/optcost, 4),
"baseline_ratio": round(c_base/optcost, 4),
"max_alpha": (round(max(alphas), 3) if alphas else None)})
print(" m=%-3d cor=%.1f eta=%-3d pieces %d->%d (A,B) raw=(%s,%s) fixed=(%s,%s) ICE=%.3f base=%.3f alpha<=%s"
% (m, corrupt, eta, len(raw), len(fixed), aR, bR, aF, bF,
c_ice/optcost, c_base/optcost, rows[-1]["max_alpha"]), flush=True)
RES["claim2_ice_property_B"] = {
"rows": rows,
"B_holds_after_merge_all": all(r["B_fixed"] for r in rows),
"A_preserved_all": all(r["A_fixed"] for r in rows),
"B_held_before_merge_any": any(r["B_raw"] for r in rows),
"max_alpha_overall": max(r["max_alpha"] for r in rows if r["max_alpha"]),
"n_cells": len(rows)}
json.dump(RES, open("ice_results.json", "w"), indent=1)
if __name__ == "__main__":
run(); print("DONE")
|