<p>I think that the paper by Klaus Jansen and Roberto Solis-Oba &quot;<a href="https://doi.org/10.1007/978-3-642-13036-6_33" rel="nofollow noreferrer">An OPT + 1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths</a>&quot; has a partial answer to your question. They consider a special case of your problem known as <strong>Cutting Stock</strong> problem when the number of diﬀerent object types is constant and defined as follows:</p>
<blockquote>
<p>In the <em>cutting stock problem</em> we are given a set <span class="math-container">$T = \{T_1,T_2,\dots,T_d\}$</span> of object types, where objects of type <span class="math-container">$T_i$</span> have positive integer length <span class="math-container">$p_i$</span>. Given an inﬁnite set of bins, each of integer capacity <span class="math-container">$\beta$</span>, the problem is to pack a set <span class="math-container">$\mathcal{O}$</span> of <span class="math-container">$n$</span> objects into the minimum possible number of bins in such a way that the capacity of the bins is not exceeded; in set <span class="math-container">$\mathcal{O}$</span> there are <span class="math-container">$n_i$</span> objects of type <span class="math-container">$T_i$</span>, for all <span class="math-container">$i =1,\dots,d$</span>.</p>
</blockquote>
<p>The authors claim that</p>
<blockquote>
<p>it is not known whether the cutting stock problem can be solved in polynomial time for every ﬁxed value <span class="math-container">$d$</span>.</p>
</blockquote>
<p>And they propose <span class="math-container">$OPT+1$</span> approximation polynomial-time algorithm when <span class="math-container">$d$</span> is fixed.</p>
<p>Since it's not proved that this special case is in <span class="math-container">$P$</span>, this is the evidence that your problem is <span class="math-container">$NP$</span>-hard.</p>
<p><strong>Addendum:</strong> it's <a href="https://web.archive.org/web/20130502030251/http://www.econ.kuleuven.ac.be/public/NDBAE03/papers/mor2001paper.pdf" rel="nofollow noreferrer">known</a> that the case with two object types (<span class="math-container">$d=2$</span>) is polynomially solvable, but for <span class="math-container">$d=3$</span> there is known only <span class="math-container">$OPT+1$</span>-approximation.</p>

CC BY-SA 2.5
2010-12-17T08:44:45.790Z
Thank you for your answer. It was not proved to be in $P$, but neither NP-hard right? Anyway, as you said it gives me a partial answer and makes me think that for OPP-2 it was most probably not studied.
Petru
CC BY-SA 2.5
2010-12-17T12:56:58.397Z
I think you're probably right that your problem was not studied. As you said "It was not proved to be in P, but neither NP-hard" and I understand it this way too.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-17T16:23:37.690Z
Maybe this problem can be added into the [list](http://cstheory.stackexchange.com/q/79/1800) of "not known to be in P or being NPC" problems.
Hsien-Chih Chang 張顯之
CC BY-SA 4.0
2010-12-16T16:19:32.283Z
2023-02-16T10:56:29.130Z
2023-02-16T10:56:29.130Z
Oleksandr Bondarenko
<p>Let $V$ be a set of $D$-dimensional rectangular shapes. For $d \in \{1,...,D\}$ and $v \in V$, $w_d(v) \in \mathbb{Q}^{+}$ describes the length of $v$ in the dimension $d$. The same notation is used for the container $C$.
The $D$-dimensional orthogonal packing problem (OPP-$D$) is to decide if $V$ fits into the container $C$ without overlapping. Formally speaking, the problem is to find out whether $\forall d \in \{1,...,D\}$ there exists a function $f_d:V\rightarrow \mathbb{Q}^{+}$, such that $\forall v \in V, f_d(v)+w_d(v) \leq w_d(C)$ and $\forall v_1,v_2 \in V$, $(v_1 \neq v_2)$, $[f_d(v_1),f_d(v_1)+w_d(v_1)) \cap [f_d(v_2),f_d(v_2)+w_d(v_2)) = \emptyset$.</p>

<p>The problem is NP-complete (see Fekete SP, Schepers J. "On higher-dimensional packing I: Modeling". Technical Report 97–288, University at zu Köln, 1997). The problem is NP-complete even for $D=2$. I am wondering, whether the orthogonal packing problem for a bounded number of types (i.e. sizes in each dimension) of items is still NP-complete or not. Till now I found a result in some paper about NP-completeness of packing squares into a square (see JOSEPH Y-T. LEUNG, TOMMY W . TAM, AND C. S. WONG, "Packing squares into a square", Journal of Parallel and Distributed Computing, Volume 10 Issue 3, Nov. 1990) which is already a restriction but I still don't know what happens when the number of types of items is bounded.</p>

<p>Thank you for your answer,</p>

CC BY-SA 2.5
2010-12-16T15:22:07.443Z
can you state the original problem ?
Suresh Venkat
CC BY-SA 2.5
2010-12-16T15:23:15.743Z
What is orthogonal packing problem?
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-16T15:46:34.250Z
(1) I am not an expert on the subject, but isn’t that problem discription too sketchy to analyze its complexity?  (2) Please try to use other people’s comments to improve your question by editing it, rather than adding more comments.  Most people do not want to follow the discussions in comments just to understand the question.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-16T15:48:29.347Z
Maybe try to define rigorously what the problem is by editing your question (click the edit button above), and add some references you've found. That will help the community understand what you have known, and what do you want to know. Help us to help you!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-16T19:27:47.623Z
(My comment and Hsien-Chih’s comment referred to the asker’s earlier comment sketching what the orthogonal packing problem is, which has been deleted later.)
Tsuyoshi Ito
<cc.complexity-theory><reference-request><np-hardness><packing>
NP-Hardness of a special case of orthogonal packing problem
Petru
# NP-Hardness of a special case of orthogonal packing problem

(Asked by: username_0 on 2010-12-16)

Let $V$ be a set of $D$-dimensional rectangular shapes. For $d \in \{1,...,D\}$ and $v \in V$, $w\_d(v) \in \mathbb{Q}^{+}$ describes the length of $v$ in the dimension $d$. The same notation is used for the container $C$.
The $D$-dimensional orthogonal packing problem (OPP-$D$) is to decide if $V$ fits into the container $C$ without overlapping. Formally speaking, the problem is to find out whether $\forall d \in \{1,...,D\}$ there exists a function $f\_d:V\rightarrow \mathbb{Q}^{+}$, such that $\forall v \in V, f\_d(v)+w\_d(v) \leq w\_d(C)$ and $\forall v\_1,v\_2 \in V$, $(v\_1 \neq v\_2)$, $[f\_d(v\_1),f\_d(v\_1)+w\_d(v\_1)) \cap [f\_d(v\_2),f\_d(v\_2)+w\_d(v\_2)) = \emptyset$.

The problem is NP-complete (see Fekete SP, Schepers J. "On higher-dimensional packing I: Modeling". Technical Report 97–288, University at zu Köln, 1997). The problem is NP-complete even for $D=2$. I am wondering, whether the orthogonal packing problem for a bounded number of types (i.e. sizes in each dimension) of items is still NP-complete or not. Till now I found a result in some paper about NP-completeness of packing squares into a square (see JOSEPH Y-T. LEUNG, TOMMY W . TAM, AND C. S. WONG, "Packing squares into a square", Journal of Parallel and Distributed Computing, Volume 10 Issue 3, Nov. 1990) which is already a restriction but I still don't know what happens when the number of types of items is bounded.

Thank you for your answer,

**Tags:** cc.complexity-theory, reference-request, np-hardness, packing

> **Comments:**
> **username_1**: can you state the original problem ?  
> **username_2**: What is orthogonal packing problem?  
> **username_2**: (1) I am not an expert on the subject, but isn’t that problem discription too sketchy to analyze its complexity?  (2) Please try to use other people’s comments to improve your question by editing it, rather than adding more comments.  Most people do not want to follow the discussions in comments just to understand the question.  
> **username_3**: Maybe try to define rigorously what the problem is by editing your question (click the edit button above), and add some references you've found. That will help the community understand what you have known, and what do you want to know. Help us to help you!  
> **username_2**: (My comment and Hsien-Chih’s comment referred to the asker’s earlier comment sketching what the orthogonal packing problem is, which has been deleted later.)  

---

## 1 answers

### Answer by username_4 on 2010-12-16. Score: 7 | Accepted answer

I think that the paper by Klaus Jansen and Roberto Solis-Oba "[An OPT + 1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths](https://doi.org/10.1007/978-3-642-13036-6_33)" has a partial answer to your question. They consider a special case of your problem known as **Cutting Stock** problem when the number of diﬀerent object types is constant and defined as follows:

> In the *cutting stock problem* we are given a set $T = \{T\_1,T\_2,\dots,T\_d\}$ of object types, where objects of type $T\_i$ have positive integer length $p\_i$. Given an inﬁnite set of bins, each of integer capacity $\beta$, the problem is to pack a set $\mathcal{O}$ of $n$ objects into the minimum possible number of bins in such a way that the capacity of the bins is not exceeded; in set $\mathcal{O}$ there are $n\_i$ objects of type $T\_i$, for all $i =1,\dots,d$.

The authors claim that

> it is not known whether the cutting stock problem can be solved in polynomial time for every ﬁxed value $d$.

And they propose $OPT+1$ approximation polynomial-time algorithm when $d$ is fixed.

Since it's not proved that this special case is in $P$, this is the evidence that your problem is $NP$-hard.

**Addendum:** it's [known](https://web.archive.org/web/20130502030251/http://www.econ.kuleuven.ac.be/public/NDBAE03/papers/mor2001paper.pdf) that the case with two object types ($d=2$) is polynomially solvable, but for $d=3$ there is known only $OPT+1$-approximation.

> **Comments:**
> **username_0**: Thank you for your answer. It was not proved to be in $P$, but neither NP-hard right? Anyway, as you said it gives me a partial answer and makes me think that for OPP-2 it was most probably not studied.  
> **username_4**: I think you're probably right that your problem was not studied. As you said "It was not proved to be in P, but neither NP-hard" and I understand it this way too.  
> **username_3**: Maybe this problem can be added into the [list](http://cstheory.stackexchange.com/q/79/1800) of "not known to be in P or being NPC" problems.  

---

