基于分支限界的不平衡气象数据晴雨分析

不平衡数据分类是机器学习研究的热点问题,传统分类算法假定不同类别分布大致平衡,并不符合天气数据实际情况。提出基于修改的代价敏感学习的方法对不平衡的天气数据进行预处理,结合天气数据自身的特点,以单位时间的降雨量为成本的值,将数据合理有效地区分为下雨与非下雨两类。进而运用基于逻辑的方法对处理完的数据进行分析,运用分支限界算法得出布尔分类器。实验结果表明此方法可行有效。该方法可进一步对布尔分类器结果进行逻辑运算,从而达到更加灵活地操作分类器的效果。     

Robust heuristic algorithms for exploiting the common tasks of relational cloud database queries

Cloud computing enables a conventional relational database system's hardware to be adjusted dynamically according to query workload, performance and deadline constraints. One can rent a large amount of resources for a short duration in order to run complex queries efficiently on large-scale data with virtual machine clusters. Complex queries usually contain common subexpressions, either in a single query or among multiple queries that are submitted as a batch. The common subexpressions scan the same relations, compute the same tasks (join, sort, etc.), and/or ship the same data among virtual computers. The total time spent for the queries can be reduced by executing these common tasks only once. In this study, we build and use efficient sets of query execution plans to reduce the total execution time. This is an NP-Hard problem therefore, a set of robust heuristic algorithms, Branch-and-Bound, Genetic, Hill Climbing, and Hybrid Genetic-Hill Climbing, are proposed to find (near-) optimal query execution plans and maximize the benefits. The optimization time of each algorithm for identifying the query execution plans and the quality of these plans are analyzed by extensive experiments.     

解离散系数滤波器设计问题的分支定界算法

基于离散系数滤波器设计问题已有的半定规划松弛模型,利用文献[6]的方法给出了该问题的二次规划松弛模型,该模型能给出比半定规划模型更好的界,然后运用分支定界方法求解该模型。与随机扰动方法相比,该方法能得到一个性能更好的次优解,对于精度要求较高的滤波器设计问题,这种方法非常有效,并通过了仿真实验的证实。     

A new approach to the d-MC problem

Many real-world systems (such as cellular telephones, transportation, etc.) are multistate-node acyclic network (MNAN) composed of multistate-nodes. Such network has a source node (position) where the signal source is located, a number of sink nodes that only receive the signal, and a number of intermediate nodes that retransmit the received signal to some other nodes. The non-sink node has different states determined by a set of nodes receiving the signal directly from it. The reliability of MNAN can be computed in terms of minimal trees (MTs). Based on the Branch-and-Bound algorithm, we developed an intuitive algorithm that is simpler than the best-known existing method. The computational complexity of the proposed algorithm is also analyzed. One example is illustrated to show how all MTs are generated by the proposed algorithm. The reliability of this example is then computed.     

Festlegung einer Jahresarbeitszeitverteilung durch Optimierung von Schichtplänen

Zusammenfassung Es wird ein Verfahren zur kostenminimalen Festlegung einer kapazitätsorientierten Jahresarbeitszeitverteilung für den Produktionsbereich vorgestellt. Dazu wird auf Basis einer vorgegebenen Menge von Schichtplänen eine simultane Auswahl- und Reihenfolgeplanung durchgeführt, die die Jahresarbeitszeitverteilung optimiert. Im Gegensatz zu den gängigen Verfahren zur Jahresarbeitszeitplanung können bei dieser Vorgehensweise die durch die Schichtpläne auferlegten Arbeitszeitrestriktionen sowie die damit verbundenen Kosten im Detail berücksichtigt werden. Der Einfluß planungsrelevanter Parameter auf die resultierende Jahresarbeitszeitverteilung wird ausführlich diskutiert.     

立体堆与分枝界限算法

分枝界限算法是解决组合优化问题的常用方法之一.对于给定的问题和分枝策略,算法的运行时间取决于实现算法的数据结构.该文讨论了立体堆及其上的插入、删除算法;通过将分枝界限算法的运作过程与排序过程建立对应关系,给出了一般分枝界限算法的复杂度下界Ω(m+hlogh),其中m为评估的结点数,h为扩展的结点数;得出了立体堆为实现一般分枝界限算法的几乎最优数据结构;并对具体的作业分派问题实现了一个使用立体堆的分枝界限算法;提出了改善立体堆平衡性的措施.     

Flow shop scheduling for separation model of set-up and net process based on Branch-and-Bound method

Lots of research reports on flow shop scheduling problems have been reported. Generally speaking, these models are applicable to a simple model with no separation of set-up processes and net ones. In many production lines, we cannot ignore the set-up times in comparison with the net processing times. We can expect to shorten the total processing time by executing the set-up processes and net ones in parallel. We need a parallel operation model to improve schedule results.We will propose a new scheduling method for multi-stage flow shops. The aim of the method is to shorten the total processing time by operating the set-up processes and the net ones of each job in parallel. We applied the Branch-and-Bound method and developed a new calculation algorithm for the lower bound estimation of the total processing time. Finally, we will evaluate our proposed method by some numerical experiments using actual production line data.     

Branch and bound for the cutwidth minimization problem

The cutwidth minimization problem consists of finding a linear arrangement of the vertices of a graph where the maximum number of cuts between the edges of the graph and a line separating consecutive vertices is minimized. We first review previous approaches for special classes of graphs, followed by lower bounds and then a linear integer formulation for the general problem. We then propose a branch-and-bound algorithm based on different lower bounds on the cutwidth of partial solutions. Additionally, we introduce a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic to obtain good initial solutions. The combination of the branch-and-bound and GRASP methods results in optimal solutions or a reduced relative gap (difference between upper and lower bounds) on the instances tested. Empirical results with a collection of previously reported instances indicate that the proposed algorithm is able to solve all the small instances (up to 32 vertices) as well as some of the large instances tested (up to 158 vertices) using less than 30 minutes of CPU time. We compare the results of our method with previous lower bounds, and with the best previous linear integer formulation solved using Cplex. Both comparisons favor the proposed procedure.     

HBBA: hybrid algorithm for buffer allocation in tandem production lines

In this paper, we consider the problem of buffer space allocation for a tandem production line with unreliable machines. This problem has various formulations all aiming to answer the question: how much buffer storage to allocate between the processing stations? Many authors use the knapsack-type formulation of this problem. We investigate the problem with a broader statement. The criterion depends on the average steady-state production rate of the line and the buffer equipment acquisition cost. We evaluate black-box complexity of this problem and propose a hybrid optimization algorithm (HBBA), combining the genetic and branch-and-bound approaches. HBBA is excellent in computational time. HBBA uses a Markov model aggregation technique for goal function evaluation. Nevertheless, HBBA is more general and can be used with other production rate evaluation techniques.     

Comparison of deterministic and stochastic approaches to global optimization

In this paper, we compare two different approaches to nonconvex global optimization. The first one is a deterministic spatial Branch‐and‐Bound algorithm, whereas the second approach is a Quasi Monte Carlo (QMC) variant of a stochastic multi level single linkage (MLSL) algorithm. Both algorithms apply to problems in a very general form and are not dependent on problem structure. The test suite we chose is fairly extensive in scope, in that it includes constrained and unconstrained problems, continuous and mixed‐integer problems. The conclusion of the tests is that in general the QMC variant of the MLSL algorithm is generally faster, although in some instances the Branch‐and‐Bound algorithm outperforms it.