*LP Assistant
This file last updated on December 8, 2007*

*Table of Contents*:

- About
*LP Assistant* - LP Problems -- A Quick Start
- Defining a Problem
- Working a Problem

- LP Problems -- Commands and Features
- Workspace Level Operations
- Closing Comments

*LP Assistant* is free (but copyrighted) software that enables students
in a linear programming course to easily set up a simplex tableau representing
a linear programming problem in canonical form, and then to execute a sequence
of pivot operations to drive towards a solution. The notation used by *LP
Assistant* is that of *An Introduction to Linear Programming and Game
Theory, Third Edition*, by Paul R. Thie and G. E. Keough, to be published
in 2008 by John Wiley and Sons, Inc. The design and implementation of *LP
Assistant* is by G. E. Keough.

When defining a problem and setting up a simplex tableau, *LP Assistant*
allows for the addition (and removal) of both constraints and variables as necessary
to fit the problem. While the user is responsible for properly defining slack
variables and identifying basic variables, *LP Assistant* will manage
artificial variables and the arithmetic associated with the auxiliary *w*-function
which helps drive the problem into canonical form with original basic variables.

Once the user has completed the construction phase of the simplex tableau for
a problem, a computational mode is entered during which the user indicates a
pivot term by clicking with the mouse and *LP Assistant* executes the
arithmetic of the pivot operation about that term. Because the proper selection
of pivots in the simplex algorithm requires knowledge of certain ratios, *LP
Assistant* displays ratios in real time as the user moves the mouse over
a tableau looking for the correct pivot term.

*LP Assistant* also allows the user to begin a new problem from a current
tableau at any time. This feature has two intended uses:

- once a problem with artificial variables has driven the
*w*-function to its trivial state, the user can continue the problem in a new window, without the clutter of the*w*-function and the artificial variables; - if the user wishes to add new constraints after several steps in the algorithm (e.g., to implement branch-and-bound or Gomory plane-cutting), it's quite appropriate to start new problems with the additional constraint(s).

*LP Assistant* is written entirely in Java and distributed as a single
Java Archive file to support its use on multiple platforms. The software has
a reasonable amount of sophistication in its implementation, with no fixed bounds
on the number of constraints or variables used in a given problem. However,
it does not pretend to offer industrial strength capabilities or to be an LP
solver (for which there are already many excellent products available, both
commercially and in the public domain). Indeed, *LP Assistant* manages
only a user interface and the arithmetic of the pivot operation -- it contains
no code to fully implement the simplex algorithm or even to monitor the progress
of a user when working out an LP problem.

Further implementation comments appear in the Closing Comments section below.

The source code of *LP Assistant* is available upon request from G.
E. Keough at the address keough@bc.edu.

When *LP Assistant* opens, a Workspace Window is opened, and a new tableau
for a problem having 2 constraints and 3 variables is opened within the Workspace
in its own window named "Untitled Problem 1".

Notice that some button groups appear at the left side of the window:

- the current Mode will be set to Edit (which allows you to change entries in the tableau);
- the Algorithm is set to Simplex (this controls the display of ratios as described below; the Dual Simplex algorithm is described in Chapter 4 of the text); and
- the Display will be set for Exact (which displays fractions exactly, rather than rounded numerically).

We wish to solve a new linear programming problem, and we will illustrate using the process described at the start of Section 3.5 in the text, based on the following problem of Section 3.3:

Minimize -4

x_{1}+x_{2}+x_{3}+ 7x_{4}+ 3x_{5}= z

subject to

-6x_{1}+x_{3}- 2x_{4}+ 2x_{5}= 6

-3x_{1}+x_{2}-x_{3}+ 8x_{4}+x_{5}= 9

allx_{i}nonnegative.

After expressing the problem in canonical form with *x*_{2}
and *x*_{3} serving as basic variables (note: *LP Assistant*
does not check the form of problems -- the user must present the problem in
canonical form), we will minimize *z* with

-6

x_{1}+x_{3}- 2x_{4}+ 2x_{5}= 6

-3x_{1}+x_{2}+ 6x_{4}+ 3x_{5}= 15

5x_{1}+ 3x_{4}- 2x_{5}= -21 +z

This problem has two constraints and five variables, so first we must enlarge
the new tableau (in the window entitled "Untitled Problem 1") to accommodate
two extra variables. From the Tableau menu in the "Untitled Problem 1"
window, twice select *Tableau -> Add Regular Variable* (or use the
accelerator key combination Command+B).

Now enter the numerical values into the tableau. You do so by clicking in any location in the tableau and typing. You can use the Tab key to move around through the tableau entries, although you cannot type in the first column where the "X" notations are displayed. The completed tableau looks like this.

Next, set the basic variable labels. You do this by clicking on the "X" in the first row and a popup menu will appear as shown below, from which you may choose the variable to be basic for this constraint (here, you should choose X3). Similarly, set the basic variable for the second row to be X2.

After all numeric entries are entered and the two basic variables labeled, click the button marked "Pivot" at the left side of the window. (You'll notice a slight change in the tableau presentation in this mode -- you'll understand why shortly). You are now ready to begin working on the problem.

**2.2 Working an LP Problem **

The problem window is now defined as shown above, and all that remains now
is to execute a sequence of pivots to find a solution to the problem. But with
*LP Assistant* in Pivot mode, this is literally as easy as moving and
clicking the mouse.

To execute a pivot, simply click on the pivot term. As shown in Table 3.2 in
the text, the proper sequence of pivots for this example begins at the 2*x*_{5}*
*term in the first constraint. Clicking at that term, the term is circled,
the pivot executed, and the resulting tableau appended to the display. Clicking
at the 6*x*_{1} term in the second constraint of the resulting
tableau executes a second pivot operation, with a third (and final) tableau
appended, as shown below. (Notice, by the way, that fractions are properly drawn
in this third tableau; this is the reason the graphic presentation changes slightly
when moving from Edit mode to Pivot mode.)

Here, we knew the sequence of pivots in advance, but the simplex algorithm directs the user to select a pivot term from a column in which there is a negative objective function coefficient (the bottom row), and further based on minimizing the ratio of basic variable value to constraint coefficient in such a column.

*LP Assistant* helps you make the proper choice by showing you the appropriate
ratio in real time as you move the mouse over a tableau. The numerical ratio
appears on the left pane just under the label Ratio. For example, if you position
the mouse over the 7/2 entry in the first row of the last tableau, you'll see
the ratio displayed as 1.714, which is the ratio 6 to 7/2.

Ratios are shown during Pivot Mode only in cells in the last tableau for which
a pivot operation would make *numerical* sense -- i.e., you cannot pivot
on a "1" if all other entries above and below in the constraint columns
are "0" (a variable is already in the basis), and you cannot pivot
on a "0" entry. However, *LP Assistant* does not prohibit you
from selecting a pivot term that does not make *logical* sense for applying
the simplex algorithm -- the user assumes full responsibility for selecting
the pivot terms.

How do you know when a solution has (or has not) been found? It's important
to understand that *LP Assistant* makes no indication of what conclusion
should be drawn at any time. The user bears the responsibility of interpreting
the tableaux generated. In the example in question, the third tableau has all
nonnegative coefficients along the bottom row, so the user must recognize that
a problem solution has been found and no further pivots need be executed. The
minimum value of the function is *z* = 14 at *x*_{1} =
1, *x*_{5} = 6, and *x*_{2} = *x*_{3}
= *x*_{4} = 0.

While setting up the initial tableau for a problem in *LP Assistant*,
there are other actions that may need to be taken than seen in the example above.
These include

- Navigating and Typing in Edit Mode
- Adding a Constraint
- Removing a Constraint
- Adding a Regular Variable
- Removing a Regular Variable
- Adding an Artificial Variable
- Removing an Artificial Variable
- Changing between the Simplex Algorithm and the Dual Simplex Algorithm
- Changing the way values are displayed
- Creating a new problem from an existing problem
- Continuing a worked problem with added constraints
- Undoing Pivot Operations
- Changing the Font and Size

We'll address each of these in sequence. **Note**: Action
1 is (clearly) only available in Edit Mode. Actions 2 through 7 are available
only for a problem having one tableau. Once the user has entered Pivot Mode
and executed at least one pivot operation, the Add and Remove operations are
no longer available.

**Navgating and Typing in Edit Mode** generally respects most
keystroke operations associated with spreadsheets. Click on a cell and strat
typing to enter a value. Use the Tab key, Arrow keys, Return key and so forth
to move from cell to cell via keyboard direction.

All coefficients entered in a problem must be *rational*. You can type
coefficients in decimal form (e.g., type 2.3 for the fraction 23/10) or as quotients
of integers (i.e., just type the five characters "23/10," with the
slash character denoting division). As long as you type only digits, the period,
the minus sign, and the division sign in a menaingful sequence, *LP Assistant*
will likely correctly parse your input. Whenever an input sequence of characters
cannot be correctly parsed, *LP Assistant* will replace your input with
a zero.

Once coefficients are entered, all pivot arithmetic will be done exactly, without
numerical roundoff. Thus, * always enter exact rational numbers when
you know them*. For example, enter the coefficient 1/3 simply by
typing "1/3" -- entering any of its likely approximations such as
"0.3" or "0.33" or "0.333" will only reduce the
accuracy of future calculations.

On the other hand, coefficients which cannot be expressed in rational form
* must* be entered using a numerical approximation.
However, in virtually every practical application of linear programming, this
will not be an issue.

To **Add a Constraint** to a problem, select *Tableau ->
Add Constraint* (or, use the accelerator key combination Command+= [Command
key plus the Equals key], or click in the Basis column of the tableau in the
row with the objective function coefficients and select *Add Constraint*
from the popup menu that appears. New constraints are always added as the last
constraint.

To **Remove a Constraint**, either select *Tableau -> Remove
Constraint -> From Row N*, where N is the row in which the constraint
appears; or, click in the Basis column and select *Remove This Constraint*
from the popup menu.

To **Add a Regular Variable**, select *Tableau -> Add Regular
Variable* (or, use the accelerator key combination Command+B). New Variables
are always added with the next available (highest) index for regular variables;
if there are currently three regular variables in the problem, the new variable
will be *x*_{4}. (If there are artificial variables in the problem,
they are renumbered appropriately.)

To **Remove a Regular Variable**, select *Tableau -> Remove
Variable -> Variable N*, where N is the index of the regular variable
to be removed. (All variables in the problem with higher indices will be renumbered
appropriately.)

To **Add an Artificial Variable**, click in the Basis column of
the row (constraint) in which the artificial variable is to be added, and select
Add Artificial Variable from the popup menu that appears. Artificial variables
are always inserted having the highest variable index.

The first time you add an artificial variable to a tableau, you'll see the
tableau properly enlarged not only with an extra column, but also with an extra
row below the objective function coefficients. This last row contains, of course,
the coefficients of the auxiliary *w*-function that helps drive the system
into canonical form having no artificial variables in the basis. All columns
associated with artificial variables, as well as the *w*-row, will be
shaded with a light gold to remind the user of the special, auxiliary nature
of these entries (and, in particular, that they are not editable).

As long as artificial variables are present in the tableau and the tableau
is in Pivot Mode, *LP Assistant* will automatically maintain the coefficients
in the *w*-row according to the scheme by which the *w*-row is
constructed. (Coefficients in the *w*-row may not always be updated as
changes are made in Edit Mode, but all are validated when entering Pivot Mode.)

To **Remove an Artificial Variable**, click in the Basis column
of the row (constraint) in which the artificial variable is to be removed, and
select *Remove Artificial Variable* from the popup menu that appears.
If this is the last artificial variable removed, the auxiliary *w*-row
in the tableau will be removed as well.

To **Change from the Simplex Algorithm to the the Dual Simplex Algorithm**
and vice versa, click the appropriate radio button for Algorithm. The tableau
will be relabeled in X or Y format according to the algorithm in use. The change
is more than cosmetic -- this setting controls the **Display of Ratios**.

When using the Simplex Algorithm, the ratio displayed is computed from the
*constant* coefficient and the constraint coefficient. When using the
Dual Simplex Algorithm, the ratio displayed is computed from the *objective*
function coefficient and the constraint coefficient.

If the *w*-row is present when using the Dual Simplex Algorithm, the
ratio is computed using the *w*-row only if the row has not yet reached
the trivial state of zeroes (for the regular variables), ones (for the artificial
variables), and 0 (for the *w*-value). Otherwise, the ratio is computed
using the objective function coefficient.

To **Change the Way Values are Displayed**, select one of the
Display buttons labeled "1/2," "1.0," "1.00,"
or "1.000." These show values exactly as fractions, or rounded to
one, two, or three decimal places, respectively. Note that these buttons control
display only; values are maintained internally at all times in exact format.

To **Create a new problem from an existing problem**, select *Problem
-> New from (Name)* in the Workspace Window menubar, where (Name) is
the name of the currently active problem window. The last tableau of the current
problem becomes the first tableau in a new problem window.

Note that if a *w*-row is present in the last tableau of the current
tableau, it is removed (as are all artificial variables) for the tableau in
the new window. In theory, if a *w*-row is present in a problem, its
purpose is to drive the problem to a more amenable form in which the artificial
variables are no longer necessary. Thus one of the uses of this operation is
to move from a current tableau in which the *w*-function has been driven
to zero, to a new tableau in which the problem can now be continued with an
identified basis consisting only of the original variables of the problem.

To **Continue a worked problem with added constraints**, select
*Problem -> New from (Name)* from the menubar in the Workspace Window
as described above, where (Name) is the name of the currently active problem
window in which you're working. Switching to Edit Mode then allows you to modify
the continued problem. This procedure is especially useful for integer programming
problems where the Gomory Plane Cutting algorithm or Branch and Bound techniques
can be applied.

To **Undo a Pivot Operation**, select *Tableau -> Remove
Last Tableau*. The first tableau can never be removed, of course.

Finally, to **Change the Font and Size** of characters appearing
in a tableau, select *Useful Aids -> Font and Size Selection* from
the Workspace Window menu. A selection window will appear at the lower, left
of the Workspace Window as seen in

Choose Font and Size as desired fom the pulldown menus, then click Apply. If
there are Problem Windows open, the change will be made to the top-most window.
If there are no Problem Windows open, then clicking Apply will set this as the
default font and size for all windows opened after this time. (However, your
preference is not saved between runs of *LP Assistant*, nor is it written
with any saved files.)

In addition to several operations discussed above that are specific to an LP problem, the Workspace Window's Problem menu has items to allow creating a New Problem, Saving a current problem to disk (using either Save or Save As), Opening a previously-saved problem, and Printing a problem. These items will generally work as users expect and all except Quit have accelerator key equivalents.

The following comments further describe certain aspects related to these operations
in *LP Assistant*:

- When the Save As dialog opens, it is focused on the user's home directory.
- The file format for
*LP Assistant*is straight text, with the resulting file editable (if it's sensible to do so) using any text editor. We recommend that files be saved with extension**".txt**" so that*LP Assistant*can find them easily (the Open dialog initially filters its list of selections for files having the**.txt**extension, but is capable of allowing selection of any file on disk). - The printing code (currently) uses the measurements in a problem's window to lay out pages and assumes that all tableaux fit left-to-right on a single page (multiple tableaux will be printed on consecutive pages, of course). The default width of a tableau window will print in a width of approximately 6.25 inches, which together with user-entered margins (that default to 1 inch both left and right), allows tableaux to fit properly. For wider tableaux, consider narrowing the window horizontally, using smaller margins, and printing in landscape mode.
- One important aspect regarding printing is that the problem will automatically be placed into Pivot Mode before printing is executed. This guarantees both the nicer tableau format and that any open edits have been committed.
- Closing any problem window will trigger a "Do you want to save..." dialog if there have been changes to the problem since it was last saved (or if it was never saved). Similarly, closing the Workspace Window or selecting Quit from the Problem menu will trigger a "Do you want to save..." dialog for each open problem window in the Workspace Window.
- However, quitting
*LP Assistant*by directly quitting the shell in which the Java VM is running**will not**trigger appropriate "Save" dialogs. In particular, on a Mac, typing Command + Q exits the Java VM, bypassing*LP Assistant*'s normal quitting sequence. Our recommendation: always quit*LP Assistant*either by closing the Workspace Window or by choosing*Quit*from the Problem menu. - Cut, Copy, Paste, and Undo issues have not been directly addressed at this stage of development, although they are supported via the usual keystroke commands (X, C, V, Z) when entering data values in Edit Mode (only because the underlying Java JTable implementation supports these).
- On the whole, most operations in
*LP Assistant*have complementary operations that are effectively undo operations ... and since the amount of typing in minimal (only number entry is permitted), it is unlikely that a direct Undo command will be supported. Eventually,*LP Assistant*may include special copy and/or paste commands to allow full tableau displays to be moved between*LP Assistant*and Word, Excel, or even TeX.

*LP Assistant* represents a new development cycle for *PRT Simplex*,
a program originally developed for the Macintosh in Pascal, and more recently
in Metrowerks C++ with a robust interface supplied by the PowerPlant application
framework. The major design goal in developing *LP Assistant* has been
to move educational technology developed in *PRT Simplex* that has been
used so successfully for many years in the classroom into a more widely available,
platform-independent application.

Thus, the code for *LP Assistant* is 100% Java, using Java2 Platform
Standard Edition v1.4.2, together with elements of AWT and Swing. *LP Assistant*
uses the Java class BigRational for its internal numerics, in which all values
are maintained as the ratio of two Java BigIntegers (which are "arbitrary-precision
integers"), hence the program maintains all arithmetic operations in exact
form without overflow issues.

The code for *LP Assistant* can be made available upon request for educational
purposes, to users of our forthcoming *An Introduction to Linear Programming
and Game Theory, Third Edition*, and to improve the design and quality of
the product. *LP Assistant* will remain free, although copyrighted software;
we have our lawyers working out the exact licensing issues (!).

Finally, *LP Assistant* is a work in progress and your feedback is valued.
Please feel free to write!