Feasibility: Constraint Satisfaction

THE PROBLEM

A hospital needs to cover three daily shifts (Morning, Afternoon, Night) using a pool of four nurses. The rules are simple: every shift must have at least one nurse, and no nurse can work more than one shift per day. There is no score to maximize or cost to minimize — the goal is just to find any valid schedule that satisfies all constraints. This is a feasibility problem: omitting the objective clause tells DeciDB to return the first satisfying assignment it finds.

SAMPLE DATA

CREATE TABLE assignments (
    nurse_id INTEGER, nurse_name VARCHAR,
    shift_id INTEGER, shift_name VARCHAR
);
INSERT INTO assignments VALUES
    (1, 'Alice', 1, 'Morning'),
    (1, 'Alice', 2, 'Afternoon'),
    (1, 'Alice', 3, 'Night'),
    (2, 'Bob',   1, 'Morning'),
    (2, 'Bob',   2, 'Afternoon'),
    (2, 'Bob',   3, 'Night'),
    (3, 'Carol', 1, 'Morning'),
    (3, 'Carol', 2, 'Afternoon'),
    (4, 'Dan',   2, 'Afternoon'),
    (4, 'Dan',   3, 'Night');

THE QUERY

SELECT nurse_name, shift_name, assigned
FROM assignments
DECIDE assigned(BOOL)
SUCH THAT
    SUM(assigned) >= 1 PER shift_id AND
    SUM(assigned) <= 1 PER nurse_id
ORDER BY nurse_id, shift_id;

QUERY BREAKDOWN

1

DECIDE assigned(BOOL) — One binary variable per row. Each row represents one nurse–shift pair; assigned=1 means "this nurse works this shift".

2

SUM(assigned) >= 1 PER shift_id — For each distinct shift, at least one nurse must be assigned. The PER keyword generates one copy of this constraint per distinct value of shift_id — no hardcoded shift IDs needed.

3

SUM(assigned) <= 1 PER nurse_id — Each nurse works at most one shift. Again, one constraint per distinct nurse ID, derived from the data.

4

No MAXIMIZE or MINIMIZE — This is a feasibility query. DeciDB finds any valid assignment and returns it. If no assignment satisfies all constraints, the query reports infeasibility.

RESULT

nurse_name	shift_name	assigned
Alice	Morning	1
Alice	Afternoon	0
Alice	Night	0
Bob	Morning	0
Bob	Afternoon	0
Bob	Night	1
Carol	Morning	0
Carol	Afternoon	1
Dan	Afternoon	0
Dan	Night	0

INTERPRETATION

This is one valid schedule: Alice covers Morning, Carol covers Afternoon, and Bob covers Night. Dan is not assigned. Every shift has at least one nurse (SUM(assigned) >= 1 PER shift_id), and no nurse works more than one shift (SUM(assigned) <= 1 PER nurse_id). This problem has more than one equally good answer. DeciDB returns one of them — a shift may come back with two nurses on it, since the constraint asks for at least one. Write SUM(assigned) = 1 PER shift_id to require exactly one. To choose among valid schedules on some measure, such as total seniority, add a MAXIMIZE clause.