# "Packing" Problem identification

 1 Hello I am trying to identify what could be the name of the following problem: Let $$I$$ be a set of items. Let $$D$$ be a set of defects. Let $$l_i$$ be the length of item $$i \in I$$. Let $$l_d$$ be the length of defect $$d \in D$$. Let $$s_d$$ be the start position of defect $$d \in D$$ Let $$c_{i,d}$$ be a Boolean indicating if an item is compatible with a given defect. Let L be the length of the material, that has defects, on which the items must be positioned. An item cannot be put on a position where it would intersect with an incompatible defect. The problem being to determine, if it exists a solution where no two items overlaps and where the compatibility with the defects is respected. If I am considering that all lengths are integer, a possible formulation could be the following: Let $$x_{i,j}$$ be a binary variable indicating if the left of item $$i$$ is positioned j units of measure away from the left of the start of the material. I'll consider that variable that would imply putting an item on an incompatible defects are already fixed to 0. Then the constraints are. $$\sum_{j \in [0,L]} x_{i,j} = 1, \forall i \in I$$ $$x_{i,j} + x_{i',j'} \leq 1, \forall i \in I, i' \in I, j \in [0,L], j' \in [j,j+l_i]$$ I have already tried to give a look to packing problems with defects, but could not really find something related to the 1 dimensional case, any pointers about what the name of this problem (or a similar problem) could be are welcome. asked 26 Jun '15, 03:00 Renaud 605●1●7 accept rate: 8%

 1 Sounds to me like a resource-constrained scheduling problem, where items are activities, length means duration, defects are already-scheduled activities, and incompatibility means the two activities share a resource and hence cannot be scheduled simultaneously. In particular, you can enforce the "no two items overlap" constraint by adding a common resource to all the activities in $$I$$. If you choose to solve this with an explicit formulation that uses your $$x$$ variables, you might consider replacing your conflict constraints with a clique constraint for each time period: $$\sum_{i \in I} \sum_{j=t-l_i}^t x_{i,j} \le 1, \forall t \in [0,L]$$ answered 26 Jun '15, 17:44 Rob Pratt 1.2k●2●6 accept rate: 28% Interesting I did not thought of it as a scheduling constraint :-) I'll definitely look in this area for interesting ideas. Thanks for the advice about having one clique constraint per time period, but I am not planning to solve the problem using an explicit formulation. (27 Jun '15, 14:07) Renaud
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: