SCIP - assignment with task sizes
Problem: assign every task to exactly one worker while each worker stays under a capacity limit and total assignment cost is minimized.
Show code
import { initMPSolver, MPSolver, setWorkerBridgeEnabled } from 'or-tools-wasm/mp-solver';
const costs = [
[90, 76, 75, 70, 50, 74, 12, 68],
[35, 85, 55, 65, 48, 101, 70, 83],
[125, 95, 90, 105, 59, 120, 36, 73],
[45, 110, 95, 115, 104, 83, 37, 71],
[60, 105, 80, 75, 59, 62, 93, 88],
[45, 65, 110, 95, 47, 31, 81, 34],
[38, 51, 107, 41, 69, 99, 115, 48],
[47, 85, 57, 71, 92, 77, 109, 36],
[39, 63, 97, 49, 118, 56, 92, 61],
[47, 101, 71, 60, 88, 109, 52, 90],
];
const taskSizes = [10, 7, 3, 12, 15, 4, 11, 5];
const totalSizeMax = 15;
setWorkerBridgeEnabled(true);
await initMPSolver();
const solver = MPSolver.CreateSolver('SCIP');
if (!solver) throw new Error('SCIP backend is unavailable');
solver.SetNumThreads(4);
const x = costs.map((row, worker) =>
row.map((_, task) => solver.BoolVar(`x[${worker},${task}]`)));
for (let worker = 0; worker < costs.length; worker++) {
const capacity = solver.Constraint(-solver.infinity(), totalSizeMax);
for (let task = 0; task < taskSizes.length; task++) {
capacity.SetCoefficient(x[worker][task], taskSizes[task]);
}
}
for (let task = 0; task < taskSizes.length; task++) {
const assignedOnce = solver.Constraint(1, 1);
for (let worker = 0; worker < costs.length; worker++) {
assignedOnce.SetCoefficient(x[worker][task], 1);
}
}
const objective = solver.Objective();
for (let worker = 0; worker < costs.length; worker++) {
for (let task = 0; task < taskSizes.length; task++) {
objective.SetCoefficient(x[worker][task], costs[worker][task]);
}
}
objective.SetMinimization();
const status = await solver.Solve();
console.log(status, objective.Value());
Adapted from ortools/linear_solver/samples/assignment_task_sizes_mip.py.
This is a binary MIP with 80 decision variables, capacity constraints, and exactly-one assignment constraints.
Model
- Each worker-task pair is a binary decision variable.
- Every task must be assigned to exactly one worker.
- Each worker has a capacity limit based on task sizes.
- The objective minimizes total assignment cost while respecting worker capacity.
Run the solver to view the assignment.
Status / Response: