×

DrAmpl: A meta solver for optimization problem analysis. (English) Zbl 1243.90005

Summary: Optimization problems modeled in the AMPL modeling language may be examined by a set of tools found in the AMPL Solver Library. DrAmpl is a meta solver which, by use of the AMPL Solver Library, dissects such optimization problems, obtains statistics on their data, is able to symbolically prove or numerically disprove convexity of the functions involved and provides aid in the decision for an appropriate solver. A problem is associated with a number of relevant solvers available on the NEOS Server for Optimization by means of a relational database. We describe the need for such a tool, the design of DrAmpl and some of its consequences, and keep in mind that a similar tool could be developed for other algebraic modeling languages.

MSC:

90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
90C30 Nonlinear programming
90C35 Programming involving graphs or networks
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bauer FL (1974) Computational graphs and rounding error. SIAM J Numer Anal 11(1): 87–96 · Zbl 0337.65028
[2] Brooke A, Kendrick D, Meeraus A (1998) GAMS: a users’ guide. GAMS Development Corporation, Washington
[3] Byrd RH, Gilbert J-Ch, Nocedal J (2000) A trust region method based on interior point techniques for nonlinear programming. Math Program Ser A 89(1): 149–185 · Zbl 1033.90152
[4] Byrd RH, Gould NIM, Nocedal J, Waltz RA (2006) On the convergence of successive linear-quadratic programming algorithms. SIAM J Optim 16(2): 471–489 · Zbl 1092.90061
[5] Chinneck J (2001) Analyzing mathematical programs using MProbe. Ann Oper Res 104: 33–48 · Zbl 1007.90064
[6] Conn AR, Gould NIM, Toint PL (1992) LANCELOT, a Fortran package for large-scale nonlinear optimization (Release A). Number 17 in Springer Series in Computational Mathematics. Springer-Verlag, New York · Zbl 0761.90087
[7] Czyzyk J, Mesnier M, Moré JJ (1998) The NEOS server. IEEE J Comput Sci Eng 5: 68–75 · Zbl 05092192
[8] Dolan E (2001) The NEOS server 4.0 administrative guide. Technical Memorandum ANL/MCS-TM-250, The Mathematical and Computer Science Division, Argonne National Laboratory, Argonne, IL
[9] Dolan ED, Moré JJ (2001a) Benchmarking optimization software with COPS. Technical Report ANL/MCS-246, Argonne National Laboratory
[10] Dolan ED, Moré JJ (2001b) http://www.mcs.anl.edu/\(\sim\)more/cops
[11] Fletcher R, Gould NIM, Leyffer S, Toint PL, Wächter A (2002) On the global convergence of trust-region SQP-filter algorithms for general nonlinear programming. SIAM J Optim 13(2): 635–659 · Zbl 1038.90076
[12] Fourer R, Gay DM, Kernighan BW (2002) AMPL: a modeling language for mathematical programming, 2nd edn. Duxbury Press
[13] Fourer R, Maheshwari C, Neumaier A, Orban D, Schichl H (2009) Convexity and concavity detection in computational graphs: tree walks for convexity proving. INFORMS J Comput. doi: 10.1287/ijoc.1090.0321 (Published online ahead of print) · Zbl 1243.90004
[14] Gay DM (1991) Automatic differentiation of nonlinear AMPL models. In: Griewank A, Corliss G (eds) Automatic differentiation of algorithms: theory, implementation, and application. SIAM, Philadelphia, pp 61–73 · Zbl 0782.65026
[15] Gay DM (1996a) Automatically finding and exploiting partially separable structure in nonlinear programming problems. Numerical Analysis Manuscript. AT&T Bell Laboratories
[16] Gay DM (1996) More AD of nonlinear AMPL models: computing Hessian information and exploiting partial separability. In: Corliss G, Berz M, Bischof C, Griewank A (eds) Computational differentiation: techniques, applications and tools. SIAM, Philadelphia, pp 173–184 · Zbl 0866.65018
[17] Gay DM (1997) Hooking your solver to AMPL. Technical Report 97-4-06. Lucent Technologies Bell Labs Innovations, Murray Hill, NJ. http://www.ampl.com/REFS/HOOKING
[18] Gill P, Murray W, Saunders M (1997) User’s guide for SNOPT 5.3: a Fortran package for large-scale nonlinear programming. Regents of the University of California, Board of Trustees of Stanford University
[19] Gould NIM, Lucidi S, Roma M, Toint PL (1999) Solving the trust-region subproblem using the Lanczos method. SIAM J Optim 9(2): 504–525 · Zbl 1047.90510
[20] Grant MC, Boyd S, Ye Y (2006) Disciplined convex programming. In: Liberti L, Maculan N (eds) Global optimization: from theory to implementation, nonconvex optimization and its applications. Springer, New York, pp 155–210 · Zbl 1130.90382
[21] Griewank A (2000) Evaluating derivatives: principles and techniques of algorithmic differentiation. Number FR19 in Frontiers in Applied Mathematics. SIAM · Zbl 0958.65028
[22] Gropp W, Moré JJ (1997) Optimization environments and the NEOS server. In: Buhmann MD, Iserles A (eds) Approximation theory and optimization. Cambridge University Press, Cambridge, pp 167–182 · Zbl 1031.65075
[23] Kantorovich LV (1957) On a mathematical symbolism convenient for performing machine calculations. Dokl Akad Nauk SSSR 113(4): 738–741 (in Russian) · Zbl 0080.11601
[24] Nenov IP, Fylstra DH, Kolev LV (2004) Convexity determination in the microsoft excel solver using automatic differentiation techniques. Technical Report, Frontline Systems Inc., Incline Village NV, USA
[25] Schichl H, Neumaier A (2005) Interval analysis on directed acyclic graphs for global optimization. J Glob Optim 33(4): 541–562 · Zbl 1094.65061
[26] Spellucci P (1998) An SQP method for general nonlinear programs using only equality constrained subproblems. Math Program 82(3): 413–448 · Zbl 0930.90082
[27] Vanderbei RJ, Shanno DF (1999) An interior point algorithm for nonconvex nonlinear programming. Comput Optim Appl 13(3): 231–252 · Zbl 1040.90564
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.