Nuova ricerca

Daniele PRETOLANI

Professore Associato
Dipartimento di Scienze e Metodi dell'Ingegneria

Home | Curriculum(pdf) | Didattica |


Pubblicazioni

2023 - Mathematical Models for Order Batching and Assignment in a Deep-Frozen Warehouse [Relazione in Atti di Convegno]
Pretolani, Daniele; Chou, Xiaochen; Loske, Dominic; Klumpp, Matthias; Montemanni, Roberto
abstract

2021 - A Decision Support System to Evaluate Suppliers in the Context of Global Service Providers [Relazione in Atti di Convegno]
Bruck, Bruno Petrato; Vezzali, Dario; Iori, Manuel; Magni, Carlo Alberto; Pretolani, Daniele
abstract

In this paper, we present a decision support system (DSS) developed for a global service provider (GSP), which solves a real-world supplier selection problem. The GSP operates in the Italian market of facility management, supplying customers with a variety of services. These services are subcontracted to external qualified suppliers spread all over Italy and chosen on the basis of several criteria, such as service quality, availability and proximity. Selecting the best supplier is a complex task due to the large number of suppliers and the great variety of facility management services offered by the GSP. In the proposed DSS, the choice of the best supplier for a certain service is made according to a thorough multi-criteria analysis. The weights for the criteria were generated by implementing both a simplified analytic hierarchy process and a revised Simos' procedure, later validated by the decision makers at the GSP. The DSS provides quick access to historical performance data, visual tools to aid decisions, and a suggested ranked list of suppliers for each given contract. The effectiveness of the proposed system was assessed by means of extensive simulations on a seven-year period of real-data and several rounds of validation with the company.

2020 - Multiple criteria decision analysis theory and tools for the SDEWES index [Articolo su rivista]
Pretolani, D.
abstract

The goal of this work is to apply Multiple Criteria Decision Analysis tools, both theoretical and practical, to analyse, support and possibly enhance composite indexes, in particular those related to sustainability assessment. In this context, the Sustainable Development of Energy, Water and Environment Systems Index represents a paradigmatic example and an emerging reference point, thus it is specifically addressed throughout the work. On the theoretical side, the focus is on the property of “independence”, i.e., of evaluating an alternative independently of the others. It is argued that this property can be appealing for an index that is conceived to address, over time, an increasing number of inherently evolving systems. A viable and theoretically grounded approach for devising a version of the index fulfilling independence is proposed. On the practical side, the contribution concerns visual support tools. A well-known projective method is adapted to work with the index, and a new tool with comparable expressive capabilities is proposed. The new representation is more focused on the index, technically simpler, and less sensitive to changes in the input data. The features of the visual tools are illustrated exploiting currently available (partially aggregated) index data. In particular, the new tool is used to illustrate two issues addressed in the scientific literature on the index, namely, the use of scenario analysis as a predictive tool, and the decoupling of energy usage and carbon dioxide emissions.

2019 - A Decision Support System to Evaluate Suppliers in the Context of Global Service Providers [Abstract in Atti di Convegno]
Bruck, Bruno Petrato; Iori, Manuel; Pretolani, Daniele; Vezzali, Dario
abstract

In this work, we propose a decision support system (DSS) to evaluate a set of suppliers by considering a multiplicity of variables. The DSS has been implemented to solve a real problem faced by a Global Service Provider (GSP) operating in the Italian market, and is based on a simplified Analytic Hierarchy Process (AHP) application. GSPs operate in the field of facility management, providing customers with general maintenance services for their real estate assets. To realize this purpose, they subcontract to selected suppliers the execution of services. A comprehensive and multi-criteria evaluation of suppliers is the key element to select the most fitting one for a specific service requested by a particular customer. This process of suppliers’ selection directly affects success and duration of the relationship between the GSP and its customers. The content of our work consists of five parts: first, variables identification and description, necessary to create an objective and comprehensive evaluation of GSP’s suppliers; second, weights calculation of defined variables accordingly to the AHP method; third, mathematical model formulation in order to precisely describe the decision problem; fourth, data collection and database creation containing all of the raw data necessary to perform the evaluation; fifth, DSS development and test with potential users through a web application prototype specifically developed for the problem.

2018 - Looking at the SDEWES Index from a Multi-Criterion Decision Analysis Perspective [Relazione in Atti di Convegno]
Pretolani, Daniele
abstract

The SDEWES Index is obtained by aggregating several numerical indicators related to sustainable development. In the context of Multi-Criterion Decision Analysis (MCDA) this index can be seen as the solution to the “ranking problematic” for an underlying decisional problem. Accordingly, in this work we look at the SDEWES Index from an MCDA point of view. First, we consider some theoretical aspects, in particular the one usually referred to as “rank reversal”. Then we consider some (classic as well as original) visual tools for decision aid, showing how they can be adapted and exploited.

2014 - Apportionments with minimum Gini index of disproportionality: a Quadratic Knapsack approach [Articolo su rivista]
Pretolani, Daniele
abstract

The ultimate goal of proportional apportionment methods is the minimization of disproportionality, i.e., unequal distribution of political representation among voters, or citizens. The Gini index is a well known tool for measuring inequality. In this work we propose a quotient method that minimizes the Gini index of disproportionality. Our method reduces the rounding of quotas to an instance of quadratic knapsack, a widely studied combinatorial optimization problem. Preliminary computational results, including real cases from the EU Parliament and the US House of Representatives, show that the method is effective, since the instances to solve are rather easy.

2014 - Ranking paths in stochastic time-dependent networks [Articolo su rivista]
Lars Relund, Nielsen; Kim Allan, Andersen; Pretolani, Daniele
abstract

In this paper we address optimal routing problems in networks where travel times are both stochastic and time-dependent. In these networks, the best route choice is not necessarily a path, but rather a "time-adaptive strategy" that assigns successors to nodes as a function of time. Nevertheless, in some particular cases an origin-destination path must be chosen "a priori", since time-adaptive choices are not allowed. Unfortunately, finding the a priori shortest path is an NP-hard problem. In this paper, we propose a solution method for the a priori shortest path problem, and we show that it can be easily extended to the ranking of the first K shortest paths. Our method exploits the solution of the time-adaptive routing problem as a relaxation of the a priori problem. Computational results are presented showing that, under realistic distributions of travel times and costs, our solution methods are effective and robust.

2013 - Finding hypernetworks in directed hypergraphs [Articolo su rivista]
Pretolani, Daniele
abstract

The term ‘‘hypernetwork’’ (more precisely, s-hypernetwork and (s, d)-hypernetwork) has been recently adopted to denote some logical structures contained in a directed hypergraph. A hypernetwork identifies the core of a hypergraph model, obtained by filtering off redundant components. Therefore, finding hypernetworks has a notable relevance both from a theoretical and from a computational point of view. In this paper we provide a simple and fast algorithm for finding s-hypernetworks, which substantially improves on a method previously proposed in the literature. We also point out two linearly solvable particular cases. Finding an (s, d)-hypernetwork is known to be a hard problem, and only one polynomially solvable class has been found so far. Here we point out that this particular case is solvable in linear time.

2011 - Optimization and probabilistic satisfiability on nested and co-nested formulas [Articolo su rivista]
Pretolani, Daniele
abstract

Nested and co-nested formulas are two classes of CNF instances that can be characterized in terms of outerplanar graphs. For these classes, linear time algorithms are known for SAT and (unweighted) Max-SAT. In this paper we devise linear time algorithms for a general optimization version of SAT. Moreover, we show that a general probabilistic version of SAT reduces to solving a system of linear inequalities where the number of variables and constraints is linear in the size of the formula.

2010 - An aggregate label setting policy for the multi-objective shortest path problem [Articolo su rivista]
Iori, Manuel; S., Martello; Pretolani, Daniele
abstract

We consider label setting algorithms for the multi-objective shortest path problem with any number of sum and bottleneck objectives. We propose a weighted sum aggregate ordering of the labels, specifically tailored to combine sum and bottleneck objectives. We show that the aggregate order leads to a consistent reduction of solution times (up to two-thirds) with respect to the classical lexicographic order.

2009 - Bicriterion shortest paths in stochastic time-dependent networks [Capitolo/Saggio]
K. A., Andersen; L. R., Nielsen; Pretolani, Daniele
abstract

In recent years there has been a growing interest in using stochastic time-dependent (STD) networks as a modelling tool for a number of applications within such areas as transportation and telecommunications. It is known that an optimal routing policy does not necessarily correspond to a path, but rather to a time-adaptive strategy. In some applications, however, it makesgood sense to require that the routing policy should correspond to a loopless path in the network, that is, the time-adaptive aspect disappears and a priori route choice is considered.In this paper we consider bicriterion a priori route choice in STD networks, i.e. the problem of finding the set of efficient paths. Both expectation and min-max criteria are considered and a solution method based on the two-phase method is devised. Experimental results reveal that the full set of efficientsolutions can be determined on rather large test instances, which is in contrast to the time-adaptive case.

2009 - Time-adaptive and history-adaptive multicriterion routing in stochastic, time-dependent networks [Articolo su rivista]
Pretolani, Daniele; L. R., Nielsen; K. A., Andersen; M., Ehrgott
abstract

We compare two different models for multicriterion routing in stochastic time-dependent networks: the classic ‘‘time-adaptive’’ model and the more flexible ‘‘history-adaptive’’ one. We point out several properties of the sets of efficient solutions found under the two models. We also devise a method for finding supported history-adaptive solutions.

2008 - Shortest Paths in Piecewise Continuous Time-Dependent Networks [Articolo su rivista]
Dell'Amico, Mauro; Iori, Manuel; Pretolani, Daniele
abstract

We consider a shortest path problem, where the travel times on the arcs may vary with time and waiting at any node is allowed. Simple adaptations of the Dijkstra algorithm may fail to solve the problem, when discontinuities exist. We propose a new Dijkstra-like algorithm that overcomes these difficulties.

2008 - The stack loading and unloading problem [Articolo su rivista]
F., Malucelli; S., Pallottino; Pretolani, Daniele
abstract

When piling a set of items in a single stack, one often does not pay attention to the order. Real-life experience suggests that, whenever a specific item is suddenly requested, we need to dig very deep into the stack to extract it.In this paper we investigate stack reordering strategies aiming at minimizing the number of "pop" and "push" operations. In particular we focus on three versions of the problem in which reordering can take place in different phases: when unloading the stack, when loading it or in both phases.We show that the first two variants can be solved in linear time, while for the third one we devise a dynamic programming method with quadratic complexity.

2006 - Finding the K shortest hyperpaths using reoptimization [Articolo su rivista]
K. A., Andersen; L. R., Nielsen; Pretolani, Daniele
abstract

We present some reoptimization techniques for computing (shortest) hyperpath weights in a directed hypergraph.These techniques are exploited to improve the worst-case computational complexity (as well as the practical performance) of an algorithm finding the K shortest hyperpaths in acyclic hypergraphs.

2005 - Finding the K shortest hyperpaths [Articolo su rivista]
K. A., Andersen; L. R., Nielsen; Pretolani, Daniele
abstract

The K shortest paths problem has been extensively studied for many years. Efficient methods have been devised, and many practical applications are known. Shortest hyperpath models have been proposed for several problems in different areas, for example in relation with routing in dynamic networks. However, the K shortest hyperpaths problem has not yet been investigated.In this paper we present procedures for finding the K shortest hyperpaths in a directed hypergraph. This is done by extending existing algorithms for K shortest loopless paths. Computational experiments on the proposed procedures are performed, and applications in transportation, planning and combinatorial optimization are discussed.

2005 - Probability Logic and Optimization SAT: the PSAT and CPA Models [Articolo su rivista]
Pretolani, Daniele
abstract

Both probabilistic satisfiability (PSAT) and the check of coherence of probability assessment (CPA) can be considered as probabilistic counterparts of the classical propositional satisfiability problem (SAT). Actually, CPA turns out to be a particular case of PSAT; in this paper, we compare the computational complexity of these two problems for some classes of instances. First, we point out the relations between these probabilistic problems and two well known optimization counterparts of SAT, namely Max SAT and Min SAT. We then prove that Max SAT with unrestricted weights is NP-hard for the class of graph formulas, where Min SAT can be solved in polynomial time. In light of the aforementioned relations, we conclude that PSAT is NP-complete for ideal formulas, where CPA can be solved in linear time.

2004 - Hypergraph Reductions and Satisfiability Problems [Capitolo/Saggio]
Pretolani, Daniele
abstract

Although several tractable classes of SAT are known, none of these turns out to be easy for optimization, probabilistic and counting versions of SAT. These problems can be solved efficiently for formulas with bounded treewidth. However, the resulting time bounds are exponential in the treewidth, which means exponential in the size of the largest clause.In this paper we show that solution methods for formulas with treewidth two can be combined with specialized techniques for dealing with "long" clauses, thus obtaining time bounds independent of the treewidth. This leads to the definition of a new class of tractable instances for SAT and its extensions. This class is related to a particular class of reducible hypergraphs, that extends partial 2-trees and hypertrees.

2003 - Bicriterion Shortest Hyperpaths in Random Time-Dependent Networks [Articolo su rivista]
K. A., Andersen; L. R., Nielsen; Pretolani, Daniele
abstract

In relevant application areas, such as transportation and telecommunications, there has recently been a growing focus on random time-dependent networks (RTDNs), where arc lengths are represented by time-dependent discrete random variables. In such networks, an optimal routing policy does not necessarily correspond to a path, but rather to an adaptive strategy. Finding an optimal strategy reduces to a shortest hyperpath problem that can be solved quite efficiently.The bicriterion shortest path problem, i.e. the problem of finding the set of efficient paths, has been extensively studied for many years. Recently, extensions to RTDNs have been investigated. However, no attempt has been made to study bicriterion strategies. This is the aim of this paper.Here we model bicriterion strategy problems in terms of bicriterion shortest hyperpaths, and we devise an algorithm for enumerating the set of efficient hyperpaths. Since the computational effort required for a complete enumeration may be prohibitive, we propose some heuristic methods to generate a subset of the efficient solutions. Different criteria are considered, such as expected or maximum travel time or cost; a computational experience is reported.

2002 - On bandwidth-2 graphs [Articolo su rivista]
A., Caprara; F., Malucelli; Pretolani, Daniele
abstract

We give a partial characterization of graphs of bandwidth two, whose structure has been exploited to a very limited extent so far. Our results are used to derive a new linear-time recognition algorithm which is much simpler to describe than the previously known one. In particular, we shortly describe an implementation of our algorithm.

2001 - Easy cases of probabilistic satisfiability [Articolo su rivista]
K. A., Andersen; Pretolani, Daniele
abstract

The Probabilistic Satisfiability problem (PSAT) can be considered as a probabilistic counterpart of the classical SAT problem. In a PSAT instance, each clause in a CNF formula is assigned a probability of being true; the problem consists in checking the consistency of the assigned probabilities. Actually, PSAT turns out to be computationally much harder than SAT, e.g., it remains difficult for some classes of formulas where SAT can be solved in polynomial time. A column generation approach has been proposed in the literature, where the pricing subproblem reduces to a Weighted Max-SAT problem on the original formula. Here we consider some easy cases of PSAT, where it is possible to give a compact representation of the set of consistent probability assignments. We follow two different approaches, based on two different representations of CNF formulas. First we consider a representation based on directed hypergraphs. By extending a well-known integer programming formulation of SAT and Max-SAT, we solve the case in which the hypergraph does not contain cycles; a linear time algorithm is provided for this case. Then we consider the co-occurrence graph associated with a formula. We provide a solution method for the case in which the co-occurrence graph is a partial 2-tree, and we show how to extend this result to partial k-trees with k > 2.

2000 - A directed hypergraph model for random time dependent shortest paths [Articolo su rivista]
Pretolani, Daniele
abstract

We consider routing problems in dynamic networks where arc travel times are both random and time dependent. The problem of finding the best route to a fixed destination is formulated in terms of shortest hyperpaths on a suitable time-expanded directed hypergraph. The latter problem can be solved in linear time, with respect to the size of the hypergraph, for several definitions of hyperpath length. Different criteria for ranking routes can be modeled by suitable definitions of hyperpath length. We also show that the problem becomes intractable if a constraint on the route structure is imposed.

2000 - Auction algorithms for shortest hyperpath problems [Articolo su rivista]
R., DE LEONE; Pretolani, Daniele
abstract

The auction-reduction algorithm is a strongly polynomial version of the auction method for the shortest path problem. In this paper we extend the auction-reduction algorithm to different types of shortest hyperpath problems in directed hypergraphs. The results of preliminary computational experiences show that the auction-reduction method is comparable to other known methods for specific classes of hypergraphs.

1998 - Max Horn SAT and the minimum cut problem in directed hypergraphs [Articolo su rivista]
G., Gallo; C., Gentile; Pretolani, Daniele; G., Rago
abstract

In this paper we consider the Maximum Horn Satisfiability problem, which is reduced to the problem of finding a minimum cardinality cut on a directed hypergraph. For the latter problem, we propose different IP formulations, related to three different defnitions of hyperpath weight. We investigate the properties of their linear relaxations, showing that they define a hierarchy. The weakest relaxation is shown to be equivalent to the relaxation of a well known IP formulation of Max Horn SAT, and to a max-flow problem on hypergraphs. The tightest relaxation, which is a disjunctive programming problem, is shown to have integer optimum. The intermediate relaxation consists in a set covering problem with a possible exponential number of constraints. This latter relaxation provides an approximation of the convex hull of the integer solutions which, as proven by the experimental results given, is much tighter than the one known in the literature.

1998 - On some path problems on oriented hypergraphs [Articolo su rivista]
S., Nguyen; Pretolani, Daniele; L., Markenzon
abstract

The BF-graphs form a particular class of directed hypergraphs. For this important family, several applications are known in data bases and in the artificial intelligence domain. These hypergraphs may also be used to describe the behaviour of concurrent systems. We present here a theoretical analysis of several hyperpath problems for BF-graphs, with emphasis on the acyclic BF-graphs. After briefly explaining the basic concepts of directed hypergraphs, we present an algorithm for finding a BF-path. We next discuss the problem of finding a hyperpath cover, and present a polynomial solution for two constrained hyperpath problems.

1996 - Efficiency and stability of hypergraph SAT algorithms [Capitolo/Saggio]
Pretolani, Daniele
abstract

We discuss some topics related to the practical efficiency of exact methods for satisfiability. We use directed hypergraphs as an algorithmic and modeling tool; in particular, we propose a new relaxation technique, based on a hypergraph depth first search procedure. We discuss our computational experience, comparing the suitability of different approaches for various classes of instances.

1996 - Hierarchies of polynomially solvable satisfiability problems [Articolo su rivista]
Pretolani, Daniele
abstract

In this paper, we introduce general techniques for extending classes of polynomially solvable SAT instances. We generalize the approach of Gallo and Scutellà, obtaining a family of polynomial hierarchies, where one such polynomial hierarchy is a sequence of nested polynomially solvable classes that cover the whole set of CNF formulas. Following a different approach, based on a new decomposition technique, we define the class of Split-Horn formulas, which is a proper extension of the Generalized Horn formulas defined by Yamasaki e Doshita. We discuss and compare the basic properties of the proposed classes; polynomial time recognition and solution algorithms are provided.

1995 - A new algorithm for the propositional satisfiability problem [Articolo su rivista]
G., Gallo; Pretolani, Daniele
abstract

A new enumeration algorithm is proposed for the propositional satisfiability problem. Such algorithm is based on a hypergraph formulation of the problem. Two different implementations of the algorithm are presented together with the results of an experimentation intended to compare their performance with the performance of other known methods. The computational results obtained are quite promising.

1995 - Lower bounds for the quadratic semi-assignment problem [Articolo su rivista]
F., Malucelli; Pretolani, Daniele
abstract

This paper presents a class of lower bounds for the Quadratic Semi-Assignment Problem (QSAP). These bounds are based on recent results on polynomially solvable cases, in particular we will consider the QSAPs whose quadratic cost coefficients define a reducible graph. The idea is to decompose the problem into several subproblems, each defined on a reducible subgraph. A Lagrangean decomposition technique is used to improve the results. Several lower bounds are computationally compared on several types of test problems.

1993 - A linear time algorithm for unique Horn satisfiability [Articolo su rivista]
Pretolani, Daniele
abstract

In this paper, we consider the Unique-SAT problem for Horn formulas (Unique-HornSAT). We use directed hypergraphs to represent Horn formulas, and devise a solution method based on a hypergraph transformation technique. In the implementation, we solve a particular disjoint set union problem for which linear amortized time algorithms are known. As a result, we obtain a linear time algorithm for Unique-HornSAT.

1993 - Efficient labelling algorithms for the maximum noncrossing matching problem [Articolo su rivista]
F., Malucelli; T., Ottmann; Pretolani, Daniele
abstract

Consider a bipartite graph; let’s suppose we draw the origin nodes and the destination nodes arranged in two columns, and the edges as straight-line segments. A noncrossing matching is a subset of edges such that no two of them intersect. Several algorithms for the problem of finding the noncrossing matching of maximum cardinality are proposed. Moreover an extension to weighted graphs is considered.