Parallel problem generation for structured problems in mathematical programming
Abstract
The aim of this research is to investigate parallel problem generation for structured
optimization problems. The result of this research has produced a novel
parallel model generator tool, namely the Parallel Structured Model Generator
(PSMG). PSMG adopts the model syntax from SML to attain backward compatibility
for the models already written in SML [1]. Unlike the proof-of-concept
implementation for SML in [2], PSMG does not depend on AMPL [3].
In this thesis, we firstly explain what a structured problem is using concrete
real-world problems modelled in SML. Presenting those example models allows
us to exhibit PSMG’s modelling syntax and techniques in detail. PSMG provides
an easy to use framework for modelling large scale nested structured problems
including multi-stage stochastic problems. PSMG can be used for modelling linear
programming (LP), quadratic programming (QP), and nonlinear programming
(NLP) problems.
The second part of this thesis describes considerable thoughts on logical calling
sequence and dependencies in parallel operation and algorithms in PSMG.
We explain the design concept for PSMG’s solver interface. The interface follows
a solver driven work assignment approach that allows the solver to decide how
to distribute problem parts to processors in order to obtain better data locality
and load balancing for solving problems in parallel. PSMG adopts a delayed
constraint expansion design. This allows the memory allocation for computed
entities to only happen on a process when it is necessary. The computed entities
can be the set expansions of the indexing expressions associated with the
variable, parameter and constraint declarations, or temporary values used for set
and parameter constructions. We also illustrate algorithms that are important
for delivering efficient implementation of PSMG, such as routines for partitioning
constraints according to blocks and automatic differentiation algorithms for evaluating
Jacobian and Hessian matrices and their corresponding sparsity partterns.
Furthermore, PSMG implements a generic solver interface which can be linked
with different structure exploiting optimization solvers such as decomposition or
interior point based solvers. The work required for linking with PSMG’s solver
interface is also discussed.
Finally, we evaluate PSMG’s run-time performance and memory usage by
generating structured problems with various sizes. The results from both serial
and parallel executions are discussed. The benchmark results show that PSMG
achieve good parallel efficiency on up to 96 processes. PSMG distributes memory
usage among parallel processors which enables the generation of problems that
are too large to be processed on a single node due to memory restriction.
Collections
The following license files are associated with this item: