Local authorities and public services
Description
Problem name and type, features | Difficulty |
J‑1 | Water conveyance / water supply management: Maximum flow problem | ** |
| encoding of arcs, finalize, selection with `|' |
J‑2 | CCTV surveillance: Maximum vertex cover problem | ** |
| encoding of network, exists |
J‑3 | Rigging elections: Partitioning problem | **** |
| algorithm for data preprocessing; file inclusion, 3 nested/recursive procedures, working with sets, if-then, forall-do, exists, finalize |
J‑4 | Gritting roads: Directed Chinese postman problem | **** |
| algorithm for finding Eulerian path/graph for printing; encoding of arcs, dynamic array, exists, 2 functions implementing Eulerian circuit algorithm, round, getsize, break, while-do, if-then-else |
J‑5 | Location of income tax offices: p-median problem | **** |
| modeling an implication, all-pairs shortest path algorithm (Floyd-Warshall); dynamic array, exists, procedure for shortest path algorithm, forall-do, if-then, selection with `|' |
J‑6 | Efficiency of hospitals: Data Envelopment Analysis (DEA) | *** |
| description of DEA method; loop over problem solving with complete re-definition of problem every time, finalize, naming and declaring constraint |
Further explanation of this example:
'Applications of optimization with Xpress-MP', Chapter 15: Local authorities and public services
Source Files
Data Files
j1water.mos
(!******************************************************
Mosel Example Problems
======================
file j1water.mos
````````````````
Water conveyance/water supply management
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Mar. 2002
*******************************************************!)
model "J-1 Water supply"
uses "mmxprs"
declarations
ARCS: range ! Set of arcs
NODES=1..12
PIPE: array(ARCS,1..2) of integer ! Definition of arcs (= pipes)
CAP: array(ARCS) of integer ! Capacity of arcs
SOURCE,SINK: integer ! Number of source and sink nodes
end-declarations
initializations from 'j1water.dat'
PIPE CAP SOURCE SINK
end-initializations
finalize(ARCS)
declarations
flow: array(ARCS) of mpvar ! Flow on arcs
end-declarations
! Objective: total flow
TotalFlow:= sum(a in ARCS | PIPE(a,2)=SINK) flow(a)
! Flow balances in nodes
forall(n in NODES | n<>SOURCE and n<>SINK)
sum(a in ARCS | PIPE(a,1)=n) flow(a) = sum(a in ARCS | PIPE(a,2)=n) flow(a)
! Capacity limits
forall(a in ARCS) flow(a) <= CAP(a)
! Solve the problem
maximize(TotalFlow)
! Solution printing
writeln("Total flow: ", getobjval)
forall(a in ARCS) writeln(PIPE(a,1), " -> ", PIPE(a,2), ": ", getsol(flow(a)))
end-model
|