The research paper “Biobjective Branch-and-Cut Algorithms Based on LP Relaxation and Bound Sets” have been published in Informs Journal on Computing 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 […]
The research paper “An improved cut-and-solve algorithm for the single-source capacitated facility location problem” have been published in EURO Journal on Computational Optimization. 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.
The past weeks we have created Multi-Objective Optimization Repository (MOrepo) which is a response to the needs of researchers from the MCDM society to access multi-objective (MO) optimization instances. The repository contains instances, results, generators etc. for different MO problems and is continuously updated. The repository can be used as a test set for testing new algorithms, validating existing results and for reproducibility. All researchers within MO optimization are welcome to contribute. For more information see https://github.com/MCDMSociety/MOrepo.
The research paper “A bi-objective approach to discrete cost-bottleneck location problems” have been published in Annals of Operations Research. Abstract: This paper considers a family of bi-objective discrete facility location problems with a cost objective and a bottleneck objective. A special case is, for instance, a bi-objective version of the (vertex) p-centdian problem. We show that bi-objective facility location problems of this type can be solved efficiently by means of an epsilon-constraint method that solves at most (n-1)m minisum problems, where n is the number of customer points and m the number of potential facility sites. Additionally, we compare the approach to a lexicographic epsilon-constrained method that only returns efficient solutions and to a two-phase method relying on the perpendicular search method. We report extensive computational results obtained from several classes of facility location problems. The proposed algorithm compares very favorably to both the lexicographic epsilon-constrained method and to the two […]
Sune one of my PhD students has just finished his defense of his thesis titled “Discrete Location Problems – Theory, Algorithms, and Extensions to Multiple Objectives“. I would like to congratulate Sune with his PhD title and for a good presentation at the defense. I have included the thesis summary below. Summary This PhD–dissertation proposes a number of solution procedures for discrete facility location problems. In the literature of operations research, location problems are mathematical models describing optimization problems where one or more facilities need to be placed in relation to a given set of customers or demand points. An example is the location of hospitals which needs to be performed in such a way as to take into account capacity limits and the sizes of nearby towns and cities.
Reza one of my PhD students has just finished his defense of his thesis titled “Optimization Methods in a Stochastic Production Environment“. I would like to congratulate Reza with his PhD title and for a good presentation at the defense. I have included the thesis summary below. Summary This dissertation with an interdisciplinary approach applies techniques from Operations Research and Statistics in order to develop models that support decisions regarding feeding and marketing of growing/finishing pigs. Stochastic dynamic programming is used as the main optimization tool to model decisions, and state space models are used as the primary statistical technique to describe the stochastic nature of the system. Based on data streams from online farm sensors and market prices, the state space model transforms data into information which is embedded into the decision models using Bayesian updating.
The research paper “A hierarchical Markov decision process modeling feeding and marketing decisions of growing pigs” have been published in European Journal of Operational Research. 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 […]
The research paper “Markov decision processes to model livestock systems” have been published as a chapter in Handbook of Operations Research in Agriculture and the Agri-Food Industry. The paper gives a review of 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.
One of my PhD students, for who I am a co-supervisor, has just finished the defense of her thesis titled “Methods for Sensor Based Farrowing Prediction and Floor-heat Regulation: The Intelligent Farrowing Pen“. I would like to congratulate Aparna with her PhD title and for a good thesis and presentation at the defense. I have included the thesis summary below.
The research paper “Ranking paths in stochastic time-dependent networks” have been accepted for publication in European Journal of Operational Research. 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. 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 […]