New Filtering for the \mathit{cumulative} Constraint in the Context of Non-Overlapping Rectangles

DOI10.1007/978-3-540-68155-7_5MaRDI QIDQ5387618zbMATH OpenOpenAlexFDO

Authors Nicolas Beldiceanu, Mats Carlsson, Emmanuel Poder

Publication date 27 May 2008

Published in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-68155-7_5

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27)

Recommendations

• New filtering for the cumulative constraint in the context of non-overlapping rectangles
• A quadratic edge-finding filtering algorithm for cumulative resource constraints
• Time-table disjunctive reasoning for the cumulative constraint
• Linear-time filtering algorithms for the disjunctive constraint and a quadratic filtering algorithm for the cumulative not-first not-last
• A cumulative not-first/not-last filtering algorithm in \(O(n^2 \log(n))\)

Cites work

• A dynamic programming approach for consistency and propagation for knapsack constraints
• A new constraint programming approach for the orthogonal packing problem
• A new exact method for the two-dimensional orthogonal packing problem
• Edge finding for cumulative scheduling
• Exhaustive approaches to 2D rectangular perfect packings
• scientific article; zbMATH DE number 3782375 (Why is no real title available?)
• Introducing global constraints in CHIP
• Object-oriented interaction in resource constrained scheduling

Cited in

(8)

• Linear-time filtering algorithms for the disjunctive constraint and a quadratic filtering algorithm for the cumulative not-first not-last
• LP bounds in various constraint programming approaches for orthogonal packing
• Conservative scales in packing problems
• A quadratic edge-finding filtering algorithm for cumulative resource constraints
• scientific article; zbMATH DE number 2084705 (Why is no real title available?)
• scientific article; zbMATH DE number 2084718 (Why is no real title available?)
• New filtering for the cumulative constraint in the context of non-overlapping rectangles
• Consecutive ones matrices for multi-dimensional orthogonal packing problems

This page was built for publication: New Filtering for the $\mathit{cumulative}$ Constraint in the Context of Non-Overlapping Rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387618)