這個裝箱變式是否有名稱？

Question

我聽起來像一個典型的裝箱問題：x不同尺寸的產品需要包裝到不同容量的容器中，最大限度地減少所用容器的數量，並儘量減少浪費的空間。

我可以簡化這個問題，因爲產品尺寸和容器的容量可以減少到標準的一維單位。即這個產品是1個單位大，而那個是3個單位，這個盒子可容納6個單位，即12個。想象雞蛋和紙箱，或啤酒的情況。

但還有一個額外的約束：每個容器都有一個特定的屬性（我們將其稱爲顏色），並且每個產品都有一組與之兼容的顏色。顏色與產品/容器尺寸無關;一個產品可能與整個調色板顏色兼容，另一個產品可能僅與容器兼容。

這個問題變式在文獻中已經描述過嗎？如果是這樣，它的名字是什麼？

Answer 1

我認爲這個變種沒有特別的名字。儘管着色約束首先給人的印象是圖形着色相關，但事實並非如此。這只是對變量值的限制。

在一個典型的求解器實現中，每個產品（= item）都會有一個變量，它被分配到哪個容器。顏色限制只會減少特定變量的值範圍。因此，而不是指定所有變量使用相同的值範圍，使其具體變量。 （例如，在OptaPlanner中，這是提供的值範圍by the solution generally or by the entity specifically之間的差值。）所以着色約束甚至不需要是約束：它可以是大多數求解器中的模型的一部分。

任何可以處理垃圾箱包裝的求解器應該能夠處理這個變體。你的問題實際上是放鬆了Roadef 2012 Machine Reassignment problem，這是關於分配進程到計算機。簡單地刪除所有約束，除了1個資源使用約束和排除某些進程的約束到某些機器。該用例在許多求解器中實現。 （雖然在實踐中，從一個基本的裝箱示例開始，例如Cloud Balancing可能會更容易。）

Answer 2

最有可能的二維裝箱或經典的揹包問題。