Refereed work

An improved cut-and-solve algorithm for the single-source capacitated facility location problem

S.L. Gadegaard and A. Klose and L.R. Nielsen
EURO Journal on Computational Optimization, 1-27 (2017)
[pdf | doi | bibtex]

Abstract: In this paper, we present an improved cut-and-solve algorithm for the single-source capacitated facility location problem. The algorithm consists of three phases. The first phase strengthens the integer program by a cutting plane algorithm to obtain a tight lower bound. The second phase uses a two-level local branching heuristic to find an upper bound, and if optimality has not yet been established, the third phase uses the cut-and-solve framework to close the optimality gap. Extensive computational results are reported, showing that the proposed algorithm runs 10–80 times faster on average compared to state-of-the-art problem-specific algorithms.

A bi-objective approach to discrete cost-bottleneck location problems

S.L. Gadegaard and A Klose and L.R. Nielsen
Annals of Operations Research, 1-23 (2016)
[pdf | doi | bibtex]

Abstract: This paper considers a family of bi-objective discrete facility location problems with a cost objective and a bottleneck objective. A special case is, for instance, a bi-objective version of the (vertex) p-centdian problem. We show that bi-objective facility location problems of this type can be solved efficiently by means of an epsilon-constraint method that solves at most (n-1)m minisum problems, where n is the number of customer points and m the number of potential facility sites. Additionally, we compare the approach to a lexicographic epsilon-constrained method that only returns efficient solutions and to a two-phase method relying on the perpendicular search method. We report extensive computational results obtained from several classes of facility location problems. The proposed algorithm compares very favorably to both the lexicographic epsilon-constrained method and to the two phase method.

A hierarchical Markov decision process modeling feeding and marketing decisions of growing pigs

Pourmoayed, Reza and Nielsen, Lars Relund and Kristensen, Anders Ringgaard
European Journal of Operational Research, 250 (3), 925-938 (2016)
[pdf | doi | bibtex]

Abstract: Feeding is the most important cost in the production of growing pigs and has a direct impact on the marketing decisions, growth and the final quality of the meat. In this paper, we address the sequential decision problem of when to change the feed-mix within a finisher pig pen and when to pick pigs for marketing. We formulate a hierarchical Markov decision process with three levels representing the decision process. The model considers decisions related to feeding and marketing and finds the optimal decision given the current state of the pen. The state of the system is based on information from on-line repeated measurements of pig weights and feeding and is updated using a Bayesian approach. Numerical examples are given to illustrate the features of the proposed optimization model.

Markov decision processes to model livestock systems

Nielsen, L.R. and Kristensen, A.R.
In book "Handbook of Operations Research in Agriculture and the Agri-Food Industry" , 224, 419-454 (2015)
Series: International Series in Operations Research & Management Science
[pdf | doi | bibtex]

Abstract: Livestock farming problems are often sequential in nature. For instance at a specific time instance the decision on whether to replace an animal or not is based on known information and expectation about the future. At the next decision epoch updated information is available and the decision choice is re-evaluated. As a result Markov decision processes (MDPs) have been used to model livestock decision problems over the last decades. The objective of this chapter is to review the increasing amount of papers using MDPs to model livestock farming systems and provide an overview over the recent advances within this branch of research. Moreover, theory and algorithms for solving both ordinary and hierarchical MDPs are given and possible software for solving MDPs are considered.

Ranking paths in stochastic time-dependent networks

L.R. Nielsen and K.A. Andersen and D. Pretolani
European Journal of Operational Research, 236 (3), 903-914 (2014)
[pdf | doi | bibtex]

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.

Inventory control in a lost-sales setting with information about supply lead times

Abhijit Bhagwan Bendre and Lars Relund Nielsen
International Journal of Production Economics, 142 (2), 324-331 (2013)
[pdf | doi | bibtex]

Abstract: Supply chain collaboration using advancements in information technology is on the rise and this includes sharing of information between suppliers and buyers. In this paper we study the value of information about the development of supply lead times from a buyer's perspective. We consider a periodically reviewed single-item inventory system in a lost sales setting where at most one order can be outstanding at a time. We compare the performance of an inventory model assuming informed lead times to a model assuming uninformed independent and identically distributed lead times. We employ the dynamic programming approach to find the best state-dependent ordering policy to minimize the expected average total cost per time unit. Our numerical results show that acquiring information about the development of supply lead times is of value. In general the best policy suggested by the model assuming informed lead times causes lower average cost than the model assuming uninformed lead times.

Embedding a state space model into a Markov decision process

L.R Nielsen and E. Jørgensen and S. Højsgaard
Annals of Operations Research, 190 (1), 289-309 (2011)
[pdf | doi | bibtex]

Abstract: In agriculture Markov decision processes (MDPs) with finite state and action space are often used to model sequential decision making over time. For instance, states in the process represent possible levels of traits of the animal and transition probabilities are based on biological models estimated from data collected from the animal or herd. State space models (SSMs) are a general tool for modeling repeated measurements over time where the model parameters can evolve dynamically. In this paper we consider methods for embedding an SSM into an MDP with finite state and action space. Different ways of discretizing an SSM are discussed and methods for reducing the state space of the MDP are presented. An example from dairy production is given.

Optimal Replacement Policies for Dairy Cows Based on Daily Yield Measurements

L.R Nielsen and E. Jørgensen and A.R. Kristensen and S. Østergaard
Journal of Dairy Science, 93 (1), 77-92 (2010)
[pdf | doi | bibtex]

Abstract: Markov decision processes (MDP) with finite state and action space have often been used to model sequential decision making over time in dairy herds. However, the length of each stage has been at least 1 mo, resulting in models that do not support decisions on a daily basis. The present paper describes the first step of developing an MDP model that can be integrated into a modern herd management system. A hierarchical MDP was formulated for the dairy cow replacement problem with stage lengths of 1 d. It can be used to assist the farmer in replacement decisions on a daily basis and is based on daily milk yield measurements that are available in modern milking systems. Bayesian updating was used to predict the performance of each cow in the herd and economic decisions were based on the prediction. Moreover, parameters in the model were estimated using data records of the specific herd under consideration. This includes herd-specific lactation curves.

Quantifying walking and standing behaviour of dairy cows using a moving average based on output from an accelerometer

L.R Nielsen and A.R. Pedersen and M.S. Herskin and L. Munksgaard
Applied Animal Behaviour Science, 127 (1-2), 12-19 (2010)
[pdf | doi | bibtex]

Abstract: Manual observations either directly or by analysis of video recordings of dairy cow behaviour in loose housing systems are costly. Therefore progress could be made if reliable estimates of duration of walking and standing could be based on automatic recordings. In this study we developed algorithms for the detection of walking and standing in dairy cows based on the output from an electronic device quantifying acceleration in three dimensions. Ten cows were equipped with one movement sensor on each hind leg. The cows were then walked one by one in the alleys of the barn and encouraged to stand and walk in sequences of approximately 20 seconds for period of 10 minutes. Afterwards the cows were stimulated to move/lift the legs while standing in a cubicle. The behaviour was video recorded, and the recordings were analysed second by second for walking and standing behaviour as well as the number of steps taken. Various algorithms for predicting walking/standing status were compared. The algorithms were all based on a limit of a moving average calculated by using one of two outputs of the accelerometer, either a motion index or a step count, and applied over periods of three or five seconds. Furthermore, we investigated the effect of additionally applying the rule: a walking period must last at least five seconds. The results indicate that the lowest misclassification rate (10\%) of walking and standing was obtained based on the step count with a moving average of three seconds and with the rule applied. However, the rate of misclassification given walking and standing differed between algorithms, thus the choice of algorithm should relate to the specific question under consideration. In conclusion, the results suggest that the number of steps taken per time unit as well as the frequency and duration of walking and standing can be estimated with a reasonable accuracy.

Erratum to ``An algorithm for ranking assignments using reoptimization'' [Computers and Operations Research 35 (2008) 3714-3726]

Pedersen, C.R. and Nielsen, L.R. and Andersen, K.A.
Computers and Operations Research, 37, 426-427 (2010)
[pdf | doi | bibtex]

Abstract: We compare an algorithm written by Miller et al. in IEEE Transactions on Aerospace and Electronic Systems against our own implementation.

Bicriterion shortest paths in stochastic time-dependent networks

L.R. Nielsen and D. Pretolani and K.A. Andersen
In book "Multiobjective Programming and Goal Programming" , 618, 57-67 (2009)
Series: Lecture Notes in Economics and Mathematical Systems
[pdf | doi | bibtex]

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 makes good 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 efficient solutions can be determined on rather large test instances, which is in contrast to the time-adaptive case.

Time-adaptive and history-adaptive multicriterion routing in stochastic, time-dependent networks

D. Pretolani and L.R. Nielsen and K.A. Andersen and M. Ehrgott
Operations Research Letters, 37 (3), 201-205 (2009)
[pdf | doi | bibtex]

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.

The Bicriterion Multi Modal Assignment Problem: Introduction, Analysis, and Experimental Results

Pedersen, C.R. and Nielsen, L.R. and Andersen, K.A.
Informs Journal on Computing, 20 (3), 400–411 (2008)
[pdf | doi | bibtex]

Abstract: We consider the bicriterion multi modal assignment problem which is a new generalization of the classical linear assignment problem. A two-phase solution method using an effective ranking scheme is presented. The algorithm is valid for generating all nondominated criterion points or an approximation. Extensive computational results are conducted on a large library of test instances to test the performance of the algorithm and to identify hard test instances. Also, test results of the algorithm applied to the bicriterion assignment problem is provided.

An algorithm for ranking assignments using reoptimization

Pedersen, C.R. and Nielsen, L.R. and Andersen, K.A.
Computers and Operations Research, 35 (11), 3714-3726 (2008)
[pdf | doi | bibtex]

Abstract: We consider the problem of ranking assignments according to cost in the classical linear assignment problem. An algorithm partitioning the set of possible assignments, as suggested by Murty, is presented where, for each partition, the optimal assignment is calculated using a new reoptimization technique. Its computational performance is compared with all available implementations of algorithms with the same time complexity. The results are encouraging.

Finding the $K$ best policies in a finite-horizon Markov decision process

Nielsen, L.R. and Kristensen, A.R.
European Journal of Operational Research, 175 (2), 1164–1179 (2006)
[pdf | doi | bibtex]

Abstract: Directed hypergraphs represent a general modelling and algorithmic tool, which have been successfully used in many different research areas such as artificial intelligence, database systems, fuzzy systems, propositional logic and transportation networks. However, modelling Markov decision processes using directed hypergraphs has not yet been considered.
In this paper we consider finite-horizon Markov decision processes (MDPs) with finite state and action space and present an algorithm for finding the K best policies. That is, we are interested in ranking the first K policies in non-decreasing order using an additive criterion of optimality. The algorithm uses a directed hypergraph to model the finite-horizon MDP. It is shown that the problem of finding the optimal policy can be formulated as a minimum weight hyperpath problem and be solved in linear time, with respect to the input data representing the MDP, using different additive optimality criteria.

Finding the $K$ shortest hyperpaths using reoptimization

L.R. Nielsen and D. Pretolani and K.A. Andersen
Operations Research Letters, 34 (2), 155–164 (2006)
[pdf | doi | bibtex]

Abstract: The shortest hyperpath problem is an extension of the classical shortest path problem and has applications in many different areas. Recently, algorithms for finding the K shortest hyperpaths in a directed hypergraph have been developed by Andersen, Nielsen and Pretolani. In this paper we improve the worst-case computational complexity of an algorithm for finding the K shortest hyperpaths in an acyclic hypergraph. This result is obtained by applying new reoptimization techniques for shortest hyperpaths.
The algorithm turns out to be quite effective in practice and has already been successfully applied in the context of stochastic time-dependent networks, for finding the K best strategies and for solving bicriterion problems.

Finding the $K$ Shortest Hyperpaths

L.R. Nielsen and K.A. Andersen and D. Pretolani
Computers and Operations Research, 32 (6), 1477–1497 (2005)
[pdf | doi | bibtex]

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.

Route Choice in Stochastic Time-Dependent Networks

L.R. Nielsen
Department of Operations Research, University of Aarhus (2003)
Ph.D. thesis
[pdf | bibtex]

Abstract: This thesis deals with problems concerning route choice in stochastic time-dependent networks (STD networks). STD networks are an extension of more ``traditional'' networks where the travel time or cost between two nodes (towns, telephone switches etc.) are deterministic and time-independent. In stochastic time-dependent networks the travel time between two nodes is time-dependent, i.e. the travel time depends on the leaving time from a node. Furthermore, it is assumed that for each leaving time, the travel time may not be fully known and hence a probability function is used to express possible travel times.
Route choice problems in STD networks may be regarded as extensions of traditional shortest path problems in directed graphs. The problem of finding a shortest path in a directed graph may be considered as two problems in an STD network, depending on whether the entire route, denoted a strategy, must be specified a priori, i.e. before travel begins (a priori route choice) or whether the driver is allowed to react while travelling on the revealed/actual arrival times at intermediate nodes (time-adaptive route choice).
The problem of finding the best route/strategy under a priori or time-adaptive route choice consists in finding a strategy which is minimal with respect to a specific objective, e.g. expected travel time.
This thesis focuses on two route choice problems in STD networks, namely the problem of finding the K best strategies under a priori and time-adaptive route choice and bicriterion route choice under a priori and time-adaptive route choice. Here we assume that two criteria are given, e.g. minimizing expected travel time and cost. The goal is now to find efficient strategies, i.e. strategies for which it is not possible to find a different strategy such that expected travel time or cost is improved without getting a worse expected cost or travel time, respectively.

Bicriterion Shortest Hyperpaths in Random Time-Dependent Networks

L.R. Nielsen and K.A. Andersen and D. Pretolani
IMA Journal of Management Mathematics, 14 (3), 271–303 (2003)
[pdf | doi | bibtex]

Abstract: In relevant application areas, such as transportation and telecommunications, there has recently been a growing focus on random time-dependent networks (RTDN), 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.

Technical Reports

Bi-objective branch-and-cut algorithms: Applications to the single source capacitated facility location problem

S.L. Gadegaard and M. Ehrgott and L.R. Nielsen
Optimization Online (2016)
[pdf | bibtex]

Abstract: Most real-world optimization problems are of a multi-objective nature, involving objectives which are conflicting and incomparable. Solving a multi-objective optimization problem requires a method which can generate the set of rational compromises between the objectives. In this paper, we propose two distinct bound set based branch-and-cut algorithms for bi-objective combinatorial optimization problems, based on implicitly and explicitly stated lower bound sets, respectively. The algorithm based on explicitly given lower bound sets computes for each branching node a lower bound set and compares it to an upper bound set. The implicit bound set based algorithm, on the other hand, fathoms branching nodes by generating a single point on the lower bound set for each local nadir point. We outline several approaches for fathoming branching nodes and we propose an updating scheme for the lower bound sets that prevents us from solving the bi-objective LP-relaxation of each branching node. To strengthen the lower bound sets, we propose a bi-objective cutting plane algorithm that dynamically adjusts the weights of the objective functions such that different parts of the feasible set are strengthened by cutting planes. In addition, we suggest an extension of the branching strategy "Pareto branching''. Extensive computational results obtained for the bi-objective single source capacitated facility location problem prove the effectiveness of the algorithms.

An overview over pig production of fattening pigs with a focus on possible decisions in the production chain

Pourmoayed, R. and Nielsen, L.R.
Aarhus University, PigIT Report No. 4 (2014)
[pdf | bibtex]


Udredningsrapport om økonomisk foderoptimering i den enkelte besætning baseret på NorFor Plan

S. Østergaard and M. Weisbjerg and O. Aaes and N. Friggens and T. Kristensen and A.R. Kristensen and L.R. Nielsen and D. Bossen
Det Jordbrugsvidenskabelige Fakultet, Aarhus Universitet, DJF husdyrbrug 14 (2009)
[pdf | bibtex]


Time-adaptive versus history-adaptive strategies for multicriterion routing in stochastic time-dependent networks

D. Pretolani and L.R. Nielsen and K.A. Andersen and M. Ehrgott
Department of Business Studies, Aarhus School of Business, L-2008-05 (2008)
[pdf | bibtex]

Abstract: We compare two different models for multicriterion routing in stochastic time-dependent networks: the classic ``time-adaptive'' route choice and the more flexible ``history-adaptive'' route choice. We point out some interesting properties of the sets of efficient solutions (``strategies'') found under the two models. We also suggest possible directions for improving computational techniques.

Bicriterion a priori route choice in stochastic time-dependent networks

L.R. Nielsen and D. Pretolani and K.A. Andersen
Department of Business Studies, Aarhus School of Business, WP-L-2006-10 (2006)
[pdf | bibtex]

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 makes good sense to require that the routing policy corresponds 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 approach is devised. Experimental results reveal that the full set of efficient solutions can be determined on rather large test instances, which is in contrast to previously reported results for the time-adaptive case.

A note on "Multicriteria adaptive paths in stochastic, time-varying networks"

D. Pretolani and L.R. Nielsen and K.A. Andersen
Department of Business Studies, Aarhus School of Business, L-2006-11 (2006)
[pdf | bibtex]

Abstract: In this note we consider stochastic time-varying networks (STV networks, also known as stochastic or random time-dependent networks) where the arcs carry multiple attributes. In particular, we address some incorrect results contained in a recent paper by Opasanon and Miller-Hooks (2006). In STV networks travel times are modelled as random variables with time-dependent distri- butions. STV networks were first addressed by Hall (1986), who showed that the best route between two nodes is not necessarily a path, but rather a time-adaptive strategy that assigns optimal successor arcs to a node as a function of departure time. A detailed review of the literature on the subject can be found in the recent paper by Gao and Chabini (2006), where time-adaptive route choice is considered in a more general framework, that takes into account several variants of online information.

Risk Management in Forestry - Possible Solution Approaches

Nielsen, L.R. and Kristensen, A.R.
Danish Informatics Network in the Agriculture Sciences (DINA), The Royal Veterinary and Agricultural University, DINA Notat No. 111 (2005)
[pdf | bibtex]

Abstract: Risk management has received increased attention in the forest economics literature. Forest owners making harvesting decisions face many uncertain parameters such as price uncertainty, uncertainty about future growth and quality etc. The cost of ignoring these risk factors might be high. This note present a simple multi-level hierarchic Markov decision process modelling a forest stand. Three risk criteria are introduced, namely, the variance risk, the expected total consequence risk and the catastrophe avoidance risk criterion. Bicriterion solution procedures using directed hypergraphs are discussed.

On the Bicriterion Multi Modal Assignment Problem

Pedersen, C.R. and Nielsen, L.R. and Andersen, K.A.
Department of Operations Research, University of Aarhus, WP-2005-3 (2005)
[pdf | bibtex]

Abstract: We consider the bicriterion multi modal assignment problem which is a new generalization of the classical linear assignment problem. A two-phase solution method using an effective ranking scheme is presented. The algorithm is valid for generating all nondominated criterion points or an approximation. Extensive computational results are conducted on a large library of test instances to test the performance of the algorithm and to identify hard test instances. Also, test results of the algorithm applied to the bicriterion assignment problem is given. Here our algorithm outperforms all previously known exact solution methods for this problem class.

A note on ranking assignments using reoptimization

Pedersen, C.R. and Nielsen, L.R. and Andersen, K.A.
Department of Operations Research, University of Aarhus, WP-2005-2 (2005)
An article with a better implementation is shown under 'Refereed Work'
[pdf | bibtex]

Abstract: We consider the problem of ranking assignments according to cost in the classical linear assignment problem. An algorithm partitioning the set of possible assignments, as suggested by Murty, is presented where, for each partition, the optimal assignment is calculated using a new reoptimization technique. Computational results for the new algorithm are presented.

Finding the $K$ best policies in finite-horizon Markov decision processes

Nielsen, L.R. and Kristensen, A.R.
Danish Informatics Network in the Agriculture Sciences (DINA), The Royal Veterinary and Agricultural University, DINA Research Report No. 110 (2004)
[pdf | bibtex]

Abstract: Directed hypergraphs represent a general modelling and algorithmic tool, which have been successfully used in many different research areas such as artificial intelligence, database systems, fuzzy systems, propositional logic and transportation networks. However, modelling Markov decision processes using directed hypergraphs has not yet been considered.
In this paper we consider finite-horizon Markov decision processes (MDPs) with finite state and action space and present an algorithm for finding the K best policies. That is, we are interested in ranking the first K policies in non-decreasing order using an additive criterion of optimality. The algorithm uses a directed hypergraph to model the finite-horizon MDP. It is shown that the problem of finding the optimal policy can be formulated as a minimum weight hyperpath problem and be solved in linear time, with respect to the input data representing the MDP, using different additive optimality criteria.

Risk aversion in Markov decision processes

L.R. Nielsen and A.R. Kristensen
Proceedings of the European Workshop for Decision Problems in Agriculture and Natural Resources (EWDA-04)
[pdf | bibtex]

Abstract: The majority of the work in the area of Markov decision processes (MDPs) has focused on optimization criteria that are based on expected values of the rewards or costs. However, such risk-neutral approaches are not always applicable and expressive enough.
In this paper we present the preliminary results of a research project focussing on incorporating risk into MDPs by modelling MDPs using directed hypergraphs. Two risk measures are considered, namely, the variance of the total discounted reward given a policy and the expected total risk when assuming a separate risk for each time, state and action.
First, we consider recursive equations for calculating the variance/risk or maximum risk. Second, it is shown how a state-expanded directed hypergraph can be used to model a finite-horizon MDP. Here a policy corresponds to a so called hypertree. As a result, the optimal policy under e.g. the expected total cost criterion can be found solving a shortest hypertree problem on the state-expanded hypergraph. Finally, bicriterion solution techniques for directed hypergraphs are used to calculate the trade-off between risk and cost.

$K$ shortest paths in stochastic time-dependent networks

L.R. Nielsen and D. Pretolani and K.A. Andersen
Department of Accounting, Finance and Logistics, Aarhus School of Business, WP-L-2004-05 (2004)
[pdf | bibtex]

Abstract: A substantial amount of research has been devoted to the shortest path problem in networks where travel times are stochastic or (deterministic and) time-dependent. More recently, a growing interest has been attracted by networks that 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. In some particular cases, the shortest origin-destination path must nevertheless be chosen a priori, since time-adaptive choices are not allowed. Unfortunately, finding the a priori shortest path is NP-hard, while the best time-adaptive strategy can be found in polynomial time.
In this paper, we propose a solution method for the a priori shortest path problem, and we show that it can be easily adapted to the ranking of the first K shortest paths. Moreover, we present a computational comparison of time-adaptive and a priori route choices, pointing out the effect of travel time and cost distributions. The reported results show that, under realistic distributions, our solution methods are effective.

Finding the $K$ shortest hyperpaths using reoptimization

L.R. Nielsen and D. Pretolani and K.A. Andersen
Department of Accounting, Finance and Logistics, Aarhus School of Business, WP-L-2004-04 (2004)
A published version with more figures is listed under refereed work.
[pdf | bibtex]

Abstract: The shortest hyperpath problem is an extension of the classical shortest path problem and has applications in many different areas. Recently, algorithms for finding the K shortest hyperpaths in a directed hypergraph have been developed by Andersen, Nielsen and Pretolani. In this paper we improve the worst-case computational complexity of an algorithm for finding the K shortest hyperpaths in an acyclic hypergraph. This result is obtained by applying new reoptimization techniques for shortest hyperpaths.
The algorithm turns out to be quite effective in practice and has already been successfully applied in the context of stochastic time-dependent networks, for finding the K best strategies and for solving bicriterion problems.

Bicriterion Shortest Hyperpaths in Random Time-Dependent Networks

L.R. Nielsen and K.A. Andersen and D. Pretolani
Department of Operations Research, University of Aarhus, WP-2003-1 (2003)
A published version with fewer computational results is listed under refereed work.
[pdf | bibtex]

Abstract: In relevant application areas, such as transportation and telecommunications, there has recently been a growing focus on dynamic networks, 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.
Bicriterion shortest path problems have been extensively studied for many years. Recently, extensions to dynamic networks 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. For several problems arising in this context, optimal solutions can be found quite efficiently. Moreover, the general problem of listing efficient strategies can be successfully dealt with by means of heuristic methods. A computational experience is reported, where we consider several variants of the above problems. Finally, the relevant features of the bicriterion hyperpath model are discussed and compared to the classical bicriterion path approach.

Finding the $K$ Shortest Hyperpaths: algorithms and applications

L.R. Nielsen and K.A. Andersen and D. Pretolani
Department of Operations Research, University of Aarhus, WP-2002-2 (2002)
A published version with fewer computational results is listed under refereed work.
[pdf | bibtex]

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.

A Remark on the Definition of a B-Hyperpath

L.R. Nielsen and D. Pretolani
Department of Operations Research, University of Aarhus (2001)
[pdf | bibtex]

Abstract: In this note we show that a commonly used definition of a hyperpath in a directed hypergraph is not correct. This is done by presenting a counter-example which fulfils the definition but is not a hyperpath.

A Bicriterion and Parametric Analysis of the Shortest Hyperpath Problem

Lars Relund Nielsen
Department of Operations Research, University of Aarhus (2001)
Master thesis
[pdf | bibtex]

Abstract: Contains the work of the two first years of my Ph.D. Contains first a summary of the three manuscripts included in the back of the report.

The Facets of the Set Packing Polytope: A Logical Interpretation

Kim A. Andersen and Lars R. Nielsen and Morten Riis and Anders J. V. Skriver
Department of Operations Research, University of Aarhus, WP-2000-3 (2000)
[pdf | bibtex]

Abstract: In this paper we present a logical interpretation of all the facets of the set packing polytope. The approach is based on results obtained in probabilistic logic (probabilistic satisfiability) and reveals an interesting connection between probabilistic logic and integer linear programming.

Other publications

Culling pigs under price fluctuations

Pourmoayed, Reza and Nielsen, Lars Relund
OrBit, 27, 26-31 (2016)
[pdf | bibtex]


TEGP - Time-Expanded Generator with Peaks (v1.66)

L.R. Nielsen
(2013)
[pdf | bibtex]

Abstract: This manual provides documentation of the Time-Expanded Generator with Peaks (TEGP) which generates instances of stochastic time-dependent networks. The program includes several features inspired by typical aspects of road networks (congestion effects, waiting, random perturbations etc.).

Det optimale udskiftningstidspunkt for en malkeko

L.R. Nielsen and E. Jørgensen
OrBit, 17, 14-16 (2010)
[pdf | bibtex]


Koens økonomiske værdi

L.R. Nielsen and S. Højsgaard
Ny KvægForskning, 5, 8-9 (2009)
[pdf | bibtex]


TEGP - Time-Expanded Generator with Peaks (v1.5)

L.R. Nielsen
(2006)
[pdf | bibtex]

Abstract: This manual provides documentation of the Time-Expanded Generator with Peaks (TEGP) which generates instances of stochastic time-dependent networks. The program includes several features inspired by typical aspects of road networks (congestion effects, waiting, random perturbations etc.).

APGen - an assignment problem generator

L.R. Nielsen and C.R. Pedersen
(2005)
[pdf | bibtex]

Abstract: This manual provide documentation for the Assignment Problem Generator (APGen) which generate problem instances for the bicriterion assignment problem. Also instances for the bicriterion multi modal assignment problem can be generated. The instance generated will be output as an xml file which may be converted to a desired format using an xslt stylesheet. Instances for similar single criterion problems can also be generated by e.g. only considering the first criterion.

The papers distributed here have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.