Benchmarking Optimization Software with COPS 3 - ANL

ARGONNE NATIONAL LABORATORY 9700 South Cass Avenue Argonne, Illinois 60439

Benchmarking Optimization Software with COPS 3.0

Elizabeth D. Dolan, Jorge J. Mor?e and Todd S. Munson Mathematics and Computer Science Division Technical Report ANL/MCS-TM-273 February 2004

This work was supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, Office of Science, U.S. Department of Energy, under Contract W-31-109-Eng-38, by the National Science Foundation grant DMI-0322580.

Contents

1 Largest Small Polygon

3

2 Distribution of Electrons on a Sphere

5

3 Shape Optimization of a Cam

7

4 Hanging Chain

9

5 Isometrization of -pinene

11

6 Marine Population Dynamics

13

7 Flow in a Channel

16

8 Robot Arm

18

9 Particle Steering

21

10 Goddard Rocket

23

11 Hang Glider

26

12 Catalytic Cracking of Gas Oil

29

13 Methanol to Hydrocarbons

31

14 Catalyst Mixing

33

15 Elastic-Plastic Torsion

35

16 Journal Bearing

37

17 Minimal Surface with Obstacle

39

18 Triangular Mesh Smoothing

41

19 Tetrahedral Mesh Smoothing

44

20 Transition States for the Lane-Emden Problem

47

21 Transition States for the Dirichlet Problem

49

22 Transition States for the Henon Problem

51

Benchmarking Optimization Software with COPS 3.0

Elizabeth D. Dolan, Jorge J. Mor?e, and Todd S. Munson

Abstract

We describe version 3.0 of the COPS set of nonlinearly constrained optimization problems. We have added new problems, as well as streamlined and improved most of the problems. We also provide a comparison of the FILTER, KNITRO, LOQO, MINOS, and SNOPT solvers on these problems.

Introduction

The COPS [12] test set provides a modest selection of difficult nonlinearly constrained optimization problems from applications in optimal design, fluid dynamics, parameter estimation, and optimal control, among others. In this report we describe version 3.0 of the COPS problems. The formulation and discretization of the original problems have been streamlined and improved. We have also added new problems.

For each problem we discuss the formulation of the problem. We also present the structural data in the table below in order to provide an approximate idea of the size and sparsity of the problem.

Variables Constraints Bounds Linear equality constraints Linear inequality constraints Nonlinear equality constraints Nonlinear inequality constraints Nonzeros in 2f (x) Nonzeros in c (x)

We include the results of computational experiments with the FILTER [13], KNITRO [35], LOQO [33], MINOS [25], and SNOPT [17] solvers. As part of the benchmarking process we have introduced an analyzer to help determine whether the quality of the solution returned by any particular solver meets our expectations. The analyzer will be described in a separate report. We have also introduced software scripts specifically designed to benchmark this test set.

This work was supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, Office of Science, U.S. Department of Energy, under Contract W-31-109-Eng-38, by the National Science Foundation grant DMI-0322580.

Department of Industrial Engineering and Management Sciences, Northwestern University, and Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Illinois 60439. dolan@mcs..

Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Illinois 60439. {tmunson,more}@mcs..

1

Testing Methods

We have devised a set of Perl scripts for running a problem on each solver successively, so as to minimize the effect of fluctuation in the machine load. The scripts track the wall-clock time from the start of the solve, killing any process that runs for more than 1800 seconds, which we declare unsuccessful. We cycle through all problem variants, recording the wallclock time as well as the combination of AMPL system time (to interpret the model and compute varying amounts of derivative information required by each solver) and solver time. We consider the times returned by AMPL definitive, but we initially record the wall-clock times to check for discrepancies in the solvers' methods of calculating execution time. We include no problem results for which the AMPL time and the wall-clock time differ by more than ten percent. To further ensure consistency, we have verified that the AMPL time results we present could be reproduced to within five percent accuracy.

We examine the solver result number returned by each AMPL solver, but a successful return code is only the first step we take to check on the solver's work. As each solve completes, we run the analyzer to check the solution written. If the feasibility and optimality tests fail to meet our standards, we tighten whatever tolerance option applies for that solver by an order of magnitude and rerun the job. If the tolerance reaches 1.0e-16 and the solution reported does not meet our goals, then the solver fails the benchmark test, and we use the symbol in the appropriate table. We also check the solution returned by the AMPL solver when an unsuccessful return code is reported. These cases are marked with the symbol in the appropriate table. Sometimes the benchmark test indicates that a solution has been obtained to within our tolerances.

Regarding solver options, we also increase iteration, super-basics, and memory size limits that might artificially cause a solver to fail. Printed output is reduced to its lowest level for each solver. The testing method described is more strict than anything we have done in the past, but the results we obtained from default options varied widely in quality. We felt that some independent measurement, while its specifics might be argued, would enhance the worth of the benchmark as a whole.

All computations were performed on an Intel Pentium 4 1.8GHz CPU with 512M of RAM and a 256Kb cache, running Red Hat 7.3. The tested solvers include

filterSQP, ASL (20020923) KNITRO 3.0, ASL (20020905) LOQO 6.02, ASL (20020221) MINOS 5.5, ASL (20020614) SNOPT 6.1, ASL (20020614)

The source code for all the problems in this report and for the analyzer is included with the distribution [12] of COPS 3.0.

2

1 Largest Small Polygon

Find the polygon of maximal area, among polygons with nv sides and diameter d 1.

Formulation

This is a classic problem (see, for example, Graham [19]). If (ri, i) are the coordinates of the vertices of the polygon, then we must maximize

nv -1

f (r, )

=

1 2

ri+1ri sin(i+1 - i)

i=1

subject to the constraints

ri2 + rj2 - 2rirj cos(i - j) 1, i i+1,

i [0, ], ri 0,

1 i < nv, 1 i < nv, 1 i nv.

i < j nv,

Our implementation follows [16] and fixes the last vertex by setting rnv = 0 and nv = . By fixing a vertex at the origin, we can add the bounds ri 1.

Graham [19] showed that the optimal solution is regular for odd n but not regular for

even n except n = 4. Another interesting feature of this problem is the presence of order n2v nonlinear nonconvex inequality constraints. We also note that as nv , we expect the

maximal area to converge to the area of a unit-diameter circle, /4 0.7854. This problem has many local minima. For example, for nv = 4 a square with sides of length 1/ 2 and an

equilateral triangle with another vertex added at distance 1 away from a fixed vertex are

both

global

solutions

with

optimal

value

f

=

1 2

.

Indeed,

the

number

of

local

minima

is

at

least O(nv!). Thus, general solvers are usually expected to find only local solutions. Data

for this problem appears in Table 1.1.

Table 1.1: Largest-small polygon problem data

Variables Constraints Bounds Linear equality constraints Linear inequality constraints Nonlinear equality constraints Nonlinear inequality constraints Nonzeros in 2f (x) Nonzeros in c (x)

2(nv - 1)

(

1 2

nv

+

1)(nv

-

1)

-

1

2(nv - 1)

0

nv - 2

0

1 2

nv

(nv

-

1)

11(nv - 1) - 8

2nv(nv - 1) - 2

Performance Results for the AMPL implementation are summarized in Table 1.2. A polygon with almost equal sides is the starting point. Global solutions for several nv are shown in Figure 1.1.

3

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download