Most books about global optimization describe the theory of the algorithms, whereas a given implementation's quality never depends exclusively on the theoretical soundness of the algorithms that are implemented. The literature rarely discusses the tuning of algorithmic parameters, implementation tricks, software architectures, and the embedding of local solvers within global solvers. And yet, there are many good software implementations out there from which the entire community could learn something. The scope of this book is moving a few steps toward the systematization of the path that goes from the invention to the implementation and testing of a global optimization algorithm. Some of the contributors to the book are famous and some are less well-known, but all are experts in the discipline of actually getting global optimization to work. Thus, the papers in this book address the following topics: Descriptions of new implementations of general-purpose or problem-specific global optimization algorithms; New algorithms in global optimization (some with numerical results and a discussion of the implementation); Surveys discussing existing software packages
Optimization under Composite Monotonic Constraints and
Constrained Optimization over the Efficient Set
Hoang Tuy, N.T. Hoai-Phuong. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Some basic concepts and results of monotonic optimization . . . . . . . . 5
3 Problems with composite monotonic constraints . . . . . . . . . . . . . . . . . . 7
4 Constrained optimization over the efficient set . . . . . . . . . . . . . . . . . . . 11
5 Solution method for problem (Q) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6 Improvements for problems (OWE) and (OE) . . . . . . . . . . . . . . . . . . . . 19
7 Problems with a composite monotonic objective function . . . . . . . . . . 25
8 Illustrative examples and computational results . . . . . . . . . . . . . . . . . . 26
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
On a Local Search for Reverse Convex Problems
Alexander Strekalovsky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2 Some features of RCP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3 Local search methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Computational testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Some Transformation Techniques in Global Optimization
Tapio Westerlund . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2 The MINLP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3 The transformation approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4 Examples of transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5 The GGPECP algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6 Convergence to the globally optimal solution . . . . . . . . . . . . . . . . . . . . . 57
7 A numerical example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598 Some aspects on the numerical solution approach . . . . . . . . . . . . . . . . . 64
9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Solving Nonlinear Mixed Integer Stochastic Problems: a
Global Perspective
Maria Elena Bruni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3 SMINLP: state of the art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5 The two-phase solution approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6 Illustrative application: the Stochastic Trim Loss Problem . . . . . . . . . 98
7 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Application of Quasi Monte Carlo Methods in Global
Optimization
Sergei Kucherenko . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
2 Analysis of Quasirandom Search methods . . . . . . . . . . . . . . . . . . . . . . . 114
3 Single linkage and multilevel single linkage methods . . . . . . . . . . . . . . . 117
4 Computational experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
GLOB - A new VNS-based Software for Global Optimization
M. Drazi´c, V. Kovacevic-Vujci´c, M. Cangalovi´c, N. Mladenovi´c . . . . . . . 135
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
2 VNS methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
3 Software package GLOB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Disciplined Convex Programming
Michael Grant, Stephen Boyd, Yinyu Ye . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
3 Convex programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4 Modeling frameworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
5 Disciplined convex programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
6 The convexity ruleset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
7 The atom library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
8 Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
9 Creating disciplined convex programs . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 10 Implementing atoms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
Writing Global Optimization Software
Leo Liberti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
2 Global Optimization algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
3 Global Optimization software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
4 Optimization software framework design . . . . . . . . . . . . . . . . . . . . . . . . . 232
5 Symbolic manipulation of mathematical expressions . . . . . . . . . . . . . . 240
6 Local solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
7 Global solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
MathOptimizer Professional: Key Features and Illustrative
Applications
J´anos D. Pint´er, Frank J. Kampas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
2 Global Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
3 LGO Solver Suite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
4 MathOptimizer Professional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
5 Illustrative applications: solving sphere packing models . . . . . . . . . . . . 271
6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
Variable Neighborhood Search for Extremal Graphs 14: The
AutoGraphiX 2 System
M. Aouchiche, J.M. Bonnefoy, A. Fidahoussen, G. Caporossi,
P. Hansen, L. Hiesse, J. Lacher´e, A. Monhait . . . . . . . . . . . . . . . . . . . . . . . 281
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
2 AGX 2 Interactive functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
3 Algebraic syntax used in AutoGraphiX . . . . . . . . . . . . . . . . . . . . . . . . . . 291
4 Optimization using Variable Neighborhood Search . . . . . . . . . . . . . . . . 294
5 AutoGraphiX Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
6 Automated proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
7 Some examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
From Theory to Implementation: Applying Metaheuristics.
I.J. Garc´ýa del Amo, F. Garc´ýa L´opez, M. Garc´ýa Torres,, B. Meli´an
Batista, J.A. Moreno P´erez, J.M. Moreno Vega . . . . . . . . . . . . . . . . . . . . . . 311
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
2 Class hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 3 Implementation: The p-Median Problem . . . . . . . . . . . . . . . . . . . . . . . . . 333
4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
ooMILP - A C++ Callable Object-oriented Library and the
Implementation of its Parallel Version using CORBA
Panagiotis Tsiakis, Benjamin Keeping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
2 ooMILP Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
3 C++ objects and pre-CORBA serial implementation . . . . . . . . . . . . . . 357
4 Initial CORBA Version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
5 Partially decomposable MILPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
6 Parallel solution software architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
Global Order-Value Optimization by means of a Multistart
Harmonic Oscillator Tunneling Strategy
R. Andreani, J.M. Martinez, M. Salvatierra, F. Yano . . . . . . . . . . . . . . . . . 379
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
2 Local algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
3 Lissajous motions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
4 Global algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
5 Hidden patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
6 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
On generating Instances for the Molecular Distance Geometry
Problem
Carlile Lavor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
2 Mor´e-Wu instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
3 New instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
