Coverage Model

Demand Points

Set covering starts with demand points that must each be covered at least once.

highlighted = computed this step

Demand points

The demand points are 1 through 5. Motivation: every point must be covered.

points={1,…,5}\text{points}=\{1,\ldots,5\}
Coverage gridRows are sites and columns are demand points.chosen rows cover every pointchosen cost 9chosen rows A+B+Cpoint 1point 2point 3point 4point 5Acost 3covercover---Bcost 4-covercovercover-Ccost 2---covercoverDcost 6can---cancoveredcoveredcoveredcoveredcoveredfeasible cover

Cover all

A feasible answer covers all 5 demand points.

covered points=5\text{covered points}=5
Coverage gridRows are sites and columns are demand points.chosen rows cover every pointchosen cost 9chosen rows A+B+Cpoint 1point 2point 3point 4point 5Acost 3covercover---Bcost 4-covercovercover-Ccost 2---covercoverDcost 6can---cancoveredcoveredcoveredcoveredcoveredfeasible cover

Choose sites

A site row can cover several points. The job is to choose rows that leave no missing point.

choose rows so every column is covered\text{choose rows so every column is covered}
Coverage gridRows are sites and columns are demand points.chosen rows cover every pointchosen cost 9chosen rows A+B+Cpoint 1point 2point 3point 4point 5Acost 3covercover---Bcost 4-covercovercover-Ccost 2---covercoverDcost 6can---cancoveredcoveredcoveredcoveredcoveredfeasible cover

Finite model

This book uses fixed rows and fixed costs, so the arithmetic is exact.

fixed finite coverage model\text{fixed finite coverage model}
Coverage gridRows are sites and columns are demand points.chosen rows cover every pointchosen cost 9chosen rows A+B+Cpoint 1point 2point 3point 4point 5Acost 3covercover---Bcost 4-covercovercover-Ccost 2---covercoverDcost 6can---cancoveredcoveredcoveredcoveredcoveredfeasible cover