
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 DeepFrozen 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 realworld 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 multicriteria 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 sevenyear period of realdata 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 wellknown 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 multicriteria 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 MultiCriterion 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 MultiCriterion 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 timedependent 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 timedependent.
In these networks, the best route choice is not necessarily a path, but rather a "timeadaptive strategy" that assigns successors to nodes as a function of time.
Nevertheless, in some particular cases an origindestination path must be chosen "a priori", since timeadaptive choices are not allowed. Unfortunately, finding the a priori shortest path is an NPhard 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 timeadaptive 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, shypernetwork 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 shypernetworks, 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 conested formulas
[Articolo su rivista]
Pretolani, Daniele
abstract
Nested and conested 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) MaxSAT. 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 multiobjective shortest path problem
[Articolo su rivista]
Iori, Manuel; S., Martello; Pretolani, Daniele
abstract
We consider label setting algorithms for the multiobjective 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 twothirds) with respect to the classical lexicographic order.
2009
 Bicriterion shortest paths in stochastic timedependent networks
[Capitolo/Saggio]
K. A., Andersen; L. R., Nielsen; Pretolani, Daniele
abstract
In recent years there has been a growing interest in using stochastic timedependent (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 timeadaptive 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 timeadaptive 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 minmax criteria are considered and a solution method based on the twophase 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 timeadaptive case.
2009
 Timeadaptive and historyadaptive multicriterion routing in stochastic, timedependent 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 timedependent networks: the classic ‘‘timeadaptive’’ model and the more flexible ‘‘historyadaptive’’ 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 historyadaptive solutions.
2008
 Shortest Paths in Piecewise Continuous TimeDependent 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 Dijkstralike 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. Reallife 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 worstcase 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 NPhard 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 NPcomplete 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 2trees and hypertrees.
2003
 Bicriterion Shortest Hyperpaths in Random TimeDependent 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 timedependent networks (RTDNs), where arc lengths are represented by timedependent 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 bandwidth2 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 lineartime 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 Satisﬁability 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 difﬁcult 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 MaxSAT 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 wellknown integer programming formulation of SAT and MaxSAT, 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 cooccurrence graph associated with a formula. We provide a solution method for the case in which the cooccurrence graph is a partial 2tree, and we show how to extend this result to partial ktrees 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 timeexpanded 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 auctionreduction algorithm is a strongly polynomial version of the auction method for the shortest path problem. In this paper we extend the auctionreduction algorithm to diﬀerent types of shortest hyperpath problems in directed hypergraphs. The results of preliminary computational experiences show that the auctionreduction method is comparable to other known methods for speciﬁc 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 maxflow 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 BFgraphs 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 BFgraphs, with emphasis on the acyclic BFgraphs. After briefly explaining the basic concepts of directed hypergraphs, we present an algorithm for finding a BFpath. 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 SplitHorn 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 semiassignment problem
[Articolo su rivista]
F., Malucelli; Pretolani, Daniele
abstract
This paper presents a class of lower bounds for the Quadratic SemiAssignment 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 UniqueSAT problem for Horn formulas (UniqueHornSAT). 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 UniqueHornSAT.
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 straightline 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.