FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

Set covering

Description
A mobile phone operator decides to equip a currently uncovered geographical zone. A budget is allocated to equip this region. 7 locations are possible for the construction of the transmitters. Every transmitter only covers a certain number of communities. For every community the number of inhabitants is known. Where should the transmitters be built to cover the largest population with the given budget?

Further explanation of this example: 'Applications of optimization with Xpress-MP', Section 12.6 'Location of GSM transmitters' (g6transmit.mos). Similar problems: Section 9.5 'Cutting of sheet metal' (d5cutsh.mos), Section 15.2 'CCTV surveillance' (j2bigbro.mos)

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.

Data Files

covering_graph.mos

(!******************************************************
Mosel Example Problems
======================

file covering.mos

TYPE:         Covering problem
DIFFICULTY:   2
FEATURES:     MIP problem, modeling an equivalence; sparse data format,
graphical output representation, 'if-then-else'
DESCRIPTION:  A mobile phone operator decides to equip a currently
uncovered geographical zone. A budget is allocated to equip
this region. 7 locations are possible for the construction
of the transmitters. Every transmitter only covers a certain
number of communities. For every community the number of
inhabitants is known. Where should the transmitters be built
to cover the largest population with the given budget?
FURTHER INFO: Applications of optimization with Xpress-MP',
Section 12.6 Location of GSM transmitters'.
Similar problems: Section 9.5 Cutting of sheet metal',
Section 15.2 CCTV surveillance'

(c) 2008 Fair Isaac Corporation
author: S. Heipcke, 2002, rev. Sep. 2017
*******************************************************!)

model "Transmitter placement"
uses "mmxprs", "mmsvg"

declarations
COMMS = 1..15                         ! Set of communities
PLACES = 1..7                         ! Set of possible transm. locations

COST: array(PLACES) of real           ! Cost of constructing transmitters
COVER: array(PLACES,COMMS) of integer ! Coverage by transmitter locations
POP: array(COMMS) of integer          ! Number of inhabitants (in 1000)
BUDGET: integer                       ! Budget limit

build: array(PLACES) of mpvar         ! 1 if transmitter built, 0 otherwise
covered: array(COMMS) of mpvar        ! 1 if community covered, 0 otherwise
end-declarations

initializations from 'covering.dat'
COST COVER POP BUDGET
end-initializations

! Objective: total population covered
Coverage:= sum(c in COMMS) POP(c)*covered(c)

! Towns covered
forall(c in COMMS)
CoverTown(c):= sum(p in PLACES) COVER(p,c)*build(p) >= covered(c)

! Budget limit
BudgetLim:= sum(p in PLACES) COST(p)*build(p) <= BUDGET

forall(p in PLACES) build(p) is_binary
forall(c in COMMS) covered(c) is_binary

! Solve the problem
maximize(Coverage)

! Solution printing
writeln("Total coverage: ", getobjval, " total cost: ",
getsol(sum(p in PLACES) COST(p)*build(p)))
write("Build transmitters:")
forall(p in PLACES) write(if(getsol(build(p))>0, " "+p, ""))
write("\nCommunities covered:")
forall(c in COMMS) write(if(getsol(covered(c))>0, " "+c, ""))
writeln

! Solution drawing
declarations
XT,YT: array(PLACES) of integer       ! x-y-coordinates for transmitters
XC,YC: array(COMMS) of integer        ! x-y-coordinates of communities
end-declarations

initializations from 'covering.dat'
[XT,YT] as 'POST'
[XC,YC] as 'POSC'
end-initializations

svgsetgraphviewbox(10,10,110,75)
svgsetgraphscale(2)

svgaddgroup("CovGraph", "Communities covered", SVG_BLACK)
svgaddgroup("UncGraph", "Communities not covered", svgcolor(150,150,150))
forall(c in COMMS) do
if(getsol(covered(c))>0) then
svgaddtext("CovGraph", XC(c)+1, YC(c)+1, text(c))
else
svgaddtext("UncGraph", XC(c)+1, YC(c)+1, text(c))
end-if
end-do

svgaddgroup("LocGraph", "Possible locations", svgcolor(120,0,0))
svgsetstyle(SVG_FILL,SVG_CURRENT)
svgaddgroup("BuildGraph", "Chosen locations", SVG_RED)
svgsetstyle(SVG_FILL,SVG_CURRENT)
forall(p in PLACES)
if(getsol(build(p))>0) then
svgaddcircle("BuildGraph", XT(p), YT(p), 1)
svgaddtext("BuildGraph", XT(p)+1, YT(p)+1, text(p))
forall(c in COMMS)
if(COVER(p,c)>0) then
svgaddline("BuildGraph", XT(p), YT(p), XC(c), YC(c))
end-if
else
svgaddcircle("LocGraph", XT(p), YT(p), 1)
svgaddtext("LocGraph", XT(p)+1, YT(p)+1, text(p))
end-if

svgsave("covering.svg")
svgrefresh
svgwaitclose("Close browser window to terminate model execution.", 1)
end-model

`