code/ice_exp.py

"""Claim 2 (Theorem 2 / Theorem 4): given a polynomial-time (alpha, gamma)-
decomposition, the ICE algorithm achieves
    O(alpha) * rho(eta, .) + O(alpha * log^{-1}(gamma/(gamma-1)) * log k).

Definition 1 (from the source): an (alpha,gamma)-decomposition is a pair
(X_i, S_i) with Xhat = X_1 u ... u X_r such that for every i
  (A) |X_i| >= (|Xhat| - (|X_1|+...+|X_{i-1}|)) / 2
  (B) if c(S_i) <  2 c(S_{i-1}) then 8 c(S_{i-1}) < c(S_{i+1})
  (C) if c(S_i) > 10 c(S_{i-1}) then c(S_i) <= g(|Xhat|) * C_1, where C_1 is the
      min-cost solution covering ceil(|remaining|/2) elements of R_{i-1}.

The decomposition oracle below is polynomial time: each S_i is built by the
standard greedy partial-cover rule (cheapest set per newly covered element)
until half of the remaining predicted elements are covered. C_1 is computed
EXACTLY by ILP so that (C) is checked against the true optimum, not a proxy, and
alpha is *measured* as c(S_i)/C_1 rather than assumed.

ICE online phase: run a black-box online algorithm; track its spend; whenever
cumulative online cost exceeds the cost of the next decomposition piece, buy it.
"""
import json, numpy as np
from scipy.optimize import milp, LinearConstraint, Bounds
from scipy.sparse import csc_matrix

RES = {}


def make_instance(m, n, rng, p=0.18):
    A = (rng.uniform(size=(m, n)) < p).astype(np.int8)
    for e in range(m):
        if A[e].sum() == 0: A[e, rng.integers(n)] = 1
    cost = rng.uniform(1.0, 5.0, size=n)
    return A, cost


def ilp_cover(A, cost, elems):
    """Exact min-cost cover of the given elements."""
    if len(elems) == 0: return 0.0, np.zeros(A.shape[1], dtype=int)
    sub = A[list(elems)]
    c = LinearConstraint(csc_matrix(sub), lb=np.ones(len(elems)), ub=np.inf)
    r = milp(c=cost, constraints=[c], integrality=np.ones(A.shape[1]),
             bounds=Bounds(0, 1))
    if not r.success: return None, None
    return float(r.fun), np.round(r.x).astype(int)


def ilp_partial(A, cost, elems, need):
    """Exact min-cost solution covering at least `need` of `elems` (ILP with
    per-element indicators)."""
    elems = list(elems)
    if need <= 0: return 0.0
    n = A.shape[1]; m = len(elems)
    # vars: n set-vars then m element-indicators
    sub = A[elems]
    rows, cols, vals = [], [], []
    for i in range(m):                       # y_i <= sum_{S covering e_i} x_S
        for j in np.flatnonzero(sub[i]):
            rows.append(i); cols.append(j); vals.append(1.0)
        rows.append(i); cols.append(n+i); vals.append(-1.0)
    M = csc_matrix((vals, (rows, cols)), shape=(m, n+m))
    cons = [LinearConstraint(M, lb=np.zeros(m), ub=np.inf)]
    sel = np.zeros((1, n+m)); sel[0, n:] = 1.0
    cons.append(LinearConstraint(csc_matrix(sel), lb=need, ub=np.inf))
    cvec = np.concatenate([cost, np.zeros(m)])
    r = milp(c=cvec, constraints=cons, integrality=np.ones(n+m), bounds=Bounds(0, 1))
    return float(r.fun) if r.success else None


def greedy_partial(A, cost, remaining, need):
    """Polynomial-time oracle: greedy cheapest-per-new-element until `need` covered."""
    rem = set(remaining); chosen = []; covered = set()
    while len(covered) < need:
        best, bj = None, None
        for j in range(A.shape[1]):
            new = len([e for e in rem if A[e, j] and e not in covered])
            if new == 0: continue
            r = cost[j]/new
            if best is None or r < best: best, bj = r, j
        if bj is None: break
        chosen.append(bj)
        covered |= {e for e in rem if A[e, bj]}
    return chosen, covered


def decompose(A, cost, Xhat):
    """Build (X_i, S_i) satisfying (A); measure alpha from (C) and gamma from
    the realised cost growth ratio."""
    rem = list(Xhat); pieces = []
    while rem:
        need = int(np.ceil(len(rem)/2))
        S, cov = greedy_partial(A, cost, rem, need)
        Xi = sorted(cov & set(rem))
        cS = float(cost[S].sum())
        C1 = ilp_partial(A, cost, rem, need)
        pieces.append({"X_i": len(Xi), "cost_S_i": cS, "C1_exact": C1,
                       "alpha_i": (cS/C1 if C1 and C1 > 0 else None),
                       "propA": bool(len(Xi) >= need)})
        rem = [e for e in rem if e not in cov]
        if not S: break
    return pieces


def check_props(pieces):
    a = [p["alpha_i"] for p in pieces if p["alpha_i"] is not None]
    okA = all(p["propA"] for p in pieces)
    cs = [p["cost_S_i"] for p in pieces]
    okB = True
    for i in range(1, len(cs)-1):
        if cs[i] < 2*cs[i-1] and not (8*cs[i-1] < cs[i+1]): okB = False
    ratios = [cs[i]/cs[i-1] for i in range(1, len(cs)) if cs[i-1] > 0]
    return okA, okB, (max(a) if a else None), (max(ratios) if ratios else None)


def online_greedy(A, cost, requests, bought):
    """Black-box online set cover: on an uncovered request, buy cheapest covering set."""
    b = bought.copy(); spend = 0.0
    for e in requests:
        if any(b[j] and A[e, j] for j in range(A.shape[1])): continue
        cand = np.flatnonzero(A[e]); j = cand[np.argmin(cost[cand])]
        b[j] = 1; spend += cost[j]
    return b, spend


def ice(A, cost, requests, pieces_sets, piece_costs):
    """ICE: run the online algorithm; whenever its spend exceeds the next piece's
    cost, buy that piece too."""
    bought = np.zeros(A.shape[1], dtype=int); spend = 0.0; k = 0
    for e in requests:
        if not any(bought[j] and A[e, j] for j in range(A.shape[1])):
            cand = np.flatnonzero(A[e]); j = cand[np.argmin(cost[cand])]
            bought[j] = 1; spend += cost[j]
        while k < len(pieces_sets) and spend >= piece_costs[k]:
            for j in pieces_sets[k]: bought[j] = 1
            spend += piece_costs[k]; k += 1
    return bought, spend


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)
            # prediction: corrupted version of the true request set
            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))
            pieces = decompose(A, cost, sorted(Xhat))
            okA, okB, amax, gmax = check_props(pieces)
            psets, pcosts = [], []
            rem = sorted(Xhat)
            for p in pieces:
                need = int(np.ceil(len(rem)/2))
                S, cov = greedy_partial(A, cost, rem, need)
                psets.append(S); pcosts.append(float(cost[S].sum()))
                rem = [e for e in rem if e not in cov]
            b_ice, _ = ice(A, cost, req, psets, pcosts)
            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())
            rows.append({"m": m, "n": n, "corrupt": corrupt, "eta": eta,
                         "OPT_ilp": round(optcost, 3),
                         "ICE_cost": round(c_ice, 3), "baseline_cost": round(c_base, 3),
                         "ICE_ratio": round(c_ice/optcost, 4),
                         "baseline_ratio": round(c_base/optcost, 4),
                         "pieces": len(pieces), "propA_holds": okA, "propB_holds": okB,
                         "measured_alpha_max": (round(amax, 4) if amax else None),
                         "max_cost_growth_gamma": (round(gmax, 3) if gmax else None)})
            print("  m=%-3d corrupt=%.1f eta=%-3d OPT=%7.2f  ICE=%7.2f (%.3f)  base=%7.2f (%.3f)  pieces=%d A=%s B=%s alpha<=%.2f"
                  % (m, corrupt, eta, optcost, c_ice, c_ice/optcost, c_base, c_base/optcost,
                     len(pieces), okA, okB, amax or -1), flush=True)
    RES["claim2_ice"] = {
        "rows": rows,
        "propA_all": all(r["propA_holds"] for r in rows),
        "propB_all": all(r["propB_holds"] for r in rows),
        "max_measured_alpha": max(r["measured_alpha_max"] for r in rows if r["measured_alpha_max"]),
        "ICE_beats_baseline_at_eta0": [r for r in rows if r["eta"] == 0],
        "n_cells": len(rows)}
    json.dump(RES, open("ice_results.json", "w"), indent=1)


if __name__ == "__main__":
    run(); print("DONE")