It is with the aim of solving scheduling problems with irregular cost functions that this paper focuses on the continuous assignment problem. It consists in partitioning a d dimensional region into subregions of prescribed volumes so that the total cost is minimized. The dual problem of the continuous assignment problem is an unconstrained maximisation of … Read more
The hierarchical network problem is the problem of finding the least cost network, with nodes divided into groups, edges connecting nodes in each groups and groups ordered in a hierarchy. The idea of hierarchical networks comes from telecommunication networks where hierarchies exist. Hierarchical networks are described and a mathematical model is proposed for a two … Read more
This paper presents a hybrid genetic algorithm for the Job Shop Scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a … Read more
We present a new implementation of a widely used swap-based local search procedure for the P-median problem, proposed in 1968 by Teitz and Bart. Our method produces the same output as the best alternatives described in the literature and, even though its worst-case complexity is similar, it can be significantly faster in practice: speedups of … Read more
Given N customers and a set F of M potential facilities, the P-median problem consists in finding a subset of F with P facilities such that the cost of serving all customers is minimized. This is a well-known NP-complete problem with important applications in location science and classification (clustering). We present here a GRASP (Greedy … Read more
When combinatorial bidding is permitted in Spectrum Auctions, such as the upcoming FCC auction #31, the resulting winner-determination problem can be computationally challenging. We present a branch-and-price algorithm based on a set-packing formulation originally proposed by Dietrich and Forrest (2002). This formulation has a variable for every possible combination of winning bids for each bidder. … Read more
We present a practical algorithm for computing the minimum volume n-dimensional ellipsoid that must contain m given points a_1, …, a_m \in R^n. This convex constrained problem arises in a variety of applied computational settings, particularly in data mining and robust statistics. Its structure makes it particularly amenable to solution by interior-point methods, and it … Read more
We consider a Markov decision process model of a network revenue management problem. Working within this formal framework, we study policies that combine aspects of mathematical programming approaches and pure Markov decision process methods. The policies employ heuristics early in the booking horizon, and switch to a more-detailed decision rule closer to the time of … Read more
We study the problem of designing at minimum cost a two-connected network such that each edge belongs to a cycle using at most K edges. This problem is a particular case of the two-connected networks with bounded meshes problem studied by Fortz, Labbé and Maffioli. In this paper, we compute a lower bound on the … Read more
The purpose of the traffic assignment problem is to obtain a traffic flow pattern given a set of origin-destination travel demands and flow dependent link performance functions of a road network. In the general case, the traffic assignment problem can be formulated as a variational inequality, and several algorithms have been devised for its efficient … Read more