🧩 Constraint Solving POTD:Problem of the Day: Generalized Assignment Problem (GAP)

[github-actions[bot]]

Problem Statement

The Generalized Assignment Problem (GAP) assigns m jobs to n agents such that:

• Each job is assigned to exactly one agent
• Each agent has a resource capacity (e.g., time, budget, workload limit)
• Assignment of job j to agent i consumes a_ij units of capacity
• Assignment has a cost c_ij
• Goal: minimize total cost while respecting all capacity constraints

Concrete Instance

Imagine a cloud resource allocation scenario:

• 3 jobs (data processing tasks)
• 2 agents (server instances with memory limits)
• Task costs (in compute units) and memory consumption (in GB):

Job	Agent 1 Cost	Agent 1 Memory	Agent 2 Cost	Agent 2 Memory	Agent Capacities
Job A	5	3 GB	8	2 GB	5 GB
Job B	7	2 GB	3	4 GB
Job C	6	3 GB	4	2 GB

Feasible assignment: Job A → Agent 2 (cost 8, memory 2), Job B → Agent 1 (cost 7, memory 2), Job C → Agent 2 (cost 4, memory 2). Total cost = 19. Agent 1 uses 2/5 GB, Agent 2 uses 4/5 GB. ✓

Infeasible assignment: Job A → Agent 1 (3 GB), Job B → Agent 1 (2 GB), Job C → Agent 1 (3 GB). Total memory = 8 GB > 5 GB capacity. ✗

---

Why It Matters

Workforce scheduling in manufacturing: Companies assign production orders to machines or workers. Each machine has limited runtime per shift; each order has a processing time and profit margin. GAP finds the assignment that maximizes profit (or minimizes cost) while keeping each resource within its shift limit.

Cloud computing & container orchestration: Kubernetes and similar platforms solve variants of GAP to place containerized workloads on physical nodes. Each container requires CPU and memory; each node has fixed capacity. Minimizing cost (e.g., number of nodes used) or latency is the objective.

Delivery route optimization in logistics: Parcels are assigned to delivery vehicles, each with weight and volume limits. GAP minimizes the number of vehicles or total route distance.

Nursing shift scheduling: Shifts are assigned to nurses with different expertise and availability constraints. GAP balances workload while minimizing labor cost or preference violations.

---

Modeling Approaches

Approach 1: Mixed-Integer Linear Programming (MIP)

Decision variables:

• x_ij ∈ {0, 1} = 1 if job j is assigned to agent i, 0 otherwise

Constraints:

• ∀j: Σ_i x_ij = 1 (each job assigned to exactly one agent)
• ∀i: Σ_j a_ij × x_ij ≤ b_i (agent capacity constraint)

Objective:

• minimize: Σ_i Σ_j c_ij × x_ij

Trade-offs:

• ✓ Expressive and widely supported (CPLEX, Gurobi, SCIP)
• ✓ Tight linear relaxations enable branch-and-bound pruning
• ✗ Can struggle with large instances (m, n > 1000)
• ✗ Requires floating-point arithmetic

Approach 2: Constraint Programming (CP)

Decision variables:

• agent_j ∈ {1..n} = assigned agent for job j
• cost_j ∈ Z = cost of assigning job j
• total_cost ∈ Z = sum of all costs

Constraints:

• ∀i: Σ_{j: agent_j = i} a_ij ≤ b_i (global capacity constraint per agent)
• ∀j: cost_j = element(agent_j, [c_1j, c_2j, ..., c_nj])
• total_cost = Σ_j cost_j

Search:

• Variable ordering: assign jobs with fewest feasible agents first
• Value ordering: try agents in increasing cost order
• Propagation: capacity constraints prune infeasible assignments early

Trade-offs:

• ✓ Declarative modeling; global constraints handle capacity naturally
• ✓ Strong propagation for capacity constraints
• ✗ Less mature for optimization (vs. feasibility)
• ✓ Good for small-to-medium instances with rich structure

Approach 3: Local Search / Simulated Annealing

Representation: Permutation π where π[j] = assigned agent for job j

Moves:

• Swap: randomly reassign one job j to a different agent
• Relocate: move a job from one agent to another

Evaluation:

• After each move, check feasibility and compute total cost
• If feasible and cost improves, accept; else accept with probability exp(-ΔC / T)

Trade-offs:

• ✓ Scales to very large instances (thousands of jobs)
• ✓ Fast approximate solutions
• ✗ No optimality guarantee
• ✗ Sensitive to temperature schedule and neighborhood structure

Example Model (Python + OR-Tools)

from ortools.linear_solver import pywraplp

# Data
n_jobs, n_agents = 3, 2
costs = [[5, 8], [7, 3], [6, 4]]  # c[job][agent]
resource = [[3, 2], [2, 4], [3, 2]]  # a[job][agent]
capacity = [5, 5]  # b[agent]

solver = pywraplp.Solver.CreateSolver('SCIP')
x = {}
for i in range(n_agents):
    for j in range(n_jobs):
        x[i, j] = solver.IntVar(0, 1, f'x_{i}_{j}')

# Each job to exactly one agent
for j in range(n_jobs):
    solver.Add(sum(x[i, j] for i in range(n_agents)) == 1)

# Capacity constraints
for i in range(n_agents):
    solver.Add(
        sum(resource[j][i] * x[i, j] for j in range(n_jobs)) <= capacity[i]
    )

# Objective: minimize cost
solver.Minimize(
    sum(costs[j][i] * x[i, j] for i in range(n_agents) for j in range(n_jobs))
)

status = solver.Solve()
print(f"Total cost: {solver.ObjectiveValue()}")
for i in range(n_agents):
    for j in range(n_jobs):
        if x[i, j].solution_value() > 0.5:
            print(f"Job {j} → Agent {i}")

---

Key Techniques

1. Arc Consistency and Capacity Propagation

In CP, as agents fill up, fewer jobs can fit on them. Constraint propagation detects this early:

• If agent i has only 2 GB left and all remaining unassigned jobs require ≥ 3 GB, prune agent i from consideration.
• This dramatically reduces the search space before branching.

2. Variable and Value Ordering in Search

• Variable ordering: Assign jobs with the fewest feasible agents first (most constrained variable). Job A with only one possible agent should be assigned before Job B with five options.
• Value ordering: When assigning job j, try agents in order of cost (increasing). This finds good solutions early, enabling branch-and-bound pruning.

3. Symmetry Breaking & Relaxation

• Relaxation: Ignore capacity constraints to get a lower bound on cost via an easy assignment problem (each job to its cheapest agent). If this lower bound exceeds the best known feasible solution, prune the branch.
• Symmetry breaking: If some agents are identical (same capacity and cost structure), break symmetry by forcing a canonical ordering (e.g., always prefer Agent 1 over Agent 2 when costs are equal).

---

Challenge Corner

For readers to explore:

1. Symmetry & Redundancy: In our cloud instance example, suppose all agents are identical (same capacity, same costs for each job). How many equivalent solutions exist? Can you add constraints to break this symmetry and speed up search?

2. Hybrid Approach: Design a hybrid algorithm that:

   • Solves the LP relaxation to get a lower bound
   • Uses the LP solution to guide a local search neighborhood
   • Periodically checks feasibility with a CP solver

   Which technique should drive which?

3. Uncertainty Extension: Suppose job costs are uncertain (uniform random within ±10% of nominal value). Model this as a robust GAP that minimizes worst-case cost. How does your model change?

---

References

1. Pentico, D. W. (2007). "Assignment Problems: A Golden Anniversary Survey." European Journal of Operational Research, 176(2), 774–793.

   • Comprehensive survey covering GAP variants, applications, and algorithms.

2. Martello, S., & Toth, P. (1981). "An Algorithm for the Generalized Assignment Problem." Proceedings of the 2nd Operational Research Society Conference.

   • Foundational branch-and-bound algorithm for GAP.

3. van Hoeve, W. J., & Miller, A. J. (2013). "Subgraph Isomorphism and Related Problems." In Handbook of Constraint Programming, Elsevier.

   • Discusses global constraints and propagation techniques applicable to assignment problems.

4. OR-Tools Documentation ((developers.google.com/redacted)

   • Practical tutorials on modeling and solving GAP with MIP and CP solvers.

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

• expires on Sep 21, 2026, 3:34 AM UTC-08:00