: The Simple LP Solver (V1.3.0a) : can solve large size linear programming problems in an efficient way. The size of the problem theoratically depends on the memory allocated to the program by the computer. Normally maximum of 2GB memory is allocated for a program. This limits the total array size to 128M; row count x column count (for the revised simplex methodology, constraint counts x constraints count while decision variables counts + >= constraints counts x constraints count for simplex methodology). Large inputs may take significant time (10s of minutes) even for loading the input from a file.

The program provides Simplex and Revised Simplex solvers for both Primal and Dual calculations. If the all constraints are <=, the Single Phase technique is applied while Two Phased technique is automatically used for others; “ = ” and “ >= ” constraints.

The problems with two decision variables can be solved by using Graphical Method.

The Solver checks coefficent of decision variables and constraints if they are all zero. A constraint with all coefficients are zero is eliminated. Any redundant constraints are eliminated. The Solver also check the negative RHS values and converts them to positive by multiplying by -1 and changing the equality sign. The Solver checks the degeneration. Sample Input files and more information on the Linear Programming and the Program are available at www.utilities.eu.pn/html/simple_lp_solver.html

The program is based on Microsoft Windows (TM) Rich Edit Controls with multiple document support. Therefore, the program supports many keyboard accelerators by default.

The program also has a simple text editor that supports plain text and richedit formats. When a blank document is created, document format is richedit by default. If it is saved as plain text, next time it is opened as plain text document. Richedit documents read from a drive are opened in richedit format regardless of the file extension. In example, if a richedit file has .txt extension, it is still opened as richedit file. Other formats are handled as plain text format.

The program also supports drag and drop feature. A file can be opened by dropping a document icon on the application icon.

This program is developed and distributed by Tanel as freeware for commercial and non-commercial use. The program is provided as it is with no guarantee in any manner. The use of the program is completely User's responsibility. The developer cannot be held responsible for the negative affects of the program.

Any improvement suggestions and bug reports can be e-mailed to Tanel; tanel.utilities@gmail.com. The suggestions and reports will be evaluated and may be incorporated in future releases.

For more information please visit www.utilities.eu.pn address.

This project was developed with Pelles C for Windows (C).


This program is developed and distributed by Tanel as freeware for commercial and non-commercial use. The program is provided as it is with no guarantee in any manner. The use of the program is completely User's responsibility. The developer cannot be held responsible for the negative affects of the program.

Support information is available at http://www.utilities.eu.pn/html/support.html. Any improvement suggestions and bug reports can be e-mailed to Tanel by http://www.utilities.eu.pn/html/contact.html or tanel.utilities@gmail.com. The suggestions and reports will be evaluated and may be incorporated in future releases.

Other versions (if any) can be downloaded from http://www.utilities.eu.pn/html/downloads.html

This project was developed with Pelles C for Windows (C).

Input Form / Table is based on the BABYGRID code copyrighted (C) 20002 by David Hillard and following message is included in the source code;

BABYGRID code copyrighted (C) 20002 by David Hillard

This code must retain this copyright message

Printed BABYGRID message reference and tutorial available.

email: mudcat@mis.net for more information.


Hardware and software requirements;

x86 CPU, 1GB RAM

Microsoft Windows XP SP2, Windows 7, Windows 8 or Windows 10 Operating System

Requires following dll files that are normally loaded as part of standard OS installation;

riched20.dll, kernel32.dll, gdi32.dll, comctl32.dll, advapi32.dll, Comdlg32.dll, User32.dll, Htmlhelp.dll


Toolbar and Status Bar: The program provides a toolbar and a status bar. The tool bar has basic fast access icons for some of frequently used functions that can be also accessed thru menu items. The menu items and tool bar buttons are enabled and disabled in accordance with current operation and status. File name is also displayed in the document window title bar (if it is maximized, in the main window's title bar) with full path name and document tab handle (file name only). Some of the Toolbar Icons are subject to licensing rules stated in Support & Licensing, and included in the program folder.

Bold-Underline-Italic-Superscript-Subscript icons have two behaviours;

· İf there is text selection, a button alters the attribute of the selected portion

· If there is no text selection, prssed button stays pressed mode and the related attribute is applied on to text to be typed. To turn off the attribute, a button needs to re-pressed.

The status bar is located at the bottom section of main application window. It provides file name with full path name, file type: Document/Input File/Input Form/Output File/Graphic, text mode; Rich Text/Plain Text, status of Caps Lock key, status of Insert / Over Write and status of edit mode, Editable/Read Only for the current document.


Simplex Solver

The simplex method for maximization problems is used. Therefore, minimization problems are converted to maximization problems. Following steps are followed;

· Check the goal function for zero coefficients for all variables.

· Check and fix the constraints for zero coefficients for all variables.

· Check and fix redundant constraints.

· Check and fix negative RHS values.

· Continue with Single Phase procedure if all constraints are <=, otherwise switch to Two Phase procedure.

· Single Phase Simplex procedure;

o    Add slack variables (s) to bring all constraints into equality ( =) form.

o    Create initial simplex table as shown below;

 |  | x1 | x2 | ... | e1 | e2 | ... | s1 | s2 | ...
Z | 0 |  |  |  |  |  |  |  |  |
Const.1 | RHS 1 |  |  |  |  |  |  |  |  |
Const.2 | RHS 2 |  |  |  |  |  |  |  |  |
Const.3 | RHS 3 |  |  |  |  |  |  |  |  |
... | ... |  |  |  |  |  |  |  |  |

o    Solve the problem in accordance with maximization problem criterias.

· Two Phase Simplex procedure;

o    Add slack variables (s), artificial variables (a) and excess variables (e) to bring all constraints into equality ( =) form.

o    Create initial two phase simplex table as shown below;

 | w | x1 | x2 | ... | e1 | e2 | ... | s1 | s2 | ... | a1 | a2 | ...
w | 0 |  |  |  |  |  |  |  |  |  |  |  |
Z | 1 |  |  |  |  |  |  |  |  |  |  |  |
Const.1 | RHS 1 |  |  |  |  |  |  |  |  |  |  |  |
Const.2 | RHS 2 |  |  |  |  |  |  |  |  |  |  |  |
Const.3 | RHS 3 |  |  |  |  |  |  |  |  |  |  |  |
... | ... |  |  |  |  |  |  |  |  |  |  |  |

o    Calculate the initial values for w row for Basic Feasible Solution (BFS). Z row is not needed for this stage but it is useful since original objective function will be in the appropriate form for the second phase.

o    Solve the problem in accordance with maximization problem criterias as Phase 1.

o    If the BFS is found at the end of Phase 1, eliminate w row and artificial variables from the table.

o    Continue to solve the problem in accordance with maximization problem criterias as Phase 2.


Revised Simplex Solver

The revised simplex method for minimization problems is used. Therefore, maximization problems are converted to minimization problems. Following steps are followed;

· Check the goal function for zero coefficients for all variables.

· Check and fix the constraints for zero coefficients for all variables.

· Check and fix redundant constraints.

· Check and fix negative RHS values.

· Continue with Single Phase procedure if all constraints are <=, otherwise switch to Two Phase procedure.

· Single Phase Simplex procedure;

o    Add slack variables (s) to bring all constraints into equality ( =) form.

o    Create initial revised simplex table as shown below;

 |  | x1 | x2 | x3 | ...
Z | 0 |  |  |  |
Const.1 | RHS 1 |  |  |  |
Const.2 | RHS 2 |  |  |  |
Const.3 | RHS 3 |  |  |  |
... | ... |  |  |  |

o    Create Basis Inverse (B-1 ) matrix with artificial variables as shown below (initially unity matrix);

 | z | s1 | s2 | s3 | ...
z | 1 |  |  |  |
s1 |  | 1 |  |  |
s2 |  |  | 1 |  |
s3 |  |  |  | 1 |
... |  |  |  |  | 1

o    Solve the problem in accordance with maximization problem criterias.

· Two Phase Revised Simplex procedure;

o    Add slack variables (s), artificial variables (a) and excess variables (e) to bring all constraints into equality ( =) form.

o    Create initial two phase revised simplex table as shown below;

 | w | x1 | x2 | x3 | ... | e1 | e2 | ...
w | 0 |  |  |  |  |  |  |
z | 1 |  |  |  |  |  |  |
Const.1 | RHS 1 |  |  |  |  |  |  |
Const.2 | RHS 2 |  |  |  |  |  |  |
Const.3 | RHS 3 |  |  |  |  |  |  |
... | ... |  |  |  |  |  |  |

o    Create Basis Inverse (B-1 ) matrix with artificial variables as shown below (initially unity matrix);

 | w | z | s1 | s2 | s3 | ... | a1 | a2 | a3 | ...
w | 1 |  |  |  |  |  |  |  |  |
z |  | 1 |  |  |  |  |  |  |  |
s1 |  |  | 1 |  |  |  |  |  |  |
s2 |  |  |  | 1 |  |  |  |  |  |
s3 |  |  |  |  | 1 |  |  |  |  |
... |  |  |  |  |  | 1 |  |  |  |
a1 |  |  |  |  |  |  | 1 |  |  |
a2 |  |  |  |  |  |  |  | 1 |  |
a3 |  |  |  |  |  |  |  |  | 1 |
... |  |  |  |  |  |  |  |  |  | 1

o    Calculate the initial values for w row for Basic Feasible Solution (BFS). Z row is not needed for this stage but it is useful since original objective function will be in the appropriate form for the second phase.

o    Solve the problem in accordance with maximization problem criterias as Phase 1.

o    If the BFS is found at the end of Phase 1, eliminate w row-column and artificial variables from the table.

o    Continue to solve the problem in accordance with maximization problem criterias as Phase 2.


Functions available in File menu:

Input Table: Asks count of decision variables and count of constraints, and creates an Input Form for problem entry.

In the Data Input Form; Maximum of 250 decision variables and maximum of 63.999 constraints can be entered. Higher values are automatically set to the limits. Please note that large inputs causes 10s of minutes processing time. Unsufficient memory may even cause program to crash. Normally maximum of 2GB memory is allocated for a program. This limits the total array size to 128M; row count x column count (for the revised simplex methodology, constraint counts x constraints count while decision variables counts + >= constraints counts x constraints count for simplex methodology). It is allowed to create large matrices but the size is checked before the calculation. If it is too big for the available memory, the Solver does not start.

Input From File: Loads a problem from a comma seperated text file. When it is loaded it will be displayed as follows and will be ready for Solver. Please note that large inputs causes 10s of minutes processing time. Unsufficient memory may even cause program to crash. Normally maximum of 2GB memory is allocated for a program. This limits the total array size to 128M; row count x column count (for the revised simplex methodology, constraint counts x constraints count while decision variables counts + >= constraints counts x constraints count for simplex methodology). It is allowed to create large matrices but the size is checked before the calculation. If it is too big for the available memory, the Solver does not start.

The format of the data is given in “Format of the data read from a file or write to a file” section.

Load Table from File: Loads a problem from a comma seperated text file to the Input Form. When it is loaded it will be displayed as follows and will be ready for Solver. Please note that large inputs causes 10s of minutes processing time. Unsufficient memory may even cause program to crash. Normally maximum of 2GB memory is allocated for a program. This limits the total array size to 128M; row count x column count (for the revised simplex methodology, constraint counts x constraints count while decision variables counts + >= constraints counts x constraints count for simplex methodology). It is allowed to create large matrices but the size is checked before the calculation. If it is too big for the available memory, the Solver does not start.

The format of the data is given in “Format of the data read from a file or write to a file” section.

Save Table to File: Writes a problem from an Input Form to a file as comma seperated text.

The format of the data is given in “Format of the data read from a file or write to a file” section.

Recent Input Files: Lists the last 10 of Input documents and opens the selected one

New: Creates a blank document in richedit format

Open: Opens a document from a drive

Save: Saves the current document with existing name into a drive. If there is no existing name, Save As dialog is automatically displayed

Save As: Saves the current document with a new name into a drive

Close: Closes the current document. If document was changed, it is prompted and confirmation is requested;

Print: Prints the current document (wysiwyg)

Recent Files: Lists the last 10 of documents and opens the selected one

Exit: Terminates the program. If document(s) was(were) changed, it is prompted and confirmation is requested


Functions available in Edit menu:

Redo: Repeats the last action (support multilevel redo)

Undo: Reverts the last action (support multilevel undo)

Cut: Cuts the selected text and saves into clipboard buffer (so it is available for other applications as well)

Copy: Copies the selected text and saves into clipboard buffer (so it is available for other applications as well)

Paste: Pastes the clipboard content to the location of cursor

Delete: Deletes the selected text

Select All: Selects the entire document

Find: Searches text in the current document in both direction. If a text is highlighted before the Find dialog is opened, it is automatically copied to Find dialog

Find&Replace: Searches text and replaces with new text in the current document in both direction. If a text is highlighted before the Find dialog is opened, it is automatically copied to Find dialog

Change Edit Mode: Switches between Read Only and Editable Mode. Documents with Input Form and Input File type are always Read Only.


Functions available in Format menu:

Fonts: Selects Font type, font style, font size, font effects, font color and font scripts. If a text is highlighted, changes are applied to highlighted text. If the document is saved as plain text, the selections are not saved with the document

Change Case: Changes the case of the highlighted text to upper cased or lower case.


Functions available in Solve menu: (Please note that large inputs causes 10s of minutes processing time. Unsufficient memory may even cause program to crash. Normally maximum of 2GB memory is allocated for a program. This limits the total array size to 128M; row count x column count (for the revised simplex methodology, constraint counts x constraints count while decision variables counts + >= constraints counts x constraints count for simplex methodology). It is allowed to create large matrices but the size is checked before the calculation. If it is too big for the available memory, the Solver does not start.

Simplex: Executes single phase or two phase simplex method to solve the Primal problem. It asks what will be displayed and if pre-checks will be performed as follows;

Revised Simplex: Executes single phase or two phase revised simplex method to solve the Primal problem. It asks what will be displayed and if pre-checks will be performed as follows;

Dual Simplex: Executes single phase or two phase simplex method to solve the Dual of problem. It asks what will be displayed and if pre-checks will be performed as follows;

Dual Revised Simplex: Executes single phase or two phase revised simplex method to solve the Dual of problem. It asks what will be displayed and if pre-checks will be performed as follows;

Graph: Executes graphical method to solve the Primal problem with two decision variables.

Customize: Legends for Goal Function for Basis and Artifical, Decision Variables, Artificial Variables, Slack Variables, Excess/Surplus Variables, CVS delimeter, number of iterations and Decision and Slack Variables for Dual can be changed. Automatic software Updata check at startup can be enabled or disabled. If “OK” button is pressed, new legends are used for the current session of Simple LP Solver. They need to be saved by pressing “Save” button if the values are required to be valid for the programs runs later. Defaults values; Z, W, x, s, a, e, ",", 1,000, y and d can be loaded back by pressing “Default” button. They also needs to saved.

If changed values are not saved or related configuration file corrupts, the program starts with defaults values.

Functions available in Solve menu_htm_m26cd0c4c.png


Functions available in Window menu:

Cascade: Displays document windows in cascade mode

Tile Horizontally: Tiles the document windows horizontally

Tile Vertically: Tiles the document windows vertically


Functions available in Help menu:

Help Subjects: Opens help file

About: Displays version information of the program

Check for Update: Checks if new version of the program is available

Visit Web Site: Opens www.utilities.eu.pn web site in the default browser


Right Click Context Menu:


Format of the data read from a file or write to a file (Default delimeter is comma but it can be changed thru Parameters window. New Line is considered as delimeter)

Count of decision variables,

count of constraints,

problem type (1 for maximization / -1 for minimization),

coeff for 1st decision variable,

coeff for 2nd decision variable,

...,

0,

0,

coeff for 1st variable of 1st constraint,

coeff for 2nd variable of 1st constraint,

...,

Equality Sign of 1st constraint

RHS of 1st constraint,

...

Equality Sign; 0 for = constraints, 1 for < and <= constraints, 2 for > and >= constraints

i.e;

4, 4, 1,

1, 1, 3, -0.5,0, 0,

1, 0, 2, 0, 1,740,

0, 2, 0, -7, 1, 0,

1, 1, 1, 1, 0, 9,

0, 1, -1, 2, 2, 0.5