Facility Planning and Design

Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes

  • Miguel F. Anjos
  • Anthony Vannelli
    • Categories Facility Planning and Design, Semi-definite Programming, VLSI layout Tags , , , ,

    This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) inter- actions between them. We demonstrate that the combination of a semidefinite programming relaxation with … Read more

    On the integrality of the uncapacitated facility location polytope

  • Mourad Baiou
  • Francisco Barahona
    • Categories Facility Planning and Design, Polyhedra Tags ,

    We study a system of linear inequalities associated with the uncapacitated facility location problem. We show that this system defines a polytope with integer extreme points if and only if the graph does not contain a certain type of odd cycles. We also derive odd cycle inequalities and give a separation algorithm. ArticleDownload View PDF

    Efficient Formulations for the Multi-Floor Facility Layout Problem with Elevators

  • Marc Goetschalckx
  • Takashi Irohara
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Production and Logistics Tags , , , ,

    The block layout problem for a multi-floor facility is an important sub class of the facility layout problem with practical applications when the price of land is high or when a compact building allows for more efficient environmental control. Several alternative formulations for the block layout problem of a multi-floor facility are presented, where the … Read more

    Theory of Semidefinite Programming for Sensor Network Localization

  • Anthony Man-Cho So
  • Yinyu Ye
    • Categories Applications - Science and Engineering, Facility Planning and Design, Semi-definite Programming Tags ,

    We analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior–point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we … Read more

    Alternative Formulation for the p-median Problem

  • Sourour Elloumi
    • Categories Combinatorial Optimization, Facility Planning and Design Tags , , ,

    Given a set of clients and a set of potential sites for facilities, several location problems consist of opening a set of sites and assigning each client to the closest open facility to it. It can be viewed as a variation of the uncapacitated facility location problem. We propose a new formulation of this problem … Read more

    A Semidefinite Optimization Approach for the Single-Row Layout Problem with Unequal Dimensions

  • Miguel F. Anjos
  • Andrew Kennings
  • Anthony Vannelli
    • Categories Facility Planning and Design, Semi-definite Programming, VLSI layout Tags , , , ,

    The facility layout problem is concerned with the arrangement of a given number of rectangular facilities so as to minimize the total cost associated with the (known or projected) interactions between them. We consider the one-dimensional space allocation problem (ODSAP), also known as the single-row facility layout problem, which consists in finding an optimal linear … Read more

    Scheduling Workover Rigs for Onshore Oil Production

  • Daniel Aloise
  • Dario J. Aloise
  • Celso C. Ribeiro
  • Caroline Rocha
  • Luiz Moura
  • José Ribeiro Filho
    • Categories Facility Planning and Design, Meta Heuristics, Production and Logistics Tags , , , ,

    Many oil wells in Brazilian onshore fields rely on artificial lift methods. Maintenance services such as cleaning, reinstatement, stimulation and others are essential to these wells. These services are performed by workover rigs, which are avaliable on a limited number with respect to the number of wells demanding service. The decision of which workover rig … Read more

    A hybrid multistart heuristic for the uncapacitated facility location problem

  • Mauricio G.C. Resende
  • Renato F. Werneck
    • Categories Combinatorial Optimization, Facility Planning and Design, Meta Heuristics Tags , ,

    We present a multistart heuristic for the uncapacitated facility location problem, based on a very successful method we originally developed for the P-median problem. We show extensive empirical evidence to the effectiveness of our algorithm in practice. For most benchmarks instances in the literature, we obtain solutions that are either optimal or a fraction of … Read more

    A Fast Swap-based Local Search Procedure for Location Problems

  • Mauricio G.C. Resende
  • Renato F. Werneck
    • Categories Combinatorial Optimization, Facility Planning and Design Tags , ,

    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 it does not have a better worst-case complexity, it can be significantly faster in … Read more

    Location and design of a competitive facility for profit maximisation

  • Emilio Carrizosa
  • Frank Plastria
    • Categories Facility Planning and Design, Nonlinear Optimization Tags , , , , ,

    A single facility has to be located in competition with fixed existing facilities of similar type. Demand is supposed to be concentrated at a finite number of points, and consumers patronise the facility to which they are attracted most. Attraction is expressed by some function of the quality of the facility and its distance to … Read more