In this paper, we consider a class of quadratic maximization problems. One important instance in that class is the famous quadratic maximization formulation of the max-cut problem studied by Goemans and Williamson. Since the problem is NP-hard in general, following Goemans and Williamson, we apply the approximation method based on the semidefinite programming (SDP) relaxation. … Read more
We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lov\’asz and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures’ performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations … Read more
Taking a small graph, on which the randomized New-Best-In maximum clique heuristic fails to find the maximum clique, we construct on its basis a class of graphs exemplifying the inefficiency of SM greedy heuristics considered by Brockington and Culberson. We show that a 7(k+1)-vertex graph from this class is enough to provide a counterexample for … Read more
We survey how semidefinite programming can be used for finding good approximative solutions to hard combinatorial optimization problems. Citation Preliminary version appeared as Report PNA-R0210, CWI, Amsterdam, April 2002. To appear as Chapter in the Handbook on Discrete Optimization, K. Aardal, G. Nemhauser, R. Weismantel, eds., Elsevier Publishers. Article Download View Semidefinite programming and integer … Read more
The effectiveness of a layout design cannot be completely measured if the operational characteristics of the manufacturing system are ignored. There is, therefore, a need to develop integrated manufacturing system design models. In this paper, the integration of unit load and material handling considerations in facility layout design is presented. This integration is based on … Read more
The distance-based facility layout problem with unequal-area departments has been studied by many researchers for over 30 years. Still, current approaches require certain assumptions that limit the type of solutions obtained. In this paper, we consider manufacturing systems in which replicates of the same machine type may exist in the facility and propose an extended … Read more
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