Loading solver…
MPSolver - network design MIP
Problem: decide which shipping lanes to open, then route demand through the opened network at minimum fixed plus variable cost.
Show code
import { MPSolver } from 'or-tools-wasm/mp-solver';
const solver = MPSolver.createSolver('SCIP');
solver.setNumThreads(4);
const open = arcs.map((arc) => solver.addBoolVariable(`open_${arc.id}`));
const flow = arcs.map((arc) =>
demands.map((demand) => solver.addNumVariable(0, solver.infinity(), `flow_${arc.id}_${demand.id}`)));
for (const [arcIndex, arc] of arcs.entries()) {
const capacity = solver.addConstraint(-solver.infinity(), 0);
capacity.setCoefficient(open[arcIndex], -arc.capacity);
for (const demandIndex of demands.keys()) {
capacity.setCoefficient(flow[arcIndex][demandIndex], 1);
}
}
for (const [demandIndex, demand] of demands.entries()) {
for (const node of nodes) {
const rhs = node.id === demand.from ? demand.amount : node.id === demand.to ? -demand.amount : 0;
const conservation = solver.addConstraint(rhs, rhs);
for (const [arcIndex, arc] of arcs.entries()) {
if (arc.from === node.id) conservation.setCoefficient(flow[arcIndex][demandIndex], 1);
if (arc.to === node.id) conservation.setCoefficient(flow[arcIndex][demandIndex], -1);
}
}
}
const objective = solver.objective();
for (const [arcIndex, arc] of arcs.entries()) {
objective.setCoefficient(open[arcIndex], arc.fixedCost);
for (const demandIndex of demands.keys()) {
objective.setCoefficient(flow[arcIndex][demandIndex], arc.unitCost);
}
}
objective.setMinimization();
await solver.solve({ executor: 'worker' });
- This is a mixed-integer linear program: lane-open decisions are binary, shipment flows are continuous.
- Opening a lane pays a fixed cost even before any shipment moves on it.
- Each shipment demand must be conserved through the network from source to destination.
- A lane can carry flow only if it is opened, and its total flow cannot exceed capacity.
- Hover a demand or an opened lane after solving to see the related routes.
Solution
Run the solver to choose lanes and route shipments.
Status / Response: