LP bounds in various constraint programming approaches for orthogonal packing

M. Mesyagutov, G. Scheithauer, G. Belov

Research output: Contribution to journalArticleResearchpeer-review

12 Citations (Scopus)


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
Issue number10
Publication statusPublished - Oct 2012
Externally publishedYes


  • Column generation
  • Constraint programming
  • Linear programming

Cite this