[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math Topics]   [Library]   [Utilities]

Problem Description

LP_Solve is a Mixed Integer Program solver which is callable from many languages.  Here's a Delphi  program which solves several sample LP problems and allows others to be entered and solved. 

Background & Techniques

This program provides  a Delphi user friendly interface to LP-Solve, a free linear programming tool available from
http://lpsolve.sourceforge.net/ and/or http://tech.groups.yahoo.com/group/lp_solve/.  The Yahoo site requires group membership to access files but the site has more of the files needed than does the SourceForge site which seems only to include an executable version of the solver.. I have downloaded and included all of the necessary files for this demo in the downloads below.   For programmers, the documentation for using LP-Solve features is available at  http://lpsolve.sourceforge.net/5.1/. 

Linear programming is a technique for solving a large class of optimization problems which can be described by a set of linear equations.  For example, 

A potter is making cups and plates. It takes her 6 minutes to make a cup and 3 minutes to make a plate. Each cup uses 3/4 lb. of clay and each plate uses one lb. of clay. She has 20 hours available for making the cups and plates and has 250 lbs. of clay on hand. She makes a profit of $2 on each cup and $1.50 on each plate. How many cups and how many plates should she make in order to maximize her profit?

Let variable names "Cups" and "Plates" signify then number of cups and plates produced. The problem is to maximize the profit, 1.5*Cups + 2*Plates, with the constraints:

To solve this problem with LP_Solve, we just need to pass it the variable coefficients for the profit equation and coefficients and the limit for each of the constraints.  The table has a column for each variable and a row for the "objective function" followed by a row for each constraint.  The LPDemo version looks like this:

LPDemo takes this table, passes the information to LP_Solve, and produces the following output from the LP_Solve results.

Solved
Optimum variable values are:
Cups = 120.000
Plates = 160.000

Profit
2.000 * Cups + 1.500 * Plates = ???
2.000 * 120.000 + 1.500 * 160.000 = 480.000

Constraints
Clay used
0.750 * Cups + 1.000 * Plates <= 250.000
0.750 * 120.000 + 1.000 * 160.000 = 250.000
Time used
0.100 * Cups + 0.050 * Plates <= 20.000
0.100 * 120.000 + 0.050 * 160.000 = 20.000
 

I used version 5.1 of the solver because the latest version (5.5) doesn't seem to have all the files available, specifically LPSolve51.pas a Delphi interface to the API functions available in LPSolve51.dll.  Both files are included in the source distribution below.  LPSolve51.dll is dynamically linked at execution time and is also included in the executable download.    

The "Cases" page displays the initial sample program. The word description of the problem occupies the top portion of the page.  The table describing the variables, the problem objective and the constraints appears at the bottom of the page. The "Solve" button transfers the
information form the table to the record format required by LP_Solve and calls its "Solve" function to attempt a solution. Results appear below the problem description in that display.

The "Load" button will load text and detailed information for several sample cases included. The "Save" button saves the text and problem detail to a file. If you want to modify the sample problems or define your own, here are some details:

Only the basic options available in LP_Solve are implemented here. You can specify the number of variables and the number of constraints to change the size of the table. You can also specify whether to look for the maximum or minimum for the objective function.
The objection function is the expression describing the quantity to be optimized. The top row of the table is reserved for names of the variables. The row below that defines the objective. Each following row defines a constraint. The first column is reserved for names of
the constraints. Columns to the right define coefficients for each of the variables in the objective function and each of the constraint equations. The next to last column contains the relation of the constraint to the constant contained in the rightmost column. Allowed relation operators are ">=", "<=", or "=". For the objective row, the final 2 columns should remain as "= ???".
 

Addendum Feb 1, 2011:  A small change to the LoadString (in Loadcase) and SaveString (in SaveCase) procedures today makes the program compliable with both Delphi 7 and Delphi XE  (Actually Delphi versions prior to Delphi 2009 and Delphi 2009 and later versions.  Earlier versions generate "AnsiString" types by default using one byte per character, later versions create "Uniocde" strings by default which use 2 bytes per character.  LPDemo uses TFileStream controls to save and reload cases.  Streaming methods are not very smart about data types, they just  require a count of the number of bytes to write and the starting address to save from or load into.  You can see the problem if cases saved with ANSI strings are read back later as Unicode strings.   All of the sample cases included with LPDemo were created with ANSIStrings so the change today forces strings to be written and read as ANSI strings regardless of the Delphi version.  The ANSI strings are converted to or from the default string format regardless of whether the default string type is the long or short version.   LPDemo was reposted as Version 2.1.    

Running/Exploring the Program 

Suggestions for Further Explorations

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2013, Gary Darby    All rights reserved.