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) » (min for « minimize » and max for « maximize »), where the values a, b, c, d and e are constant.

To summarize, solving a linear program consists in optimizing (i.e., minimizing or maximizing) a linear function over a convex set (polyhedron) which, in 2 dimensions, is a polygon (possibly empty or unbounded). In what follows, 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, or (with a slight abuse of terminology) a feasible basic solution. Let z^* be the (finite) optimal value of a linear program (i.e., the best value that any of its feasible basic solutions can have), and let its objective function be [opt] (dx + ey) (where [opt] is equal to either min or max): 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.

In its current release, this software has been written as a Java program (and more precisely released as a JAR archive). As for any Java program, this means that, in order to run it, you will need to have a Java Virtual Machine (or JVM, in short) installed on your computer.

The basic command that needs to be executed in a console or terminal in order to run a Java program called G2DS and released as a JAR archive (which means that its full name is « G2DS.jar ») is the following one (where « java » is precisely the name of the program corresponding to the JVM, and where « > » is the symbol for the command prompt):

• The first line of the file contains the objective function, written as « OPT sep coefficient of x sep coefficient of y ». Here, « OPT » is either equal to « MIN » (if one wants to minimize the objective function), or equal to « MAX » (if one wants to maximize the objective function), or even equal to anything else except « . » (if one does not want to define any objective function). Obviously, « coefficient of x » (respectively « coefficient of y ») denotes the coefficient of x (respectively the one of y) in such an objective function.


• Each of the remaining lines in the file (except the last one) is associated with a constraint, written as « coefficient of x sep coefficient of y sep inequality sign sep right-hand side ». Here, obviously, « coefficient of x » and « coefficient of y » are the coefficients of x and y, respectively, in this constraint, « right-hand side » is the value of the right-hand side of the constraint, and « inequality sign » is the pair of symbols that actually represents the inequality sign (« <= » for « ≤ », and « >= » for « ≥ »).


• Eventually, the last line of the file only contains a single symbol « . », which indicates that we have reached the end of the file.

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 in this case). 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 former one is lost.

The status area is located between the three upper lines of the software and the area where the graphical representation of the problem is displayed. This status area, displayed in red, is used by the software 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 software, 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 software automatically computes the most suitable zoom factor. You can be informed of the scaling factor used by the software 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 features provided by this software which are not absolutely necessary for a basic use. To begin with, we describe the features associated with buttons:

• The « Recall » and « Clear » buttons (1^st line) are respectively used for displaying the coefficients of the current objective function (i.e., 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 software that (some of) your inputs are ratios of integers and that you expect not to loose any precision. If you press this button, the software will transform your constraint into an equivalent one with integer coefficients. This new constraint cannot be reduced any further (which means that 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 at least one of your inputs is a 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 + 1 y ≥ 4/5 » is incorrect (as far as the « Reduce » button is concerned!).

• You can modify the colors used in the software by double-clicking on certain areas. 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 area of the software. To modify the color (2), double-click anywhere inside the feasible polygon. To modify the color (3), double-click on the underlined text area « Problem status: ». To modify the color (4), double-click on the text « Objective function: ». Eventually, to modify the color (5), double-click on the underlined text area « 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 select a constraint in the list of constraints (2^nd line), then the corresponding facet (if any!) will be selected and its color will be the color (3), except if this is either « x = 0 » or « y = 0 ».


• If you click (with a simple click) on the underlined text area « 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, and 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 modify 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 underlined text area « New constraint: » (although this text is already in black when other actions, like for example removing a constraint, have been performed and automatically made the software exit this mode).


• If you place the mouse cursor on the text area « G2DS 3.0 », you will see the copyright of the software appear on screen. As soon as the cursor exits this text area, the text « G2DS 3.0 » will reappear on screen.


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


• Similarly, since the release of Version 3.0, if you place the mouse cursor on the underlined text area « Problem status: », you will see the number of facets of the problem appear on screen (also underlined). As soon as the cursor exits this text area, the underlined text « Problem status: » will reappear on screen.

This section details the new features available in this software since the release of Version 2.0. 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 underlined text area « Such that: » (which, as soon as you place the mouse cursor on it, actually displays the number of constraints, also underlined): 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 now 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!), 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 underlined 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)!

This section details the new (new) features available in this software since the release of Version 3.0.

Firstly, if you click (with a simple click) on the underlined text area « Problem status: » (which, as soon as you place the mouse cursor on it, actually displays the number of facets, also underlined), then a first facet of the problem (among the ones that are neither « x = 0 » nor « y = 0 », if at least one such facet exists!) is selected (and thus will be of color (3)), and the corresponding constraint is also selected in the list of constraints (2^nd line). If you click again (with a simple click) on this text area, another facet is selected instead (as well as the corresponding constraint), and then another one, and so on. If you click a sufficient number of times so that all the facets have been successively selected, then the process will start again from the first facet selected. Notice that adding or removing a constraint (and other events, such as asking the software to solve the linear program as an integer linear program) will make the software exit this mode (and then you will have to start the whole process again from the beginning, if needed).

Secondly, if you click (with a simple click) on the underlined text area that indicates the number of feasible basic solutions of the problem (1^st line of the status area, in red), then a first feasible basic solution of the problem is selected (and thus will be of color (3)), and its coordinates are displayed in the text area « Basic solution displayed: » (in which, as long as this is not the case, is simply displayed « Basic solution displayed: none »). If you click again (with a simple click) on this text area, another feasible basic solution is selected instead (and, again, its coordinates are displayed in the text area « Basic solution displayed: »), and then another one, and so on. If you click a sufficient number of times so that all the feasible basic solutions have been successively selected, then the process will start again from the first feasible basic solution. Notice, here again, that adding or removing a constraint (and other events, such as asking the software to solve the linear program as an integer linear program) will make the software exit this mode (and then you will have to start the whole process again from the beginning, if needed).