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

NK-MaxClique and MMCQ: Tow New Exact branch and bound algorithms for the Maximum Clique Problem

IEEE ACCESS 2020年 8卷 180045-180053页

作者： Mohammadi, Neda Kadivar, Mehdi Shahrekord Univ Dept Comp Sci Shahrekord *** Iran

The maximum clique problem (MCP) is a fundamental problem in combinatorial optimization which finds important applications in real-word. This paper describes two new efficient branch-and-bound maximum clique algorithms NK-MaxClique and MMCQ, designed for solving MCP. We define some pruning conditions based on core numbers and vertex ordering to efficiently remove many of the search space. With respect to this ordering, the algorithms consider the vertices respectively to find the corresponding maximum clique in subproblems. Simulation results demonstrate that the algorithms outperform the previous well-known algorithms for many instances when applied to DIMACS benchmark and random graphs.

关键词： Color Approximation algorithms Heuristic algorithms Upper bound Licenses Optimization Simulation branch and bound algorithms complexity core number maximum clique

来源：评论

学校读者我要写书评

暂无评论

Enhancing branch-and-bound for Multiobjective 0-1 Programming

引用

INFORMS JOURNAL ON COMPUTING 2024年第1期36卷 1-304, C2页

作者： Forget, Nicolas Parragh, Sophie N. Aarhus Univ Sch Business & Social Sci Dept Econ & Business Econ DK-8210 Aarhus 5 Denmark Johannes Kepler Univ Linz Inst Prod & Logist Management A-4040 Linz Austria

In the biobjective branch-and-bound literature, a key ingredient is objective branching, that is, to create smaller and disjoint subproblems in the objective space, obtained from the partial dominance of the lower bound set by the upper bound set. When considering three or more objective functions, however, applying objective branching becomes more complex, and its benefit has so far been unclear. In this paper, we investigate several ingredients that allow us to better exploit objective branching in a multiobjective setting. We extend the idea of probing to multiple objectives for the 0-1 case, enhance it in several ways, and show that, when coupled with objective branching, it results in significant speedups in terms of CPU times. We also show how to adapt it to the general integer case. Furthermore, we investigate cut generation based on the objective branching constraints. Besides, we generalize the best bound idea for node selection to multiple objectives, and we show that the proposed rules outperform, in the multiobjective literature, the commonly employed depth-first and breadth-first strategies. We also analyze problem specific branching rules. We test the proposed ideas on available benchmark instances for three problem classes with three and four objectives, namely, the capacitated facility location problem, the uncapacitated facility location problem, and the knapsack problem. Our enhanced multiobjective branch-and-bound algorithm outperforms the best existing branch-and-bound-based approach and is the first to obtain competitive and even slightly better results than a state-of-the-art objective space search method on a subset of the problem classes.

关键词： multiple criteria integer programming branch and bound algorithms multiobjective combinatorial optimization probing node selection rules

来源：评论

学校读者我要写书评

暂无评论

GROUPED VARIABLE SELECTION WITH DISCRETE OPTIMIZATION: COMPUTATIONAL AND STATISTICAL PERSPECTIVES

引用

ANNALS OF STATISTICS 2023年第1期51卷 1-32页

作者： Hazimeh, Hussein Mazumder, Rahul Radchenko, Peter Google Res Mountain View CA 94043 USA MIT Sloan Sch Management 77 Massachusetts Ave Cambridge MA 02139 USA Univ Sydney Univ Sydney Business Sch Sydney NSW Australia

We present a new algorithmic framework for grouped variable selection that is based on discrete mathematical optimization. While there exist several appealing approaches based on convex relaxations and nonconvex heuristics, we focus on optimal solutions for the l(0)-regularized formulation, a problem that is relatively unexplored due to computational challenges. Our methodol-ogy covers both high-dimensional linear regression and nonparametric sparse additive modeling with smooth components. Our algorithmic framework con-sists of approximate and exact algorithms. The approximate algorithms are based on coordinate descent and local search, with runtimes comparable to popular sparse learning algorithms. Our exact algorithm is based on a stan-dalone branch-and-bound (BnB) framework, which can solve the associated mixed integer programming (MIP) problem to certified optimality. By ex-ploiting the problem structure, our custom BnB algorithm can solve to opti-mality problem instances with 5 x 10(6) features and 103 observations in min-utes to hours-over 1000 times larger than what is currently possible using state-of-the-art commercial MIP solvers. We also explore statistical proper-ties of the l(0)-based estimators. We demonstrate, theoretically and empiri-cally, that our proposed estimators have an edge over popular group-sparse estimators in terms of statistical performance in various regimes. We provide an open source implementation of our proposed framework.

关键词： Group variable selection sparsity nonparametric additive models l(0) regularization mixed integer programming branch and bound algorithms

来源：评论

学校读者我要写书评

暂无评论

A Novel Approach for Subgraph Isomorphism Problem on Bipartite Graphs 27

A Novel Approach for Subgraph Isomorphism Problem on Biparti...

引用

27th Signal Processing and Communications Applications Conference (SIU)

作者： Koca, Mehmet Burak Sevilgen, Fatih Erdogan Gebze Tekn Univ Bilgisayar Muhendisligi Bolumu Kocaeli Turkey

ISBN: (纸本)9781728119045

Subgraph isomorphism problem on specialized graphs is an open research area. Most of the algorithms that had been developed for subgraph isomorphism problem are designed for general graphs. Although, they can be utilized for any graph type, this generic design prevents to take advantages of characteristics of the specialized graphs to burst performance of the subgraph isomorphism search. In this study, we will introduce a novel branch and bound algorithm for subgraph isomorphism problem on bipartite graphs. Bipartite feature of these graphs is utilized to improve search performance by limiting the size of possibility set and by getting rid of backtracking phase of branch and bound technique. Experimental results show that the algorithm provides between 10 and 120 fold better performance results on bipartite graphs when it is compared with the state-of-art algorithms.

关键词： Subgraph isomorphism bipartite graphs branch and bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Multiobjective Nonlinear Sum of Fractional Optimization Problems with Nonconvex Constraints with the Use of the Duality-Based branch and bound Algorithm

引用

UKRAINIAN MATHEMATICAL JOURNAL 2018年第11期69卷 1689-1709页

作者： Bhati, D. Singh, P. Motilal Nehru Natl Inst Technol Allahabad Uttar Pradesh India

We study the solution of a multiobjective nonlinear sum of fractional optimization problems. A dualitybased branch and bound cut method is developed for the efficient solution of this problems. The proposed methodology is validated by proving the required theoretical assertions for the solution. The present method is an extension of the work P. P. Shen, Y. P. Duan, and Y. G. Pei [J. Comput. Appl. Math., 223, 145-158 (2009)] developed for a single-objective sum of ratios of nonlinear optimization problems. The proposed method is realized in MatLab (version 2014b). Two numerical problems are considered and solved by using the proposed method and the global optimal solution is obtained.

关键词： Duan Solution sums optimal solution yttrium branch and bound algorithms nonlinearity

来源：评论

学校读者我要写书评

暂无评论

NP-StructurePredictor: Prediction of Unknown Natural Products in Plant Mixtures

引用

JOURNAL OF CHEMICAL INFORMATION AND MODELING 2017年第12期57卷 3138-3148页

作者： Harn, Yeu-Chern Su, Bo-Han Ku, Yuan-Ling Lin, Olivia A. Chou, Cheng-Fu Tseng, Y. Jane Natl Taiwan Univ Grad Inst Networking & Multimedia 1 Roosevelt Rd Sect 4 Taipei 10617 Taiwan NTU Ctr Genom Med Metabolom Core Lab 7F2 Syujhou Rd Taipei 10055 Taiwan Natl Taiwan Univ Dept Comp Sci & Informat Engn 1 Roosevelt Rd Sect 4 Taipei 10617 Taiwan Med & Pharmaceut Ind Technol & Dev Ctr 7F9 Wuquan Rd Taipei 24886 Taiwan Natl Taiwan Univ Grad Inst Biomed Elect & Bioinformat 1 Roosevelt Rd Sect 4 Taipei 10617 Taiwan Natl Taiwan Univ Drug Res Ctr Coll Med 1 Jen Ai Rd Sect 1 Taipei 10051 Taiwan

Identification of the individual chemical constituents of a mixture, especially solutions extracted from medicinal plants, is a time-consuming task. The identification results are often limited by challenges such as the development of separation methods and the availability of known reference standards. A novel structure elucidation system, NP-StructurePredictor, is presented and used to accelerate the process of identifying chemical structures in a mixture based on a branch and bound algorithm combined with a large collection of natural product databases. NP-StracturePredictor requires only targeted molecular weights calculated from a list of m/z values from liquid chromatography-mass spectrometry (LC-MS) experiments as input information to predict the chemical structures of individual components matching the weights in a mixture. NP-StructurePredictor also provides the predicted structures with statistically calculated probabilities so that the most likely chemical structures of the natural products and their analogs can be proposed accordingly. Four data sets consisting of different Chinese herbs with mixtures containing known compounds were selected for validation studies, and all their components were correctly identified and highly predicted using NP-StructurePredictor. NP-StructurePredictor demonstrated its applicability for predicting the chemical structures of novel compounds by returning highly accurate results from four different validation case studies.

关键词： highly accurate branch and bound algorithms Natural products chemical structure mixtures Reference Standards Chemical composition chemical compounds validation study Plants, Medicinal Molecular weights Analog Dataset

来源：评论

学校读者我要写书评

暂无评论

Experimental verification of efficiency of some composite algorithms

Experimental verification of efficiency of some composite al...

引用

International Conference on Applied Mathematics & Computational Science

作者： Vitaly O. Groppen Research Institute of Computer Sciences North-Caucsian Mining and Metallurgy Institute

ISBN: (数字)9781538694688

ISBN: (纸本)9781538694695

The paper contains experimental analysis of efficiency of a new class of algorithms i.e. composite algorithms aimed at solving of knapsack problem providing global optimal solution. These algorithms combine features of branch and bound algorithms together with branch and cut procedure - as latter is used dynamic programming: verified are modifications of branch and bound procedures, which cut off "bad" vectors of variables technique includes technologies used in dynamic programming, and vice versa - modifications of the algorithm, which implements dynamic programming, are involving bounds determination procedures used by branch and bound methods. It is shown experimentally that, in the case of the knapsack problem, the efficiency of these algorithms exceeds the effectiveness of the parent procedures, and this difference increases with the number of variables.

关键词： Boolean variables Composite algorithms Dynamic programming branch and bound procedures Knapsack problem knapsack problems dynamic programming algorithms branches New classes branch and bound methods branch and bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Globally optimal beamforming design for downlink CoMP transmission with limited backhaul capacity

Globally optimal beamforming design for downlink CoMP transm...

引用

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Kien-Giang Nguyen Quang-Doanh Vu Markku Juntti Le-Nam Tran Centre for Wireless Communications University of Oulu P.O. Box 4500 FI-90014 Finland Department of Electronic Engineering Maynooth University Ireland

ISBN: (纸本)9781509041183

This paper considers a multicell downlink channel in which multiple base stations (BSs) cooperatively serve users by jointly precoding shared data transported from a central processor over limited-capacity backhaul links. We jointly design the beamformers and BS-user link selection so as to maximize the sum rate subject to user-specific signal-to-interference-noise (SINR) requirements, per-BS backhaul capacity and per-BS power constraints. As existing solutions for the considered problem are suboptimal and their optimality remains unknown due to the lack of globally optimal solutions, we characterized this gap by proposing an globally optimal algorithm for the problem of interest. Specifically, the proposed method is customized from a generic framework of a branch and bound algorithm applied to discrete monotonic optimization. We show that the proposed algorithm converges after a finite number of iterations, and can serve as a benchmark for existing suboptimal solutions and those that will be developed for similar contexts in the future. In this regard, we numerically compare the proposed optimal solution to a current state-of-the-art, which show that this suboptimal method only attains 70% to 90% of the optimal performance.

关键词： Multicell cooperation limited backhaul sum rate maximization discrete monotonic optimization return stroke optimal solution Downlink beamformers branch and bound algorithms optimum performance Beamforming iterative methods

来源：评论

学校读者我要写书评

暂无评论

Resource Tardiness Weighted Cost Minimization in Project Scheduling (vol 2017, 1308704, 2017)

引用

ADVANCES IN OPERATIONS RESEARCH 2017年第1期2017卷 11-11页

作者： Chaleshtari, Ali Shirzadeh Islamic Azad Univ West Tehran Branch Dept Ind Engn Coll Engn Tehran Iran

In this paper, we study a project scheduling problem that is called resource constrained project scheduling problem under minimization of total weighted resource tardiness penalty cost (RCPSP-TWRTPC). In this problem, the project is subject to renewable resources, each renewable resource is available for limited time periods during the project life cycle, and keeping the resource for each extra period results in some tardiness penalty cost. We introduce a branch and bound algorithm to solve the problem exactly and use several bounding, fathoming, and dominance rules in our algorithm to shorten the enumeration process. We point out parameters affecting the RCPSP-TWRTPC degree of difficulty, generate extensive sets of sample instances for the problem, and perform comprehensive experimental analysis using the customized algorithm and also CPLEX solver. We analyze the algorithm behavior with respect to the changes in instances degree of difficulty and compare its performance for different cases with the CPLEX solver. The results reveal algorithm efficiency.

关键词： Tardiness project life cycle algorithm efficiency algorithms branch and bound algorithms renewable resource

来源：评论

学校读者我要写书评

暂无评论

Combinatorial approach for sizing and optimal energy management of HEV including durability constraints 24

Combinatorial approach for sizing and optimal energy managem...

引用

24th IEEE International Symposium on Industrial Electronics (ISIE)

作者： Chauvin, Alan Hijazi, Alaa Bideaux, Eric Sari, Ali Univ Lyon INSA Lyon Lab Ampere UMR CNRS 5005 F-69621 Villeurbanne France Univ Lyon 1 UMRS CNRS 5005 Lab Ampere F-69622 Lyon France

ISBN: (纸本)9781467375542

This paper presents a combinatorial approach used to solve an optimization problem including component sizing and energy management control applied to an offroad hybrid electric vehicle with durability constraints. The problem under consideration is the optimization of the hybrid power supply system of an electric mini-excavator. It is composed of a fuel cell system and one energy storage system, i. e includes a lithium battery or a supercapacitors pack. The goal is to minimize the global cost of the machine during its entire working lifetime. In order to fulfill the requirements, an ageing model is included in the original problem to simulate the degradation of the battery and the fuel cell. The paper is focused on the reformulation of the nonlinear original problem into combinatorial subproblems. Then a branch and bound algorithm is applied to solve all sub-problems. Some results are presented to compare the different energy storages configurations.

关键词： Energy management Hybrid electric vehicles Power supply systems Porcine hemagglutinating encephalomyelitis virus High Endothelial Venule original problem fuel cell power systems lithium batteries component sizing branch and bound algorithms Durability Supercapacitors SIZING

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：