Refereed work
Warmstarting lower bound set computations for branchandbound algorithms for multi objective integer linear programsForget, N. and Gadegaard, S. L. and Nielsen, L. R.European Journal of Operational Research, In press (2022) [pdf  doi  bibtex]
Abstract: In this paper we propose a generic branchandbound algorithm for solving multiobjective integer linear programming problems. In the recent literature, competitive frameworks has been proposed for biobjective 0–1 problems, and many of these frameworks rely on the use of the linear relaxation to obtain lower bound sets. When increasing the number of objective functions, however, the polyhedral structure of the linear relaxation becomes more complex, and consequently requires more computational effort to obtain. In this paper we overcome this obstacle by speeding up the computations. To do so, in each branching node we use information available from its father node to warmstart a Bensonslike algorithm. We show that the proposed algorithm significantly reduces the CPU time of the framework on several different problem classes with three, four and five objective functions. Moreover, we point out difficulties that arise when nonbinary integer variables are introduced in the models, and test our algorithm on problem that contains nonbinary integer variables too.


Optimizing pig marketing decisions under price fluctuationsR. Pourmoayed and L.R. NielsenAnnals of Operations Research (2020) [pdf  doi  bibtex]
Abstract: In the manufacturing of fattening pigs, pig marketing refers to a sequence of culling decisions until the production unit is empty. The profit of a production unit is highly dependent on the price of pork, the cost of feeding and the cost of buying piglets. Price fluctuations in the market consequently influence the profit, and the optimal marketing decisions may change under different price conditions. Most studies have considered pig marketing under constant price conditions. However, because price fluctuations have an influence on profit and optimal marketing decisions it is relevant to consider pig marketing under price fluctuations. In this paper we formulate a hierarchical Markov decision process with two levels which model sequential marketing decisions under price fluctuations in a pig pen. The state of the system is based on information about pork, piglet and feed prices. Moreover, the information is updated using a Bayesian approach and embedded into the hierarchical Markov decision process. The optimal policy is analyzed under different patterns of price fluctuations. We also assess the value of including price information into the model.


Biobjective BranchandCut Algorithms Based on LP Relaxation and Bound SetsS.L. Gadegaard and L.R. Nielsen and M. EhrgottInforms Journal on Computing, 31 (4), 790804 (2019) [pdf  doi  bibtex]
Abstract: Most realworld optimization problems are of a multiobjective nature, involving objectives which are conflicting and incomparable. Solving a multiobjective 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 branchandcut algorithms for biobjective 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 biobjective LPrelaxation of each branching node. To strengthen the lower bound sets, we propose a biobjective 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 biobjective single source capacitated facility location problem prove the effectiveness of the algorithms.


An approximate dynamic programming approach for sequential pig marketing decisions at herd levelR. Pourmoayed and L.R. NielsenEuropean Journal of Operational Research, 276 (3), 10561070 (2019) [pdf  doi  bibtex]
Abstract: One of the most important operations in the production of growing/finishing pigs is the marketing of pigs for slaughter. While pork production can be managed at different levels (animal, pen, section, or herd), it is beneficial to consider the herd level when determining the optimal marketing policy due to interdependencies, such as those created by fixed transportation costs and crosslevel constraints. In this paper, we consider sequential marketing decisions at herd level. A highdimensional infinitehorizon Markov decision process (MDP) is formulated which, due to the curse of dimensionality, cannot be solved using standard MDP optimization techniques. Instead, approximate dynamic programming (ADP) is applied to solve the model and find the best marketing policy at herd level. Under the total expected discounted reward criterion, the proposed ADP approach is first compared with a standard solution algorithm for solving an MDP at pen level to show the accuracy of the solution procedure. Next, numerical experiments at herd level are given to confirm how the marketing policy adapts itself to varying costs (e.g., transportation cost) and crosslevel constraints. Finally, a sensitivity analysis for some parameters in the model is conducted and the marketing policy found by ADP is compared with other wellknown marketing polices, often applied at herd level.


A biobjective approach to discrete costbottleneck location problemsS.L. Gadegaard and A Klose and L.R. NielsenAnnals of Operations Research, 267, 179201 (2018) [pdf  doi  bibtex]
Abstract: This paper considers a family of biobjective discrete facility location problems with a cost objective and a bottleneck objective. A special case is, for instance, a biobjective version of the (vertex) pcentdian problem. We show that biobjective facility location problems of this type can be solved efficiently by means of an ε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 εconstrained method that only returns efficient solutions and to a twophase 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 ε constrained method and to the two phase method.


An improved cutandsolve algorithm for the singlesource capacitated facility location problemS.L. Gadegaard and A. Klose and L.R. NielsenEURO Journal on Computational Optimization, 6 (1), 127 (2018) [pdf  doi  bibtex]
Abstract: In this paper, we present an improved cutandsolve algorithm for the singlesource 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 twolevel local branching heuristic to find an upper bound, and if optimality has not yet been established, the third phase uses the cutandsolve 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 stateoftheart problemspecific algorithms.


A hierarchical {Markov} decision process modeling feeding and marketing decisions of growing pigsPourmoayed, Reza and Nielsen, Lars Relund and Kristensen, Anders RinggaardEuropean Journal of Operational Research, 250 (3), 925938 (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 feedmix 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 online 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 systemsNielsen, L.R. and Kristensen, A.R.In book "Handbook of Operations Research in Agriculture and the AgriFood Industry" , 224, 419454 (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 reevaluated. 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 timedependent networksL.R. Nielsen and K.A. Andersen and D. PretolaniEuropean Journal of Operational Research, 236 (3), 903914 (2014) [pdf  doi  bibtex]
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.


Inventory control in a lostsales setting with information about supply lead timesAbhijit Bhagwan Bendre and Lars Relund NielsenInternational Journal of Production Economics, 142 (2), 324331 (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 singleitem 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 statedependent 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 processL.R Nielsen and E. Jørgensen and S. HøjsgaardAnnals of Operations Research, 190 (1), 289309 (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.


Erratum to ``An algorithm for ranking assignments using reoptimization'' [Computers and Operations Research 35 (2008) 37143726]Pedersen, C.R. and Nielsen, L.R. and Andersen, K.A.Computers and Operations Research, 37, 426427 (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.


Optimal Replacement Policies for Dairy Cows Based on Daily Yield MeasurementsL.R Nielsen and E. Jørgensen and A.R. Kristensen and S. ØstergaardJournal of Dairy Science, 93 (1), 7792 (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 herdspecific lactation curves.


Quantifying walking and standing behaviour of dairy cows using a moving average based on output from an accelerometerL.R Nielsen and A.R. Pedersen and M.S. Herskin and L. MunksgaardApplied Animal Behaviour Science, 127, 1219 (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.


Timeadaptive and historyadaptive multicriterion routing in stochastic, timedependent networksD. Pretolani and L.R. Nielsen and K.A. Andersen and M. EhrgottOperations Research Letters, 37 (3), 201205 (2009) [pdf  doi  bibtex]
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.


Bicriterion shortest paths in stochastic timedependent networksL.R. Nielsen and D. Pretolani and K.A. AndersenIn book "Multiobjective Programming and Goal Programming" , 618, 5767 (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
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 makes
good 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 efficient
solutions can be determined on rather large test instances, which is in
contrast to the timeadaptive case.


The Bicriterion Multi Modal Assignment Problem: Introduction, Analysis, and Experimental ResultsPedersen, C.R. and Nielsen, L.R. and Andersen, K.A.Informs Journal on Computing, 20 (3), 400411 (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 twophase 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 reoptimizationPedersen, C.R. and Nielsen, L.R. and Andersen, K.A.Computers and Operations Research, 35 (11), 37143726 (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$} shortest hyperpaths using reoptimizationL.R. Nielsen and D. Pretolani and K.A. AndersenOperations Research Letters, 34 (2), 155164 (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 worstcase 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 timedependent networks, for finding the K best strategies and for solving bicriterion problems. 

Finding the {$K$} best policies in a finitehorizon {M}arkov decision processNielsen, L.R. and Kristensen, A.R.European Journal of Operational Research, 175 (2), 11641179 (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 finitehorizon 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 nondecreasing order using an additive criterion of optimality. The algorithm uses a directed hypergraph to model the finitehorizon 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 HyperpathsL.R. Nielsen and K.A. Andersen and D. PretolaniComputers and Operations Research, 32 (6), 14771497 (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. 

Bicriterion Shortest Hyperpaths in Random TimeDependent NetworksL.R. Nielsen and K.A. Andersen and D. PretolaniIMA Journal of Management Mathematics, 14 (3), 271303 (2003) [pdf  doi  bibtex]
Abstract: In relevant application areas, such as transportation and telecommunications, there has recently been a growing focus on random timedependent 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. 

Route Choice in Stochastic TimeDependent NetworksL.R. NielsenDepartment of {O}perations {R}esearch, {U}niversity of {A}arhus (2003) [pdf  bibtex]
Abstract: This thesis deals with problems concerning route choice in stochastic timedependent 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 timeindependent. In stochastic timedependent networks the travel time between two nodes is timedependent, 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 (timeadaptive route choice). The problem of finding the best route/strategy under a priori or timeadaptive 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 timeadaptive route choice and bicriterion route choice under a priori and timeadaptive 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. 
Technical Reports
Linear relaxation based branchandbound for multiobjective integer programming with warmstartingForget, N. and Gadegaard, S.L. and Nielsen, L.R.Optimizaton Online (2021) [pdf  bibtex]
Abstract: In this paper we propose a generic branchandbound algorithm for solving multiobjective integer linear programming problems. % In the recent literature, competitive frameworks has been proposed for biobjective 01 problems, and many of these frameworks rely on the use of the linear relaxation to obtain lower bound sets. When increasing the number of objective functions, however, the polyhedral structure of the linear relaxation becomes more complex, and consequently requires more computational effort to obtain. In this paper we overcome this obstacle by speeding up the computations. To do so, in each branching node we use information available from its farther node to warmstart a Bensonslike algorithm. We show that the proposed algorithm significantly reduces the CPU time of the framework on several different problem classes with three, four and five objective functions. Moreover, we point out difficulties that arise when nonbinary integer variables are introduced in the models, and test our algorithm on problem that contains nonbinary integer variables too.


Branchandbound and objective branching with three objectivesForget, N. and Klamroth, K. and Gadegaard, S.L. and Przybylski, A. and Nielsen, L.R.Optimizaton Online (2020) [pdf  bibtex]
Abstract: The recent success of biobjective BranchandBound (B&B) algorithms heavily relies on the efficient computation of upper and lower bound sets. Besides the classical dominance test, bound sets are used to improve the computational time by imposing inequalities derived from (partial) dominance in the objective space. This process is called objective branching since it is mostly applied when generating child nodes. In this paper, we extend the concept of objective branching to triobjective combinatorial optimization problems. Several difficulties arise in this case, as there is no longer a lexicographic order among nondominated outcome vectors in the multiobjective case, with more than two objectives. We discuss the general concept of objective branching in any number of dimensions and suggest a merging operation of local upper bounds to avoid the generation of redundant subproblems. Numerical experiments on triobjective knapsack, assignment and facility location problems show a significant speedup in the B&B framework.


Biobjective branchandcut algorithms: Applications to the single source capacitated facility location problemS.L. Gadegaard and M. Ehrgott and L.R. NielsenOptimization Online (2016) [pdf  bibtex]
Abstract: Most realworld optimization problems are of a multiobjective nature, involving objectives which are conflicting and incomparable. Solving a multiobjective 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 branchandcut algorithms for biobjective 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 biobjective LPrelaxation of each branching node. To strengthen the lower bound sets, we propose a biobjective 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 biobjective 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 chainPourmoayed, R. and Nielsen, L.R.Aarhus University (2014) [pdf  bibtex] 

Udredningsrapport om økonomisk foderoptimering i den enkelte besætning baseret på NorFor PlanS. Østergaard and M. Weisbjerg and O. Aaes and N. Friggens and T. Kristensen and A.R. Kristensen and L.R. Nielsen and D. BossenDet Jordbrugsvidenskabelige Fakultet, Aarhus Universitet (2009) [pdf  bibtex] 

Timeadaptive versus historyadaptive strategies for multicriterion routing in stochastic timedependent networksD. Pretolani and L.R. Nielsen and K.A. Andersen and M. EhrgottDepartment of Business Studies, Aarhus School of Business (2008) [pdf  bibtex]
Abstract: We compare two different models for multicriterion routing in stochastic
timedependent networks: the classic ``timeadaptive'' route choice and the
more flexible ``historyadaptive'' 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.


A note on "Multicriteria adaptive paths in stochastic, timevarying networks"D. Pretolani and L.R. Nielsen and K.A. AndersenDepartment of Business Studies, Aarhus School of Business (2006) [pdf  bibtex]
Abstract: In this note we consider stochastic timevarying networks (STV networks, also known as stochastic
or random timedependent networks) where the arcs carry multiple attributes. In particular, we
address some incorrect results contained in a recent paper by Opasanon and MillerHooks (2006).
In STV networks travel times are modelled as random variables with timedependent 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 timeadaptive 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 timeadaptive route
choice is considered in a more general framework, that takes into account several variants of online
information.


Bicriterion a priori route choice in stochastic timedependent networksL.R. Nielsen and D. Pretolani and K.A. AndersenDepartment of {B}usiness {S}tudies, {A}arhus {S}chool of {B}usiness (2006) [pdf  bibtex]
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
makes good sense to require that the routing policy corresponds 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
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 timeadaptive case.


On the Bicriterion Multi Modal Assignment ProblemPedersen, C.R. and Nielsen, L.R. and Andersen, K.A.Department of Operations Research, University of Aarhus (2005) [pdf  bibtex]
Abstract: We consider the bicriterion multi modal assignment problem which is a new generalization of the classical linear assignment problem. A twophase 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 reoptimizationPedersen, C.R. and Nielsen, L.R. and Andersen, K.A.Department of Operations Research, University of Aarhus (2005) [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.


Risk Management in Forestry  Possible Solution ApproachesNielsen, L.R. and Kristensen, A.R.Danish Informatics Network in the Agriculture Sciences (DINA), The Royal Veterinary and Agricultural University (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 multilevel 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.


{$K$} shortest paths in stochastic timedependent networksL.R. Nielsen and D. Pretolani and K.A. AndersenDepartment of {A}ccounting, {F}inance and {L}ogistics, {A}arhus {S}chool of {B}usiness (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) timedependent. More recently, a growing interest has been attracted by networks that 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. In some particular cases, the shortest origindestination path must nevertheless be chosen a priori, since timeadaptive choices are not allowed. Unfortunately, finding the a priori shortest path is NPhard, while the best timeadaptive 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 timeadaptive 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 reoptimizationL.R. Nielsen and D. Pretolani and K.A. AndersenDepartment of {A}ccounting, {F}inance and {L}ogistics, {A}arhus {S}chool of {B}usiness (2004) [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 worstcase 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 timedependent networks, for finding the K best strategies and for solving bicriterion problems. 

Finding the {$K$} best policies in finitehorizon {M}arkov decision processesNielsen, L.R. and Kristensen, A.R.Danish Informatics Network in the Agriculture Sciences (DINA), The Royal Veterinary and Agricultural University (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 finitehorizon 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 nondecreasing order using an additive criterion of optimality. The algorithm uses a directed hypergraph to model the finitehorizon 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 {M}arkov decision processesL.R. Nielsen and A.R. KristensenProceedings 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 riskneutral 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 stateexpanded directed hypergraph can be used to model a finitehorizon 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 stateexpanded hypergraph. Finally, bicriterion solution techniques for directed hypergraphs are used to calculate the tradeoff between risk and cost. 

Bicriterion Shortest Hyperpaths in Random TimeDependent NetworksL.R. Nielsen and K.A. Andersen and D. PretolaniDepartment of {O}perations {R}esearch, {U}niversity of {A}arhus (2003) [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 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.
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 applicationsL.R. Nielsen and K.A. Andersen and D. PretolaniDepartment of {O}perations {R}esearch, {U}niversity of {A}arhus (2002) [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}HyperpathL.R. Nielsen and D. PretolaniDepartment of {O}perations {R}esearch, {U}niversity of {A}arhus (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 counterexample which fulfils the definition but is not a hyperpath.


A Bicriterion and Parametric Analysis of the Shortest Hyperpath ProblemLars Relund NielsenDepartment of {O}perations {R}esearch, {U}niversity of {A}arhus (2001) [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 InterpretationKim A. Andersen and Lars R. Nielsen and Morten Riis and Anders J. V. SkriverDepartment of {O}perations {R}esearch, {U}niversity of {A}arhus (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
{TEGP}  TimeExpanded Generator with Peaks (v1.66)L.R. Nielsen(2013) [pdf  bibtex]
Abstract: This manual provides documentation of the TimeExpanded Generator with Peaks (TEGP) which
generates instances of stochastic timedependent networks. The program includes several features inspired
by typical aspects of road networks (congestion effects, waiting, random perturbations etc.).


{TEGP}  TimeExpanded Generator with Peaks (v1.5)L.R. Nielsen(2006) [pdf  bibtex]
Abstract: This manual provides documentation of the TimeExpanded Generator with Peaks (TEGP) which
generates instances of stochastic timedependent networks. The program includes several features inspired
by typical aspects of road networks (congestion effects, waiting, random perturbations etc.).


{APGen}  an assignment problem generatorL.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.
