🧩 Constraint Solving POTD:Problem of the Day: Resource Allocation Under Constraints

[github-actions[bot]]

Problem Statement

The Problem

You manage a set of resources (machines, workers, cloud computing units) and must allocate them to competing tasks or projects to maximize some objective while respecting constraints.

Concrete Instance

Consider a small software development team:

• Resources: 3 senior engineers, 4 junior engineers, 2 project managers, 1 DevOps specialist
• Tasks: 5 projects, each requiring specific skills and durations:
  • Project A: Needs 2 senior, 1 junior, 1 PM (8 weeks)
  • Project B: Needs 1 senior, 2 junior, 1 PM (6 weeks)
  • Project C: Needs 0 senior, 3 junior, 1 PM (5 weeks)
  • Project D: Needs 1 senior, 1 junior, 0 PM, 1 DevOps (4 weeks)
  • Project E: Needs 0 senior, 2 junior, 0 PM (7 weeks)
• Objective: Maximize total project value (A=100, B=80, C=60, D=90, E=50) while minimizing resource idle time
• Constraints:
  • Each resource can work on at most 2 projects simultaneously
  • Skills must match (e.g., junior engineers cannot substitute for seniors on critical tasks)
  • Some projects must complete within specific windows (deadline constraints)
  • Certain projects are prerequisites for others

Input/Output Specification

• Input: Resource inventory (type, quantity), task requirements, precedence graph, project deadlines, profit values
• Output: Assignment of resources to tasks, start/end times for each task, total project value achieved, resource utilization metrics

Why It Matters

Cloud Infrastructure Optimization: Data centers allocate CPUs, memory, network bandwidth, and storage to workloads. Constraint solvers optimize placement to minimize latency, power consumption, and cost while meeting SLAs. Major cloud providers use CP solvers to schedule millions of resource allocation decisions daily.

Project Management & Staff Allocation: Construction companies, consulting firms, and software development teams use resource allocation to staff projects, minimize project makespan, and avoid overallocation. Hospitals allocate nurses, surgeons, and operating rooms to surgery schedules while respecting working-hour regulations and skill requirements.

Supply Chain Planning: Manufacturers allocate production capacity, raw materials, and logistics resources across orders to meet demand, minimize inventory, and maximize profit. This is fundamental to just-in-time manufacturing and responsive supply chains.

Modeling Approaches

Approach 1: Constraint Programming (Standard)

Variables:

• assign[r,t] ∈ {0, 1}: Does resource r work on task t?
• start[t] ∈ {0..H}: Start time of task t (H = planning horizon)
• end[t] = start[t] + duration[t]

Constraints:

• Skill matching: sum_{r ∈ seniors} assign[r,t] ≥ required_seniors[t] for each task t
• Resource capacity: sum_{t} assign[r,t] · overlap(t, t') ≤ max_concurrent[r] (prevents over-allocation)
• Precedence: end[pred] ≤ start[t] for task t depending on predecessor pred
• Deadline: end[t] ≤ deadline[t] for time-sensitive tasks
• Global cardinality: global_cardinality(assign, resource_levels) ensures inventory limits

Objective: maximize sum_{t} value[t] · (all_assigned[t] ? 1 : 0) - idle_cost

Trade-offs: Expressiveness is excellent; specialized propagation (edge finding, disjunctive constraints) handles precedence and resource capacity efficiently. Scales well to 100s of resources and 1000s of tasks with good heuristics.

Approach 2: Mixed-Integer Linear Programming (MIP)

Variables:

• x[r,t] ∈ [0, 1]: Fractional or binary allocation fraction of resource r to task t
• y[t] ∈ {0, 1}: Binary indicator: is task t fully completed?
• s[t] ∈ R+: Start time of task t

Constraints:

• Resource conservation: sum_{t} x[r,t] ≤ capacity[r] for each resource r
• Task completion: sum_{r} x[r,t] ≥ required[t] · y[t] (task only counts if fully resourced)
• Precedence (disjunctive): s[t] ≥ s[pred] + duration[pred] or big-M linearization
• Time windows: s[t] + duration[t] ≤ deadline[t]

Objective: maximize sum_{t} value[t] · y[t]

Trade-offs: MIP solvers handle large-scale problems (10,000+ variables) and provide optimality guarantees via branch-and-bound. However, precedence and complex resource interactions are harder to express without big-M constants and auxiliary variables; this weakens relaxation bounds. Good for continuous or fractional allocations; pure CP is often better for hard combinatorial decisions.

Approach 3: Local Search / Metaheuristics

Variables: Permutation/sequence of tasks; resource assignment heuristic.

Neighborhood moves:

• Swap task pair in schedule (local reordering)
• Reassign a task to a different resource
• Shift task start time within feasible window

Evaluation: Fast feasibility check; move delta-evaluates objective quickly.

Trade-offs: Excellent for very large instances (10,000+ tasks) where exact methods time out. No optimality guarantee, but often finds good solutions in seconds. Simple to implement; combines well with CP (hybrid approaches: CP for structure, local search for refinement).

Example Model (MiniZinc / Pseudocode)

int: num_resources;
int: num_tasks;
array[1..num_tasks] of int: duration;
array[1..num_tasks] of int: value;
array[1..num_tasks, 1..num_resources] of 0..1: skill_match;

var 0..H: horizon;
array[1..num_tasks] of var 0..horizon: start;

% Skill matching
constraint forall(t in 1..num_tasks, r in 1..num_resources where skill_match[t,r] == 0)
  (not assigned[t,r]);

% Resource capacity: no overallocation
constraint forall(r in 1..num_resources)
  cumulative(start, duration, [assigned[t,r] | t in 1..num_tasks], 1);

% Precedence
constraint start[task2] >= start[task1] + duration[task1];

% Deadline
constraint start[task] + duration[task] <= deadline[task];

solve maximize sum(t in 1..num_tasks)(value[t] * all_assigned[t]);

Key Techniques

1. Cumulative Constraint & Edge Finding

The cumulative global constraint models resource capacity: it ensures that at any time point, the sum of resource consumption by active tasks does not exceed capacity. Edge-finding algorithms (Carlier, Cesta-Oddi) compute mandatory start/end times and prune infeasible orderings, dramatically reducing search space. This is essential for scheduling-based allocation problems.

2. Domain-Consistent Skill Matching & Channeling

Represent skills as separate decision variables (e.g., assign[r,t] for whether resource r works on task t) and post constraints linking them to the main schedule variables. Use table constraints or lexicographic ordering to encode skill compatibility. Channeling between different variable representations (e.g., task-to-resource vs. resource-to-task) enables stronger propagation.

3. Symmetry Breaking & Value Ordering Heuristics

Resources of the same type are interchangeable (symmetry). Add lexicographic ordering constraints (e.g., "if resources r1 and r2 have the same skills, break ties in allocation order"). For task ordering, use min-slack heuristic (prioritize tasks with tight deadlines) or weighted-shortest-job-first. These cut search space by 10–100×.

Challenge Corner

For the curious:

1. Can you model this with integer-indexed time only, avoiding continuous start times? Discretize the time horizon into time buckets; each bucket indicates whether a task is "active" or not. What are the trade-offs in LP relaxation tightness and constraint count?

2. What's the minimum set of symmetry-breaking constraints needed if resources are partitioned by skill level? Think about lexicographic ordering applied only across resources of the same type.

3. How would you extend this to handle uncertainty in task duration? Could you use robust optimization, stochastic programming, or online constraint relaxation? Which approach fits project management best?

References

• Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming. Elsevier. (Ch. 14–15: Scheduling and Resource Allocation.)
• Laborie, P. & Ghallab, M. (2016). "Planning with sharable resource constraints: Complexity, algorithms and experimental analysis." Artificial Intelligence, 236, 60–85.
• Hooker, J. N. (2011). "Planning and scheduling by logic-based Benders decomposition." Operations Research, 55(3), 465–478.
• Baptiste, P., Le Pape, C., & Nuijten, W. (2001). Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Kluwer Academic. (Authoritative reference on cumulative constraint algorithms.)

---

Happy constraint solving! 🧩

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 7.88 AIC · ⌖ 5.62 AIC · ⊞ 6.3K · ◷

• expires on Sep 17, 2026, 3:34 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 #60251.