On the advantage over a random assignment

We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the random assignment algorithm. This is a useful measure for optimization problems where the random assignment algorithm is known to give essentially the best possible polynomial time approximation. In this paper, we focus on this measure for the optimization problems Max‐Lin‐2 in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and Max‐k‐Lin‐2, a special case of the above problem in which each equation has at most k variables. The main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from Fourier analysis and derandomization. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Heuristic Rejection in Interval Global Optimization

Based on the investigation carried out in Ref. 1, this paper incorporates new studies about the properties of inclusion functions on subintervals while a branch-and-bound algorithm is solving global optimization problems. It is found that the relative place of the global minimum value within the inclusion function value of the objective function at the current interval indicates mostly whether the given interval is close to a minimizer point. This information is used in a heuristic interval rejection rule that can save a considerable amount of computation. Illustrative examples are discussed and an extended numerical study shows the advantages of the new approach.     

关于组合最优化理论的多媒体教学实践

本文讨论和分析了开发组合最比化理论系列课程多媒体课件的基本认识、课件的主要特色和体会，并提出了使用多媒体课件中应注意的问题．     

Rational Functions with Prescribed Global and Local Minimizers

A family of multivariate rational functions is constructed. It has strong local minimizers with prescribed function values at prescribed positions. While there might be additional local minima, such minima cannot be global. A second family of multivariate rational functions is given, having prescribed global minimizers and prescribed interpolating data.     

一种改进的数字散斑相关方法用于检测人的口型变化

提出了一种基于数字散斑相关测量技术的口型变化检测技术,该技术以白光数字散斑相关测量方法为基础,根据实际应用的需要,引入重心算法并进行了改进,可以实时地检测人说话时的口型变化。通过实验表明,提出的方法是一种实用的、快速、高精度的口型变化测试方法,可为今后的唇语识别技术奠定基础。     

一种控制掺铒光纤激光器超混沌的方法——非线性延时反馈参数调制法

提出一种非线性延时反馈参数调制法来控制混沌/超混沌，给出了利用这种方法控制处于超混沌状态的双环掺铒光纤激光器的方案.数值模拟表明，只要延时时间和反馈强度合适就可以把双环掺铒光纤激光器从超混沌状态成功地控制到不同的周期状态. 关键词： 掺铒光纤激光器 超混沌 非线性延时反馈参数调制 混沌控制     

Structural optimization design for large mirror

The system design must be started from the concept with low cost and high performance. In this point, the topological shape of the structure is very important in the view of the structural rigidities and light-weight design.In this paper, the optimization methodology is presented in the design stage of the large optical mirror. We obtain the optimal layout through the topology optimization and then design the details through the size or shape optimization for structural rigidity.     

An experimental analysis of a population based approach for global optimization

In this paper we perform a computational analysis of a population based approach for global optimization, Population Basin Hopping (PBH), which was proven to be very efficient on very challenging global optimization problems by the authors (see ). The experimental analysis aims at understanding more deeply how the approach works and why it is successful on challenging problems.     

New Branch-and-Cut Algorithm for Bilevel Linear Programming

Linear mixed 0–1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0–1 Gomory cuts to BLP. The first phase of our new algorithm generates Gomory-like cuts. The second phase consists of a branch-and-bound procedure to ensure finite termination with a global optimal solution. Different features of the algorithm, in particular, the cut selection and branching criteria are studied in details. We propose also a set of algorithmic tests and procedures to improve the method. Finally, we illustrate the performance through numerical experiments. Our algorithm outperforms pure branch-and-bound when tested on a series of randomly generated problems. Work of the authors was partially supported by FCAR, MITACS and NSERC grants.     

Discrete global descent method for discrete global optimization and nonlinear integer programming

A novel method, entitled the discrete global descent method, is developed in this paper to solve discrete global optimization problems and nonlinear integer programming problems. This method moves from one discrete minimizer of the objective function f to another better one at each iteration with the help of an auxiliary function, entitled the discrete global descent function. The discrete global descent function guarantees that its discrete minimizers coincide with the better discrete minimizers of f under some standard assumptions. This property also ensures that a better discrete minimizer of f can be found by some classical local search methods. Numerical experiments on several test problems with up to 100 integer variables and up to 1.38 × 10¹⁰⁴ feasible points have demonstrated the applicability and efficiency of the proposed method.