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

Delay Margin Analysis of Uncertain Linear Control Systems Using Probabilistic μ

INTERNATIONAL JOURNAL OF ROBUST AND NONLINEAR CONTROL 2025年第6期35卷 2101-2118页

作者： Somers, F. Roos, C. Biannic, J. -m. Sanfedino, F. Preda, V. Bennani, S. Evain, H. Univ Toulouse DTIS ONERA Toulouse France ISAE SUPAERO Toulouse France ESA-ESTEC Noordwijk Netherlands CNES Toulouse France

Monte Carlo simulations have long been a widely used method in the industry for control system validation. They provide an accurate probability measure for sufficiently frequent phenomena but are often time-consuming and may fail to detect very rare events. Conversely, deterministic techniques such as mu or IQC-based analysis allow fast calculation of worst-case stability margins and performance levels, but in the absence of a probabilistic framework, a control system may be invalidated on the basis of extremely rare events. Probabilistic mu-analysis has therefore been studied since the 1990s to bridge this analysis gap by focusing on rare but nonetheless possible situations that may threaten system integrity. The solution adopted in this paper implements a branch-and-bound algorithm to explore the whole uncertainty domain by dividing it into smaller and smaller subsets. At each step, sufficient conditions involving mu upper bound computations are used to check whether a given requirement-related to the delay margin in the present case-is satisfied or violated on the whole considered subset. Guaranteed bounds on the exact probability of delay margin satisfaction or violation are then obtained, based on the probability distributions of the uncertain parameters. The difficulty here arises from the exponential term e-tau s classically used to represent a delay tau, which cannot be directly translated into the Linear Fractional Representation (LFR) framework imposed by mu-analysis. Two different approaches are proposed and compared in this paper to replace the set of delays e-tau s,tau is an element of[0 phi]. First, an equivalent representation using a rational function with unit gain and phase variations that exactly cover those of the original delays, resulting in an LFR with frequency-dependent uncertainty bounds. Then, Pad & eacute;approximations, whose order is chosen to handle the trade-off between conservatism and complexity. A constructive way to derive minimal

关键词： branch-and-bound algorithms linear fractional representation probabilistic mu-analysis robustness analysis uncertain systems

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2019年第2期279卷 308-319页

作者： Chassein, Andre Goerigk, Marc Kurtz, Jannis Poss, Michael Deutsch Post DHL Grp Data Analyt Ctr Excellence Bonn Germany Univ Siegen Network & Data Sci Management Siegen Germany Rhein Westfal TH Aachen Dept Math Aachen Germany Univ Montpellier LIRMM CNRS Montpellier France

We consider robust combinatorial optimization problems where the decision maker can react to a scenario by choosing from a finite set of k solutions. This approach is appropriate for decision problems under uncertainty where the implementation of decisions requires preparing the ground. We focus on the case that the set of possible scenarios is described through a budgeted uncertainty set and provide three algorithms for the problem. The first algorithm solves heuristically the dualized problem, a non convex mixed-integer non-linear program (MINLP), via an alternating optimization approach. The second algorithm solves the MINLP exactly for k = 2 through a dedicated spatial branch-and-bound algorithm. The third approach enumerates k-tuples, relying on strong bounds to avoid a complete enumeration. We test our methods on shortest path instances that were used in the previous literature and on randomly generated knapsack instances, and find that our methods considerably outperform previous approaches. Many instances that were previously not solved within hours can now be solved within few minutes, often even faster. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Robust optimization k-adaptability Budgeted uncertainty branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimizing the Total Tardiness of a Game Project Considering the Overlap Effect

引用

IEEE ACCESS 2020年 8卷 216507-216518页

作者： Wang, Jen-Ya Chen, Meng-Wei Jea, Kuen-Fang Hungkuang Univ Dept Comp Sci & Informat Management Taichung 43302 Taiwan Natl Chung Hsing Univ Dept Comp Sci & Engn Taichung 40227 Taiwan

There has long been a custom that game development is not the mainstream of engineering and its tardiness brings little or even no harm to this industry. Nowadays, the pendulum of industrial development has swung to another side. A game project may involve hundreds of developers, thousands of jobs, and millions of costs. Situations would be worse if jobs overlap with others. Any delay of a large game project can cause a heavy penalty. Consequently, in this study, we propose two scheduling algorithms to reduce the total tardiness of a game project. If the problem size is small, a branch-and-bound algorithm is employed to provide the optimal schedules;otherwise a genetic algorithm is used to generate near-optimal schedules. The experimental results show that the proposed algorithms reduce the total tardiness significantly.

关键词： Games Task analysis Job shop scheduling Schedules Optimal scheduling Servers Scheduling algorithms Jog scheduling game industry optimization branch-and-bound algorithms overlap effect

来源：评论

学校读者我要写书评

暂无评论

On linear programming relaxations for solving polynomial programming problems

引用

COMPUTERS & OPERATIONS RESEARCH 2018年 99卷 67-77页

作者： Dalkiran, Evrim Ghalami, Laleh Wayne State Univ Ind & Syst Engn 4815 Fourth St Detroit MI 48202 USA

This paper studies linear programming (LP) relaxations for solving polynomial programming problems. A polynomial programming problem can be equivalently formulated as a quadratically constrained quadratic program (QCQP) by introducing new variables that represent nonlinear monomials and substituting them within the original formulation. Whereas Reformulation-Linearization Technique (RLT)-based LP relaxations constructed for the original formulation are tight, the relaxations generated using the equivalent lower degree formulations are smaller and require less computational effort to optimize in comparison to the effort the former requires. In this study, we analyze the strength and tractability of the standard RLT, the J-set, and recursive McCormick relaxations for polynomial programming problems, and identify the superior relaxation depending on the problem characteristics. Extensive computational results are provided to demonstrate the relative effectiveness of the standard RLT, J-set, and recursive McCormick algorithms using problems from the literature and randomly generated test instances. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Reformulation-Linearization Technique (RLT) J-set relaxation McCormick inequalities Polynomial programming problems Linear programming relaxations branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Exact approaches for the knapsack problem with setups

引用

COMPUTERS & OPERATIONS RESEARCH 2018年 90卷 208-220页

作者： Furini, Fabio Monaci, Michele Traversi, Emiliano PSL Res Univ Univ Paris Dauphine LAMSADE F-75016 Paris France Univ Bologna DEI I-40136 Bologna Italy Univ Paris 13 Lab Informat Paris Nord F-93430 Villetaneuse France

We consider a generalization of the knapsack problem in which items are partitioned into classes, each characterized by a fixed cost and capacity. We study three alternative Integer Linear Programming formulations. For each formulation, we design an efficient algorithm to compute the linear programming relaxation (one of which is based on Column Generation techniques). We theoretically compare the strength of the relaxations and derive specific results for a relevant case arising in benchmark instances from the literature. Finally, we embed the algorithms above into a unified implicit enumeration scheme which is run in parallel with an improved Dynamic Programming algorithm to effectively solve the problem to proven optimality. An extensive computational analysis shows that our new exact algorithm is capable of efficiently solving all the instances of the literature and turns out to be the best algorithm for instances with a low number of classes. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Knapsack problems Column generation Relaxations branch-and-bound algorithms Computational experiments

来源：评论

学校读者我要写书评

暂无评论

Recasting and optimizing intersection automation as a connected-and-automated-vehicle (CAV) scheduling problem: A sequential branch-and-bound search approach in phase-time-traffic hypernetwork

引用

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2017年 105卷 479-506页

作者： Li, Pengfei (Taylor) Zhou, Xuesong Mississippi State Univ Dept Civil & Environm Engn Mississippi State MS 39762 USA Arizona State Univ Sch Sustainable Engn & Built Environm Tempe AZ 85287 USA

It is a common vision that connected and automated vehicles (CAVs) will increasingly appear on the road in the near future and share roads with traditional vehicles. Through sharing real-time locations and receiving guidance from infrastructure, a CAV's arrival and request for green light at intersections can be approximately predicted along their routes. When many CAVs from multiple approaches at intersections place such requests, a central challenge is how to develop an intersection automation policy (IAP) to capture complex traffic dynamics and schedule resources (green lights) to serve both CAV requests (interpreted as request for green lights on a particular signal phase at time t) and traditional vehicles. To represent heterogeneous vehicle movements and dynamic signal timing plans, we first formulate the IAP optimization as a special case of machine scheduling problem using a mixed integer linear programming formulation. Then we develop a novel phase-time-traffic (PTR) hypernetwork model to represent heterogeneous traffic propagation under traffic signal operations. Since the IAP optimization;by nature, is a special sequential decision process, we also develop sequential branch-and-bound search algorithms over time to IAP optimization considering both CAVs and traditional vehicles in the PTR hypernetwork. As the critical part of the branch-and-bound search, special dominance and bounding rules are also developed to reduce the search space and find the exact optimum efficiently. Multiple numerical experiments are conducted to examine the performance of the proposed IAP optimization approach. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Intersection automation policy Traffic signal control Phase-time network branch-and-bound algorithms Automated vehicle Connected vehicle

来源：评论

学校读者我要写书评

暂无评论

branch-and-bound algorithms for scheduling in permutation flowshops to minimize the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted flowtime, weighted tardiness and weighted earliness of jobs

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2009年第7期60卷 991-1004页

作者： Madhushini, N. Rajendran, C. Deepa, Y. Indian Inst Technol Dept Management Studies Madras 600036 Tamil Nadu India

The problem of scheduling in permutation flowshops is considered in this paper with the objectives of minimizing the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted flowtime, weighted tardiness and weighted earliness of jobs, with each objective considered separately. Lower bounds on the given objective (corresponding to a node generated in the scheduling tree) are developed by solving an assignment problem. branch-and-bound algorithms are developed to obtain the best permutation sequence in each case. Our algorithm incorporates a job-based lower bound (integrated with machine-based bounds) with respect to the weighted flowtime/weighted tardiness/weighted flowtime and weighted tardiness, and a machine-based lower bound with respect to the weighted earliness of jobs. The proposed algorithms are evaluated by solving many randomly generated problems of different problem sizes. The results of an extensive computational investigation for various problem sizes are presented. In addition, one of the proposed branch-and-bound algorithms is compared with a related existing branch-and-bound algorithm. Journal of the Operational Research Society (2009) 60, 991-1004. doi:10.1057/***.2602642

关键词： flowshop scheduling assignment problem weighted flowtime weighted tardiness weighted earliness branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Graphics processing unit-accelerated bounding for branch-and-bound applied to a permutation problem using data access optimization

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2014年第16期26卷 2667-2683页

作者： Melab, N. Chakroun, I. Bendjoudi, A. Univ Lille 1 CNRS LIFL INRIA Lille Nord Europe F-59655 Villeneuve Dascq France CERIST Algiers 16030 Algeria

branch-and-bound (B&B) algorithms are attractive methods for solving to optimality combinatorial optimization problems using an implicit enumeration of a dynamically built tree-based search space. Nevertheless, they are time-consuming when dealing with large problem instances. Therefore, pruning tree nodes (subproblems) is traditionally used as a powerful mechanism to reduce the size of the explored search space. Pruning requires to perform the bounding operation, which consists of applying a lower bound function to the subproblems generated during the exploration process. Preliminary experiments performed on the Flow-Shop scheduling problem (FSP) have shown that the bounding operation consumes over 98% of the execution time of the B&B algorithm. In this paper, we investigate the use of graphics processing unit (GPU) computing as a major complementary way to speed up the search. We revisit the design and implementation of the parallel bounding model on GPU accelerators. The proposed approach enables data access optimization. Extensive experiments have been carried out on well-known FSP benchmarks using an Nvidia Tesla C2050 GPU card. Compared to a CPU-based single core execution using an Intel Core i7-970 processor without GPU, speedups higher than 100 times faster are achieved for large problem instances. At an equivalent peak performance, GPU-accelerated B&B is twice faster than its multi-core counterpart. Copyright (c) 2013 John Wiley & Sons, Ltd.

关键词： massively parallel computing GPU computing branch-and-bound algorithms lower bounding flow-shop scheduling

来源：评论

学校读者我要写书评

暂无评论

Efficiently Enumerating All Connected Induced Subgraphs of a Large Molecular Network

Efficiently Enumerating All Connected Induced Subgraphs of a...

引用

1st International Conference on algorithms for Computational Biology (AlCoB)

作者： Maxwell, Sean Chance, Mark R. Koyutuerk, Mehmet Case Western Reserve Univ Ctr Prote & Bioinformat Cleveland OH 44106 USA Case Western Reserve Univ Dept Elect Engn & Comp Sci Cleveland OH 44106 USA

ISBN: (纸本)9783319079530;9783319079523

In systems biology, the solution space for a broad range of problems is composed of sets of functionally associated biomolecules. Since connectivity in molecular interaction networks is an indicator of functional association, such sets can be identified from connected induced subgraphs of molecular interaction networks. Applications typically quantify the relevance (e. g., modularity, conservation, disease association) of connected subnetworks using an objective function and use a search algorithm to identify sets of subnetworks that maximize this objective function. Efficient enumeration of connected subgraphs of a large graph is therefore useful for these applications, and many existing search algorithms can be used for this purpose. However, there is a lack of non-heuristic algorithms that minimize the total number of subgraphs evaluated during the search for subgraphs that maximize the objective function. Here, we propose and evaluate an algorithm that reduces the computations necessary to enumerate subgraphs that maximize an objective function given a monotonically decreasing bounding function.

关键词： connected subgraph enumeration protein interaction networks branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Reducing thread divergence in a GPU-accelerated branch-and-bound algorithm

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2013年第8期25卷 1121-1136页

作者： Chakroun, I. Mezmaz, M. Melab, N. Bendjoudi, A. Univ Lille 1 CNRS LIFL INRIA Lille Nord Europe F-59655 Villeneuve Dascq France Univ Mons Math & Operat Res Dept MathRO B-7000 Mons Belgium Ctr Rech Informat Sci & Tech CERIST Algiers 16030 Algeria

In this paper, we address the design and implementation of graphical processing unit (GPU)-accelerated branch-and-bound algorithms (B&B) for solving flow-shop scheduling optimization problems (FSP). Such applications are CPU-time consuming and highly irregular. On the other hand, GPUs are massively multithreaded accelerators using the single instruction multiple data model at execution. A major issue that arises when executing on GPU, a B&B applied to FSP is thread or branch divergence. Such divergence is caused by the lower bound function of FSP that contains many irregular loops and conditional instructions. Our challenge is therefore to revisit the design and implementation of B&B applied to FSP dealing with thread divergence. Extensive experiments of the proposed approach have been carried out on well-known FSP benchmarks using an Nvidia Tesla (C2050 GPU card (http://***/docs/IO/43395/NV_DS_Tesla_C2050_C2070_jul10_***)). Compared with a CPU-based execution, accelerations up tox77.46 are achieved for large problem instances. Copyright (c) 2012 John Wiley & Sons, Ltd.

关键词： GPU computing branch-and-bound algorithms data parallelism thread divergence

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：