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

Rotation cycle schedulings for multi-item production systems

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2001年第2期135卷 361-372页

作者： Chan, GH Song, YY Natl Univ Singapore Dept Math Kent Ridge Digital Labs Singapore 119613 Singapore Natl Univ Singapore Dept Math Singapore 119260 Singapore

Consider the production planning and scheduling on a single machine with finite constant production rate over a planning horizon N. For single-item production problem, we have characterised the structure of the optimal solution when N approaches to infinity. This result suggests a near optimal solution when the planning horizon N is large. For multi-item production problem, we restrict our analysis on the Rotation Cycle policies. Under the assumptions of the policy, we convert the problem into a generalised travelling salesman problem and hence a branch and bound algorithm is proposed to solve the problem. For a given error bound of the solution, the algorithm can be further simplified to determine a near-optimal rotation cycle. (C) 2001 Published by Elsevier Science B.V.

关键词： branch and bound algorithm travelling salesman rotation cycle

来源：评论

学校读者我要写书评

暂无评论

Maximization of the ratio of two convex quadratic functions over a polytope

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2001年第1期20卷 43-60页

作者： Gotoh, JY Konno, H Univ Tsukuba Inst Policy & Planning Sci Tsukuba Ibaraki 305 Japan Chuo Univ Dept Ind & Syst Engn Tokyo 112 Japan

In this paper, we will develop an algorithm for solving a quadratic fractional programming problem which was recently introduced by Lo and MacKinlay to construct a maximal predictability portfolio, a new approach in portfolio analysis. The objective function of this problem is defined by the ratio of two convex quadratic functions, which is a typical global optimization problem with multiple local optima. We will show that a well-designed branch-and-bound algorithm using (i) Dinkelbach's parametric strategy, (ii) linear overestimating function and (iii) omega -subdivision strategy can solve problems of practical size in an efficient way. This algorithm is particularly efficient for Lo-MacKinlay's problem where the associated nonconvex quadratic programming problem has low rank nonconcave property.

关键词： fractional programming Dinkebach's approach branch and bound algorithm global optimization maximizing predictability portfolio

来源：评论

学校读者我要写书评

暂无评论

Iterative coloring extension of a maximum clique

引用

NAVAL RESEARCH LOGISTICS 2001年第6期48卷 518-550页

作者： Caramia, M Dell'Olmo, P Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy Univ Roma La Sapienza Dipartimento Stat Probabil & Stat Applicate I-00185 Rome Italy

In this paper we present an improved branch and bound algorithm for the vertex coloring problem. The idea is to try to extend the coloring of a maximum clique to its adjacent vertices. If this succeeds. its successive neighbors are considered;in case of failure (i.e., in the case the initial colors are not sufficient), working on the subgraph induced by the maximum clique and its neighborhood, the lower bound is improved by seeking for an optimal coloring of this subgraph by branch and bound. The process is repeated iteratively until the whole graph is examined. The iterative scheme exploits a further lower bound obtained by integrating a simple algorithm into the maximum clique search, and a new method to compute upper bounds on subgraphs. Furthermore, a new branching rule and a method for the selection of the initial maximum clique are presented. Extensive computational results and comparisons with existing exact coloring algorithms on random graphs and benchmarks are given. (C) 2001 John Wiley & Sons, Inc.

关键词： branch and bound algorithm combinatorial optimization exact coloring lower bound maximum clique

来源：评论

学校读者我要写书评

暂无评论

Concavity cuts for disjoint bilinear programming

引用

MATHEMATICAL PROGRAMMING 2001年第2期90卷 373-398页

作者： Alarie, S Audet, C Jaurnard, B Savard, G Ecole Polytech GRPR Montreal PQ H3C 3A7 Canada Ecole Polytech GERAD Montreal PQ H3C 3A7 Canada Ecole Polytech Dept Genie Elect & Genie Informat Montreal PQ H3C 3A7 Canada Ecole Polytech Dept Math & Genie Ind Montreal PQ H3C 3A7 Canada

We pursue the study of concavity cuts for the disjoint bilinear programming problem. This optimization problem has two equivalent symmetric linens maxmin reformulations, leading to two sets of concavity cuts. We first examine the depth of these cuts by considering the assumptions on the boundedness of the feasible regions of both maxmin and bilinear formulations. We next propose a branch and bound algorithm which make use of concavity cuts. We also present a procedure that eliminates degenerate solutions. Extensive computational experiences are reported. Sparse problems with up to 500 variables in each disjoint sets and 100 constraints, and dense problems with up to 60 variables again in each sets and 60 constraints are solved in reasonable computing times.

关键词： concavity cuts disjoint bilinear programming linear maxmin programming branch and bound algorithm global optimization

来源：评论

学校读者我要写书评

暂无评论

Portfolio optimization problem under concave transaction costs and minimal transaction unit constraints

引用

MATHEMATICAL PROGRAMMING 2001年第2期89卷 233-250页

作者： Konno, H Wijayanayake, A Dept Ind Engn & Management Tokyo 152 Japan Tokyo Inst Technol Ctr Res Adv Financial Technol Tokyo 152 Japan

We will propose a branch and bound algorithm for calculating a globally optimal solution of a portfolio construction/rebalancing problem under concave transaction costs and minimal transaction unit constraints. We will employ the absolute deviation of the rate of return of the portfolio as the measure of risk and solve linear programming subproblems by introducing (piecewise) linear underestimating function for concave transaction cost functions. It will be shown by a series of numerical experiments that the algorithm can solve the problem of practical size in an efficient manner.

关键词： portfolio optimization concave transaction cost rebalancing minimal transaction unit branch and bound algorithm global optimization

来源：评论

学校读者我要写书评

暂无评论

MINIMAL COST INDEX TRACKING UNDER NONLINEAR TRANSACTION COSTS AND MINIMAL TRANSACTION UNIT CONSTRAINTS

引用

International Journal of Theoretical and Applied Finance 2001年第6期4卷 939-957页

作者： HIROSHI KONNO ANNISTA WIJAYANAYAKE Center for Research in Advanced Financial Technology Tokyo Institute of Technology Japan Department of Industrial Engineering and Management Tokyo Institute of Technology Japan

Index tracking is a very common and popular approach in portfolio management. When there is neither (nonconvex) transaction costs nor minimal transaction unit constraints, the problem can be formulated as a convex least square problem, so that it can be solved by standard methods. However, when the transaction cost is nonconvex and not negligible, or if there is a minimal unit constraint on the amount of transaction, the problem becomes a nonconvex minimization problem with discrete variables. In this paper, we will propose a branch and bound algorithm for solving this class of problems and show that it can solve an index tracking problem of practical size in a reasonable amount of computation time.

关键词： Portfolio optimization index tracking concave transaction cost minimal transaction unit branch and bound algorithm mean-absolute deviation model

来源：评论

学校读者我要写书评

暂无评论

A Dynamic Single-Stage Multi-Item Inventory Control Model

引用

IFAC Proceedings Volumes 2001年第8期34卷 73-78页

作者： Mohamed-Aly Ould-Louly Alexandre Dolgui Industrial Systems Optimization Lab. University of Technology of Troyes 12 rue Marie Curie BP2060 - 10010 Troves cedex France Ph: + 33 (0)3 25 71 56 29 Fax: +33 (0)3 25 71 56 49

We study assembly systems with one type of finished products and several types of components. The lead times of components are random variables, and the customer demand of finished product is constant. We proposed a Markov chain that enables the determination of system performance measures, and we show how to exploit this model for optimization. Our aim is to minimize the average holding cost for the components while keeping a given service level for customer demands. In this paper we propose lower bounds and dominance properties of goal function. These results can be used in a branch and bound algorithm.

关键词： Supply planning Inventory control Markov chains Optimization branch and bound algorithm Lower bound Dominance properties

来源：评论

学校读者我要写书评

暂无评论

A branch and bound algorithm for solving mean-risk-skewness portfolio models

引用

OPTIMIZATION METHODS & SOFTWARE 1998年第2期10卷 297-317页

作者： Konno, H Suzuki, T Kobayashi, D Tokyo Inst Technol Dept Ind Engn & Management Meguro Ku Tokyo 1528552 Japan

This paper discusses an efficient algorithm for solving the mean-absolute deviation-skewness (MADS) portfolio optimization model in which the third order moment in addition to the first and second moment of the rate of return of the portfolio is taken into account. The MADS model can be considered either as an extension of the mean-absolute deviation (MAD) model or an approximation of the mean-variance-skewness (MVS) model which is a straightforward extension of the mean-variance (MV) model. Models which take account of the third moment play an important role when the rate of return of the assets are non-symmetrically distributed. We will propose an efficient branch and bound algorithm for solving a non-concave maximization problem and demonstrate that it can generate a globally optimal solution in an efficient manner.

关键词： absolute deviation skewness portfolio optimization global optimization problem branch and bound algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal capacitor placement using deterministic and genetic algorithms

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2000年第3期15卷 1041-1046页

作者： Delfanti, M Granelli, GP Marannino, P Montagna, M Univ Pavia Dipartimento Ingn Elettr I-27100 Pavia Italy

A procedure for solving the capacitor placement problem is presented. The objective is to determine the minimum investment required to satisfy suitable reactive constraints. Due to the discrete nature of reactive compensation devices, optimal capacitor placement leads to a nonlinear programming problem with mixed (discrete and continuous) variables, It is solved with an iterative algorithm based on successive linearizations of the original nonlinear model. The mixed integer linear programming problem to be solved at each iteration of the procedure is tackled by applying both a deterministic method (branch and bound) and genetic algorithm techniques, A hybrid procedure, aiming to exploit the best features of both algorithms is also considered. The proposed procedures are tested and compared with reference to a small CIGRE system and two actual networks derived from the Italian transmission and distribution system.

关键词： branch and bound algorithm genetic algorithms mixed integer programming VAR planning

来源：评论

学校读者我要写书评

暂无评论

Semantic Decomposition By Covering

Semantic Decomposition By Covering

引用

作者： Sripadham, Shankar B. Virginia Tech | University

This thesis describes the implementation of a covering algorithm for semantic decomposition of sentences of technical patents. This research complements the ASPIN project that has a long term goal of providing an automated system for digital system synthesis from patents. In order to develop a prototype of the system explained in a patent, a natural language processor (sentence-interpreter) is required. These systems typically attempt to interpret a sentence by syntactic analysis (parsing) followed by semantic analysis. Quite often, the technical narrative contains grammatical errors, incomplete sentences, anaphoric references and typological errors that can cause the grammatical parse to fail. In such situations, an alternate method that uses a repository of pre-compiled, simple sentences (called frames) to analyze the sentences of the patent can be a useful back up. By semantically decomposing the sentences of patents to a set of frames whose meanings are fully understood, the meaning of the patent sentences can be interpreted. This thesis deals with the semantic decomposition of sentences using a branch and bound covering algorithm. The algorithm is implemented in C++. A number of experiments were conducted to evaluate the performance of this algorithm. The covering algorithm uses a standard branch and bound algorithm to semantically decompose sentences. The algorithm is fast, flexible and can provide good (100 % coverage for some sentences) coverage results. The system covered 67.68 % of the sentence tokens using 3459 frames in the repository. 54.25% of the frames identified by the system in covers for sentences, were found to be semantically correct. The experiments suggest that the performance of the system can be improved by increasing the number of frames in the repository.

关键词： branch and bound algorithm Linguistic interpretation Covering Sentence interpretation Thesis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：