# Numerical Solutions to the Variational Problems by [PERSON]'s Path-Finding Algorithm
## 7 Catenary Problem
The constant b has to be evaluated numerically from the equation  
\[\text{L}_{\text{r}}=\frac{2\text{b}}{\mu\text{g}}\text{sinh}\left(\frac{\mu \text{g}\text{x}_{\text{s}}}{\text{b}}\right), \tag{35}\]  
To simulate the shape of a hanging rope using [PERSON]'s algorithm, we can simply use the method described in Section 3. The change is only on the definition of the edge's weight. As mentioned above, the edge is an abstract entity. We can assign any suitable physical value and geometrical shape to an edge. In this case, we define an edge as a small straight segment of \(\text{s}_{\text{ij}}\) connecting the vertices i and j. The mass of each segment is \(\mu\text{g}\text{s}_{\text{ij}}\). The gravitational potential of each segment is  
\[\text{U}_{\text{ij}}=\frac{\mu\text{g}\left(\text{y}_{\text{i}}+\text{y}_{ \text{j}}\right)\text{s}_{\text{ij}}}{2}, \tag{36}\]  
where \(\text{y}_{\text{i}}\) and \(\text{y}_{\text{j}}\) are the y-coordinate of the adjacent vertices joined by the edge. We can define this gravitational potential as the weight of the edge joining vertices i and j. The actual shape of the rope can be approximated as the one that minimizes the total gravitational potential:  
\[\text{U}=\sum_{\text{path}}\text{U}_{\text{ij}}. \tag{37}\]  
The [PERSON]'s algorithm will find, among all possible paths, the path with minimum potential. Solving the problem with the length constraint is a bit tricky. We will use the technique of Lagrangian relaxation [23] by introducing an adjustable parameter z to the weight in Equation (36), then minimizing the new potential function,  
\[\text{U}^{\prime}=\sum_{\text{path}}\text{U}^{\prime}_{\text{ij}} \tag{38}\]  
where  
\[\text{U}^{\prime}_{\text{ij}}=\left[\frac{\mu\text{g}\left(\text{y}_{\text{i }}+\text{y}_{\text{j}}\right)}{2}+\text{z}\right]\text{s}_{\text{ij}}. \tag{39}\]  
We can see that this is the discrete version of the Lagrange multiplier technique used in Equation (33) to solve the problem analytically. The parameter z can be adjusted to relax the minimization condition. We may interpret that z can be used to adjust the reference point of the gravitational potential. When z \(>\) 0, the rope is farther away from the reference point, and the optimized path becomes shorter than the path when z \(=\) 0. It is straightforward to expect that when z \(<\) 0, the rope is closer to the reference point, and the optimized path becomes longer than the path when z \(=\) 0. However, the negative z can cause some problems. If z is \"too negative\", it can introduce the negative weights to the system. Summing up the negative weights results in the total weight that is even smaller. The algorithm will find the possible longest path regardless of the value of z. To solve this problem, we must change our question a bit [39]. Instead of finding the optimal path joining the two supporting points, we will find the optimum path joining the lowest point and, let us say, the right supporting point. The left half of the curve is the mirror reflection of the right half, with the vertical line passing the lower point as the axis of symmetry. Since we do not know the position of the lowest point in advance, we will gauss the initial position as the lowest point. The parameter z is adjusted until the slope at, and only at, the lowest point is equal to zero. The length of the optimal path is compared with the desired length. The position of the lowest point and the value of z is then adjusted until the desired length is achieved. Figure 9 shows the resulting catenary curves with various lengths. The dashed lines are the paths obtained from [PERSON]'s algorithm, while the solid lines are the exact solutions from Equations (34) and (35). In all simulations, we use the 20 \(\times\) 20-unit square lattice (\(\Delta x=\Delta y=1\)) with 20 sub-lattices on each plaquette side. The product \(\mu\)g is set to 1 for convenience.