关于三个相同伪硬币问题的一些新结果

本文中,给定一台比较型测试装置和确切的三个相同伪硬币出现的信息,作者研究最小测试数的探求问题,这个最小测试数能从λ个有同样外观的硬币组成的集合中鉴别出三个相同的伪硬币,这里λ≥4.作者构造了对于无限多个λ值的一个最优鉴别分组测试算法,这个最优鉴别分组测试算法改进了To（s）ic的对于无限多个λ值的一个最优鉴别分组测试算法,也改进了Bo（s）njak的对于无限多个λ值的一个最优鉴别分组测试算法.作者还提出另一个鉴别分组测试算法,并且猜想这个算法是最优的.     

基于遗传算法对规避目标搜索模型

分析了在应召条件下对规避目标搜索行动的特点,然后采用遗传算法建立了可用于辅助搜索决策制定协同搜索方案的模型,为分析应召搜索提供了新的方法,该方法克服了传统的运筹学搜索论在协同行动等复杂条件下寻求最优搜索方案的不足。     

多个接收者认证码的信息论下界及其组合特征

对一般的（带保密的）多个接收者认证码进行了讨论,给出了这类认证码的ｒ阶欺骗攻击成功概率的信息论下界,并利用部分平衡ｔ－设计和狭义区组设计刻划了达到信息论下界的多个接收者认证码的组合特征。     

搜索四个坏硬币的最优化方法

给出了用天平从ｎ个硬币的集合中搜索出４个坏硬币的最少测试次数的一个估计。     

线性规划的一种新算法——直接搜索迭代法

本文提出一种新的线性规划迭代算法，它把一般线性规划问题化为一个只含不等式约束的标准形，然后从标准形的任一可行点开始直接进行迭代，即可求出最优解，粗估本算法计算性能在高维时至少不亚于Ｋａｒｍａｒｋａｒ法等内点法，低维时也可与单纯形法相比，且迭代过程无误差积累。     

船载直升机目标搜索最佳方案决策模型

根据现代搜索理论的发展,对船载直升机在目标搜索中的具体运用进行了研究,建立了船载直升机目标搜索时搜索力的最优配置模型,解决了在已知目标分布的条件下船载直升机搜索中选择初始探测点、确定搜索路径、确定搜索次数以及搜索效率评估等问题．     

搜索两个不同坏硬币的最优化方法

设n个外观相同的硬币的集合X中含有两个坏硬币，这两个坏硬币的重量彼此不同，但都比好硬币重，而假定好硬币有相同的重量．以g2（n）表示用天平从X中找出两个坏硬币的最少测试次数．本文证明了对任意的n成立［log3（n2）］≤g2（n）≤［log3（n2）］＋1．且对无穷多个n，文中所给的测试过程是最优的．     

基于遗传算法的对规避目标搜索模型

分析了在应召条件下对规避目标搜索行动的特点,然后采用遗传算法建立了可用于辅助搜索决策者制定协同搜索方案的模型,为分析应召搜索提供了新的方法,该方法克服了传统的运筹学搜索论在协同行动等复杂条件下寻求最优搜索方案的不足     

整数非线性规划的一种直接搜索寻优算法

本文的工作是将Rosenbrock算法移殖求解整数非线性规划,得到一种求解整数非线性规划的直接搜索寻优算法,该算法只要求函数是可计算的,可适用于实际规划问题。     

Searching in trees

In (Discrete Math. 17 (1977)181) Rivest introduced the search complexity of binary trees and proved that among all binary trees with a fixed search complexity the smallest ones are the so-called Fibonacci trees. This result is extended for q-trees. The structure of the smallest q-trees is again Fibonacci-like but more complicated than in the binary case. In addition an upper bound for the asymptotic growth of these trees is given.     

Edge search in graphs with restricted test sets

Suppose a graph G(V,E) contains one defective edge e. We search for the endpoints of e by asking questions of the form “Is at least one of the vertices of X an endpoint of e?”, where X is a subset of V with cardinality at most p. Then what is the minimum number c_p(G) of questions, which are needed in the worst case to find e?We solve this search problem suggested by M. Aigner in [M. Aigner, Combinatorial Search, Teubner, 1988] by deriving lower and sharp upper bounds for c_p(G). For the case that G is the complete graph K_n the problem described above is equivalent to the (2,n) group testing problem with test sets of cardinality at most p. We present sharp upper and lower bounds for the worst case number c_p of tests for this group testing problem and show that the maximum difference between the upper and the lower bounds is 3.     

Exact and heuristic methods for the selective maintenance problem

We present in this paper, new resolution methods for the selective maintenance problem. This problem consists in finding the best choice of maintenance actions to be performed on a multicomponent system, so as to maximize the system reliability, within a time window of a limited duration. When the number of components of the system is important, this combinatorial problem is not easy to solve, in particular because of the nonlinear objective function modeling the system reliability. This problem did not receive much attention yet. Consequently, rare are the effective resolution methods that are offered to the user. We thus developed heuristics and an exact method based on a branch and bound procedure, which we apply to various system configurations. We compare the obtained results, and we evaluate the best method to be used in various situations.     

Searching for a counterfeit coin with two unreliable weighings

We provide a worst-case optimal procedure to identify one unknown heavy coin among N identically looking coins when a balance scale is used and at most two weighing results can be erroneous. The exact minimal number of weighings is determined. This solves completely the weighing problem of the case of two unreliable weighings.     

基于模矢搜索和遗传算法的混合约束优化算法

近年,免梯度方法又开始引起大家的注意，由于不需要计算函数的梯度．特别适合用来求解那些无法得到梯度信息或需要花很大计算量才能得到梯度信息的问题．本文构造了一个基于模矢搜索和遗传算法的混合优化算法．在模矢搜索方法的搜索步，用一个类似于遗传算法的方法产生一个有限点集．算法是全局收敛的.     

Design of computer network topologies: A Vroom Inspired Psychoclonal Algorithm

In the prevailing era of network and communication technology, the problem pertaining to the determination of the most economic way to interconnect nodes while satisfying some reliability and quality of service constraints has been agnized as one of the most intricate and challenging problem for the modern day researchers and practitioners belonging to Communication and Networking community. Motivated by the improved performance of the concepts like proliferation, affinity maturation, receptor editing, etc., over the more prevalent generalized crossover and mutation; and by the application and effectiveness of Maslow’s need hierarchy in combinatorial optimization as well the more logical motivational concepts provided by Vroom’s valence expectancy theory, authors have proposed and investigated their applications to the topological design of distributed packet switched networks. The extensive computations over the problems of varying complexities and dimensions prove the superiority of the proposed methodology. It has been observed that the proposed Vroom Inspired Psychoclonal Algorithm (VIPA) outperforms the traditional well established random search algorithms (i.e. Genetic Algorithm, Simulated Annealing and Artificial Immune Systems) in the context of underlying problem; the performance being significantly improved as the problem complexity increases.     

New lower bounds for the three-dimensional finite bin packing problem

The three-dimensional finite bin packing problem (3BP) consists of determining the minimum number of large identical three-dimensional rectangular boxes, bins, that are required for allocating without overlapping a given set of three-dimensional rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. We propose new lower bounds for the problem where the items have a fixed orientation and then we extend these bounds to the more general problem where for each item the subset of rotations by 90° allowed is specified. The proposed lower bounds have been evaluated on different test problems derived from the literature. Computational results show the effectiveness of the new lower bounds.     

A memetic algorithm approach for solving the multidimensional multi-way number partitioning problem

In this paper, we describe a generalization of the multidimensional two-way number partitioning problem (MDTWNPP) where a set of vectors has to be partitioned into p sets (parts) such that the sums per every coordinate should be exactly or approximately equal. We will call this generalization the multidimensional multi-way number partitioning problem (MDMWNPP). Also, an efficient memetic algorithm (MA) heuristic is developed to solve the multidimensional multi-way number partitioning problem obtained by combining a genetic algorithm (GA) with a powerful local search (LS) procedure. The performances of our memetic algorithm have been compared with the existing numerical results obtained by CPLEX based on an integer linear programming formulation of the problem. The solution reveals that our proposed methodology performs very well in terms of both quality of the solutions obtained and the computational time compared with the previous method of solving the multidimensional two-way number partitioning problem.     

A reference length approach for the 3D strip packing problem

In the three-dimensional strip packing problem (3DSP), we are given a container with an open dimension and a set of rectangular cuboids (boxes) and the task is to orthogonally pack all the boxes into the container such that the magnitude of the open dimension is minimized. We propose a block building heuristic based on extreme points for this problem that uses a reference length to guide its solution. Our 3DSP approach employs this heuristic in a one-step lookahead tree search algorithm using an iterative construction strategy. We tested our approach on standard 3DSP benchmark test data; the results show that our approach produces better solutions on average than all other approaches in literature for the majority of these data sets using comparable computation time.