layout

Beating the SDP bound for the floor layout problem: A simple combinatorial idea

  • Santanu S. Dey
  • Joey Huchette
  • Juan Pablo Vielma
    • Categories Facility Planning and Design, Integer Programming Tags ,

    For many Mixed-Integer Programming (MIP) problems, high-quality dual bounds can obtained either through advanced formulation techniques coupled with a state-of-the-art MIP solver, or through Semidefinite Programming (SDP) relaxation hierarchies. In this paper, we introduce an alternative bounding approach that exploits the “combinatorial implosion” effect by solving portions of the original problem and aggregating this information … Read more

    Strong mixed-integer formulations for the floor layout problem

  • Santanu S. Dey
  • Joey Huchette
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design Tags ,

    The floor layout problem (FLP) tasks a designer with positioning a collection of rectangular boxes on a fixed floor in such a way that minimizes total communication costs between the components. While several mixed integer programming (MIP) formulations for this problem have been developed, it remains extremely challenging from a computational perspective. This work takes … Read more

    Test problems of circles in circle packing with behavior constraint and known the optimal solutions

  • Che Chao
  • Teng Hong-fei
  • Wang Yi-Shou
  • Chen Yu
    • Categories Combinatorial Optimization Tags , , , ,

    Test problems are generally used to effectively evaluate the algorithms for packing problem. Based on the engineering background of the layout optimization for a retrievable satellite module, this paper describes the test problems for circles packing problem with known optimization solution first. There are N(≦217) circular objects, different in size, packed in a circular container … Read more