The widest k -set of disjoint paths problem Ribeiro, Marco Antônio; Carvalho, Iago Augusto; Pereira, Armando Honório
R.A.I.R.O. Recherche opérationnelle,
01/2023, Volume:
57, Issue:
1
Journal Article
Peer reviewed
Open access
Finding disjoint and widest paths are key problems in telecommunication networks. In this paper, we study the Widest
k
-set of Disjoint Paths Problem (WKDPP), an
NP
-Hard optimization problem that ...considers both aspects. Given a digraph
G
= (
N
,
A
), WKDPP consists of computing
k
arc-disjoint paths between two nodes such that the sum of its minimum capacity arcs is maximized. We present three mathematical formulations for WKDPP, a symmetry-breaking inequality set, and propose two heuristic algorithms. Computational experiments compare the proposed heuristics with another from the literature to show the effectiveness of the proposed methods.
•A linear integer programming formulation and valid inequalities for the PDTSPMS.•Separation methods and strategies to improve the performance of the branch-and-cut.•Branch-and-cut that includes the ...valid inequalities and strategies.•The branch-and-cut outperforms all the other existing algorithms for the PDTSPMS.
The focus of this work is the study of valid inequalities and exact algorithms for the pickup and delivery traveling salesman problem with multiple stacks. In the problem, a single vehicle must fulfill a set of client requests. Each request states that the vehicle must pick up an item at a given location, and later deliver it to another particular location. Inside the vehicle, items are stored in horizontal stacks of limited capacity. The loading and unloading operations of items follow the last-in-first-out policy. Every item is picked up on top of a stack and can only be delivered if it is also on top of its stack. The goal of this problem is to find a vehicle route of minimum cost. We propose a new formulation along with new valid inequalities for the problem. Several of these valid inequalities are lifted versions of inequalities previously proposed in the literature. The branch-and-cut algorithm based on the formulation and the valid inequalities is compared with the state-of-the-art solution methods for the problem. Computational experiments performed on benchmark instances show that the implemented algorithm outperforms all other competing exact algorithms for this problem.
Abstract
Given a connected digraph, a vertex designated as the root, and an integer
, the
‐arborescence star problem is to choose
vertices besides the root and define a reverse arborescence spanning ...them. Each vertex outside the arborescence must be assigned to one vertex inside it. The objective of the problem is to minimize arborescence and assignment costs. We propose two formulations for the problem and prove theoretical results about their strength. Moreover, we develop branch‐and‐cut algorithms based on each one of the formulations and improve an earlier branch‐and‐cut algorithm for the problem with an exact separation method. Additionally, we show that finding a feasible solution for an arbitrary instance is NP‐hard and introduce preprocessing procedures for the problem. The proposed algorithms are evaluated with a set of benchmark instances from the literature. For small and medium‐sized instances, our proposed algorithms provide the best results when compared to the existing algorithm from the literature. For large instances, the proposed algorithms are shown to be competitive with the existing approach.
Given a connected digraph, a vertex designated as the root, and an integer p$p$, the p$p$‐arborescence star problem is to choose p$p$ vertices besides the root and define a reverse arborescence ...spanning them. Each vertex outside the arborescence must be assigned to one vertex inside it. The objective of the problem is to minimize arborescence and assignment costs. We propose two formulations for the problem and prove theoretical results about their strength. Moreover, we develop branch‐and‐cut algorithms based on each one of the formulations and improve an earlier branch‐and‐cut algorithm for the problem with an exact separation method. Additionally, we show that finding a feasible solution for an arbitrary instance is NP‐hard and introduce preprocessing procedures for the problem. The proposed algorithms are evaluated with a set of benchmark instances from the literature. For small and medium‐sized instances, our proposed algorithms provide the best results when compared to the existing algorithm from the literature. For large instances, the proposed algorithms are shown to be competitive with the existing approach.
