REGIÕES E REDES
(REGIONS AND NETWORKS)
Lecture 2: Transport networks design and
evaluation
Xpress presentation - Laboratory work
Eng. Luis Martínez
Instituto Superior Técnico / Masters in Civil Engineering – Regions and Networks 2008/2009
REGIONS AND NETWORKS
Transport networks design and evaluation
Instituto Superior Técnico
Masters in Civil Engineering
1
OUTLINE
Xpress structure
Create input files for Xpress
Xpress-IVE overview
Xpress-IVE key features
Mosel programming language key words
Declare and initialize variables in Mosel
Declare an objective function and constraints in Mosel
Declare and run the optimization in Mosel
Output the results (library “mmive”)
Xpress Laboratory work with two network design examples
A minimum spanning tree problem example
REGIONS AND NETWORKS
Transport networks design and evaluation
Xpress presentation
A Min-cost-flow problem example
Instituto Superior Técnico / Masters in Civil Engineering – Regions and Networks 2008/2009
2
XPRESS PRESENTATION - XPRESS
STRUCTURE
solve linear, integer, quadratic, non-linear, and stochastic programming problems.
Solver engines:
Xpress-Optimizer (LP, MIP, QP, MIQP, QCQP, NLP)
Xpress-SLP (NLP, MINLP)
Xpress-SP is a Stochastic Programming tool for solving optimization problems
involving uncertainty
Xpress-Kalis is Constraint Programming software (discrete combinatorial problems)
Model building and development tools:
Xpress-Mosel programming language
Xpress-BCL is an object-oriented library
Xpress-IVE is a complete visual development environment for Xpress-Mosel under
Windows
Xpress-Application Developer (XAD) extends Xpress-Mosel with an API for
graphical user interface development
Instituto Superior Técnico / Masters in Civil Engineering – Regions and Networks 2008/2009
REGIONS AND NETWORKS
Transport networks design and evaluation
Xpress-MP is a suite of mathematical modeling and optimization tools used to
3
The input files are created in .dat files format
These files should contain the vectors and matrices with the input variables identified for
reading from the Xpress engine.
Arcs: [(1 1) "Lisboa" "Odivelas"
(2 1) "Lisboa" "Loures"
(3 1) "Lisboa" "Amadora"
(4 1) "Lisboa" "Oeiras"
(5 1) "Lisboa" "Sintra"
(6 1) "Lisboa" "Cascais"
(7 1) "Lisboa" "Mafra"
(8 1) "Lisboa" "Vila Franca de Xira“]
x: [("Lisboa")111461 ("Odivelas") 108843 ("Loures")
110098 ("Amadora") 105211]
flow: [0
15900
26500
26500
23850
15900
0
9540
13780
15900
26500
9540
0
14840
19080
26500
13780
14840
0
42400
23850
15900
19080
42400
0]
Instituto Superior Técnico / Masters in Civil Engineering – Regions and Networks 2008/2009
REGIONS AND NETWORKS
Transport networks design and evaluation
XPRESS PRESENTATION - CREATE
INPUT FILES FOR XPRESS
4
XPRESS PRESENTATION - XPRESS-IVE
OVERVIEW
REGIONS AND NETWORKS
Transport networks design and evaluation
Run and
debug
control
Variables
and
constraints
activity and
output
Mosel editor
Optimization results
Optimization process
Instituto Superior Técnico / Masters in Civil Engineering – Regions and Networks 2008/2009
5
XPRESS PRESENTATION - XPRESS-IVE
KEY FEATURES
model – model name
uses – libraries to be used ("mmxprs","mmive“)
parameters – define parameters of the model – filename of the input data file
(DATAFILE= ……dat)
end-parameters
declarations – declare variables and ranges of variables of the input file
end-declarations
initializations from DATAFILE – initialize variables from file (insert variables
names)
end-initializations
declarations – declare decision variables
end-declarations
end-model
Instituto Superior Técnico / Masters in Civil Engineering – Regions and Networks 2008/2009
REGIONS AND NETWORKS
Transport networks design and evaluation
The code file should have the following structure:
6
Key words:
Variables types
string – text
integer – integer number
real – real number
mpvar – decision variable
array(range) of type of variable
forall(range) – iterator
forall(range) do end-do – cycle with actions
if end-if – conditional action
sum – somation
REGIONS AND NETWORKS
Transport networks design and evaluation
XPRESS PRESENTATION - MOSEL
PROGRAMMING LANGUAGE KEY WORDS
:= – assign value; =, >=,<= – equality and inequality operators
Instituto Superior Técnico / Masters in Civil Engineering – Regions and Networks 2008/2009
7
Variables declaration and initialization:
declarations
NODES: set of string
x: array(NODES) of real
y: array(NODES) of real
A: array(ARCS:set of integer,1..2) of string
DIST: array (ARCS) of real
demand:array(NODES,NODES) of integer
Declare range
Declare input
variables (range size
defined by the input
data file)
end-declarations
initializations from DATAFILE
A x y demand
Variables read in the file
REGIONS AND NETWORKS
Transport networks design and evaluation
XPRESS PRESENTATION - DECLARE AND
INITIALIZE VARIABLES IN MOSEL
end-initializations
Instituto Superior Técnico / Masters in Civil Engineering – Regions and Networks 2008/2009
8
Objective function declaration
Cost:=sum(i in ARCS)(a*flow(i) + b*Exist(i))*DIST(i)
Constraint variable (linctr)
Decision variables
Constraints declaration
forall(a in NODES)
Total(a):= sum(i in ARCS|A(i,1)=a) flow(i)>= sum(b in NODES)
demand(a,b)
FlowT:=sum(c in ARCS) flow(c) = sum(i,j in NODES) demand(i,j)
forall(c in ARCS) flow(c) is_integer
forall(c in ARCS) Exist(c) is_binary
Instituto Superior Técnico / Masters in Civil Engineering – Regions and Networks 2008/2009
REGIONS AND NETWORKS
Transport networks design and evaluation
XPRESS PRESENTATION - DECLARE AN
OBJECTIVE FUNCTION AND CONSTRAINTS
9
After the declaration of the objective function and all the constraints
we need to define the optimization method that will apply
(minimization, maximization)
minimize (Cost)
maximize (utility)
Optimize the identified constraint variable
After the definition of the optimization method (if we don’t define any
output results – text or graphical), we need to close the model with
the key word end-model
Having all the complete code needed we can now run the model in
the Run button.
Instituto Superior Técnico / Masters in Civil Engineering – Regions and Networks 2008/2009
REGIONS AND NETWORKS
Transport networks design and evaluation
XPRESS PRESENTATION - DECLARE AND
RUN THE OPTIMIZATION IN MOSEL
10
Write output results in text:
getsol(mpvar) – get the solution values of the variable
getobjval – get final value of the objective function
writeln(string) – write in a string line
write(string) – write a string
strfmt(number) – write as string
Draw graphs:
CnctGraph:= IVEaddplot("Road", IVE_YELLOW)
TermGraph:= IVEaddplot("Cities", IVE_GREEN)
IVEdrawpoint(TermGraph, x(i), y(i))
IVEdrawline(CnctGraph, x(A(i)), y(A(i)), x(A(j)), y(A(j)))
IVEdrawlabel(CnctGraph, (x(A(i))+x(A(j)))/2, (y(A(i))+y(A(j)))/2,
string(getsol(flow(a,j))))
Instituto Superior Técnico / Masters in Civil Engineering – Regions and Networks 2008/2009
REGIONS AND NETWORKS
Transport networks design and evaluation
XPRESS PRESENTATION - OUTPUT THE
RESULTS
11
XPRESS LABORATORY - A MINIMUM
SPANNING TREE PROBLEM EXAMPLE (I)
Decision Variables:
X: array (NODES, NODES) – binary
Level: array (NODES) - integer
Nodes
Objective function: ∑ α ⋅ Lengthij
i , j =1
Constraints:
Nodes / i <> j
Number of connections:
∑x
ij
= N −1
i , j =1
Avoid Subcycle:
∀i , j level j ≥ leveli + 1 − N + N × xij
Direct all connections towards the root: ∀ j
Road length: 2333.06
N / j <>1
∑x
ij
=1
Spain Network Example
i =1
Connections: A Coruña-Pontevedra Lugo-A Coruña Asturias-Lugo Cantabria-León Vizcaya-Cantabria Guipúzcoa-Vizcaya
REGIONS AND NETWORKS
Transport networks design and evaluation
Goal: Design a network that connects all the nodes of the graph at minimum cost
León-Asturias Burgos-Vizcaya Navarra-Guipúzcoa Madrid-Salamanca Barcelona-Zaragoza Valencia-Zaragoza SevillaBadajoz Salamanca-León Zaragoza-Navarra Badajoz-Salamanca
Instituto Superior Técnico / Masters in Civil Engineering – Regions and Networks 2008/2009
12
XPRESS LABORATORY - A MIN-COST-FLOW
MULTI-TERMINAL PROBLEM EXAMPLE (I)
several sink nodes at minimum cost considering capacity constraints on the links
of the graph
Decision Variables:
Flow: array (ARCS,ODpairs) – integer
Arcs ,ODPairs
∑ α ⋅ Flow
Objective function:
ij
⋅ Lengthi
i =1, j =1
Constraints:
Arcs / Oi =O j
Total source flow: ∀ j ,ODPairs
∑ Flow
ij
≥ Demand j
i =1
Node equilibrium:
Arcs / Di = n
∑ Flow
∀ nodes , jODPairs
ij
i =1
Arcs / Ok = n
=
∑ Flow
k, j
k =1
Capacity constraint:
ODPairs
∀arcs
∑ Flow
ai
≤ Capacity a ⋅ MaximumRatio
i =1
REGIONS AND NETWORKS
Transport networks design and evaluation
Goal: Assign demand flow the an existing network from a several sources to a
Spain Network Example
Positive flow: ∀arcs , jODPairs Flowaj ≥ 0
Instituto Superior Técnico / Masters in Civil Engineering – Regions and Networks 2008/2009
13