Sebastian Alberto Urrutia

• Tonetti, Caio Henrique Segawa; dos Santos, Vinicius Fernandes & Urrutia, Sebastián (2024). POLYNOMIAL TIME ALGORITHMS FOR THE TOKEN SWAPPING PROBLEM ON COGRAPHS. Reserche operationelle. ISSN 0399-0559. 58(1), p. 441–455. doi: 10.1051/ro/2023134.
• 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. doi: 10.1111/itor.13353. 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.

• Ribeiro, Celso C.; Urrutia, Sebastián & De Werra, Dominique (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. 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.

• 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.

• 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 978-3-030-94216-8. p. 155–169. doi: 10.1007/978-3-030-94216-8_12. 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.

• Zojaji, Amir; Soltaniani, Kiarash; Hvattum, Lars Magnus & Urrutia, Sebastián (2022). Cyclic solutions to a maritime inventory routing problem. Maritime Transport Research. ISSN 2666-822X. 3, p. 1–13. doi: 10.1016/j.martra.2022.100074. 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. 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%.

• 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.

• 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. 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

• da Silva, Rodrigo Ferreira; 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

• Urrutia, Sebastián; De Werra, Dominique & 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

• 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. 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

• 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, 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%.

• 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. 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. 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 Cristin

• Ribeiro, Celso C.; Urrutia, Sebastián & de Werra, Dominique (2023). Combinatorial models for scheduling sports tournaments. Springer. ISBN 978-3-031-37282-7. 175 p. 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 Cristin

• Bentsen, Håkon; Hvattum, Lars Magnus & Urrutia, Sebastián (2019). A review of Binary Integer Programming applications and solution methods. 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.
• Oppen, Johan; Cavalcante, Evellyn; Samer, Phillippe & Urrutia, Sebastián (2016). Combinatorial relaxation bounds and preprocessing for berth allocation problems.
• Sampaio, Afonso Henrique; Urrutia, Sebastián & Oppen, Johan (2015). A decomposition approach to solve the quay crane scheduling problem.
• Urrutia, Sebastián; Milanés, Anolan Yamilé & Løkketangen, Arne (2013). A GPU algorithm for the DTSPMS.
• 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.
• Urrutia, Sebastián; Milanés, Anolan Yamilé & Løkketangen, Arne (2012). A strategic oscillation heuristic for the double Traveling Salesman Problem with multiple stacks. 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.

• Urrutia, Sebastián & Løkketangen, Arne (2012). A Dynamic Programming based Local Search Approach for the Double Traveling Salesman Problem with Multiple Stacks.
• Løkketangen, Arne; Milanés, Anolan Yamilé & Urrutia, Sebastián (2012). Double TSP with multiple stacks - strategic oscilliation and heuristic search.

View all works in Cristin