Ordered Window Sequencing Mip

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.