Hard Constraints vs Soft Constraints in CP-SAT

The distinction: forbidden vs expensive

Every rule in a CP-SAT scheduling model falls into one of two categories. A hard constraint must be satisfied. If the solver cannot find a solution that respects all hard constraints simultaneously, it returns INFEASIBLE. No schedule is produced. A soft constraint can be violated, but each violation adds a penalty to the objective function. The solver minimises the total penalty, so it tries to satisfy soft constraints, but it will break them if doing so produces a better overall schedule.

The critical question when designing a model is: "What happens when this rule is violated?" If the answer is "the schedule is illegal," the rule is a hard constraint. If the answer is "the schedule is suboptimal but usable," the rule is a soft constraint.

Getting this distinction wrong has real consequences. Too many hard constraints and the solver returns INFEASIBLE when a usable schedule exists. Too many soft constraints and the solver produces schedules that violate regulations. The art of constraint modelling is finding the right boundary.

Hard constraints in scheduling

Hard constraints encode rules that cannot be broken under any circumstances. In employee scheduling, these are typically legal requirements, physical impossibilities, or pre-existing commitments.

One shift per day

# For each employee e, for each day d:
sum(assign[e, d, s] for s in all_shifts) <= 1

An employee cannot work two shifts in the same day. This is a physical constraint: a person cannot be in two places at once. There is no scenario where violating this is acceptable, so it must be hard.

Qualification enforcement

# If employee e is not qualified for shift s:
assign[e, d, s] = 0  (for all days d)

A security agent cannot be assigned to a logistics shift if they do not hold the logistics qualification. This is a regulatory requirement. Violating it means unqualified staff in safety-critical positions.

Pre-assigned absences

# HOLIDAY, VACATION, FIXED_OFF on day d for employee e:
assign[e, d, s] = 0  (for all shifts s)
is_off[e, d] = 1

If an employee is on approved vacation, the solver cannot schedule them. The vacation was agreed before the schedule was generated. Overriding it would break a contractual commitment.

Minimum 11-hour rest period

# For each toxic pair (s1, s2), for each employee e, for each day d:
assign[e, d, s1] + assign[e, d+1, s2] <= 1

Labour law mandates a minimum rest period between shifts. We pre-compute "toxic pairs" of shifts that would violate the 11-hour rule and forbid them. This is a legal constraint that protects employee health and safety.

Soft constraints and penalties

Soft constraints encode goals the solver should pursue, but can sacrifice when necessary. Each violation costs a penalty. The solver minimises the sum of all penalties: lower is better.

Coverage (penalty: 10,000 per missing slot)

# For each function f, for each day d:
assigned = sum(assign[e, d, s] for e qualified for f, s in function f)
missing = max(0, need[f, d] - assigned)
penalty += missing * WEIGHT_COVERAGE

The highest-priority soft constraint. An uncovered shift means an operational gap. But making coverage hard would mean that any staffing shortage (vacations, sick leave) makes the entire schedule INFEASIBLE. Coverage is soft so the solver can produce the best possible schedule even when there are not enough people.

Weekend guarantee (penalty: 5,000)

# For each non-student employee e:
has_weekend_off = max over all weekends w of:
    (is_off[e, saturday_w] AND is_off[e, sunday_w])
penalty += (1 - has_weekend_off) * WEIGHT_WEEKEND

Every employee should get at least one full weekend off per month. This is a quality-of-life goal, not a legal mandate. In peak periods, the solver may need to skip a weekend for some employees to maintain coverage.

Consecutive working days (penalty: 2,000)

# For each employee e, for each window of 7 consecutive days:
if all 7 days are worked: penalty += WEIGHT_CONSECUTIVE

Working more than 6 consecutive days is undesirable but sometimes unavoidable. This is the classic case of a constraint that sits on the boundary between hard and soft (more on this below).

Days off (penalty: 1,500 per missing day)

# For each employee e:
actual_off = sum(is_off[e, d] for d in month)
missing_off = max(0, target_off[e] - actual_off)
penalty += missing_off * WEIGHT_DAYS_OFF

Each employee has a target number of days off based on their contract. The solver tries to meet the target, but can fall short if coverage demands require it.

Isolated days off (penalty: 1,000)

# For each employee e, for each day d (not first or last):
if is_off[e, d] AND NOT is_off[e, d-1] AND NOT is_off[e, d+1]:
    penalty += WEIGHT_ISOLATED_OFF

A single day off sandwiched between two working days is less restful than consecutive days off. The solver prefers clustering days off together.

Qualification equity (penalty: 500 per gap unit)

# For each group g, for each function f:
gap = max_shifts[g, f] - min_shifts[g, f]
penalty += gap * WEIGHT_QUALIF_EQUITY

Within each group, shifts should be distributed fairly across qualification types. Employees with holidays or vacations are excluded from the equity calculation.

Workload equity (penalty: 50 per gap unit)

# For each group g:
gap = max_days_worked[g] - min_days_worked[g]
penalty += gap * WEIGHT_WORKLOAD_EQUITY

The lowest-priority objective. The solver will sacrifice workload equity to preserve any higher-priority goal.

When a hard constraint becomes soft

The classic example is consecutive working days. Labour law says an employee should not work more than 6 consecutive days. The instinct is to encode this as hard. But consider what happens during a staffing shortage.

Imagine a team of 20 employees where 5 are on vacation in the same week. The remaining 15 must cover all shifts. With consecutive days as a hard constraint, the solver cannot find any assignment that covers all shifts without someone working 7 days in a row. The result: INFEASIBLE. No schedule at all.

Now make consecutive days soft with a penalty of 2,000. The solver finds a solution where 3 employees work 7 consecutive days, but every shift is covered. The planner sees the violations in the report, understands the trade-off, and decides whether to approve the schedule or adjust the input data (e.g. reassign a vacation day).

The soft version is strictly better: it gives the planner a usable schedule plus a clear warning, instead of no schedule at all.

The decision framework

Use this mental flowchart when deciding how to encode a rule:

Is the rule a legal or safety requirement?
  YES --> Can the schedule still be usable if violated?
            YES --> Soft (high penalty)
            NO  --> Hard
  NO  --> Is the rule a quality-of-life preference?
            YES --> Soft (medium/low penalty)
            NO  --> Is it a physical impossibility?
                      YES --> Hard
                      NO  --> Soft

Most scheduling rules fall into the "soft with high penalty" category. The only truly hard constraints are physical impossibilities (one shift per day, qualification requirements) and irrevocable commitments (pre-assigned absences, rest periods mandated by law without exception).

Penalty hierarchy

The penalty weights create a priority system. The solver will sacrifice lower-priority objectives to preserve higher-priority ones. Here is the hierarchy we use in production:

Objective	Penalty weight	Priority
Missing coverage	Very high	Highest
No weekend guaranteed	High	High
Consecutive days > 6	High	High
Missing days off	Medium	Medium
Isolated day off	Medium	Medium
Qualification equity gap	Low	Low
Workload equity gap	Very low	Lowest

The rationale: an uncovered shift (highest weight) is always worse than a missing day off (medium weight). A missing day off is worse than a slightly unfair distribution. Coverage is always the highest penalty because an uncovered shift means an operational failure, while any other violation is a quality issue that can be reviewed and accepted.

The gaps between penalty levels matter. Coverage at 10,000 is 2x the weekend penalty at 5,000, meaning the solver would skip one employee's weekend before leaving a shift uncovered. But it would not skip two weekends (highest weight) unless it had to leave a full shift uncovered otherwise.

Debugging INFEASIBLE

When CP-SAT returns INFEASIBLE, it means the hard constraints conflict with each other. There is no possible assignment of variables that satisfies all of them simultaneously. This is never caused by soft constraints, since those can always be violated.

Common causes

• Too many absences + too few qualified staff. If 10 out of 12 security agents are on vacation, and the daily need is 3, the solver cannot cover all days with only 2 available agents (one shift per day means each agent can only cover one day at a time, but they can work every day). The real issue is usually a combination of absences and qualification scarcity.
• Conflicting fixed assignments. An employee has a FIXED_OFF on a day where they also have a mandatory shift assigned elsewhere in the data. Two hard constraints that directly contradict each other.
• Rest period impossibilities. The combination of shift timings and mandatory rest periods makes it impossible to create any valid sequence for some employees.

Debugging approach

# Step 1: Remove all soft constraints and solve with only hard constraints
#         If still INFEASIBLE, the conflict is in the hard constraints

# Step 2: Relax hard constraints one at a time
#         Remove qualification enforcement --> still INFEASIBLE?
#         Remove rest period constraints --> still INFEASIBLE?
#         Remove absence constraints --> now FEASIBLE?
#         --> The conflict involves absences

# Step 3: Narrow down
#         Re-add constraints, removing one employee's absences at a time
#         --> Employee X's absences cause the conflict

# Step 4: Decide
#         Option A: Adjust input data (move Employee X's vacation)
#         Option B: Convert the conflicting hard constraint to soft

In practice, the most common fix is to convert a hard constraint to soft with a high penalty. The second most common is to adjust the input data (fewer simultaneous absences, different qualification assignments).

Real-world example

A planner enters 15 employees on vacation in the same week. The operation has 40 employees total across 4 functional groups. Daily needs require 25 employees working each day.

Scenario A: all constraints hard

With consecutive days as a hard constraint (max 6), the solver returns INFEASIBLE. The 25 remaining employees cannot cover 7 days of needs (175 shift-days required) while each working at most 6 days (150 shift-days available). The planner gets no schedule and no guidance on what to change.

Scenario B: consecutive days as soft

With consecutive days as a soft constraint (penalty 2,000), the solver finds a solution. 3 employees work 7 consecutive days. All shifts are covered. The penalty report shows:

Coverage gaps:         0  (penalty:      0)
Weekend violations:    2  (penalty: 10,000)
Consecutive > 6:       3  (penalty:  6,000)
Missing days off:      5  (penalty:  7,500)
Isolated days off:     4  (penalty:  4,000)
Equity gaps:           -  (penalty:  1,200)
--------------------------------------------
Total score:                       28,700

The planner sees that 3 employees will work 7 days straight. They can now make an informed decision: approve the schedule as-is, move one vacation to a different week, or bring in a temporary worker. The solver gave them a usable baseline and a clear picture of the trade-offs.

Design guidelines

Start with everything hard

Begin your model with all rules as hard constraints. Run the solver on realistic data. If it returns FEASIBLE, you are done. If it returns INFEASIBLE, you know exactly which rules need to become soft.

Convert to soft one rule at a time

When INFEASIBLE, do not convert all constraints to soft at once. Identify the "bendable" rules, the ones where a violation is undesirable but not catastrophic, and convert them one at a time. Test after each conversion.

Never make safety or legal constraints soft

Qualification enforcement (unqualified staff in safety-critical roles), minimum rest periods (fatigue-related safety risk), and pre-assigned absences (contractual obligations) should remain hard. If these cause INFEASIBLE, the correct response is to fix the input data, not to relax the constraint.

Coverage is always the highest penalty

An uncovered shift is worse than any quality issue. If the solver must choose between leaving a shift uncovered (highest weight) or having someone work 7 consecutive days (2,000), the right trade-off is always to fill the shift. The penalty hierarchy encodes this automatically.

Use the penalty report as a diagnostic tool

The penalty breakdown tells the planner where the schedule is weakest. If 80% of the penalty comes from coverage gaps, the problem is understaffing. If equity penalties dominate, the groups may be unbalanced. The solver does not just produce a schedule; it produces a diagnosis.

Document the rationale for each constraint type

For every constraint in the model, record why it is hard or soft. When a planner asks "why did employee X work 7 days in a row?", the answer should be traceable: "consecutive days is soft (penalty 2,000) because making it hard causes INFEASIBLE during high-absence weeks. The solver chose this violation to preserve full coverage."