Adding an item to a container, but first a lot of checks

Question

First time on this exchange, so giving this a title was already a challenge. So let's start at the beginning. This kind professor Güneş Erdoğan has published an CLP (Container Loading Problem) solver. His solution is made in a spreadsheet so it is VBA for Applications.

I have manually converted his code to a PHP script. I have everything working and running. But he has stated himself that there is room for improvement.

His algorithm has a while loop where it keeps making solutions based on random sorting. If the new solution is better than the current, the current gets replaced. Since the algorithm has a given time as input, for example 30, the code will keep doing this for 30 seconds and then return the best solution.

So I took the challenge to improve the code and try to get more iterations within the 30 seconds. Using a profiling tool it shows me that the method called addItemToContainer takes up most of the time. I've already spend quite some time on this method to try and improve it but I honestly can't find anything.

Then I found this exchange and I'm curious if anyone here can help me any further.

addItemToContainer code:

public function addItemToContainer(Solution $solution, int $containerIndex, int $itemTypeIndex, int $addType): bool
{
    $currentContainer = $solution->containers[$containerIndex];
    $currentItemType = $this->itemTypeList[$itemTypeIndex];
    $minX = $currentContainer->width + 1;
    $minY = $currentContainer->height + 1;
    $minZ = $currentContainer->length + 1;

    $candidatePosition = -1;

    $additionPointsCount = \count($currentContainer->addition_points);

    // Checks if the item is able to fit into the current container based on volume
    if (($currentContainer->volume_packed + $currentItemType->volume) > $currentContainer->volume_capacity) {
        goto addItemToContainerFinish;
    }

    // Checks if the item is able to fit into the current container based on weight
    if (($currentContainer->weight_packed + $currentItemType->weight) > $currentContainer->weight_capacity) {
        goto addItemToContainerFinish;
    }

    // Checks each rotation, based on the rotation order of the solution
    for ($i = 0; $i < 6; $i++) {
        $rotationIndex = $i;
        if ($candidatePosition !== -1) {
            goto addItemToContainerFinish;
        }

        $currentRotation = $solution->rotation_order[$itemTypeIndex][$rotationIndex];

        // Forbidden rotations
        if ((($currentRotation === 3) || ($currentRotation === 4)) && ($currentItemType->xy_rotatable === false)) {
            continue;
        }

        if ((($currentRotation === 5) || ($currentRotation === 6)) && ($currentItemType->yz_rotatable === false)) {
            continue;
        }

        // Symmetry breaking
        if (($currentRotation === 2) && (\abs($currentItemType->width - $currentItemType->length) < $this->epsilon)) {
            continue;
        }

        if (($currentRotation === 4) && (\abs($currentItemType->width - $currentItemType->height) < $this->epsilon)) {
            continue;
        }

        if (($currentRotation === 6) && (\abs($currentItemType->height - $currentItemType->length) < $this->epsilon)) {
            continue;
        }

        // Loops through each addition point to find the next gap to put a new item
        for ($j = 0; $j < $currentContainer->addition_point_count; $j++) {
            if ($additionPointsCount - 1 >= $j) {
                $additionPoint = $currentContainer->addition_points[$j];
                $originX = $additionPoint->origin_x;
                $originY = $additionPoint->origin_y;
                $originZ = $additionPoint->origin_z;
            } else {
                $originX = 0;
                $originY = 0;
                $originZ = 0;
            }

            // set opposite positions based on the rotation which is calculated above
            switch ($currentRotation) {
                case 1:
                    $oppositeX = $originX + $currentItemType->width;
                    $oppositeY = $originY + $currentItemType->height;
                    $oppositeZ = $originZ + $currentItemType->length;
                    break;
                case 2:
                    $oppositeX = $originX + $currentItemType->length;
                    $oppositeY = $originY + $currentItemType->height;
                    $oppositeZ = $originZ + $currentItemType->width;
                    break;
                case 3:
                    $oppositeX = $originX + $currentItemType->width;
                    $oppositeY = $originY + $currentItemType->length;
                    $oppositeZ = $originZ + $currentItemType->height;
                    break;
                case 4:
                    $oppositeX = $originX + $currentItemType->height;
                    $oppositeY = $originY + $currentItemType->length;
                    $oppositeZ = $originZ + $currentItemType->width;
                    break;
                case 5:
                    $oppositeX = $originX + $currentItemType->height;
                    $oppositeY = $originY + $currentItemType->width;
                    $oppositeZ = $originZ + $currentItemType->length;
                    break;
                case 6:
                    $oppositeX = $originX + $currentItemType->length;
                    $oppositeY = $originY + $currentItemType->width;
                    $oppositeZ = $originZ + $currentItemType->height;
                    break;
                default:
                    $oppositeX = 0;
                    $oppositeY = 0;
                    $oppositeZ = 0;
                    break;
            }

            // Check the feasibility of all four corners, w.r.t. to the other items
            if (($oppositeX > $currentContainer->width + $this->epsilon) || ($oppositeY > $currentContainer->height + $this->epsilon) || ($oppositeZ > $currentContainer->length + $this->epsilon)) {
                continue;
            }

            // Check if there is conflict with other items within the container
            foreach ($currentContainer->items as $item) {
                if (
                    ($oppositeX < $item->origin_x + $this->epsilon) ||
                    ($item->opposite_x < $originX + $this->epsilon) ||
                    ($oppositeY < $item->origin_y + $this->epsilon) ||
                    ($item->opposite_y < $originY + $this->epsilon) ||
                    ($oppositeZ < $item->origin_z + $this->epsilon) ||
                    ($item->opposite_z < $originZ + $this->epsilon)
                ) {
                    // No conflict
                } else {
                    // Conflict
                    continue 2 ;
                }
            }

            // Support
            if ($originY < $this->epsilon) {
                $support = true;
            } else {
                $areaSupported = 0;
                $support = false;
                $containerItemsCount = \count($currentContainer->items);
                for ($k = $containerItemsCount - 1; $k >= 0; $k--) {
                    $item = $currentContainer->items[$k];
                    if (\abs($originY - $item->opposite_y) < $this->epsilon) {
                        // Check for intersection
                        $intersectionRight = $oppositeX;
                        if ($intersectionRight > $item->opposite_x) {
                            $intersectionRight = $item->opposite_x;
                        }

                        $intersectionLeft = $originX;
                        if ($intersectionLeft < $item->origin_x) {
                            $intersectionLeft = $item->origin_x;
                        }

                        $intersectionTop = $oppositeZ;
                        if ($intersectionTop > $item->opposite_z) {
                            $intersectionTop = $item->opposite_z;
                        }

                        $intersectionBottom = $originZ;
                        if ($intersectionBottom < $item->origin_z) {
                            $intersectionBottom = $item->origin_z;
                        }

                        if (($intersectionRight > $intersectionLeft) && ($intersectionTop > $intersectionBottom)) {
                            $areaSupported += (($intersectionRight - $intersectionLeft) * ($intersectionTop - $intersectionBottom));
                            if ($areaSupported > (($oppositeX - $originX) * ($oppositeZ - $originZ)) - $this->epsilon) {
                                $support = true;
                                break;
                            }
                        }
                    }
                }
            }

            if (!$support) {
                continue;
            }

            // No conflicts at this point
            if (
                ($originZ < $minZ) ||
                (($originZ <= $minZ + $this->epsilon) && ($originY < $minY)) ||
                (($originZ <= $minZ + $this->epsilon) && ($originY <= $minY + $this->epsilon) && ($originX < $minX))
            ) {
                $minX = $originX;
                $minY = $originY;
                $minZ = $originZ;
                $candidatePosition = $j;
                $candidateRotation = $currentRotation;
            }
        }
    }

    // Portion of the function where the item gets added to the container
    addItemToContainerFinish :

    // If the candidate position is equal to -1 return
    if ($candidatePosition === -1) {
        return false;
    } else {
        $newItem = new Item();
        $newItem->item_type = $itemTypeIndex;
        if ($additionPointsCount - 1 >= $candidatePosition) {
            $newItem->origin_x = $currentContainer->addition_points[$candidatePosition]->origin_x;
            $newItem->origin_y = $currentContainer->addition_points[$candidatePosition]->origin_y;
            $newItem->origin_z = $currentContainer->addition_points[$candidatePosition]->origin_z;
        } else {
            $newItem->origin_x = 0;
            $newItem->origin_y = 0;
            $newItem->origin_z = 0;
        }
        $newItem->rotation = $candidateRotation;
        $newItem->mandatory = $currentItemType->mandatory;

        // Based on the resulted rotation set the opposite position
        switch ($candidateRotation) {
            case 1:
                $newItem->opposite_x = $newItem->origin_x + $currentItemType->width;
                $newItem->opposite_y = $newItem->origin_y + $currentItemType->height;
                $newItem->opposite_z = $newItem->origin_z + $currentItemType->length;
                break;
            case 2:
                $newItem->opposite_x = $newItem->origin_x + $currentItemType->length;
                $newItem->opposite_y = $newItem->origin_y + $currentItemType->height;
                $newItem->opposite_z = $newItem->origin_z + $currentItemType->width;
                break;
            case 3:
                $newItem->opposite_x = $newItem->origin_x + $currentItemType->width;
                $newItem->opposite_y = $newItem->origin_y + $currentItemType->length;
                $newItem->opposite_z = $newItem->origin_z + $currentItemType->height;
                break;
            case 4:
                $newItem->opposite_x = $newItem->origin_x + $currentItemType->height;
                $newItem->opposite_y = $newItem->origin_y + $currentItemType->length;
                $newItem->opposite_z = $newItem->origin_z + $currentItemType->width;
                break;
            case 5:
                $newItem->opposite_x = $newItem->origin_x + $currentItemType->height;
                $newItem->opposite_y = $newItem->origin_y + $currentItemType->width;
                $newItem->opposite_z = $newItem->origin_z + $currentItemType->length;
                break;
            case 6:
                $newItem->opposite_x = $newItem->origin_x + $currentItemType->length;
                $newItem->opposite_y = $newItem->origin_y + $currentItemType->width;
                $newItem->opposite_z = $newItem->origin_z + $currentItemType->height;
                break;
        }

        \array_push($solution->containers[$containerIndex]->items, $newItem);

        // Update the volume and weight of the container
        $currentContainer->volume_packed += $currentItemType->volume;
        $currentContainer->weight_packed += $currentItemType->weight;

        if ($addType === 2) {
            $currentContainer->repack_item_count[$itemTypeIndex] = $currentContainer->repack_item_count[$itemTypeIndex] - 1;
        }

        // Update the addition points
        for ($i = $candidatePosition; $i < $currentContainer->addition_point_count - 1; $i++) {
            $currentContainer->addition_points[$i] = clone($currentContainer->addition_points[$i + 1]);
        }

        $currentContainer->addition_point_count = $currentContainer->addition_point_count - 1;

        $itemsCount = \count($currentContainer->items);
        $lastItem = $currentContainer->items[$itemsCount - 1];
        // Add a new addition point to the container based on the last item
        if (($lastItem->opposite_x < $currentContainer->width - $this->epsilon) &&
            ($lastItem->origin_y < $currentContainer->height - $this->epsilon) &&
            ($lastItem->origin_z < $currentContainer->length - $this->epsilon)) {
            $currentContainer->addition_point_count = $currentContainer->addition_point_count + 1;
            $additionPoint = new ItemLocation();
            $additionPoint->origin_x = $lastItem->opposite_x;
            $additionPoint->origin_y = $lastItem->origin_y;
            $additionPoint->origin_z = $lastItem->origin_z;
            if (\count($currentContainer->addition_points) < $currentContainer->addition_point_count) {
                \array_push($currentContainer->addition_points, $additionPoint);
            } else {
                $currentContainer->addition_points[$currentContainer->addition_point_count - 1] = $additionPoint;
            }
        }

        // Add a new addition point to the container based on the last item
        if (($lastItem->origin_x < $currentContainer->width - $this->epsilon) &&
            ($lastItem->opposite_y < $currentContainer->height - $this->epsilon) &&
            ($lastItem->origin_z < $currentContainer->length - $this->epsilon)) {
            $currentContainer->addition_point_count = $currentContainer->addition_point_count + 1;
            $additionPoint = new ItemLocation();
            $additionPoint->origin_x = $lastItem->origin_x;
            $additionPoint->origin_y = $lastItem->opposite_y;
            $additionPoint->origin_z = $lastItem->origin_z;
            if (\count($currentContainer->addition_points) < $currentContainer->addition_point_count) {
                \array_push($currentContainer->addition_points, $additionPoint);
            } else {
                $currentContainer->addition_points[$currentContainer->addition_point_count - 1] = $additionPoint;
            }
        }

        // Add a new addition point to the container based on the last item
        if (($lastItem->origin_x < $currentContainer->width - $this->epsilon) &&
            ($lastItem->origin_y < $currentContainer->height - $this->epsilon) &&
            ($lastItem->opposite_z < $currentContainer->length - $this->epsilon)) {
            $currentContainer->addition_point_count = $currentContainer->addition_point_count + 1;
            $additionPoint = new ItemLocation();
            $additionPoint->origin_x = $lastItem->origin_x;
            $additionPoint->origin_y = $lastItem->origin_y;
            $additionPoint->origin_z = $lastItem->opposite_z;
            if (\count($currentContainer->addition_points) < $currentContainer->addition_point_count) {
                \array_push($currentContainer->addition_points, $additionPoint);
            } else {
                $currentContainer->addition_points[$currentContainer->addition_point_count - 1] = $additionPoint;
            }
        }

        // Update the profit
        if ($itemsCount === 1) {
            $solution->net_profit += ($currentItemType->profit - $solution->containers[$containerIndex]->cost);
        } else {
            $solution->net_profit += $currentItemType->profit;
        }

        // Update the volume per container and the total volume
        $solution->total_volume += $currentItemType->volume;
        $solution->total_weight += $currentItemType->weight;

        // Update the unpacked items
        if ($addType === 1) {
            $solution->unpacked_item_count[$itemTypeIndex] = $solution->unpacked_item_count[$itemTypeIndex] - 1;
        }
        return true;
    }
}

So the main question is if maybe you can find something which possibly can improve the amount of iterations the algorithm can do.

(Since the code is pretty big, here is a pastebin)

Answer 1

1. I don't personally know of any advantage to prefixing php functions with a backslash, so consider removing the unnecessary character. (or tell me why it is useful)

2. Perform arithmetic once. AKA "Don't Repeat Yourself" (D.R.Y.)

   $additionPointsCount = \count($currentContainer->addition_points);
   

   becomes:

   $lastPoint = count($currentContainer->addition_points) - 1;
   

3. I'd have to double check the docs to recommend a replacement for goto(), but I'm pretty sure that the php docs say to avoid it all costs. I recall a comic strip illustration that conveys the importance of its avoidance. Then again, unless I am overlooking something, perhaps this is a suitable use case which avoids having to manually transfer variables into a new curom function scope.

4. If two separate sets if conditions lead to the same goto, then write D.R.Y. code and merge the conditions. Likewise with several conditions that lead to continue.

5. To simplify conditions evaluating the same value with two or more sets of ||, use in_array(). When ordering the conditions, write the least expensive evaluations first and the most taxing evaluations (that, say, make a function call) last. Because conditions short circuit on the first "condition breaking" false, the heavier checks are avoided and efficiency is gained. Also, try to remove excessive parentheses.

   if ((($currentRotation === 3) || ($currentRotation === 4)) && ($currentItemType->xy_rotatable === false)) {
       continue;
   }
   

   becomes

   if ($currentItemType->xy_rotatable === false && in_array($currentRotation, [3, 4])) {
       continue;
   }
   

6. If you can't manage to reverse all of the logic in a multi-conditional expression (leading to continue 2;), then wrap all of the conditions in parentheses and write ! before it to provide the opposite boolean evaluation, this way you don't need the else branch.

7. When pushing just one element into an indexed array, just use square braced syntax and spare the array_push() call.