LP bounds in various constraint programming approaches for orthogonal packing

M. Mesyagutov, G. Scheithauer, G. Belov

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)

Abstract

We consider the 2D orthogonal feasibility problem (OPP-2) and the 2D strip packing problem (SPP-2). Given a set of rectangular items, the OPP-2 is to decide whether all items can be orthogonally packed into the given rectangular container; the SPP-2 is to find a packing of all items occupying the minimal height of the given semi-infinite strip. Both OPP-2 and SPP-2 are considered without items rotation. We investigate the known Constraint Programming (CP) approaches for OPP-2, in particular the dichotomy and disjunctive branching strategies and adapt 1D relaxation bounds based on linear programming (LP) into the constraint propagation process of the CP. Using the dichotomic search procedure the developed methods for OPP-2 are transformed for the case of SPP-2. Numerical results demonstrate the efficiency of the proposed strategies and of the combination of CP and LP-based pruning rules.

Original languageEnglish
Pages (from-to)2425-2438
Number of pages14
JournalComputers and Operations Research
Volume39
Issue number10
DOIs
Publication statusPublished - Oct 2012
Externally publishedYes

Keywords

  • Column generation
  • Constraint programming
  • Linear programming

Cite this