Presentation of G2DS

A linear program is defined by a set of linear constraints and a linear objective function. Here, we are only interested in linear programs having 2 variables, x and y, which means that any constraint can be written as "ax + by op c" (op being "≥", "=" or "≤") and that the objective function can be written as "min/max (dx + ey)".

To summarize, solving a linear program consists in optimizing a linear function over a convex set (polyhedron) which, in 2 dimensions, is a polygon (possibly empty or unbounded). In the following, this polygon will be refered to as the feasible polygon or constraints polygon. The "edges" of the polygon are called facets. A point belonging to two adjacent facets is called a basic point. Let z* be the optimal value of a linear program, and let its objective function be [opt] dx + ey: then, the line dx + ey = z* is called the optimal line.

If we also require that the variables x and y only take integer values, then the obtained problem is called an integer linear program.

Adding an objective function is almost the same as adding a new constraint. The 2 text fields of the 1^st line respectively contain the coefficient of x and the coefficient of y in the objective function (and the 3 remarks of the previous section concerning the input procedure also apply). Then, select "min" (for minimization), "max" (for maximization) or "none" (for adding no objective function), and press the "Set" button. The linear program will be solved automatically. Note that, each time you define a new objective function (by pressing "Set"), the old one is lost.

The status area is located between the three upper lines of the applet and the area where the graphical representation of the problem is displayed. This status area, displayed in red, is used by the applet to inform you of the current status of the linear program (number of feasible basic solutions, optimal value, information about integer solutions, etc.). Each time you launch the applet, you can of course add as many constraints as you like (the only limit being the processing time!) and redefine the objective function as many times as you want. Each time a constraint is added or removed, the status area and the constraints polygon are automatically updated (the facets of the latter are the black lines). In the same way, when the objective function is defined/redefined, the optimal line is displayed on screen and the status is updated, except when the linear program has no optimal solution (in such a case, the information will be displayed in the status area anyway).

In order to draw the feasible polygon correctly, the applet automatically computes the most suitable zoom factor. You can be informed of the scaling factor used by the applet through the 2 values "Xmax" and "Ymax". There are 10 points on both the x axis and the y axis, the distance between two consecutive points being constant. The 10^th point on the x axis corresponds to the point with x=Xmax and the 10^th on the y axis to the one with y=Ymax. The respective x coordinates of the other points on the x axis are then Xmax/10, 2*Xmax/10, etc.

This section details the additional functions provided by this applet which are not absolutely necessary for a basic use. First, we describe the functions associated with buttons:

• The "Recall" and "Clear" buttons (1^st line) are respectively used for displaying the coefficients of the current objective function (ie, the last one you submitted by pressing "Set") and for clearing the 2 text fields of this line. Moreover, they can also be used for showing and hiding, respectively, the optimal line on the display area.



• The "Edit" button (2^nd line) is used for editing, in the 3 text fields of the 3^rd line, the constraint selected in the list of constraints (2^nd line).



• The "Reduce" button (3^rd line) is used for indicating the applet that (some of) your inputs are ratios of integers and that you expect not to loose any precision. If you press this button, the applet will transform your constraint into an equivalent one with integer coefficients. This new constraint cannot be reduced any further (it does not exist any equivalent constraint with smaller integer coefficients). You can then add this constraint as if you wrote the coefficients yourself, by pressing "Add". If your inputs are ratio of real (and not integral) numbers, the "Reduce" button will have no effect. For example, "3/2 x + 1 y ≥ 4/5" will be transformed into "15 x + 10 y ≥ 8", but "3.5/2 x + 1y ≥ 4/5" is incorrect (as far as the "Reduce" button is concerned!).

• You can modify the colors used in the applet by double-clicking on certain zones. There are 5 colors that you can modify: the background color (1), the color of the feasible polygon (2), the color of the selected facets and points (see below, (3)), the color of the optimal line and points (4) and the color of the new constraints (5). To modify the color (1), just double-click on any empty zone of the applet. To modify the color (2), double-click anywhere inside the feasible polygon. To modify the color (3), double-click on a facet (be careful, you have to be precise!) or on the text "Such that:". To modify the color (4), double-click on the optimal line (precision is needed!) or on the text "Objective function:". Eventually, to modify the color (5), double-click on the text "New constraint:".



• If the mouse cursor is on the x axis, the x coordinate of the corresponding point will be displayed on screen ("x = ..."), its y coordinate being equal to 0. You can proceed the same way on the y axis.



• If you click (with a simple click) on a facet (you will need precision), you will select it. Its color becomes the color (3), except if this is "x = 0" or "y = 0", and the corresponding constraint is selected in the list of constraints (2^nd line). On the other hand, you can also select a constraint in the list of constraints, and the corresponding facet (if any!!!) will be selected and its color will be the color (3), except if this is "x = 0" or "y = 0".



• If you click (with a simple click) on a basic point (you will need precision), you will select it. Its color becomes the color (3) and its coordinates are displayed, near it, on the screen.



• If you click (with a simple click) on the text "New constraint:", it takes the color (5), which means that you can now add a constraint graphically. Then, click anywhere outside the feasible polygon once, it will become the starting point of the line associated with your new constraint. Eventually, click elsewhere in the display area, and the line associated with the constraint will be drawn. Note that your new constraint must necessarily separate the feasible polygon into two parts (otherwise, it will not be drawn). As soon as the line is drawn, its equation appears in the 3 text fields of the 3^rd line. Select the inequality symbol you want ("≥" or "≤") and modify some of the coefficients if you like: now, you can add the new constraint by simply pressing "Add". You cannot modify the starting point of the new line unless you quit and then re-enter this mode, but you can modified the other point at any time by just clicking on the display area (the equation of the line is automatically updated each time you do this). Anytime you wish to quit this mode, just click once again on the text "New constraint:" (this text is already in black when other actions, like for example removing a constraint, have been performed and automatically made the applet exit this mode).



• If you place the mouse cursor on the text area "G2DS 2.0", you will see the copyright of the applet appear on screen. As soon as the cursor exits this text area, the text "G2DS 2.0" will reappear on screen.



• If you place the mouse cursor on the text area "Such that:", you will see the number of constraints of the problem appear on screen. As soon as the cursor exits this text area, the text "Such that:" will reappear on screen.

This section details the new functions available in this applet since the release of the last version. They provide the possibility of solving the linear program defined by the user as an integer linear program. More precisely, it will be solved as a linear program first, and then as an integer linear program. To enter this mode, you just have to click (with a simple click) on the text area "Such that:" (which, as soon as you place the mouse cursor on it, displays the number of constraints) : then, the suffix "(i)" is added to this text area (to point out the fact that we have entered a mode where the integer solutions are displayed), and the information about the integer solutions of the linear program (number of integer solutions, unbounded feasible polygon, existence of an optimal integer solution, etc.) are displayed in the status area. Moreover, the integer solutions contained in the display area are displayed as little black squares, and, if an objective function has been defined and if the optimal integer value is bounded (and provided that the optimal integer solution is contained in the display area!), then this optimal integer solution is displayed as a little square with color (4).

In order to exit this mode (and to come back to the normal one), you just have to click once again (with a simple click) on the text area "Such that:". It should be noticed that the reason why the display area is defined with respect to the feasible basic solutions, and not with respect to the integer solutions (and, in particular, not with respect to the optimal integer solution), is that the optimal integer solution can be quite far from all the feasible basic solutions (and, so, from the optimal basic solution also). For instance, if we consider the following linear program: maximize -3x+y, such that y ≥ 3/2, -x+20y ≤ 30, x ≥ 0 and y ≥ 0, then the optimal basic solution is (x = 0, y = 3/2), while the optimal integer solution is (x = 10, y = 2)!