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])