liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Models and Methods for Costly Global Optimization and Military Decision Support Systems
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.ORCID iD: 0000-0002-9881-4170
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The thesis consists of five papers. The first three deal with topics within costly global optimization and the last two concern military decision support systems.

The first part of the thesis addresses so-called costly problems where the objective function is seen as a “black box” to which the input parameter values are sent and a function value is returned. This means in particular that no information about derivatives is available. The black box could, for example, solve a large system of differential equations or carry out   timeconsuming simulation, where a single function evaluation can take several hours! This is the reason for describing such problems as costly and why they require customized algorithms. The goal is to construct algorithms that find a (near)-optimal solution using as few function evaluations as possible. A good example of a real life application comes from the automotive industry, where the development of new engines utilizes advanced mathematical models that are governed by a dozen key parameters. The objective is to optimize the engine by changing these parameters in such a way that it becomes as energy efficient as possible, but still meets all sorts of demands on strength and external constraints. The first three papers describe algorithms and implementation details for these costly global optimization problems.

The second part deals with military mission planning, that is, problems that concern logistics, allocation and deployment of military resources. Given a fleet of resource, the decision problem is to allocate the resources against the enemy so that the overall mission success is optimized. We focus on the problem of the attacker and consider two separate problem classes. In the fourth paper we introduce an effect oriented planning approach to an advanced weapon-target allocation problem, where the objective is to maximize the expected outcome of a coordinated attack. We present a mathematical model together with efficient solution techniques. Finally, in the fifth paper, we introduce a military aircraft mission planning problem, where an aircraft fleet should attack a given set of targets. Aircraft routing is an essential part of the problem, and the objective is to maximize the expected mission success while minimizing the overall mission time. The problem is stated as a generalized vehicle routing model with synchronization and precedence side constraints.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2012. , 39 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1450
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-77078ISBN: 978-91-7519-891-0 (print)OAI: oai:DiVA.org:liu-77078DiVA: diva2:524846
Public defence
2012-06-04, C3, C-huset, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Opponent
Supervisors
Available from: 2012-05-04 Created: 2012-05-04 Last updated: 2015-02-25Bibliographically approved
List of papers
1. An adaptive radial basis algorithm (ARBF) for expensive black-box mixed-integer constrained global optimization
Open this publication in new window or tab >>An adaptive radial basis algorithm (ARBF) for expensive black-box mixed-integer constrained global optimization
2008 (English)In: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 9, no 3, 311-339 p.Article in journal (Refereed) Published
Abstract [en]

Response surface methods based on kriging and radial basis function (RBF) interpolationhave been successfully applied to solve expensive, i.e. computationally costly,global black-box nonconvex optimization problems.In this paper we describe extensions of these methods to handlelinear, nonlinear, and integer constraints.In particular, algorithms for standard RBF and the new adaptive RBF (ARBF) aredescribed.Note, however, while the objective function may be expensive, we assumethat any nonlinear constraints are either inexpensive or are incorporatedinto the objective function via penalty terms.Test results are presented on standard test problems, both nonconvexproblems with linear and nonlinear constraints, and mixed-integernonlinear problems (MINLP). Solvers in the TOMLAB OptimizationEnvironment (http://tomopt.com/tomlab/) have been compared,specifically the three deterministic derivative-free solversrbfSolve, ARBFMIP and EGO with three derivative-based mixed-integernonlinear solvers, OQNLP, MINLPBB and MISQP, as well as the GENOsolver implementing a stochastic genetic algorithm. Results showthat the deterministic derivative-free methods compare well with thederivative-based ones, but the stochastic genetic algorithm solver isseveral orders of magnitude too slow for practical use.When the objective function for the test problems is costly to evaluate,the performance of the ARBF algorithm proves to be superior.

Place, publisher, year, edition, pages
Springer, 2008
Keyword
Global optimization, radial basis functions, response surface model, surrogate model, expensive function, CPU-intensive, optimization software, splines, mixed-integer nonlinear programming, nonconvex, derivative-free, black-box, linear constraints, nonlinear constraints
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-77076 (URN)10.1007/s11081-008-9037-3 (DOI)000259577400002 ()
Available from: 2012-05-04 Created: 2012-05-04 Last updated: 2017-12-07Bibliographically approved
2. The Influence of Experimental Designs on the performance of surrogate model based costly global optimization solvers
Open this publication in new window or tab >>The Influence of Experimental Designs on the performance of surrogate model based costly global optimization solvers
2009 (English)In: Studies in Informatics and Control, ISSN 1220-1766, E-ISSN 1841-429X, Vol. 18, no 1, 87-95 p.Article in journal (Refereed) Published
Abstract [en]

When dealing with costly objective functions in optimization, one good alternative is to use a surrogate model approach. A common feature for all such methods is the need of an initial set of points, or "experimental design", in order to start the algorithm. Since the behavior of the algorithms often depends heavily on this set, the question is how to choose a good experimental design. We investigate this by solving a number of problems using different designs, and compare the outcome with respect to function evaluations and a root mean square error test of the true function versus the surrogate model produced. Each combination of problem and design is solved by 3 different solvers available in the TOMLAB optimization environment. Results indicate two designs as superior.

Place, publisher, year, edition, pages
National Institute for R&D in Informatics (ICI), 2009
Keyword
Black-box, Surrogate model, Costly functions, Latin Hypercube Designs, Experimental Design
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-77077 (URN)000269029600010 ()
Available from: 2012-05-04 Created: 2012-05-04 Last updated: 2017-12-07Bibliographically approved
3. Implementation of a One-Stage Efficient Global Optimization (EGO) Algorithm
Open this publication in new window or tab >>Implementation of a One-Stage Efficient Global Optimization (EGO) Algorithm
2009 (English)Report (Other academic)
Abstract [en]

Almost every Costly Global Optimization (CGO) solver utilizes a surrogate model, or response surface, to approximate the true (costly) function. The EGO algorithm introduced by Jones et al. utilizes the DACE framework to build an approximating surrogate model. By optimizing a less costly utility function, the algorithm determines a new point where the original objective function is evaluated. This is repeated until some convergence criteria is fulfilled.The original EGO algorithm finds the new point to sample in a two-stage process. In its first stage, the estimates of the interpolation parameters are optimized with respect to already sampled points. In the second stage, these estimated values are considered true in order to optimize the location of the new point. The use of estimate values as correct introduces a source of error.Instead, in the one-stage EGO algorithm, both the parameters and the location of a new point are optimized at the same time, removing the source of error. This new subproblem becomes more difficult, but eliminates the need of solving two subproblems.Difficulties in implementing a fast and robust One-Stage EGO algorithm in TOMLAB are discussed, especially the solution of the new subproblem.

Publisher
26 p.
Series
Research Report 2009, School of Education, Culture and Communication, Division of Applied Mathematics, Mälardalen University, ISSN 1404-4978 ; 2009:2
Keyword
Global Optimization, Costly, EGO
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-77075 (URN)
Available from: 2012-05-04 Created: 2012-05-04 Last updated: 2015-02-26Bibliographically approved
4. Effect Oriented Planning
Open this publication in new window or tab >>Effect Oriented Planning
2012 (English)Report (Other academic)
Abstract [en]

The problem setting concerns the tactical planning of a military operation. Imagine a big wide open area where a number of interesting targets are positioned. It could be radar stations or other surveillance equipment, with or without defensive capabilities, which the attacker wishes to destroy. Moreover, the targets are possibly guarded by defending units, like Surface-to-Air Missile (SAM) units. The positions of all units, targets and defenders, are known. We consider the problem of the attacker, where the objective is to maximize the expected outcome of a joint attack against the enemy, subject to a limited amount of resources (i.e. aircraft, tanks). We present a mathematical model for this problem, together with alternative model versions which provide optimistic and a pessimistic approximations. The model is not efficient for large problem instances, hence we also provide heuristic solution approaches and successfully provide solutions to a number of scenarios.

Publisher
90 p.
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2012:6
Keyword
Targeting Problem, Weapon-Target Assignment, Military Operations Research, Decision Support
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-77072 (URN)
Available from: 2012-05-04 Created: 2012-05-04 Last updated: 2015-02-25Bibliographically approved
5. Aircraft Mission Planning
Open this publication in new window or tab >>Aircraft Mission Planning
2012 (English)Report (Other academic)
Abstract [en]

This paper deals with a Military Aircraft Mission Planning Problem, where the problem is to find time efficient flight paths for a given aircraft fleet that should attack a number of ground targets. Due to the nature of the attack, two aircraft need to rendezvous at the target, that is, they need to be synchronized in both space and time. At the attack, one aircraft is launching a guided weapon, while the other is illuminating the target. Each target is associated with multiple attack and illumination options. Further, there may be precedence constraints between targets, limiting the order of the attacks. The objective is to maximize the outcome of the entire attack, while also minimizing the mission time span. We present two mathematical models for this problem and compare their efficiency on some small test cases. We also provide some heuristic approaches since direct application of a general MIP solver to the mathematical model is only practical for smaller scenarios. The heuristics are compared and they successfully provide solutions to a number of scenarios.

Publisher
72 p.
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2012:7
Keyword
Aircraft Routing, Generalized Vehicle Routing Problem, Precedence, Synchronization, Military Operations Research, Decision Support
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-77074 (URN)
Available from: 2012-05-04 Created: 2012-05-04 Last updated: 2015-02-25Bibliographically approved

Open Access in DiVA

Models and Methods for Costly Global Optimization and Military Decision Support Systems(2147 kB)1002 downloads
File information
File name FULLTEXT01.pdfFile size 2147 kBChecksum SHA-512
8d110fbae51ac7bc89ce08e50e415c209239382213c361e6d03781d7f960db4732ed6417ffb12343cec319b2a9b9b6defc6ab46d7d7e4b6b123eba1817a37056
Type fulltextMimetype application/pdf
omslag(83 kB)61 downloads
File information
File name COVER01.pdfFile size 83 kBChecksum SHA-512
f956d478c258e4b6ffd6d02ff7888a8ad5c24e47c71b27eac199da14e11ae8af27a1a3f4a446fb1107733af4ec8a42832c26c6b60c03b6c3ae017bf7b3fb1f35
Type coverMimetype application/pdf

Authority records BETA

Quttineh, Nils-Hassan

Search in DiVA

By author/editor
Quttineh, Nils-Hassan
By organisation
Optimization The Institute of Technology
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 1002 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1198 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf