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

The ring-star problem: A new integer programming formulation and a branch-and-cut algorithm

DISCRETE APPLIED MATHEMATICS 2011年第16期159卷 1901-1914页

作者： Simonetti, L. Frota, Y. de Souza, C. C. Univ Estadual Campinas Inst Comp BR-13852970 Campinas SP Brazil Univ Fed Fluminense Dept Comp Sci BR-22410240 Niteroi RJ Brazil

A ring star in a graph is a subgraph that can be decomposed into a cycle (or ring) and a set of edges with exactly one vertex in the cycle. In the minimum ring-star problem (MRSP) the cost of a ring star is given by the sum of the costs of its edges, which vary, depending on whether the edge is part of the ring or not. The goal is to find a ring-star spanning subgraph minimizing the sum of all ring and assignment costs. In this paper we show that the MRSP can be reduced to a minimum (constrained) Steiner arborescence problem on a layered graph. This reduction is used to introduce a new integer programming formulation for the MRSP. We prove that the dual bound generated by the linear relaxation of this formulation always dominates the one provided by an early model from the literature. Based on our new formulation, we developed a branch-and-cut algorithm for the MRSP. On the primal side, we devised a GRASP heuristic to generate good upper bounds for the problem. Computational tests with these algorithms were conducted on a benchmark of public domain. In these experiments both our exact and heuristics algorithms had excellent performances, noticeably in dealing with instances whose optimal solution has few vertices in the ring. In addition, we also investigate the minimum spanning caterpillar problem (MSCP) which has the same input as the MRSP and admits feasible solutions that can be viewed as ring stars with paths in the place of rings. We present an easy reduction of the MSCP to the MRSP, which makes it possible to solve to optimality instances of the former problem too. Experiments carried out with the MSCP revealed that our branch-and-cut algorithm is capable to solve to optimality instances with up to 200 vertices in reasonable time. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Ring-star problem Caterpillar trees Integer programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for the ring spur assignment problem

A branch-and-cut algorithm for the ring spur assignment prob...

引用

5th International Network Optimization Conference (INOC)

作者： Carroll, Paula Fortz, Bernard Labbe, Martine McGarraghy, Sean Univ Coll Dublin Quinn & Smurfit Sch Business Dublin Ireland Univ Libre Bruxelles Dept Informat Fac Sci Brussels Belgium

The ring spur assignment problem arises in the design of next-generation telecommunications networks and has applications in location-allocation problems. The aim is to identify a minimum cost set of interconnected ring spurs. We seek to connect all nodes of the network either on a set of bounded disjoint local rings or by a single spur edge connected to a node on a local ring. Local rings are interconnected by a special ring called the tertiary ring. We show that the problem is NP -Hard and present an Integer Programming formulation with additional valid inequalities. We implement a branch-and-cut algorithm and present our conclusions with computational results. (c) 2013 Wiley Periodicals, Inc. NETWORKS, 2013

关键词： survivable network design NP-hardness proof IP formulation branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

The ring-star problem: A new integer programming formulation and a branch-and-cut algorithm

The ring-star problem: A new integer programming formulation...

引用

8th Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009)

作者： Simonetti, L. Frota, Y. de Souza, C. C. Univ Estadual Campinas Inst Comp BR-13852970 Campinas SP Brazil Univ Fed Fluminense Dept Comp Sci BR-22410240 Niteroi RJ Brazil

关键词： Ring-star problem Caterpillar trees Integer programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast bounding technique for branch-and-cut algorithm based monthly SCUC

Fast bounding technique for branch-and-cut algorithm based m...

引用

General Meeting of the IEEE-Power-and-Energy-Society

作者： Wang, Peng Wang, Yang Xia, Qing Tsinghua Univ Dept Elect Engn State Key Lab Power Syst Beijing 100084 Peoples R China

ISBN: (纸本)9781467327299

Monthly unit commitment with energy constraints is crucial for reducing the energy consumption of generation scheduling. Restricted by the calculation complexity, most approaches for long-term SCUC have to sacrifice the optimality of the solution for the sake of the acceptable calculation time. In response to this issue, a fast bounding technique is proposed to improve the traditional branch and cut algorithm. This technique is able to quickly decrease the upper bound and increase the lower bound for the optimal solution of long-term SCUC in branch-and-cut search, and improve the calculation speed of monthly SCUC in the premise of guaranteeing the optimality of solution. A practical provincial power system in China is employed in cases study, and corresponding results demonstrate the effectiveness of the proposed algorithm.

关键词： branch-and-cut algorithm cut plane tech-nique energy efficiency energy constraints mixed integer program (MIP) long-term security constrained unit commit-ment (SCUC)

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm framework for the integrated aircraft hangar maintenance scheduling and staffing problem 19

A branch-and-cut algorithm framework for the integrated airc...

引用

2nd International Conference on Information Science and System (ICISS)

作者： Qin, Yichen Chan, Felix T. S. Chung, S. H. Qu, T. Jinan Univ Sch Elect & Informat Engn Zhuhai Campus Zhuhai 519070 Peoples R China Hong Kong Polytech Univ Dept Ind & Syst Engn Hong Kong Peoples R China

ISBN: (纸本)9781450361033

The problem of maintenance scheduling and staffing at an aircraft heavy maintenance service company is studied. The objective is to establish an integrated aircraft maintenance schedule and maintenance technicians' rosters to fulfil different maintenance requests while minimizing the overall tardiness cost and labor cost. Upon receiving the maintenance requests, the hangar planner has to determine if the maintenance company is capable to serve the aircraft within the planning period, then allocate the parking stands and staying time of each aircraft in the hangar for the subsequent maintenance operations. Due to the complexity of the combinatorial problem, the commercial solver using branch-and-bound algorithm is incapable to tackle with the medium-sized instance within reasonable time. To enhance the computational efficiency, a framework of branch-and-cut algorithm is proposed in this paper, aiming to decompose the original model and tighten the lower bound of the original problem by the effective cuts. The concept of combinatorial benders' decomposition algorithm is adopted in the development of algorithm.

关键词： Aircraft hangar maintenance hangar layout planning workforce scheduling branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for vehicle routing problems

引用

Annals of Operations Research 1994年第1期50卷 37-59页

作者： Araque G, J.R. Kudva, G. Morin, T.L. Pekny, J.F. School of Industrial Engineering and Program in Computational Combinatorics Purdue University West Lafayette 47907 Indiana United States School of Chemical Engineering Purdue University West Lafayette 47907 Indiana United States

We present a branch-and-cut algorithm for the identical customer Vehicle Routing Problem. Transforming the problem into an equivalent Path-Partitioning Problem allows us to exploit its polyhedral structure and to generate strong cuts corresponding to facet-inducing inequalities. By using cuts defined by multistars, partial multistars and generalized subtour elimination constraints, we are able to consistently solve 60-city problems to proven optimality and are currently attempting to solve problems involving a hundred cities. We also present details of the computer implementation and our computational results. © 1994 J.C. Baltzer AG, Science Publishers.

关键词： branch-and-cut algorithm combinatorial optimization facets polyhedral theory scientific computation Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

The Tree-Star Problem: A Formulation and a branch-and-cut algorithm

引用

Electronic Notes in Discrete Mathematics 2016年 52卷 285-292页

作者： Lucena, Abilio Simonetti, Luidi da Cunha, Alexandre Salles Departamento de Administração / PESC-COPPE Universidade Federal do Rio de Janeiro Rio de Janeiro Brazil Instituto de Computação Universidade Federal Fluminense Niteroi Brazil Departamento de Ciência da Computação Universidade Federal de Minas Gerais Belo Horizonte Brazil

Let G(V,E) be a connected undirected graph and assume that an edge e=i,j∈E may be priced differently, at the different spanning trees of G that contain it. A cost ce applying when e is leaf implying, i.e., when e bel... 详细信息

Let G(V,E) be a connected undirected graph and assume that an edge e=i,j∈E may be priced differently, at the different spanning trees of G that contain it. A cost c_e applying when e is leaf implying, i.e., when e belongs to the spanning tree and i or j are spanning tree leaves. Otherwise, when e belongs to the tree but is not leaf implying, a cost d_e would apply. Under such a pricing of edges, the Tree-Star Problem is to find a least cost spanning tree of G. The problem does not appear to have been previously investigated in the literature and we show it to be NP-hard, formulate it as a mixed integer program, and propose and test a branch-and-cut algorithm for it. So far, the algorithm contains no primal heuristic. However, as it stands, it is already capable of solving to proven optimality tree-star instances with as many as 299 vertices. © 2016 Elsevier B.V.

关键词： branch-and-cut algorithm Formulation The Tree-Star Problem

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Freight train line planning for large-scale high-speed rail network: An integer Benders decomposition-based branch-and-cut algorithm

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2024年 192卷

作者： Li, Shengdong Zuo, Dajie Li, Wenqing Zhang, Yongxiang Shi, Li Chengdu Univ Informat Technol Sch Logist Chengdu 610103 Peoples R China Southwest Jiaotong Univ Sch Transportat & Logist Chengdu 610031 Peoples R China

This paper aims to study and address the problem of completely re-scheduling high-speed freight train line plans under the conditions of a large-scale network, particularly for direct freight trains between central network nodes. First, we constructed a line pool of candidate trains. Then, considering constraints such as flow balance, station capacity, and train transport capacity, we formulated an integer programming model with 0-1 variables. The objective is to minimize train operation costs and freight transfer fees, determining the origin and destination stations and the operating frequency of freight trains. To address the structural characteristics of the model, an integer Benders decomposition-based branch-and-cut algorithm (IBD-BCA) is proposed. This algorithm, within the framework of branch-and-bound, solves the master problem decomposed by Benders and adds two sets of integer Benders cuts to achieve the optimal solution of the model. To demonstrate the effectiveness and performance of the model and algorithm, numerical experiments were conducted based on actual data from the main high-speed railway network in China. The results show that the IBD-BCA in this study can obtain optimal solutions within a reasonable time and requires adding a relatively small number of cuts during the search process. Compared with branch-and-bound algorithms and direct solving using Gurobi, the IBD-BCA proposed maintains sufficient efficiency when dealing with large-scale problems. Additionally, sensitivity analyses of parameters such as capacity and costs validate the robustness and scalability of the presented model and algorithm.

关键词： High-speed railway Freight transportation Train line plan Benders decomposition branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Integer programming model and branch-and-cut algorithm for the stack inbound and pre-marshalling problem

引用

COMPUTERS & OPERATIONS RESEARCH 2023年第1期155卷

作者： Wu, Lebao Jiang, Zuhua Wang, Fuhua Shanghai Jiao Tong Univ Dept Ind Engn & Management Shanghai 200240 Peoples R China

The steel plate yard of shipbuilding separates the inbound and pre-processing operations, increasing the number of moves. This paper considers the mixed inbound and pre-processing operation and studies the stack inbound and pre-marshalling problem where storage and relocation moves can alternate. This problem aims to find a minimum operation to store all inbound plates while eliminating all blocking plates. We propose a novel integer programming model combining two moves in one time period. This model reduces the number of periods, thereby decreasing the model size, but requires extra constraints to avoid infeasible patterns. An exact branch-and-cut algorithm is introduced to tackle the influence of these extra constraints. This paper provides a new modeling approach for stack-related problems, and the experiments show that the proposed method outperforms other ILP-based methods in the literature.

关键词： Stack inbound Pre-marshalling problem Integer programming model branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：