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: