OR/MS Today - December 2002 Software Review LINDO API Linear, quadratic, MIP callable library is a useful tool for OR/MS practitioners who write their own computer code. By Andy Felt The average optimization software reviewed in OR/MS Today has two parts: the graphical user interface (GUI) and the mathematical engine. LINDO Application Programming Interface (API) is solely an engine that has been purposely separated from the GUI. This makes LINDO API a useful tool to a very focused set of Operations Research/Management Science practitioners — namely, those who write their own computer code. (In this article, we use the word programming in its classical sense to mean the act of planning activities for a large organization using mathematical optimization. A program is a mathematical model of such a situation. Code is used to describe instructions to a computer in any of the common compiled languages: C, C++, Fortran, Java, etc.) LINDO API, from Chicago-based LINDO Systems, Inc., is a library of functions that may be called from within many coding environments. It offers well-organized data structures and powerful linear, mixed integer and quadratic solvers in a linked library. But LINDO API was not intended for those who want to point and click their way through a model to a solution. The intended users of LINDO API are those who wish to access from within their own application the same linear, mixed integer, and quadratic solver engines that are available from other LINDO software. Such users might have their own proprietary modeling environment, or they might be coding a large algorithm that has need for such solvers within, or they might need greater control of the solvers than they have in the other LINDO software. LINDO API is supported on Windows, Linux and Solaris operating systems. In addition to standard hardware requirements (see Product Information box), one needs a coding environment that can link to external libraries. Most C, C++, Fortran, Java and Visual Basic environments fit this need. Alternatively, LINDO API can be called from MATLAB. My own experience with LINDO API has been positive. For two years, LINDO Systems has allowed my research group to use LINDO API inside our own software, CPA. This software implements a generalized cutting plane algorithm for two stage stochastic linear programs. You can try out CPA at the NEOS site: www-neos.mcs.anl.gov. Solvers With LINDO API, what's under the hood is all you get. Three solvers are available: a primal simplex solver, a dual simplex solver and a barrier solver. These solvers are simply the engine from the software LINDO, which offers a graphical front end as well. The barrier solver can handle quadratic objective and constraint functions, while the others are limited to linear functions. The model input data type for each solver is the same, so changing from one solver to another is a simple matter of changing the function call. Each solver can operate within a branch and bound solver for solving mixed integer programs. Data Structures and Input Formats The basic data structures used within LINDO API are flexible, easy to interface and intuitive. The topmost structure is a modeling environment, called LSenv. The environment contains one or more model structures, called LSmodel. Each model is a single linear or quadratic program, complete with model options, data and eventually solutions. The macro-data structure is well thought out and implemented, so that many options may be set globally in the environment wrapper, or superceded at the model level. Model data (the actual LP or QP coefficients) may be placed directly into memory by the calling code, or specified in a file in MPS or LINDO format. Direct entry involves placing your data into a sparse matrix and vector representation that is easy to use and well explained in the documentation. The internal structures appear to make efficient use of computer memory. The software can also write LP (primal or dual) data out in MPS or LINDO format. Users of MATLAB will be glad to know that all LINDO API functions may be called from within MATLAB by using the MATLAB executable MXLINDO. Unfortunately, LINDO API cannot currently interface with mathematical modeling languages like AMPL or GAMS. Examples of function calls The user of LINDO API has many functions that may be called from within a coding environment. The housekeeping routines — license handling, allocation, error handling — are numerous and well organized. It is easy to use quality coding techniques when using LINDO API. Figure 1 shows a minimal coding example, where the environment is created, the data is loaded, and the LP is solved. In addition to these basic calls, LINDO API provides a group of functions for modifying the model. One may add, delete or modify any of the model features: constraints, variables, quadratic data, integer data, right hand side coefficients, etc. Warm starts can be implemented by specification of a starting basis. Minimal Coding Example /* myexample.c A C code example for solving the following LP: Maximize 3 x1 + 4 x2 subj. to x1 + x2 <= 6 x1 <= 4 x1 + 2 x2 <= 11 -x1 + x2 >= -2 x1 >= 0 x2 >= 0 This is meant to be a minimal example, with very little with respect to error checking, memory management, etc. */ #include <stdlib.h> #include <stdio.h> /* LINDO API header file */ #include "lindo.h" /* license.h must be edited to include the license key that came with your software */ #include "license.h" /* main entry point */ int main() { int nErrorCode; /* Number of constraints */ int nM = 4; /* Number of variables */ int nN = 2; /* declare an instance of the LINDO environment object */ pLSenv pEnv; /* declare an instance of the LINDO model object */ pLSmodel pModel; /* *>>> Step 1 <<< Create a LINDO environment. */ pEnv = LScreateEnv ( &nErrorCode, MY_LICENSE_KEY); /* *>>> Step 2 <<< Create a model in the environment. */ pModel = LScreateModel ( pEnv, &nErrorCode); /* * >>>> Step 3 <<< Specify the linear portion of the model. */ /* The direction of optimization */ int objsense = LS_MAX; /* The objective's constant term */ double objconst = 0.; /* The objective's linear term */ double c[2] = { 3., 4. }; /* The right-hand sides of the constraints */ double rhs[4] = { 6.0, 4., 11., -2. }; /* The constraint types */ char contype[4] = { 'L','L','L','G' }; /* The number of nonzeros in the constraint matrix */ int Anz = 7; /* The indices of the first nonzero in each column */ int Abegcol[3] = { 0, 4, Anz }; /* The last entry is always the number of nonzeros */ /* The length of each column. We can set this to NULL if we do not expect to add rows later. */ int *Alencol = NULL; /* The nonzero coefficients by column */ double A[7] = { 1., 1., 1., -1., 1., 2., 1. }; /* The row indices of the nonzero coefficients */ int Arowndx[7] = { 0, 1, 2, 3, 0, 2, 3 }; /* By default, all variables have a lower bound of zero * and an upper bound of infinity. Therefore pass NULL * pointers in order to use these default values. */ double *lb = NULL, *ub = NULL; /* Pass the linear portion of the data to problem structure * by a call to LSloadLPData() */ nErrorCode = LSloadLPData( pModel, nM, nN, objsense, objconst,c, rhs, contype, Anz, Abegcol, Alencol, A, Arowndx, lb, ub); /* >>>Step 4<<< Pass the integrality restriction to problem structure * by a call to LSloadMIPData() */ char vartype[14] ={ 'C','I'}; /* C means continuous, I means integer, B means binary */ nErrorCode = LSloadMIPData(pModel, vartype); /* * >>> Step 5 <<< Invoke the Branch & Bound solver*/ nErrorCode = LSsolveMIP( pModel, NULL); /* >>> Step 6 <<< Retrieve the MIP solution */ int i; double x[2], MipObj; /* Get the value of the objective and solution */ LSgetMIPSolution( pModel, &MipObj, x) ; printf ("*** Optimal Objective Value= %f\n", MipObj); for (i = 0; i < nN; i++) printf( "Optimal solution for variable %d: %5.2f \n", i+1, x[i] ); printf ("\n"); * >>> Step 7 <<< Delete the LINDO environment */ nErrorCode = LSdeleteEnv( pEnv); } For those working on very large codes, the callback feature may be useful. If this feature is set, the solver periodically checks in with the calling function, at which time the current status may be probed, adjustments made or the solver terminated. Installation and technical support The installation of LINDO API is straightforward on one hand and tricky on the other. On a Windows system, an install wizard makes installation easy. In Linux, a README file takes the user through an easy three-step installation process. LINDO has certainly done their part to make the setup of LINDO API easy. However, there is a certain level of difficulty inherent in the use of callable libraries in general. The problems usually arise during the linking phase, when the compiler tries to find and use the LINDO libraries. Here, the user must wade through the swamp of compiler settings, environment variables and standard library version compatibility to try to find the magic setup that works. This can be daunting for the inexperienced code warrior. The good news is that LINDO Systems provides excellent technical support. There is a real phone number that is answered by a real person (do I sound jaded?), and in a single transfer the caller finds that he/she is talking to a real developer of LINDO API. The service is prompt and effective. The developers even listen to suggestions. Last spring, I suggested a small change in the format of one of the function calls. It was implemented in the next few months. Documentation The documentation that accompanies LINDO API is extensive and well written. Each callable function and parameter is described, and several examples of calling code are given. The examples show a variety of calling languages (C, C++, Java, Visual Basic and MATLAB). The examples given in the documentation are supposed to match files that are distributed with the library. However, some of these (probably the accompanying files) have been changed, so that the user should treat the accompanying files as additional examples, rather than exact implementations of the examples in the documentation. In addition, appendices on MPS and LINDO file formats are provided. Conclusion LINDO Systems has put forward a solid competitor in the callable optimization library market. LINDO API does not have as many features as some of its competitors (e.g. stochastic optimization solver and parallel computing), but if you only want a basic LP, MIP or QP solver, you can get a great value with LINDO API. Product Summary System Requirements The minimum memory required to run EO 4.0 is 64MB, but 256MB is recommended. A 2 GB hard drive is required with a minimum of 650 MB of free disk space. Windows operating systems beginning with Windows 95 are supported. Excel 97 (or later) and the 32-bit ODBC driver are required. Product Information LINDO API is available from: LINDO Systems, Inc. 1415 North Dayton Street Chicago, IL 60622 Tel: (800) 441-2378 Fax: (312) 988-9065 E-mail: webinfo@lindo.com URL: http://www.lindo.com Pricing Information: $395-$5,195 (depending on problem size and solver options) • Educational licenses available • Commercial runtime licenses (for embedding LINDO API into commercial software) available Standard Hardware Requirements: • Operating system: Windows (32 bit), Linux, Solaris • Minimum RAM: 32 MB • Minimum Hard Drive free space: 20 MB Vendor Comments Editor's note: It is the policy of OR/MS Today to allow developers of reviewed software an opportunity to clarify and/or comment on the review article. Following are comments from Mark Wiley, vice president-marketing, LINDO Systems, Inc. We thank Andy Felt for the thorough review. We mention a few additional features of the LINDO API that may be of interest. LINDO API is threadsafe for linear and integer models, meaning that it can be used in Web-based applications where several copies of it may be running simultaneously. For models containing bugs, the API has a capability for identifying minimal sets of infeasible constraints, or minimal sets of unbounded variables. Although the review is of the API as a stand-alone solver, it is used as the solver engine in the LINGO modeling language and in the What'sBest spreadsheet add-in. Since the review was written, several new features have been added to the LINDO API. These features should be available about the time that this review appears. The most notable new feature is that general purpose nonlinear capability has been added. The nonlinear capability is integrated with the MIP capability so that a model may have both nonlinearities and integer variables. The nonlinear capability is notable in that it includes global optimization in two flavors: a) a multi-start capability, and b) a guaranteed global capability. The multi-start capability is useful for quickly finding better solutions when a nonconvex model has several local optima. The guaranteed global capability will rigorously find a global optimum if allowed to run to completion. The nonlinear capability supports a wide range of functions such as abs(x), max(x,y), sin(x), etc. Java Native Interface (JNI) support has been added to allow the solvers to be called in applets from a Web browser, and support has been improved for developers using C/C++, VB and FORTRAN. Software Review Editor Mohan Sodhi, a member of the Operations Management faculty at Cass Business School in London, is the software review editor for OR/MS Today. Reviewers interested in reviewing software and vendors interested in having their software reviewed should reach Sodhi directly at M.Sodhi@city.ac.uk. Andy Felt (afelt@uwsp.edu) is an assistant professor of Mathematics and Computing at the University of Wisconsin-Stevens Point. He has developed software for the pulp and paper industry, as well as for his own research in stochastic linear programming. In addition, Felt has five years experience as a chemical engineer. Table of Contents OR/MS Today Home Page OR/MS Today copyright © 2003 by the Institute for Operations Research and the Management Sciences. All rights reserved. Lionheart Publishing, Inc. 506 Roswell Rd., Suite 220, Marietta, GA 30060 USA Phone: 770-431-0867 | Fax: 770-432-6969 E-mail: lpi@lionhrtpub.com URL: http://www.lionhrtpub.com Web Site © Copyright 2003 by Lionheart Publishing, Inc. All rights reserved.