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

DISCRETE APPLIED MATHEMATICS 2019年 259卷 1-18页

作者： Araoz, Julian Fernandez, Elena Rueda, Salvador Univ Politecn Cataluna Dept Stat & Operat Res BcnTech Barcelona Spain Barcelona Grad Sch Math BGSMath Barcelona Spain

This paper addresses combined location/routing problems defined on trees, where not all vertices have to be necessarily visited. A mathematical programming formulation is presented, which has the integrality property. The formulation models a directed forest where each connected component hosts at least one open facility, which becomes the root of the component. The problems considered can also be optimally solved with ad-hoc solution algorithms. Greedy type optimal algorithms are presented for the cases when all vertices have to be visited and facilities have no set-up costs. Facilities setup costs can be handled with low-order interchanges, whose optimality check is a restatement of the complementary slackness conditions of the proposed formulation. The general problems where not all vertices have to be necessarily visited can also be optimally solved with low-order optimal algorithms based on recursions. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Location Routing Trees mathematical programming formulation Totally unimodular Optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Formulating and solving a radio astronomy antenna connection problem as a generalized cable-trench problem: an empirical study

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2017年第5期24卷 943-957页

作者： Zyma, Kenneth Girard, Julien N. Landquist, Eric Schaper, Gregory Vasko, Francis J. Kutztown State Univ Dept Comp Sci & Informat Technol Kutztown PA 19530 USA CEA Saclay AIM Paris France Univ Paris Diderot UPMC CNRS LESIAObserv Paris Paris France Kutztown State Univ Dept Math Kutztown PA 19530 USA

The low-frequency array, LOFAR, is the world's largest connected low-frequency (LF) radio telescope, combining antenna arrays from across Western Europe into a single telescope. A major extension of an existing LOFAR component in Nanc, ay, France, is currently being developed. The prototype design for this extension consists of a network of 96 LF radio telescope antenna arrays distributed across a 400 x 450 m area. A significant portion of the project's cost involves connecting each antenna array directly to a central control facility via a buried coaxial cable. In his 2013 doctoral dissertation, Girard proposed a cabling layout with the goal of minimizing the total cost to dig the trenches and lay the cables, by modeling the problem as a cable-trench problem (CTP). In this paper, we will discuss Girard's approach and then formulate the problem as a generalized CTP (GCTP) in order to handle physical obstacles more efficiently. To improve upon Girard's solution, we will first apply variations of Prim's algorithm to analyze a number of different GCTPs, based on a variety of cost parameters. Next, we will show that the mixed-integer linear programming formulation of the GCTP finds even better cable and trench layouts using CPLEX. Finally, we will use a new multicommodity flow formulation of the GCTP to find provably optimal solutions using CPLEX. This work has implications beyond the installation in development in Nanc, ay, as any future component of LOFAR can apply the techniques discussed in this paper to significantly reduce construction costs.

关键词： radio astronomy applications cable-trench problem generalized cable-trench problem mathematical programming formulation

来源：评论

学校读者我要写书评

暂无评论

A simple and efficient strategy for solving very large-scale generalized cable-trench problems

引用

NETWORKS 2016年第3期67卷 199-208页

作者： Vasko, Francis J. Landquist, Eric Kresge, Gregory Tal, Adam Jiang, Yifeng Papademetris, Xenophon Kutztown State Univ Dept Math Kutztown PA 19530 USA Kutztown State Univ Dept Comp Sci Kutztown PA 19530 USA Yale Univ Dept Diagnost Radiol Sch Med 310 Cedar StPOB 208042 New Haven CT 06520 USA

Vasko et al., Comput Oper Res 29 (2002), 441-458 defined the cable-trench problem (CTP) as a combination of the Shortest Path and Minimum Spanning Tree Problems. Specifically, let G=(V,E) be a connected weighted grapph with specified vertex v1V (referred to as the root), length l(e)0 for each e E, and positive parameters and. The CTP is the problem of finding a spanning tree T of G such that l(T)+l(T) is minimized, where l (T) is the total length of the spanning tree T and l (T) is the total path length in T from v 1 to all other vertices of V. Recently, Jiang et al., Proceedings of MICCAI 6893 (2011), 528-536 modeled the vascular network connectivity problem in medical image analysis as an extraordinarily large-scale application of the generalized cable-trench problem (GCTP). They proposed an efficient solution based on a modification of Prim's algorithm (MOD_PRIM), but did not elaborate on it. In this article, we formally define the GCTP, describe MOD_PRIM in detail, and describe two linearly parallelizable metaheuristics which significantly improve the performance of MOD_PRIM. These metaheuristics are capable of finding near-optimal solutions of very large GCTPs in quadratic time in V. We also give empirical results for graphs with up to 25,001 vertices. (c) 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(3), 199-208 2016

关键词： cable-trench problem generalized cable-trench problem vascular image analysis mathematical programming formulation shortest path tree minimum spanning tree bicriteria optimization

来源：评论

学校读者我要写书评

暂无评论

Modeling Mode and Route Similarities in Network Equilibrium Problem with Go-Green Modes

引用

NETWORKS & SPATIAL ECONOMICS 2016年第1期16卷 33-60页

作者： Kitthamkesorn, Songyot Chen, Anthony Xu, Xiangdong Ryu, Seungkyu Utah State Univ Dept Civil & Environm Engn Logan UT 84322 USA Hong Kong Univ Sci & Technol Dept Civil & Environm Engn Hong Kong Hong Kong Peoples R China

Environmental sustainability is a common requirement on the development of various real-world systems, especially on road transportation systems. Motorized vehicles generate a large amount of harmful emissions, which have adverse effects to the environment and human health. Environmental sustainability requires more promotions of 'go-green' transportation modes such as public transit and bicycle to realize the increasing travel demands while keeping the environmental expenses low. In this paper, we make use of recent advances in discrete choice modeling to develop equivalent mathematical programming formulations for the combined modal split and traffic assignment (CMSTA) problem that explicitly considers mode and route similarities under congested networks. Specifically, a nested logit model is adopted to model the modal split problem by accounting for mode similarity among the available modes, and a cross-nested logit model is used to account for route overlapping in the traffic assignment problem. This new CMSTA model has the potential to enhance the behavioral modeling of travelers' mode shift between private motorized mode and 'go-green' modes as well as their mode-specific route choices, and to assist in quantitatively evaluating the effectiveness of different 'go-green' promotion policies.

关键词： Nested logit Cross-nested logit mathematical programming formulation Combined modal split and traffic assignment problem

来源：评论

学校读者我要写书评

暂无评论

A general unconstrained optimization formulation for the combined distribution and assignment problem

引用

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2014年 59卷 137-160页

作者： Yao, Jia Chen, Anthony Ryu, Seungkyu Shi, Feng Utah State Univ Dept Civil & Environm Engn Logan UT 84322 USA Cent South Univ Sch Traff & Transportat Engn Changsha 410075 Hunan Peoples R China Tongji Univ Key Lab Rd & Traff Engn Shanghai 201804 Peoples R China

This paper proposes an alternate formulation for the combined distribution and assignment (CDA) problem, which seeks to determine consistent level-of-service and flow values of the trip distribution and traffic assignment steps. The CDA problem is modeled as a hierarchical travel choice problem based on random utility theory, which forms the basis for constructing as a general unconstrained optimization formulation. It has the flexibility to handle general probabilistic distributions (not just the Gumbel distribution) in a hierarchical travel choice structure. Qualitative properties of the general unconstrained CDA formulation are rigorously proved to ensure the equivalence and uniqueness of the solution. Particularly, the model is analyzed for two logit CDA models where the choice probability can be expressed in a closed form. The first logit CDA model with the independently and identically distributed (IID) Gumbel distribution is shown to be equivalent to several well-known existing CDA models. The second logit CDA model handles the independence assumption by accounting for the unobserved similarities among destinations in the destination choice level using a spatially correlated logit model and the route overlapping in the route choice level using the path size logit model. A descent direction algorithm with the self-regulated averaging (SRA) scheme is also developed for solving the unconstrained optimization formulation of two logit CDA models. Numerical experiments are conducted to demonstrate the features of the proposed general unconstrained CDA formulations and the computational performance of the descent SRA algorithm. The results reveal that route overlapping, destination similarity, congestion, and distribution errors can have a significant influence on the network equilibrium flow allocations. Published by Elsevier Ltd.

关键词： Combined travel demand model Combined distribution and assignment model Logit Extended logit mathematical programming formulation

来源：评论

学校读者我要写书评

暂无评论

Mixed-Integer Linear programming formulations for the Software Clustering Problem

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2013年第1期55卷 113-135页

作者： Koehler, Viviane Fampa, Marcia Araujo, Olinto Univ Fed Rio de Janeiro COPPE BR-21945970 Rio De Janeiro Brazil Univ Fed Santa Maria CTISM BR-97119900 Santa Maria RS Brazil

The clustering problem has an important application in software engineering, which usually deals with large software systems with complex structures. To facilitate the work of software maintainers, components of the system are divided into groups in such a way that the groups formed contain highly-interdependent modules and the independent modules are placed in different groups. The measure used to analyze the quality of the system partition is called Modularization Quality (MQ). Designers represent the software system as a graph where modules are represented by nodes and relationships between modules are represented by edges. This graph is referred in the literature as Module Dependency Graph (MDG). The Software Clustering Problem (SCP) consists in finding the partition of the MDG that maximizes the MQ. In this paper we present three new mathematical programming formulations for the SCP. Firstly, we formulate the SCP as a sum of linear fractional functions problem and then we apply two different linearization procedures to reformulate the problem as Mixed-Integer Linear programming (MILP) problems. We discuss a preprocessing technique that reduces the size of the original problem and develop valid inequalities that have been shown to be very effective in tightening the formulations. We present numerical results that compare the formulations proposed and compare our results with the solutions obtained by the exhaustive algorithm supported by the freely available Bunch clustering tool, for benchmark problems.

关键词： mathematical programming formulation Automatic clustering Module dependency graph MILP formulation Software clustering problem

来源：评论

学校读者我要写书评

暂无评论

Estimation of Burger model parameters using inverse formulation

引用

INTERNATIONAL JOURNAL OF GEOTECHNICAL ENGINEERING 2012年第3期6卷 261-274页

作者： Dey, Arindam Basudhar, Prabir Kr. Indian Inst Technol Guwahati Dept Civil Engn Gauhati 781039 Assam India Indian Inst Technol Kanpur Dept Civil Engn Kanpur 208016 Uttar Pradesh India

This paper reports the development of a generalized inverse analysis formulation for the parameter estimation of four-parameter Burger model. The analysis is carried out by defining the problem as a mathematical programming formulation in terms of identification of the design vector, the objective function and the design constraints. Thereafter, the formulated constrained nonlinear multivariable problem is solved with the aid of fmincon: an in-built constrained optimization solver module available in MatLab. In order to gain experience, a synthetic case-study is considered wherein key issues such as the determination and setting up of variable bounds, global optimality of the solution and minimum number of data-points required for prediction of parameters is addressed. The results reveal that the developed technique is quite efficient in predicting the model parameters. The best result is obtained when the design variables are maintaining a lower bound while providing a full slack on the upper bound. Global optimality of the solution is achieved using the developed technique. A minimum of 4-5 randomly selected data-points are required to achieve the optimal solution. The developed technique has also been tested for real-time field and laboratory investigations with encouraging results.

关键词： inverse analysis four-parameter Burger model mathematical programming formulation constrained nonlinear multivariable problem variable bounds global optimality

来源：评论

学校读者我要写书评

暂无评论

A mathematical programming Incremental formulation for Unilateral Frictional Contact Problems of Linear Elasticity

引用

International Journal of Phytoremediation 2003年第1期21卷 503-515页

作者： Doudoumis, I.N. Department of Civil Engineering Aristotle University of Thessaloniki Thessaloniki 54006 Greece

In this article a detailed analytical formulation of the unilateral contact boundary conditions with Coulomb's law of dry friction is first attempted and the quasi-static contact problem between 3-D elastic bodies is studied thereafter. Discretizing the bodies by the Finite Element Method, introducing fictitious contact bonds and using the concept of the equivalent structural system, an incremental Nonlinear Complementarity Problem is finally formulated. Then, using additional simplifying assumptions, this problem can be transformed into an incremental Linear Complementarity Problem. © 2003, Copyright Taylor & Francis Group, LLC.

关键词： Ams Subject Classification: 74-XX (Mechanics Of Deformable Solids) Frictional Contact mathematical programming formulation Unilateral Contact

来源：评论

学校读者我要写书评

暂无评论

ILP formulations and optimal solutions for the RWA problem

ILP formulations and optimal solutions for the RWA problem

引用

IEEE Global Telecommunications Conference (GLOBECOM 04)

作者： Jaumard, B Meyer, C Thiongane, B Yu, X Dept. of Comp. Sci. and Oper. Res. Université de Montréal Montréal Que. H3C 3J7 C.P. 6128 succ. centre-ville Canada Dept. Optimization of Commun. Netwk. Université de Montréal Montréal Que. H3C 3J7 C.P. 6128 succ. centre-ville Canada Department of Electrical Engineering Ecl. Polytech. de Montreal Canada

ISBN: (纸本)0780387945

We present a review of tire various integer linear programming (ILP) formulations that have been proposed for the routing and wavelength assignment problem in WDM optical networks with a unified and simplified notation. We consider both symmetrical and asymmetrical traffic matrices We propose a new formulation for symmetrical traffic. We show that all formulations proposed under asymmetrical traffic assumptions are equivalent (i.e. same optimal value for their continuous relaxations) although their number of variables and constraints differ. We propose an experimental comparison of various lower and upper hounds with the objective of minimizing the blocking rate, and show that several benchmark problems proposed by Krishnaswamy and Sivarajan (2001) can be solved exactly or with a fairly high precision.

关键词： MVA problem mathematical programming formulation heuristic

来源：评论

学校读者我要写书评

暂无评论

Markov decision processes with a stopping time constraint

引用

mathematical METHODS OF OPERATIONS RESEARCH 2001年第2期53卷 279-295页

作者： Horiguchi, M Chiba Univ Div Math Sci & Phys Grad Sch Sci & Technol Inage Ku Chiba 2638522 Japan

In this paper, the optimization problem for a stopped Markov decision process with finite states and actions is considered over stopping times tau constrained so that E tau less than or equal to alpha for some fixed alpha > 0. The problem is solved through randomization of stopping times and mathematical programming formulation by occupation measures. Another representation, called F-representation, of randomized stopping times is given, by which the concept of Markov or stationary randomized stopping times is introduced. We treat two types of occupation measures, running and stopped, but stopped occupation measure is shown to be expressed by running one. We study the properties of the set of running occupation measures achieved by different classes of pairs of policies and randomized stopping times. Analyzing the equivalent mathematical programming problem formulated by running occupation measures corresponding with stationary policies and stationary randomized stopping times, we prove the existence of an optimal constrained pair of stationary policy and stopping time requiring randomization in at most one state.

关键词： stopped Markov decision processes constrained stopping time mathematical programming formulation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：