Daniel Severín
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
Daniel Severín has a total of 22 co-authors. Here are the top co-authors by number of shared publications:
- Graciela Nasini
FCEIA Universidad Nacional de Rosario Rosario Argentina
7 shared publications Graciela Nasini
4 shared publications- Isabel Méndez-Díaz
Departamento de Computación, FCEyN, Universidad de Buenos Aires, Ciudad Autónoma de Buenos Aires, Argentina
4 shared publications - Manoel Campêlo
Dep. Estatística e Matemática Aplicada Universidade Federal do Ceará Brazil
4 shared publications - Diego Recalde
Department of Mathematics, Escuela Politécnica Nacional, Quito, Ecuador
3 shared publications - Mauro Lucci
Depto. de Matemática (FCEIA) Universidad Nacional de Rosario Argentina
3 shared publications
Latest Publications
- 10 March 2025
- Published by Wiley in International Transactions in Operational Research
- Vol. 33 (5) , 3158-3186
Exact resolution of a simultaneous vehicle routing and crew scheduling problem in long‐haul transport
This work focuses on exact methods for a simultaneous vehicle routing and crew scheduling problem in long‐haul transport. Pickup‐and‐delivery requests with time windows must be fulfilled over a multi‐day planning horizon. Unlike some classic approaches, the correspondence between trucks and drivers is not fixed and they can be exchanged in some locations and at any time. Drivers can also travel for free as truck passengers or take external taxis for an additional cost. The objective is to minimise the truck and taxi travel costs and the penalties for late deliveries. Routes for trucks and drivers are represented separately as directed paths in certain digraphs and then synchronised in time and space. Three compact integer linear programming formulations are proposed, and many families of valid inequalities are described. Extensive computational experiments are conducted on randomly generated instances. The formulations are experimentally compared, and the effectiveness of the proposed valid inequalities as cutting planes in a branch‐and‐cut algorithm is evaluated.
- 10 March 2025
- Published by Wiley in International Transactions in Operational Research
- Vol. 33 (5) , 3158-3186
Exact resolution of a simultaneous vehicle routing and crew scheduling problem in long‐haul transport
This work focuses on exact methods for a simultaneous vehicle routing and crew scheduling problem in long‐haul transport. Pickup‐and‐delivery requests with time windows must be fulfilled over a multi‐day planning horizon. Unlike some classic approaches, the correspondence between trucks and drivers is not fixed and they can be exchanged in some locations and at any time. Drivers can also travel for free as truck passengers or take external taxis for an additional cost. The objective is to minimise the truck and taxi travel costs and the penalties for late deliveries. Routes for trucks and drivers are represented separately as directed paths in certain digraphs and then synchronised in time and space. Three compact integer linear programming formulations are proposed, and many families of valid inequalities are described. Extensive computational experiments are conducted on randomly generated instances. The formulations are experimentally compared, and the effectiveness of the proposed valid inequalities as cutting planes in a branch‐and‐cut algorithm is evaluated.
- Open Access
Solving the List Coloring Problem through a Branch-and-Price algorithm
In this work, we present a branch-and-price algorithm to solve the weighted version of the List Coloring Problem, based on a vertex cover formulation by stable sets. This problem is interesting for its applications and also for the many other problems that it generalizes, including the well-known Graph Coloring Problem. With the introduction of the concept of indistinguishable colors, some theoretical results are presented which are later incorporated into the algorithm. We propose two branching strategies based on others for the Graph Coloring Problem, the first is an adaptation of the one used by Mehrotra and Trick in their pioneering branch-and-price algorithm, and the other is inspired by the one used by Méndez-Díaz and Zabala in their branch-and-cut algorithm. The rich structure of this problem makes both branching strategies robust. Extended computation experimentation on a wide variety of instances shows the effectiveness of this approach and evidences the different behaviors that the algorithm can have according to the structure of each type of instance.
Open AccessSolving the List Coloring Problem through a Branch-and-Price algorithm
In this work, we present a branch-and-price algorithm to solve the weighted version of the List Coloring Problem, based on a vertex cover formulation by stable sets. This problem is interesting for its applications and also for the many other problems that it generalizes, including the well-known Graph Coloring Problem. With the introduction of the concept of indistinguishable colors, some theoretical results are presented which are later incorporated into the algorithm. We propose two branching strategies based on others for the Graph Coloring Problem, the first is an adaptation of the one used by Mehrotra and Trick in their pioneering branch-and-price algorithm, and the other is inspired by the one used by Méndez-Díaz and Zabala in their branch-and-cut algorithm. The rich structure of this problem makes both branching strategies robust. Extended computation experimentation on a wide variety of instances shows the effectiveness of this approach and evidences the different behaviors that the algorithm can have according to the structure of each type of instance.
- 1 March 2023
- Published by Wiley in International Transactions in Operational Research
- Vol. 30 (2) , 970-1001
A metaheuristic for crew scheduling in a pickup-and-delivery problem with time windows
- 1 March 2023
- Published by Wiley in International Transactions in Operational Research
- Vol. 30 (2) , 970-1001
A metaheuristic for crew scheduling in a pickup-and-delivery problem with time windows
- 1 October 2021
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 301, 26-48
An integer programming approach for solving a generalized version of the Grundy domination number
- 1 October 2021
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 301, 26-48
An integer programming approach for solving a generalized version of the Grundy domination number
- Open Access
An integer programming approach for solving a generalized version of the Grundy domination number
A sequence of vertices in a graph is called a legal dominating sequence if every vertex in the sequence dominates at least one vertex not dominated by those that precede it, and at the end all vertices of the graph are dominated. The Grundy domination number of a graph is the size of a largest legal dominating sequence. In this work, we introduce a generalized version of the Grundy domination problem. We explicitly calculate the corresponding parameter for paths and web graphs. We propose integer programming formulations for the new problem, find families of valid inequalities and perform extensive computational experiments to compare the formulations as well as to test these inequalities as cuts in a branch-and-cut framework. We also design and evaluate the performance of a heuristic for finding good initial lower and upper bounds and a tabu search that improves the initial lower bound. The test instances include randomly generated graphs, structured graphs, classical benchmark instances and two instances from a real application. Our approach is exact for graphs with 20-50 vertices and provides good solutions for graphs up to 10000 vertices.
Open AccessAn integer programming approach for solving a generalized version of the Grundy domination number
A sequence of vertices in a graph is called a legal dominating sequence if every vertex in the sequence dominates at least one vertex not dominated by those that precede it, and at the end all vertices of the graph are dominated. The Grundy domination number of a graph is the size of a largest legal dominating sequence. In this work, we introduce a generalized version of the Grundy domination problem. We explicitly calculate the corresponding parameter for paths and web graphs. We propose integer programming formulations for the new problem, find families of valid inequalities and perform extensive computational experiments to compare the formulations as well as to test these inequalities as cuts in a branch-and-cut framework. We also design and evaluate the performance of a heuristic for finding good initial lower and upper bounds and a tabu search that improves the initial lower bound. The test instances include randomly generated graphs, structured graphs, classical benchmark instances and two instances from a real application. Our approach is exact for graphs with 20-50 vertices and provides good solutions for graphs up to 10000 vertices.
- Open Access
- 1 June 2020
- Published by Elsevier in Information Processing Letters
- Vol. 158, 105937
On the additive chromatic number of several families of graphs
- 1 June 2020
- Published by Elsevier in Information Processing Letters
- Vol. 158, 105937
Open AccessOn the additive chromatic number of several families of graphs
- Open Access
On the additive chromatic number of several families of graphs
The Additive Coloring Problem is a variation of the Coloring Problem where labels of $\{1,\ldots,k\}$ are assigned to the vertices of a graph $G$ so that the sum of labels over the neighborhood of each vertex is a proper coloring of $G$. The least value $k$ for which $G$ admits such labeling is called \emph{additive chromatic number} of $G$. This problem was first presented by Czerwi\'nski, Grytczuk and \.Zelazny who also proposed a conjecture that for every graph $G$, the additive chromatic number never exceeds the classic chromatic number. Up to date, the conjecture has been proved for complete graphs, trees, non-3-colorable planar graphs with girth at least 13 and non-bipartite planar graphs with girth at least 26. In this work, we show that the conjecture holds for split graphs. We also present exact formulas for computing the additive chromatic number for some subfamilies of split graphs (complete split, headless spiders and complete sun), regular bipartite, complete multipartite, fan, windmill, circuit, wheel, cycle sun and wheel sun.Open AccessOn the additive chromatic number of several families of graphs
The Additive Coloring Problem is a variation of the Coloring Problem where labels of $\{1,\ldots,k\}$ are assigned to the vertices of a graph $G$ so that the sum of labels over the neighborhood of each vertex is a proper coloring of $G$. The least value $k$ for which $G$ admits such labeling is called \emph{additive chromatic number} of $G$. This problem was first presented by Czerwi\'nski, Grytczuk and \.Zelazny who also proposed a conjecture that for every graph $G$, the additive chromatic number never exceeds the classic chromatic number. Up to date, the conjecture has been proved for complete graphs, trees, non-3-colorable planar graphs with girth at least 13 and non-bipartite planar graphs with girth at least 26. In this work, we show that the conjecture holds for split graphs. We also present exact formulas for computing the additive chromatic number for some subfamilies of split graphs (complete split, headless spiders and complete sun), regular bipartite, complete multipartite, fan, windmill, circuit, wheel, cycle sun and wheel sun. - Open Access
- 1 August 2019
- Published by Elsevier in Electronic Notes in Theoretical Computer Science
- Vol. 346, 613-624
A Branch and Price Algorithm for List Coloring Problem
- 1 August 2019
- Published by Elsevier in Electronic Notes in Theoretical Computer Science
- Vol. 346, 613-624
Open AccessA Branch and Price Algorithm for List Coloring Problem
- Open Access
A Branch and Price Algorithm for List Coloring Problem
Coloring problems in graphs have been used to model a wide range of real applications. In particular, the List Coloring Problem generalizes the well-known Graph Coloring Problem for which many exact algorithms have been developed. In this work, we present a Branch-and-Price algorithm for the weighted version of the List Coloring Problem, based on the one developed by Mehrotra and Trick (1996) for the Graph Coloring Problem. This version considers non-negative weights associated to each color and it is required to assign a color to each vertex from predetermined lists in such a way the sum of weights of the assigned colors is minimum. Computational experiments show the good performance of our approach, being able to comfortably solve instances whose graphs have up to seventy vertices. These experiences also bring out that the hardness of the instances of the List Coloring Problem does not seem to depend only on quantitative parameters such as the size of the graph, its density, and the size of list of colors, but also on the distribution of colors present in the lists.
Open AccessA Branch and Price Algorithm for List Coloring Problem
Coloring problems in graphs have been used to model a wide range of real applications. In particular, the List Coloring Problem generalizes the well-known Graph Coloring Problem for which many exact algorithms have been developed. In this work, we present a Branch-and-Price algorithm for the weighted version of the List Coloring Problem, based on the one developed by Mehrotra and Trick (1996) for the Graph Coloring Problem. This version considers non-negative weights associated to each color and it is required to assign a color to each vertex from predetermined lists in such a way the sum of weights of the assigned colors is minimum. Computational experiments show the good performance of our approach, being able to comfortably solve instances whose graphs have up to seventy vertices. These experiences also bring out that the hardness of the instances of the List Coloring Problem does not seem to depend only on quantitative parameters such as the size of the graph, its density, and the size of list of colors, but also on the distribution of colors present in the lists.
- Open Access
The polytope of legal sequences
A sequence of vertices in a graph is called a \emph{(total) legal dominating sequence} if every vertex in the sequence (total) dominates at least one vertex not dominated by those ones that precede it, and at the end all vertices of the graph are (totally) dominated. The \emph{Grundy (total) domination number} of a graph is the size of the largest (total) legal dominating sequence. In this work, we address the problems of determining these two parameters by introducing a generalized version of them. We explicitly calculate the corresponding (general) parameter for paths and web graphs. We propose integer programming formulations for the new problem and we study the polytope associated to one of them. We find families of valid inequalities and derive conditions under which they are facet-defining. Finally, we perform computational experiments to compare the formulations as well as to test valid inequalities as cuts in a B\&C framework.
Open AccessThe polytope of legal sequences
A sequence of vertices in a graph is called a \emph{(total) legal dominating sequence} if every vertex in the sequence (total) dominates at least one vertex not dominated by those ones that precede it, and at the end all vertices of the graph are (totally) dominated. The \emph{Grundy (total) domination number} of a graph is the size of the largest (total) legal dominating sequence. In this work, we address the problems of determining these two parameters by introducing a generalized version of them. We explicitly calculate the corresponding (general) parameter for paths and web graphs. We propose integer programming formulations for the new problem and we study the polytope associated to one of them. We find families of valid inequalities and derive conditions under which they are facet-defining. Finally, we perform computational experiments to compare the formulations as well as to test valid inequalities as cuts in a B\&C framework.