mixle.precedence_scheduling module

Precedence-constrained selection and scheduling: maximum-weight closure and time-phased capacity scheduling.

Two general combinatorial-optimization problems recur whenever items each carry a value (positive or negative) and a precedence relation: item b may not be taken without its predecessor items – in the scheduling problem, b may not be scheduled in an earlier period than any of them. (That is “never later than”, not “strictly earlier”: a predecessor and its dependent may share a period. schedule_activities() spells out what that does and does not guarantee.) Two questions sit on top of that model:

  • Maximum-weight closure (maximum_weight_closure()) – ignoring time, which subset of items maximizes total value subject to precedence? Picard’s construction reduces this to a single min-cut: connect a source to every positive-value item with capacity equal to its value, connect every negative-value item to a sink with capacity equal to its magnitude, and add an effectively-infinite-capacity arc b -> pred for every precedence pair – an infinite arc can never be cut, so the source side of the min-cut can never contain an item without also containing its predecessors, which is exactly the closure property. Solved with mixle.relations.max_flow() / mixle.relations.min_cut() (Edmonds-Karp is a valid, if not asymptotically optimal, pseudoflow substitute for this fixed-size combinatorial problem).

  • Time-phased scheduling (schedule_activities()) – given a per-period capacity and a discount rate, when (which period, if ever) should each item be scheduled to maximize net present value, honoring precedence at every period boundary and never exceeding capacity? This is a mixed-integer program (binary x[b, t] = item b scheduled in period t) solved by mixle.relations.branch_and_bound_milp().

Neither construction is domain-specific: any “which interdependent items are worth taking, and when” problem reduces the same way – project selection under budget/dependency constraints, task scheduling with prerequisites, VLSI partitioning. The canonical worked instantiation of the first is open-pit mine planning’s “ultimate pit limit” (Lerchs-Grossmann): each block’s economic value (ore net of processing cost, or negative for waste net of removal cost) plus the precedence a stable slope imposes (a block cannot be extracted before the material a stable slope requires be removed above it) is exactly the maximum-weight closure problem; the second’s canonical instantiation is that same block model’s time-phased extraction schedule under mill/mining capacity. Both are used that way elsewhere in this codebase, but the functions here take plain items, values, and precedence pairs – nothing about a block, an ore, or a mine.

>>> import numpy as np
>>> value = np.array([-1.0, 10.0])       # item 0 is a cost, item 1 depends on it
>>> precedence = [(1, 0)]                # item 1 requires item 0 first
>>> maximum_weight_closure(value, precedence)
array([ True,  True])
maximum_weight_closure(value, precedence)[source]

The maximum-weight closure of a precedence DAG (Picard’s max-flow reduction).

value is a length-n array of per-item net value (positive or negative). precedence lists (b, pred) pairs meaning item b requires item pred be selected first. Returns a length-n boolean mask, True for every item in the value-maximizing, precedence-closed selection: a super-source connects to every positive-value item with capacity equal to its value, every negative-value item connects to a super-sink with capacity equal to its magnitude, and each precedence pair becomes an effectively-infinite-capacity arc b -> pred – such an arc is never cut, so the min-cut’s source side can never hold b without also holding pred, which is exactly the closure property. The source side of the minimum cut (mixle.relations.min_cut()) is the optimal closure. “Effectively infinite” is a finite big-M (the total absolute value plus one) rather than a literal np.inf: mixle.relations.max_flow() reconstructs flow as cap - residual, and an infinite cap on an arc that ever carries flow leaves residual also infinite, so that subtraction is inf - inf = nan – which then makes mixle.relations.min_cut()’s reachability BFS silently drop the arc (nan > tol is false), breaking the closure guarantee. A finite big-M that no optimal cut could ever prefer to sever avoids the NaN while keeping the same combinatorial meaning.

Open-pit mine planning calls this the ultimate pit limit: each block’s value is ore net of processing cost (positive) or waste net of removal cost (negative), and precedence lists the blocks a stable slope forces to be removed before each block – but the reduction above has no block, ore, or slope in it.

Parameters:
Return type:

ndarray

schedule_activities(value, precedence, capacity, n_periods, *, discount=0.0, mode='exact')[source]

Time-phased schedule maximizing discounted value under precedence and per-period capacity.

value is a length-n array of finite per-item net value; precedence lists (b, pred) pairs as in maximum_weight_closure(); capacity is a length-n_periods array bounding how many items may be scheduled in each period (one item = one unit of capacity: callers wanting heterogeneous per-item resource use can pre-scale capacity or split a heavy item into unit sub-items). Binary x[b, t] = item b scheduled in period t; precedence is enforced at every period boundary, each item is scheduled at most once (never, if it is never worth it), and the objective discounts each period’s value by (1 + discount) ** t. Solved exactly by mixle.relations.branch_and_bound_milp().

Precedence here means “never later than”, not “strictly earlier”. The constraint is that pred’s cumulative scheduling can never trail b’s at any period boundary, so a predecessor and its dependent may legitimately share a period – with one period, capacity two, values [1, 10] and precedence=[(1, 0)] both items are scheduled at period 0. That is same-boundary closure, the right model when a period is an accounting bucket (a year’s mining is not internally ordered) and the wrong one when a period is a strict hand-off. For strict “finishes before the next one starts”, give each item its own period’s worth of capacity, or model the delay explicitly rather than reading a stronger guarantee into this one. For the same reason a cyclic precedence relation is satisfiable rather than rejected: a two-cycle forces its items into the same period, which is what mutual “never later than” constraints mean. The ordering that a strict reading would call a contradiction only exists under strict semantics.

capacity entries are finite and non-negative; since items consume one unit each, a fractional capacity floors (0.5 schedules nothing in that period). discount must be finite and greater than -1: at -1 the discount factor divides by zero, and an infinite one silently zeroes all future value rather than discounting it.

mode selects the semantics, and only the caller may change them:

  • "exact" (default) always solves the declared maximum-NPV MILP over the full horizon.

  • "rolling" is an explicitly approximate myopic rolling horizon – windows of periods solved exactly in sequence, each committing its items before the next window is built. It carries no optimality bound: because a window cannot see reward that only arrives after it, the heuristic can refuse an entire profitable dependency chain. On a 50-item, 10-period instance with unit capacity and a 10-item chain (nine predecessors worth -1, terminal item worth 100) it returned no schedule and NPV 0, where the full MILP takes the chain in periods 0-9 for NPV 91.

Above _DIRECT_MILP_LIMIT item-period binaries this used to switch to "rolling" on its own, so an ordinary optimum-shaped result silently answered a different problem than the one declared. Large instances now stay exact unless the caller opts into the approximation.

Returns (npv, period) where period[b] is the 0-indexed period item b is scheduled in, or -1 if it is never scheduled.

Open-pit mine planning uses this for time-phased block extraction scheduling under mill/mining capacity, but nothing here is block- or mine-specific: it is a general precedence-constrained, capacity-limited scheduling MILP.

Parameters:
Return type:

tuple[float, ndarray]