🧩 Constraint Solving POTD:Problem of the Day: Weighted Interval Scheduling

[github-actions[bot]]

Problem Statement

Given a set of jobs (intervals), each with a start time, end time, and profit (or weight), select a subset of non-overlapping jobs that maximizes total profit. Two jobs conflict if their intervals overlap (i.e., job i and job j conflict if start_i < end_j and start_j < end_i).

Concrete Instance

Suppose you have 6 jobs:

Job	Start	End	Profit
1	1	3	5
2	2	5	6
3	4	6	5
4	6	9	4
5	7	8	3
6	8	10	7

Goal: Select jobs so no two overlap and the total profit is maximized.
Optimal solution: Select jobs {1, 3, 6} with total profit = 5 + 5 + 7 = 17.

Input/Output

• Input: n jobs, each with (start_i, end_j, profit_i)
• Output: A subset S of jobs such that no two jobs in S overlap, and the total profit is maximized

---

Why It Matters

• Resource scheduling: Allocate conference rooms, operating theaters, or equipment to multiple demand intervals
• Media broadcasting: Maximize ad revenue by selecting which advertisements to air within constrained time slots
• Manufacturing: Schedule machine jobs to minimize idle time while respecting due dates and maximizing output value
• Cloud computing: Allocate virtual machines to instances with highest revenue per time unit

This problem bridges classical optimization and real-world scheduling constraints—it's simple to state but offers rich algorithmic insights.

---

Modeling Approaches

Approach 1: Dynamic Programming (Classical)

Paradigm: Declarative optimization via value iteration

Sort jobs by end time. Let dp[i] = maximum profit using jobs from 1 to i. For each job i, decide: include it (add profit_i to dp[p(i)], where p(i) is the latest job ending before job i starts) or skip it (take dp[i-1]).

Pros:

• Polynomial-time O(n log n + n2) solution
• Optimal for medium-scale instances
• No solver needed; pure algorithmic approach

Cons:

• Not easily extended to variant constraints (e.g., precedence, resource limits)
• Requires problem-specific algorithm design

Recurrence:

dp[0] = 0
For i = 1 to n:
  dp[i] = max(profit[i] + dp[p(i)], dp[i-1])

Approach 2: Integer Linear Programming (MIP)

Paradigm: Constraint and optimization modeling

Define binary variable x_i ∈ {0, 1} for each job (1 = select, 0 = skip).

Decision variables:

• x_i ∈ {0, 1} for job i

Constraints:

• For each pair of conflicting jobs (i, j): x_i + x_j ≤ 1
• Implicit: total profit is Σ profit_i × x_i

Objective:

• Maximize Σ profit_i × x_i

Pros:

• General framework; easily extends to multi-resource variants
• Solvers (CPLEX, Gurobi, SCIP) apply advanced techniques (branch-and-cut, presolve)
• Scales to thousands of jobs

Cons:

• Slower than specialized DP for pure interval scheduling
• Requires explicit conflict enumeration (O(n2) constraints in worst case)

Approach 3: Constraint Programming with Global Constraints

Paradigm: Declarative constraint satisfaction with specialized propagators

Use a global cumulative-style constraint or custom no_overlap predicate.

Pseudo-code (MiniZinc-like):

var set of 1..n: jobs;
constraint forall(i, j in jobs where i < j)(
  end[i] ≤ start[j] \/ end[j] ≤ start[i]
);
maximize sum(i in jobs)(profit[i]);

Pros:

• Expressive; naturally encodes problem structure
• Constraint propagation can prune search space efficiently
• Easier to add variant constraints (e.g., max k jobs, resource usage)

Cons:

• Slower than DP for pure interval scheduling on small instances
• Solver selection matters significantly

Example Model (MiniZinc Pseudo-code)

% Weighted Interval Scheduling in MiniZinc
int: n;
array[1..n] of int: start_time;
array[1..n] of int: end_time;
array[1..n] of int: profit;

% Decision: select[i] = 1 if job i is selected, 0 otherwise
array[1..n] of var 0..1: select;

% No two selected jobs can overlap
constraint forall(i, j in 1..n where i < j)(
  select[i] + select[j] <= 1 \/ 
  end_time[i] <= start_time[j] \/ 
  end_time[j] <= start_time[i]
);

% Objective: maximize total profit
maximize sum(i in 1..n)(profit[i] * select[i]);

---

Key Techniques

1. Sorting and Preprocessing

Sorting jobs by end time is crucial for the DP approach. It reduces the recurrence to O(n) after O(n log n) preprocessing. For any model, removing dominated jobs (subsumed by better alternatives) tightens bounds.

2. Binary Search for Latest Compatible Job

In DP, finding p(i) (the latest job ending before job i) via binary search reduces overall complexity from O(n2) to O(n log n). This is a classic trick for interval problems.

3. Symmetry Breaking and Lower Bounds (MIP/CP)

• If two jobs have identical (start, end) times, only keep the highest-profit one.
• Lower bound: sort jobs by profit/duration ratio and greedily select; use this to prune the branch-and-bound tree.
• Symmetry: force jobs to be selected in order (break some equivalent orderings).

4. Greedy Heuristics as Initial Bounds

Greedy algorithms—e.g., "select earliest-ending non-conflicting job" or "select highest-profit non-conflicting job"—rarely give optimal solutions but provide fast initial upper/lower bounds, accelerating solver convergence.

---

Challenge Corner

Can you solve a constrained variant?

Extend the problem: each selected job consumes a resource (e.g., staff hours). If you have a limited resource budget B, how does the model change? Can you still use DP? What if jobs now have precedence constraints (job i must finish before job j can start)?

Deeper question: The unweighted interval scheduling problem (maximize number of non-overlapping jobs) is solved greedily in O(n log n). Why doesn't the greedy approach work when profits are added? Can you construct a small counterexample?

---

References

1. Kleinberg, J. & Tardos, É. (2006). Algorithm Design (Chapters 6–7). Pearson. — Classic DP coverage with interval scheduling as a starred example.

2. Williams, H. P. (2013). Model Building in Mathematical Programming (5th ed.). Wiley. — MIP modeling perspective on scheduling problems.

3. Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming (Chapter 11). Elsevier. — Global constraints and constraint propagation for scheduling.

4. Skiena, S. S. (2020). The Algorithm Design Manual (3rd ed.), Section 7.6. — Accessible treatment with implementation guidance.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · ~12 AIC · ⌖ ~7 AIC · ⊞ 6.7K · ◷

• expires on Nov 6, 2026, 3:31 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #73489.