simplex

This solver allows one to enter a linear programming problem in English (or Spanish), then parses and solves it. To see it in action, open the demo file in a browser, and press the "Examples" button.

Using it in your own code

Using the solver involves four steps:

Create an lpProblem object and specify the LP problem to solve.
Set flags describing the kind of problem or the kind of output you want.
Call solve().
Retrieve the solution.

Creating an lpProblem

You create a new lpProblem object with

p = new lpProblem();

The constructor takes an optional argument, another lpProblem object to copy. If you don't copy an existing object, you'll next want to specify the LP problem to solve. This can be done in one of several ways:

Specify the LP problem as a string.

Set p.problemStr to a full LP problem, given as a string. The string must have the form

Maximize <linear objective> subject to
<linear constraints separated by commas or line breaks>

Maximize can be replaced by minimize and Spanish can be used as well. If you want to constrain one or more variables to have integer values, add the following at the end of the string:

integer <comma separated list of variables>

Specify linear expressions using juxtaposition for multiplication, so 2x + 3y, not 2*x+3*y. Use <= and >= to specify inequalities. The objective function may be specified as a linear expression or as an equation specifying the name of the objective function, like p = 2x + 3y. Constraints should have the form <linear expression> <= <number> where the inequality could also be >= or =. The number on the right hand side must be non-negative. Do not put commas in numbers.

Specify the LP problem by setting the objective and constraint properties.

Set p.objective to a string representing the objective function, in the form [max|min]imize [var =] <linear expression>.
Set p.constraints to an array of strings representing the constraints.
If you are solving an integer or mixed problem, set p.isIntegral to true and set p.integerUnknowns to an array of unknown names that should be constrained to be integers.

Setting flags

p.mode can be set to
- lp_Integral for all tableaus to have integer entries and solutions to be given as fractions
- lp_Fraction for all tableaus to have fractional entries and solutions to be given as fractions
- lp_Decimal for tableaus and solutions to be given using decimal notation.
p.showArtificialVariables defaults to false, in which case the slack and surplus variables are not shown as part of solutions. If set to true, these variables are reported in solutions.
p.sigDigits is the number of significant digits to show in decimal mode in tableau entries and solutions. It defaults to 6.
lp_verboseLevel is a global variable controlling what is saved in the global string lp_trace_string while the problem is being solved. The default is to save nothing. If lp_verboseLevel = lp_verbosity_tableaus, all intermediate tableaus are saved. If lp_verboseLevel = lp_verbosity_solutions then all tableaus and the corresponding basic solutions are saved. The string saved is HTML, suitable to insert in a <div>, for example, to display on a web page.
lp_reportErrorsTo is a global string controlling how errors are reported. If empty (the default), errors are not reported. If set to "alert", errors cause alerts to be posted. If set to the ID of an HTML element, errors are inserted in that HTML element on the page.

Calling `solve()`

Once the problem is set up and flags properly set, call p.solve(), which takes no arguments. If something is wrong with the way the problem was stated, it may throw an error, which will be a string describing the problem. This string will also be available as p.error.

Retrieving the solution

After calling p.solve(), check p.status, which will be either lp_optimal if an optimal solution was found, or lp_no_solution if there was no solution. In the latter case, the property p.message contains a string indicating why no solution was found.

Assuming a solution was found, p.tableaus will be an array of all the tableaus generated by the simplex method (see Tableaus below for more information about these tableaus and methods to display them nicely) and p.solutions will be an array of solutions, each being an array of values for the variables. The property p.unknowns is an array giving the names of the unknowns in the order in which the values appear in the solutions.

To get the solutions as nicely formatted strings, call one of the following:

p.solutionToString() returns a string showing the solution of the problem, using the settings of p.showArtificialVariables and p.mode.
p.lastSolutionToString() is used internally to return the basic solution from the last tableau, which will not necessarily be the solution to the problem if doing integer or mixed programming.
p.formatUnknowns ( includeArtificalVariables ) returns an array with the names of the unknowns in the order used in the following functions. The optional argument tells whether to include the slack and surplus variables (default: false).
p.formatLastSolution ( includeArtificalVariables, mode ) returns the solution of the problem as an array of strings giving the values of the variables in the order specified in p.unknowns. The optional arguments tell whether to include the artificial variables (default: false) and the mode of solution to show (default: value of p.mode).
p.formatIntegerSolution ( includeArtificalVariables, mode ) is the corresponding routine you should use if doing integer or mixed programming.
p.formatLastObjectiveValue ( mode ) returns a string representing the optimal value of the objective function (for non-integer/mixed programming). The mode is optional, defaulting to p.mode.
p.formatIntegerObjectiveValue ( mode ) is the corresponding routine to use when doing integer or mixed programming.
p.formatSolutions ( includeArtificalVariables, mode ) is similar to formatLastSolution, but returns an array of basic solutions, one for each tableau generated by the simplex method.
p.formatObjectiveValues ( mode ) is similar to formatLastObjectiveValue but returns an array of all the values of the objective function for all of the tableaus.

Tableaus

The tableau class extends Array; tableaus are always two-dimensional arrays. The 0th row contains the variable names corresponding to each column and the 0th column contains the currently active variables corresponding to each row. The actual tableau starts with index [1][1], so the matrix itself uses 1-based indexing.

There are three methods added to the Array class:

pivot ( row, col, sigDigs ) pivots on the entry in [row][col] and returns a new tableau. sigDigs is used to mitigate subtractive error and should usually be set to something large, like 13.
toString ( mode, sigDigs ) returns an ASCII formatted string representing the tableau. It contains no HTML tags and is suitable for showing in <pre> tags (but such tags are not part of the string). mode is one of lp_Integral, lp_Fraction, or lp_Decimal, and sigDigs is used for rounding the entries, so might be something like 6.
toHTML ( mode, sigDigs, params ) returns a string of HTML code representing the tableau as a <table>. mode and sigDigs are as for toString. params is an optional argument: If it has a cellPadding property, that is used to set the padding in the <table> (default: 10); if it has a lineColor property, that is used to set the color of the lines separating the first and last rows and columns from the rest of the tableau (default: "black").

drlippman/simplex