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

Combinatorial optimization model and MIP formulation for the structural analysis of conditional differential-algebraic systems

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2011年第2期61卷 422-429页

作者： Lacroix, Mathieu Mahjoub, A. Ridha Martin, Sebastien Univ Paris 09 LAMSADE F-75775 Paris 16 France Univ Blaise Pascal Clermont Ferrand II LIMOS F-63177 Aubiere France

In this paper we consider the structural analysis problem for differential-algebraic systems with conditional equations. This problem consists, given a conditional differential-algebraic system, in verifying if the system is structurally nonsingular for every state, and if not in finding a state in which the system is structurally singular. We give a formulation for this problem as an integer linear program. This is based on a transformation of the problem into a matching problem in an auxiliary graph. We also show that the linear relaxation of that formulation can be solved in polynomial time. using this, we develop a branch-and-cut algorithm for solving the problem and present some experimental results. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Differential-algebraic system Structural analysis Graph Integer linear program Matching branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Design of survivable IP-over-optical networks

引用

ANNALS OF OPERATIONS RESEARCH 2006年第1期146卷 41-73页

作者： Borne, Sylvie Gourdin, Eric Liao, Bernard Mahjoub, A. Ridha Univ Clermont Ferrand Lab LIMOS CNRS F-63177 Clermont Ferrand France France Telecom Lab CORE CPN Div R&D F-92794 Issy Les Moulineaux 9 France France Telecom Lab ROSI DCAS F-75505 Paris 15 France

In the past years, telecommunications networks have seen an important evolution with the advances in optical technologies and the explosive growth of the Internet. Several optical systems allow a very large transport capacity, and data traffic has dramatically increased. Telecommunications networks are now moving towards a model of high-speed routers interconnected by intelligent optical core networks. Moreover, there is a general consensus that the control plan of the optical networks should utilize IP-based protocols for dynamic provisioning and restoration of lightpaths. The interaction of the IP routers with the optical core networks permits to achieve end-to-end connections, and the lightpaths of the optical networks define the topology of the IP network. This new infrastructure has to be sufficiently survivable, so that network services can be restored in the event of a catastrophic failure. In this paper we consider a multilayer survivable network design problem that may be of practical interest for IP-over-optical neworks. We give an integer programming formulation for this problem and discuss the associated polytope. We describe some valid inequalities and study when these are facet defining. We discuss separation algorithms for these inequalities and introduce some reduction operations. We develop a branch-and-cut algorithm based on these results and present extensive computational results.

关键词： IP-over-optical network survivability integer programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Formulations for the Split Delivery Capacitated Profitable Tour Problem 23rd

Formulations for the Split Delivery Capacitated Profitable T...

引用

23rd International Conference on Computational Science and its Applications (ICCSA)

作者： Caspar, Marvin Schermer, Daniel Wendt, Oliver Univ Kaiserslautern Landau Business Informat Syst & Operat Res BISOR Postfach 3049 D-67653 Kaiserslautern Germany

ISBN: (纸本)9783031368042;9783031368059

In this paper, we study the Split Delivery Capacitated Profitable Tour Problem (SDCPTP) that extends the profitable tour problem by a fleet of vehicles and the possibility of split deliveries. In the SDCPTP, the objective is to select a subset of requests and find for each vehicle a feasible tour such that the prize collected by fulfilling the selected requests net of the cost of delivery is maximized. We propose three mixed-integer linear programming formulations for modeling the SDCPTP. These formulations differ primarily in their treatment of the subtour elimination constraints within the branch-and-cut algorithm. The first of these formulations is applicable to the more general asymmetric case, whereas the other two are computationally more efficient in presence of symmetric variants of the problem. Using benchmark instances from the literature, we provide a detailed numerical study that demonstrates the effectiveness of a state-of-the-art solver in tackling these models. For managerial insights, we perform a sensitivity analysis on the SDCPTP with respect to the number of vehicles and requests as well as the benefits of enabling split delivery.

关键词： Mixed-Integer Linear Programming branch-and-cut algorithm Capacitated Profitable Tour Problem Split Delivery

来源：评论

学校读者我要写书评

暂无评论

The location-dispatching problem: Polyhedral results and content delivery network design

The location-dispatching problem: Polyhedral results and con...

引用

1st International Symposium on Combinatorial Optimization (ISCO)

作者： Chretienne, Philippe Fouilhoux, Pierre Gourdin, Eric Segura, Jean-Mathieu Univ Paris 06 Lab LIP6 F-75005 Paris France France Telecom R&D Orange Labs F-92794 Issy Les Moulineaux 9 France

Let G = (V, A) be a directed graph and F be a set of items. The Location-Dispatching Problem consists of determining subsets L-1 subset of F F located at nodes i is an element of V, minimizing the sum of two costs: a piecewise linear installation cost associated with L-1 and an access cost for each node of V to reach a copy of each item of F. We formulate this problem as a linear program with binary variables x and integer variables z. We propose a facial study of the associated polytope and we introduce the so-called integrity hop cost inequalities that force z to be an integer as soon as x is binary. Using this, we devise a branch-andcut algorithm and report some experimental results. This algorithm has been used to solve Content Delivery Network instances in order to optimize a Video On Demand (VoD) system. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Location Integer program Polytope branch-and-cut algorithm CDN design

来源：评论

学校读者我要写书评

暂无评论

A MIXED INTEGER LINEAR PROGRAMMING FORMULATION FOR THE SPARSE RECOVERY PROBLEM IN COMPRESSED SENSING

A MIXED INTEGER LINEAR PROGRAMMING FORMULATION FOR THE SPARS...

引用

IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)

作者： Karahanoglu, N. Burak Erdogan, Hakan Birbil, S. Ilker TUBITAK BILGEM Adv Technol Res Inst Kocaeli Turkey Sabanci Univ Fac Engn & Nat Sci Istanbul Turkey

ISBN: (纸本)9781479903566

We propose a new mixed integer linear programming (MILP) formulation of the sparse signal recovery problem in compressed sensing (CS). This formulation is obtained by introduction of an auxiliary binary vector, where ones locate the recovered nonzero indices. Joint optimization for finding this auxiliary vector together with the underlying sparse vector leads to the proposed MILP formulation. By addition of a few appropriate constraints, this problem can be solved by existing MILP solvers. In contrast to other methods, this formulation is not an approximation of the sparse optimization problem, but is its equivalent. Hence, its solution is exactly equal to the optimal solution of the original sparse recovery problem, once it is feasible. We demonstrate this by recovery simulations involving different sparse signal types. The proposed scheme improves recovery over the mainstream CS recovery methods especially when the underlying sparse signals have constant amplitude nonzero elements.

关键词： compressed sensing l(0) norm minimization sparse signal recovery mixed integer linear programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Comparing restoration concepts using optimal network configurations with integrated hardware and routing decisions 4

Comparing restoration concepts using optimal network configu...

引用

4th International Workshop on Design of Reliable Communication Networks (DRCN 2003)

作者： Orlowski, S Wessäly, R Konrad Zuse Zentrum Informat Tech Berlin Berlin Germany

ISBN: (纸本)0780381181

We investigate the impact of link and path restoration on the cost of telecommunication networks. The surprising result is the following: the cost of an optimal network configuration is almost independent of the restoration concept if (i) the installation of network elements (ADMs, DXCs, or routers) and interface cards, (ii) link capacities, and (iii) working and restoration routings are simultaneously optimized. We present a mixed-integer programming model which integrates all these decisions. Using a branch-and-cut algorithm (with column generation to deal with all potential routing paths), we solve structurally different real-world problem instances and show that the cost of optimal solutions is almost independent of the used restoration concept. In addition, we optimize spare capacities for given shortest working paths which are predetermined with respect to different link metrics. In comparison to simultaneous optimization of working and restoration routings, it turns out that this approach does not allow to obtain predictably good results.

关键词： survivable network design link and path restoration branch-and-cut algorithm hardware configuration routing

来源：评论

学校读者我要写书评

暂无评论

Multi-product Lot-Sizing Problem with Remanufacturing, Lost Sales and Sequence-Dependent Changeover Cost 14th

Multi-product Lot-Sizing Problem with Remanufacturing, Lost ...

引用

14th International Conferences on Computational Logistics (ICCL)

作者： Gana, Lucas Davila-Galvez, Sebastian Quezada, Franco Univ Santiago Chile USACH Dept Ind Engn Fac Engn Santiago Chile Univ Santiago Chile USACH Program Dev Sustainable Prod Syst PDSPS Fac Engn Santiago Chile

ISBN: (纸本)9783031436116;9783031436123

This work studies a lot-sizing problem motivated by a textile remanufacturing company in Chile. In particular, we investigate a multi-product lot-sizing with remanufacturing, lost sales, and sequence-dependent changeover costs. The problem is first formulated as a mixed-integer linear program. Then, we adapted a known family of valid inequalities and proposed a new exponential family of valid inequalities taking advantage of the problem structure. We use them in a branch-and-cut algorithm to solve the problem. The preliminary numerical results show the proposed inequalities' usefulness in strengthening the proposed formulation's linear relaxation and show that the method outperforms the generic branch-and-cut algorithm embedded in a stand-alone mathematical solver.

关键词： Lot-sizing and Scheduling Remanufacturing Changeover cost Valid inequalities branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Aggregating Incomplete Lists of Journal Rankings: An Application to Academic Accounting Journals

引用

ACCOUNTING PERSPECTIVES 2010年第3期9卷 217-235页

作者： Cook, Wade Raviv, Tal Richardson, Alan York Univ N York ON Canada Tel Aviv Univ Tel Aviv Israel

We introduce a branch-and-cut algorithm to aggregate published journal rankings based on subsets of the accounting literature in order to create a consensus ranking. The aggregate ranking allows specialist and regional journals, which may only be ranked in a limited number of studies, to be placed with respect to each other and with respect to the generalist journals that are usually included in ranking studies. The approach we develop is a significant advance over ad hoc approaches to aggregating journal rankings that have appeared in the literature and may provide a theoretically sound and replicable basis for further exploration of the concept of journal quality and the stability of journal rankings over time and ranking methods.

关键词： branch-and-bound algorithm branch-and-cut algorithm Consensus rankings Journal ranking Partial rankings

来源：评论

学校读者我要写书评

暂无评论

Separating valid odd-cycle and odd-set inequalities for the multiple depot vehicle scheduling problem

引用

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION 2013年第3-4期1卷 283-312页

作者： Groiez, Mounira Desaulniers, Guy Hadjar, Ahmed Marcotte, Odile Ecole Polytechn Montreal Dept Math & Genie Ind Montreal PQ H3C 3A7 Canada Gerad Montreal PQ H3C 3A7 Canada Kronos Canadian Syst Inc Montreal PQ H3V 1H8 Canada Univ Quebec Montreal Dept Informat CP 8888Succ Ctr Ville Montreal PQ H3C 3P8 Canada Gerad Montreal PQ H3C 3P8 Canada

We consider the multicommodity network flow formulation of the multiple depot vehicle scheduling problem (MDVSP) and investigate several strategies within a branch-and-cut framework for solving the MDVSP. In particular, we compare sub-algorithms for separating the cutting planes introduced by Hadjar et al. (Oper Res 54:130-149, 2006). We also evaluate the effectiveness of a new criterion for fixing some variables in the multicommodity flow formulation. Finally, we present computational experiments to illustrate the strengths and weaknesses of the strategies.

关键词： Transportation scheduling Multicommodity flow branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

The location-dispatching problem: Polyhedral results and content delivery network design

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 867-874页

作者： Chrétienne, Philippe Fouilhoux, Pierre Gourdin, Eric Segura, Jean-Mathieu Laboratoire LIP6 Université Pierre et Marie Curie 4 place Jussieu 75005 Paris France Orange Labs France Telecom R and D 92794 Issy-les-Moulineaux Cedex 9 38-40 bd du Général Leclerc France

Let G=(V,A) be a directed graph and F be a set of items. The Location-Dispatching Problem consists of determining subsets Li⊆ F, i ∈ V, minimizing the sum of two costs: an installation cost associated with nodes i of... 详细信息

Let G=(V,A) be a directed graph and F be a set of items. The Location-Dispatching Problem consists of determining subsets L_i⊆ F, i ∈ V, minimizing the sum of two costs: an installation cost associated with nodes i of V such that L_i ≠ θ and an access cost to each item of F. We formulate this problem as an integer linear program and propose a facial study of the associated polytope. We describe valid inequalities and give sufficient conditions for these inequalities to be facet defining. Using this, we devise a branch-and-cut algorithm and report some preliminary experimental results. This algorithm has been used to solve Content Delivery Network instances in order to optimize a Video On Demand (VoD) system. © 2010 Elsevier B.V.

关键词： branch-and-cut algorithm CDN design Dispatching Facets Location VoD system

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：