Ordered-Window Sequencing MIPs

Core idea

When a sequencing objective depends on neighboring ordered patterns, a plain item-position assignment model may be too weak or too easy to linearize incorrectly. Model the local ordered patterns that the objective scores, then link those patterns so they form one consistent sequence.

Use this pattern for schedules, routes, job orders, block sequences, timetables, shift plans, and other ordered assignments where costs depend on adjacent pairs, sliding windows, or overlapping local events.

Modeling workflow

1. Identify the ordered positions: periods, route stops, sequence indices, slots, machine positions, or service windows.
2. Identify the items to place: jobs, exams, blocks, visits, tasks, resources, or customer groups.
3. Decide which binary variables match the objective structure:
   • assignment variables for item-position placement;
   • arc variables for predecessor-successor relationships;
   • ordered-window variables for local patterns of length two or more.
4. Add hard feasibility constraints before optimizing: each item appears exactly as required, each required position is filled, invalid placements are blocked, and local windows cannot contain repeated items unless repeats are allowed.
5. Add auxiliary variables for adjacent pairs, sliding triples, longer windows, or overlapping local patterns.
6. Link auxiliary variables tightly to the primary sequence representation.
7. Build named objective components and minimize the weighted sum defined by the instance.
8. Extract the final sequence and audit the objective independently.

Preserve ordered tuple data

Treat tuple-indexed costs or counts as ordered unless the task explicitly says they are unordered. A schedule induces direction through the order of positions.

For a window beginning at position t, use the tuple in sequence order:

pair_key = (item_at[t], item_at[next_t])
triple_key = (item_at[t], item_at[next_t], item_at[next_next_t])

Do not sort, canonicalize, symmetrize, or aggregate tuple keys unless the task says the data are unordered:

# Wrong for directed or ordered sequence costs unless explicitly allowed.
key = tuple(sorted((a, b, c)))

Sorting tuple keys can turn a directed sequence objective into a different unordered objective.

Before coding the objective, inspect the data schema and write down the tuple semantics you will use:

• If rows are keyed as (i, j) or (i, j, k), the safe default is ordered.
• Do not add reverse pairs, sorted triples, or all permutations unless the source explicitly says the table is symmetric or unordered.
• If the table contains both (i, j) and (j, i), that does not by itself mean both should be summed for one ordered window. It may simply be a complete ordered table.
• If tuple rows are missing, decide from the task/data whether missing means zero, invalid, or impossible before optimizing.

For each objective component, implement one small evaluator expression that matches the component definition exactly:

component = 0
for start in eligible_starts:
    key = tuple(item_at_position(start, offset) for offset in offsets)
    component += weight_table.get(key, 0)

Use this evaluator as the reference for both optimization checks and final metrics.

Assignment-linked local windows

If using assignment variables,

assign[i, t] = 1 if item i is assigned to ordered position t

then create a local-window indicator for each ordered tuple and eligible start position. For a length-3 window:

window[i, j, k, t] = 1 if i, j, k occupy positions t, next(t), next(next(t))

A standard linearization is:

window[i, j, k, t] <= assign[i, t]
window[i, j, k, t] <= assign[j, next_t]
window[i, j, k, t] <= assign[k, next_next_t]
window[i, j, k, t] >= assign[i, t] + assign[j, next_t] + assign[k, next_next_t] - 2

Use the same pattern for adjacent pairs or longer local windows. Create only eligible starts when the task defines a start-position mask.

Direct ordered-window model

Some sequencing problems are cleaner with ordered-window variables as the main sequence representation:

W[t, a1, a2, ..., ar] = 1

meaning that the ordered tuple (a1, a2, ..., ar) starts at position t. This is useful when the objective primarily scores sliding windows and their overlaps.

Typical constraint families are:

• exactly one selected window at each eligible start;
• each item appears the required number of times in each position role;
• local windows with repeated items are prohibited when the sequence is a permutation;
• neighboring windows agree on their shared items.

Prefix/suffix continuity

Adjacent local windows must describe one consistent global sequence. For a length-r window, the suffix of the window at t should match the prefix of the window at next(t).

Generic continuity template:

sum over a0 of W[t, a0, q1, ..., q_{r-1}]
=
sum over ar of W[next(t), q1, ..., q_{r-1}, ar]

for each shared ordered suffix/prefix (q1, ..., q_{r-1}).

Use cyclic wraparound only when the source formulation or task definition makes the sequence cyclic. Otherwise handle the first and last positions with explicit boundary logic. Even in a cyclic model, reporting metrics may use only the start positions declared eligible by the instance.

Overlap penalties

If the objective penalizes two or more overlapping local patterns, introduce an overlap indicator or an equivalent linearization. Do not replace an ordered overlap rule with an unordered span count or with all combinations inside a larger window unless the task defines that rule.

For two overlapping local patterns represented by A and B, use:

overlap <= A
overlap <= B
overlap >= A + B - 1

Then attach the instance-defined ordered cost to overlap. Keep the overlap term inside the optimized model whenever it is part of the objective. Optimizing a reduced model and adding the omitted high-order penalty afterward usually optimizes a different problem.

When the prose mentions pressure, overlap, or "three in four" behavior, pause and distinguish these common but different definitions:

• all unordered triples contained in a four-position span;
• ordered triples whose positions have span at most four;
• pairs of adjacent active three-position windows sharing positions;
• explicit auxiliary variables from a source formulation.

These are not interchangeable. Use only the definition implied by the supplied starts, successor rules, variables, or verifier-style wording.

Active-pattern overlap rule

For overlap penalties, first ask: "What lower-order pattern must be active?" Do not infer an overlap term as "all combinations inside a wider window" unless the task explicitly defines it that way.

Use this workflow:

1. Build the active set of primitive ordered patterns.
2. Check overlap through membership in that active set.
3. Add only the cost specified for that overlapping pattern pair.

Generic template:

active = set()
for start in eligible_starts:
    active.add(tuple(item_at_position(start, offset) for offset in primitive_offsets))

overlap_count = 0
for extended_tuple in candidate_extended_tuples:
    left = primitive_left(extended_tuple)
    right = primitive_right(extended_tuple)
    if left in active and right in active:
        overlap_count += overlap_cost(extended_tuple, left, right)

Common wrong shortcut:

for window in all_length_4_windows:
    for triple in combinations(window, 3):
        overlap_count += triplet_count[triple]

That shortcut is correct only when the objective explicitly says the overlap term is all triples contained in each length-4 window.

Before implementing any overlap term, write down:

• primitive pattern;
• active-start set;
• overlap membership rule;
• overlap cost formula.

Start-position masks and boundary rules

Many sequencing objectives score only certain starts, such as same-shift starts, calendar-day starts, route-leg starts, or valid short-horizon starts. Keep these masks separate from the tuple weights.

A reliable pattern is:

for start in eligible_starts[component_name]:
    ordered_tuple = tuple(item_at_position(start, offset) for offset in offsets)
    component += weight_table.get(ordered_tuple, 0)

Do not infer additional boundary windows from prose. Use the starts, successor rules, and component definitions supplied by the instance.

If the ordered positions are labeled, do not assume labels are contiguous integers unless the instance says so. Build a successor map from the declared ordered position list:

ordered_positions = list(instance["all_positions"])
successor = {
    pos: ordered_positions[idx + 1]
    for idx, pos in enumerate(ordered_positions[:-1])
}

Then evaluate windows by following the successor relation. This avoids mixing up slot labels with zero-based array positions.

Objective semantics audit

Before finalizing a model or heuristic, answer these questions in code comments or the formulation:

• What is the ordered sequence being produced?
• Are pair and tuple tables ordered, unordered, or explicitly symmetric?
• Which start positions are eligible for each component?
• What successor relation defines "next"?
• Are overlap terms all subsets, active overlapping windows, or explicit variables?
• Are missing tuple rows zero or invalid?

Then create a pure evaluate(sequence, data) function before writing outputs. The evaluator must depend only on input data and the final sequence, not solver variables. Use it to audit any solution found by a solver or local search.

Common mistakes

• Modeling unordered combinations when the objective is ordered.
• Sorting or symmetrizing tuple keys without permission.
• Summing both directions of a pair because both rows exist in the input.
• Summing every permutation of a triplet because the data table is complete.
• Counting every combination inside a larger horizon instead of the defined sliding or overlapping windows.
• Confusing position labels with zero-based array indices.
• Creating window variables but forgetting no-repetition restrictions.
• Creating auxiliary variables without lower-bound linking constraints.
• Applying cyclic wraparound to reported metrics when only the model continuity is cyclic.
• Dropping high-order objective terms to make the model smaller.