Guía de referencia de lp_solve 5.5

Nota: Esta página es la traducción (en curso) al español de http://lpsolve.sourceforge.net/5.5/.

¿Qué es lp_solve y qué no es? La respuesta simple es, lp_solve resuelve problemas de programación lineal entera mixta.

¿Y qué es la programación lineal? Véase “¿Qué es la programación lineal?” y “Oh, y nosotros también queremos resolverlo como un problema entero.” para una breve descripción. Véase también “Formulación de un problema lineal en lp_solve”.

lp_solve es una aplicación libre (véase licencia pública genral menor de GNU, LGPL) para programación lineal (entera) basado en el método símplex revisado y en ramificación y acotación para variables enteras.

Contiene el código fuente completo, ejemplos y manuales.

lp_solve resuelve problemas lineales puros, (mixtos) enteros/binarios, semi-continuos y conjuntos ordenados especiales (SOS). Observe la palabra lineal. Esto significa que las ecuaciones deben ser de primer orden. 5 * x - 3* y es un ejemplo. Por el contrario x * y no es lineal y no puede ser tratada por lp_solve. La función objetivo y las restricciones deben ser lineales. Véase también “tasas”.

Mediante el algoritmo de ramificación y acotación, puede tratar variables enteras (véase variables enteras), variables semicontinuas (véase variables semicontinuas) y conjuntos ordenados especiales (véase conjuntos ordenados especiales (SOS)).

lp_solve no tiene limitaciones en el tamaño del modelo y acepta ficheros lp o mps, pero esto puede ser ampliado. Observe no obstante, que lp_solve podría necesitar mucho tiempo o incluso fallar en la resolución de algunos modelos. Los modelos grandes favorecen tal situación. Pero incluso el software comercial tiene problemas con ellos. También puede ser llamado como una librería desde diferentes lenguajes como C, VB, .NET, Delphi, Excel, Java, … También puede ser llamdo desde AMPL, MATLAB, O-Matrix, Scilab, Octave, R a través de un via a driver program. lp_solve is written in ANSI C and can be compiled on many different platforms like linux and WINDOWS. lp_solve tiene su propia comunidad en los grupos de Yahoo http://groups.yahoo.com/group/lp_solve/. Allí pueden encontrarse las últimas fuentes, ejecutables para las plataformas más comunes, ejemplos, manuales y una lista de correo donde la gente puede compartir sus pensamientos sobre lp_solve.

lp_solve fue inicialmente desarrollado por Michel Berkelaar en Eindhoven University of Technology. El trabajo de Jeroen Dirks supuso la transición de la versión básica 1.5 a la versión completa 2.0. He contributed the procedural interface, a built-in MPS reader, and many fixes and enhancements to the code. At that point there was also a Java port of lp_solve 2.0. This was not a Java native interface (JNI) to the C library, but rather a translation of the algorithm (ver 2.0) from C into Java. It was also very limited This meant that it did not keep up with lp_solve as it evolved. Starting at version 3.0, lp_solve is released under the LGPL license. Before the code could only be used for non-commercial purposes. Many other people also contributed to lp_solve, but there was no track of them. Sorry if you are not mentioned. Development was stagnated for some time at version 3.2, but now it is again alive and well via the new developers Kjell Eikland and Peter Notebaert. But also other people help to improve the product. For example the new Java interface to lp_solve was made by Juergen Ebert. It is a JNI interface that supports the full functionality of lp_solve. He did a great job. We encourage other people to participate in the development of lp_solve. First a version 4 was introduced that had already several enhancements and improvements and now with version 5 this enhancement continues resulting is faster solving times, more stability and able to solver larger models and new functionality. See Changes from version 4 to version 5.1 for the changes done to version 5 and Changes from version 5.1 to version 5.5 for the changes done to version 5.5.

Basically, lp_solve is a library, a set of routines, called the API that can be called from almost any programming language to solve MILP problems. There are several ways to pass the data to the library:

• Via the API
• Via input files
• Via an IDE

Via the API The API is a set of routines that can be called from a programming language to build the model in memory, solve it and return the results. There are many API routines to perform many possible tasks and set several options. See lp_solve API reference for an overview.

Via input files

Standard, lp_solve supports several input files types. The common known MPS format (see mps-format) is supported by most solvers, but it is not very readable for humans. Another format is the lp format (see lp-format) that is more readable. lp_solve has the unique ability to use user-written routines to input the model (see External Language Interface). See read_mps, read_freemps, read_MPS, read_freeMPS and read_lp, read_LP for the API calls to read the model from file.

There is also a driver program called lp_solve that uses the API to provide a command line application to solve models. See lp_solve for its usage. With this program you don't have to know anything of API or computer programming languages. You can just provide your model via file to the program and it will solve the model and give you the result. Via an IDE

Thanks to Henri Gourvest, there is now also an IDE program called LPSolve IDE that uses the API to provide a Windows application to solve models. See LPSolve IDE for its usage. With this program you don't have to know anything of API or computer programming languages. You can just provide your model to the program and it will solve the model and give you the result.

As already stated, lp_solve can be called from many programming language. Among them are C, C++, Pascal, Delphi, Java, VB, C#, VB.NET, Excel. But let this list not be a limitation. Any programming language capable of calling external libraries (DLLs under Windows, Shared libraries (.so) under Unix/Linux) can call lp_solve.

Here is a list of some key features of lp_solve:

• Mixed Integer Linear Programming (MILP) solver
• Basically no limit on model size
• It is free and with sources
• Supports Integer variables, Semi-continuous variables and Special Ordered Sets
• Can read model from MPS, LP or user written format
• Models can be build in-memory without the use of files
• Has a powerful API interface
• Easy callable from other programming languages
• Advanced pricing using Devex and Steepest Edge for both primal and dual simplexes
• Provides different scaling methods to make the model more numerical stable
• Has presolve capabilities to tighten constraints/make the model smaller and faster to solve
• Has a base crashing routine to determine a starting point
• Allows restart after making changes to the model. Solve continues from the last found solution
• Possible to select desired combinations of primal and dual phases 1 and 2
• Possible to set several solver parameters like tolerances
• Alternative (and faster) inverse/re-factorisation libraries are provided for. See Basis Factorization Packages
• Alternative model readers and writers possible via the XLI implementation. See External Language Interfaces
• Has the possibility to convert one model format to another format
• Provides post-optimal sensitivity analysis. See Sensitivity
• …