Wei Wu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Wei Wu has a total of 29 co-authors. Here are the top co-authors by number of shared publications:
- Mutsunori Yagiura
Graduate School of Informatics, Nagoya University, Nagoya, Aichi, Japan
6 shared publications Andrea Pizzuti
2 shared publicationsLiang Tang
2 shared publications- Manuel Iori
DISMI University of Modena and Reggio Emilia Reggio Emilia Italy
2 shared publications Mutsunori Yagiura
Nagoya Univ, Grad Sch Informat, Furo Cho,Chikusa Ku, Nagoya, Aichi 4648601, Japan
2 shared publicationsSilvano Martello
DEI “Guglielmo Marconi”, Alma Mater Studiorum University of Bologna, 40126 Bologna, Italy
2 shared publications
Latest Publications
- Open Access
- 7 April 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 13, 63952-63968
New Heuristic Approaches for the Min–Max Regret Traveling Salesman Problem
The traveling salesman problem (TSP) is widely known as one of the most important NP-hard combinatorial optimization problems. In this paper, we consider the min–max regret traveling salesman problem (MMR-TSP) with interval travel costs. The MMR-TSP aims to find a tour that minimizes the difference between its objective function value and the optimal value of the case in which the real scenario is known in advance. We examine five methods: a Benders-like decomposition method, a branch-and-cut algorithm, a fixed-scenario method, an iterated dual substitution method, and a gravitational search algorithm. For the iterated dual substitution method, we discuss several possible implementations based on different mathematical models for the classical TSP. We further propose a new heuristic approach, which we call the core selection algorithm. The experimental results show that the proposed core selection algorithm achieved superior performance compared to all other methods we examined for benchmark instances up to 80 cities. Furthermore, for the instances with 1000 cites, our new algorithm obtained high-quality solutions with an average optimality gap of 2.7%, whereas existing methods failed to obtain feasible solutions or only obtained solutions with an average optimality gap above 100%.
- 7 April 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 13, 63952-63968
Open AccessNew Heuristic Approaches for the Min–Max Regret Traveling Salesman Problem
The traveling salesman problem (TSP) is widely known as one of the most important NP-hard combinatorial optimization problems. In this paper, we consider the min–max regret traveling salesman problem (MMR-TSP) with interval travel costs. The MMR-TSP aims to find a tour that minimizes the difference between its objective function value and the optimal value of the case in which the real scenario is known in advance. We examine five methods: a Benders-like decomposition method, a branch-and-cut algorithm, a fixed-scenario method, an iterated dual substitution method, and a gravitational search algorithm. For the iterated dual substitution method, we discuss several possible implementations based on different mathematical models for the classical TSP. We further propose a new heuristic approach, which we call the core selection algorithm. The experimental results show that the proposed core selection algorithm achieved superior performance compared to all other methods we examined for benchmark instances up to 80 cities. Furthermore, for the instances with 1000 cites, our new algorithm obtained high-quality solutions with an average optimality gap of 2.7%, whereas existing methods failed to obtain feasible solutions or only obtained solutions with an average optimality gap above 100%.
- 22 November 2024
- Published by Elsevier in European Journal of Operational Research
- Vol. 322 (3) , 770-782
One-dimensional bin packing with pattern-dependent processing time
- 22 November 2024
- Published by Elsevier in European Journal of Operational Research
- Vol. 322 (3) , 770-782
One-dimensional bin packing with pattern-dependent processing time
- 16 October 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 1024
Packing squares independently
- 16 October 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 1024
Packing squares independently
- 26 January 2024
- Published by Elsevier in Information Processing Letters
- Vol. 186
Robust scheduling for minimizing maximum lateness on a serial-batch processing machine
- 26 January 2024
- Published by Elsevier in Information Processing Letters
- Vol. 186
Robust scheduling for minimizing maximum lateness on a serial-batch processing machine
- 1 September 2023
- Published by Elsevier in Computers & Operations Research
- Vol. 161
Heuristic algorithms based on column generation for an online product shipping problem
- 1 September 2023
- Published by Elsevier in Computers & Operations Research
- Vol. 161
Heuristic algorithms based on column generation for an online product shipping problem
- 29 September 2022
- Published by Elsevier in European Journal of Operational Research
- Vol. 307 (1) , 82-102
Exact algorithms based on a constrained shortest path model for robust serial-batch and parallel-batch scheduling problems
- 29 September 2022
- Published by Elsevier in European Journal of Operational Research
- Vol. 307 (1) , 82-102
Exact algorithms based on a constrained shortest path model for robust serial-batch and parallel-batch scheduling problems
- 1 September 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 34 (5) , 2523-2539
An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion
We consider binary integer programming problems with the min-max regret objective function under interval objective coefficients. We propose a heuristic framework, the iterated dual substitution (iDS) algorithm, which iteratively invokes a dual substitution heuristic and excludes from the search space any solution already checked in previous iterations. In iDS, we use a best scenario–based lemma to improve performance. We apply iDS to four typical combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the generalized assignment problem, and the set covering problem. For the multidimensional knapsack problem, we compare the iDS approach with two algorithms widely used for problems with the min-max regret criterion: a fixed-scenario approach, and a branch-and-cut approach. The results of computational experiments on a broad set of benchmark instances show that the proposed iDS approach performs best on most tested instances. For the knapsack problem, the generalized assignment problem, and the set covering problem, we compare iDS with state-of-the-art results. The iDS algorithm successfully updates best-known records for a number of benchmark instances. Summary of Contribution: This paper proposes a heuristic framework for binary integer programming (BIP) problems with the min-max regret objective function under interval objective coefficients. We selected four representative NP-hard combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the set covering problem, and the generalized assignment problem. We show the effectiveness and efficiency of the approach by comparing with state-of-the-art results.
- 1 September 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 34 (5) , 2523-2539
An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion
We consider binary integer programming problems with the min-max regret objective function under interval objective coefficients. We propose a heuristic framework, the iterated dual substitution (iDS) algorithm, which iteratively invokes a dual substitution heuristic and excludes from the search space any solution already checked in previous iterations. In iDS, we use a best scenario–based lemma to improve performance. We apply iDS to four typical combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the generalized assignment problem, and the set covering problem. For the multidimensional knapsack problem, we compare the iDS approach with two algorithms widely used for problems with the min-max regret criterion: a fixed-scenario approach, and a branch-and-cut approach. The results of computational experiments on a broad set of benchmark instances show that the proposed iDS approach performs best on most tested instances. For the knapsack problem, the generalized assignment problem, and the set covering problem, we compare iDS with state-of-the-art results. The iDS algorithm successfully updates best-known records for a number of benchmark instances. Summary of Contribution: This paper proposes a heuristic framework for binary integer programming (BIP) problems with the min-max regret objective function under interval objective coefficients. We selected four representative NP-hard combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the set covering problem, and the generalized assignment problem. We show the effectiveness and efficiency of the approach by comparing with state-of-the-art results.
- 21 April 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Code and Data Repository for An Iterated Dual Substitution Approach for Binary Integer Programming Problems under the Min–Max Regret Criterion
The software and data in this repository are a snapshot of the software and data that were used in the research reported in the paper An iterated dual substitution approach for min-max binary integer programming by W. Wu, M. Iori, S. Martello, and M. Yagiura.
- 21 April 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Code and Data Repository for An Iterated Dual Substitution Approach for Binary Integer Programming Problems under the Min–Max Regret Criterion
The software and data in this repository are a snapshot of the software and data that were used in the research reported in the paper An iterated dual substitution approach for min-max binary integer programming by W. Wu, M. Iori, S. Martello, and M. Yagiura.
- 1 November 2018
- Published by Elsevier in Computers & Industrial Engineering
- Vol. 125, 98-110
Exact and heuristic algorithms for the interval min-max regret generalized assignment problem
- 1 November 2018
- Published by Elsevier in Computers & Industrial Engineering
- Vol. 125, 98-110
Exact and heuristic algorithms for the interval min-max regret generalized assignment problem