LP_Solve Linear Programming Demo

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

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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:

bulletAmount of clay used cannot exceed 250 pounds: 0.75*Cups + Plates <=250
bulletAmount of time used cannot exceed 20 hours:    0.1*Cups+.05*Plates <= 20

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 

bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

Add additional LP_Solve options to assign other variable types (Integer, Semi-continuous, Special order), additional search options, etc. 

 

Original:  January 30, 2011

Modified:  July 29, 2017

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.