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

An implementation of linear and nonlinear multicommodity network flows

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1996年第1期92卷 37-53页

作者： Castro, J Nabona, N UNIV POLITECN CATALUNYA STAT & OPERAT RES DEPTPAU GARGALLO 5E-08071 BARCELONASPAIN

This work presents a new code for solving the multicommodity network flow problem with a linear or nonlinear objective function considering additional linear side constraints that link arcs of the same or different commodities. For the multicommodity network flow problem through primal partitioning the code implements a specialization of Murtagh and Saunders' strategy of dividing the set of variables into basic, nonbasic and superbasic. Several tests are reported, using random problems obtained from different network generators and real problems arising from the fields of long and short-term hydrothermal scheduling of electricity generation and traffic assignment, with sizes of up to 150 000 variables and 45 000 constraints. The performance of the code developed is compared to that of alternative methodologies for solving the same problems: a general purpose linear and nonlinear constrained optimization code, a specialised linear multicommodity network flow code and a primal-dual interior point coda.

关键词： linear programming multicommodity network flows network programming nonlinear programming primal partitioning

来源：评论

学校读者我要写书评

暂无评论

TOPOLOGICAL DESIGN OF A CENTRALIZED COMMUNICATION-network WITH UNRELIABLE LINKS AND NODE OUTAGE COSTS

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1994年第2期77卷 344-356页

作者： DUTTA, A KAWATRA, R MANKATO STATE UNIV COLL BUSINESSPOB 8400MANKATOMN 56002 GEORGE MASON UNIV DEPT DECIS SCI & MISFAIRFAXVA 22030

In this paper, we present a mathematical formulation of a terminal layout problem in the design of a centralized communication network with unreliable links and node outage costs. The node outage cost associated with a terminal node is a cost incurred by the network user whenever that terminal node is unable to communicate with the central node due to failure of a link. We suggest a two-phase heuristic with a time complexity of O(N3) to solve the problem. We also present a Lagrangean relaxation method to find the lower bound of the objective function value. The lower bound given by the Lagrangean relaxation method is used to estimate the quality of the solution given by the two-phase heuristic. Experimental results over a wide range of problem structures show that the average solution given by the two-phase heuristic is within 10% of the optimal objective function value.

关键词： COMPUTERS COMMUNICATIONS network programming

来源：评论

学校读者我要写书评

暂无评论

A MATHEMATICAL-MODEL FOR THE FIXED-TIME TRAFFIC CONTROL PROBLEM

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1989年第2期42卷 152-165页

作者： SERAFINI, P UKOVICH, W UNIV TRIESTE DIPARTIMENTO ELETTROTECN ELETTRON & INFORMATI-34127 TRIESTEITALY

The paper deals with the fixed-time traffic control problem, which consists of finding a periodic schedule for the signals controlling the vehicular traffic in a system of intersections. A traffic model is used which allows for constraints on green durations, conflicts and coordinations. The resulting mathematical model is formulated as an extension of the feasible differential problem of network flow theory over a special graph associated with the intersection system. The fixed-time traffic control problem is proved to be NP-complete in general. A specialized algorithm is proposed for its solution; moreover, an alternative solution method based on mixed-integer linear programming is given. Finally, a real example is modelled and solved.

关键词： network programming Road transportation scheduling traffic control

来源：评论

学校读者我要写书评

暂无评论

Implementing a Distributed Mobile Calculus Using the IMC Framework

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2007年第1期181卷 63-79页

作者： Bettini, Lorenzo De Nicola, Rocco Falassi, Daniele Loreti, Michele Univ Firenze Dipartimento Sistemi & Informat Florence Italy

In the last decade, many calculi for modelling distributed mobile code have been proposed. To assess their merits and encourage use, implementations of the calculi have often been proposed. These implementations usually consist of a limited part dealing with mechanisms that are specific of the proposed calculus and of a significantly larger part handling recurrent mechanisms that are common to many calculi. Nevertheless, also the "classic" parts are often re-implemented from scratch. In this paper we show how to implement a well established representative of the family of mobile calculi, the distributed pi-calculus, by using a Java middleware (called IMC - Implementing Mobile Calculi) where recurrent mechanisms of distributed and mobile systems are already implemented. By means of the case study, we illustrate a methodology to accelerate the development of prototype implementations while concentrating only on the features that are specific of the calculus under consideration and relying on the common framework for all the recurrent mechanisms like network connections, code mobility, name handling, etc.

关键词： Code Mobility Language Implementation network programming

来源：评论

学校读者我要写书评

暂无评论

A 2-PHASE SHORTEST-PATH ALGORITHM FOR networkS WITH NODE COORDINATES

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1995年第2期87卷 368-374页

作者： LYSGAARD, J AARHUS SCH BUSINESS DEPT MANAGEMENT SCIFUGLESANGS ALLE 4DK-8210 AARHUS VDENMARK

This paper presents a new algorithm for finding the shortest path from a source to a single sink in a network, in which the location in the plane of each node is known. The algorithm consists of two phases. In the first phase a heuristic solution to the shortest path problem is found. In the second phase the upper bound provided by the heuristic solution is utilized in a modification of a standard shortest path algorithm. Estimates based on computational tests show that on average the computation time of the presented algorithm is on the order of 40-60% of the computation time required if the information on node locations is not utilized.

关键词： OPTIMIZATION HEURISTICS network programming

来源：评论

学校读者我要写书评

暂无评论

Feedback and Time are Essential for the Optimal Control of Computing Systems

引用

IFAC-PapersOnLine 2015年第23期48卷 380-387页

作者： Kerrigan, Eric C. Imperial College London United Kingdom

The performance, reliability, cost, size and energy usage of computing systems can be improved by one or more orders of magnitude by the systematic use of modern control and optimization methods. Computing systems rely on the use of feedback algorithms to schedule tasks, data and resources, but the models that are used to design these algorithms are validated using open-loop metrics. By using closed-loop metrics instead, such as the gap metric developed in the control community, it should be possible to develop improved scheduling algorithms and computing systems that have not been over-engineered. Furthermore, scheduling problems are most naturally formulated as constraint satisfaction or mathematical optimization problems, but these are seldom implemented using state of the art numerical methods, nor do they explicitly take into account the fact that the scheduling problem itself takes time to solve. This paper makes the case that recent results in real-time model predictive control, where optimization problems are solved in order to control a process that evolves in time, are likely to form the basis of scheduling algorithms of the future. We therefore outline some of the research problems and opportunities that could arise by explicitly considering feedback and time when designing optimal scheduling algorithms for computing systems. © 2015, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.

关键词： Distributed computer systems Closed loop control systems Constraint satisfaction problems Feedback Interactive computer systems Model predictive control Numerical methods Optimization Real time systems Scheduling Scheduling algorithms Sensor networks Telecommunication networks Computing system Constraint Satisfaction Feedback algorithms Mathematical optimization problems network programming Optimal controls Optimal scheduling algorithm Optimization problems

来源：评论

学校读者我要写书评

暂无评论

GENERALIZED DYNAMIC-programming FOR MULTICRITERIA OPTIMIZATION

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1990年第1期44卷 95-104页

作者： CARRAWAY, RL MORIN, TL MOSKOWITZ, H PURDUE UNIV SCH IND ENGNW LAFAYETTEIN 47907 PURDUE UNIV KRANNERT GRAD SCH MANAGEMENTW LAFAYETTEIN 47907

Applications of dynamic programming (DP) to multicriteria sequential decision problems involving the optimization of a multicriteria preference function have been rare. This is due to the ease with which DP's monotonicity assumption can be violated in such situations. Generalized DP avoids the potential pitfalls created by this absence of monotonicity, thereby guaranteeing optimality. The methodology is applied to a prototypical multicriteria DP problem, namely a multicriteria version of the shortest path problem. [ABSTRACT FROM AUTHOR]

关键词： Dynamic programming multiple criteria programming network programming

来源：评论

学校读者我要写书评

暂无评论

Time-varying universal maximum flow problems

引用

MATHEMATICAL AND COMPUTER MODELLING 2001年第4-5期33卷 407-430页

作者： Cai, X Sha, D Wong, CK Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

We consider a time-varying network without parallel arcs and loops, where a flow must take a certain time to traverse an are. The transit time on an are and the capacity of an are are all time-varying parameters, which depend on the departure time to traverse the are. To depart at the best time, a flow can wait at the beginning vertex of an are, which is however limited by a time-varying vertex capacity. All those parameters, namely, the transit time, the are capacity, and the vertex capacity, are discrete functions of time t. The problem is to find an optimal solution to send the maximum flow from the source vertex to the sink vertex, within a given time T. Moreover, we address the so-called universal maximum flow problem, which is to find a solution that remains optimal when the time limit T is truncated to any t less than or equal to T. We consider three variants of the problem, with waiting at a vertex being arbitrarily allowed, strictly prohibited, and bounded, respectively. Relevant algorithms are proposed, which can find optimal solutions in pseudopolynomial time. (C) 2001 Elsevier Science Ltd. All rights reserved.

关键词： time-varying networks network programming universal maximum flow algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

A specialized interior-point algorithm for multicommodity network flows

引用

SIAM JOURNAL ON OPTIMIZATION 2000年第3期10卷 852-877页

作者： Castro, J Univ Politecn Cataluna Stat & Operat Res Dept E-08028 Barcelona Spain

Despite the efficiency shown by interior-point methods in large-scale linear programming, they usually perform poorly when applied to multicommodity ow problems. The new specialized interior-point algorithm presented here overcomes this drawback. This specialization uses both a preconditioned conjugate gradient solver and a sparse Cholesky factorization to solve a linear system of equations at each iteration of the algorithm. The ad hoc preconditioner developed by exploiting the structure of the problem is instrumental in ensuring the efficiency of the method. An implementation of the algorithm is compared to state-of-the-art packages for multicommodity flows. The computational experiments were carried out using an extensive set of test problems, with sizes of up to 700,000 variables and 150,000 constraints. The results show the effectiveness of the algorithm.

关键词： interior-point methods linear programming multicommodity flows network programming

来源：评论

学校读者我要写书评

暂无评论

A NOTE ON THE M-CENTER PROBLEM WITH RECTILINEAR DISTANCES

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1988年第1期35卷 118-123页

作者： ANEJA, YP CHANDRASEKARAN, R NAIR, KPK UNIV TEXAS DALLASTX 75230 UNIV NEW BRUNSWICK FREDERICTON E3B 5A3NBCANADA

Given n demand points on a plane, the problem we consider is to locate a given number, m, of facilities on the plane so that the maximum of the set of rectilinear distances of each demand point to its nearest facility is minimized. This problem is known as the m-center problem on the plane. A related problem seeks to determine, for a given r, the minimum number of facilities and their locations so as to ensure that every point is within r units of rectilinear distance from its nearest facility. We formulate the latter problem as a problem of covering nodes by cliques of an intersection graph. Certain bounds are established on the size of the problem. An efficient algorithm is provided to generate this set-covering problem. Computational results with this approach are summarized. [ABSTRACT FROM AUTHOR]

关键词： graphs integer programming Location network programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：