How to Use Meta’s Rebalancer for Task Placement & Optimization

ORLIB = "https://people.brunel.ac.uk/~mastjjb/jeb/orlib/"
 
 
def fetch(url, tries=4):
    for k in range(tries):
        try:
            with urllib.request.urlopen(urllib.request.Request(url, headers={"User-Agent": "rebalancer-tutorial"}),
                                        timeout=60) as r:
                return r.read()
        except Exception as e:
            if k == tries - 1:
                raise
            print(f"   retry {k + 1} for {url.rsplit('/', 1)[-1]}: {clean(e, 50)}")
            time.sleep(2 * 2 ** k)
 
 
def parse_gap(text):
    tok = text.split()
    P, i, out = int(tok[0]), 1, []
    for _ in range(P):
        m, n = int(tok[i]), int(tok[i + 1])
        i += 2
        profit = [[int(tok[i + r * n + j]) for j in range(n)] for r in range(m)]
        i += m * n
        weight = [[int(tok[i + r * n + j]) for j in range(n)] for r in range(m)]
        i += m * n
        cap = [int(tok[i + r]) for r in range(m)]
        i += m
        out.append((m, n, profit, weight, cap))
    assert i == len(tok), "every token of the file must be consumed"
    return out
 
 
# Published optima (maximization), OR-Library gapinfo.html; the cell re-reads the page and checks every value.
GAP_OPTIMA = {"gap1": [336, 327, 339, 341, 326], "gap2": [434, 436, 420, 419, 428], "gap3": [580, 564, 573, 570, 564],
              "gap4": [656, 644, 673, 647, 664], "gap5": [563, 558, 564, 568, 559], "gap6": [761, 759, 758, 752, 747],
              "gap7": [942, 949, 968, 945, 951], "gap8": [1133, 1134, 1141, 1117, 1127],
              "gap9": [709, 717, 712, 723, 706], "gap10": [958, 963, 960, 947, 947],
              "gap11": [1139, 1178, 1195, 1171, 1171], "gap12": [1451, 1449, 1433, 1447, 1446]}
 
 
def gap_problem(inst, solver_spec):
    m, n, profit, weight, cap = inst
    agents, jobs = [f"agent{i}" for i in range(m)], [f"job{j}" for j in range(n)]
    used, start = [0] * m, {a: [] for a in agents}
    for j in range(n):                    # first fit, least-loaded fallback; the solver repairs any overload
        fits = [i for i in range(m) if used[i] + weight[i][j] <= cap[i]]
        i = fits[0] if fits else min(range(m), key=lambda k: used[k] - cap[k])
        start[agents[i]].append(jobs[j])
        used[i] += weight[i][j]
    p = new_problem(start, objects="job", containers="agent")
    # A job's resource use depends on which agent it sits on: a dynamic object dimension keyed by the agent scope.
    p.add_dynamic_object_dimension("resource", "agent",
                                   {agents[i]: {jobs[j]: float(weight[i][j]) for j in range(n)} for i in range(m)},
                                   default_value=0.0)
    p.add_container_dimension("resource", {agents[i]: float(cap[i]) for i in range(m)}, default_value=0.0)
    p.add_constraint(spec("capacitySpec", name="agent_capacity", scope="agent", dimension="resource",
                          bound=MAX_BOUND))
    p.add_goal(spec("assignmentAffinitiesSpec", name="profit", scope="agent",
                    affinities=[{"objectName": jobs[j], "scopeItemName": agents[i], "affinity": float(profit[i][j])}
                                for i in range(m) for j in range(n)]), weight=1.0)
    p.add_solver(solver_spec)
    return p, agents, jobs
 
 
def gap_recount(inst, assignment, agents, jobs):
    m, n, profit, weight, cap = inst
    idx = {a: i for i, a in enumerate(agents)}
    use = [0] * m
    for j, job in enumerate(jobs):
        use[idx[assignment[job]]] += weight[idx[assignment[job]]][j]
    total = sum(profit[idx[assignment[job]]][j] for j, job in enumerate(jobs))
    return total, all(use[i] <= cap[i] for i in range(m)) and len(assignment) == n
 
 
@section("9. Generalised assignment: 60 OR-Library instances against their published optima")
def gap_step():
    page = fetch(ORLIB + "gapinfo.html").decode("latin-1")
    published = {name: int(v) for name, v in re.findall(r"(cd+-d)s+(d+)", re.sub(r"<[^>]+>", " ", page))}
    data, digest, nbytes = {}, hashlib.sha256(), 0
    for g in GAP_OPTIMA:
        raw = fetch(ORLIB + f"files/{g}.txt")
        digest.update(raw)
        nbytes += len(raw)
        data[g] = parse_gap(raw.decode())
    pinned = digest.hexdigest()[:12] == "54513b5b96f6"     # the files this notebook was verified with
    print(f"gap1..gap12: {nbytes / 1024:.0f} KB, sha256 of the 12 files {digest.hexdigest()[:12]} (same as the verified "
          f"copy: {pinned}), {sum(len(v) for v in data.values())} instances")
    if not pinned:
        raise RuntimeError("the OR-Library GAP files differ from the ones this notebook was verified with")
    # The page names each instance c- (c515-1 is 5 agents, 15 jobs, problem 1).
    names = {g: [f"c{m}{n}-{k + 1}" for k, (m, n, *_) in enumerate(v)] for g, v in data.items()}
    same = all(published.get(nm) == GAP_OPTIMA[g][k] for g in data for k, nm in enumerate(names[g]))
    print(f"gapinfo.html: {len(published)} published optima, matched by instance name to the table in this notebook: "
          f"{same}")
    if not same:
        raise RuntimeError("the optima on gapinfo.html differ from the embedded table")
    guard = {"HiGHS": 90.0, "local": 120.0}     # seconds; a solve starts only while its cap still fits
    print(f"n{'group':<6}{'size':>7} | {'HiGHS = optimum':>15}{'slowest':>9} | local search = optimum "
          f"(seed 1/2/3, best){'':>2} mean shortfall")
    tot = collections.Counter()
    shortfalls, relative, disagree, worst = [], [], 0, 0.0
    for g, insts in data.items():
        hit_h, slow, hit, group_short, group_h = 0, 0.0, [0, 0, 0, 0], [], 0
        for k, inst in enumerate(insts):
            opt = GAP_OPTIMA[g][k]
            sol = None
            if HIGHS_OK and guard["HiGHS"] >= 10:
                p, agents, jobs = gap_problem(inst, highs(10))
                try:
                    sol, dt = solve(p)
                except Exception as e:        # a HiGHS failure costs this instance's exact run, not the whole step
                    print(f"   {g}#{k + 1}: HiGHS raised {clean(e, 60)}")
                    tot["h_err"] += 1
            if sol is not None:
                guard["HiGHS"] -= dt
                tot["h_sec"] += dt
                val, feas = gap_recount(inst, sol["assignment"], agents, jobs)
                slow, worst = max(slow, dt), max(worst, dt)
                tot["h_run"] += 1
                group_h += 1
                tot["h_feas"] += feas
                tot["h_optimal_end"] += ends(sol) == "OPTIMAL"
                hit_h += feas and val == opt
                if feas and val > opt:
                    raise RuntimeError(f"{g}#{k + 1}: HiGHS profit {val} exceeds the published optimum {opt}")
            vals = []
            for seed in (1, 2, 3):
                if guard["local"] < 3:
                    continue
                p, agents, jobs = gap_problem(inst, local_search(3, seed=seed, moves=("single", "swap", "triple", "kl")))
                sol, dt = solve(p)
                guard["local"] -= dt
                tot["l_sec"] += dt
                val, feas = gap_recount(inst, sol["assignment"], agents, jobs)
                if val > opt and feas:
                    raise RuntimeError(f"{g}#{k + 1}: local-search profit {val} exceeds the published optimum {opt}")
                tot["l_run"] += 1
                tot["l_feas"] += feas
                vals.append(val if feas else None)
                hit[seed - 1] += feas and val == opt
            best = max((v for v in vals if v is not None), default=None)
            if len(vals) == 3 and best is not None:
                hit[3] += best == opt
                shortfalls.append(opt - best)
                group_short.append(opt - best)
                relative.append((opt - best) / opt)
                disagree += len(set(vals)) > 1
        tot["h_hit"] += hit_h
        for j in range(4):
            tot[f"l_hit{j}"] += hit[j]
        m, n = insts[0][0], insts[0][1]
        gs = f"{statistics.mean(group_short):6.1f}" if group_short else "     -"
        print(f"{g:<6}{f'{m}x{n}':>7} | {hit_h:>11} of {group_h}{slow:>8.2f}s | {hit[0]:>4} {hit[1]:>4} {hit[2]:>4} {hit[3]:>6}"
              f"{'':>20}{gs}")
    if not HIGHS_OK:
        print("nHiGHS: skipped, it failed the step-1 gate")
    else:
        print(f"nHiGHS: {tot['h_hit']} of {tot['h_run']} equal the published optimum; endReason OPTIMAL "
              f"{tot['h_optimal_end']} of {tot['h_run']}; recounted feasible {tot['h_feas']} of {tot['h_run']}; raised "
              f"{tot['h_err']}; slowest {worst:.2f} s, {tot['h_sec']:.1f} s in total")
    mean_short = statistics.mean(shortfalls) if shortfalls else float("nan")
    print(f"local search (single, swap, triple loop, Kernighan-Lin; first-fit start; 3 s cap): seed 1/2/3 hit "
          f"{tot['l_hit0']}/{tot['l_hit1']}/{tot['l_hit2']}, best of three {tot['l_hit3']} of {len(shortfalls)}; "
          f"best-of-three shortfall mean {mean_short:.1f} "
          f"({100 * statistics.mean(relative) if relative else float('nan'):.2f}% of the optimum), "
          f"max {max(shortfalls, default=0)}; seeds disagree on {disagree} "
          f"instances; recounted feasible {tot['l_feas']} of {tot['l_run']}; {tot['l_sec']:.1f} s in total")
    if (HIGHS_OK and tot["h_run"] < 60) or len(shortfalls) < 60:
        print(f"PARTIAL: {tot['h_run']} HiGHS and {len(shortfalls)} local-search instances completed (time guard or "
              f"errors); the 60-of-60 comparison does not apply")
    claim("GAP: all 60 HiGHS runs ran and equal the published optimum", tot["h_hit"] == tot["h_run"] == 60)
    claim("GAP: all 180 local-search answers ran and are feasible by recount", tot["l_feas"] == tot["l_run"] == 180)
    return ((f"HiGHS {tot['h_hit']}/{tot['h_run']} published optima (slowest {worst:.2f} s)" if HIGHS_OK else
             "HiGHS skipped") + f"; local search best-of-3 {tot['l_hit3']}/{len(shortfalls)}, best-of-3 shortfall "
            f"mean {mean_short:.1f}")
 
 
gap_step()