We use the notion of domination ratio introduced by Glover and Punnen in 1997 to present a new classification of combinatorial optimization (CO) problems: $\DOM$-easy and $\DOM$-hard problems. It follows from results proved already in the 1970’s that {\tt min TSP} (both symmetric and asymmetric versions) is $\DOM$-easy. We prove that several CO problems are … Read more
Cellular manufacturing emerged as a production strategy capable of solving the problems of complexity and long manufacturing lead times in batch production. The fundamental problem in cellular manufacturing is the formation of product families and machine cells. This paper presents a new approach for obtaining machine cells and product families. The approach combines a local … Read more
Given an undirected graph G with nonnegative edges costs and nonnegative vertex penalties, the prize collecting Steiner problem in graphs (PCSPG) seeks a tree of G with minimum weight. The weight of a tree is the sum of its edge costs plus the sum of the penalties of those vertices not spanned by the tree. … 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
We investigate the polyhedral structure of an integer program with a single functional constraint: the integer capacity-cover polyhedron. Such constraints arise in telecommunications planning and facility location applications, and feature the use of general integer (rather than just binary) variables. We derive a large class of facet-defining inequalities by using an augmenting technique that builds … 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
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
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
Arranging an n-vertex graph as the standard simplex in R^n, we identify graph cliques with simplex faces formed by clique vertices. An unstrict quadratic inequality holds for all points of the simplex; it turns to equality if and only if the point is on a face corresponding to a clique. This way this equality determines … Read more
We theorically study, on a distributed memory architecture, the parallelization of Hansen’s algorithm for the continuous global optimization with inequality constraints, using interval arithmetic. We propose a parallel algorithm based on a dynamic redistribution of the working list among the processors. On the other hand, we exploit the reduction technique, developped by Hansen, for computing … Read more