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 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:

• Vía la API: La API es un conjunto de rutinas que pueden ser llamadas desde un lenguaje de programación para construir un modelo en memoria, resolverlo y devolver el resultado. Hay muchas rutinas en la API para realizar una muchas tareas y con muchas opciones. Véase lp_solve API reference para más información.

• Vía ficheros de entrada: lp_solve soporta muchos tipos de ficheros de entrada. El comúnmente conocido como formato MPS (véase mps-format) es soportado por la mayoría de los resolvedores, pero no es muy legible para las personas. Otrop formato es el formato lp (véase lp-format) que es más legible. lp_solve tiene la habilidad única de usar rutinas escritas por los usuarios para introducir el modelo (véase External Language Interface). Véase read_mps, read_freemps, read_MPS, read_freeMPS y read_lp, read_LP para llamar a la API para que lea un modelo desde un fichero de entrada. También existe un programa llamado lp_sove que usa la API para proporcionar un programa interprete de instrucciones para la resolución de modelos. Véase lp_solve para este uso. Con ese programa no necesitas saber nada acerca de la API o de lenguajes de programación. Simplemente puedes proporcionar tu modelo mediante un fichero al programa y él dará los resultados.

• Via un IDE: Gracias a Henri Gourvest, ahora hay un IDE denominado LPSolve IDE que usa la API para proporcionar una aplicación Windows para la resolución de modelos. Véase LPSolve IDE para este uso. Con este programa no necesitas saber nada acerca de la API o de lenguajes de programación. Simplemente puedes proporcionar tu modelo al programa y él dará los resultados.

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:

• Resolución de problemas de programación enteros mixtos (MILP)
• Básicamente tamaño no limitado del modelo
• Es libre y con fuentes
• Soporta variables enteras, variables semicontinuas y conjuntos ordenados especiales
• Puede leer modelos de MPS, LP o formatos escritos por el usuario
• Los modelos se pueden contruir en memoria sin el uso de ficheros
• Tiene una potente interface API
• Es fácilmente llamable desde otros lenguajes de programación
• Cálculo de precios avanzado usando Devex y paso por aristas para símplex primales y duales.
• Proporciona varios métodos de escalado para hacer el modelo más estable numéricamente.
• Tiene la capacidad de preproceso que simplifica las restricciones y hace el modelo más rápido y más fácil de resolver.
• Tiene una rutina basada en ruptura para la determinación de un punto de partida
• Permite reiniciar después de hacer cambios en el modelo. El programa continúa desde la última solución encontrada.
• Es posible seleccionar la combinación deseada de primal y dual en fases 1 y 2.
• Es posible establecer muchos parámetros como por ejemplo la tolerancia.
• Se dispone de librerías alternativas (más rápidas) de inversión/re-factorización. Véase Basis Factorization Packages
• Lectura y escritura de modelos alternativos vía implementaciones XLI. Véase External Language Interfaces
  • Tiene la posibilidad de convertir un modelo de un formato a otro
  • Proporciona análisis de post-optimalidad. Véase Sensitivity
  • …

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.

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.

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.

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.

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.

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.

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.

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.

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.