Combinatorial Optimization by Dynamic Contraction

A heuristic optimization methodology, Dynamic Contraction (DC), is introduced as an approach for solving a wide variety of hard combinatorial problems. Contraction is an operation that maps an instance of a problem to a smaller instance of the same problem. DC is an iterative improvement strategy that relies on contraction as a mechanism for escaping local minima. As a byproduct of contraction, efficiency is improved due to a reduction of problem size. Effectiveness of DC is shown through simple applications to two classical combinatorial problems: The graph bisection problem and the traveling salesman problem.     

He-N2 radiofrequency discharge: Influence of N2 on discharge and afterglow

A diagnostic study q (energy transfer processes in a He-N₂ flowing discharge and afterglow has been performed in a radiofrequency-produced plasma cooled in a liquid nitrogen hath. Optical emission spectroscopy in the visible and infrared spectral range as well as Langrnuir probe diagnostics were used. The vibrational kinetics of CO injected in such an afterglow has been examined. It shows a slow cooling of the electrons in the afterglow regime. The electron kinetics responsible joy CO vibrahonal excitation is turned off when N₂ is added to the He discharge, while that for vibrationally excited N₂ molecules is turned on. The results are discussed on the basis of previous theorerical calculations and experiments on the He-N₂ system.     

Bivariate Free Knot Splines

We consider the least squares approximation of gridded 2D data by tensor product splines with free knots. The smoothing functional to be minimized—a generalization of the univariate Schoenberg functional—is chosen in such a way that the solution of the bivariate problem separates into the solution of a sequence of univariate problems in case of fixed knots. The resulting optimization problem is a constrained separable least squares problem with tensor product structure. Based on some ideas developed by the authors for the univariate case, an efficient method for solving the specially structured 2D problem is proposed, analyzed and tested on hand of some examples from the literature.     

Two differential equation systems for equality-constrained optimization

This paper presents two differential systems, involving first and second order derivatives of problem functions, respectively, for solving equality-constrained optimization problems. Local minimizers to the optimization problems are proved to be asymptotically stable equilibrium points of the two differential systems. First, the Euler discrete schemes with constant stepsizes for the two differential systems are presented and their convergence theorems are demonstrated. Second, we construct algorithms in which directions are computed by these two systems and the stepsizes are generated by Armijo line search to solve the original equality-constrained optimization problem. The constructed algorithms and the Runge–Kutta method are employed to solve the Euler discrete schemes and the differential equation systems, respectively. We prove that the discrete scheme based on the differential equation system with the second order information has the locally quadratic convergence rate under the local Lipschitz condition. The numerical results given here show that Runge–Kutta method has better stability and higher precision and the numerical method based on the differential equation system with the second information is faster than the other one.     

Solving a multiobjective location routing problem with a metaheuristic based on tabu search. Application to a real case in Andalusia

In this work we present a multiobjective location routing problem and solve it with a multiobjective metaheuristic procedure. In this type of problem, we have to locate some plants within a set of possible locations to meet the demands of a number of clients with multiple objectives. This type of model is used to solve a problem with real data in the region of Andalusia (Spain). Thus, we study the location of two incineration plants for the disposal of solid animal waste from some preestablished locations in Andalusia, and design the routes to serve the different slaughterhouses in this region. This must be done while taking into account certain economic objectives (start-up, maintenance, and transport costs) and social objectives (social rejection by towns on the truck routes, maximum risk as an equity criterion, and the negative implications for towns close to the plant).     

等式与界约束非线性优化信赖域算法的全局收敛

§ 1　ＩｎｔｒｏｄｕｃｔｉｏｎＣｏｎｓｉｄｅｒｔｈｅｆｏｌｌｏｗｉｎｇｎｏｎｌｉｎｅａｒｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ :ｍｉｎｉｍｉｚｅｆ(ｘ)ｓｕｂｊｅｃｔｔｏＣ(ｘ) =0 ,　ａ≤ｘ≤ｂ ,( 1 .1 )ｗｈｅｒｅｆ(ｘ) :Ｒｎ→Ｒ ,Ｃ(ｘ) =(ｃ1(ｘ) ,ｃ2 (ｘ) ,...,ｃｍ(ｘ) ) Ｔ:Ｒｎ→Ｒｍ ａｒｅｔｗｉｃｅｃｏｎｔｉｎｕｏｕｓｌｙｄｉｆｆｅｒｅｎｔｉａｂｌｅ,ｍ≤ｎ ,ａ ,ｂ∈Ｒｎ.Ｔｒｕｓｔｒｅｇｉｏｎａｌｇｏｒｉｔｈｍｓａｒｅｖｅｒｙｅｆｆｅｃｔｉｖｅｆｏｒｓｏｌｖｉｎｇｎｏｎｌｉｎｅａｒｏｐｔｉｍｉ…     

A closed-form representation of mixed-integer program value functions

We identify a class of formulas computable in polynomial time such that the functions defined by these formulas are precisely the value functions of mixed-integer programs with rational constraint coefficients.     

Mathematical analysis of investment systems

Investment systems are studied using a framework that emphasize their profiles (the cumulative probability distribution on all the possible percentage gains of trades) and their log return functions (the expected average return per trade in logarithmic scale as a function of the investment size in terms of the percentage of the available capital). The efficiency index for an investment system, defined as the maximum of the log return function, is proposed as a measure to compare investment systems for their intrinsic merit. This efficiency index can be viewed as a generalization of Shannon's information rate for a communication channel. Applications are illustrated.     

求解无线传感器网络路由问题的蚁群最优化算法及其收敛性

首先将无线传感器网络的路由问题转化成求解最小Steiner树问题,然后给出了求解无线传感器网络路由的蚁群优化算法,并对算法的收敛性进行了证明．最后对找到最优解后信息素值的变化进行了分析．即在限制信息素取值的条件下,当迭代次数充分大时,该算法能以任意接近于1的概率找到最优解,并且当最优解找到后,最优树边上的信息素单调增加,而最优解以外边上的信息素在有限步达到最小值．     

Lagrangian Duality in Set-Valued Optimization

In this paper, we study optimization problems where the objective function and the binding constraints are set-valued maps and the solutions are defined by means of set-relations among all the images sets (Kuroiwa, D. in Takahashi, W., Tanaka, T. (eds.) Nonlinear analysis and convex analysis, pp. 221–228, 1999). We introduce a new dual problem, establish some duality theorems and obtain a Lagrangian multiplier rule of nonlinear type under convexity assumptions. A necessary condition and a sufficient condition for the existence of saddle points are given. The authors thank the two referees for valuable comments and suggestions on early versions of the paper. The research of the first author was partially supported by Ministerio de Educación y Ciencia (Spain) Project MTM2006-02629 and by Junta de Castilla y León (Spain) Project VA027B06.