We study some mathematical programming formulations for the origin-destination model in airline revenue management. In particular, we focus on the traditional probabilistic model proposed in the literature. The approach we study consists of solving a sequence of two-stage stochastic programs with simple recourse, which can be viewed as an approximation to a multi- stage stochastic … Read more
We analyze a version of the Mizuno-Todd-Ye predictor-corrector interior point algorithm for the P_*(\kappa)-matrix linear complementarity problem (LCP). We assume the existence of a strictly positive feasible solution. Our version of the Mizuno-Todd-Ye predictor-corrector algorithm is a generalization of Potra’s (2002) conclusions on the LCP with P_*(\kappa)-matrices. To derive a formulation of the complexity for … Read more
In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formulation by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation … Read more
We consider the vehicle routing problem where one can choose among vehicles with different costs and capacities to serve the trips. We develop six different formulations: the first four based on Miller-Tucker-Zemlin constraints and the last two based on flows. We compare the linear programming bounds of these formulations. We derive valid inequalities and lift … Read more
We consider the problem of installing a two-level telecommunication network. Terminal nodes communicate with each other through hubs. Hubs can be installed on terminal nodes and they are interconnected by a complete network. Each terminal is connected to a hub node by direct links. The aim is to minimize the cost of installing hubs and … Read more
Energy, a fundamental entity of modern life, is usually produced using fossil fuels as the primary raw material. A consequence of burning fossil fuels is the emission of environmentally harmful substances. Energy production systems generate steam and electricity that are served to different process customers to satisfy their energy requirement. The improvement of economical and … Read more
This extended annotated bibliography focuses on what has been published during the last ten years in the area of combinatorial optimization and scheduling theory concerning robustness and other similar techniques dealing with worst case optimization under uncertainty and non-accuracy of problem data CitationChristian-Albrechts University in Kiel, Institute of Production and Logistics, Working paper ArticleDownload View … Read more
The Generalized Assignment Problem (GAP) is a classic scheduling problem with many applications. We propose a branch-and-cut-and-price for that problem featuring a stabilization mechanism to accelerate column generation convergence. We also propose ellipsoidal cuts, a new way of transforming the exact algorithm into a powerful heuristic, in the same spirit of the cuts recently proposed … Read more
This paper presents a genetic algorithm for the Resource Constrained Multi-Project Scheduling Problem (RCMPSP). The chromosome representation of the problem is based on random keys. The schedules are constructed using a heuristic that builds parameterized active schedules based on priorities, delay times, and release dates defined by the genetic algorithm. The approach is tested on … Read more
Oracle Based Optimization (OBO) conveniently designates an approach to handle a class of convex optimization problems in which the information pertaining to the function to be minimized and/or to the feasible set takes the form of a linear outer approximation revealed by an oracle. We show, through three representative examples, how difficult problems can be … Read more