Re: Bin Packing - Algorithms Discussion Boards

What have you tried so far in solving this?

"I've seen more information on a frickin' sticky note!" - Dave Kreskowiak

Consider a warehouse with a number of shelves(Bins) that have number, length, width, height and limit Weight capacity.

The Items that place in this warehouse are a number of cubes that have number, length, width, height and weight.

The algorithm must find the right place for Items so Bins have the lowest waste of space. and sum of weight of Items in each bin must not be more than its weight capacity.

Items are placed at the edge of Bins. Namely, any Items can't be placed on Items, behind Items and in front of Items.
____________
I tried to write my problem as an integer linear programming model.

I can't Upload Image Of My Linear Model So I Insert This Link: Here Is the link
[Click Here]
______________
I tried this algorithm:

1_ Sort list of bins Smallest To Biggest.

2_ Sort list of items Biggest To Smallest.

3_ insert each item in first bin that have free space, by best fit algorithm.

It worked but can't swap bins when it's necessary. In other words it is not an optimized algorithm.

please help me Smile | :)

modified 19-Aug-15 5:34am.

Please don't repost the same message if it doesn't appear immediately.
All three of your posts went to moderation, and required a human to decide if they were or were not spam.
I have deleted the "spares".

Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...

The ILP model allows items to overlap inside a bin, is that supposed to be possible?

No How can I Fix It?

Make copies of every item, one copy per "way it could fit in the bin", then ban combinations that overlap (for ex. in a 2x2x2 bin if you have an 1x1x2 item and a 1x2x2 item, then the case where the 1x2x2 is flat on the ground and the 1x1x2 item is standing upright is illegal). Also have a constraint that says that in total you will take the item exactly once (sum of all copies is 1).

Hi,
Already seen this question somewhere Smile | :)

What about giving your actual code and explain where you have a problem ?

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

Hi
This is about my "project course".

The project almost completed by c#.

[^]
______________
I used a greedy algorithm to placing items in bins so it is not a optimized algorithm. Cry | :((

here is my placing function:

C#

public static string placeItemInBin(Item itemToPlacing)
{
    sortBinList();
    LinkedListNode<Bin> binNode;
    bool isPlaced = false;
    int allSideStates = 1;

    while (allSideStates <= 2)
    {
        binNode = listOfBins.First;
        while (isPlaced == false && binNode != null)
        {
            if (binNode.Value.RemainLength >= itemToPlacing.Length)
                if (binNode.Value.RemainWeight >= itemToPlacing.Weight
                    && binNode.Value.Width >= itemToPlacing.Width
                    && binNode.Value.Height >= itemToPlacing.Height)
                {
                    LinkedListNode<Partition> partitionNode;
                    LinkedListNode<Partition> Best;
                    Best=null;
                    partitionNode = binNode.Value.parts.First;
                    while (partitionNode != null)
                    {
                        //Best Fit :
                        if (partitionNode.Value.num == -1
                            && partitionNode.Value.size >= itemToPlacing.Length
                            && (Best == null || partitionNode.Value.size <= Best.Value.size))
                        {
                            Best = partitionNode;
                            if (Best.Value.size == itemToPlacing.Length)
                                break;
                        }
                        partitionNode = partitionNode.Next;
                    }
                    if (Best != null) //Now Is Time To Place Item In Bin
                    {
                        string placingDetail;

                        if (Best.Value.size == itemToPlacing.Length)//No Need To Separate Nodes
                        {
                            Best.Value.num = itemToPlacing.Number;
                            itemToPlacing.CmPlaceInBin = Best.Value.cmBegin;
                        }
                        else //Separate Nodes
                        {
                            Partition newPart = new Partition(itemToPlacing.Length, itemToPlacing.Number,
                                Best.Value.cmBegin);
                            Best.Value.cmBegin += itemToPlacing.Length;
                            Best.Value.size -= itemToPlacing.Length;
                            //Add New Part Node:
                            binNode.Value.parts.AddBefore(Best, newPart);
                            //
                            itemToPlacing.CmPlaceInBin = newPart.cmBegin;
                        }

                        itemToPlacing.BinNumber = binNode.Value.Number;
                        binNode.Value.RemainLength -= itemToPlacing.Length;
                        binNode.Value.RemainWeight -= itemToPlacing.Weight;
                        binNode.Value.RemainVolume -= itemToPlacing.Length
                            * binNode.Value.Width * binNode.Value.Height;
                        isPlaced = true;
                        if (itemToPlacing.IsRotate == true)
                            placingDetail = "Item: Number: " + itemToPlacing.Number +
                            " (Rotated), Placed In Bin Number: " + binNode.Value.Number;
                        else
                            placingDetail = "Item: Number: " + itemToPlacing.Number +
                            " (Not Rotated), Placed In Bin Number: " + binNode.Value.Number;
                        return placingDetail;
                    }
                }
            binNode = binNode.Next;
        }
        itemToPlacing.changeSideState();
        allSideStates++;
    }
    //Bin Not Found
    itemToPlacing.BinNumber = -1;
    itemToPlacing.CmPlaceInBin = -1;
    return "Not Found";
}

You should update your question with the code, so everyone will see it.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

How do you define Best fit or Wasted space ?

your optimisation is combinational !
Which mean that to best fit a packet, you may need to move another one, and the move can cascade until you find a combination of placement that is better.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

CSS

BestFit:
Minimize: Item.Length*Bin.Width*Bin.Height
Subject To: Bin.RemainWeight>=Item.Weight & Bin.RemainLength>=Item.Length

___________________

Right,
I Don't know when must replace Items in Bins

so I need an algorithm

Does this make sense? Shouldn't we just minimize the total amount of bin-space?

Right,
It has a similar meaning:
"We should maximize the total used amount of bin-space and maximize the used amount of bin-weight-capacity"

I think your problem is a cross between a few problems:

- it is similar to the knapsack problem with Multiple constraints
https://en.wikipedia.org/wiki/Knapsack_problem[^]

- It is similar to the cutting stock problem with real stock and where the cut don't go back in stock.

And certainly a few others.

What is important is that they are all NP-Hard problems.
Starting from there your optimisation program is more or less a tree exploration program.
On each step, you try to place a packet in the warehouse, if you find a place, go to next packet, otherwise, if you fail to find a place, you backtrack to move previous packet until you success.
To reduce computing time, you sort packets by difficulty to place, starting by the most difficult.
The base of your program will be a recursive tree exploration program.

By the way, your program will fail when a difficult packet comes and the only place is already in use, in this case, you have to backtrack.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

Strict alternation (using a variable turn that can take the values 0 or 1) can be used to enforce mutual exclusion among two processes p0 and p1.
A. Generalize the idea to get a procedure for mutual exclusion among n processes p0 through
pn−1.
B. Generalize further, to create a procedure for l-exclusion, where n > l ≥ 2.
For both of the above, write suitable pseudocode, and prove if the three desired properties are satisfied with it

This sounds like homework. Which I am afraid to say that you wont get anyone answering that for you.

People will help you with your homework if you show the work that you have done and give a detailed explanation of what you are expecting the code to do (and not to repeat the homework) and what is happening.

Every day, thousands of innocent plants are killed by vegetarians.

Help end the violence EAT BACON

It is actually not a homework. I am trying to apply classic distributed algorithms in a peer-to-peer n player mobile game where each player plays only with one of the players who hasn't already lost in an earlier round to another player. A player who has lost waits until last player wins against runner-up , at which time all players are back in game, until then they need play proxy games with any other lost player to improve skills and ranking, but not get any points when the tournament restarts.

When there are is any player playing in tournament, the code looks like this :
for process i
while( 1)
{
while( games[i/2] != 0){}
enter criticalsection and play game;
games[i/2] <- 1; //assign to other player
//after m such rounds, if score of I is > score of I+1, I wins, else I+1 wins. But my challenge is winner set array should be accessible by only one of n processes.

You could have explained that in the first place in a single question, rather than the three you posted.

I thought splitting into three discrete smaller problems would help get focused sharper suggestions. Thanks for pointing out

If it is not homework, it look furiously like it.

Have you done something ? or do you just someone to give you a full functional solution ?

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

SQL

A file is to be shared among n different processes, each of which has a unique process ID (a natural number) associated with it. The file can be accessed simultaneously by several processes, subject to the following constraint: if a process with an even process ID is accessing the file, only other processes with even process IDs are permitted to access it; processes with odd IDs are barred, and must wait until all the even-ID processes finish with the file. Similarly, if a process with an odd ID is accessing the file, only other odd-ID processes are permitted to access it, and even-ID processes must wait until all the odd-ID processes finish.
Give pseudocode for a process pi, 0 ≤ i ≤ n − 1.

Sorry but this site does not provide the answers to your homework questions. You need to show what you have done and where you are stuck.

It is actually not a homework. I am trying to apply classic distributed algorithms in a peer-to-peer n player mobile game where each player plays only with one of the players who hasn't already lost in an earlier round to another player. A player who has lost waits until last player wins against runner-up , at which time all players are back in game, until then they need play proxy games with any other lost player to improve skills and ranking, but not get any points when the tournament restarts.

When there are is any player playing in tournament, the code looks like this :
for process i
while( 1)
{
while( games[i/2] != 0){}
enter critical section and play game;
games[i/2] <- 1; //assign to other player
//after m such rounds, if score of I is > score of I+1, I wins, else I+1 wins.

Scores for each round in a tournament is stored in a different file for each cycle of tournament and hence I need it to be accessible by only one player - winner or loser( winner is even and loser is assigned odd number and reordered after every round to determine ranking for next tournament round)

The final sentence in your original post reads:

Quote:
Give pseudocode for a process pi, 0 ≤ i ≤ n − 1.

, which is why it was thought to be a homework question.

Apologies, I did not know there would be people on this forum scouting for assignment/homework answers. My bad. Hope my thread is not flagged or marked as spam.
Any rough idea/guidance on which I can build will do