Global Optimization: From Theory to Implementation

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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

VIII Contents

8 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

Contents IX

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

X Contents

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