Derek H. Smith
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
Derek H. Smith has a total of 53 co-authors. Here are the top co-authors by number of shared publications:
- Roberto Montemanni
Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy
36 shared publications - Stephanie Perkins
School of Computing and Mathematics, University of South Wales, Llantwit Rd, Pontypridd CF37 1DL, UK
15 shared publications S. Hurley
9 shared publications- Stuart M. Allen
School of Computer Science & Informatics, Cardiff University, Cardiff, UK
5 shared publications Roberto Montemanni
Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, Italy
3 shared publicationsA. Ryley
2 shared publications
Latest Publications
- Open Access
- 3 August 2026
- Published by MDPI AG in Algorithms
- Vol. 19 (8) , 643
Exact and Approximate Linear Models for the Multi-Vehicle Probabilistic Covering Tour Problem
The Multi-Vehicle Probabilistic Covering Tour Problem aims at designing the tours of a fleet of vehicles characterized by a limited range that has to distribute goods to some distribution facilities, in order for those goods to subsequently reach the final customers. Each truck distributes directly only to the facilities, and the delivered goods reach the final customers with a given probability. The aim of the problem is to maximize the expected quantity of goods delivered to the final customers. The problem can be modeled as a mixed integer program with a non-linear objective function, as already presented in the literature together with a solving method based on a linear model with an exponential number of constraints. The contributions of the present work are a new model and two new linear approximation models able to provide tight lower and upper bounds for the optimal solution of the original problem. An extensive computational campaign on the instances available in the literature validates the new approaches we propose, providing several improved heuristic solutions and upper bounds with respect to the previous state-of-the-art. Several instances are also closed here for the first time.
- 3 August 2026
- Published by MDPI AG in Algorithms
- Vol. 19 (8) , 643
Open AccessExact and Approximate Linear Models for the Multi-Vehicle Probabilistic Covering Tour Problem
The Multi-Vehicle Probabilistic Covering Tour Problem aims at designing the tours of a fleet of vehicles characterized by a limited range that has to distribute goods to some distribution facilities, in order for those goods to subsequently reach the final customers. Each truck distributes directly only to the facilities, and the delivered goods reach the final customers with a given probability. The aim of the problem is to maximize the expected quantity of goods delivered to the final customers. The problem can be modeled as a mixed integer program with a non-linear objective function, as already presented in the literature together with a solving method based on a linear model with an exponential number of constraints. The contributions of the present work are a new model and two new linear approximation models able to provide tight lower and upper bounds for the optimal solution of the original problem. An extensive computational campaign on the instances available in the literature validates the new approaches we propose, providing several improved heuristic solutions and upper bounds with respect to the previous state-of-the-art. Several instances are also closed here for the first time.
- Open Access
The Moore Graph of Diameter 2 and Degree 57 via Cyclic Derangements
The possible existence of a regular Moore graph of diameter 2 and degree 57 with the maximum number 3250 of vertices has been an open question for over 65 years. One approach to a construction focuses on the set of permutations that describe the 1-factors that give the adjacencies between leaf vertices of pairs of branches of a tree. Most of these permutations are derangements, that is they are permutations with no fixed points. As many products of 2, 3, or 4 of these derangements must also be derangements, it is tempting to use a group of derangements, that is a group of permutations in which every non-identity element is a derangement. The first case to consider is when the group of derangements is a cyclic group of permutations. In this paper it is proved that a construction using only a cyclic group of permutations is impossible. This leaves only the possibility of using some other group of derangements, or a set of derangements that do not form a group. The prospects for extending the work to these cases is considered at the end of the paper.
Open AccessThe Moore Graph of Diameter 2 and Degree 57 via Cyclic Derangements
The possible existence of a regular Moore graph of diameter 2 and degree 57 with the maximum number 3250 of vertices has been an open question for over 65 years. One approach to a construction focuses on the set of permutations that describe the 1-factors that give the adjacencies between leaf vertices of pairs of branches of a tree. Most of these permutations are derangements, that is they are permutations with no fixed points. As many products of 2, 3, or 4 of these derangements must also be derangements, it is tempting to use a group of derangements, that is a group of permutations in which every non-identity element is a derangement. The first case to consider is when the group of derangements is a cyclic group of permutations. In this paper it is proved that a construction using only a cyclic group of permutations is impossible. This leaves only the possibility of using some other group of derangements, or a set of derangements that do not form a group. The prospects for extending the work to these cases is considered at the end of the paper.
- Open Access
- 29 November 2025
- Published by MDPI AG in Algorithms
- Vol. 18 (12) , 759
Compact Models for Some Cluster Problems on Node-Colored Graphs
Three optimization problems based on node-colored undirected graphs are the subject of the present study. These problems model real-world applications in several domains, such as cybersecurity, bioinformatics, and social networks, although they have a similar abstract representation. In all of the problems, the goal is to partition the graph into colorful connected components, which means that in each of the connected components, a color can appear in at most one node. The problems are optimized according to different objective functions, leading to different optimal partitions. We propose a compact Mixed Integer Linear Programming formulation for each of the three problems. These models are based on spanning trees, represented through multi-commodity flows. The compact nature of the new linear models is easier to handle than the approaches that previously appeared in the literature. These were based on models with an exponential number of constraints, which, therefore, required complex solving techniques based on the dynamic generation of constraints within a branch-and-cut framework. Computational experiments carried out on the standard benchmark instances for the problems show the potential of the new compact methods, which, once fed into modern state-of-the-art solvers, are able to obtain results better than the previous algorithmic approaches. As an outcome of the experimental campaign, a dozen instances of the different problems considered are closed for the first time.
- 29 November 2025
- Published by MDPI AG in Algorithms
- Vol. 18 (12) , 759
Open AccessCompact Models for Some Cluster Problems on Node-Colored Graphs
Three optimization problems based on node-colored undirected graphs are the subject of the present study. These problems model real-world applications in several domains, such as cybersecurity, bioinformatics, and social networks, although they have a similar abstract representation. In all of the problems, the goal is to partition the graph into colorful connected components, which means that in each of the connected components, a color can appear in at most one node. The problems are optimized according to different objective functions, leading to different optimal partitions. We propose a compact Mixed Integer Linear Programming formulation for each of the three problems. These models are based on spanning trees, represented through multi-commodity flows. The compact nature of the new linear models is easier to handle than the approaches that previously appeared in the literature. These were based on models with an exponential number of constraints, which, therefore, required complex solving techniques based on the dynamic generation of constraints within a branch-and-cut framework. Computational experiments carried out on the standard benchmark instances for the problems show the potential of the new compact methods, which, once fed into modern state-of-the-art solvers, are able to obtain results better than the previous algorithmic approaches. As an outcome of the experimental campaign, a dozen instances of the different problems considered are closed for the first time.
- Open Access
- 27 October 2025
- Published by Association for Computing Machinery (ACM)
- p. 163-168
On Solving the Shortest Paths with Exclusive-Disjunction Arc Pairs Conflicts
- 27 October 2025
- Published by Association for Computing Machinery (ACM)
- p. 163-168
Open AccessOn Solving the Shortest Paths with Exclusive-Disjunction Arc Pairs Conflicts
- Open Access
- 20 August 2025
- Published by MDPI AG in Mathematics
- Vol. 13 (16) , 2674
On Solving the Knapsack Problem with Conflicts
A variant of the well-known Knapsack Problem is studied in this paper. In the classic problem, a set of items is given, with each item characterized by a weight and a profit. A knapsack of a given capacity is provided, and the problem consists of selecting a subset of items such that the total weight does not exceed the capacity of the knapsack, while the total profit is maximized. In the variation considered in the present work, pairs of items are conflicting, and cannot be selected at the same time. The resulting problem, which can be used to model several real applications, is considerably harder to approach than the classic one. In this paper, we consider a mixed-integer linear program representing the problem and we solve it with a state-of-the-art black-box software. A vast experimental procedure on the instances available from the literature, and adopted in the last decade by the community, indicates that the approach we propose achieves results comparable with, and in many cases better than, those of state-of-the-art methods, notwithstanding that the latter are typically based on more complex and problem-specific ideas and algorithms than the idea we propose.
- 20 August 2025
- Published by MDPI AG in Mathematics
- Vol. 13 (16) , 2674
Open AccessOn Solving the Knapsack Problem with Conflicts
A variant of the well-known Knapsack Problem is studied in this paper. In the classic problem, a set of items is given, with each item characterized by a weight and a profit. A knapsack of a given capacity is provided, and the problem consists of selecting a subset of items such that the total weight does not exceed the capacity of the knapsack, while the total profit is maximized. In the variation considered in the present work, pairs of items are conflicting, and cannot be selected at the same time. The resulting problem, which can be used to model several real applications, is considerably harder to approach than the classic one. In this paper, we consider a mixed-integer linear program representing the problem and we solve it with a state-of-the-art black-box software. A vast experimental procedure on the instances available from the literature, and adopted in the last decade by the community, indicates that the approach we propose achieves results comparable with, and in many cases better than, those of state-of-the-art methods, notwithstanding that the latter are typically based on more complex and problem-specific ideas and algorithms than the idea we propose.
- Open Access
- 18 August 2025
- Published by MDPI AG in Algorithms
- Vol. 18 (8) , 526
On Solving the Minimum Spanning Tree Problem with Conflicting Edge Pairs
The Minimum Spanning Tree with Conflicting Edge Pairs is a generalization that adds conflict constraints to a classical optimization problem on graphs used to model several real-world applications. In recent years, several heuristic and exact approaches have been proposed to tackle this problem. In this paper, we present a mixed-integer linear program not previously applied to this problem, and we solve it with an open-source solver. Computational results for the benchmark instances commonly adopted in the literature of the problem are reported. The results indicate that the approach we propose obtains results aligned with those of the much more sophisticated approaches available, notwithstanding it being much simpler to implement. During the experimental campaign, six instances were closed for the first time, with nine improved best-known lower bounds and sixteen improved best-known upper bounds over a total of two hundred thirty instances considered.
- 18 August 2025
- Published by MDPI AG in Algorithms
- Vol. 18 (8) , 526
Open AccessOn Solving the Minimum Spanning Tree Problem with Conflicting Edge Pairs
The Minimum Spanning Tree with Conflicting Edge Pairs is a generalization that adds conflict constraints to a classical optimization problem on graphs used to model several real-world applications. In recent years, several heuristic and exact approaches have been proposed to tackle this problem. In this paper, we present a mixed-integer linear program not previously applied to this problem, and we solve it with an open-source solver. Computational results for the benchmark instances commonly adopted in the literature of the problem are reported. The results indicate that the approach we propose obtains results aligned with those of the much more sophisticated approaches available, notwithstanding it being much simpler to implement. During the experimental campaign, six instances were closed for the first time, with nine improved best-known lower bounds and sixteen improved best-known upper bounds over a total of two hundred thirty instances considered.
- Open Access
On Solving the Assignment Problem with Conflicts
A variant of the well-known Assignment Problem is studied in this paper, where pairs of assignments are conflicting, and cannot be selected at the same time. This configures a set of hard constraints. The problem, which models real applications, looks for a complete assignment that minimizes the total cost, while no conflict is violated. In this paper, we consider a previously known mixed integer linear program representing the problem and we solve it with the open-source solver CP-SAT, part of the Google OR-Tools computational suite. An experimental campaign on the instances available from the literature, indicates that the approach we propose achieves results comparable with, those of state-of-the-art solvers, notwithstanding its intrinsic conceptual and implementation simplicity. The solver adopted is also able to provide heuristic solutions quicker and better than the heuristic methods previously discussed in the literature.
Open AccessOn Solving the Assignment Problem with Conflicts
A variant of the well-known Assignment Problem is studied in this paper, where pairs of assignments are conflicting, and cannot be selected at the same time. This configures a set of hard constraints. The problem, which models real applications, looks for a complete assignment that minimizes the total cost, while no conflict is violated. In this paper, we consider a previously known mixed integer linear program representing the problem and we solve it with the open-source solver CP-SAT, part of the Google OR-Tools computational suite. An experimental campaign on the instances available from the literature, indicates that the approach we propose achieves results comparable with, those of state-of-the-art solvers, notwithstanding its intrinsic conceptual and implementation simplicity. The solver adopted is also able to provide heuristic solutions quicker and better than the heuristic methods previously discussed in the literature.
- Open Access
On Solving the Knapsack Problem with Conflicts
A variant of the well-known Knapsack Problem is studied in this paper, where pairs of items are conflicting, and cannot be selected at the same time. This configures a set of hard constraints. The problem, which can be used to model real applications, looks for a selection of items such that the total profit is maximized, the capacity of the container is respected, and no conflict is violated. In this paper, we consider a previously known mixed integer linear program representing the problem and we solve it with the open-source solver CP-SAT, part of the Google OR-Tools computational suite. An experimental campaign on the instances available from the literature and adopted in the last decade, indicate that the approach we propose achieves results comparable with, and often better than, those of state-of-the-art solvers, notwithstanding its intrinsic conceptual and implementation simplicity.
Open AccessOn Solving the Knapsack Problem with Conflicts
A variant of the well-known Knapsack Problem is studied in this paper, where pairs of items are conflicting, and cannot be selected at the same time. This configures a set of hard constraints. The problem, which can be used to model real applications, looks for a selection of items such that the total profit is maximized, the capacity of the container is respected, and no conflict is violated. In this paper, we consider a previously known mixed integer linear program representing the problem and we solve it with the open-source solver CP-SAT, part of the Google OR-Tools computational suite. An experimental campaign on the instances available from the literature and adopted in the last decade, indicate that the approach we propose achieves results comparable with, and often better than, those of state-of-the-art solvers, notwithstanding its intrinsic conceptual and implementation simplicity.
- Open Access
On Solving the Shortest Paths with Exclusive-Disjunction Arc Pairs Conflicts
A variant of the well-known Shortest Path Problem is studied in this paper, where pairs of conflicting arcs are provided, and for each conflicting pair a penalty is paid once neither or both of the arcs are selected. This configures a set of soft-constraints. The problem, which can be used to model real applications, looks for a path from a given origin to a given destination that minimizes the cost of the arcs traversed plus the penalties incurred. In this paper, we consider a compact mixed integer linear program representing the problem and we solve it with the open-source solver CP-SAT, part of the Google OR-Tools computational suite. An experimental campaign on the instances available from the literature indicates that the approach we propose achieves results comparable with those of state-of-the-art solvers, notwithstanding it is a compact model, while the other approaches require the generation of dynamic constraints in order for the models to be competitive. Some best-known results have been improved in this study, and some instances have been closed for the first time.
Open AccessOn Solving the Shortest Paths with Exclusive-Disjunction Arc Pairs Conflicts
A variant of the well-known Shortest Path Problem is studied in this paper, where pairs of conflicting arcs are provided, and for each conflicting pair a penalty is paid once neither or both of the arcs are selected. This configures a set of soft-constraints. The problem, which can be used to model real applications, looks for a path from a given origin to a given destination that minimizes the cost of the arcs traversed plus the penalties incurred. In this paper, we consider a compact mixed integer linear program representing the problem and we solve it with the open-source solver CP-SAT, part of the Google OR-Tools computational suite. An experimental campaign on the instances available from the literature indicates that the approach we propose achieves results comparable with those of state-of-the-art solvers, notwithstanding it is a compact model, while the other approaches require the generation of dynamic constraints in order for the models to be competitive. Some best-known results have been improved in this study, and some instances have been closed for the first time.
- Open Access
On Solving the Set Covering Problem with Conflicts on Sets
A variant of the well-known Set Covering Problem is studied in this paper, where subsets of a collection have to be selected, and pairwise conflicts among subsets of items exist. The selection of each subset has a cost, and the inclusion of conflicting subsets is associated with a penalty to be paid. The problem, which can be used to model real applications, looks for a selection of subsets that cover the original collection, while minimizing the sum of covering and penalty costs. In this paper we consider a compact mixed integer linear program and we solve it with an open-source solver. Computational results on the benchmark instances commonly used in the literature of the problem are reported. The results indicate that the new approach we propose is capable of good results, both in terms of lower and upper bounds, although not matching the state-of-the-art on average. The new approach was, however, able to improve 9 best-known heuristic solutions.
Open AccessOn Solving the Set Covering Problem with Conflicts on Sets
A variant of the well-known Set Covering Problem is studied in this paper, where subsets of a collection have to be selected, and pairwise conflicts among subsets of items exist. The selection of each subset has a cost, and the inclusion of conflicting subsets is associated with a penalty to be paid. The problem, which can be used to model real applications, looks for a selection of subsets that cover the original collection, while minimizing the sum of covering and penalty costs. In this paper we consider a compact mixed integer linear program and we solve it with an open-source solver. Computational results on the benchmark instances commonly used in the literature of the problem are reported. The results indicate that the new approach we propose is capable of good results, both in terms of lower and upper bounds, although not matching the state-of-the-art on average. The new approach was, however, able to improve 9 best-known heuristic solutions.