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.

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.

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.

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.

Two-Level Linear Relaxation Method for Generalized Linear Fractional Programming

This paper presents an efficient algorithm for globally solving a generalized linear fractional programming problem.For establishing this algorithm,we firstly construct a two-level linear relaxation method,and by utilizing the method,we can convert the initial generalized linear fractional programming problem and its subproblems into a series of linear programming relaxation problems.Based on the branch-and-bound framework and linear programming relaxation problems,a branch-and-bound algorithm is presented for globally solving the generalized linear fractional programming problem,and the computational complexity of the algorithm is given.Finally,numerical experimental results demonstrate the feasibility and efficiency of the proposed algorithm.

Parallel Bounded Search for the Maximum Clique Problem

Given an undirected graph,the Maximum Clique Problem(MCP)is to find a largest complete subgraph of the graph.MCP is NP-hard and has found many practical applications.In this paper,we propose a parallel Branch-and-Bound(BnB)algorithm to tackle this NP-hard problem,which carries out multiple bounded searches in parallel.Each search has its upper bound and shares a lower bound with the rest of the searches.The potential benefit of the proposed approach is that an active search terminates as soon as the best lower bound found so far reaches or exceeds its upper bound.We describe the implementation of our highly scalable and efficient parallel MCP algorithm,called PBS,which is based on a state-of-the-art sequential MCP algorithm.The proposed algorithm PBS is evaluated on hard DIMACS and BHOSLIB instances.The results show that PBS achieves a near-linear speedup on most DIMACS instances and a superlinear speedup on most BHOSLIB instances.Finally,we give a detailed analysis that explains the good speedups achieved for the tested instances.

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.

REFINEMENTS OF THE COLUMN GENERATION PROCESS FOR THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

The Vehicle Routing Problem with Time Windows is a generalization of the well knowncapacity constrained Vehicle Routing Problem.A homogeneous fleet of vehicles has to service a setof customers.The service of the customers can only start within a weU-defined time intervaldenoted the time window.The objective is to determine routes for the vehicles that minimizes theaccumulated cost(or distance).Currently the best approaches for determining optimal solutions arebased on column generation and Branch-and-Bound,also known as Branch-and-Price.This paperpresents two ideas for ran-time improvements of the Branch-and-Price framework for the VehicleRouting Problem with Time Windows.Both ideas reveal a significant potential for run-timerefinements when speeding up an exact approach without compromising optimality.