@ARTICLE{Pourmoayed20, author = {R. Pourmoayed and L.R. Nielsen}, title = {Optimizing pig marketing decisions under price fluctuations}, year = {2020}, journal = {Annals of Operations Research}, doi = {10.1007/s10479-020-03646-0}, 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.}, }
@ARTICLE{Gadegaard19a, author = {S.L. Gadegaard and L.R. Nielsen and M. Ehrgott}, title = {Biobjective Branch-and-Cut Algorithms Based on LP Relaxation and Bound Sets}, year = {2019}, volume = {31}, number = {4}, journal = {Informs Journal on Computing}, pages = {790--804}, doi = {10.1287/ijoc.2018.0846}, 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.}, }
@ARTICLE{Gadegaard18b, author = {S.L. Gadegaard and A Klose and L.R. Nielsen}, title = {A bi-objective approach to discrete cost-bottleneck location problems}, year = {2018}, volume = {267}, journal = {Annals of Operations Research}, pages = {179--201}, doi = {10.1007/s10479-016-2360-8}, 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 ε-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 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 ε -constrained method and to the two phase method.}, }
@ARTICLE{Gadegaard18a, author = {S.L. Gadegaard and A. Klose and L.R. Nielsen}, title = {An improved cut-and-solve algorithm for the single-source capacitated facility location problem}, year = {2018}, volume = {6}, number = {1}, journal = {EURO Journal on Computational Optimization}, pages = {1-27}, doi = {10.1007/s13675-017-0084-4}, 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.}, }
@TECHREPORT{Gadegaard16a, author = {S.L. Gadegaard and M. Ehrgott and L.R. Nielsen}, title = {Bi-objective branch-and-cut algorithms: Applications to the single source capacitated facility location problem}, month = {April}, year = {2016}, institution = {Optimization Online}, url = {www.optimization-online.org/DB_HTML/2016/04/5402.html}, 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.}, }
@ARTICLE{Pourmoayed16, author = {Pourmoayed, Reza and Nielsen, Lars Relund and Kristensen, Anders Ringgaard}, title = {A hierarchical {Markov} decision process modeling feeding and marketing decisions of growing pigs}, year = {2016}, volume = {250}, number = {3}, journal = {European Journal of Operational Research}, pages = {925-938}, doi = {10.1016/j.ejor.2015.09.038}, 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.}, }
@MISC{Pourmoayed16a, author = {Pourmoayed, Reza and Nielsen, Lars Relund}, title = {Culling pigs under price fluctuations}, month = {November}, year = {2016}, url = {https://www.research.relund.dk}, }
@INBOOK{Relund15a, author = {Nielsen, L.R. and Kristensen, A.R.}, chapter = {Markov decision processes to model livestock systems}, title = {Handbook of Operations Research in Agriculture and the Agri-Food Industry}, booktitle = {Handbook of Operations Research in Agriculture and the Agri-Food Industry}, publisher = {Springer}, editor = {Lluis M. Plà-Aragonés}, year = {2015}, volume = {224}, series = {International Series in Operations Research \& Management Science}, pages = {419-454}, doi = {10.1007/978-1-4939-2483-7_19}, 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.}, }
@TECHREPORT{Pourmoayed14a, author = {Pourmoayed, R. and Nielsen, L.R.}, title = {An overview over pig production of fattening pigs with a focus on possible decisions in the production chain}, year = {2014}, institution = {Aarhus University}, url = {http://www.pigit.ku.dk/publications/PigIT-Report4.pdf}, }
@ARTICLE{Relund14a, author = {L.R. Nielsen and K.A. Andersen and D. Pretolani}, title = {Ranking paths in stochastic time-dependent networks}, year = {2014}, volume = {236}, number = {3}, journal = {European Journal of Operational Research}, pages = {903-914}, doi = {10.1016/j.ejor.2013.10.022}, 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.}, }
@ARTICLE{Bendre13, author = {Abhijit Bhagwan Bendre and Lars Relund Nielsen}, title = {Inventory control in a lost-sales setting with information about supply lead times}, year = {2013}, volume = {142}, number = {2}, journal = {International Journal of Production Economics}, pages = {324-331}, doi = {10.1016/j.ijpe.2012.12.002}, 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.}, }
@MISC{Relund13a, author = {L.R. Nielsen}, title = {{TEGP} - Time-Expanded Generator with Peaks (v1.66)}, month = {July}, year = {2013}, url = {https://www.research.relund.dk}, 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.).}, }
@ARTICLE{Relund10b, author = {L.R Nielsen and E. Jørgensen and S. Højsgaard}, title = {Embedding a state space model into a Markov decision process}, year = {2011}, volume = {190}, number = {1}, journal = {Annals of Operations Research}, pages = {289-309}, doi = {10.1007/s10479-010-0688-z}, 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.}, }
@ARTICLE{Pedersen10, author = {Pedersen, C.R. and Nielsen, L.R. and Andersen, K.A.}, title = {Erratum to ``An algorithm for ranking assignments using reoptimization'' [Computers and Operations Research 35 (2008) 3714-3726]}, year = {2010}, volume = {37}, journal = {Computers and Operations Research}, pages = {426-427}, doi = {10.1016/j.cor.2009.04.009}, abstract = {We compare an algorithm written by Miller et al. in IEEE Transactions on Aerospace and Electronic Systems against our own implementation.}, }
@ARTICLE{Relund10a, author = {L.R Nielsen and E. Jørgensen and A.R. Kristensen and S. Østergaard}, title = {Optimal Replacement Policies for Dairy Cows Based on Daily Yield Measurements}, year = {2010}, volume = {93}, number = {1}, journal = {Journal of Dairy Science}, pages = {77-92}, doi = {10.3168/jds.2009-2209}, 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.}, }
@ARTICLE{Relund10c, author = {L.R Nielsen and A.R. Pedersen and M.S. Herskin and L. Munksgaard}, title = {Quantifying walking and standing behaviour of dairy cows using a moving average based on output from an accelerometer}, year = {2010}, volume = {127}, journal = {Applied Animal Behaviour Science}, pages = {12-19}, doi = {10.1016/j.applanim.2010.08.004}, 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.}, }
@MISC{Relund10d, author = {L.R. Nielsen and E. Jørgensen}, title = {Det optimale udskiftningstidspunkt for en malkeko}, month = {July}, year = {2010}, url = {www.research.relund.dk}, }
@TECHREPORT{Oestergaard09, author = {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}, title = {Udredningsrapport om økonomisk foderoptimering i den enkelte besætning baseret på NorFor Plan}, month = {February}, year = {2009}, institution = {Det Jordbrugsvidenskabelige Fakultet, Aarhus Universitet}, }
@ARTICLE{Pretolani09, author = {D. Pretolani and L.R. Nielsen and K.A. Andersen and M. Ehrgott}, title = {Time-adaptive and history-adaptive multicriterion routing in stochastic, time-dependent networks}, year = {2009}, volume = {37}, number = {3}, journal = {Operations Research Letters}, pages = {201-205}, doi = {10.1016/j.orl.2009.02.001}, 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.}, }
@INBOOK{Relund09, author = {L.R. Nielsen and D. Pretolani and K.A. Andersen}, chapter = {Bicriterion shortest paths in stochastic time-dependent networks}, title = {Multiobjective Programming and Goal Programming}, publisher = {Springer Berlin Heidelberg}, editor = {V. Barichard and M. Ehrgott and X. Gandibleux and V. T'Kindt}, year = {2009}, volume = {618}, series = {Lecture Notes in Economics and Mathematical Systems}, pages = {57-67}, doi = {10.1007/978-3-540-85646-7_6}, 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.}, }
@MISC{Relund09b, author = {L.R. Nielsen and S. Højsgaard}, title = {Koens økonomiske værdi}, month = {October}, year = {2009}, }
@ARTICLE{Pedersen08, author = {Pedersen, C.R. and Nielsen, L.R. and Andersen, K.A.}, title = {The Bicriterion Multi Modal Assignment Problem: Introduction, Analysis, and Experimental Results}, year = {2008}, volume = {20}, number = {3}, journal = {Informs Journal on Computing}, pages = {400--411}, doi = {10.1287/ijoc.1070.0253}, 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.}, }
@ARTICLE{Pedersen08a, author = {Pedersen, C.R. and Nielsen, L.R. and Andersen, K.A.}, title = {An algorithm for ranking assignments using reoptimization}, year = {2008}, volume = {35}, number = {11}, journal = {Computers and Operations Research}, pages = {3714-3726}, doi = {10.1016/j.cor.2007.04.008}, 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.}, }
@TECHREPORT{Pretolani08, author = {D. Pretolani and L.R. Nielsen and K.A. Andersen and M. Ehrgott}, title = {Time-adaptive versus history-adaptive strategies for multicriterion routing in stochastic time-dependent networks}, year = {2008}, institution = {Department of Business Studies, Aarhus School of Business}, 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.}, }
@TECHREPORT{Pretolani06, author = {D. Pretolani and L.R. Nielsen and K.A. Andersen}, title = {A note on "Multicriteria adaptive paths in stochastic, time-varying networks"}, year = {2006}, institution = {Department of Business Studies, Aarhus School of Business}, url = {www.asb.dk}, 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.}, }
@ARTICLE{Relund05b, author = {L.R. Nielsen and D. Pretolani and K.A. Andersen}, title = {Finding the {$K$} shortest hyperpaths using reoptimization}, year = {2006}, volume = {34}, number = {2}, journal = {Operations Research Letters}, pages = {155--164}, doi = {10.1016/j.orl.2005.04.008}, 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. \par 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.}, }
@ARTICLE{Relund06, author = {Nielsen, L.R. and Kristensen, A.R.}, title = {Finding the {$K$} best policies in a finite-horizon {M}arkov decision process}, year = {2006}, volume = {175}, number = {2}, journal = {European Journal of Operational Research}, pages = {1164--1179}, doi = {10.1016/j.ejor.2005.06.011}, 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. \par 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.}, }
@MISC{Relund06b, author = {L.R. Nielsen}, title = {{TEGP} - Time-Expanded Generator with Peaks (v1.5)}, month = {January}, year = {2006}, url = {https://www.research.relund.dk}, 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.).}, }
@TECHREPORT{Relund06c, author = {L.R. Nielsen and D. Pretolani and K.A. Andersen}, title = {Bicriterion a priori route choice in stochastic time-dependent networks}, year = {2006}, institution = {Department of {B}usiness {S}tudies, {A}arhus {S}chool of {B}usiness}, url = {http://www.asb.dk/}, 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.}, }
@TECHREPORT{Pedersen05, author = {Pedersen, C.R. and Nielsen, L.R. and Andersen, K.A.}, title = {On the Bicriterion Multi Modal Assignment Problem}, month = {December}, year = {2005}, institution = {Department of Operations Research, University of Aarhus}, url = {http://www.imf.au.dk/publs?id=586}, 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.}, }
@TECHREPORT{Pedersen05b, author = {Pedersen, C.R. and Nielsen, L.R. and Andersen, K.A.}, title = {A note on ranking assignments using reoptimization}, month = {December}, year = {2005}, institution = {Department of Operations Research, University of Aarhus}, url = {http://www.imf.au.dk/publs?id=585}, 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.}, }
@ARTICLE{Relund05, author = {L.R. Nielsen and K.A. Andersen and D. Pretolani}, title = {Finding the {$K$} Shortest Hyperpaths}, year = {2005}, volume = {32}, number = {6}, journal = {Computers and Operations Research}, pages = {1477--1497}, doi = {10.1016/j.cor.2003.11.014}, 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. \par 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.}, }
@TECHREPORT{Relund05a, author = {Nielsen, L.R. and Kristensen, A.R.}, title = {Risk Management in Forestry - Possible Solution Approaches}, month = {January}, year = {2005}, institution = {Danish Informatics Network in the Agriculture Sciences (DINA), The Royal Veterinary and Agricultural University}, url = {www.research.relund.dk}, 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.}, }
@MISC{Relund06a, author = {L.R. Nielsen and C.R. Pedersen}, title = {{APGen} - an assignment problem generator}, month = {December}, year = {2005}, url = {https://www.research.relund.dk}, 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.}, }
@TECHREPORT{Relund04b, author = {L.R. Nielsen and D. Pretolani and K.A. Andersen}, title = {{$K$} shortest paths in stochastic time-dependent networks}, year = {2004}, institution = {Department of {A}ccounting, {F}inance and {L}ogistics, {A}arhus {S}chool of {B}usiness}, url = {http://www.asb.dk/}, 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. \par 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.}, }
@TECHREPORT{Relund04d, author = {L.R. Nielsen and D. Pretolani and K.A. Andersen}, title = {Finding the {$K$} shortest hyperpaths using reoptimization}, year = {2004}, institution = {Department of {A}ccounting, {F}inance and {L}ogistics, {A}arhus {S}chool of {B}usiness}, url = {http://www.asb.dk/}, 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. \par 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.}, }
@TECHREPORT{Relund04e, author = {Nielsen, L.R. and Kristensen, A.R.}, title = {Finding the {$K$} best policies in finite-horizon {M}arkov decision processes}, year = {2004}, institution = {Danish Informatics Network in the Agriculture Sciences (DINA), The Royal Veterinary and Agricultural University}, url = {www.research.relund.dk}, 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. \par 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.}, }
@INPROCEEDINGS{Relund04f, author = {L.R. Nielsen and A.R. Kristensen}, title = {Risk aversion in {M}arkov decision processes}, booktitle = {Proceedings of the European Workshop for Decision Problems in Agriculture and Natural Resources ({EWDA}-04)}, month = {September}, year = {2004}, address = {Silsoe Research Institute, Silsoe, England}, url = {www.research.relund.dk}, 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. \par 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. \par 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.}, }
@TECHREPORT{Relund02b, author = {L.R. Nielsen and K.A. Andersen and D. Pretolani}, title = {Bicriterion Shortest Hyperpaths in Random Time-Dependent Networks}, year = {2003}, institution = {Department of {O}perations {R}esearch, {U}niversity of {A}arhus}, url = {http://www.imf.au.dk/publs?id=419}, 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. \par 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. \par 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.}, }
@ARTICLE{Relund03a, author = {L.R. Nielsen and K.A. Andersen and D. Pretolani}, title = {Bicriterion Shortest Hyperpaths in Random Time-Dependent Networks}, year = {2003}, volume = {14}, number = {3}, journal = {IMA Journal of Management Mathematics}, pages = {271--303}, doi = {10.1093/imaman/14.3.271}, 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. \par 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. \par 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.}, }
@PHDTHESIS{Relund04a, author = {L.R. Nielsen}, title = {Route Choice in Stochastic Time-Dependent Networks}, month = {December}, year = {2003}, school = {Department of {O}perations {R}esearch, {U}niversity of {A}arhus}, url = {http://www.imf.au.dk/publs?id=499}, 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.\par 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). \par 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. \par 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.}, }
@TECHREPORT{Relund02a, author = {L.R. Nielsen and K.A. Andersen and D. Pretolani}, title = {Finding the {$K$} Shortest Hyperpaths: algorithms and applications}, year = {2002}, institution = {Department of {O}perations {R}esearch, {U}niversity of {A}arhus}, url = {http://www.imf.au.dk/publs?id=263}, 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.\par 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.}, }
@TECHREPORT{Relund01a, author = {L.R. Nielsen and D. Pretolani}, title = {A Remark on the Definition of a {B}-Hyperpath}, year = {2001}, institution = {Department of {O}perations {R}esearch, {U}niversity of {A}arhus}, address = {University of Aarhus}, url = {www.research.relund.dk}, 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.}, }
@MASTERSTHESIS{Relund01b, author = {Lars Relund Nielsen}, title = {A Bicriterion and Parametric Analysis of the Shortest Hyperpath Problem}, year = {2001}, school = {Department of {O}perations {R}esearch, {U}niversity of {A}arhus}, url = {www.research.relund.dk}, 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.}, }
@TECHREPORT{Andersen00, author = {Kim A. Andersen and Lars R. Nielsen and Morten Riis and Anders J. V. Skriver}, title = {The Facets of the Set Packing Polytope: A Logical Interpretation}, year = {2000}, institution = {Department of {O}perations {R}esearch, {U}niversity of {A}arhus}, url = {http://www.imf.au.dk/publs?id=146}, 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.}, }
@ARTICLE{Pourmoayed19a, author = {R. Pourmoayed and L.R. Nielsen}, title = {An approximate dynamic programming approach for sequential pig marketing decisions at herd level}, year = {2019}, volume = {276}, number = {3}, journal = {European Journal of Operational Research}, pages = {1056--1070}, doi = {10.1016/j.ejor.2019.01.050}, 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 inter-dependencies, such as those created by fixed transportation costs and cross-level constraints. In this paper, we consider sequential marketing decisions at herd level. A high-dimensional infinite-horizon 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 cross-level constraints. Finally, a sensitivity analysis for some parameters in the model is conducted and the marketing policy found by ADP is compared with other well-known marketing polices, often applied at herd level.}, }
@TECHREPORT{Forget20a, author = {Forget, N. and Klamroth, K. and Gadegaard, S.L. and Przybylski, A. and Nielsen, L.R.}, title = {Branch-and-bound and objective branching with three objectives}, year = {2020}, institution = {Optimizaton Online}, url = {http://www.optimization-online.org/DB_HTML/2020/12/8158.html}, abstract = {The recent success of bi-objective Branch-and-Bound (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 tri-objective combinatorial optimization problems. Several difficulties arise in this case, as there is no longer a lexicographic order among nondominated outcome vectors in the multi-objective 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 tri-objective knapsack, assignment and facility location problems show a significant speed-up in the B&B framework.}, }
@ARTICLE{Andersen23, author = {K.A. Andersen and T.K. Boomsma and L.R. Nielsen}, title = {{MILP} Sensitivity Analysis for the Objective Function Coefficients}, year = {2023}, volume = {5}, number = {1}, journal = {{INFORMS} Journal on Optimization}, pages = {92--109}, doi = {10.1287/ijoo.2022.0078}, abstract = {This paper presents a new approach to sensitivity analysis of the objective function coefficients in mixed-integer linear programming (MILP). We determine the maximal region of the coefficients for which the current solution remains optimal. The region is maximal in the sense that, for variations beyond this region, the optimal solution changes. For variations in a single objective function coefficient, we show how to obtain the region by biobjective mixed-integer linear programming. In particular, we prove that it suffices to determine the two extreme nondominated points adjacent to the optimal solution of the MILP problem. Furthermore, we show how to extend the methodology to simultaneous changes to two or more coefficients by use of multiobjective analysis. Two examples illustrate the applicability of the approach.}, }
@ARTICLE{Forget22a, author = {Forget, N. and Gadegaard, S.L. and Nielsen, L.R.}, title = {Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs}, year = {2022}, volume = {302}, number = {3}, journal = {European Journal of Operational Research}, pages = {909--924}, doi = {10.1016/j.ejor.2022.01.047}, abstract = {In this paper we propose a generic branch-and-bound algorithm for solving multi-objective integer linear programming problems. In the recent literature, competitive frameworks has been proposed for bi-objective 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 warm-start a Bensons-like 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 non-binary integer variables are introduced in the models, and test our algorithm on problem that contains non-binary integer variables too.}, }
@ARTICLE{Forget22b, author = {Forget, N. and Gadegaard, S.L. and Klamroth, K. and Nielsen, L.R. and Przybylski, A.}, title = {Branch-and-bound and objective branching with three or more objectives}, year = {2022}, volume = {148}, journal = {Computers and Operations Research}, pages = {106012}, doi = {10.1016/j.cor.2022.106012}, abstract = {The recent success of bi-objective Branch-and-Bound (B&B) algorithms heavily relies on the efficient computation of upper and lower bound sets. These bound sets are used as a supplement to the classical dominance test 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 multi-objective integer optimization problems with three or more objective functions. Several difficulties arise in this case, as there is no longer a lexicographic order among non-dominated outcome vectors when there are three or more 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 sub-problems. Finally, results from extensive experimental studies on several classes of multi-objective optimization problems is reported.}, }
@TECHREPORT{Forget21, author = {Forget, N. and Gadegaard, S.L. and Nielsen, L.R.}, title = {Linear relaxation based branch-and-bound for multi-objective integer programming with warm-starting}, year = {2021}, institution = {Optimizaton Online}, url = {http://www.optimization-online.org/DB_HTML/2021/08/8531.html}, abstract = {In this paper we propose a generic branch-and-bound algorithm for solving multi-objective integer linear programming problems. % In the recent literature, competitive frameworks has been proposed for bi-objective 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 farther node to warm-start a Bensons-like 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 non-binary integer variables are introduced in the models, and test our algorithm on problem that contains non-binary integer variables too.}, }
