Lower Bounds and a Nearly Fastest General Parallel Branch-and-Bound Algorithm

In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p+h log p) for the general parallel best-first B&B algorithm in PRAM-CREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p+H+(H/p) log (H/p)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one as p = max{hε, r}, where ε = 1/ rootlogh, and r is the largest branch number of the nodes in the state-space tree.

A branch-and-bound algorithm for multi-dimensional quadratic 0-1 knapsack problems

In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding feasible solutions. The Lagrangian relaxations were solved with the maximum-flow algorithm and the Lagrangian bounds was determined with the outer approximation method. Computational results show the efficiency of the proposed method for multi-dimensional quadratic 0-1 knapsack problems.

A branch-and-bound algorithm for discrete multi-factor portfolio optimization model

In this paper, a new branch-and-bound algorithm based on the Lagrangian dual relaxation and continuous relaxation is proposed for discrete multi-factor portfolio selection model with roundlot restriction in financial optimization. This discrete portfolio model is of integer quadratic programming problems. The separable structure of the model is investigated by using Lagrangian relaxation and dual search. Computational results show that the algorithm is capable of solving real-world portfolio problems with data from US stock market and randomly generated test problems with up to 120 securities.

Constrained branch-and-bound algorithm for image registration

In this paper, the authors propose a refined Branch-and-Bound algorithm for affine-transformation based image registration. Given two feature point-sets in two images respectively, the authors first extract a sequence of high-probability matched point-pairs by considering well-defined features. Each resultant point-pair can be regarded as a constraint in the search space of Branch-and-Bound algorithm guiding the search process. The authors carry out Branch-and-Bound search with the constraint of a pair-point selected by using Monte Carlo sampling according to the match measures of point-pairs. If such one cannot lead to correct result, additional candidate is chosen to start another search. High-probability matched point-pairs usually results in fewer loops and the search process is accelerated greatly. Experimental results verify the high efficiency and robustness of the author’s approach.

Relaxation-strategy-based Modification Branch-and-Bound Algorithm for Solving a Class of Transportation-production Problems

In this paper,a new algorithm relaxation-strategy-based modification branchand-bound algorithm is developed for a type of solving the minimum cost transportationproduction problem with concave production costs.The major improvement of the proposed new method is that modification algorithm reinforces the bounding operation using a Lagrangian relaxation,which is a concave minimization but obtains a tighter bound than the usual linear programming relaxation.Some computational results are included.Computation results indicate that the algorithm can solve fairly large scale problems.

AN IMPROVED BRANCH-AND-BOUND ALGORITHM TO MINIMIZE THE WEIGHTED FLOWTIME ON IDENTICAL PARALLEL MACHINES WITH FAMILY SETUP TIMES

This article investigates identical parallel machines scheduling with family setup times. The objective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.

Learning to Branch in Combinatorial Optimization With Graph Pointer Networks

Traditional expert-designed branching rules in branch-and-bound(B&B) are static, often failing to adapt to diverse and evolving problem instances. Crafting these rules is labor-intensive, and may not scale well with complex problems.Given the frequent need to solve varied combinatorial optimization problems, leveraging statistical learning to auto-tune B&B algorithms for specific problem classes becomes attractive. This paper proposes a graph pointer network model to learn the branch rules. Graph features, global features and historical features are designated to represent the solver state. The graph neural network processes graph features, while the pointer mechanism assimilates the global and historical features to finally determine the variable on which to branch. The model is trained to imitate the expert strong branching rule by a tailored top-k Kullback-Leibler divergence loss function. Experiments on a series of benchmark problems demonstrate that the proposed approach significantly outperforms the widely used expert-designed branching rules. It also outperforms state-of-the-art machine-learning-based branch-and-bound methods in terms of solving speed and search tree size on all the test instances. In addition, the model can generalize to unseen instances and scale to larger instances.

Data mining and well logging interpretation: application to a conglomerate reservoir

Data mining is the process of extracting implicit but potentially useful information from incomplete, noisy, and fuzzy data. Data mining offers excellent nonlinear modeling and self-organized learning, and it can play a vital role in the interpretation of well logging data of complex reservoirs. We used data mining to identify the lithologies in a complex reservoir. The reservoir lithologies served as the classification task target and were identified using feature extraction, feature selection, and modeling of data streams. We used independent component analysis to extract information from well curves. We then used the branch-and- bound algorithm to look for the optimal feature subsets and eliminate redundant information. Finally, we used the C5.0 decision-tree algorithm to set up disaggregated models of the well logging curves. The modeling and actual logging data were in good agreement, showing the usefulness of data mining methods in complex reservoirs.

Accelerated solution of the transmission maintenance schedule problem:a Bayesian optimization approach

To maximize the maintenance willingness of the owner of transmission lines,this study presents a transmission maintenance scheduling model that considers the energy constraints of the power system and the security constraints of on-site maintenance operations.Considering the computational complexity of the mixed integer programming(MIP)problem,a machine learning(ML)approach is presented to solve the transmission maintenance scheduling model efficiently.The value of the branching score factor value is optimized by Bayesian optimization(BO)in the proposed algorithm,which plays an important role in the size of the branch-and-bound search tree in the solution process.The test case in a modified version of the IEEE 30-bus system shows that the proposed algorithm can not only reach the optimal solution but also improve the computational efficiency.

System Reliability Analysis of Offshore Strctures and Component Safety Rank Assessment

Offshore structures will encounter serious environmental load, so it is important to study the structural system reliability and to evaluate the structural component safety rank. In this paper, the bracnch-and-bound method is adopted to search the main failure path, and the Ditlevsen bound method is used to calculate the system failure probability. The structure is then assessed by the fuzzy comprehensive assessment method, which evaluates the structural component safety rank. The ultimate equation of the tubular cross- section is analyzed on the basis of ultimate stregnth analysis. The influence of effect coefficients on the structural system failure probability is investigated, and basic results are obtained. A general program for spatial frame structures by means of the above method is developed, and verified by the numerical examples.

Weekly Fleet Assignment Model and Algorithm

A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet assignment, subject to the constraints of coverage, aircraft flow balance, fleet size, aircraft availability, aircraft usage, flight restriction, aircraft seat capacity, and stopover. Then the branch-and-bound algorithm based on special ordered set was applied to solve the model. At last, a real- wofld case study on an airline with 5 fleets, 48 aircrafts and 1 786 flight legs indicated that the profit increase was ￥ 1 591276 one week and the running time was no more than 4 rain, which shows that the model and algorithm are fairly good for domestic airline.

反向Top-k查询算法研究

互联网中沉淀了大量可分析利用的数据,如何有效地利用这些海量数据,为不同行业产品制造方提供对新产品的分析,已成为时下的热点。反向Top-k查询技术是一种常用的数据分析及处理技术,并且已经在很多领域得到了应用。研究了已有的基于反向Top-k的查询算法Skyband-based算法和Branch-and-bound算法,针对很多实际应用领域偏好权重向量会出现改变的情况,提出了一种适用于进行"二次计算"的交互式算法,通过实验将交互式算法跟效率高的Branch-and-bound算法对比得出,当用户修改部分偏好权重向量之后,利用交互式算法可以比Branchand-bound算法更加高效率地计算出结果。

A nonlinear service composition method based on the Skyline operator

The concept of service composition can provide the complex functionality for users. As the widespread application of cloud computing, the number of services grows exponentially. It becomes more difficult to find out the optimal service composition solution quickly. This paper proposes a nonlinear service composition method based on the Skyline operator. The Skyline operator is to find a collection of data that cannot be dominated by others, which is used to prune the redundant services to reduce the search space. Then the service composition problem is formulated as a nonlinear integer programming model by a mathematical programming language(AMPL), and solved by the existing nonlinear solvers Bonmin. The experiments show that the proposed method can effectively improve the efficiency of service composition, while ensuring the quality of solution.

Application of Portfolio Model in the Real Investment Transactions

This paper studies discrete investment portfolio model that the objective function is utility function. According to a hybrid branch-and-bound method based on Lagrangian relaxation and continuous relaxation, the paper analyzes the question using the real statistical data. The results indicate that discrete investment portfolio model really has its guidance in the actual investment.

An Algorithm for Global Optimization Using Formula Manupulation

Constrained nonlinear optimization problems are well known as very difficult problems. In this paper, we present a new algorithm for solving such problems. Our proposed algorithm combines the Branch-and-Bound algorithm and Lipschitz constant to limit the search area effectively;this is essential for solving constrained nonlinear optimization problems. We obtain a more appropriate Lipschitz constant by applying the formula manipulation system of each divided area. Therefore, we obtain a better approximate solution without using a lot of searching points. The efficiency of our proposed algorithm has been shown by the results of some numerical experiments.

Structural System Reliability Assessment and Updating Using Chain-Structure BNs

An efficient computational framework for structural system reliability analysis and Updating based on Chain-Structure Bayesian networks(BNs)is present in the paper.The framework combines BNs and structural reliability methods(SRMs)for reliability assessment and updating.BNs have advantages in evaluating complex probabilistic dependence structures and reliability updating,while SRMs are employed to assess the conditional probability table.The improved branch-and-bound(B&B)method is integrated with BNs to simplify the whole network.In order to further reduce computational demand,failure(or survival)path events are introduced to create chain-structure BNs.Considering the correlations between failure modes,the system reliability is obtained through the Probability Network Estimation Technology(PNET).Finally,the reliability updating is carried out through BNs inference.Results show that computational efficiency is improved by the Chain-Structure BNs.System reliability problems with both continuous and discrete random variables can be better resolved by combining BNs and SRMs.This approach is also able to update system reliability when new information available.

Hybrid Formulation of the Multi-Item Capacitated Dynamic Lot Sizing Problem

It is shown that when backorders, setup times and dynamic demand are included in capacitated lot sizing problem, the resulting classical formulation and one of the transportation formulations of the problem (referred to as CLSP_BS) are equivalent. And it is shown that both the formulations are “weak” formulations (as opposed to “strong” formulation). The other transportation version is a strong formulation of CLSP_BS. Extensive computational studies are presented for medium and large sized problems. In case of medium-sized problems, strong formulation produces better LP bounds, and takes lesser number of branch-and-bound (B&B) nodes and less CPU time to solve the problem optimally. However for large-sized problems strong formulation takes more time to solve the problem optimally, defeating the benefit of strength of bounds. This essentially is because of excessive increase in the number of constraints for the large sized problems. Hybrid formulations are proposed where only few most promising strong constraints are added to the weak formulation. Hybrid formulation emerges as the best performer against the strong and weak formulations. This concept of hybrid formulation can efficiently solve a variety of complex real life large-sized problems.

Research on Optimization of Selection of Train Passing Routes and Division of Shunting Work in Railway Hub

in this paper, a general integer prosramming model is set up, and its solution ispresented to optimize the organization of wagon flows and the determination ofthe train running route as well as division of shuntins work among stations in ahub. As application example is put forword, with some conclusions reached.

Safety estimation of structural systems via interval analysis

Considering that the uncertain information has serious influences on the safety of structural systems and is always limited, it is reasonable that the uncertainties are generally described as interval sets. Based on the non-probabilistic set-theoretic theory, which is applied to measuring the safety of structural components and further combined with the branch-and-bound method for the probabilistic reliability analysis of structural systems, the non-probabilistic branch-and-bound method for determining the dominant failure modes of an uncertain structural system is given. Meanwhile, a new system safety measuring index obtained by the non-probabilistic set-theoretic model is investigated. Moreover, the compatibility between the classical probabilistic model as well as the proposed interval-set model will be discussed to verify the physical meaning of the safety measure in this paper. Some numerical examples are utilized to illustrate the validity and feasibility of the developed method.

ESTIMATED AND EXACT SYSTEM RELIABILITIES OF A MAINTAINABLE COMPUTER NETWORK

This paper presents an algorithm to evaluate estimated and exact system reliabilities for a computer network in the cloud computing environment.From the quality of service（QOS） viewpoint,the computer network should be maintained when falling to a specific state such that it cannot afford enough capacity to satisfy demand.Moreover,the transmission time should be concerned as well.Thus,the data can be sent through several disjoint minimal paths simultaneously to shorten the transmission time.Under the maintenance budget B and time constraint T,we evaluate the system reliability that d units of data can be sent from the cloud to the client through multiple paths.Two procedures are integrated in the proposed algorithm-an estimation procedure for estimated system reliability and an adjusting procedure utilizing the branch-and-bound approach for exact system reliability.Subsequently,the estimated system reliability with lower bound and upper bound,and exact system reliability are computed by applying the recursive sum of disjoint products（RSDP） algorithm.