Search This Blog

Wednesday, June 06, 2012

Index




Introduction

What is lp_solve and what is it not? The simple answer is, lp_solve is a Mixed Integer Linear Programming (MILP) solver.
It is a free (see LGPL for the GNU lesser general public license) linear (integer) programming solver based on the revised simplex method and the Branch-and-bound method for the integers.
It contains full source, examples and manuals.
lp_solve solves pure linear, (mixed) integer/binary, semi-continuous and special ordered sets (SOS) models. Note the word linear. This means that equations must be of the first order. 5 * x - 3 * y is an example. However x * y is not linear and cannot be handled by lp_solve. Both the objective function and the constraints have this restriction. Also see Ratios.
Via the Branch-and-bound algorithm, it can handle integer variables (see integer variables), semi-continuous variables (see semi-continuous variables) and Special Ordered Sets (see Special Ordered Sets (SOS)).
lp_solve has no limit on model size and accepts standard both lp or mps input files, but even that can be extended. Note however that some models could give lp_solve a hard time and will even fail to solve. The larger the model the likely the chance for that. But even commercial solvers have problems with that.
It can also be called as a library from different languages like C, VB, .NET, Delphi, Excel, Java, ...
lp_solve is written in ANSI C and can be compiled on many different platforms like linux and WINDOWS.
lp_solve has its own community via the Yahoo group http://groups.yahoo.com/group/lp_solve/. There you can find the latest sources, executables for the common platforms, examples, manuals and a message board where people can share their thoughts on lp_solve.
lp_solve was originally developed by Michel Berkelaar at Eindhoven University of Technology. The work of Jeroen Dirks made the transition from the basic version 1.5 to the full version 2.0 possible. 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 compared to version 4 for the changes done in version 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 two ways to pass the data to the library:
  • Via the API
  • Via input files

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.
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
  • ...
Posted by at

No comments:

Post a Comment

Thank you

Subscribe to: Post Comments (Atom)