Using discrete optimization algorithms to find minimum energy configurations of slender cantilever beams with non-convex energy functions

This paper deals with a new solution technique for approximately solving certain variational problems in elasticity by using discrete optimization techniques that were originally used in information theory. This allows us to easily and approximately solve large deformation buckling problems for slender cantilever beams (including post-buckling behavior) as well as problems where the strain energy function is non-convex.The core idea is to quantize or discretize the variables describing the possible configurations of the body. This, when combined with the fact that the variational problem has an inherent Markov structure allows us to use computationally efficient search techniques based on dynamic programming (equivalent to finding the shortest path in a weighted directed graph) to find optimal solutions within the quantized state space. The results can be used in two ways: (1) directly as a fast approximate solution to the variational problem (2) As a means for finding very good (nearly minimum energy) initial configurations for application of conventional minimization techniques, which might otherwise fail because of a poor starting configurations which are far from the global minimum. We demonstrate both these uses in the paper.     

Infeasible-interior-point algorithm for a class of nonmonotone complementarity problems and its computational complexity

This paper presents an infeasible-interior-point algorithm for a class of nonmonotone complementarity problems, and analyses its convergence and computational complexity. The results indicate that the proposed algorithm is a polynomial-time one.     

Spherical Minimax Location Problem

This paper presents an algorithm for determining a minimax location to service demand points that are equally weighted and distributed over a sphere. The norm under consideration is geodesic. The algorithm presented here is based on enumeration and has a polynomial time complexity.     

A handy proof of Gay's theorem

In 1979, Gay proved that Broyden's methods, when used for n‐square linear systems, terminate in at most 2n iterations (SIAM J. Numer. Anal. 1979; 16 :623–630). Also, the ABS methods were introduced in 1984 (Numer. Math. 1984; 45 :1361–1376). In this paper we show another (handy) proof of Gay's theorem by these algorithms. Copyright © 2008 John Wiley & Sons, Ltd.     

On the performance of the ICP algorithm

We present upper and lower bounds for the number of iterations performed by the Iterative Closest Point (ICP) algorithm. This algorithm has been proposed by Besl and McKay as a successful heuristic for matching of point sets in d-space under translation, but so far it seems not to have been rigorously analyzed. We consider two standard measures of resemblance that the algorithm attempts to optimize: The RMS (root mean squared distance) and the (one-sided) Hausdorff distance. We show that in both cases the number of iterations performed by the algorithm is polynomial in the number of input points. In particular, this bound is quadratic in the one-dimensional problem, under the RMS measure, for which we present a lower bound construction of Ω(nlogn) iterations, where n is the overall size of the input. Under the Hausdorff measure, this bound is only O(n) for input point sets whose spread is polynomial in n, and this is tight in the worst case.We also present several structural geometric properties of the algorithm under both measures. For the RMS measure, we show that at each iteration of the algorithm the cost function monotonically and strictly decreases along the vector Δt of the relative translation. As a result, we conclude that the polygonal path π, obtained by concatenating all the relative translations that are computed during the execution of the algorithm, does not intersect itself. In particular, in the one-dimensional problem all the relative translations of the ICP algorithm are in the same (left or right) direction. For the Hausdorff measure, some of these properties continue to hold (such as monotonicity in one dimension), whereas others do not.     

Energy-Efficient Broadcast and Multicast Trees in Wireless Networks

The wireless networking environment presents formidable challenges to the study of broadcasting and multicasting problems. In this paper we focus on the problem of multicast tree construction, and we introduce and evaluate algorithms for tree construction in infrastructureless, all-wireless applications. The performance metric used to evaluate broadcast and multicast trees is energy-efficiency. We develop the Broadcast Incremental Power (BIP) algorithm, and adapt it to multicast operation by introducing the Multicast Incremental Power (MIP) algorithm. These algorithms exploit the broadcast nature of the wireless communication environment, and address the need for energy-efficient operation. We demonstrate that our algorithms provide better performance than algorithms that have been developed for the link-based, wired environment.     

Fuzzy minimum weight edge covering problem

Minimum weight edge covering problem, known as a classic problem in graph theory, is employed in many scientific and engineering applications. In the applications, the weight may denote cost, time, or opponent’s payoff, which can be vague in practice. This paper considers the edge covering problem under fuzzy environment, and formulates three models which are expected minimum weight edge cover model, α-minimum weight edge cover model, and the most minimum weight edge cover model. As an extension for the models, we respectively introduce the crisp equivalent of each model in the case that the weights are independent trapezoidal fuzzy variables. Due to the complexity of the problem, a hybrid intelligent algorithm is employed to solve the models, which can deal with the problem with any type of fuzzy weights. At last, some numerical experiments are given to show the application of the models and the robustness of the algorithm.     

一个新的线性规划无人工变量算法

本文研究了线性规划的求解问题.利用对偶转化的方法,获得了一个计算效率高的新的无人工变量通用算法.该新算法比最近提出的无人工变量算法push-to-pull算法效率更高.     

An ant-based algorithm for coloring graphs

This paper presents an ant-based algorithm for the graph coloring problem. An important difference that distinguishes this algorithm from previous ant algorithms is the manner in which ants are used in the algorithm. Unlike previous ant algorithms where each ant colors the entire graph, each ant in this algorithm colors just a portion of the graph using only local information. These individual coloring actions by the ants form a coloring of the graph. Even with the lack of pheromone laying capacity by the ants, the algorithm performed well on a set of 119 benchmark graphs. Furthermore, the algorithm produced very consistent results, having very small standard deviations over 50 runs of each graph tested.