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

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

来源：评论

学校读者我要写书评

暂无评论

Stronger MIP formulations for the Steiner forest problem

引用

MATHEMATICAL PROGRAMMING 2021年第1-2期186卷 373-407页

作者： Schmidt, Daniel Zey, Bernd Margot, Francois Univ Bonn Inst Comp Sci Bonn Germany TU Dortmund Dept Comp Sci Chair 11 Dortmund Germany

The Steiner forest problem asks for a minimum weight forest that spans a given number of terminal sets. We propose new cut- and flow-based integer linear programming formulations for the problem which yield stronger linear programming bounds than the two previous strongest formulations: The directed cut formulation (Balakrishnan et al. in Oper Res 37(5):716-740, 1989;Chopra and Rao in Math Prog 64(1):209-229, 1994) and the advanced flow formulation by Magnanti and Raghavan (Networks 45:61-79, 2005). We further introduce strengthening constraints and provide an example where the integrality gap of our models is 1.5. In an experimental evaluation, we show that the linear programming bounds of the new formulations are indeed strong on practical instances and that the related branch-and-cut algorithm outperforms algorithms based on the previous formulations.

关键词： Steiner forest problem Integer programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving the Single Vehicle Routing Problem with Variable Capacity

引用

TRANSPORTATION SCIENCE 2016年第2期50卷 708-719页

作者： Louveaux, Francois V. Salazar-Gonzalez, Juan-Jose Univ Namur Dept Business Adm B-5000 Namur Belgium Univ La Laguna DEIOC Tenerife 38271 Spain

This paper considers the classical vehicle routing problem (VRP) where the vehicle capacity is not fixed. Indeed, at the moment of acquiring (or renting) the vehicle that will serve all customers, there is some freedom of choice. A larger vehicle capacity implies a lower total distance travelled but larger operating costs. The reverse is true for a smaller vehicle. This paper gives an approach to select the best capacity and the best route to minimize a function of the acquisition cost and travelled distance. We first consider an enumerative approach, which consists of solving a sequence of VRPs, starting from the one having the largest capacity. The number of VRPs to solve using this approach is unknown. Based on computational experiments, this number is mostly large in our benchmark instances. We then proceed to a direct approach based on the two-index formulation of the VRP. We introduce several valid inequalities that allow us to have an integer linear programming formulation of the VRP with fixed vehicle capacity. We describe separation procedures for these inequalities. We conclude with computational results that confirm the utility of these inequalities when solving benchmark VRP instances.

关键词： vehicle routing problem unknown vehicle capacity branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimum edge blocker dominating set problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第1期247卷 16-26页

作者： Pajouh, Foad Mahdavi Walteros, Jose L. Boginski, Vladimir Pasiliao, Eduardo L. Univ Massachusetts Management Sci & Informat Syst Dept Boston MA 02125 USA SUNY Buffalo Dept Ind & Syst Engn Buffalo NY 14260 USA Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Air Force Res Lab Munit Directorate Eglin AFB FL 32542 USA

This paper introduces and studies the minimum edge blocker dominating set problem (EBDP), which is formulated as follows. Given a vertex-weighted undirected graph and r> 0, remove a minimum number of edges so that the weight of any dominating set in the remaining graph is at least r. Dominating sets are used in a wide variety of graph-based applications such as the analysis of wireless and social networks. We show that the decision version of EBDP is NP-hard for any fixed r> 0. We present an analytical lower bound for the value of an optimal solution to EBDP and formulate this problem as a linear 0-1 program with a large number of constraints. We also study the convex hull of feasible solutions to EBDP and identify facet-inducing inequalities for this polytope. Furthermore, we develop the first exact algorithm for solving EBDP, which solves the proposed formulation by a branch-and-cut approach where nontrivial constraints are applied in a lazy fashion. Finally, we also provide the computational results obtained by using our approach on a test-bed of randomly generated instances and real-life power-law graphs. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.

关键词： Network interdiction Minimum weighted dominating set NP-hardness branch-and-cut algorithm Critical elements detection

来源：评论

学校读者我要写书评

暂无评论

Polyhedral study of simple plant location problem with order

引用

OPERATIONS RESEARCH LETTERS 2013年第2期41卷 153-158页

作者： Vasilyev, Igor Klimentova, Xenia Boccia, Maurizio Russian Acad Sci ISDCT SB RAS Inst Syst Dynam & Control Theory Siberian Branch Irkutsk 664033 Russia Univ Sannio Dipartimento Ingn I-82100 Benevento Italy

This paper is addressed to the generalization of simple plant location problem where customer's preferences are taken into account. Some basic polyhedral studies and a new family of facet-defining inequalities are given. The effectiveness of the proposed approach is illustrated by the computational experience. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Simple plant location problem with order Facet-defining inequality branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

The green vehicle routing problem: A heuristic based exact solution approach

引用

APPLIED SOFT COMPUTING 2016年 39卷 154-164页

作者： Koc, Cagri Karaoglan, Ismail HEC Montreal CIRRELT Montreal PQ Canada HEC Montreal Canada Res Chair Distribut Management Montreal PQ Canada Selcuk Univ Dept Ind Engn Konya Turkey

This paper develops a simulated annealing heuristic based exact solution approach to solve the green vehicle routing problem (G-VRP) which extends the classical vehicle routing problem by considering a limited driving range of vehicles in conjunction with limited refueling infrastructure. The problem particularly arises for companies and agencies that employ a fleet of alternative energy powered vehicles on transportation systems for urban areas or for goods distribution. Exact algorithm is based on the branch-and-cut algorithm which combines several valid inequalities derived from the literature to improve lower bounds and introduces a heuristic algorithm based on simulated annealing to obtain upper bounds. Solution approach is evaluated in terms of the number of test instances solved to optimality, bound quality and computation time to reach the best solution of the various test problems. Computational results show that 22 of 40 instances with 20 customers can be solved optimally within reasonable computation time. (C) 2015 Elsevier B.V. All rights reserved.

关键词： The green vehicle routing problem Mixed integer programming formulation branch-and-cut algorithm Simulated annealing

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Multi-Objective Trip Planning With Solution Ranking Based on User Preference and Restaurant Selection

引用

IEEE ACCESS 2022年 10卷 10688-10705页

作者： Choachaicharoenkul, Supoj Coit, David Wattanapongsakorn, Naruemon King Mongkuts Univ Technol Thonburi Fac Engn Dept Comp Engn Bangkok 10140 Thailand Rutgers State Univ Dept Ind & Syst Engn Piscataway NJ 08854 USA Tsinghua Univ Dept Ind Engn Beijing 100190 Peoples R China

The tourist trip design problem (TTDP) helps the trip planners, such as tourists, tour companies, and government agencies, automate their trip planning. TTDP solver chooses and sequences an optimal subset of point of interest (POIs), which adhere to the POIs attributes and tourist preferences, and then generates a travel itinerary that maximizes their pleasure. However, the traditional TTDP does not include the lunch period at a local restaurant, which causes the rest of the itinerary in the afternoon to shift, nor compulsory POIs that the trip planners must be included in the itinerary. Moreover, as tourism contributes to high greenhouse gas emissions, especially from its transportation, minimizing the itinerary's total distance is also considered. Unfortunately, this objective conflicts with the profit scores;no single itinerary can optimize both objectives simultaneously. Hence, the multi-objective technique and the results of non-dominated itineraries can be organized as a Pareto front. The trip planners can choose one suitable itinerary from the Pareto front based on their preferences. To address these real-world issues, we formulate a new variant of the well-known orienteering problem with time windows (OPTW) called the multi-objective orienteering problem with Time Windows, Restaurant Selection, and Compulsory POIs (MOPTW-RSCP). The proposed problem is provided with a mathematical formulation and two exact algorithms for solving them, i.e., greedy and branch-and-cut Pareto-based techniques. The algorithms' performance is tested against the Rattanakosin island (the old city of Bangkok) dataset. We conduct 24 test cases, and the computational results confirm the algorithms' efficiency.

关键词： Transportation Optimization Legged locomotion Carbon dioxide Tourism industry Mathematical models Planning branch-and-cut algorithm decision support system greedy algorithm multi-objective optimization orienteering problem solution ranking tourist trip design problem

来源：评论

学校读者我要写书评

暂无评论

Evaluation of Environmental Benefits Caused by Reservation-Based Shared Parking: A Case Study of Beijing, China

引用

IEEE ACCESS 2021年 9卷 3744-3751页

作者： Zhao, Pengfei Guan, Hongzhi Wang, Pengfei Yan, Hai Beijing Univ Civil Engn & Architecture Sch Civil & Transportat Engn Beijing 102616 Peoples R China Beijing Univ Technol Fac Urban Construct Coll Architecture & Civil Engn Beijing 100124 Peoples R China Beijing Univ Technol Minist Educ Key Lab Urban Secur & Disaster Engn Beijing 100124 Peoples R China Hebei Normal Univ Sci & Technol Coll Urban Construct Qinhuangdao 066004 Hebei Peoples R China Beijing Univ Technol Fac Urban Construct Coll Metropolitan Transportat Beijing 100124 Peoples R China

With the help of accurate parking navigation systems, sharing vacant private parking spaces with public travelers may have the potential of reducing the number of cruising vehicles and contribute to traffic emission reduction. However, the quantitative effects of such a measure are still relatively unknown in traffic management. In this article, we firstly established an optimal allocation model of shared parking spaces, which is a pure integer linear programming model of maximizing the number of served public vehicles to avoid cruising for parking. Further, the parking space allocation model was expanded to an estimation model that quantifies the effect of emission reduction. Secondly, a branch-and-cut algorithm was introduced as the core algorithm to solve the proposed models. Finally, detailed sensitivity analysis, based on empirical data collected by electronic parking toll collections and questionnaire surveys in Beijing, China, evaluated the proposed model and algorithm. The results indicate that shared parking can not only effectively reduce the cruising time and the number of vehicles, but also has significantly a positive effect on emission reduction. This research is helpful to provide theoretical support for alleviating parking pressure and environmental problems.

关键词： Potential emission reduction shared parking optimal parking space allocation pure integer linear programming model branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for Cluster Editing: Evaluation and Experiments

引用

algorithmICA 2011年第2期60卷 316-334页

作者： Boecker, Sebastian Briesemeister, Sebastian Klau, Gunnar W. Univ Jena Inst Informat Jena Germany Jena Ctr Bioinformat Jena Germany Univ Tubingen Div Simulat Biol Syst ZBIT WSI Tubingen Germany CWI NL-1090 GB Amsterdam Netherlands

The Cluster Editing problem is defined as follows: Given an undirected, loopless graph, we want to find a set of edge modifications (insertions and deletions) of minimum cardinality, such that the modified graph consists of disjoint cliques. We present empirical results for this problem using exact methods from fixed-parameter algorithmics and linear programming. We investigate parameter-independent data reduction methods and find that effective preprocessing is possible if the number of edge modifications k is smaller than some multiple of vertical bar V vertical bar , where V is the vertex set of the input graph. In particular, combining parameter-dependent data reduction with lower and upper bounds we can effectively reduce graphs satisfying k <= 25 vertical bar V vertical bar In addition to the fastest known fixed-parameter branching strategy for the problem, we investigate an integer linear program (ILP) formulation of the problem using a cutting plane approach. Our results indicate that both approaches are capable of solving large graphs with 1000 vertices and several thousand edge modifications. For the first time, complex and very large graphs such as biological instances allow for an exact solution, using a combination of the above techniques. (A preliminary version of this paper appeared under the title "Exact algorithms for cluster editing: Evaluation and experiments" in the Proceedings of the 7th Workshop on Experimental algorithms, WEA 2008, in: LNCS, vol. 5038, Springer, pp. 289-302.).

关键词： Cluster editing algorithm engineering Computer experiments NP-complete problem Fixed-parameter tractability FPT Integer linear programming ILP branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：