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

An exact approach for the r-interdiction covering problem with fortification

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2019年第1期27卷 111-131页

作者： Roboredo, Marcos Costa Aizemberg, Luiz Pessoa, Artur Alves Univ Fed Fluminense Dept Engn Prod Rua Passo Patria 156 BR-24210240 Niteroi RJ Brazil Banco Nacl Desenvolvimento Ave Republ Chile 100 BR-20031917 Rio De Janeiro RJ Brazil

In this paper we treat the r-interdiction covering problem with fortification (RICF). The environment of this problem is composed of a set of customers J and a set of facilities I. For each customer j, there is set of facilities containing the facilities that can cover the demand of j. The system efficiency is given by the sum of the total covered demand. The facilities are subject to interdictions. When a facility is interdicted, it can not cover the demand of any customer. To mitigate the negative impact of the interdictions on the system efficiency, the system planner can fortify a subset of facilities. If a facility is fortified then it can not be interdicted. The RICF consists of choosing q facilities to be fortified knowing that r not fortified facilities will be interdicted at the worst case. We propose a branch-and-cut algorithm for the problem. Our results are compared with the exact method found in the literature, being faster for the most instances, mainly the large ones.

关键词： Integer programming branch-and-cut algorithm r-Interdiction covering problem with fortification

来源：评论

学校读者我要写书评

暂无评论

Scheduling optimization for two crossover automated stacking cranes considering relocation

引用

OPERATIONAL RESEARCH 2022年第3期22卷 2099-2120页

作者： Chen, Sumin Zeng, Qingcheng Hu, Yushan Dalian Maritime Univ Sch Maritime Econ & Management 1 Linghai Rd Dalian 116026 Peoples R China Dalian Maritime Univ Collaborat Innovat Ctr Transport Studies 1 Linghai Rd Dalian 116026 Peoples R China

In this paper, we focus on the two crossover automated stacking cranes (ASCs) scheduling problem that arises at a storage block in an automated container terminal. To address relocation during retrieval operations, we use two methods with job precedence constraints: (1) adjusting the operation sequence of jobs to avoid relocation operations and (2) optimizing the dispatching for relocation operations to improve the efficiency of ASCs. Therefore, the method proposed in this paper optimizes the dispatching for storage, retrieval, and relocation and the routes of the ASCs while considering interferences between the ASCs and job precedence constraints. A branch-and-cut algorithm based on the characteristics of the problem is designed to decompose the problem into two problem classes connected via logic-based Benders constraints. Numerical experiments indicate that the proposed algorithm is efficient for solving realistically sized problems. Furthermore, the influence of the number of relocations is investigated based on experimental results.

关键词： Container terminals Automated stacking crane scheduling Relocation Benders constraints branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Two-edge connectivity with disjunctive constraints: Polyhedral analysis and branch-and-cut

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2023年 184卷

作者： Almudahka, Intesar Diarrassouba, Ibrahima Mahjoub, A. Ridha Taktak, Raouia Kuwait Univ Coll Sci Dept Stat & Operat Res Safat Kuwait Univ Le Havre Normandy UNIHAVRE LMAH CNRSFR 3335 F-76600 Le Havre France Univ Paris 09 PSL LAMSADE CNRSUMR 7243 Paris France Univ Sfax ISIMS Sfax Tunisia Univ Sfax Smrts CRNS Sfax Tunisia

In this paper we consider the two-edge-connected subgraph problem with disjunctive constraints. We inves-tigate the convex hull of the solutions to this problem. We describe several classes of valid inequalities, and discuss their facial aspect. We also devise separation routines for these inequalities. Using this, we propose a branch-and-cut algorithm for the problem along with an extensive computational study is presented.

关键词： Network survivability Connectivity constraints Disjunctive constraints branch-and-cut algorithm Facet

来源：评论

学校读者我要写书评

暂无评论

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

引用

DISCRETE APPLIED MATHEMATICS 2014年 164卷 68-85页

作者： 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A Bilevel Model for Centralized Optimization of Charging Stops for EV on Highways 10th

A Bilevel Model for Centralized Optimization of Charging Sto...

引用

10th International Conference on Network Games, Control and Optimization (NetGCooP)

作者： Woznica, Anthony Quadri, Dominique Hayel, Yezekael Beaude, Olivier Univ Paris Sud Univ Paris Saclay LRI Bat 650 F-91405 Orsay France Univ Avignon 339 Chemin Meinajaries F-84911 Avignon 9 France EDF Lab Paris Saclay Palaiseau France

ISBN: (纸本)9783030874735;9783030874728

This paper addresses the multi-period problem of fixing the energy charging price at a set of charging stations deployed to support long journeys of electric vehicles along highways. In order to model the problem, we propose a non-linear bilevel program, in which the leader (a single centralized operator) fixes the charging price over the time horizon to maximize its profit and the follower (the operator of the electric vehicles) chooses the optimal assignment of the electric vehicles to the stations so to minimize a cost function. To solve the resulting model, we suggest to adopt an adaption of the branch-and-cut algorithm for Mixed Integer Linear Bilevel Programming proposed by Fischetti et al. (2018). Preliminary computational results are provided to show the interesting performance of the new modeling and algorithmic approach.

关键词： Electrical vehicles Bilevel programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

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

来源：评论

学校读者我要写书评

暂无评论

A new formulation for the Weighted Safe Set Problem 11

A new formulation for the Weighted Safe Set Problem

引用

11th Latin and American algorithms, Graphs and Optimization Symposium (LAGOS)

作者： Malaguti, Enrico Pedrotti, Vagner Univ Bologna Dipartimento Ingn Energia Elettr & Informaz Gugli Bologna Italy Univ Fed Mato Grosso do Sul Fac Comp Campo Grande MS Brazil

Given a connected graph G = (V, E), a Safe Set S is a subset of the vertex set V such that the cardinality of each connected component in the subgraph induced by V \ S does not exceed the cardinality of any connected component in the subgraph induced by S, whenever there is an edge in G between vertices of the two components. When the vertices of G are weighted, the weight of a component is defined as the sum of the weights of its vertices, and the notion of safe set is extended by considering the weight of connected components in subgraphs induced by S and by V \ S. We propose an integer linear formulation for the Weighted Safe Set Problem that uses only one variable per vertex. The formulation has an exponential number of constraints, which can be generated on-the-fly within a branch-and-cut algorithm. We describe a linear-time separation algorithm for these constraints. In addition, we describe families of cuts based on cliques and on minimum weight cut separators, and discuss separation algorithms. A branch-and-cut algorithm that solves the proposed formulation is computationally compared with two alternative formulations from the literature, and shows faster in solving most of benchmark instances with low edge density. (C) 2021 The Authors. Published by Elsevier B.V.

关键词： Safe Set Problem Weighted Safe Set Problem branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：