Relief Allocation - DeciDB Examples

THE PROBLEM

A relief agency ships supplies from depots to regions along fixed routes. Opening a depot costs money once; shipping along a route costs money per unit. A depot can only ship what it has in stock, and a region marked critical must have its demand met. The goal is to cover the critical demand at the lowest total cost. The depot decision belongs to the depot, not to each route it serves, so its opening cost must be charged once no matter how many routes the join produces.

SAMPLE DATA

CREATE TABLE Depots (
    depotID VARCHAR, stock INTEGER, opening_cost INTEGER
);
INSERT INTO Depots VALUES
    ('D1', 800, 12000),
    ('D2', 500, 8000);

CREATE TABLE Routes (
    routeID VARCHAR, depotID VARCHAR, regionID VARCHAR,
    capacity INTEGER, unit_cost INTEGER
);
INSERT INTO Routes VALUES
    ('T1', 'D1', 'R1', 500, 6),
    ('T2', 'D1', 'R2', 350, 6),
    ('T3', 'D2', 'R2', 300, 3);

CREATE TABLE Regions (
    regionID VARCHAR, demand INTEGER, priority VARCHAR
);
INSERT INTO Regions VALUES
    ('R1', 450, 'critical'),
    ('R2', 600, 'standard');

THE QUERY

SELECT routeID, depotID, regionID, open, ship
FROM Depots D JOIN Routes T USING (depotID) JOIN Regions R USING (regionID)
DECIDE D.open(BOOL), T.ship(INT)
SUCH THAT ship BETWEEN 0 AND capacity * open
  AND SUM(ship) <= stock PER depotID
  AND SUM(ship) >= demand WHEN priority = 'critical' PER regionID
MINIMIZE SUM(unit_cost * ship) + SUM(D: opening_cost * open)
ORDER BY routeID;

QUERY BREAKDOWN

1

DECIDE D.open(BOOL), T.ship(INT) — Two table-scoped decisions. open has one value per depot and ship one value per route, however many rows the three-way join produces.

2

ship BETWEEN 0 AND capacity * open — A route ships nothing unless its depot is open, and never more than the route's capacity. A decision may appear in the bound of a BETWEEN.

3

SUM(ship) <= stock PER depotID — One constraint per depot, bounded by that depot's own stock column.

4

SUM(ship) >= demand WHEN priority = 'critical' PER regionID — WHEN keeps only the critical regions, then PER writes one constraint for each of them.

5

SUM(D: opening_cost * open) — The relation qualifier D: reduces over the depots themselves, so each depot contributes its opening cost once. The unqualified SUM(opening_cost * open) would charge D1 once for each route it serves.

RESULT

routeID	depotID	regionID	open	ship
T1	D1	R1	1	450
T2	D1	R2	1	0
T3	D2	R2	0	0

INTERPRETATION

R1 is the only critical region, and only route T1 reaches it, so T1 must carry the full demand of 450 — within its capacity of 500 and within D1's stock of 800. Opening D1 is therefore unavoidable, and its 12,000 is paid once. R2 is standard, so nothing has to reach it: T2 ships 0, and D2 stays shut rather than paying 8,000 to open. Total cost is 12,000 for D1 plus 450 × 6 = 2,700 of shipping. Because open is scoped to Depots, both rows carrying D1 report the same value, and SUM(D: opening_cost * open) counts that depot once.