Sebastian Urrutia

• Assunção, Lucas; Urrutia, Sebastián & Santos, Andréa Cynthia (2026). Kernel pump : boosting the convergence of the feasibility pump through a kernel search-based decomposition. Mathematical Programming Computation. ISSN 1867-2949. doi: 10.1007/s12532-026-00333-2. Full text in Research Archive Show summary

  Abstract Feasibility Pump (FP) is a well-studied mixed integer linear programming primal heuristic that sequentially guides fractional solutions into integer feasibility by minimizing their distance to given target integer points, while preserving the linear constraints of the original problem. Due to its effectiveness and simplicity, FP has been embedded in most commercial solvers, and several variants of the basic method have been proposed, aiming at improving its convergence and the quality of the solutions obtained. This work introduces Kernel Pump (KP), a novel FP speed-up technique that relies on the intuition that not all binary variables are active (i.e., set to one) in a feasible solution, and can, thus, be sub-divided in a kernel search fashion. Precisely, KP identifies a subset of promising binary variables (the kernel) and distributes the rest into buckets ranked by their likelihood of composing a feasible/optimal solution. FP sub-problems are then solved iteratively, focusing on the current kernel and progressively adding variables from the buckets whenever necessary. Extensive computational experiments on benchmark instances from MIPLIB 2017, as well as two additional problems from the literature of vehicle routing and scheduling, reveal a considerable boost in success rate, also decreasing running times for the majority of instances tested. Notably, aside from outperforming FP, the new method was able to find feasible solutions in cases where CPLEX failed within an hour of search. To our knowledge, this is also the first study to introduce a decomposition approach within the FP framework.

• Yadegari, Mahshid; Urrutia, Sebastián; Santos, Andréa Cynthia & Dang, Quockhanh (2026). Integer programming models for unidirectional and bidirectional cyclic load-dependent routing problems. Journal of Modelling in Management. ISSN 1746-5664. p. 1–23. doi: 10.1108/jm2-09-2025-0468. Full text in Research Archive Show summary

  Purpose Vehicle load is a critical factor that impacts route selection within logistic networks. This study aims to compare two different strategies for generating routes in a cyclic load-dependent traveling salesman problem. Design/methodology/approach The study introduces novel load-dependent cyclic routing strategies and propose two new problems to model them: The unidirectional and bidirectional variants of the cyclic load-dependent traveling salesman problem. Three mathematical formulations are proposed for the problems using integer linear programming. Two formulations, for both variants of the problem, use the so-called MTZ constraints while the third one for the bidirectional variant is based on an arc-network. To evaluate the performance of the proposed strategies, the study uses three sets of instances: benchmarks from the literature, realistic instances and randomly generated instances. Findings The study shows that the bidirectional strategy is strictly better than the unidirectional one in instances with unitary distances and demands. For general-distance and general-demand instances, computational results show that the bidirectional strategy obtains better solutions than the unidirectional one in most cases. Originality/value The proposed problems are original despite being variants of cyclic inventory routing problems. The load on the vehicle is often neglected in operational research literature. The bidirectional strategy in the context of cyclic problems is original. While not extremely complex, the theoretical results on unitary distance and unitary demand instances are new.

• Konovalenko, Anna; Hvattum, Lars Magnus & Urrutia, Sebastián (2026). Two paradigms for combining optimization and satisfiability : Maximum satisfiability and optimum satisfiability problems. Journal of Information and Optimization Sciences. ISSN 0252-2667. 47(2), p. 399–427. doi: 10.47974/jios-1392. Full text in Research Archive Show summary

  Maximum satisfiability (MaxSAT) and optimum satisfiability (OptSAT) problems are two optimization versions of the NP-complete Boolean satisfiability problem. In the literature, these versions have been described and tackled separately by using specialized solvers for each problem. This paper investigates a connection between MaxSAT and OptSAT where each problem can be reduced to the other. We consider several heuristic solvers and different sets of benchmark instances for each problem and investigate whether one class of solvers can tackle instances of the other problem with competitive results. Through computational experiments, we conclude that specialized solvers for one of the problems cannot compete with specialized solvers for the other problem and point out potential improvements of the solvers that are needed to successfully address a wider range of problem instances.

• Werra, Dominique de; Urrutia, Sebastián & Assunção, Lucas (2026). Break minimization in incomplete round-robin tournaments. Discrete Applied Mathematics. ISSN 0166-218X. 387(July), p. 6–14. doi: 10.1016/j.dam.2026.02.023. Full text in Research Archive
• Matos, Saulo; Melo, Rafael A.; Januario, Tiago; Urrutia, Sebastián & Werra, Dominique de (2026). On invariants for 1-factorizations of K2n: Description and computation. Communications in Combinatorics and Optimization (CCO). ISSN 2538-2128. 11, p. 1–27. doi: 10.22049/cco.2025.30792.2619. Full text in Research Archive Show summary

  A 1-factorization is a partition of the edge set of a graph into perfect matchings. The concept of 1-factorization is of great interest due to its applications in modeling sports tournaments. An invariant of a 1-factorization is a property that depends only on its structure such that isomorphic 1-factorizations are guaranteed to have equal invariant values. As such, non-isomorphic 1-factorizations may or may not have different invariant values. An invariant is complete when any two non-isomorphic 1-factorizations have distinct invariant values. We review seven invariants available in the literature to distinguish non-isomorphic 1-factorizations of K2n (complete graphs with an even number of vertices). Additionally, considering that the invariants available in the literature are not complete, we propose two new ones, denoted lantern profiles and even-size bichromatic chains. We analyze the invariants concerning their sizes and calculation time complexity. Furthermore, we conduct computational experiments to assess their ability to distinguish non-isomorphic 1-factorizations. To accomplish that we use the sets of non-isomorphic 1-factorizations of K10 and K12. We also consider the sets of non-isomorphic perfect 1-factorizations of K12, K14, and K16, as well as randomly generated 1-factorizations of K16 and K20. Moreover, the experiments evaluate how the combination of invariants can increase the distinguishing ability.

• Algendi, Abdalrahman; Urrutia, Sebastián & Hvattum, Lars Magnus (2025). A matheuristic for the home healthcare routing and scheduling problem with ferry-dependent travel times. Computers & Operations Research. ISSN 0305-0548. 188(2026)(April ). doi: 10.1016/j.cor.2025.107372. Full text in Research Archive Show summary

  Home healthcare in coastal regions of Norway presents unique operational challenges, as caregivers must combine road driving with scheduled ferry trips to reach certain patients. Unlike conventional time-dependent travel, fixed ferry timetables impose strict synchronization requirements, where a missed departure may lead to prolonged idle times, cascading delays, or even unserved patients. Despite its practical significance, this integration of driving and ferry transportation has not been examined in the home healthcare routing and scheduling literature, leaving a gap between research and practice. To address this gap, we formulate a mixed-integer linear programming model that incorporates patient and caregiver time windows, skill matching requirements, and synchronization constraints, including those induced by ferry-dependent travel. Given the complexity of the problem, we propose a two-phase matheuristic. Phase I constructs a feasible solution through a sequential graph expansion strategy that employs either classical or weighted proximity search, while Phase II refines this solution using the same search method. Computational tests on 20 realistic instances derived from two Norwegian healthcare centers demonstrate that the proposed method with weighted proximity search outperforms direct model solving and the classical proximity search in terms of feasibility, optimality, and solution quality. In particular, the method solves instances with up to 30 patients (50 visits) to proven optimality and identifies high-quality feasible solutions for instances with up to 80 patients (135 visits) within a 3600-second time limit. [Available online 18 December 2025]

• Ribeiro, Celso C.; Urrutia, Sebastián & Werra, Dominique de (2025). Metaheuristics for Problems in Sports Scheduling. In Martí, Rafael; Pardalos, Panos M. & Resende, Mauricio G.C. (Ed.), Handbook of Heuristics. Springer Nature. ISSN 9783032003850. p. 1493–1522. doi: 10.1007/978-3-032-00385-0_62. Full text in Research Archive Show summary

  In this chapter, we consider the problem of scheduling time-constrained round-robin sports tournament problems, metaheuristics for its approximate solution, and their practical applications. This chapter uses graph theory as the fundamental tool. It presents a short introduction to its essential elements, definitions, and results relevant to the subject of this work. We also introduce the basic graph model used to represent single round-robin tournaments and the circle method for constructing timetables. We describe the different neighborhood structures that have been used in the literature of metaheuristics and local search procedures for scheduling time-constrained single round-robin sports tournaments: Home-Away Swap, Team Swap, Partial Team Swap, Round Swap, Partial Round Swap, and Generalized Partial Team Swap. They may be directly extended to double round-robin problems. We conclude by presenting a collection of applications of metaheuristics to sports scheduling problems.

• Werra, Dominique de; Urrutia, Sebastián & Assunção, Lucas (2025). Minimizing breaks in incomplete round-robin tournaments. Procedia Computer Science. 273, p. 101–101. doi: 10.1016/j.procs.2025.10.285. Full text in Research Archive Show summary

  In round-robin schedules, a break occurs when a team plays two consecutive home or two consecutive away games. Minimizing breaks is important for ensuring competitive fairness and logistical efficiency. This article addresses the problem of minimizing breaks in incomplete round-robin schedules in which each pair of teams plays again each other at most once. The problem of minimizing breaks is a classical problem that was previously thoroughly studied in the context of complete round-robin schedules. Using a graph-theoretic model we analyze structural properties of incomplete round-robin schedules. We derive some bounds on the minimum number of breaks. Then, we propose an algorithm that is able to construct incomplete single round-robin schedules minimizing the number of breaks for given numbers of teams and rounds if the number of rounds is not larger than 3/4 of the number of teams.

• Algendi, Abdalrahman; Urrutia, Sebastián; Hvattum, Lars Magnus & Melo, Rafael A. (2025). Nested logic-based Benders decomposition for an integrated home healthcare problem. European Journal of Operational Research. ISSN 0377-2217. 328(2026)(1), p. 32–48. doi: 10.1016/j.ejor.2025.06.006. Full text in Research Archive Show summary

  In this study, we apply nested logic-based Benders decomposition to solve an integrated home healthcare staffing, assignment, routing, and scheduling problem with application in Norway. The proposed method operates at two decomposition levels. Consequently, the entire problem is decomposed into three hierarchical sub-problems: the staffing problem, the assignment problem, and the routing and scheduling problem. These sub-problems are interrelated through two levels of logic-based Benders cuts. Computational experiments on 40 test instances demonstrate the superior performance of nested logic-based Benders decomposition compared to directly solving a mixed-integer linear programming model available in the literature. Specifically, the proposed solution method achieved proven optimality in 28 instances and provided feasible solutions for the remaining 12 instances. In contrast, directly solving the mixed-integer linear programming model yielded proven optimality in 16 instances, provided feasible solutions for 20 instances, and failed to find feasible solutions for 4 instances within the same computational time limit.

• Melo, Rafael A.; Ribeiro, Celso C.; Urrutia, Sebastián & Vansteenwegen, Pieter (2025). A logic-based Benders decomposition approach for a fuel delivery problem with time windows, unsplit compartments, and split deliveries. European Journal of Operational Research. ISSN 0377-2217. 325(1), p. 100–117. doi: 10.1016/j.ejor.2025.03.003. Full text in Research Archive Show summary

  We consider a single-period fuel delivery problem in which a distribution company has to transport multiple types of fuel from a depot to a set of service stations using a heterogeneous set of multi-compartment vehicles. Among other characteristics, the problem includes time windows, a limit on the duration of each route, unsplit compartments, and split deliveries. We propose two mixed integer programming (MIP) formulations and a logic-based Benders decomposition approach. The first formulation is an arc-based model while the second is based on the possible trips. The logic-based Benders decomposition follows a trip-based principle and breaks down the problem into a generalized assignment master problem and a subproblem responsible for identifying violated feasibility cuts implicated by the time-related constraints. It takes advantage of the problem-specific characteristics that allow efficiently solving the resulting subproblems. The logic-based Benders decomposition also serves as a heuristic, which works by limiting the number of trips generated throughout the process. Symmetry breaking constraints and preprocessing procedures are also proposed to help solving the formulations. The computational experiments using synthetic instances show that the logic-based Benders decomposition outperforms the other formulations and is very effective in solving the considered benchmark instances. It solved to optimality instances with up to 20 customers. The MIP heuristic obtained solutions within 7.2% of the optimal cost for all but one of the tested instances with up to 25 customers. Furthermore, it proved to be a viable approach for medium-sized instances where the exact logic-based Benders decomposition encountered difficulties.

• Lima, Carlos V. G. C.; Santos, Vinicius F. dos; Sousa, Joãao H.G. & Urrutia, Sebastián (2024). On the computational complexity of the strong geodetic recognition problem. RAIRO - Operations Research. 58(5), p. 3755–3770. doi: 10.1051/ro/2024120. Full text in Research Archive Show summary

  A strong geodetic set of a graph G = (V, E) is a vertex set S ⊆ V (G) in which it is possible to cover all the remaining vertices of V (G) ∖ S by assigning a unique shortest path between each vertex pair of S. In the Strong Geodetic problem (SG) a graph G and a positive integer k are given as input and one has to decide whether G has a strong geodetic set of cardinality at most k. This problem is known to be NP-hard for general graphs. In this work we introduce the Strong Geodetic Recognition problem (SGR), which consists in determining whether a given vertex set S ⊆ V (G) is strong geodetic. We demonstrate that this version is NP-complete. We investigate and compare the computational complexity of both decision problems restricted to some graph classes, deriving polynomial-time algorithms, NP-completeness proofs, and initial parameterized complexity results, including an answer to an open question in the literature for the complexity of SG for chordal graphs.

• Urrutia, Sebastián & Santos, Vinicius dos (2024). Finding the minimum cost acceptable element in a sorted matrix. Leibniz International Proceedings in Informatics. 301, p. 28:1–28:14. doi: 10.4230/LIPIcs.SEA.2024.28. Full text in Research Archive Show summary

  In this work we introduce the problem of finding a minimum cost acceptable element in an n × n matrix M whose columns and rows are sorted in non-decreasing order. More precisely, given a sorted matrix M and access to a given oracle function f: ℕ × ℕ → {True, False}, one has to find a pair (i, j) of indices such that f(i,j) returns True and the value M[i,j] is as small as possible. Assuming the computation of f(i,j) takes time bounded by a constant, a naive algorithm scanning all the positions of the matrix takes time O(n²). Another natural approach, based on a priority queue, takes time O(z log z) in which z stands for the position of the first pair of indices for which the oracle returns True in a sorted list of all elements of M. In the worst case, when z = n², the naive algorithm is better than the priority queue one. In this work we introduce different algorithms with complexities depending on n and z, such as O(n √z) and O(min(n²,z²)), and compare them, both theoretically and experimentally, in terms of running time and number of calls to the oracle. Among other things, we find that in most cases our algorithms do not make a significantly larger number of calls to the oracle than the priority queue-based algorithm, which achieves the minimum of such call when all elements of the matrix are distinct, while being much faster in large instances.

• Tonetti, Caio Henrique Segawa; Santos, Vinicius Fernandes dos & Urrutia, Sebastián (2024). Polynomial time algorithms for the token swapping problem on cographs. RAIRO - Operations Research. 58(1), p. 441–455. doi: 10.1051/ro/2023134. Full text in Research Archive Show summary

  The reconfiguration framework models the concept of transformation of combinatorial objects under a variety of operations and constraints. When it comes to reconfiguration challenges, the questions of importance are connectivity, diameter and distance, which can be considered and restrained in many ways. This work focuses on the Token Swap problem, a reconfiguration problem with variations that even precede the systematic study of the reconfiguration framework. In this problem, the goal is to convert an initial token placement on the vertices of a graph into a target token placement with the minimum number of swap operations. The main result of this paper is the construction of a polynomial algorithm for threshold graphs and subsequently cographs.

• Algendi, Abdalrahman; Urrutia, Sebastián; Hvattum, Lars Magnus & Helgheim, Berit (2024). Home healthcare staffing, routing, and scheduling problem with multiple shifts and emergency considerations. Networks: An International Journal. ISSN 0028-3045. 85(2), p. 223–242. doi: 10.1002/net.22260. Full text in Research Archive Show summary

  Effective planning of human resources is critical in designing an efficient home healthcare system. In this study, we present a novel home healthcare staffing, routing, and scheduling problem inspired by a real-world application. The proposed problem addresses a set of patients, with varying daily visit requirements, being served by a set of caregivers with different qualification levels over a multi-day multi-shift planning horizon. The problem aims to minimize the number of extra shifts for caregivers, maximize the allocation of caregivers to emergencies, and minimize the sum of route durations over the planning horizon. These objectives are optimized hierarchically while considering a set of restrictions, including time windows, skill matching, synchronization, care continuity, and labor regulations. To tackle the problem, we introduce a mixed-integer linear programming model. The model is then extended and two sets of valid inequalities are incorporated to enhance its tightness. Computational experiments are conducted on a set of 20 instances. The results highlight the efficiency of the proposed extension in increasing both the number of instances that can be solved to optimality and the number of instances for which a feasible solution is found.

• Fagerholt, Kjetil; Hvattum, Lars Magnus; Papageorgiou, Dimitri J. & Urrutia, Sebastián (2023). Maritime inventory routing : recent trends and future directions. International Transactions in Operational Research. ISSN 0969-6016. 30(6), p. 3013–3056. doi: 10.1111/itor.13313. Full text in Research Archive Show summary

  We review recent literature pertaining to the maritime inventory routing problem (MIRP), a stimulating, albeit niche, subclass of vendor-managed inventory problems. MIRPs deal with optimally distributing products with a (typically heterogeneous) vessel fleet between production and consumption ports with inventory tracking and inventory limits. We present two mixed-integer linear programming models for the MIRP—one based on discrete time, the other based on continuous time—and we discuss the advantages and disadvantages of each of the two modeling approaches. In surveying more than 50 papers spanning the decade 2013–2023, we investigate MIRP variants from many different applications and discuss how these have been modeled and solved. Our purpose is to provide a comprehensive overview of state-of-the-art MIRP research published in this period, collated along multiple dimensions. In addition to providing information about available test instances, we highlight recent trends and interesting avenues for future research. As such, we believe this survey will be useful to students, researchers, and practitioners in this domain.

• Ribeiro, Celso C.; Urrutia, Sebastián & Werra, Dominique De (2023). A tutorial on graph models for scheduling round-robin sports tournaments. International Transactions in Operational Research. ISSN 0969-6016. 30(6), p. 3267–3295. doi: 10.1111/itor.13290. Full text in Research Archive Show summary

  Many sports leagues organize their competitions as round-robin tournaments. This tournament design has a rich mathematical structure that has been studied in the literature over the years. We review some of the main properties and fundamental scheduling methods of round-robin tournaments. Special attention is given to extra-mural tournaments in which each team in the competition has its venue. Teams play either at home or away in such tournaments in each round. The surge of breaks in the perfect alternation of home and away breaks is studied in detail.

• Tomacheski, Clynton; Milanés, Anolan Yamilé & Urrutia, Sebastián (2023). The nilcatenation problem and its application for detecting money laundering activities in cryptocurrency networks. International Transactions in Operational Research. ISSN 0969-6016. 31(2024)(6), p. 3955–3974. doi: 10.1111/itor.13353. Full text in Research Archive Show summary

  This work considers a combinatorial optimization problem in graphs, the nilcatenation problem, and investigates its potential application for detecting money laundering activities in cryptocurrency networks. The nilcatenation problem consists of finding a set of arcs that can be removed from an arc-weighted directed graph without changing the balance of any vertex. The balance of a vertex is defined as the difference between the sum of the weights of outgoing and incoming arcs. We propose a 0/1 integer linear programming formulation and a local branching algorithm. The approaches are computationally evaluated and compared using three sets of test instances, two of them generated from Bitcoin's testnet and mainnet networks. An experiment on the testnet showed that it is possible to retrieve a nilcatenation artificially introduced with fake bitcoin transactions. Experiments on the mainnet showed that it is possible to find large nilcatenations, possibly indicating money laundering activities.

• Zojaji, Amir; Soltaniani, Kiarash; Hvattum, Lars Magnus & Urrutia, Sebastián (2022). Cyclic solutions to a maritime inventory routing problem. Maritime Transport Research. 3, p. 1–13. doi: 10.1016/j.martra.2022.100074. Full text in Research Archive Show summary

  An inventory routing problem occurs when a company manages inventories both at production sites and consumption sites while also being in charge of the transportation of goods. We consider a maritime inventory routing problem where inventories are located at ports and a single product is transported between these ports using a heterogeneous fleet of vessels. As opposed to standard research on such maritime inventory routing problems, a model is developed that produces cyclic plans that are repeatable. Such plans are more costly than plans found using standard non-cyclic models, but the latter suffer from end-of-horizon effects due to being over-optimistic and making myopic decisions in accordance with an objective of minimizing costs.

• Algendi, Abdalrahman; Urrutia, Sebastián & Hvattum, Lars Magnus (2022). Optimizing production levels in maritime inventory routing with load-dependent speed optimization. Flexible Services and Manufacturing Journal. ISSN 1936-6582. 35(1), p. 111–141. doi: 10.1007/s10696-022-09460-z. Full text in Research Archive Show summary

  Maritime inventory routing problems with load-dependent speed optimization involves determining optimal routes, as well as vessel speeds and loads at these routes, so that inventory limits are satisfied at both production and consumption ports. This paper considers a variant where production rates can be selected from several available alternative production levels, as opposed to the normal situation where production rates are chosen a priori. In both cases, production rates remain constant for the duration of the planning horizon. The effect on transportation costs when considering production levels as decision variables is evaluated. The resulting solutions are compared with solutions obtained when production rates are considered as fixed parameters. Computational experiments on a set of benchmark instances from the literature confirm that the process of determining the optimal production levels plays a crucial role in improving the solutions to maritime inventory routing problems with load-dependent speed optimization. Optimizing the production levels can reduce transportation costs by up to 35%.

• Guimarães, Marcos V. A.; Bogue, Eduardo T.; Carvalho, Iago A.; Pereira, Armando H.; Noronha, Thiago F. & Urrutia, Sebastián (2022). A biased random-key genetic algorithm for the 2-dimensional guillotine cutting stock problem with stack constraints. In Dorronsoro, Bernabé; Yalaoui, Farouk; Talbi, El-Ghazali & Danoy, Grégoire (Ed.), Metaheuristics and Nature Inspired Computing 8th International Conference, META 2021, Marrakech, Morocco, October 27-30, 2021, Proceedings. Springer. ISSN 9783030942168. p. 155–169. doi: 10.1007/978-3-030-94216-8_12. Full text in Research Archive Show summary

  This paper tackles the 2-Dimensional Guillotine Cutting Stock Problem with Stack Constraints. The problem asks for the cutting of a set of items with the minimum amount of raw material. The cutting patterns are subject to a number of constraints, including a new realistic constraint, regarding item precedence, which has just been introduced in the literature. In this case, the items are organized in stacks, where each stack represents a customer request and defines the order in which the items must be cut. That is, if item i precedes item j within a stack, then i must be cut before j. However, there is no precedence constraint between items in different stacks. This constraint comes from applications where items must be stacked and shipped in the exact order that they will be used by the customer, thus avoiding the risk of damaging fragile items (as is the case in the glass industry) or the cost of moving heavy items (as is the case in the steel industry). We propose two heuristics, one Evolutionary Algorithm (EA) adapted from a similar problem in the literature, and a novel Biased Random Key Genetic Algorithm (BRKGA). Computational results show that BRKGA outperforms the evolutionary algorithm from the literature.

• Amaral, Heber F.; Urrutia, Sebastián & Hvattum, Lars Magnus (2021). Delayed improvement local search. Journal of Heuristics. ISSN 1381-1231. 27(5), p. 923–950. doi: 10.1007/s10732-021-09479-9. Full text in Research Archive Show summary

  Local search is a fundamental tool in the development of heuristic algorithms. A neighborhood operator takes a current solution and returns a set of similar solutions, denoted as neighbors. In best improvement local search, the best of the neighboring solutions replaces the current solution in each iteration. On the other hand, in first improvement local search, the neighborhood is only explored until any improving solution is found, which then replaces the current solution. In this work we propose a new strategy for local search that attempts to avoid low-quality local optima by selecting in each iteration the improving neighbor that has the fewest possible attributes in common with local optima. To this end, it uses inequalities previously used as optimality cuts in the context of integer linear programming. The novel method, referred to as delayed improvement local search, is implemented and evaluated using the travelling salesman problem with the 2-opt neighborhood and the max-cut problem with the 1-flip neighborhood as test cases. Computational results show that the new strategy, while slower, obtains better local optima compared to the traditional local search strategies. The comparison is favourable to the new strategy in experiments with fixed computation time or with a fixed target.

• Silva, Rodrigo Ferreira da; Urrutia, Sebastián & Hvattum, Lars Magnus (2021). Extended high dimensional indexing approach for reachability queries on very large graphs. Expert Systems With Applications. ISSN 0957-4174. 181(November), p. 1–11. doi: 10.1016/j.eswa.2021.114962. Full text in Research Archive Show summary

  Given a directed acyclic graph G = (V,A) and two vertices u, v ∈ V , the reachability problem is to answer if there is a path from u to v in the graph. In the context of very large graphs, with millions of vertices and a series of queries to be answered, it is not practical to search the graph for each query. On the other hand, the storage of the full transitive closure of the graph is also impractical due to its O(|V |2) size. Scalable approaches aim to create indices used to prune the search during its execution. Negative indices may be able to determine (in constant time) that a query has a negative answer while positive indices may determine (again in constant time) that a query has a positive answer. In this paper we propose novel scalable approach called LYNX that uses a large number of topological sorts of G as a negative cut index without degrading the query time. A similar strategy is applied regarding a positive cut index. In addition, LYNX proposes a user-defined index size that enables the user to control the ratio between negative and positive cuts depending on the expected query pattern. We show by computational experiments that LYNX consistently outperforms the state-of-the-art approach in terms of query-time using the same index-size for graphs with high reachability ratio. In intelligent computer systems that rely on frequent tests of connectivity in graphs, LYNX can reduce the time delay experience by end users through a reduced query time. This comes at the expense of an increased setup time whenever the underlying graph is updated. Keywords: directed acyclic graphs, topological sorts, reachability queries, graph indexing

• Pereira, Armando Honorio; Mateus, Geraldo Robson & Urrutia, Sebastián (2021). Valid inequalities and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks. European Journal of Operational Research. ISSN 0377-2217. 300(1), p. 207–220. doi: 10.1016/j.ejor.2021.07.051. Full text in Research Archive Show summary

  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. Keywords: combinatorial optimization, branch-and-cut, traveling salesman, pickup and delivery, multiple stacks

• Urrutia, Sebastián; Werra, Dominique De & Januario, Tiago (2021). Recoloring subgraphs of K2n for sports scheduling. Theoretical Computer Science. ISSN 0304-3975. 877, p. 36–45. doi: 10.1016/j.tcs.2021.03.029. Full text in Research Archive Show summary

  The exploration of one-factorizations of complete graphs is the foundation of some classical sports scheduling problems. One has to traverse the landscape of such one-factorizations by moving from one of those to a so-called neighbor one-factorization. This approach amounts to modifying locally the coloring associated with a one-factorization. We consider some particular types of modifications and describe various constructions which give one-factorizations which may be modified or not by these techniques. Among those are recoloring of bichromatic cycles, altering of optimally colored subcliques of even size, or recoloring of chordless lanterns. Keywords: graph theory, one-factorization, subgraph recoloring

• Eide, Line; Årdal, Gro Cesilie Håhjem; Evsikova, Nataliia; Hvattum, Lars Magnus & Urrutia, Sebastián (2020). Load-dependent speed optimization in maritime inventory routing. Computers & Operations Research. ISSN 0305-0548. 123(November), p. 1–12. doi: 10.1016/j.cor.2020.105051. Full text in Research Archive Show summary

  Maritime inventory routing problems involve determining optimal routes for seagoing vessels between ports while managing the inventory of each port. Normally, such problems are considered with the vessels operating at fixed sailing speeds. However, the speed of vessels can typically be adjusted within an interval, and the actual fuel consumption depends on both the load and the speed of the vessel. The fuel consumption function combines speed and load in a non-linear manner, but can be approximated through linearization. In this work, to evaluate the importance of taking into account that both speeds and load levels influence the fuel costs, the resulting solutions are contrasted with solutions from the case where speeds and travel costs are taken as constants, as well as the case where speed is a decision, but the cost considered to be independent of the load. For either of these cases, load-dependent speed optimization can be added as a post-processing step. Computational experiments show that combining speed and load do have an impact on the selection of routes in maritime inventory routing problems, and that proper modelling of the fuel consumption can reduce sailing costs significantly. On the test instances considered, taking into account speed while ignoring the load leads to cost savings of around 38%. Considering the fuel consumption as a function of speed and load when planning leads to additional cost savings of 28%.

• Pereira, Armando Honorio; Mateus, Geraldo Robson & Urrutia, Sebastián (2020). Branch-and-cut algorithms for the p-arborescence star problem. International Transactions in Operational Research. ISSN 0969-6016. 29(4), p. 2374–2400. doi: 10.1111/itor.12857. Full text in Research Archive Show summary

  Given a connected digraph, a vertex designated as the root, and an integer p,thep-arborescence star problemis to choose p vertices besides the root and define a reverse arborescence spanning them. Each vertex outsidethe arborescence must be assigned to one vertex inside it. The objective of the problem is to minimize ar-borescence and assignment costs. We propose two formulations for the problem and prove theoretical resultsabout their strength. Moreover, we develop branch-and-cut algorithms based on each one of the formula-tions 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 introducepreprocessing procedures for the problem. The proposed algorithms are evaluated with a set of benchmarkinstances from the literature. For small and medium-sized instances, our proposed algorithms provide thebest results when compared to the existing algorithm from the literature. For large instances, the proposedalgorithms are shown to be competitive with the existing approach.Keywords: integer programming, branch and cut, arborescence, wireless sensor networks

• Faraj, Marcelo Fonseca; Urrutia, Sebastián & Sarubbi, Joao F M (2019). Gamma deployment problem in grids: hardness and new integer linear programming formulation. International Transactions in Operational Research. ISSN 0969-6016. 27(6), p. 2740–2759. doi: 10.1111/itor.12759. Full text in Research Archive Show summary

  Vehicular networks are mobile networks designed for the domain of vehicles and pedestrians. These networks are an essential component of intelligent transportation systems and have the potential to ease traffic management, lower accident rates, and offer other solutions to smart cities. One of the most challenging aspects in the design of a vehicular network is the distribution of its infrastructure units, which are called roadside units (RSUs). In this work, we tackle the gamma deployment problem that consists of deploying the minimum number of RSUs in a vehicular network in accordance with a quality of service metric called gamma deployment. This metric defines a vehicle as covered if it connects to some RSUs at least once in a given time interval during its whole trip. Then, the metric parameterizes the minimum percentage of covered vehicles necessary to make a deployment acceptable or feasible. In this paper, we prove that the decision version of the gamma deployment problem in grids is NP-complete. Moreover, we correct the multiflow integer linear programming formulation present in the literature and introduce a new formulation based on set covering that is at least as strong as the multiflow formulation. In experiments with a commercial solver, the set covering formulation widely outperforms the multiflow formulation with respect to running time and linear programming relaxation gap. Keywords: gamma deployment; complexity; integer linear programming.

• Urrutia, Sebastián; Milanés, Anolan Yamilé & Løkketangen, Arne (2015). A dynamic programming based local search approach for the double traveling salesman problem with multiple stacks. International Transactions in Operational Research. ISSN 0969-6016. 22(1), p. 61–75. doi: 10.1111/itor.12053. Full text in Research Archive Show summary

  The double traveling salesman problem with multiple stacks consists in determining a pair of routes (pickup and delivery) for a unique vehicle in two different and disjoint networks. It models a realistic transportation problem with loading/unloading constraints imposed by having a set of last-in-first-out (LIFO) stacks used for storing the goods being transported. The arrangement of the items in the container determines the loading plan that in terms constrains both routes. In this paper, we propose a novel local search approach. The local search heuristic is applied to the loading plan instead of working directly on the routes. A dynamic programming algorithm is used to map the loading plan solution into corresponding optimal routes. Computational results show that the proposed approach is competitive with state-of-the-art heuristics for the problem.

View all works in NVA

• Ribeiro, Celso C.; Urrutia, Sebastián & Werra, Dominique de (2023). Combinatorial models for scheduling sports tournaments. Springer. ISBN 9783031372827. 175 p. Full text in Research Archive Show summary

  This book introduces solutions for sports scheduling problems in a variety of settings. In particular the book covers timetabling, the traveling tournament problem, carryover minimization, breaks minimization, tournament design, tournament planning, and referee assignment. A rich selection of applications to sports such as football, baseball, basketball, cricket or hockey are employed to illustrate the methods and techniques. In a step-by-step tutorial format the book describes the use of graph theory concepts, local search operators and integer programming in the context of sports scheduling. The methods presented in this book are essential to sports scheduling in all its dimensions, from tournaments that are followed by millions of people across the world, with broadcast rights that amount to hundreds of millions of dollars in some competitions, to amateur leagues that require coordination and logistical efforts due to the large number of tournaments and competitors.

View all works in NVA

• Bentsen, Håkon; Hvattum, Lars Magnus & Urrutia, Sebastián (2019). A review of Binary Integer Programming applications and solution methods. Full text in Research Archive Show summary

  Binary Integer Programming (BIP) covers a large variety of different problems, with many real world applications. This work first reviews the scientific literature with the aim of creating an overview of the most important applications of pure BIP models. The literature review is conducted using different search strings in order to find the relevant papers from prominent online databases. The findings are then filtered manually and categorized by application. There are relatively few general purpose solvers for BIP, and computational experiments are conducted to show their performance on benchmark instances from the literature, covering a wide variety of applications. Based on these results, we argue that there is a need for improved general purpose solvers for BIP problems, with a performance level closer to what is found in specialized solvers. Keywords: programming, mixed-integer

• Hvattum, Lars Magnus; Zaitseva, Anna & Urrutia, Sebastián (2018). Profit maximization in inventory routing problems. Full text in Research Archive
• Oppen, Johan; Cavalcante, Evellyn; Samer, Phillippe & Urrutia, Sebastián (2016). Combinatorial relaxation bounds and preprocessing for berth allocation problems. Full text in Research Archive
• Sampaio, Afonso Henrique; Urrutia, Sebastián & Oppen, Johan (2015). A decomposition approach to solve the quay crane scheduling problem. Full text in Research Archive
• Urrutia, Sebastián; Milanés, Anolan Yamilé & Løkketangen, Arne (2013). A GPU algorithm for the DTSPMS. Full text in Research Archive
• Milanés, Anolan Yamilé; Urrutia, Sebastián & Løkketangen, Arne (2013). Uma heurística paralela na GPU para o problema do Caixeiro Viajante Duplo com Múltiplas Pilhas. Full text in Research Archive
• Urrutia, Sebastián & Løkketangen, Arne (2012). A Dynamic Programming based Local Search Approach for the Double Traveling Salesman Problem with Multiple Stacks. Full text in Research Archive
• Løkketangen, Arne; Milanés, Anolan Yamilé & Urrutia, Sebastián (2012). Double TSP with multiple stacks - strategic oscilliation and heuristic search. Full text in Research Archive
• Urrutia, Sebastián; Milanés, Anolan Yamilé & Løkketangen, Arne (2012). A strategic oscillation heuristic for the double Traveling Salesman Problem with multiple stacks. Full text in Research Archive Show summary

  The extended abstract describes a new heuristic for the Double Traveling Salesman Problem with Multiple Stacks. Preliminary computational results indicate that the heuristics performance is very similar to that of state of the art algorithms.

• Algendi, Abdalrahman; Urrutia, Sebastián; Hvattum, Lars Magnus & Helgheim, Berit (2024). Home health care staffing, routing, and scheduling problem with multiple shifts and emergency considerations. Høgskolen i Molde - Vitenskapelig høgskole i logistikk. ISSN 9788279623625. Full text in Research Archive Show summary

  Effective planning of human resources is critical in designing an efficient home healthcare system. In this study, we present a novel home healthcare staffing, routing, and scheduling problem inspired by a real-world application. The proposed problem addresses a set of patients, with varying daily visit requirements, being served by a set of caregivers with different qualification levels over a multi-day multi-shift planning horizon. The study aims to achieve three objectives: minimizing the number of additional shifts, maximizing the allocation of caregivers to emergencies, and minimizing the sum of route lengths. These objectives are optimized hierarchically while considering a set of restrictions, including time windows, skill matching, synchronicity, care continuity, and labor regulations. To tackle the problem, we introduce a mixed-integer linear programming model. The model is then extended and two sets of valid inequalities are incorporated to enhance its tightness. Computational experiments are conducted on a set of 20 instances. The results highlight the efficiency of the proposed extension in increasing both the number of instances that can be solved to optimality and the number of instances for which a feasible solution is found. Keywords: Mixed-integer programming; Valid inequalities; Home healthcare; Human resource planning; Multiple shifts; Synchronization.

View all works in NVA