The Branch Processes of Chern-Simons (CS) <Emphasis Type="Italic">p</Emphasis>-Branes

In this paper, by making use of Duan’s topological current theory, the branch process of Chern-Simons (CS) p-branes is discussed in detail. Chern-Simons (CS) p-branes are found generating or annihilating at the limit points and encountering, splitting, or merging at the bifurcation points and higher degenerated points systematically of the vector order parameter field . Furthermore, it is also shown that CS p-branes are found splitting or merging at the degenerate point of field function but the total topological charges of the CS p-branes are still unchanged.     

Calculating safety stocks for assembly systems with random component procurement lead times: A branch and bound algorithm

In this paper, a discrete single-level multi-component inventory control model for assembly systems with random component procurement lead times is considered. The economic order quantity (EOQ) policy is used for a type of finished product. The requirements of the components are constant and cyclic (periodic), and their values per period are deduced from the EOQ for the finished product. The paper focuses on the components safety stock calculation. The objective is to minimise the average holding cost of the components while keeping the desired service level for the finished product. For this, an upper bound, two lower bounds, two dominance properties and an efficient branch and bound algorithm are suggested. Several tests are executed and conclusions are drawn. The proposed model provides a substantial saving for assembly systems with a large number and unreliable delivery of components as in semi-conductor and automotive industries.     

求线性比试和问题的确定性全局优化算法

为求线性比试和问题的全局最优解,本文给出了一个分支定界算法.通过一个等价问题和一个新的线性化松弛技巧,初始的非凸规划问题归结为一系列线性规划问题的求解.借助于这一系列线性规划问题的解,算法可收敛于初始非凸规划问题的最优解.算法的计算量主要是一些线性规划问题的求解.数值算例表明算法是切实可行的.     

A new branch and bound algorithm for cell formation problem

Cell formation (CF) is the first and the most important problem in designing cellular manufacturing systems. Due to its non-polynomial nature, various heuristic and metaheuristic algorithms have been proposed to solve CF problem. Despite the popularity of heuristic algorithms, few studies have attempted to develop exact algorithms, such as branch and bound (B&B) algorithms, for this problem. We develop three types of branch and bound algorithms to deal with the cell formation problem. The first algorithm uses a binary branching scheme based on the definitions provided for the decision variables. Unlike the first algorithm, which relies on the mathematical model, the second one is designed based on the structure of the cell formation problem. The last algorithm has a similar structure to the second one, except that it has the ability to eliminate duplicated nodes in branching trees. The proposed branch and bound algorithms and a hybrid genetic algorithm are compared through some numerical examples. The results demonstrate the effectiveness of the modified problem-oriented branch and bound algorithm in solving relatively large size cell formation problems.     

Comparing branch-and-price algorithms for the Multi-Commodity k-splittable Maximum Flow Problem

The Multi-Commodity k-splittable Maximum Flow Problem consists in routing as much flow as possible through a capacitated network such that each commodity uses at most k paths and the capacities are satisfied. The problem appears in telecommunications, specifically when considering Multi-Protocol Label Switching. The problem has previously been solved to optimality through branch-and-price. In this paper we propose two exact solution methods both based on an alternative decomposition. The two methods differ in their branching strategy. The first method, which branches on forbidden edge sequences, shows some performance difficulty due to large search trees. The second method, which branches on forbidden and forced edge sequences, demonstrates much better performance. The latter also outperforms a leading exact solution method from the literature. Furthermore, a heuristic algorithm is presented. The heuristic is fast and yields good solution values.     

Investment in electricity networks with transmission switching

We consider the application of Dantzig-Wolfe decomposition to stochastic integer programming problems arising in the capacity planning of electricity transmission networks that have some switchable transmission elements. The decomposition enables a column-generation algorithm to be applied, which allows the solution of large problem instances. The methodology is illustrated by its application to a problem of determining the optimal investment in switching equipment and transmission capacity for an existing network. Computational tests on IEEE test networks with 73 nodes and 118 nodes confirm the efficiency of the approach.     

一类带反凸约束的非线性比式和问题的全局优化算法

本文针对一类带有反凸约束的非线性比式和分式规划问题,提出一种求其全局最优解的单纯形分支和对偶定界算法.该算法利用Lagrange对偶理论将其中关键的定界问题转化为一系列易于求解的线性规划问题.收敛性分析和数值算例均表明提出的算法是可行的.     

Challenges of continuous global optimization in molecular structure prediction

The molecular geometry, the three dimensional arrangement of atoms in space, is a major factor determining the properties and reactivity of molecules, biomolecules and macromolecules. Computation of stable molecular conformations can be done by locating minima on the potential energy surface (PES). This is a very challenging global optimization problem because of extremely large numbers of shallow local minima and complicated landscape of PES. This paper illustrates the mathematical and computational challenges on one important instance of the problem, computation of molecular geometry of oligopeptides, and proposes the use of the Extended Cutting Angle Method (ECAM) to solve this problem.     

The mixed and multi model line balancing problem: a comparison

The balancing problem deals with the assignment of tasks to work stations. We can distinguish two approaches in the literature on the mixed model line balancing problem, that both transform this problem into a single model line balancing problem. These approaches use combined precedence diagrams and adjusted task processing times, respectively.An experiment was carried out to compare several heuristics based on the combined precedence diagram. A new optimisation method has been developed. The results indicate that the position of common tasks in the precedence diagram of the different models has a significant effect on both the CPU time and the unequal distribution of the total work content of single models among work stations. Moreover, good solutions with respect to the number of required stations go together with long CPU times. For several instances, we decreased the CPU times considerably without deteriorating the performance of the methods, by using a reversed combined precedence diagram.