LP bounds in various constraint programming approaches for orthogonal packing

M. Mesyagutov, G. Scheithauer, G. Belov

Research output: Contribution to journalArticleResearchpeer-review

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

@article{f6179b74e6ca4e0da286a39ba4d58702,
title = "LP bounds in various constraint programming approaches for orthogonal packing",
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.",
keywords = "Column generation, Constraint programming, Linear programming",
author = "M. Mesyagutov and G. Scheithauer and G. Belov",
year = "2012",
month = "10",
doi = "10.1016/j.cor.2011.12.010",
language = "English",
volume = "39",
pages = "2425--2438",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier",
number = "10",

}

LP bounds in various constraint programming approaches for orthogonal packing. / Mesyagutov, M.; Scheithauer, G.; Belov, G.

In: Computers and Operations Research, Vol. 39, No. 10, 10.2012, p. 2425-2438.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - LP bounds in various constraint programming approaches for orthogonal packing

AU - Mesyagutov, M.

AU - Scheithauer, G.

AU - Belov, G.

PY - 2012/10

Y1 - 2012/10

N2 - 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.

AB - 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.

KW - Column generation

KW - Constraint programming

KW - Linear programming

UR - http://www.scopus.com/inward/record.url?scp=84856101677&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2011.12.010

DO - 10.1016/j.cor.2011.12.010

M3 - Article

VL - 39

SP - 2425

EP - 2438

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 10

ER -