Design choices for optimization
applications
Susanne Heipcke
Xpress Team, FICO
http://www.fico.com/xpress

The material in this presentation is the property of Fair Issac Corporation, is provided for the recipient only, andshall not be used, reproduced, or disclosed without Fair Isaac Corporation’s express consent.
c 2010 Fair Issac Corporation.

Overview» Modeling platforms» Application design» Xpress-Mosel» Mosel: Selected new features» Application examples» Summaryc 2010 Fair Isaac Corporation.

Modeling platforms

c 2010 Fair Issac Corporation.

Model development cycle

Model
Problemconception

Computational
problem instanceInterpretation& analysis

Computational
solution instanceHumanc 2010 Fair Issac Corporation.

Model solution

ComputerWhy use modeling software?

» Developing a working model is the difficult bit» Important to have software that helps» speed to market» verify correctness» maintenance & modification» algorithmic considerations» execution speedc 2010 Fair Issac Corporation.

MoselBCL

Model building libraries

OPL

AIMMS

Modeling + Programming

GUI

AMPL

GAMS

mp-modelConcertModeling platforms

Modeling languages
Matrix generators70s

c 2010 Fair Issac Corporation.

80s

90s

2000s

Modeling platforms

Modeling language

Modeling library

Matrix based

Verify correctness

easy

quite easy

very hard

Maintenanceeasyharderdifficult

Data handlinghigh level

native/some intrinsic

native language

language dependent

easy

quite easy

possibly slower

fasterfastest

fast

slow

slowestBuilding algorithms
Model execution speed
Speed to market

c 2010 Fair Issac Corporation.

Xpress modeling interfaces» Mosel» formulate model and develop optimization methods
using Mosel language / environment» BCL» build up model in your application code using
object-oriented model builder library» Optimizer» read in matrix files» input entire matrix from program arraysc 2010 Fair Issac Corporation.

Mosel» A modeling and solving environment» integration of modeling and solving» programming facilities» open, modular architecture» Interfaces to external data sources (e.g. ODBC,
host application) provided» Language is concise, user friendly, high level» Best choice for rapid development anddeploymentc 2010 Fair Issac Corporation.

Xpress-BCL» Model consists of BCL functions withinapplication source code (C, C++, Java, C# or
VB)» Develop with standard C/C++/Java/C#/VB tools» Provide your own data interfacing» Lower level, object oriented approach» Enjoy benefits of structured modeling withinyour application source codec 2010 Fair Issac Corporation.

Xpress-Optimizer» Model is set of arrays within application
source code (C, Java, C#, or VB)» May also input problems from a matrix file
» Develop with standard C/C#/Java/VB tools» Provide your own data interfacing» Very low level, no problem structure» Most efficient but lose easy model
development and maintenancec 2010 Fair Issac Corporation.

Application designc 2010 Fair Issac Corporation.

Application design

Application
designTargetaudience?

c 2010 Fair Issac Corporation.

Project
design?

Algorithms?

Application design

Targetaudience?

c 2010 Fair Issac Corporation.

OR specialists/
Research

Analysts/
Business experts

End users

Preference?

’Lightweight’GUI

Applicationarchitecture?

Application design

Applicationarchitecture?

Standalone

Userinteraction?

c 2010 Fair Issac Corporation.

Model + GUI

Integrated
component

Data I/O,
interfaces?

Application designUserinteraction?
staticRestarts (change data)
Tuning (solver parameters,
stopping criteria)
Configuration(select constraints)

c 2010 Fair Issac Corporation.

dynamic
Logging/progress display
Influence solution algorithms(user-defined cuts or heuristics,
bounds, reject solutions)Application design

Data I/O,
interfaces?
Model interfaces
Development environment
File formats, databaseconnectivityGUI

c 2010 Fair Issac Corporation.

Application interface
Embedding functionality(access to andinteraction with model)
Host languages

Application design

Project
design?

Independent phases
Possiblyseveralplatforms

Overlapping phases
Singleflexible
platform

Development/
maintenance?

c 2010 Fair Issac Corporation.

All-in-one (single phase)
Singleplatform

Application design

Development/
maintenance?
Persons / teams involved
Inhouse vs. externalContinuity

c 2010 Fair Issac Corporation.

Application design

Algorithms?

Solver choice

Solverinteraction

Standard formats
Related problem types
Paradigm switch
User extensionsc 2010 Fair Issac Corporation.

Callbacks

Decomposition/
Parallelism
Programming facilities
Communication andcoordination mechanisms
Distributed computing

Xpress-Mosel

c 2010 Fair Issac Corporation.

Xpress-Mosel» A high-level modeling language combinedwith standard functionality of programming
languages» implementation of models and solution algorithms ina single environment» Open, modular architecture» extensions to the language without any need formodifications to the core system» Compiled language» platform-independent compiled models for
distribution to protect intellectual propertyc 2010 Fair Issac Corporation.

...and also
» Mosel modules» solvers: mmxprs, mmquad, mmxslp, mmnl, kalis» data handling: mmetc, mmodbc, mmoci» model handling, utilities: mmjobs, mmsystem» graphics: mmive, mmxad» IVE: visual development environment(Windows)» Library interfaces for embedding models into
applications (C, Java, C#, VB)» Tools: debugger, profiler, model conversion,
preprocessorc 2010 Fair Issac Corporation.

Example: Portfolio optimization
Problem description» An investor wishes to invest a certain amountof money into a selection of shares.
» Constraints:
1. Invest at most 30% of the capital into any share.
2. Invest at least half of the capital in North-Americanshares.
3. Invest at most a third in high-risk shares.

» Objective: obtain the highest expected returnon investment

c 2010 Fair Issac Corporation.

Example: Portfolio optimization
Mathematical model

maximize

X

RETs · fracss∈SHARES

X

fracs ≤ 1 / 3s∈RISKX

fracs ≥ 0. 5

s∈NA

X

fracs = 1s∈SHARES∀s ∈ SHARES : 0 ≤ fracs ≤ 0. 3
c 2010 Fair Issac Corporation.

Example: Portfolio optimization
Mosel modelc 2010 Fair Issac Corporation.

Example: Portfolio optimization
Logical Conditions
1. Binary variables

2. Semi-continuous variables

c 2010 Fair Issac Corporation.

Example: Portfolio optimization
Extended problem» We wish to» run the model with different limits on the portion ofhigh-risk shares,» represent the results as a graph, plotting theresulting total return against the deviation as ameasure of risk.

» Algorithm: for every parameter value» re-define the constraint limiting the percentage ofhigh-risk values,» solve the resulting problem,» if the problem is feasible: store the solution values.

c 2010 Fair Issac Corporation.

Example: Portfolio optimization
Extended problem

c 2010 Fair Issac Corporation.

Example: Portfolio optimization
Extended problem

c 2010 Fair Issac Corporation.

Data handling» Physical files:» text files (Mosel format, new: binary format,
diskdata; free format, new: XML,» spreadsheets, databases (ODBC or specific drivers)» In memory:» memory block/address» streams; pipes; callbacks (new: IO callback)c 2010 Fair Issac Corporation.

Data handlingc 2010 Fair Issac Corporation.

XAD application

c 2010 Fair Issac Corporation.

Advanced solving tasks» Infeasibility handling» definition of slack variables» IIS (irreducible infeasible sets)» infeasibility repair meachanism» Solution enumeration» obtain the N best solutions

c 2010 Fair Issac Corporation.

Solution enumeration

Standard MIP search:c 2010 Fair Issac Corporation.

Solution enumerator:

Schemes of decomposition andconcurrent solving
The "multis":– multi-solver

Mosel instance
Mosel model
uses ’mmxprs’
uses ’mmxslp’

c 2010 Fair Issac Corporation.

Schemes of decomposition andconcurrent solving
The "multis":– multi-solver– multi-problem

Mosel instance
Mosel model

Problemc 2010 Fair Issac Corporation.

shareddata

ProblemSchemes of decomposition andconcurrent solving
The "multis":– multi-solver– multi-problem– multi-model

Mosel instance
Master model
start

Problemc 2010 Fair Issac Corporation.

SubmodeleventsProblemSchemes of decomposition andconcurrent solving
The "multis":– multi-solver– multi-problem– multi-model– multi-nodec 2010 Fair Issac Corporation.

Local instance
Master model

ProblemRemote instancestart

eventsSubmodelProblemSchemes of decomposition andconcurrent solving» Simple parallel runs
» different data instances» different algorithm configurations» Decomposition» Benders» Dantzig-Wolffe» Column generation» loop over top node
» branch-and-price» Cut generation» (cut-and-branch, branch-and-cut)» adding constraints
c 2010 Fair Issac Corporation.

Mosel: Selected new features» Distributed model execution» IO callbacks» XML interfacec 2010 Fair Issac Corporation.

Distributed model execution» mmjobs: facilities for model management,
synchronization of concurrent models basedon event queues, shared memory IO driver.
» New: extending capacities for handling
multiple models to distributed computing
using several Mosel instances (running locallyor on remote nodes connected through a
network)c 2010 Fair Issac Corporation.

Distributed model execution» Mosel instance management: connecting anddisconnecting Mosel instances, access toremote files, handling of host aliases (newtype: Mosel)» Remote connection IO drivers: two drivers(xsrv and rcmd) for creating remote Mosel
instances.
» Remote file acces IO drivers: access to physicalfiles or streams on remote Mosel instances(rmt), usable wherever Mosel expects a(generalized) filename, in particular ininitializations blocks.
c 2010 Fair Issac Corporation.

Distributed model execution» Remote machine must run a server» Default (as specified by value of control conntmpl):
Mosel server xprmsrv (started as separate program,available for all platforms supported by Xpress),connect with driver xsrv
connect(mosInst, "ABCD123")! Same as:
connect(mosInst, "xsrv:ABCD123")» Alternative: other servers, connect with driver rcmd,
e.g. with rhs, (NB: Mosel command line option -r isrequired for remote runs):connect(mosInst, "rcmd:rsh ABCD123 mosel -r")

c 2010 Fair Issac Corporation.

Distributed model execution» The Mosel server can be configured.
» Use this command to display the available options:xprmsrv -h

Configuration options include verbosity settings,
choice of the TCP port, and the definition of a log
file.
» Alternatively, use a configuration file for more
flexible configuration and to define multiple
environments
xprmsrv myconfig.conf

c 2010 Fair Issac Corporation.

Configuration file
» Contents of myconfig.conf:# Global setting of a log file
LOGFILE=/tmp/logfile.txt# Add a password to the default environment ’xpress’[xpress]
PASS=hardone# Define new environment using a different Xpress version[xptest]XPRESSDIR=/opt/xpressmp/testing
XPRESS=/opt/xpressmp/lic
MOSEL_CWD=$XPRESSDIR/workdir» Usage:r1:= connect(inst1, "xsrv:localhost/xpress/hardone")r2:= connect(inst2, "xrsv:mypcname/xptest")

c 2010 Fair Issac Corporation.

Local instances» Remote machine may be identical with thecurrent node (new instance started on thesame machine in a separate process)connect(mosInst, "")! Same as:
connect(mosInst, "rcmd:mosel -r")connect(mosInst, "localhost")! Same as:
connect(mosInst, "xsrv:localhost")

c 2010 Fair Issac Corporation.

Executing a submodel
model "Run model rtparams"
uses "mmjobs"
declarations
modPar: Model
end-declarations! Compile the model file
if compile("rtparams.mos")<>0 then exit(1); end-if! Load the bim fileload(modPar, "rtparams.bim")! Start model execution + parameter settingsrun(modPar, "PARAM1=" + 3.4 + ",PARAM3=’a string’" + ",PARAM4=" + true)! Wait for model termination
wait
dropnextevent! Ignore termination event message
end-model

c 2010 Fair Issac Corporation.

Executing a submodel remotelymodel "Run model rtparams remotely"uses "mmjobs"
declarations
modPar: Model
mosInst: Mosel
end-declarations! Compile the model file
if compile("rtparams.mos")<>0 then exit(1); end-if
NODENAME:= ""! "" for current node, or name, or IP address! Open connection to a remote node
if connect(mosInst, NODENAME)<>0 then exit(2); end-if! Load the bim fileload(mosInst, modPar, "rmt:rtparams.bim")! Start model execution + parameter settingsrun(modPar, "PARAM1=" + 3.4 + ",PARAM3=’a string’" + ",PARAM4=" + true)
wait! Wait for model termination
dropnextevent! Ignore termination event message
end-model
c 2010 Fair Issac Corporation.

Executing a submodel remotelymodel "Compile and run model rtparams remotely"uses "mmjobs"
declarations
modPar: Model
mosInst: Mosel
end-declarations
NODENAME:= ""! "" for current node, or name, or IP address! Open connection to a remote node
if connect(mosInst, NODENAME)<>0 then exit(2); end-if! Compile the model file remotely
if compile(mosInst, "", "rmt:rtparams.mos", "rtparams.bim")<>0 thenexit(1); end-if! Load the bim fileload(mosInst, modPar, "rtparams.bim")! Start model execution + parameter settingsrun(modPar, "PARAM1=" + 3.4 + ",PARAM3=’a string’" + ",PARAM4=" + true)
wait! Wait for model termination
dropnextevent! Ignore termination event message
end-model
c 2010 Fair Issac Corporation.

New and overloaded subroutines» Instance connection/disconnection
r:= connect(myInst, "")disconnect(myInst)» Remote compilation & loading
r:= compile(myInst, "", "filename.mos", "filename.bim")load(myInst, myModel, "filename.bim")» Redirecting Mosel streams
setdefstream(myInst, F_OUTPUT, "rmt:instoutput.txt")

c 2010 Fair Issac Corporation.

Some utilities» System information
compName:= getsysinfo(SYS_NODE);
currNode:= getparam("NODENUMBER");modelID:= getparam("JOBID");

allinfo:=getsysinfo(myInst)parent:= getparam("PARENTNUMBER")
instID:= getid(myInst)» Instance status information
if getstatus(myInst)<>0 thenwriteln("Instance is not connected")
end-if» Aliases
sethostalias("localhost2","localhost")
r:= connect(myInst, "localhost2")
sysName:= gethostalias("localhost2");
clearaliases

c 2010 Fair Issac Corporation.

getaliases(allAliases)

Distributed model execution» Documentation: ’Mosel Language Reference
manual’, Chapter 7 mmjobs» Examples: see newest version of thewhitepaper ’Multiple models and parallel
solving with Mosel’, Section 2.8 Working withremote Mosel instances» Another introductory example in ’Guide for
evaluators 2’, Section 6 Working in a
distributed architecture

c 2010 Fair Issac Corporation.

IO callbacks» In-memory communication so far: fixed data
structure sizes» New: alternative communication mechanism
working with flows enables dynamic sizing ofdata structures on the application level» particularly useful for solution output where
effective data sizes are not known a priori» available in C, Java, .NET

c 2010 Fair Issac Corporation.

IO callbacks» Pass the address of the function (C) or class(Java) implementing the callback to Mosel via
model parameters» initializations to: use the Mosel
post-processing library functions to retrieve
data from Mosel into the application» initializations from: new set offunctions to send data to Mosel, using thesame format as the default text file format

c 2010 Fair Issac Corporation.

IO callbacks (C)mydata: [ ("ind1" 3) [5 1.2] ("ind2" 7) [4 6.5] ]XPRMcb_sendctrl(cb, XPRM_CBC_OPENLST, 0);
XPRMcb_sendctrl(cb, XPRM_CBC_OPENNDX, 0);
XPRMcb_sendstring(cb, "ind1", 0);
XPRMcb_sendint(cb, 3, 0);
XPRMcb_sendctrl(cb, XPRM_CBC_CLOSENDX, 0);
XPRMcb_sendctrl(cb, XPRM_CBC_OPENLST, 0);
XPRMcb_sendint(cb, 5, 0);
XPRMcb_sendreal(cb, 1.2, 0);
XPRMcb_sendctrl(cb, XPRM_CBC_CLOSELST, 0);
XPRMcb_sendctrl(cb, XPRM_CBC_OPENNDX, 0);
XPRMcb_sendstring(cb, "ind2", 0);
XPRMcb_sendint(cb, 7, 0);
XPRMcb_sendctrl(cb, XPRM_CBC_CLOSENDX, 0);
XPRMcb_sendctrl(cb, XPRM_CBC_OPENLST, 0);
XPRMcb_sendint(cb, 4, 0);
XPRMcb_sendreal(cb, 6.5, 0);
XPRMcb_sendctrl(cb, XPRM_CBC_CLOSELST, 0);
XPRMcb_sendctrl(cb, XPRM_CBC_CLOSELST, 0);
c 2010 Fair Issac Corporation.

! [
!
(
!
"ind1"
!
3
!
)
!
[
!
5
!
1.2
!
]
!
(
!
"ind2"
!
7
!
)
!
[
!
4
!
6.5
!
]
! ]

IO callbacks (Java)mydata: [ ("ind1" 3) [5 1.2] ("ind2" 7) [4 6.5] ]ictx.sendControl(ictx.CONTROL_OPENLST);
ictx.sendControl(ictx.CONTROL_OPENNDX);
ictx.send("ind1");
ictx.send(3);ictx.sendControl(ictx.CONTROL_CLOSENDX);
ictx.sendControl(ictx.CONTROL_OPENLST);
ictx.send(5);ictx.send(1.2);
ictx.sendControl(ictx.CONTROL_CLOSELST);
ictx.sendControl(ictx.CONTROL_OPENNDX);
ictx.send("ind2");
ictx.send(7);ictx.sendControl(ictx.CONTROL_CLOSENDX);
ictx.sendControl(ictx.CONTROL_OPENLST);
ictx.send(4);ictx.send(6.5);
ictx.sendControl(ictx.CONTROL_CLOSELST);
ictx.sendControl(ictx.CONTROL_CLOSELST);
c 2010 Fair Issac Corporation.

! [
!
(
!
"ind1"
!
3
!
)
!
[
!
5
!
1.2
!
]
!
(
!
"ind2"
!
7
!
)
!
[
!
4
!
6.5
!
]
! ]

IO callbacks» Documentation: ’Mosel Library Reference
manual’, Section 1.5.2.2 cb driver – Handlingof initializations blocks» Examples: see newest version of the ’Mosel
User Guide’, Sections 13.4.3 Dynamic data (C),14.1.6.3 Dynamic data (Java)c 2010 Fair Issac Corporation.

XML interface» The module smew provides an XML interface
for the Mosel language.
» smew relies on two external libraries without
which the module will not work:» scew (’simple C expat wrapper’) — handling of the
XML tree» expat — the parser

c 2010 Fair Issac Corporation.

Structure of an XML document<?xml ... ?><root><parent><element attrname="attrvalue">
contents<child><leaf>leafcontents</leaf></child><child>2nd child contents</child></element><emptyelement attrname="attrvalue" /></parent></root>c 2010 Fair Issac Corporation.

Preamblesmew functionality» New types:» xmldoc represents an XML document» xmleltref is a reference to a node/element in the
document.
Several xmleltref may reference the same element
and the module does not check consistency: if anelement is removed, it is up to the user to make surenone of its references will be used afterwards

c 2010 Fair Issac Corporation.

smew functionality» Subroutines:» File access: load, save
» Document structure: getroot, setroot,
isvalid, getpreamble, setpreamble,
getchildren, getparent, add, remove» Handling elements: getname, setname,getcontent,
get[int|real|bool|str]content,
setcontent, getattr,
get[int|real|bool|str]attr, setattr,
delattr, getallattrc 2010 Fair Issac Corporation.

Example: Portfolio optimization
XML data format
declarations
SHARES: set of string
RISK: set of string
NA: set of string
RET: array(SHARES) of real
AllData: xmldoc
ShareList: list of xmleltref
end-declarations! Set of shares! Set of high-risk values among shares! Set of shares issued in N.-America! Estimated return in investment! XML document! List of XML elements! Reading data from an XML fileload(AllData, "folio.xml")
getchildren(getroot(AllData), ShareList, "share")
RISK:= union(l in ShareList | getattr(l,"risk")="high"){getstrattr(l,"name")}
NA:= union(l in ShareList | getattr(l,"region")="NA"){getstrattr(l,"name")}forall(l in ShareList) RET(getstrattr(l,"name")):= getintattr(l, "ret")c 2010 Fair Issac Corporation.

Example: Portfolio optimization
XML data format» Data file folio.xml:<portfolio><share name="treasury" ret="5" dev="0.1" country="Canada"region="NA" risk="low" /><share name="hardware" ret="17" dev="19" country="USA"region="NA" risk="high" />...
<share name="electronics" ret="21" dev="16" country="Japan"
region="Asia" risk="high" /></portfolio>c 2010 Fair Issac Corporation.

Example: Portfolio optimization
XML data format
declarations
SHARES: set of string
frac: array(SHARES) of mpvar
AllData: xmldoc
Share,Root,Sol: xmleltref
end-declarations! Set of shares! Fraction of capital used per share! XML document! XML elements! Create solution representation in XML format
Root:= setroot(AllData, "result")
Sol:= add(Root, "solution")
forall(s in SHARES) do
Share:= add(Sol, "share")setattr(Share, "name", s)
Share.content:= frac(s).sol
end-dosave(AllData, "result.xml")
save(AllData, "")c 2010 Fair Issac Corporation.

! Save solution to XML format file
! Display XML format solution on screenExample: Portfolio optimization
XML data format» Generated output file result.xml:<?xml version="1.0" encoding="ISO-8859-1" standalone="yes"?><result><solution><share name="treasury">0.3</share><share name="hardware">0</share>...
<share name="electronics">0</share></solution></result>

c 2010 Fair Issac Corporation.

smew distribution» Available for download from the Mosel open
source webpage» Archive contains» module source file: smew.c» module library file: smew.dso (copy into subdirectorydso)» library files: *expat.* and *scew.* (copy into
subdirectory bin [Windows] or lib [Unix])» documentation: smew.txt» examples: folioxml.mos, folioxmlqp.mos,booksearch.mos, xmltest.mosc 2010 Fair Issac Corporation.

Application examples» Alternative interfaces: Portfolio rebalancing» Distributed Mosel: client-server» Visualization: Aircraft routing

c 2010 Fair Issac Corporation.

Portfolio rebalancing:
Problem description» Modify the composition of an investment
portfolio as to achieve or approach a specified
investment profile.

c 2010 Fair Issac Corporation.

Application architecture» Single, configurable model file
» Different interfaces for model execution» stand-alone mode (command line or throughXpress-IVE) for development» graphical interface (written with XAD) for single
model runs and simulation» Java application for running batches of model
instancesc 2010 Fair Issac Corporation.

Optimization application in Mosel
Standalone

IVE
start application
return results

Data files

Mosel model

Output files

c 2010 Fair Issac Corporation.

Optimization application in Mosel
XAD GUI

Configuration file
Summary
outputData files

XAD
start application
return results

Mosel model

Output files

c 2010 Fair Issac Corporation.

Optimization application in Mosel
Embedded into host application

Java

Data files
Summary
outputstart application
return results

Mosel model

Output files

c 2010 Fair Issac Corporation.

Optimization application in Mosel
Alternative interfaces

Configuration file

XAD

IVE

Summary
outputstart application
return results

Data files

Mosel model

Output files

c 2010 Fair Issac Corporation.

Java

Data files

Summary
outputInput» Stand-alone and XAD: data input from text
files directly into Mosel» uses a filter module to accomodate different number
formats» Java: data read and stored by host application;communication with model instances throughmemoryc 2010 Fair Issac Corporation.

Output» Textual output log on screen or to file
» Optionally detailed HTML output» Java: summary statistics of multiple runs
» XAD:» summary statistics in the case of multiple runs
» optional output to Excel

c 2010 Fair Issac Corporation.

XAD interface» Graphical user interface (Windows)» Configuration of model runs
» data files» parameter settings» selection of constraints» Choice of solving mode:» repeated runs for a single model (simulation)» solve all instances from customer file (evaluation ofparameter settings)» Graphical comparison of resultsc 2010 Fair Issac Corporation.

XAD interface:
Detailed resultsc 2010 Fair Issac Corporation.

XAD interface:Parameter and version log

c 2010 Fair Issac Corporation.

XAD interface:
Multiple run summaryc 2010 Fair Issac Corporation.

Some highlights» Model:» easy maintenance through single model» deployment as BIM file: no changes to model by
end-user» language extensions according to specific needs» Interfaces:» several run modes adapted to different types ofusages» efficient data exchange with host application
through memory» parallel model runs (Java) or repeated sequential runs
(XAD)
c 2010 Fair Issac Corporation.

Distributed Mosel:
problem description» Multi-user optimization application processing
a large number of optimization model
instances» Idea: replace the preselected, static
assignment of optimization runs by a Mosel
server that controls the job queuesc 2010 Fair Issac Corporation.

User

c 2010 Fair Issac Corporation.

Production
machineMosel server

...

...

User

Database

Distributed Mosel:client-server architecture

Production
machineDistributed Mosel:
highlights» Use Mosel lists for representation of dynamic
queueing system» Mosel master (’server’) model communicateswith database and handles remote submodels

c 2010 Fair Issac Corporation.

Aircraft routing:Problem description» For given sets of flights and aircraft,determine which aircraft services a flight.
» Aircraft are not identical» they cannot all service every flight» a specific maintenance site must be used per plane» some scheduled long maintenance breaks» Starting condition: each aircraft has a starting
position and a specific amount of accumulated
flight minutes

c 2010 Fair Issac Corporation.

Aircraft routing:
Representation» Temporal (activity on node) network:» a flight corresponds to a node
» ’cost’ of node: flight minutes ( 6= elapsed time)» successor nodes: flights starting from a destination
within a given time window after arrival ofpredecessor» maintenance: represented by a node
» aircraft: commodity traveling through the networkc 2010 Fair Issac Corporation.

Aircraft routing:Decomposition» Different views are possible:» per time unit (e.g., day)» per commodity (aircraft)» Idea: generate set of feasible routes per
aircraft by solving optimization subproblems
maximizing the flight minutes up to eachmaintenance stop
» iteratively force usage of ’less preferred’ flights» may keep suboptimal solutions

c 2010 Fair Issac Corporation.

Aircraft routing:
Application architecture» Master problem: route selection» Subproblems: route generation (one instanceper plane)» parallel, possibly remote, execution of submodels» User interface (optional): XAD GUI

c 2010 Fair Issac Corporation.

Aircraft routing:
Application GUI

c 2010 Fair Issac Corporation.

Aircraft routing:Visualization» Visualization of input data helps with
understanding and analysis of the problem» Representation of intermediate results during
development (IVE) or as progress report tousers (XAD)

c 2010 Fair Issac Corporation.

Aircraft routing:Visualization

c 2010 Fair Issac Corporation.

Aircraft routing:User interaction» Manual construction of routes» Editing generated plansc 2010 Fair Issac Corporation.

Aircraft routing:User interaction

c 2010 Fair Issac Corporation.

Summaryc 2010 Fair Issac Corporation.

Summary» Have seen:» design choices for optimization applications» Xpress-Mosel:» recent developments make possible implementationof complex algorithms and a high degree of userinteraction» unique features for handling large-scale problems:
support of decomposition, concurrent solving,
distributed computing, and also 64bit coefficientindexing

c 2010 Fair Issac Corporation.

Where to get more information» Xpress website:» http://www.fico.com/xpress» Xpress resources (documentation,
whitepapers)» http://optimization.fico.com» Searchable on-line examples database:» http://examples.xpress.fico.com» Trial download:» http://decisions.fico.com/
downloadTrial.html

c 2010 Fair Issac Corporation.

www.fico.com/xpress

The material in this presentation is the property of Fair Issac Corporation, is provided for the recipient only, andshall not be used, reproduced, or disclosed without Fair Isaac Corporation’s express consent.
c 2010 Fair Issac Corporation.