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

A branch-and-cut algorithm for the symmetric generalized traveling salesman problem

OPERATIONS RESEARCH 1997年第3期45卷 378-394页

作者： Fischetti, M Gonzalez, JJS Toth, P UNIV LA LAGUNA SCH MATHE-38207 LA LAGUNASPAIN UNIV PADUA I-35100 PADUAITALY UNIV BOLOGNA SCH ENGNI-40126 BOLOGNAITALY

We consider a variant of the classical symmetric Traveling Salesman Problem in which the nodes are partitioned into clusters and the salesman has to visit at least one node for each cluster. This NP-hard problem is known in the literature as the symmetric Generalized Traveling Salesman Problem (GTSP), and finds practical applications in routing, scheduling and location-routing. In a companion paper (Fischetti et al. 1995) we modeled GTSP as an integer linear program, and studied the facial structure of two polytopes associated with the problem. Here we propose exact and heuristic separation procedures for some classes of facet-defining inequalities, which are used within a branch-and-cut algorithm for the exact solution of GTSP. Heuristic procedures are also described. Extensive computational results for instances taken from the literature and involving up to 442 nodes are reported.

关键词： networks/graphs generalized traveling salesman programming integer cutting plane branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Revisiting the Hamiltonian p-median problem: A new formulation on directed graphs and a branch-and-cut algorithm

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2019年第1期276卷 40-64页

作者： Bektas, Tolga Gouveia, Luis Santos, Daniel Univ Liverpool Sch Management Chatham St Liverpool L69 7ZH Merseyside England Univ Lisbon Fac Ciencias Ctr Matemat Aplicacoes Fundamentais & Invest Oper C6 Piso 4 P-1749016 Lisbon Portugal

This paper studies the asymmetric Hamiltonian p-median problem, which consists of finding p mutually disjoint circuits of minimum total cost in a directed graph, such that each node of the graph is included in one of the circuits. Earlier formulations view the problem as the intersection of two subproblems, one requiring at most p, and the other requiring at least p circuits, in a feasible solution. This paper makes an explicit connection between the first subproblem and subtour elimination constraints of the traveling salesman problem, and between the second subproblem and the so-called path elimination constraints that arise in multi-depot/location-routing problems. A new formulation is described that builds on this connection, that uses the concept of an acting depot, resulting in a new set of constraints for the first subproblem, and a strong set of (path elimination) constraints for the second subproblem. The variables of the new model also allow for effective symmetry-breaking constraints to deal with two types of symmetries inherent in the problem. The paper describes a branch-and-cut algorithm that uses the new constraints, for which separation procedures are proposed. Theoretical and computational comparisons between the new formulation and an adaptation of an existing formulation originally proposed for the symmetric Hamiltonian p-median problem are presented. Computational results indicate that the algorithm is able to solve asymmetric instances with up to 171 nodes and symmetric instances with up to 100 nodes. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Hamiltonian p-median Multi-cut inequalities Multi-depot routing branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2023年第2期309卷 488-505页

作者： Khachai, Daniil Sadykov, Ruslan Battaia, Olga Khachay, Michael Kedge Business Sch 680 Cours Liberat Talence France Univ Bordeaux Inria Ctr 200 Ave Vieille Tour Talence France RAS Ivannikov Inst Syst Programming Moscow Russia

The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) is an extension of two well-known combinatorial optimization problems - the Generalized Traveling Salesman Problem (GTSP) and the Precedence Constrained Asymmetric Traveling Salesman Problem (PCATSP), whose path version is known as the Sequential Ordering Problem (SOP). Similarly to the classic GTSP, the goal of the PCGTSP, for a given input digraph and partition of its node set into clusters, is to find a minimum cost cyclic route (tour) visiting each cluster in a single node. In addition, as in the PCATSP, feasible tours are restricted to visit the clusters with respect to the given partial order. Unlike the GTSP and SOP, to the best of our knowledge, the PCGTSP still remain to be weakly studied both in terms of polyhedral theory and algo-rithms. In this paper, for the first time for the PCGTSP, we propose several families of valid inequalities, establish dimension of the PCGTS polytope and prove sufficient conditions ensuring that the extended Balas' pi- and sigma-inequalities become facet-inducing. Relying on these theoretical results and evolving the state-of-the-art algorithmic approaches for the PCATSP and SOP, we introduce a family of MILP-models (formulations) and several variants of the branch-and-cut algorithm for the PCGTSP. We prove their high performance in a competitive numerical evaluation against the public benchmark library PCGTSPLIB, a known adaptation of the classic SOPLIB to the problem in question. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Travelling salesman Integer programming branch-and-cut algorithm Facet-inducing inequalities Polyhedral structure

来源：评论

学校读者我要写书评

暂无评论

Balanced vehicle routing: Polyhedral analysis and branch-and-cut algorithm

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2019年第2期273卷 452-463页

作者： Bektas, Tolga Gouveia, Luis Martinez-Sykora, Antonio Salazar-Gonzalez, Juan-Jose Univ Southampton Southampton Business Sch CORMSIS Southampton SO17 1BJ Hants England Univ Lisbon Fac Ciencias DEIO Ctr Invest Operac Bloco C-2 Campo GrandeCidade Univ P-1749016 Lisbon Portugal Univ La Laguna DMEIO Tenerife 38200 Spain

This paper studies a variant of the unit-demand Capacitated Vehicle Routing Problem, namely the Balanced Vehicle Routing Problem, where each route is required to visit a maximum and a minimum number of customers. A polyhedral analysis for the problem is presented, including the dimension of the associated polyhedron, description of several families of facet-inducing inequalities and the relationship between these inequalities. The inequalities are used in a branch-and-cut algorithm, which is shown to computationally outperform the best approach known in the literature for the solution of this problem. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Routing Balanced Polyhedral study branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for the profitable windy rural postman problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2016年第3期249卷 1092-1101页

作者： Avila, Thais Corberan, Angel Plana, Isaac Sanchis, Jose M. Univ Valencia Dept Estadist & Invest Operat E-46003 Valencia Spain Univ Valencia Dept Matemat Econ & Empresa E-46003 Valencia Spain Univ Politecn Valencia Dept Matemat Aplicada E-46022 Valencia Spain

In this paper we study the profitable windy rural postman problem. This is an arc routing problem with profits defined on a windy graph in which there is a profit associated with some of the edges of the graph, consisting of finding a route maximizing the difference between the total profit collected and the total cost. This problem generalizes the rural postman problem and other well-known arc routing problems and has real-life applications, mainly in snow removal operations. We propose here a formulation for the problem and study its associated polyhedron. Several families of facet-inducing inequalities are described and used in the design of a branch-and-cut procedure. The algorithm has been tested on a large set of benchmark instances and compared with other existing algorithms. The results obtained show that the branch-and-cut algorithm is able to solve large-sized instances optimally in reasonable computing times. (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.

关键词： Windy rural postman problem Arc routing Profits branch-and-cut algorithm Polyhedron

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for the capacitated profitable tour problem

引用

DISCRETE OPTIMIZATION 2014年 14卷 78-96页

作者： Jepsen, Mads Kehlet Petersen, Bjorn Spoorendonk, Simon Pisinger, David Tech Univ Denmark DTU Management Engn DK-2800 Lyngby Denmark

This paper considers the Capacitated Profitable Tour Problem (CPTP) which is a special case of the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). The CPTP belongs to the group of problems known as traveling salesman problems with profits. In CPTP each customer is associated with a profit and a demand and the objective is to find a capacitated tour (rooted in a depot node) that minimizes the total travel distance minus the profit of the visited customers. The CPTP can be recognized as the sub-problem in many column generation applications, where it is traditionally solved through dynamic programming. In this paper we present an alternative framework based on a formulation for the undirected CPTP and solved through branch-and-cut. Valid inequalities are presented among which we introduce a new family of inequalities for the CPTP denoted rounded multistar inequalities and we prove their validity. Computational experiments are performed on a set of instances known from the literature and a set of newly generated instances. The results indicate that the presented algorithm is highly competitive with the dynamic programming algorithms. In particular, we are able to solve instances with 800 nodes to optimality where the dynamic programming algorithms cannot solve instances with more than 200 nodes. Moreover dynamic programming and branch-and-cut complement each other well, giving us hope for solving more general problems through hybrid approaches. The paper is intended to serve as a platform for further development of branch-and-cut algorithms for CPTP hence also acting as a survey/tutorial. (C) 2014 Elsevier B.V. All rights reserved.

关键词： branch-and-cut algorithm Valid inequalities Profitable tour problem Capacitated shortest path problem Traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

Polyhedral results and a branch-and-cut algorithm for the k-cardinality tree problem

引用

MATHEMATICAL PROGRAMMING 2013年第1-2期142卷 511-538页

作者： Simonetti, Luidi da Cunha, Alexandre Salles Lucena, Abilio Univ Fed Fluminense Inst Comp Rio De Janeiro Brazil Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte MG Brazil Univ Fed Rio de Janeiro Dept Adm Programa Engn Sistemas & Comp Rio De Janeiro Brazil

Given an undirected graph G with vertex and edge weights, the k-cardinality tree problem asks for a minimum weight tree of G containing exactly k edges. In this paper we consider a directed graph reformulation of the problem and carry out a polyhedral investigation of the polytope defined by the convex hull of its feasible integral solutions. Three new families of valid inequalities are identified and two of them are proven to be facet implying for that polytope. Additionally, a branch-and-cut algorithm that separates the new inequalities is implemented and computationally tested. The results obtained indicate that our algorithm outperforms its counterparts from the literature. Such a performance could be attributed, to a large extent, to the use of the new inequalities and also to some pre-processing tests introduced in this study.

关键词： branch-and-cut algorithm Polyhedral study k-Cardinality tree problem

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2020年第4期12卷 529-568页

作者： Tahernejad, Sahar Ralphs, Ted K. DeNegre, Scott T. Lehigh Univ Dept Ind & Syst Engn Bethlehem PA 18015 USA Hosp Special Surg 535 E 70th St New York NY 10021 USA

In this paper, we describe a comprehensive algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) using a generalized branch-and-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer linear optimization and MIBLPs) with new techniques to produce a flexible and robust framework capable of solving a wide range of bilevel optimization problems. The framework has been fully implemented in the open-source solver MibS. The paper describes the algorithmic options offered by MibS and presents computational results evaluating the effectiveness of the various options for the solution of a number of classes of bilevel optimization problems from the literature.

关键词： Bilevel optimization Mixed integer optimization branch-and-cut algorithm Open-source solver

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2020年第2期75卷 493-513页

作者： Kobayashi, Ken Takano, Yuich Fujitsu Labs LTD. Artificial Intelligence LabNakahara-ku 4-1-1 Kamikodanaka Kawasaki Kanagawa 2118588 Japan Univ Tsukuba Fac Engn Informat Syst 1-1-1 Tennodai Tsukuba Shi Ibaraki 3058577 Japan

We consider a cutting-plane algorithm for solving mixed-integer semidefinite optimization (MISDO) problems. In this algorithm, the positive semidefinite (psd) constraint is relaxed, and the resultant mixed-integer linear optimization problem is solved repeatedly, imposing at each iteration a valid inequality for the psd constraint. We prove the convergence properties of the algorithm. Moreover, to speed up the computation, we devise a branch-and-cut algorithm, in which valid inequalities are dynamically added during a branch-and-bound procedure. We test the computational performance of our cutting-plane and branch-and-cut algorithms for three types of MISDO problem: random instances, computing restricted isometry constants, and robust truss topology design. Our experimental results demonstrate that, for many problem instances, our branch-and-cut algorithm delivered superior performance compared with general-purpose MISDO solvers in terms of computational efficiency and stability.

关键词： Mixed-integer optimization Semidefinite optimization cutting-plane algorithm branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：