 FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home   Choice of locations for income tax offices

Description
Choice of locations for income tax offices: linear, 'element', 'occurrence', 'equiv' constraints; search strategy for variables.

Further explanation of this example: 'Xpress Kalis User Guide', Section 3.9 equiv: Location of income tax offices

Source Files

Data Files

j5tax_ka.mos

```(!******************************************************
CP Example Problems
===================

file j5tax_ka.mos
`````````````````
Choice of locations for income tax offices
(See "Applications of optimization with Xpress-MP",
Section 15.5 Location of income tax offices)

The variables build(c) representing the decisions
whether to build an office and the variables depend(c)
indicating the office associated with a town are linked
by `occurrence' and `equivalence' constraints:
numdep(c) = |depend(d)=c|
numdep(c) >= 1 <=> build(c) = 1

The distances in the objective function are represented
through `element' constraints (auxiliary variables depdist(c)
indicate the distance from town c to the closest office).

*** This model cannot be run with a Community Licence
for the provided data instance ***

(c) 2008 Artelys S.A. and Fair Isaac Corporation
Creation: 2005, rev. Mar. 2013, Nov. 2019
*******************************************************!)

model "J-5 Tax office location (CP)"
uses "kalis"

forward procedure calculate_dist

setparam("KALIS_DEFAULT_LB", 0)

declarations
NC = 12
CITIES = 1..NC                        ! Set of cities

DIST: array(CITIES,CITIES) of integer ! Distance matrix
POP: array(CITIES) of integer         ! Population of cities
LEN: dynamic array(CITIES,CITIES) of integer ! Road lengths
NUMLOC: integer                       ! Desired number of tax offices
D: array(CITIES) of integer           ! Auxiliary array used in constr. def.

build: array(CITIES) of cpvar         ! 1 if office in city, 0 otherwise
depend: array(CITIES) of cpvar        ! Office on which city depends
depdist: array(CITIES) of cpvar       ! Distance to tax office
numdep: array(CITIES) of cpvar        ! Number of depending cities per off.
totDist: cpvar                        ! Objective function variable
Strategy: array(1..2) of cpbranching  ! Branching strategy
end-declarations

initializations from 'Data/j5tax.dat'
LEN POP NUMLOC
end-initializations

! Calculate the distance matrix
calculate_dist

forall(c in CITIES) do
build(c) <= 1
1 <= depend(c); depend(c) <= NC
min(d in CITIES) DIST(c,d) <= depdist(c)
depdist(c) <= max(d in CITIES) DIST(c,d)
numdep(c) <= NC
end-do

! Distance from cities to tax offices
forall(c in CITIES) do
forall(d in CITIES) D(d):=DIST(c,d)
element(D, depend(c)) = depdist(c)
end-do

! Number of cities depending on every office
forall(c in CITIES) occurrence(c, depend) = numdep(c)

! Relations between dependencies and offices built
forall(c in CITIES) equiv( build(c) = 1, numdep(c) >= 1 )

! Limit total number of offices
sum(c in CITIES) build(c) <= NUMLOC

! Branching strategy
Strategy(1):= assign_and_forbid(KALIS_MAX_DEGREE, KALIS_MAX_TO_MIN, build)
Strategy(2):= split_domain(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX,
depdist, true, 5)
cp_set_branching(Strategy)

! Objective: weighted total distance
! totDist = sum(c in CITIES) POP(c)*depdist(c)
! Equivalent formulation:
totDist = dot(POP,depdist)

! Solve the problem
if not cp_minimize(totDist) then
writeln("Problem is infeasible")
exit(1)
end-if

! Solution printing
writeln("Total weighted distance: ", getsol(totDist),
" (average per inhabitant: ",
getsol(totDist)/sum(c in CITIES) POP(c), ")")
forall(c in CITIES) if(getsol(build(c))>0) then
write("Office in ", c, ": ")
forall(d in CITIES) write(if(getsol(depend(d))=c, " "+d, ""))
writeln
end-if

!-----------------------------------------------------------------

! Calculate the distance matrix using Floyd-Warshall algorithm
procedure calculate_dist
! Initialize all distance labels with a sufficiently large value
BIGM:=sum(c,d in CITIES | exists(LEN(c,d))) LEN(c,d)
forall(c,d in CITIES) DIST(c,d):=BIGM

forall(c in CITIES) DIST(c,c):=0    ! Set values on the diagonal to 0

! Length of existing road connections
forall(c,d in CITIES | exists(LEN(c,d))) do
DIST(c,d):=LEN(c,d)
DIST(d,c):=LEN(c,d)
end-do

! Update shortest distance for every node triple
forall(b,c,d in CITIES | c<d )
if DIST(c,d) > DIST(c,b)+DIST(b,d) then
DIST(c,d):= DIST(c,b)+DIST(b,d)
DIST(d,c):= DIST(c,b)+DIST(b,d)
end-if
end-procedure

end-model

```   