Tabla de Contenidos

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/.

Introducción a lp_solve 5.5.0.15

¿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 programa interface. lp_solve está escrito en ANSI C y puede ser compilado en en diferentes plataformas como linux y 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. Él contribuyó a los procedimientos de la interface, un lector MPS integrado, y corrigió muchos errores y he hizo mejoras en el código. En ese momento también había una versión en Java de lp_solve 2.0. Ésta no era una interface nativa Java (JNI) para la librería C, era una traducción del algoritmo (ver 2.0) de C a Java. También era muy limitada. Lo que significa que no se mantuvo junto a lp_solve en su desarrollo. Comenzando con la versión 3.0, lp_solve fue liberado bajo licencia LGPL. Antes el código sólo podía usarse con propósito no comercial. Muchas otras personas han contribuido a lp_solve, pero no hay registros sobre ellas. Disculpa si no eres mencionado. El desarrollo estuvo paralizado durante algún tiempo en la versión 3.2, pero ahora está activo otra vez y bien via los nuevos desarrolladores Kjell Eikland y Peter Notebaert. Pero otras personas también ayudan a mejorar el producto. Por ejemplo, la nueve interface Java para lp_solve ha sido hecha por Juergen Ebert. Es una interface JNI que soporta plenamente las funcionalidades de lp_solve. Él hizo un gran trabajo.. Nosotros animamos a otras personas a participar en el desarrollo de lp_solve. Primero se introdujo la versión 4 que tenía muchas mejoras y correcciones y ahora con la versión 5 las mejoras continúan obteniéndose mejores tiempos de resolución, más estabilidad y posibilitando la resolución de modelos mayores y nuevas funcionalidades. Véase Changes from version 4 to version 5.1 para los cambios hechos a la versión 5 y Changes from version 5.1 to version 5.5 para los cambios hechos en la versión 5.5.

Esencialmente, lp_solve es una librería, un conjunto de rutinas, llamadas la API que pueden ser llamadas desca casi cualquier lenguaje de programación para resolver problemas MILP. Hay muchas formas de pasar los datos a la librería:

Como se ha dicho previamente, lp_solve puede ser llamado desde muchos lenguajes de programación, entre otros Pascal, Delphi, Java, VB, C#, VB.NET, Excel, pero esta lista no es una limitación. Cualquier lenguaje de programación capaz de llamar a librerías externas (DLL bajo Windows, librerías compartidas (.so) bajo Unix/Linux) puede llamar a lp_solve.

Aquí hay una lista de algunas de las funcionalidades de lp_solve:

Inicio rápido

lp_solve (o lpsolve) tiene una multitud de prestaciones. Para los principiantes, puede ser difícil determinar por dónde empezar. La distribución contiene multitud de ficheros y para empezar sólo necesitas un par de ellos. Según vayas aprendiendo puedes necesitar más. Aquí se explica como empezar con lp_solve.

Formulando un problema

Si no sabes mucho acerca de programación lineal, mira primero Formulación de un problema en lpsolve. Empieza leyendo la primera parte donde se presentan ejemplos prácticos hasta llegar a formularlos como un modelo matemático, entonces vuelve aquí. Dichos ejemplos prácticos son usados en las siguientes presentaciones.

Otro artículo libre y muy útil acerca de los fundamentos de programación lineal y otras técnicas avanzadas, además de discusiones y modelado de problemas es Applications of optimization with Xpress-MP. El trabajo describe la programación lineal y el modelado on la aplicación comerical Xpress-MP., pero es útil para otras apliaciones como lp_solve. En caso de que el enlace no funcione, intenta buscarlo vía google.

Resolver un problema mediante IDE

La forma más sencilla de empezar con lp_solve es mediante un IDE. El IDE funciona sólo bajo Windows, aunque también puede usarse con el emulador wine. Véase LPSolve IDE.

Resolver un problema mediante la línea de instrucciones

Otra forma de resolver un modelo es mediante la línea de instrucciones del programa. Esto funciona en cualquier plataforma, pero todo se controla mediante instrucciones. Este entorno es bien conocido por los programadores de Unix/Linux y de consola DOS. Véase línea de instrucciones del programa.

Resolver un problema mediante la API

Los programadores quieren usar lp_solve de una manera totalmente distinta. Ellos quieren llamar a lp_solve como una librería directamente desde su lenguaje de programación. Esto es lo que se llama API (Application Programming Interface). Véase Llamando a la API de lpsolve desde tu lenguaje de programación y Construcción de un modelo para un lenguaje de programación. Un resumen de la API cpmpleta puede encontrarse en: Guía de la API de lp_solve.

Compile the source code yourself

The distribution contains precompiled libraries/binaries for Windows and Linux. However lp_solve can be compiled on other platforms also. You may also to make modifications to it and then you have to recompile also, even on the precompiled platforms. See Calling the lpsolve API from your application. In this article it is both explained how to link your code to the library and how to compile the lp_solve code.

Basis Factorization Packages

Alternative inverse/re-factorization libraries can be used by lp_solve. This is a feature for the more experienced users of lp_solve. See Basis Factorization Packages for more information. The sources of these packages are in the lp_solve_5.5.0.15_bfp_*_source.tar.gz archives. The binaries are in the lp_solve_5.5.0.15_exe* archive.

External Language Interfaces

Alternative model readers and writers possible via the XLI implementation. Models expressed in format files other than lp or MPS format can also be read or written by lp_solve via this unique feature. See External Language Interfaces for more information. The sources of these packages are in the lp_solve_5.5.0.15_xli_*_source.tar.gz archives. The binaries are in the lp_solve_5.5.0.15_exe* archive.

Calling lp_solve from higher level Mathematical languages

lp_solve can be called from AMPL, MATLAB, O-Matrix, Sysquake, Scilab, Octave, FreeMat, Euler, Python, Sage, PHP, R.

You now have a pretty good idea what lp_solve is about.