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 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
• Vía ficheros de entrada
• Vía un entorno IDE

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.

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.

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
• …