检索结果-南通市图书馆

Lower bounds and a Nearly Fastest General Parallel branch-and-bound Algorithm

在线全文

学校读者我要写书评

暂无评论

Journal of Systems Engineering and Electronics 2000年第3期11卷 65-73页

作者： Wu, Jigang Xie, Xing Wan, Yingyu Chen, Guoliang Dept. of Computer Science Yantai University 264005 P. R. China Dept. of Computer Science University of Science and Technology of China Hefei 230026 P. R. China

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.

关键词： branch-and-bound State-space tree Active list Parallel algorithm Combinatorial search.

A Constraint Programming-Based branch and bound Algorithm for Job Shop Problems

在线全文

学校读者我要写书评

暂无评论

A Constraint Programming-Based Branch and Bound Algorithm fo...

A　branch-AND-PRICE　ALGORITHM　FOR　SOLVING　THE　CUTTING　STRIPS　PROBLEM

2010 Chinese Control and Decision Conference

作者： Yuanyuan Tan,Shixin Liu,Dazhi Wang School of Information Science & Engineering,Northeastern University Key Laboratory off Integrated Automation of Process Industry Shenyang 110004,China

＜正＞In recent years,constraint programming（CP） has been widely applied to solved scheduling *** one of the key elements in CP,constraint propagation has been proved to be an efficient methodology to speed up the search *** this paper,we develop a hybrid branch and bound algorithm with CP technique,called HCPBAB,which focuses on branches cutting to achieve outstanding performance tuning and constraints handling ability compared with the original ***,we extend the popular input/output negation,input-or-output constraint propagation process into HCPBAB to extensively test our proposed *** results on 40 instances taken from standard job shop benchmarks show that 33 instances are optimally solved while HCPBAB obtains 11 better solutions compared with Rego C’s results in 2009.

关键词： Job Shop Scheduling Problem branch-and-bound Constraint Programming Constraint Propagation

来源： cnki会议评论

在线全文

cnki会议

学校读者我要写书评

暂无评论

Applied Mathematics(A Journal of Chinese Universities) 1997年第2期12卷 215-224页

作者： CHENZHIPING C.A.J.HURKENS J.L.DEJONG DepantmeatofMathematicsandComputingSciences EindhovenUniversityofTechnologyTheNertherlands. DepartmentofMathematicsandComputingSciences EindhovenUniversityofTechnologyTheNertherlands. DepartmeatofMathematics Xi＇anJiaotongUniversityXi＇an710049.

After giving a suitable model for the cutting strips problem, we present a branch and price algorithm for it by combining the column generation technique and the branch and bound method with LP relaxations. Some theoretical issues and implementation details about the algorithm are discussed, including the solution of the pricing subproblem, the quality of LP relaxations, the branching scheme as well as the column management. Finally, preliminary computational experience is reported.

关键词： branch-and-bound Column generation Cutting strips problem

Two-Level Linear Relaxation Method for Generalized Linear Fractional Programming

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2023年第3期11卷 569-594页

作者： Hong-Wei Jiao You-Lin Shang Postdoctoral Research Base Henan Institute of Science and TechnologyXinxiang453003HenanChina Postdoctoral Research Station of Control Science and Engineering Henan University of Science and TechnologyLuoyang471023HenanChina

This paper presents an efficient algorithm for globally solving a generalized linear fractional programming *** 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 *** 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 ***,numerical experimental results demonstrate the feasibility and efficiency of the proposed algorithm.

关键词： Generalized linear fractional programming Global optimization Two-level linear relaxation method branch-and-bound

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

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Systems Science and Systems Engineering 2004年第3期13卷 326-341页

作者： Jesper LARSEN Informatics and Mathematical Modelling Technical University of Denmark 2800 Kgs.LyngbyDenmark

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 *** service of the customers can only start within a weU-defined time intervaldenoted the time *** 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 *** paperpresents two ideas for ran-time improvements of the branch-and-Price framework for the VehicleRouting Problem with Time *** ideas reveal a significant potential for run-timerefinements when speeding up an exact approach without compromising optimality.

关键词： Vehicle routing time windows column generation shortest path branch-and-bound

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

在线全文

学校读者我要写书评

暂无评论

Global Energy Interconnection 2021年第5期4卷 493-500页

作者： Jingcheng Mei Guojiang Zhang Donglian Qi Jianliang Zhang College of Electrical Engineering Zhejiang UniversityHangzhou 310027P.R.China State grid Jiangsu Electric Power Company Limited Nanjing210024P.R.China

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 *** the computational complexity of the mixed integer programming(MIP)problem,a machine learning(ML)approach is presented to solve the transmission maintenance scheduling model *** 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 *** 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.

关键词： Transmission maintenance scheduling Mixed integer programming(MIP) Machine learning Bayesian optimization(BO) branch-and-bound

Structural System Reliability Assessment and Updating Using Chain-Structure BNs

在线全文

学校读者我要写书评

暂无评论

建筑工程（中英文版） 2015年第3期3卷 36-43页

作者： Qi’ang Wang Ziyan Wu Zongming Cai School of Mechanics Civil Engineering and ArchitectureNorthwestern Polytechnical UniversityXi’an 710129China

An efficient computational framework for structural system reliability analysis and Updating based on Chain-Structure Bayesian networks(BNs)is present in the *** framework combines BNs and structural reliability methods(SRMs)for reliability assessment and *** have advantages in evaluating complex probabilistic dependence structures and reliability updating,while SRMs are employed to assess the conditional probability *** improved branch-and-bound(B&B)method is integrated with BNs to simplify the whole *** order to further reduce computational demand,failure(or survival)path events are introduced to create chain-structure *** 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 *** show that computational efficiency is improved by the Chain-Structure *** reliability problems with both continuous and discrete random variables can be better resolved by combining BNs and *** approach is also able to update system reliability when new information available.

关键词： System Reliability Chain-Structure BNs Improved branch-and-bound Method Failure Path Events PNET

An Algorithm for Global Optimization Using Formula Manupulation

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Applied Mathematics 2012年第11期3卷 1601-1606页

作者： Tsutomu Shohdohji Fumihiko Yano Department of Computer and Information Engineering Nippon Institute of Technology Saitama Japan Division of Integrated Sciences J. F. Oberlin University Tokyo Japan

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.

关键词： Global Optimization Lipschitz Constant Lipschitz Condition branch-and-bound Algorithm Formula Manipulation

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

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

American Journal of Operations Research 2015年第6期5卷 503-513页

作者： Mayank Verma Renduchintala Raghavendra Kumar Sharma Department of Industrial and Management Engineering Indian Institute of Technology Kanpur Kanpur India

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.

关键词： Capacitated Lot Sizing Linear Relaxation Strong Formulation Hybrid Formulation branch-and-bound