Algorithms

19-Jul-15 20:39

Sorry for my English. Smile | :)

_____________________
I can't find an algorithm for this special type of bin packing problem: Cry | :((

____________________

Consider a warehouse with a number of shelves that have number, width, height, depth and limit Weight capacity.

The objects 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 objects that have the lowest waste of space. and objects weight not be more than shelf weight capacity.

** If a place was assigned to an object, back, front, and on it can not be allocated.

Richard MacCutchan19-Jul-15 21:47

19-Jul-15 21:47

I guess you did not try https://www.google.com/search?q=packing algorithm 3d[^]

Cenator19-Jul-15 22:12

19-Jul-15 22:12

Thank you. Thumbs Up | :thumbsup:

Yes It is 3D Bin Packing, too.

But here:

1) We have several shelves.
2) If a place for an object was assigned, we can't put any objects on it, in front of it or in back.(just left side or right side is true)

Richard MacCutchan19-Jul-15 22:23

19-Jul-15 22:23

Then you need to go and read some of the information in those links that Google provided.

Cenator19-Jul-15 22:55

19-Jul-15 22:55

funny!

what is wrong with you?
simply you can don't answer to me

Thumbs Down | :thumbsdown:

Richard MacCutchan19-Jul-15 23:05

19-Jul-15 23:05

Cenator wrote:
what is wrong with you?
simply you can don't answer to me

I gave you an answer in my first message. Click on the link and you will find the information you are asking for.

I also suggest you read http://www.codeproject.com/Messages/2966804/How-to-get-an-answer-to-your-question.aspx[^] for future reference.

Eddy Vluggen20-Jul-15 0:19

Eddy Vluggen

20-Jul-15 0:19

That's a nice way of saying "thank you".

If there was an answer readily available, we would not have to write so much code. If you can do the procedure for one shelf, you can do it for multiple shelves.

So, where is the problem? Smile | :)

Bastard Programmer from Hell Suspicious | :suss:

If you can't read my code, try converting it here[^]

harold aptroot20-Jul-15 4:25

harold aptroot

20-Jul-15 4:25

Try to write it as an integer linear programming model, it can be solved directly (maybe not efficiently, it depends) and it helps other people understand exactly what your problem looks like so we're sure we're all talking about the same problem.
If you have that, I'll gladly take a look at it.

Cenator18-Aug-15 20:28

18-Aug-15 20:28

Hi I did It In New Post

Patrice T22-Jul-15 8:10

22-Jul-15 8:10

This is not a 3D packing problem !

If you want to optimize the warehouse usage, you need to choose if you want to minimize wasted space or wasted weight.

an algo:

sort the cubes from biggest to smallest.
for each cube
   Select available places
   place the cube at the place which waste minimum
next

if your problem allow to put more than 1 cube in a place which is not stated), then it is 3D packing

Patrice

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

Member 1179127122-Jul-15 8:25

Member 11791271

22-Jul-15 8:25

Thank you very much

This is my answer

Cenator22-Jul-15 18:53

22-Jul-15 18:53

Finally I did it:

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.RemainWidth >= itemToPlacing.Width)
                if (binNode.Value.RemainWeight >= itemToPlacing.Weight
                    && binNode.Value.Height >= itemToPlacing.Height
                    && binNode.Value.Depth >= itemToPlacing.Depth)
                {
                    LinkedListNode<Partirion> partitionNode;
                    LinkedListNode<Partirion> Best;
                    Best=null;
                    partitionNode = binNode.Value.parts.First;
                    while (partitionNode != null)
                    {
                        //Best Fit :
                        if (partitionNode.Value.num == -1
                            && partitionNode.Value.size >= itemToPlacing.Width
                            && (Best == null || partitionNode.Value.size <= Best.Value.size))
                        {
                            Best = partitionNode;
                            if (Best.Value.size == itemToPlacing.Width)
                                break;
                        }
                        partitionNode = partitionNode.Next;
                    }
                    if (Best != null)
                    {
                        //separate node:
                        Partirion newPart = new Partirion(itemToPlacing.Width, itemToPlacing.Number,
                            Best.Value.cmBegin);
                        Best.Value.cmBegin += itemToPlacing.Width;
                        Best.Value.size -= itemToPlacing.Width;
                        //Add Nodes:
                        binNode.Value.parts.AddBefore(Best, newPart);
                        //
                        itemToPlacing.BinNumber = binNode.Value.Number;
                        binNode.Value.RemainWidth -= itemToPlacing.Width;
                        binNode.Value.RemainWeight -= itemToPlacing.Weight;
                        binNode.Value.RemainVolume -= itemToPlacing.Width
                            * binNode.Value.Height * binNode.Value.Depth;
                        isPlaced = true;
                        return ("item: (" + itemToPlacing + ") ====> Bin: (" + binNode.Value + ")");
                    }

                }
            binNode = binNode.Next;
        }
        itemToPlacing.changeSideState();
        allSideStates++;
    }
    return "Not Found";
}

modified 23-Jul-15 1:00am.

Patrice T22-Jul-15 20:21

22-Jul-15 20:21

Patrice

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

Patrice T22-Jul-15 22:10

22-Jul-15 22:10

Now you investigate to see what gives the best solution
- no sort of cubes
- sort from biggest to smallest
- sort from smallest to biggest

Patrice

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

Cenator22-Jul-15 22:17

22-Jul-15 22:17

Thanks

Yes; Best way is here:

LinkBinsOrItems.sortItemList();//Biggeset To Smallest
LinkBinsOrItems.sortBinList();//Smallest To Biggest

Best Sort Mode:

private void btnBestMode_Click(object sender, EventArgs e)
{
    //Check if Lists Are Empty?
    //If the LinkedList<T> is empty, the First and Last properties contain null.
    if (LinkBinsOrItems.listOfBins == null)
    {
        if (LinkBinsOrItems.listOfItems == null)//If Both Of Lists Are Empty
        {
            MessageBox.Show("Item List And Also Bin List Are Empty!!"
                +"You Must Enter Bins And Items..."
                , "Bin List And Item list Empty Error", MessageBoxButtons.OK
                , MessageBoxIcon.Information);
            return;
        }
        //If Only Bin List Is Empty
        MessageBox.Show("Bin List Is Empty!! You Must Enter Bins...", "Bin List Empty Error"
            , MessageBoxButtons.OK, MessageBoxIcon.Information);
        return;
    }
    //If Only Item List Is Empty
    if (LinkBinsOrItems.listOfItems == null)
    {
        MessageBox.Show("Item List is Empty!! You Must Enter Items..."
            , "Item List Empty Error", MessageBoxButtons.OK, MessageBoxIcon.Information);
        return;
    }

    //Show Warning To User
    DialogResult result = MessageBox.Show("Are you sure you want to do sorting "
        +"for creat more free space?(This can change items places"
        , "Sort For Best Mode",MessageBoxButtons.YesNo,MessageBoxIcon.Question);
    if (result == DialogResult.No)
        return;

    LinkedListNode<Item> itemNode;
    LinkedListNode<Bin> binNode;

    //Clear Bins And Items Relations
    itemNode = LinkBinsOrItems.listOfItems.First;
    for (int i = 1; i <= LinkBinsOrItems.listOfItems.Count; i++)
    {
        itemNode.Value.BinNumber = -1;
    }
    binNode = LinkBinsOrItems.listOfBins.First;
    for (int i = 1; i <= LinkBinsOrItems.listOfBins.Count; i++)
    {
        binNode.Value.clearRelations();
    }

    //Sort Bin And Item List:
    LinkBinsOrItems.sortItemList();//Biggeset To Smallest
    LinkBinsOrItems.sortBinList();//Smallest To Biggest

    //Do Placing:
    listBox1.Items.Add("");
    itemNode = LinkBinsOrItems.listOfItems.First;
    for (int i = 1; i <= LinkBinsOrItems.listOfItems.Count; i++)
    {
        listBox1.Items.Add(itemNode.Value);
        listBox2.Items.Add(LinkBinsOrItems.placeItemInBin(itemNode.Value));
        itemNode = itemNode.Next;
    }

    //Inintal Rrport
    itemReportInitaling();//test
    BinReportInitaling();//Test
}

Patrice T23-Jul-15 5:07

Re: GA/GEP Mutation Rates

23-Jul-15 5:07

Cenator wrote:
Thanks [Rose]

Thank you.
CP have a standard way to reward contributors: click on the green arrow on left of the useful answer/advice. the author is rewarded with reputation points and you also gain some organizer points.
--------------------------------------------
Depending on reality of the problem size of the warehouse and number of cubes to fit, you may want to optimize the answer even further.

Patrice

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

GA/GEP Mutation Rates

Dominick Marciano17-Jul-15 11:25

Dominick Marciano

17-Jul-15 11:25

I wasn't sure if this forum was the best one for this question, so I apologize in advance if it isn't.

I'm currently learned Gene Expression Programming and I'm a little unclear as to how the mutation rate is applied to a population. I've looked at source code from different implementations and I've seen it used different ways and would like to know if there is actually a proper way to implement it or if it can be implement at the programmers discretion.

As an example, say there are 10 chromosomes, each with 2 genes, and each gene has 10 nodes and the mutation rate (mr) is 0.1. I've seen code that mutates nodes implemented in these way:

Loop through each chromosome and generate a random number (rn) between 0 - 1 on each loop. If the rn <= mr then select the gene for mutation. Then loop through every node of the chromosome, ignoring gene boundaries (so in this example there are 20 nodes = 10 nodes/gene * 2 genes) and generate another rn and if the rn <= mr, mutate the node.
Loop through each chromosome and generate a random number (rn) between 0 - 1 on each loop. If the rn <= mr then select the gene for mutation. Then loop through each gene, again generating a rn on each loop, and if the rn <= mr select the gene for mutation, otherwise continue the loop. If the gene is selected for mutation, loop through each node of the selected gene (10 nodes since there are 10 nodes/gene), generating a rn on each loop and mutate the selected node if rn <= mr.
Randomly select 10% of the nodes in the entire populate (in this case 20 nodes since there are 200 nodes = 10 chromosomes * 2 genes/chromosome * 10 nodes/gene).
Randomly select 10% of the chromosomes (in this case 1 chromosome) and then select the nodes for mutation following the same procedure as Item 1 or Item 2 above, starting from the second loop.

I believe that either Item 1 or Item 2 would be the correct way to apply the mutation operator, but I haven't been able to find a definitive answer either through searches on Google/CP or in the book I have been reading.

One other thing that is mentioned in the book I am reading, but isn't explained in detail is the following: there is a population of 10 chromosomes, each with 1 gene, and a total length of 14 nodes. The book states that the mutation rate should be equivalent to two one-point mutations per chromosome, which in this case (because the chromosome's length is 14) should be 0.143. How was a mr of 0.143 derived from the chromosome length of 14? This isn't explained anywhere so far, even though this equivalence has been mentioned multiple times.

Any information, or links to answers, would be greatly appreciated. Thank you in advance for any help.

A black hole is where God tried to divide by zero.

There are 10 kinds of people in the world; those who understand binary and those who don't.

Alan Balkany30-Jul-15 7:19

Alan Balkany

30-Jul-15 7:19

IMHO the type of mutation doesn't matter that much. Its purpose is to "jump" to nearby areas in the problem space. Any variation will accomplish that. The best mutation rate can't be stated as a hard and fast rule, as in that book; it will depend on the specific problem you're trying to solve.

(BTW, there's no "singularity" at the center of a black hole; the "infinite density" is an artifact of using continuous equations to describe a discrete system. The physicists have mistaken their equations for the reality they're trying to model.)

C/C++ algorithm to reorganize and extract the data

feifeihanyu10-Jul-15 4:22

feifeihanyu

10-Jul-15 4:22

Hi all,

I have three arrays: X[i], Y[i] and Value[i], which are the position (x, y) of the pixel "i" and its value (pixel actived as 1, otherwise 0). Pleae have a look at this graph linked:

[See here, please: "graph"]
Data format is also shown at the right side of the graph. I would like to extract the sub-array which represents connected-components (or spots) in the image since the data is sorted in order of ascending x rather than in order of spots.
It is easy to achieve my purpose by programing in Matlab which already has some advance functions. But for the reason that it is huge data and low processing speed in matlab), I have to do carry out it by using C/C++.
Does anyone have some good idea to extract sub-array for each spot? Thanks in advanced.

With best regards
feifeihanyu

modified 10-Jul-15 10:31am.

Re: C/C++ algorithm to reorganize and extract the data

Richard MacCutchan10-Jul-15 4:47

Re: C/C++ algorithm to reorganize and extract the data

10-Jul-15 4:47

You need some extra information to connect the pixels that make a spot. As it stands there is no way to be certain that, for example, spot(5, 8) connects to the other two. What would happen if the blue spot was touching the red one, how would you tell where the separation occurs?

feifeihanyu10-Jul-15 5:53

feifeihanyu

10-Jul-15 5:53

Hi, thanks for reply!
All connected-pixels make a spot! If the blue spot touchs the red one, then they are actually one spot!
There is an algorithm to label connected-components in binary image. see here Blob detection
The difference from that example is that I already have arrays representing non-zero pixel positions with pixel values instead of a full binary image! The problem is that (x, y) of spots/blobs is sorted in order. so the positions (x, y) of different spots and blobs may mix together if they local at the same raw or column! for example, the positions of the red and the purple,please see my graph and right side, I labeled the positions from the same spot by lines.

Actually, I can transform the arrays into a full binary image, then perform a similar algorithm like Blob detection . But it will be a problem if I have many images which have few blobs but with big dimension, for example, 4096x4096. then it not wise to do that becasue many time will be wasted in loop search. I need an algorithm dealing with the arrays directly in stead of a full binary image. This is why I post a question here for asking for help.

regards
feifeihanyu

modified 10-Jul-15 12:21pm.

Re: C/C++ algorithm to reorganize and extract the data

Member 1184955320-Jul-15 3:53

Member 11849553

20-Jul-15 3:53

can somebody tell me who i can talk to regarding Mathematics and Algorithms

Re: C/C++ algorithm to reorganize and extract the data

Richard MacCutchan20-Jul-15 4:40