LP Assistant
This file last updated on December 8, 2007

2. LP Problems -- A Quick Start
1. Defining a Problem
2. Working a Problem
3. LP Problems -- Commands and Features
4. Workspace Level Operations

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:

1. 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;
2. 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.

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

## 2. LP Problems -- A Quick Start

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).
2.1 Defining an LP Problem

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 -4x1 + x2 + x3 + 7x4 + 3x5 = z
subject to
-6x1 + x3 - 2x4 + 2x5 = 6
-3x1 + x2 - x3 + 8x4 + x5 = 9
all xi nonnegative.

After expressing the problem in canonical form with x2 and x3 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

-6x1 + x3 - 2x4 + 2x5 = 6
-3x1 + x2 + 6x4 + 3x5 = 15
5x1 + 3x4 - 2x5 = -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 2x5 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 6x1 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 x1 = 1, x5 = 6, and x2 = x3 = x4 = 0.

## 3. LP Problems -- Commands and Features

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

1. Navigating and Typing in Edit Mode
3. Removing a Constraint
5. Removing a Regular Variable
7. Removing an Artificial Variable
8. Changing between the Simplex Algorithm and the Dual Simplex Algorithm
9. Changing the way values are displayed
10. Creating a new problem from an existing problem
11. Continuing a worked problem with added constraints
12. Undoing Pivot Operations
13. 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 x4. (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.)

## 4. Workspace Level Operations

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:

1. When the Save As dialog opens, it is focused on the user's home directory.
2. 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).
3. 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.
4. 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.
5. 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.
6. 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.
7. 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).
8. 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.