 FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home   Robust shortest path

Description
Determine the shortest path through a road network subject to uncertain travel times caused by road works (formulated as a 'cardinality' uncertainty set).

Further explanation of this example: Whitepaper 'Robust Optimization with Xpress', Section 2 Robust shortest path

Source Files

Data Files

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

``````````````````
Shortest path with cardinality robustness constraints

(c) 2014 Fair Isaac Corporation
author: S. Heipcke, Mar. 2014, rev. Nov. 2014
*******************************************************!)
uses "mmxprs", "mmrobust"

parameters
NWORK = 2             ! Number of roadworks
end-parameters

forward procedure printsol(val: real)
forward procedure printrobsoleval
forward procedure evalfixedrobsol

declarations
Nodes: range                                  ! Set of nodes
ARC: array(Arcs:range,1..2) of integer        ! Arc origins/destinations
LEN,MAXDELAY: array(Arcs) of real             ! Length and max delay per arc
DELAY: array(Arcs) of real                    ! Actual delay
Source,Sink: integer                          ! Source and sink node numbers

NomProb,ExtProb,RobProb: mpproblem            ! Alternative problem formulations
use: array(Arcs) of mpvar                     ! 1 iff arc is used
usesol: array(Arcs) of real                   ! Solution values
userobsol: array(Arcs) of real                ! Robust solution values
TotalLength: linctr                           ! Objective function

delay: array(Arcs) of uncertain               ! Uncertain delay
end-declarations

!**** Input datafile ****
initializations from DATAFILE
Nodes
Arcs
ARC
[LEN,MAXDELAY] as "ArcData"
Source  Sink
end-initializations

!**** Robust problem formulation ****
with RobProb do
forall(a in Arcs) use(a) is_binary

! Sink and source of flow
OneSourceR:= sum(a in Arcs | ARC(a,1)=Source) use(a)=1
OneSinkR:= sum(a in Arcs | ARC(a,2)=Sink) use(a)=1
NoRetSourceR:= sum(a in Arcs | ARC(a,2)=Source) use(a)=0
NoRetSinkR:=sum(a in Arcs | ARC(a,1)=Sink) use(a)=0

! Flow balance in intermediate nodes
forall(n in Nodes-{Source,Sink})
BalanceR(n):= sum(a in Arcs | ARC(a,2)=n) use(a) = sum(a in Arcs | ARC(a,1)=n) use(a)

! Only use one direction per edge
forall(a in Arcs | ARC(a,1)<ARC(a,2)) OneDirR(a):= use(a) +
sum(b in Arcs | ARC(b,2)=ARC(a,1) and ARC(b,1)=ARC(a,2)) use(b) <= 1

! Random construction work on NWORK arcs
forall(a in Arcs) delay(a) <= MAXDELAY(a)
forall(a in Arcs) delay(a) >= 0
cardinality(union(a in Arcs) {delay(a)}, NWORK)

! Shortest path length
TotalLengthR:= sum(a in Arcs) (LEN(a)+delay(a))*use(a)

! Solving
minimize(TotalLengthR)

! Solution reporting
writeln("#### Robust solution ####")
if getprobstat=XPRS_OPT then
writeln("Delay: ", array(a in Arcs) delay(a).sol )
writeln("Shortest path: ", getobjval)
writeln("Delay on shortest path: ",
sum(a in Arcs | use(a).sol>0 ) delay(a).sol)
forall(a in Arcs | use(a).sol>0)
write("  ", if(ARC(a,1)=Source, "Source", string(ARC(a,1))), "->",
if(ARC(a,2)=Sink, "Sink", string(ARC(a,2))), " (",
LEN(a), "+", delay(a).sol,");")
writeln
else
writeln("No solution")
end-if

! Save the robust solution
forall(a in Arcs) userobsol(a):=use(a).sol

end-do

!**** Nominal problem (all delays fixed at zero) ****
with NomProb do
forall(a in Arcs) use(a) is_binary

! Sink and source of flow
sum(a in Arcs | ARC(a,1)=Source) use(a)=1
sum(a in Arcs | ARC(a,2)=Sink) use(a)=1
sum(a in Arcs | ARC(a,2)=Source) use(a)=0
sum(a in Arcs | ARC(a,1)=Sink) use(a)=0

! Flow balance in intermediate nodes
forall(n in Nodes-{Source,Sink})
sum(a in Arcs | ARC(a,2)=n) use(a) = sum(a in Arcs | ARC(a,1)=n) use(a)

! Only use one direction per edge
forall(a in Arcs | ARC(a,1)<ARC(a,2)) use(a) +
sum(b in Arcs | ARC(b,2)=ARC(a,1) and ARC(b,1)=ARC(a,2)) use(b) <= 1

! Delays fixed to maximum
forall(a in Arcs) DELAY(a) := 0

! Shortest path length
TotalLengthN:= sum(a in Arcs) (LEN(a)+DELAY(a))*use(a)

! Solving
minimize(TotalLengthN)

! Solution reporting
writeln("\n#### Nominal solution (no delay) ####")
printsol(getobjval)
printrobsoleval

! Save the solution values and calculate worst case value for the given N
forall(a in Arcs) usesol(a):=use(a).sol
evalfixedrobsol

end-do

!**** Extreme problem (all delays fixed at upper bounds) ****
with ExtProb do
forall(a in Arcs) use(a) is_binary

! Sink and source of flow
sum(a in Arcs | ARC(a,1)=Source) use(a)=1
sum(a in Arcs | ARC(a,2)=Sink) use(a)=1
sum(a in Arcs | ARC(a,2)=Source) use(a)=0
sum(a in Arcs | ARC(a,1)=Sink) use(a)=0

! Flow balance in intermediate nodes
forall(n in Nodes-{Source,Sink})
sum(a in Arcs | ARC(a,2)=n) use(a) = sum(a in Arcs | ARC(a,1)=n) use(a)

! Only use one direction per edge
forall(a in Arcs | ARC(a,1)<ARC(a,2)) use(a) +
sum(b in Arcs | ARC(b,2)=ARC(a,1) and ARC(b,1)=ARC(a,2)) use(b) <= 1

! Delays fixed to maximum
forall(a in Arcs) DELAY(a):= MAXDELAY(a)

! Shortest path length
TotalLengthN:= sum(a in Arcs) (LEN(a)+DELAY(a))*use(a)

! Solving
minimize(TotalLengthN)

! Solution reporting
writeln("\n#### Worst-case solution (all roads delayed) ####")
printsol(getobjval)
printrobsoleval

! Save the solution values and calculate worst case value for the given N
forall(a in Arcs) usesol(a):=use(a).sol
evalfixedrobsol

end-do

!**** Solution reporting ****
procedure printsol(val: real)
writeln("Delay: ", DELAY)
if getprobstat=XPRS_OPT then
writeln("Shortest path: ", val)
writeln("Delay on shortest path: ", sum(a in Arcs) DELAY(a)*use(a).sol)
forall(a in Arcs | use(a).sol>0)
write("  ", if(ARC(a,1)=Source, "Source", string(ARC(a,1))), "->",
if(ARC(a,2)=Sink, "Sink", string(ARC(a,2))), " (",
LEN(a), "+", DELAY(a),");")
writeln
else
writeln("No solution")
end-if
end-procedure

!**** Evaluate the saved robust solution with actual delay values ****
procedure printrobsoleval
writeln("Evaluation of robust solution with fixed delay values:")
writeln("  Robust solution path: ",
sum(a in Arcs) (LEN(a)+DELAY(a))*userobsol(a) )
writeln("  Delay for robust sol: ", sum(a in Arcs) DELAY(a)*userobsol(a) )
forall(a in Arcs | userobsol(a).sol>0)
write("  ", if(ARC(a,1)=Source, "Source", string(ARC(a,1))), "->",
if(ARC(a,2)=Sink, "Sink", string(ARC(a,2))), " (",
LEN(a), "+", DELAY(a),");")
writeln
end-procedure

!**** Calculate the worst case delay for a given solution ****
procedure evalfixedrobsol
writeln("Worst-case delay for selected path (N=", NWORK, " delays):")
with RobProb do
! Fix path to current (non-robust) solution values
forall(a in Arcs | usesol(a)>0) FixArc(a):=use(a)>=usesol(a)

! Solving
minimize(TotalLengthR)

! Solution reporting
writeln("  Value for shortest path: ", getobjval)
writeln("  Delay on shortest path: ",
sum(a in Arcs | use(a).sol>0 ) delay(a).sol )
forall(a in Arcs | use(a).sol>0)
write("  ", if(ARC(a,1)=Source, "Source", string(ARC(a,1))), "->",
if(ARC(a,2)=Sink, "Sink", string(ARC(a,2))), " (",
LEN(a), "+", delay(a).sol,");")
writeln

! Unfix the solution values
forall(a in Arcs | usesol(a)>0) FixArc(a):=0

end-do
end-procedure

end-model

```   