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

The Hamiltonian p-median problem: Polyhedral results and branch-and-cut algorithms

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第2期316卷 473-487页

作者： Barbato, Michele Gouveia, Luis Univ Milan Dipartimento Informat Giovanni Degli Antoni Via Celoria 18 I-20133 Milan Italy Univ Lisbon Fac Ciencias Ctr Matemat Aplicacoes Fundamentais & Invest Opera C6 Piso 4 P-1749016 Lisbon Portugal

In this paper we study the Hamiltonian p-median problem, in which we are given an edge-weighted graph and we are asked to determine p vertex-disjoint cycles spanning all vertices of the graph and having minimum total weight. We introduce two new families of valid inequalities for a formulation of the problem in the space of edge variables. Each one of the families forbids solutions to the 2-factor relaxation of the problem that have less than.. cycles. The inequalities in one of the families are associated with large cycles of the underlying graph and generalize known inequalities associated with Hamiltonian cycles. The other family involves inequalities for the case with p = (sic)n/3(sic), associated with edge cuts and multi-cuts whose shores have specific cardinalities. We identify inequalities from both families that define facets of the polytope associated with the problem. We design branch-and-cut algorithms based on these families of inequalities and on inequalities associated with 2-opt moves removing sub-optimal solutions. Computational experiments on benchmark instances show that the proposed algorithms exhibit a comparable performance with respect to existing exact methods from the literature. Moreover the algorithms solve to optimality new instances with up to 400 vertices.

关键词： Combinatorial optimization Hamiltonian p-median problem Valid inequality Polyhedral study branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Discrete cutting path problems: a general solution framework and industrial applications

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2025年第3期63卷 949-969页

作者： Khachai, Daniil Battaia, Olga Petunin, Alexander Khachay, Michael Kedge Business Sch 680 Cours Liberat Talence France Ural Fed Univ Ekaterinburg Russia NN Krasovskii Inst Math & Mech Ekaterinburg Russia RAS Ivannikov Inst Syst Programming Moscow Russia

The optimal tool routing for cutting machines, also known as cutting path optimisation is an important problem in production research. This problem is relevant in various manufacturing environments such as aeronautic, automotive, garment and semiconductor industries. In this paper, we introduce a general solution framework for the discrete cutting Path Problem which includes: (i) the universal approach to reduce numerous settings of this problem to the appropriate auxiliary instances of the well-known Precedence Constrained Generalized Traveling Salesman Problem;(ii) the proposition of efficient solution methods for finding (sub-) optimal solutions. We carry out extensive computational experiments in order to evaluate performance of the proposed framework and the obtained results demonstrate its efficiency for real-life industrial instances.

关键词： cutting path problem endpoint cutting problem precedence constrained generalised travelling salesman problem branch-and-cut algorithm adaptive large neighbourhood search industry innovation and infrastructure

来源：评论

学校读者我要写书评

暂无评论

Optimization algorithms for the k edge-connected L-hop-constrained network design problem

引用

SOFT COMPUTING 2024年第11-12期28卷 7201页

作者： Diarrassouba, I. Mahjoub, A. R. Almudahka, I. M. Normandie Univ UNIHAVRE LMAH FR 3335CNRS F-76600 Le Havre France Kuwait Univ Coll Sci Dept Stat & Operat Res Kuwait Kuwait Univ Paris 09 Lab LAMSADE CNRSUMR 7243 PSL Pl Marechal Lattre Tassigny F-75775 Paris 16 France

In this paper, we study the k edge-connected L-hop-constrained network design problem. Given a weighted graph G=(V,E), a set D of pairs of nodes, two integers L >= 2 and k >= 2, the problem consists in finding a minimum weight subgraph of G containing at least k edge-disjoint paths of length at most L between every pair {s,t} of D. The problem has several applications in telecommunications network design. It also has applications in reliable container transportation network design and public transportation. Even if the problem has been studied for several decades, it appears, to the best of our knowledge, that the associated polytope is not well known, even when L is an element of{2,3}. In this paper, we are particularly interested in the polyhedral analysis of the problem as well as an exact solving of the problem for large-scale instances. We consider the case where L is an element of{2,3} and present two integer programming formulations introduced in Diarrassouba et al. (2016). Then, we consider the polytope associated with these formulations, and present several new classes of valid inequalities, involving the so-called design variables. We also present separation algorithms for these inequalities and devise branch-and-cut algorithms for solving the problem. Finally, we present an extensive computational study for L is an element of{2,3} and k is an element of{3,4,5}, in which we test the efficiency of our branch-and-cut algorithms. We also compare the algorithm against a resolution using CPLEX branch-and-cut and CPLEX Benders Decomposition frameworks. The results show that our branch-and-cut algorithm can be competitive against these two frameworks.

关键词： Hop-constrained survivable network Edge-disjoint paths Hop-constrained path Valid inequalities branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Beyond symmetry: best submatrix selection for the sparse truncated SVD

引用

MATHEMATICAL PROGRAMMING 2024年第1-2期208卷 1-50页

作者： Li, Yongchun Xie, Weijun Georgia Inst Technol Atlanta GA 30332 USA

The truncated singular value decomposition (SVD), also known as the best low-rank matrix approximation with minimum error measured by a unitarily invariant norm, has been applied to many domains such as biology, healthcare, among others, where high-dimensional datasets are prevalent. To extract interpretable information from the high-dimensional data, sparse truncated SVD (SSVD) has been used to select a handful of rows and columns of the original matrix along with the best low-rank approximation. Different from the literature on SSVD focusing on the top singular value or compromising the sparsity for the seek of computational efficiency, this paper presents a novel SSVD formulation that can select the best submatrix precisely up to a given size to maximize its truncated Ky Fan norm. The fact that the proposed SSVD problem is NP-hard motivates us to study effective algorithms with provable performance guarantees. To do so, we first reformulate SSVD as a mixed-integer semidefinite program, which can be solved exactly for small- or medium-sized instances within a branch-and-cut algorithm framework with closed-form cuts and is extremely useful for evaluating the solution quality of approximation algorithms. We next develop three selection algorithms based on different selection criteria and two searching algorithms, greedy and local search. We prove the approximation ratios for all the approximation algorithms and show that all the ratios are tight when the number of rows or columns of the selected submatrix is no larger than half of the data matrix, i.e., our derived approximation ratios are unimprovable. Our numerical study demonstrates the high solution quality and computational efficiency of the proposed algorithms. Finally, all our analysis can be extended to row-sparse PCA.

关键词： Sparse truncated SVD Mixed-integer semidefinite program branch-and-cut algorithm Approximation algorithms Row-sparse PCA

来源：评论

学校读者我要写书评

暂无评论

The family capacitated vehicle routing problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第3期314卷 836-853页

作者： Bernardino, Raquel Paias, Ana Univ Lisbon ISEG Sch Econ & Management Lisbon Portugal CEMAPRE REM Res Econ & Math Lisbon Portugal Univ Lisbon Fac Ciencias DEIO C6Piso 4 P-1749016 Lisbon Portugal Univ Lisbon Fac Ciencias CMAFcIO Lisbon Portugal

In this article, we address the family capacitated vehicle routing problem (F-CVRP), an NP-hard problem that generalizes both the FTSP and the capacitated vehicle routing problem. The F-CVRP has practical application in warehouse management in warehouses with scattered storage. We present several mixed integer linear programming formulations for this problem and establish a theoretical and empirical comparison. We also propose valid inequalities adapted from known routing problems from the literature. Some formulations are solved using a branch-and-cut algorithm, which is tested with a newly generated data set. The computational experiment allows us to identify the instances' most challenging characteristics and the exact methods' limitations. Finally, we develop an iterated local search (ILS) algorithm to efficiently obtain feasible solutions for the instances that could not be solved to proven optimality. The ILS algorithm is very efficient and can improve the upper bounds obtained by the exact methods within the set time limit.

关键词： Routing Family traveling salesman problem Projection results branch-and-cut algorithm Iterated local search algorithm

来源：评论

学校读者我要写书评

暂无评论

Customized bus scheme design of large transport terminals with jointly optimization of departure time, vehicle allocation and routing

引用

IET INTELLIGENT TRANSPORT SYSTEMS 2023年第1期17卷 85-101页

作者： Wu, Yuelin Yuan, Zhenzhou Xiao, Qingyu Yang, Dong Beijing Jiaotong Univ Sch Traff & Transportat Key Lab Transport Ind Big Data Applicat Technol C Minist Transport 3 Shangyuan Village Beijing 100044 Peoples R China China Acad Transportat Sci Ctr Comprehens Transportat Beijing Peoples R China

The customized bus (CB) service of large transport terminals can provide passengers with convenient transfers and door-to-door services, which has the potential to help ease the pressure of arriving passenger flow in large transport terminals. Considering the costs of operators and passengers, this paper establishes a multi-commodity network flow optimization model to simultaneously obtain departure schedule, passenger-to-vehicle assignment and routing under the condition of multiple vehicle types. It provides more passengers with high-quality CB service and obtains higher vehicle capacity utilization. Accordingly, the solution is proposed that combines a branch-and-cut algorithm with grid-density-based clustering. An illustrative example verifies the effectiveness and tests the impact of the departure time-window. The case study of Chengdu city compares the results under different types of vehicle schemes and conducts the sensitivity analysis of penalty and minimum load ratio. The experiments conclude: (i) The proposed algorithm stably improves computation speed (76.38%) without affecting the optimal results;(ii) a loose time-window can serve more people, but the excessively loose one no longer has impacts on the results. (iii) The multi-type of vehicle scheme performs best compared to the single type of vehicle schemes.

关键词： transportation jointly optimization Optimisation techniques vehicle capacity utilization pattern clustering branch-and-cut algorithm vehicle routing multiple vehicle types Systems theory applications in transportation passenger flow departure time-window sensitivity analysis scheduling customized bus scheme design passenger-to-vehicle assignment Data handling techniques transport terminals door-to-door services convenient transfers customized bus service high-quality CB service Chengdu city multicommodity network flow optimization model vehicle scheme departure schedule loose time-window optimisation vehicle allocation road vehicles Combinatorial mathematics grid-density-based clustering

来源：评论

学校读者我要写书评

暂无评论

Models and algorithms for the Weighted Safe Set Problem

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期329卷 23-34页

作者： Malaguti, Enrico Pedrotti, Vagner Univ Bologna Dipartimento Ingn Energia Elettr & Informaz Guglie Bologna Italy Univ Fed Mato Grosso Fac Comp Campo Grande 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 neighbor connected component in the subgraph induced by S. 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 which can tackle the four variants of the problem which arise by imposing connectivity of the safe set, and by considering weighted or unweighted vertices, respectively. Despite alternative formulations from the literature, that require a large number of variables, our formulation only uses one variable per vertex. The formulation has an exponential number of constraints, which are needed to define the structure of the safe set, and can be generated on-the-fly within a branch-and-cut algorithm. We describe linear-time separation procedures for these constraints, as well as families of additional inequalities 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 the state-of-the-art alternative formulation from the literature, and shows faster in solving most of benchmark instances.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Safe Set Problem Weighted Safe Set Problem branch-and-cut algorithm Computational experiments

来源：评论

学校读者我要写书评

暂无评论

The inventory routing problem with split deliveries

引用

NETWORKS 2023年第4期82卷 400-413页

作者： Dinh, Nho Minh Archetti, Claudia Bertazzi, Luca Univ Brescia Dept Econ & Management Brescia Italy ESSEC Business Sch Dept Informat Syst Decis Sci & Stat Paris France

We study the benefit of introducing split deliveries in the inventory routing problem (IRP), both when the order-up-to level (OU) and the maximum level replenishment policies are applied. We first propose a mathematical formulation and solve it by implementing a branch-and-cut algorithm. Then, we carry out a worst-case analysis to show the cost increase we have in the worst case by using unsplit deliveries instead of split deliveries, both for the OU and the maximum-level replenishment policies. Extensive computational results on benchmark instances allow us to evaluate the benefit of introducing split deliveries. Finally, a sensitivity analysis on customer demands, initial inventory levels, maximum inventory levels and distance to the depot allows us to understand the instance features that make split deliveries effective in IRPs.

关键词： branch-and-cut algorithm inventory routing problems maximum-level order-up-to-level split deliveries worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：