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

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

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for hub network design problems with profits

引用

NAVAL RESEARCH LOGISTICS 2022年第4期69卷 622-639页

作者： Gao, Yuan Xia, Jun Ke, Hua Beijing Inst Technol Sch Management & Econ Beijing Peoples R China Shanghai Jiao Tong Univ Antai Coll Econ & Management Sino US Global Logist Inst Shanghai 200030 Peoples R China Tongji Univ Sch Econ & Management Shanghai 200092 Peoples R China

Hub network design problems with profits (HNDPPs) extend the classical hub location problems (HLPs), with the profit maximization objective. HNDPPs aim to design a service network with hub nodes and hub links, select the commodities to be served, and determine the transportation routes for the selected commodities. In this article, we allow the transportation route of each commodity to contain more than one hub link, which generalizes existing HNDPPs and is known to be more profitable. A new path-based formulation is proposed, which is then reformulated in a Benders decomposition fashion, and an exact branch-and-cut algorithm is developed to solve the Benders master problem. At the nodes of the enumeration tree, Benders decomposition algorithm is used to solve a linear relaxation of the Benders master problem. When implementing the Benders decomposition algorithm, the special structure of the subproblem is explored, based on which an efficient method is proposed to generate Benders cuts. In addition, refinements and a heuristic strategy are used to speed up the branch-and-cut algorithm. Extensive numerical experiments on benchmark instances have been carried out to verify the effectiveness and efficiency of the proposed solution method.

关键词： benders decomposition branch-and-cut algorithm hub network design problems with profits mixed integer linear programming

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On optimally solving sub-tree scheduling for wireless sensor networks with partial coverage: A branch-and-cut algorithm

引用

NETWORKS 2023年第4期81卷 499-513页

作者： Bianchessi, Nicola Univ Milan Dipartimento Informat Milan Italy Univ Milan Dipartimento Informat Via Celoria 18 I-20133 Milan Italy

Given a wireless sensor network, we consider the problem to minimize its total energy consumption over consecutive time slots with respect to communication activities. Nonempty and disjoint subsets of nodes are required to be active and connected under a tree topology configuration in the different time slots, and each network node must be active in a unique time slot. Moreover, the power required by the same pair of network nodes to communicate on the associated direct channel may vary in the different time slots. The problem has been recently introduced in the literature under the name Sub-Tree Scheduling for Wireless Sensor Networks with Partial Coverage. We focus on the exact solution of the problem. We present a branch-and-cut (BC) algorithm based on a novel integer linear programming formulation which allows avoiding the introduction of symmetries in the solution space. In particular, the algorithm relies on an efficient and nontypical separation algorithm for known valid inequalities, and on an easy-to-implement primal bound heuristic. The effectiveness of the BC algorithm is empirically shown through an extensive experimental analysis involving 300 newly generated benchmark instances with up to 200 network nodes and 8 time slots. Additionally, the experimental results show that the BC algorithm represents a valid computational tool to benchmark the performance of heuristics addressing the problem, and can be used in practice, as an heuristic solver, to tackle problem instances that are not too large.

关键词： branch-and-cut algorithm consecutive time slots energy consumption minimization partial coverage sub-tree scheduling wireless sensor network

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for a bipartite graph construction problem in digital communication systems

引用

NETWORKS 2020年第2期75卷 137-157页

作者： Kabakulak, Banu Taskin, Z. Caner Pusane, Ali E. Bogazici Univ Dept Ind Engn Istanbul Turkey Bogazici Univ Dept Elect & Elect Engn Istanbul Turkey

We study a bipartite graph (BG) construction problem that arises in digital communication systems. In a digital communication system, information is sent from one place to another over a noisy communication channel using binary symbols (bits). The original information is encoded by adding redundant bits, which are then used to detect and correct errors that may have been introduced during transmission. Harmful structures, such as small cycles, severely deteriorate the error correction capability of a BG. We introduce an integer programming formulation to generate a BG for a given smallest cycle length. We propose a branch-and-cut algorithm for its solution and investigate the structural properties of the problem to derive valid inequalities and variable fixing rules. We also introduce heuristics to obtain feasible solutions for the problem. The computational experiments show that our algorithm can generate BGs without small cycles in an acceptable amount of time for practically relevant dimensions.

关键词： bipartite graphs branch-and-cut algorithm integer programming symmetry telecommunications valid inequalities

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for the Team Orienteering Problem

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2018年第2期25卷 627-635页

作者： Bianchessi, Nicola Mansini, Renata Speranza, M. Grazia Johannes Gutenberg Univ Mainz Gutenberg Sch Management & Econ Chair Logist Management Jakob Welder Weg 9 D-55128 Mainz Germany Univ Brescia Dept Informat Engn Via Branze 38 I-25123 Brescia Italy Univ Brescia Dept Econ & Management Cda S Chiara 50 I-25122 Brescia Italy

The Team Orienteering Problem aims at maximizing the total amount of profit collected by a fleet of vehicles while not exceeding a predefined travel time limit on each vehicle. In the last years, several exact methods based on different mathematical formulations were proposed. In this paper, we present a new two-index formulation with a polynomial number of variables and constraints. This compact formulation, reinforced by connectivity constraints, was solved by means of a branch-and-cut algorithm. The total number of instances solved to optimality is 327 of 387 benchmark instances, 26 more than any previous method. Moreover, 24 not previously solved instances were closed to optimality.

关键词： Team Orienteering Problem two-index mathematical formulation branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：