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

Linear optimization problem constrained by fuzzy max-min relation equations

INFORMATION SCIENCES 2013年 234卷 71-79页

作者： Chang, Cheung-Wen Shieh, Bih-Sheue Natl Univ Tainan Dept Appl Math Tainan 700 Taiwan

Fang and Li introduced the optimization model with a linear objective function and constrained by fuzzy max-min relation equations. They converted this problem into a 0-1 integer programming problem and solved it using the jump-tracking branch-and-bound method. Subsequently, Wu et al. improved this method by providing an upper bound on the optimal objective value and presented three rules for simplifying the computation of an optimal solution. This work presents new theoretical results concerning this optimization problem. They include an improved upper bound on the optimal objective value, improved rules for simplifying the problem and a rule for reducing the solution tree. Accordingly, an accelerated approach for finding the optimal objective value is presented, and represents an improvement on earlier approaches. Its potential applications are discussed. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Linear optimization branch-and-bound method Fuzzy relations Fuzzy relation equations Max-min composition

来源：评论

学校读者我要写书评

暂无评论

Speeding up Chinese character recognition in an automatic document reading system

引用

PATTERN RECOGNITION 1998年第11期31卷 1601-1612页

作者： Tseng, YH Kuo, CC Lee, HJ Natl Chiao Tung Univ Dept Comp Sci & Informat Engn Hsinchu 30050 Taiwan

In this paper, we present two techniques for speeding up character recognition. Our character recognition system, including the candidate-cluster selection and modified branch-and-bound detail-matching modules, is implemented using two statistical features: crossing-counts and contour-direction counts. In the training stage, we divide characters into different clusters by using reference characters. To have a very high recognition rate, the candidate-cluster selection module selects the top 60 clusters with minimal distances from among 300 predefined clusters. To further speed-up the recognition speed, we use a modified branch-and-bound algorithm in the detail-matching module. In the automatic document reading system, characters and punctuation marks are first extracted from printed document images and sorted according to their positions and the document orientation. The system then recognizes all printed Chinese characters between pairs of punctuation marks. The results are then spoken aloud by a speech-synthesis system. The character recognition system and the text-to-speech synthesis system are integrated in the Windows-based document reading system, which provides a user-friendly environment. (C) 1998 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.

关键词： crossing-count features contour-direction features candidate-cluster selection branch-and-bound method text-to-speech technique automatic document reading system

来源：评论

学校读者我要写书评

暂无评论

A deterministic approach to global box-constrained optimization

引用

OPTIMIZATION LETTERS 2013年第4期7卷 819-829页

作者： Evtushenko, Yury Posypkin, Mikhail Russian Acad Sci Ctr Comp Moscow Russia Russian Acad Sci Inst Syst Anal Moscow Russia

A deterministic global optimization algorithm for box-constrained problems is presented. The proposed approach is based on well-known non-uniform space covering technique. In the paper this approach is further elaborated. We propose a new techniques that enables a significant reduction of the search space by means of dropping parts of processed boxes. Also a new quadratic underestimation for the objective function based on hessian eigenvalues bounds is presented. It is shown how this underestimation can be improved by exploiting the first-order optimality conditions. In the experimental section we compare the proposed approach with existing methods and programming tools. Numerical tests indicate that the proposed algorithm is highly competitive with considered methods.

关键词： Box-constrained optimization Deterministic optimization branch-and-bound method Lipschitzian optimization

来源：评论

学校读者我要写书评

暂无评论

A mathematical programming approach to the construction of BIBDs

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2011年第5期88卷 1067-1082页

作者： Yokoya, Daisuke Yamada, Takeo Natl Def Acad Dept Comp Sci Kanagawa 2398686 Japan

A balanced incomplete block design (BIBD) is instrumental in design of experiments. This is usually constructed by algebraic methods such as finite algebra or difference sets. However, in algebraic approaches, no unified method exists, and each BIBD has been constructed in some ad hoc ways. On the other hand, computer-based methods apply the same algorithm to all BIBDs;hence, these are unified approaches. Although various meta-heuristic algorithms have been tried, the success of these methods has been rather limited. This article presents an alternative approach to this problem that formulates the problem as a nonlinear mixed integer programming problem. We develop a branch-and-bound algorithm to solve this, and a tabu search algorithm to overcome some weakness in the former algorithm. We compare the performance of these algorithms against some previously developed algorithms, and demonstrate that our algorithms are competitive to these methods.

关键词： BIBD MIP problem branch-and-bound method tabu search

来源：评论

学校读者我要写书评

暂无评论

Single machine scheduling using dominance relation to minimize earliness subject to ready and due times

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 1996年第1-2期44卷 35-43页

作者： Asano, M Ohta, H Department of Industrial Engineering College of Engineering University of Osaka Prefecture Sakai Osaka 593 Japan

This paper considers a single machine scheduling problem with the constraints of prespecified ready and due times and the assumption of sequence-dependent setup times. That is, every job is available for processing on the ready time of each job and cannot be processed before the time. Also, every job must be completed before or just on the due time of each job, and no tardy jobs are allowed. This paper proposes an optimization algorithm using dominance relation for the scheduling problem based on the branch-and-bound method to effectively determine the optimum solution so as to minimize the total earliness. In the proposed algorithm, the model size at each node can be reduced by determining the dominance relation to perform branching operation. Furthermore, the strong lower bound is derived by determining the total minimum overlapping time for all unassigned jobs. Although the computational time through the proposed algorithm increases exponentially to solve problems by increasing the number of jobs, the branching operation and strong lower bound using the dominance relation will enhance the computational efficiency. The effectiveness of proposed algorithm will also be reported by simulation results.

关键词： single machine scheduling minimizing earliness ready and due times branch-and-bound method dominance relation just-in-time production

来源：评论

学校读者我要写书评

暂无评论

Algorithm for Solving Optimal Arrangement Problem in Connected-(r, s)-out-of-(m, n):F Lattice System

引用

IEEE TRANSACTIONS ON RELIABILITY 2020年第2期69卷 497-509页

作者： Nakamura, Taishin Yamamoto, Hisashi Tokyo Metropolitan Univ Grad Sch Syst Design Tokyo 1910065 Japan

This paper considers the optimal arrangement problem in a connected-(r, s)-out-of-(m, n):F lattice system. This problem aims to find a component arrangement to maximize system reliability under the assumption that the component reliabilities are given. Although existing studies developed a few algorithms for finding the optimal arrangement of connected-(r, s)-out-of(m, n):F lattice systems, these existing algorithms can only find the optimal arrangement in the special cases. In this paper, we develop an improved algorithm for efficiently finding the optimal arrangement of general connected-(r, s)-out-of-(m, n):F lattice systems. It is based on the branch-and-bound method. First, we derive three conditions for pruning a branch based on the existing conditions for the optimal arrangement. The conditions can reduce the number of candidates for the optimal arrangement. Moreover, we improve the algorithm by incorporating the derived conditions as given by Omura et al. In the improved algorithm, we compute the system reliability efficiently by memorizing the specific values and then utilizing them. The result of the numerical experiment shows the proposed algorithm is more efficient than the algorithm proposed by Omura et al. in terms of the computation time. The result shows that the proposed algorithm can find the optimal arrangement whereas the algorithm proposed by Nakamura et al. cannot find. The optimal arrangement and its system reliability, which the proposed algorithm provides can also be used to evaluate the quality of solutions obtained by (meta) heuristic algorithms.

关键词： branch-and-bound method connected-(r, s)-out-of-(m, n):F lattice system optimal arrangement problem system reliability

来源：评论

学校读者我要写书评

暂无评论

Online model predictive control for max-plus linear systems with selective parameters

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2004年第11期E87A卷 2944-2949页

作者： Goto, H Masuda, S Japan Res Inst Ltd Tokyo 1020082 Japan Tokyo Metropolitan Inst Technol Hino Tokyo 1910065 Japan

We develop an algorithm for a controller design method for Max-Plus Linear (MPL) systems with selective parameters. Since the conventional algorithm we proposed requires high computational load when the prediction horizon is large, two methods for reducing the calculation time are proposed. One is based upon the branch-and-bound method, and the other is to reuse the optimal solution. The effectiveness of these two methods is confirmed through numerical simulation.

关键词： max-plus linear system selective parameter model predictive control branch-and-bound method

来源：评论

学校读者我要写书评

暂无评论

Grasping optimization using a required external force set

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2007年第1期4卷 52-66页

作者： Watanabe, Tetsuyou Yoshikawa, Tsuneo Yamaguchi Univ Dept Engn Mech Yamaguchi 7558611 Japan Ritsumeikan Univ Coll Informat Sci & Engn Ritsumeikan 5258577 Japan

In this paper, we investigate optimal grasp points on an arbitrary-shaped grasped object using a required external force set. The required external force set is given based on a task, and consists of the external forces and moments, which must be balanced by virtue of contact forces applied by a robotic hand. When the origin is in the interior of the set, a force-closure grasp is required. When the dimension of the set is one, an equilibrium grasp is required. Therefore, we can investigate whatever the desired grasp is, such as when the desired grasp is a force closure and equilibrium grasps. Also, we only have to consider the forces contained in a given required external force set, not the whole set of possible resulting forces. Furthermore, we can avoid the frame-invariant problem (the criterion value changes with the change of the task (object) coordinate frame). We consider an optimization problem from the viewpoint of decreasing the magnitudes of the contact forces needed to balance any external force and moment contained in a given required external force set. In order to solve the problem, we present an algorithm based on a branch-and-bound method. We also present some numerical examples to show the validity of our approach. Note to Practitioners-This paper is concerned with grasping an object by a robotic hand. This article address how to grasp the object, namely, how to position every finger on the object. Recently, robots are desired to be used in housekeeping and in caring for elderly people. For this purpose, robot (multifingered) hands are equipped with the robots as general-purpose end effectors. The robot hands are required to automatically move to accomplish such tasks. In this case, the most fundamental issue for robot hands is to grasp the object. At home, there are many various-shaped objects. Consider the case where the robot (hand) is commanded to perform a certain task, such as putting the object into a box. In this case, the robot (hand) must

关键词： branch-and-bound method grasping optimization required external force set

来源：评论

学校读者我要写书评

暂无评论

Globally Optimal Selection of Ground Stations in Satellite Systems With Site Diversity

引用

IEEE WIRELESS COMMUNICATIONS LETTERS 2020年第7期9卷 1101-1104页

作者： Efrem, Christos N. Panagopoulos, Athanasios D. Natl Tech Univ Athens Sch Elect & Comp Engn Athens 15780 Greece

The availability of satellite communication systems is extremely limited by atmospheric impairments, such as rain (for radio frequencies) and cloud coverage (for optical frequencies). A solution to this problem is the site diversity technique, where a network of geographically distributed ground stations (GSs) can ensure, with high probability, that at least one GS is available for connection to the satellite at each time period. However, the installation of redundant GSs induces unnecessary additional costs for the network operator. In this context, we study an optimization problem that minimizes the number of required GSs, subject to availability constraints. First, the problem is transformed into a binary-integer-linear-programming (BILP) problem, which is proven to be NP-hard. Subsequently, we design a branch-and-bound (B&B) algorithm, with global-optimization guarantee, based on the linear-programming (LP) relaxation and a greedy method as well. Finally, numerical results show that the proposed algorithm significantly outperforms state-of-the-art methods, and has low complexity in the average case.

关键词： Complexity theory Satellite broadcasting Optical fiber networks Optimized production technology Probability Satellites Satellite communications site diversity ground stations selection cardinality minimization combinatorial optimization binary integer linear programming NP-hardness linear-programming relaxation branch-and-bound method

来源：评论

学校读者我要写书评

暂无评论

Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs

引用

DISCRETE APPLIED MATHEMATICS 2007年第16期155卷 2093-2110页

作者： Mak, Vicky Boland, Natashia Deakin Univ Sch Informat Technol & Engn Burwood Vic 3125 Australia Univ Melbourne Dept Math & Stat Melbourne Vic 3010 Australia

The asymmetric travelling salesman problem with replenishment arcs (RATSP), arising from work related to aircraft routing, is a generalisation of the well-known ATSP. In this paper, we introduce a polynomial size mixed-integer linear programming (MILP) formulation for the RATSP, and improve an existing exponential size ILP formulation of Zhu [The aircraft rotation problem, Ph.D. Thesis, Georgia Institute of Technology, Atlanta, 19941 by proposing two classes of stronger cuts. We present results that under certain conditions, these two classes of stronger cuts are facet-defining for the RATS polytope, and that ATSP facets can be lifted, to give RATSP facets. We implement our polyhedral findings and develop a Lagrangean relaxation (LR)-based branch-and-bound (BNB) algorithm for the RATSP, and compare this method with solving the polynomial size formulation using ILOG Cplex 9.0, using both randomly generated problems and aircraft routing problems. Finally we compare our methods with the existing method of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408-427]. It turns out that both of our methods are much faster than that of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408-427], and that the LR-based BNB method is more efficient for problems that resemble the aircraft rotation problems. (C) 2007 Elsevier B.V. All rights reserved.

关键词： combinatorial optimisation travelling salesman polyhedral analysis lagrangean relaxation branch-and-bound method

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：