You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
🧩 Constraint Solving POTD:Problem of the Day: Car Sequencing
#80079
A car factory builds cars on a single assembly line. Each car is a class that needs some set of optional features (sunroof, towbar, air conditioning, ...). Each feature is installed at a station that can only handle a limited load, so the line must be ordered so that no station is overloaded in any stretch of consecutive positions.
Input
n cars, each with a set of required options R_c ⊆ {1..m}
For each option o, a capacity pair (p_o, q_o): at most p_o cars requiring o may appear in any q_o consecutive positions
Output
A permutation of the cars (a sequence) satisfying every window constraint, or proof that none exists
Small instance (6 cars, 3 options)
Car
Options
Option
(p, q)
c1
{1}
1
(1, 2)
c2
{1, 2}
2
(2, 3)
c3
{2}
3
(1, 3)
c4
{3}
c5
{2, 3}
c6
{}
One valid sequence is c2 c5 c1 c3 c4 c6. Option 2 appears at positions {1, 2, 4}, so any window of 3 holds at most 2 of them. Option 1 at positions {1, 3} never has two in a window of 2. Option 3 at positions {2, 5} never has two in a window of 3.
Why It Matters
Automotive manufacturing: Car sequencing is the textbook example of a mixed-model assembly line problem. Badly ordered lines cause paint, trim or towbar stations to fall behind, forcing line stoppages.
Any high-mix production line: Electronics, appliances and furniture lines face the same "don't overload a station in a window" structure.
Benchmark for CP research: It is listed in CSPLib (prob001) and was one of the first problems to show how a clever global propagator beats a naive decomposition.
Modeling Approaches
1. Constraint Programming: sequence variables with sliding-sum constraints
Variables: s_t ∈ {1..n} is the car at position t, with alldifferent(s_1..s_n)
Derived booleans: b_{o,t} = 1 iff the car at position t requires option o, via b_{o,t} = (s_t ∈ C_o), where C_o is the set of cars needing o
Constraint: for every window W of length q_o, Σ_{t∈W} b_{o,t} ≤ p_o
Trade-off: very readable and easy to extend with extra rules. Propagation on the b variables is weak if the window sums are decomposed naively. Stronger models use a sliding-sum or global cardinality propagator.
2. Mixed Integer Programming: assignment matrix
Variables: x_{c,t} ∈ {0,1} is 1 iff car c is placed at position t
Σ_t x_{c,t} = 1 for each car, Σ_c x_{c,t} = 1 for each position
For each option o and window W of length q_o: Σ_{t∈W} Σ_{c∈C_o} x_{c,t} ≤ p_o
Trade-off: the LP relaxation gives useful bounds when you minimise a secondary objective (for example, the number of violated windows in a soft version). The model has n2 binaries, so it scales worse than CP on large instances.
Sliding-sum / global cardinality propagation. Instead of checking each window independently, a sliding-sum constraint tracks the minimum and maximum number of required options in each window. Once a window reaches its limit p_o, the propagator forces every remaining position in that window to not require o. This is much stronger than decomposing into plain sums.
Symmetry breaking. Cars with identical option sets are interchangeable. Ordering their positions (for example, requiring the lowest-index car of a class to appear first) removes factorial symmetry without losing solutions. Many CP-SAT and Gecode models do this with lexicographic constraints.
Search heuristics. Choose the variable with the fewest remaining options (first-fail). Use dom/wdeg to learn which windows are hard, and restart search when it thrashes on large instances.
Challenge Corner
Car sequencing is often solved with a soft objective: minimise the number of violated windows. How would you encode this in your CP-SAT model, and which bound would you add to prove optimality?
Can you model the problem with only n·m booleans instead of n2? Think about the per-option demand alone.
Two cars with the same option set can be swapped without changing feasibility. What is the smallest set of symmetry-breaking constraints that removes all of these swaps?
Hard extension: the real line must also respect a minimum spacing between two cars with the same colour. How does this change the propagation strength?
References
Dincbas, M., Simonis, H., & Van Hentenryck, P. (1988). Solving the car-sequencing problem in constraint logic programming. ECAI-88. (Early CP treatment of car sequencing.)
Smith, B. M. (2006). Modelling. In Rossi, van Beek & Walsh (eds.), Handbook of Constraint Programming, Ch. 11. (Compares car sequencing models, including the sliding-sum view.)
Gent, I. P., & Walsh, T. (1999). CSPLib: a benchmark library for constraints. (Car sequencing is prob001.)
Google OR-Tools CP-SAT documentation: (developers.google.com/redacted)
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
Problem Statement
A car factory builds cars on a single assembly line. Each car is a class that needs some set of optional features (sunroof, towbar, air conditioning, ...). Each feature is installed at a station that can only handle a limited load, so the line must be ordered so that no station is overloaded in any stretch of consecutive positions.
Input
ncars, each with a set of required optionsR_c ⊆ {1..m}o, a capacity pair(p_o, q_o): at mostp_ocars requiringomay appear in anyq_oconsecutive positionsOutput
Small instance (6 cars, 3 options)
One valid sequence is
c2 c5 c1 c3 c4 c6. Option 2 appears at positions {1, 2, 4}, so any window of 3 holds at most 2 of them. Option 1 at positions {1, 3} never has two in a window of 2. Option 3 at positions {2, 5} never has two in a window of 3.Why It Matters
Modeling Approaches
1. Constraint Programming: sequence variables with sliding-sum constraints
s_t ∈ {1..n}is the car at positiont, withalldifferent(s_1..s_n)b_{o,t} = 1iff the car at positiontrequires optiono, viab_{o,t} = (s_t ∈ C_o), whereC_ois the set of cars needingoWof lengthq_o,Σ_{t∈W} b_{o,t} ≤ p_oTrade-off: very readable and easy to extend with extra rules. Propagation on the
bvariables is weak if the window sums are decomposed naively. Stronger models use a sliding-sum or global cardinality propagator.2. Mixed Integer Programming: assignment matrix
x_{c,t} ∈ {0,1}is 1 iff carcis placed at positiontΣ_t x_{c,t} = 1for each car,Σ_c x_{c,t} = 1for each positionoand windowWof lengthq_o:Σ_{t∈W} Σ_{c∈C_o} x_{c,t} ≤ p_oTrade-off: the LP relaxation gives useful bounds when you minimise a secondary objective (for example, the number of violated windows in a soft version). The model has
n2binaries, so it scales worse than CP on large instances.Example Model (OR-Tools CP-SAT, Python)
Key Techniques
p_o, the propagator forces every remaining position in that window to not requireo. This is much stronger than decomposing into plain sums.dom/wdegto learn which windows are hard, and restart search when it thrashes on large instances.Challenge Corner
n·mbooleans instead ofn2? Think about the per-option demand alone.References
All reactions