检索结果-内蒙古大学图书馆

Reference-point-based branch and bound algorithm for multiobjective optimization

JOURNAL OF GLOBAL OPTIMIZATION 2024年第4期88卷 927-945页

作者： Wu, Wei-tian Yang, Xin-min Sichuan Univ Coll Math Chengdu 610065 Peoples R China Natl Ctr Appl Math Chongqing Chongqing 401331 Peoples R China Chongqing Normal Univ Sch Math Sci Chongqing 401331 Peoples R China

In this paper, a nonconvex multiobjective optimization problem with Lipschitz objective functions is considered. A branch and bound algorithm that incorporates the decision maker's preference information is proposed for this problem. In the proposed algorithm, a new discarding test is designed to check whether a box contains preferred solutions according to the preference information expressed by means of reference points. In this way, the proposed algorithm is able to gradually guide the search towards the region of interest on the Pareto fronts during the solution process. We prove that the proposed algorithm obtains e-efficient solutions distributed among the regions of interest with respect to the given reference points. Moreover, lower bound on the total finite number of required iterations for predefined precision is also provided. Finally, the algorithm is illustrated with a number of test problems.

关键词： Multiobjective optimization branch and bound algorithm Preference information Reference point

来源：评论

学校读者我要写书评

暂无评论

Enhanced branch and bound algorithm: Minimizing Subproblem Complexity in Power Dispatch

引用

IEEE ACCESS 2024年 12卷 93753-93760页

作者： Cesur, Elif Cesur, Muhammet Rasit Abraham, Ajith Istanbul Medeniyet Univ Ind Engn Dept TR-34700 Istanbul Turkiye Bennett Univ Sch Comp Sci Engn & Technol Greater Noida 201310 Uttar Pradesh India

The branch and bound (BB) algorithm, while ensuring optimality, often encounters performance bottlenecks, characterized by slow execution and high computational overhead, especially when dealing with intricate or extensive problem instances (NP-Hard). This study introduces an innovative approach by dividing the problem into partial (local) problems in a manner that would not compromise optimality and solving sub-problems of each local problem individually, to shrink the solution space. In the initial phase, this research establishes and validates the mathematical foundation of the proposed algorithm, which involves a pruning approach. Subsequently, enhancements are incorporated into the existing BB to partition the solution space into more manageable sub-spaces and consolidate solutions from these sub-spaces. In the final phase, the Enhanced branch and bound (EBB) algorithm is applied to a real-world power dispatching optimization case study. The outcomes of this investigation reveal the following: 1) For smaller problem instances, both the conventional BB and the proposed EBB algorithm yield identical optimal solutions. 2) In contrast, the EBB algorithm demonstrates significantly improved performance in solving NP-hard problems that pose challenges for the BB and BB with pruning. The primary contribution of this research is the introduction of EBB, an enhanced version of BB, specifically designed to effectively tackle NP-hard problems. This approach can be integrated with all pruning, branching, and bounding strategies used in BB, thereby boosting its performance and making it applicable to all problems solved by BB variations.

关键词： Optimization Search problems NP-hard problem Machine learning algorithms Dispatching Surveys Problem-solving Power distribution branch and bound algorithm pruning strategy enhanced branch and bound algorithm power dispatching optimization

来源：评论

学校读者我要写书评

暂无评论

A branch and bound algorithm for Scheduling of Flexible Manufacturing Systems

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2024年第3期21卷 4382-4396页

作者： Ahn, Jeongsun Kim, Hyun-Jung Korea Adv Inst Sci & Technol Dept Ind & Syst Engn Daejeon 34141 South Korea

Flexible manufacturing systems (FMSs), which can easily adapt to changes in job types, have been widely used in manufacturing areas. Scheduling of FMSs is a variant of a flexible job shop with transport robots and no buffer, and it is extremely hard as it involves determining the job processing sequence on machines and the sequence of robot tasks, with various jobs with different processing flows and the risk of deadlocks. Due to these characteristics, many existing studies have focused on developing heuristic algorithms. However, an optimal solution is still crucial to minimize FMSs makespan. Therefore, we propose a mixed integer programming (MIP) and a branch and bound (B & B) algorithm with a timed Petri net (TPN) to achieve optimal scheduling of FMSs. FMSs are first modeled with a TPN, and tight lower bounds are proposed based on bottleneck machines and sophisticated ready times. In addition, the search space is effectively reduced by the transition index marking (TIM)-based dominance rule and various deadlock prevention conditions based on the TPN. The experimental results show that our proposed B & B algorithm outperforms mathematical formulation and previous algorithms in various FMS instances

关键词： branch and bound algorithm flexible manufacturing system optimization Petri net scheduling

来源：评论

学校读者我要写书评

暂无评论

A branch and bound algorithm for Transmission Network Expansion Planning Using Nonconvex Mixed-Integer Nonlinear Programming Models

引用

IEEE ACCESS 2022年 10卷 39875-39888页

作者： Zoppei, Reinaldo T. Delgado, Marcos A. J. Macedo, Leonardo H. Rider, Marcos J. Romero, Ruben Fed Univ Rondonopolis Inst Exact & Nat Sci BR-78736900 Rondonopolis Mato Grosso Brazil Sao Paulo State Univ Dept Elect Engn BR-15385000 Ilha Solteira SP Brazil Univ Estadual Campinas Dept Syst & Energy BR-13083852 Campinas SP Brazil

The branch and bound (BB) algorithm is widely used to obtain the global solution of mixed-integer linear programming (MILP) problems. On the other hand, when the traditional BB structure is directly used to solve nonconvex mixed-integer nonlinear programming (MINLP) problems, it becomes ineffective, mainly due to the nonlinearity and nonconvexity of the feasible region of the problem. This article presents the difficulties and ineffectiveness of the direct use of the traditional BB algorithm for solving nonconvex MINLP problems and proposes the formulation of an efficient BB algorithm for solving this category of problems. The algorithm is formulated taking into account particular aspects of nonconvex MINLP problems, including (i) how to deal with the nonlinear programming (NLP) subproblems, (ii) how to detect the infeasibility of an NLP subproblem, (iii) how to treat the nonconvexity of the problem, and (iv) how to define the fathoming rules. The proposed BB algorithm is used to solve the transmission network expansion planning (TNEP) problem, a classical problem in power systems optimization, and its performance is compared with the performances of off-the-shelf optimization solvers for MINLP problems. The results obtained for four test systems, with different degrees of complexity, indicate that the proposed BB algorithm is effective for solving the TNEP problem with and without considering losses, showing equal or better performance than off-the-shelf optimization solvers.

关键词： Search problems Propagation losses Planning Metaheuristics Linear programming Biological system modeling Programming profession branch and bound algorithm mixed-integer nonlinear programming optimization transmission network expansion planning

来源：评论

学校读者我要写书评

暂无评论

A branch and bound algorithm for optimal television commercial scheduling

引用

MATHEMATICAL BIOSCIENCES AND ENGINEERING 2022年第5期19卷 4933-4945页

作者： Lu-Wen Liao Natl Taichung Univ Sci & Technol Dept Intelligent Prod Engn Taichung 40401 Taiwan

In the current era of multimedia, television (TV) plays an important role in transmitting advertising messages. In addition, advertising is the primary source of revenue for the TV industry. Thus, a critical issue for TV stations is the scheduling of commercials in suitable advertising breaks on different TV channels to maximize revenue and minimize penalties. This type of TV commercial scheduling problem is similar to the machine scheduling problem, and both have availability constraints. However, the literature on TV commercial scheduling has not considered this perspective. Motivated by this, we consider the problem of scheduling commercials with specific service-level requirements on TV channels while minimizing the maximum lateness. The lateness of a commercial is defined to be its completion time minus its due date, and the maximum lateness is the maximum value of lateness among all commercials. We propose an exact branch and bound algorithm based on the LFJ (least flexible job first)/EDD (earliest due date first) rules and network flow methods, which were developed to solve the machine scheduling problem with availability constraints. Computational analysis shows that the bounding scheme proposed is highly effective, and a very low percentage of nodes is generated by the branch and bound algorithm. The algorithm can obtain an optimal solution for the problem.

关键词： TV commercials service level requirement scheduling LFJ EDD rule branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving the fuzzy assignment problems via utilizing branch and bound algorithm-practically treated

ITALIAN JOURNAL OF PURE AND APPLIED MATHEMATICS

引用

ITALIAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2022年第48期48卷 481-490页

作者： Dawood, Shimaa Mohammed Elaibi, Waleed Mohammed Chachan, Hanan Ali Mustansiriyah Univ Coll Sci Dept Math Baghdad Iraq Mustansiriyah Univ Dept Stat Coll Adm & Econ Baghdad Iraq

In this paper described of assignment cost for the numbers that are fuzzy. Here, the assignment problem, which is fuzzy or invalid, is turned into crisp values throughout robust ranking technique, and by using branch and bound algorithm we gated the optimal solution and at a less *** applied example is taken from Source No. (9) to solving the assignment problem for the Cotton Industries Company in Iraq and find the optimal assignment and total cost.

关键词： fuzzy assignment problem branch and bound algorithm assignment problem robust ranking technique

来源：评论

学校读者我要写书评

暂无评论

A branch and bound algorithm to solve a two-machine no-wait flowshop scheduling problem with truncated learning function

引用

INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE AND ENGINEERING MANAGEMENT 2020年第2期15卷 89-95页

作者： Azizi, Vahid Hu, Guiping Iowa State Univ Dept Ind & Mfg Syst Engn Ames IA 50011 USA

This paper addresses a two-machine no-wait flowshop problem with the effect of the truncated learning function of jobs whose actual processing times depend on their positions in the sequence. By considering truncated learning effect, the actual processing time of a job is a function of its position index in the schedule and a control parameter. In a production scenario with truncated learning effect, the actual processing time of a job will not be lower than a threshold when the number of processed jobs increases. We develop a branch and bound algorithm to minimize the makespan. A lower bound and a dominance property have been proposed to increase the speed of elimination process in the branch and bound algorithm.

关键词： Flowshop scheduling no-wait truncated learning branch and bound algorithm heuristic

来源：评论

学校读者我要写书评

暂无评论

Optimal Reactive Power Dispatch With Discrete Controllers Using a branch-and-bound algorithm: A Semidefinite Relaxation Approach

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2021年第5期36卷 4539-4550页

作者： Constante F., Santiago G. Lopez, Juan Camilo Rider, Marcos J. Univ Campinas UNICAMP Dept Syst & Energy Sch Elect & Comp Engn BR-13083852 Campinas SP Brazil

In this paper, a methodology to solve the optimal reactive power dispatch (ORPD) in electric power systems (EPS), considering discrete controllers, is proposed. Discrete controllers, such as the tap position of on-load tap changing (OLTC) transformers and switchable reactive shunt compensation, are optimized by the proposed method. A semidefinite relaxation (SDR) of the ORPD problem and a branch-and-bound (B&B) algorithm have been fully deployed. A new formulation is presented for the OLTC transformers to obtain a connected structure of the semidefinite programming (SDP) matrices. The customized B&B algorithm deals with the discrete nature of the binary control variables. Moreover, in order to enhance the convexification, valid inequalities called lifted nonlinear cuts (NLC) are implemented in the SDR. Additionally, a chordal decomposition technique is used to improve the computational performance. Finally, the B&B algorithm is used to solve the mixed-integer semidefinite programming problem. Several benchmarks have been used to show the accuracy and scalability of the proposed method, and convergence analysis shows that near-global optimal solutions are generated with small relaxation gaps.

关键词： Reactive power Programming Shunts (electrical) Switches Steady-state Matrix decomposition Linear matrix inequalities branch and bound algorithm discrete controllers electric power systems lifted nonlinear cuts optimal reactive power dispatch semidefinite relaxation

来源：评论

学校读者我要写书评

暂无评论

Developing a Game-Based Learning for branch and bound algorithm 11

Developing a Game-Based Learning for Branch and Bound Algori...

引用

11th International Conference on Advanced Computer Science and Information Systems (ICACSIS)

作者： Aditya, Stefanus James Santoso, Harry Budi Isal, R. Yugo Kartono Univ Indonesia Fac Comp Sci Depok Indonesia

ISBN: (纸本)9781728152929

The use of information technology in the e-Learning process gives positive and negative impacts. One of the positive impacts is the easy access for vast information;while the negative impacts is the ineffective learning because it makes students lazy. Previous research has used games or game elements to decrease the negative impacts of e-Learning. A survey about algorithm Design and Analysis course was conducted, and it shows that there are some difficult subjects that need to be taught using an alternative method of learning. This research discusses how to design a video game in order to learn branch and bound algorithm and evaluate the game produced with the design. First, online surveys were done to gather the requirement, then the game design was made, then the game was implemented and evaluated. The evaluation would be used to make a better design for the next development iteration. The result of playtesting shows positive feedbacks and receives critics and suggestions. This research finds that designing a good game for learning is hard because developer must carefully define all elements in the game, so that everything is balanced and complements each other.

关键词： Education Game-Based Learning Game Development branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

Data-Driven Travel Itinerary with branch and bound algorithm 16

Data-Driven Travel Itinerary with Branch and Bound Algorithm

引用

16th IEEE Int Conf on Dependable, Autonom and Secure Comp/16th IEEE Int Conf on Pervas Intelligence and Comp/4th IEEE Int Conf on Big Data Intelligence and Comp/3rd IEEE Cyber Sci and Technol Congress (DASC/PiCom/DataCom/CyberSciTech)

作者： Du Jiaoman Li Lei Li Xiang Hosei Univ Grad Sch Engn Tokyo 1848584 Japan Hosei Univ Fac Sci & Engn Tokyo 1848584 Japan Beijing Univ Chem Technol Sch Econ & Management Beijing 100029 Peoples R China

ISBN: (纸本)9781538675182

In this paper, we study a novel self-driving travel planning problem, where the tourist aims to minimize the total cost. The idea is to use a mathematical model to planning a route-time scheme for travel spots and hotels. Specifically, this planning determines the tour for travel spots and considers the hotel selection under the rest break constraint, as well as schemes routes and time arrangement for the trip. Meanwhile, based on real-time and multi-resource demand, we use multi-resource data to execute multiple websites' information extraction. We utilize two algorithms to solve the proposed problem and make a comparison, one is exact branch and bound scheme and the other is the branch and bound based heuristic algorithm. In the proposed heuristic algorithm, the travel spots in the problem are decomposed by K-means algorithm, then each group of travel spots is bounded by the greedy algorithm and Hungarian method for upper bound and lower bound, respectively. Each branch node branches using Hungarian method and each branch can be treated as an assignment problem solved by Hungarian method. Finally, we give numerical examples and discuss the results.

关键词： Travel Itinerary Problem branch and bound algorithm Data-Driven

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：