Attic method

However, since bound constraints are crucial to the efficiency of the Attic method, it is very important that they are assigned for all the variables. 

however, fundamental to preprocess the constraints to remove all useless variables and constraints, and insert the maximum number of bounds, thereby hopefully reducing their distance, and exploiting all the information contained in the assigned constraints. 

Many linear programming efficiency tests proposed in the literature are (maybe intentionally) formulated in absurd ways equations without variables, variables that do not appear anywhere in the constraints, linear combinations, useless equations, and so on. 

To deal with these problems, it is essential to preprocess the data so as to make them consistent. After the preprocessing procedure, the number of variables and constraints can be significantly reduced with respect to the original problem. 

The person that knows the problem will always formulate it best. 

---

The BzzFactorizedGaussAttic name comes from the fact that the first time it was used to solve a linear programming problem with the Attic method (see Chapter 10). The BzzFactorizedGaussAttic class includes the default constructor only. An object from this class is initialized using as the argument the matrix of the system and its right-hand side terms. 

The concept on which the Attic method is based is that any feasible point (vertex or nonvertex) sees the solution (it can be joined to the solution by a line) as the space is convex for all the linear programming problems (Buzzi-Ferraris, 2011b). 

Therefore, the Attic method is a halfway route between the Simplex method and the Interior Point method in fact, the working point must not lay on a vertex, which makes the method behave more like the Interior Point method, but, at the same time, the active constraints are satisfied, which makes it look like the Simplex method. 

Contrary to Simplex and Interior Point, nonnegativity constraints do not play a special role in the Attic method, apart from their prerogative of making the corresponding row of the matrix D particularly sparse. 

From a theoretical viewpoint, the Attic method does not require bound constraints to be made explicit, particularly nonnegativity constraints. 

The Attic method is based on the necessary conditions by Karush, Kuhn, and Tucker (KKT) applied to a problem, which is linear in its objective function and constraints. 

In the Attic method, it is essential to distinguish between the vertex and nonvertex feasible points. Since we talk about vertices even in traditional methods, albeit sometimes with different meanings, we will indicate vertices for the Attic method as attic vertices when there is a significant difference. An attic vertex may differ from the traditional vertex for two reasons first, the attic vertex may involve a smaller number of variables second, an attic vertex satisfies n constraints with n > ny and all the rows of the matrix J are real constraints. This is possible only if the rank m of the corresponding matrix J is equal to ny. A point that satisfies either n constraints even with n > ny but with rank m < ny or n constraints with rank m = ny but with only n y < ny — ns real active (within the matrix J) constraints is not an attic vertex. The importance of distinguishing between attic vertices and nonvertex feasible points is explained below. 

A second important difference in the Attic method is the presence of artificial inequality constraints these are constraints on a single variable and, when they are present in the matrix J, they must be treated differently to the active bound constraints since they are not real constraints. 

Differences between the Attic Method and Traditionai Approaches 1363... 

The Attic method exploits this possibility with the aim of preventing steps in the optimization procedure that are too small. In this, it differs from the Simplex method also since it is possible to move from a feasible attic vertex to a feasible nonvertex. 

The Attic method differs from traditional methods in certain important ways. Five of them are reported hereinafter ... 

The first difference is that the Attic method does not require the problem to be written in the standard form and therefore does not require the introduction of any additional variables. The number of rows and the number of columns from the matrix J used at each iteration in the Attic method are always equal to the number of variables, ny, obtained after the preprocessing. 

The following simple example (Figure 10.1) highlights the differences between the requirements of the standard form and the Attic method formulation. 

Differences beUveen the Attic Method and Traditional Approaches 1365... 

Therefore, the matrix A consists of 9 rows and 12 columns. If the variable X2, which is not subject to the nonnegativity constraint, were explicitly obtained by an equation rather than replaced by two variables, the matrix A would consist of 8 rows and 10 columns. The matrix J used in the Attic method at each iteration is dimensioned 2x2, which is the same size as the original problem, whereas the matrix Fi will have dimensions between 0x0 and 2x2. 

This simple example highlights the following advantages of the Attic method and how it differs from the Simplex method ... 

The matrix J used by the Attic method may have significantly smaller dimensions than the matrix A used by traditional methods. Consequently, computational effort can be reduced at each iteration. 

The fourth significant difference is that some of the matrix J rows may be artificial constraints. This is the real, and most important, difference between Attic and Simplex or Interior Point methods, and makes the Attic method extremely flexible and potentially more efficient than the traditional methods. 

In the Simplex method, a vertex must be considered to be the working point conversely, in the Attic method, it is looked on from a different point of view it is the intersection of ny constraints. In a problem with many vertices and a relatively small number of constraints, this possibility may have significant benefits when the constraints that will be active at the solution can be inserted one at a time (see Section 10.5.1). 

In a convex space, every vertex or feasible point can be joined by a straight line to the solution. Often, such a line must leave one or more constraints that the working point is lying on and pass through the attic to achieve the solution the Attic method leaves one or more constraints when it is advantageous, while the Simplex method cannot. 

As previously mentioned, in the Attic method, it is important to discriminate between attic vertices and interior points, between different types of constraints, and between variables with floor or roof constraints. 

To understand how the Attic method works and the advantages it offers, the previous problems (10.33) and (10.34) are solved below, starting from the point Xi = X2 = 0 (see Figure 10.1). 

In the starting point, the Attic method verifies whether any variable has only floor constraints as satisfied constraints. In this problem, both the variables have the same sign in both the objective function and in the satisfied constraints hence there are no roof constraints for them and it is possible to perform a search along X by obtaining xi = l x2 =0 F = —5, and along x 2 by obtaining xi = 0 x 2 = 1 F = —6. 

Having performed the aforementioned searches, the Attic method executes another search with the equality constraints and the artificial constraints as the initial matrix J. Since no equality constraints are involved in this problem, the initial matrix J is the identity matrix. Thus, the initial operating matrix, Fi, that must be factorized, has dimensions 0x0. 

The number of iterations required to achieve the solution is always smaller or equal to the iterations of the Simplex method in fact, the Attic method could follow the same procedure as the Simplex method, but the number of iterations can be dramatically reduced if some internal feasible points are... 

In the Simplex method, a (variable) column is inserted into the basic matrix and another one exits from it at each iteration. The column exchanged can be any column in the existing matrix and this leads to several difficulties in updating the new column in terms of memory allocation and factorization stability as well. In the Attic method, one row is introduced at a time, but it is not inserted between the rows already present. This new row is inserted immediately after the rows already factorized. The factorization of the new row can be efficiently performed by exploiting the existing factorization of the rows already present in the matrix, and the sparsity of both the new and the existing rows. 

The Attic method is different from the Interior Point in that it does not make constraints inviolable through a barrier. While it does not have to use vertices at each iteration, as per Simplex methods, it often limits or prevents an explosion in the number of vertices to be sequentially analyzed. 

The Simplex and Attic methods can be seen as different strategies of active set methods applied to the special problem of linear function and linear constraints. 

Zigzagging and cycling problems may also arise in the Attic method, but the Attic method can provide some simple devices to combat these problems when they occur since it is not necessary to pass through the adjacent vertices. To understand the problem and to search for the proper strategies, it is useful to start from the analogy on which the Attic method is based that is, visualizing a convex surface that contains the attic. 

The Attic method tries to exploit the fact that the ratio of the number of vertices to the number of constraints for linear programming problems is usually very large. 

For example, the ratio is 2 /nv for this class of problems since the number of constraints 2ny linearly increases with ttv- It is, therefore, suitable to consider a vertex as the intersection of ny constraints rather than as a working point. By doing so, the most promising constraints will be inserted one at a time. Unlike the Simplex method, this is possible for the Attic method since it is not forced to move only on vertices (see Figure 10.2). 

At this point, it is possible to evaluate the maximum number of iterations required to solve this special class of problems by means of the general strategy proposed in the Attic method. 

Table 10.1 shows the maximum number of iterations with respect to the problem dimensions that should be required by the Simplex method and by the Attic method to solve the linear programming problems with these features (e.g., the Klee-Minty problem). 

Table 10.1 Number of iterations with respect to the dimension of the problem (10.46) and (10.47) comparison between Simplex and Attic methods.

The Attic method is able to solve this particular problem by exploiting only the searches along variables with floor constraints. To check the behavior of the Attic method, when it is not possible to exploit such a device, the sequence obtained... 

---