×

zbMATH — the first resource for mathematics

OSiL: An instance language for optimization. (English) Zbl 1189.90007
Summary: Distributed computing technologies such as Web Services are growing rapidly in importance in today’s computing environment. In the area of mathematical optimization, it is common to separate modeling languages from optimization solvers. In a completely distributed environment, the modeling language software, solver software, and data used to generate a model instance might reside on different machines using different operating systems. Such a distributed environment makes it critical to have an open standard for exchanging model instances.
In this paper we present OSiL (Optimization Services instance Language), an XML-based computer language for representing instances of large-scale optimization problems including linear programs, mixed-integer programs, quadratic programs, and very general nonlinear programs. OSiL has two key features that make it much superior to current standard forms for optimization problem instances. First, it uses the object-oriented features of XML schemas to efficiently represent nonlinear expressions. Second, its XML schema maps directly into a corresponding in-memory representation of a problem instance. The in-memory representation provides a robust application program interface for general nonlinear programming, facilitates reading and writing postfix, prefix, and infix formats to and from the nonlinear expression tree, and makes the expression tree readily available for function and derivative evaluations.

MSC:
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90Cxx Mathematical programming
68M11 Internet topics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques and Tools. Addison-Wesley, Reading (1986) · Zbl 1155.68020
[2] Bell, B.: CppAD: A package for C++ algorithmic differentiation. http://www.coin-or.org/CppAD/ (2006)
[3] Bischof, C.H., Bücker, H.M., Marquardt, W., Petera, M., Wyes, J.: Transforming equation-based models in process engineering. In: Bücker, H.M., Corliss, G., Hovland, P., Naumann, U., Norris, B. (eds.) Automatic Differentiation: Applications, Theory, and Implementations. Lecture Notes in Computational Science and Engineering, pp. 189–198. Springer, Berlin (2005) · Zbl 1270.68385
[4] Bradley, G.: Introduction to extensible markup language (XML) with operations research examples. ICS Newsl. 24, 1–20 (2003)
[5] Bradley, G.: Network and graph markup language (NaGML)–data file formats. Technical Report NPS-OR-04-007, Department of Operations Research, Naval Postgraduate School, Monterey, CA, USA (2004). Available from the author, bradley@nps.navy.mil
[6] Chang, T.-H.: Modelling and presenting mathematical programs with xml:lp. Masters thesis, Department of Management, University of Canterbury, Christchruch, NZ (2003)
[7] Czyzyk, J., Mesnier, M.P., Moré, J.J.: The NEOS server. IEEE J. Comput. Sci. Eng. 5, 68–75 (1998) · Zbl 05092192 · doi:10.1109/99.714603
[8] Dolan, E.D., Fourer, R., Goux, J.-P., Munson, T.S., Sarich, J.: Kestrel: An interface from optimization modeling systems to the NEOS server. Technical report, Optimization Technology Center, Northwestern University, Evanston, IL and Mathematics & Computer Science Division, Argonne National Laboratory, Argonne, IL (2006). http://www.optimization-online.org/DB_HTML/2007/01/1559.html · Zbl 1243.90002
[9] Dolan, E.D., Fourer, R., Moré, J.J., Munson, T.S.: Optimization on the NEOS server. SIAM News 35(6), 4–9 (2002).
[10] Ezechukwu, O.C., Maros, I.: OOF: open optimization framework. Technical Report ISSN 1469-4174, Department of Computing, Imperial College of London, London, UK (2003)
[11] Fourer, R., Gay, D.M.: Extending an algebraic modeling language to support constraint logic programming. INFORMS J. Comput. 14, 322–344 (2002) · Zbl 1238.90113 · doi:10.1287/ijoc.14.4.322.2825
[12] Fourer, R., Gay, D.M., Kernighan, B.W.: A modeling language for mathematical programming. Manag. Sci. 36, 519–554 (1990) · Zbl 0701.90062 · doi:10.1287/mnsc.36.5.519
[13] Fourer, R., Lopes, L., Martin, K.: LPFML: A W3C XML schema for linear and integer programming. INFORMS J. Comput. 17, 139–158 (2005) · Zbl 1239.90071 · doi:10.1287/ijoc.1040.0120
[14] Fourer, R.: Modeling languages versus matrix generators for linear programming. ACM Trans. Math. Softw. 9, 143–183 (1983) · doi:10.1145/357456.357457
[15] Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming, 2nd edn. Brooks/Cole, Pacific Grove (2003) · Zbl 0701.90062
[16] Gay, D.M.: Hooking your solver to AMPL (revised 1994, 1997). Technical report, Bell Laboratories, Murray Hill, NJ (1993)
[17] Griewank, A.: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM, Philadelphia (2000) · Zbl 0958.65028
[18] Halldórsson, B.V., Thorsteinsson, E.S., Kristjánsson, B.: A modeling interface to non-linear programming solvers an instance: xMPS, the extended MPS format. Technical report, Carnegie Mellon University and Maximal Software (2000)
[19] Kristjánsson, B.: Optimization modeling in distributed applications: how new technologies such as XML and SOAP allow OR to provide web-based services (2001). http://www.maximal-usa.com/slides/Svna01Max/index.htm
[20] Lindo Systems, Inc.: LINDO API user’s manual. Technical report, Lindo Systems, Inc. (2002). http://www.lindo.com/lindoapi_pdf.zip
[21] Lougee-Heimer, R.: The Common Optimization INterface for operations research. IBM J. Res. Dev. 47(1), 57–66 (2003) · Zbl 05420370 · doi:10.1147/rd.471.0057
[22] Lustig, I.J., Puget, J.-F.: Program program: Constraint programming and its relationship to mathematical programming. Interfaces 31(6), 29–53 (2001)
[23] Ma, J.: Optimization services (OS), a general framework for optimization modeling systems. Ph.D. Dissertation, Department of Industrial Engineering & Management Sciences, Northwestern University, Evanston, IL (2005)
[24] Rosenbrock, H.H.: An automatic method for finding the greatest or least value of a function. Comput. J. 3, 175–184 (1960) · doi:10.1093/comjnl/3.3.175
[25] Sandhu, P.: The MathML Handbook. Charles River Media, Hingham (2003) · Zbl 1041.68122
[26] Skonnard, A., Gudgin, M.: Essential XML Quick Reference. Pearson Education, Boston (2002)
[27] Van Hentenryck, P.: Constraint and integer programming in OPL. INFORMS J. Comput. 14, 345–372 (2002) · Zbl 1238.90102 · doi:10.1287/ijoc.14.4.345.2826
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.