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

A branch-and-cut algorithm for the Multiple Steiner TSP with order constraints

Electronic Notes in Discrete Mathematics 2013年 41卷 487-494页

作者： Borne, S. Mahjoub, A.R. Taktak, R. LIPN Paris 13 University France LAMSADE Paris Dauphine University France

The paper deals with a problem motivated by survivability issues in multilayer IP-over-WDM telecommunication networks. Given a set of traffic demands for which we know a survivable routing in the IP layer, our purpose is to look for the corresponding survivable topology in the WDM layer. The problem amounts to Multiple Steiner TSPs with order constraints. We propose an integer linear programming formulation for the problem and investigate the associated polytope. We also present new valid inequalities and discuss their facial aspect. Based on this, we devise a branch-and-cut algorithm and present preliminary computational results. © 2013 Elsevier B.V.

关键词： branch-and-cut algorithm IP-over-WDM networks Order constraint Steiner TSP

来源：评论

学校读者我要写书评

暂无评论

Robust MILP formulations for the two-stage weighted vertex p-center problem

引用

COMPUTERS & OPERATIONS RESEARCH 2023年第1期159卷

作者： Duran-Mateluna, Cristian Ales, Zacharie Elloumi, Sourour Jorquera-Bravo, Natalia Inst Polytech Paris UMA ENSTA Paris F-91120 Palaiseau France CEDRIC Conservatoire Natl Arts & Metiers F-75003 Paris France Univ Santiago Chile USACH Fac Engn Program Dev Sustainable Prod Syst PDSPS Santiago Chile Univ Santiago Chile USACH Fac Engn Ind Engn Dept Santiago Chile

The weighted vertex p-center problem (PCP ) consists of locating p facilities among a set of available sites such that the maximum weighted distance (or travel time) from any demand node to its closest located facility is minimized. This paper studies the exact solution of the two-stage robust weighted vertex p-center problem (RPCP2). In this problem, the location of the facilities is fixed in the first stage while the demand node allocations are recourse decisions fixed once the uncertainty is revealed. The problem is modeled by box uncertainty sets on both the demands and the distances. We introduce five different robust reformulations based on MILP formulations of (PCP ) from the literature. We prove that considering a finite subset of scenarios is sufficient to obtain an optimal solution of (RPCP2). We leverage this result to introduce a column-and-constraint generation algorithm and a branch-and-cut algorithm to efficiently solve this problem optimally. We highlight how these algorithms can also be adapted to solve the single-stage problem (RPCP1) which is obtained when no recourse is considered. We present a numerical study to compare the performances of these formulations on randomly generated instances and on a case study from the literature.

关键词： Discrete location p-center problem Robust MILP formulations Column-and-constraint generation algorithm branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A computational study on the Maximum-Weight Bounded-Degree Rooted Tree Problem

引用

APPLIED MATHEMATICS AND COMPUTATION 2022年 413卷 126623-126623页

作者： Kerivin, Herve Zhao, Jinhua CNRS LIMOS UMR 6158 F-63178 Aubiere France Cent China Normal Univ Fac Artificial Intelligence Educ Cent China Normal Univ Wollongong Joint Inst Wuhan 430079 Peoples R China

This paper contributes to the computational study of the Maximum-Weight Bounded-Degree Rooted Tree Problem. Based on previous work, two types of formulations are introduced for the problem, along with some newly discovered constraints that can enhance the formulations. The separation problem for each family of constraints are studied in terms of their complexity and associated algorithms. We then compare the performance of four branch-and-cut frameworks in extensive computational simulations, especially the performance difference between original models and enhanced models with newly discovered constraints. Results show that the enhanced models have a significantly better performance than the original ones. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Bounded-degree rooted tree branch-and-cut algorithm Separation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Benders decomposition applied to profit maximizing hub location problem with incomplete hub network

引用

COMPUTERS & OPERATIONS RESEARCH 2022年 142卷 105715-105715页

作者： Oliveira, Fabricio Alves de Sa, Elisangela Martins de Souza, Sergio Ricardo Fed Inst Minas Gerais IFMG Rua Afonso Sardinha 90 BR-36420000 Ouro Branco MG Brazil Fed Ctr Technol Educ Minas Gerais CEFET MG Ave Amazonas 7675 BR-30510000 Belo Horizonte MG Brazil

This paper addresses a profit maximizing multiple allocation hub network design problem, which is a hub location problem with incomplete hub network, aiming to determine the quantity and location of the hubs, allocate demand nodes to these hubs, establish the network topology, and route the demand flows to satisfy the demands between the origin and destination pairs that were selected to be served in order to obtain the highest profit. This problem also considers the multiple allocation strategy, does not allow direct connections between non-hub nodes, does not impose capacity constraints, and assumes that there are fixed costs involved in installing hubs and installing hub arcs. A new formulation for the problem is presented and it is proved that this formulation is stronger than another one in the literature, which models the same problem. Several versions of the Benders decomposition method, combining the generation of Pareto-optimal cuts, multiple cuts strategies, and Benders branch-and-cut scheme, are proposed and analyzed through extensive computational experiments on benchmark instances. The best-proposed Benders decomposition versions were compared with the CPLEX solver, with and without the activation of its Benders decomposition algorithm. The results showed that these algorithms perform much better than the solver versions. The proposed Benders decomposition approach can solve benchmark instances with up to 150 nodes.

关键词： Hub network design problem Profit maximization Incomplete hub network Hub location problem Benders decomposition method branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A routing model and solution approach for alternative fuel vehicles with consideration of the fixed fueling time

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2020年 142卷 106364-106364页

作者： Shao, Yihuan Dessouky, Maged Univ Southern Calif Daniel J Dept Ind & Syst Engn Los Angeles CA 90089 USA

In this paper, we introduce the Vehicle Routing Problem for Alternative Fuel Vehicles with Fixed Fueling Time (VRPAFVFFT) to model decisions to be made with regards to the vehicle routes cons, dering fuel stations. A Mixed Integer Programming (MIP) model is proposed with improving methods, which includes an adaptive branch-and-cut algorithm. To solve large scale problems, we present a hybrid heuristic method, which combines an Adaptive Large Neighborhood Search (ALNS) with a local search and a MIP model. We conduct experiments to show the efficiency of our solving methods as well as insights from real world cases.

关键词： Green VRP Alternative fuel vehicles Fuel stations branch-and-cut algorithm ALNS

来源：评论

学校读者我要写书评

暂无评论

Models and algorithms for the Traveling Salesman Problem with Time-dependent Service times

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第3期283卷 825-843页

作者： Cacchiani, Valentina Contreras-Bolton, Carlos Toth, Paolo Univ Bologna DEI Viale Risorgimento 2 I-40136 Bologna Italy

The Traveling Salesman Problem with Time-dependent Service times (TSP-TS) is a generalization of the Asymmetric TSP, in which the service time at each customer is given by a (linear or quadratic) function of the corresponding start time of service. TSP-TS calls for determining a Hamiltonian tour (i.e. a tour visiting each customer exactly once) that minimizes the total tour duration, given by the sum of travel and service times. We propose a new Mixed Integer Programming model for TSP-TS, that is enhanced by lower and upper bounds that improve previous bounds from the literature, and by incorporating exponentially many subtour elimination constraints, that are separated in a dynamic way. In addition, we develop a multi-operator genetic algorithm and two branch-and-cut methods, based on the proposed model. The algorithms are tested on benchmark symmetric instances from the literature, and compared with an existing approach. The computational results show that the proposed exact methods are able to prove the optimality of the solutions found for a larger set of instances in shorter computing times. We also tested the branch-and-cut algorithms on larger size symmetric instances with up to 58 nodes and on asymmetric instances with up to 45 nodes, demonstrating the effectiveness of the proposed algorithms. In addition, we tested the genetic algorithm on symmetric and asymmetric instances with up to 200 nodes. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Travelling Salesman Time-dependent Service times Mathematical model branch-and-cut algorithm Genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints

引用

INFORMS JOURNAL ON COMPUTING 2020年第1期32卷 120-134页

作者： Arslan, Okan Jabali, Ola Laporte, Gilbert HEC Montreal Montreal PQ H3T 2A7 Canada Politecn Milan Dipartimento Elettron Informaz & Bioingn I-20133 Milan Italy

Given a graph, a set of origin-destination (OD) pairs with communication requirements, and an integer k >= 2, the network design problem with vulnerability constraints (NDPVC) is to identify a subgraph with the minimum total edge costs such that, between each OD pair, there exist a hop-constrained primary path and a hop-constrained backup path after any k - 1 edges of the graph fail. Formulations exist for single-edge failures (i.e., k = 2). To solve the NDPVC for an arbitrary number of edge failures, we develop two natural formulations based on the notion of length-bounded cuts. We compare their strengths and flexibilities in solving the problem for k >= 3. We study different methods to separate infeasible solutions by computing length-bounded cuts of a given size. Experimental results show that, for single-edge failures, our formulation increases the number of solved benchmark instances from 61% (obtained within a two-hour limit by the best published algorithm) to more than 95%, thus increasing the number of solved instances by 1,065. Our formulation also accelerates the solution process for larger hop limits and efficiently solves the NDPVC for general k. We test our best algorithm for two to five simultaneous edge failures and investigate the impact of multiple failures on the network design.

关键词： network design survivability vulnerability branch-and-cut algorithm length-bounded minimum cut

来源：评论

学校读者我要写书评

暂无评论

A multi-stage stochastic integer programming approach for a multi-echelon lot-sizing problem with returns and lost sales

引用

COMPUTERS & OPERATIONS RESEARCH 2020年 116卷 104865-000页

作者： Quezada, Franco Gicquel, Celine Kedad-Sidhoum, Safia Dong Quan Vu Sorbonne Univ CNRS Lab Informat Paris 6 F-75005 Paris France Univ Paris Saclay LRI F-91190 Gif Sur Yvette France CEDRIC CNAM F-75003 Paris France Nokia Paris Saclay Nokia Bell Labs Route Villejust F-91620 Nozay France

We consider an uncapacitated multi-item multi-echelon lot-sizing problem within a remanufacturing system involving three production echelons: disassembly, refurbishing and reassembly. We seek to plan the production activities on this system over a multi-period horizon. We consider a stochastic environment, in which the input data of the optimization problem are subject to uncertainty. We propose a multi-stage stochastic integer programming approach relying on scenario trees to represent the uncertain information structure and develop a branch-and-cut algorithm in order to solve the resulting mixed-integer linear program to optimality. This algorithm relies on a new set of tree inequalities obtained by combining valid inequalities previously known for each individual scenario of the scenario tree. These inequalities are used within a cutting-plane generation procedure based on a heuristic resolution of the corresponding separation problem. Computational experiments carried out on randomly generated instances show that the proposed branch-and-cut algorithm performs well as compared to the use of a stand-alone mathematical solver. Finally, rolling horizon simulations are carried out to assess the practical performance of the multi-stage stochastic planning model with respect to a deterministic model and a two-stage stochastic planning model. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Stochastic lot-sizing Remanufacturing system Lost sales Multi-stage stochastic integer programming Scenario tree Valid inequalities branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：