On more-dimensional packing III: Exact Algorithms

Fekete, Sandor P. and Schepers, Jörg (2000) On more-dimensional packing III: Exact Algorithms.
Technical Report , 29 p.

Abstract

More-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Combining the use of our data structure for characterizing feasible packings with our new classes of lower bounds, and other heuristics, we develop a two-level tree search algorithm for solving more-dimensional packing problems to optimality. Computational results are reported, including optimal solutions for all two-dimensional test problems from recent literature.


Actions:
Download: [img] Postscript - Updated Version
Download (368kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: 56 (Google Scholar) |
Uncontrolled Keywords: 3-dimensional geometry branch-and-bound exact algorithms geometric optimization interval graphs packing
Subjects:
  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C30 Nonlinear programming

  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R99 None of the above, but in this section

    		•
    Divisions: Mathematical Institute
    Related URLs:
      Deposit Information:
      ZAIK Number: zpr97-290
      Depositing User: Archive Admin
      Date Deposited: 02 Apr 2001 00:00
      Last Modified: 19 Dec 2011 09:46
      URI: http://e-archive.informatik.uni-koeln.de/id/eprint/290