Publications with abstracts

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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

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

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.

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

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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

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

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

Abstract: In relevant application areas, such as transportation and telecommunications, there has recently been a growing focus on dynamic networks, where arc lengths are represented by time-dependent discrete random variables. In such networks, an optimal routing policy does not necessarily correspond to a path, but rather to an adaptive strategy. Finding an optimal strategy reduces to a shortest hyperpath problem that can be solved quite efficiently.
Bicriterion shortest path problems have been extensively studied for many years. Recently, extensions to dynamic networks have been investigated. However, no attempt has been made to study bicriterion strategies. This is the aim of this paper.
Here we model bicriterion strategy problems in terms of bicriterion shortest hyperpaths. For several problems arising in this context, optimal solutions can be found quite efficiently. Moreover, the general problem of listing efficient strategies can be successfully dealt with by means of heuristic methods. A computational experience is reported, where we consider several variants of the above problems. Finally, the relevant features of the bicriterion hyperpath model are discussed and compared to the classical bicriterion path approach.

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.

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.

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.

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.

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.).

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.).

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.