Optimization problem with box sizes

Optimization problem with box sizes

Postby Guest » Tue Jun 23, 2015 9:49 am

So I am trying to formulate a linear program to minimize shipping costs for a list of 1000 items of varying sizes. I have total of 10 options for box size and each has a different shipping cost. For the lowest shipping cost, I will put each item in the appropriate box but I want to buy only 3 different box sizes. How do I formulate this problem? Breaking my head over this for a week now....
Guest
 

Re: Optimization problem with box sizes

Postby Guest » Tue Jun 23, 2015 10:30 am

Decision variables = [tex]x_{1 }[/tex],........ x_{10}[/tex] for number of boxes of each size

Say [tex]a_{1 },.....a_{10 } =[/tex]cost for shipping each box size

Obj Function
Min [tex]a_{1 }x_{1 }+.....+a_{10 }x_{10 }[/tex]
Guest
 

Re: Optimization problem with box sizes

Postby Guest » Tue Jun 23, 2015 11:47 am

It should be a 0-1 integer program with [tex]x_{1 }[/tex],....,[tex]x_{10}[/tex] = {0,1} where 0 = do not use this box size and 1 = use this box size
also, another constraint [tex]x_{1 }[/tex]+....+[tex]x_{10}[/tex] <=3 to limit only 3 sizes
Thoughts?


Guest wrote:Decision variables = [tex]x_{1 }[/tex],........ x_{10} for number of boxes of each size

Say a_{1 },.....a_{10 } = cost for shipping each box size

Obj Function
Min a_{1 }x_{1 }+.....+a_{10 }x_{10 }
Guest
 

Re: Optimization problem with box sizes

Postby Guest » Tue Jun 23, 2015 11:52 am

This is not a linear programming problem but an integer programming problem (there is no way to enforce a constraint that says at most 3 quantities are non-zero using just linear programming). Your best bet for solving this sort of problem is just to write a custom program to search through all the different possibilities (there are only 120 different combinations of 3 choices of box).

Hope this helped,

R. Baber.
Guest
 

Re: Optimization problem with box sizes

Postby Guest » Tue Jun 23, 2015 2:35 pm

n1,n2,....,n10 = number of boxes of each size
c1,c2,...,c10 = cost of shipping each size
x1,x2,...,x10 = binary for decision to use box
y1,y2,...,y10 = number of items taht will fit in each of 10 boxes

Obj func Min c1.n1.x1 + c2.n2.x2 +..... +c10.n10.x10

Constraints
x1,x2,...x10 = {0,1} 0 = do not use box, 1 = use box
x1 + x2 +... + x10 = 3 so only 3 box sizes are used
n1 + n2 +.... +n10 = 1000 so all items have boxes
n1 <= y1
n2 <= y1 + y2
.
.
.
.
n10 <= y1 + y2 +... +y10
x1,x2....,x10,y1,y2,...,y10,n1,n2,...,n10 >=0
Guest
 

Re: Optimization problem with box sizes

Postby Guest » Tue Jun 23, 2015 2:37 pm

Does this make sense? Am I missing something here???

Guest wrote:n1,n2,....,n10 = number of boxes of each size
c1,c2,...,c10 = cost of shipping each size
x1,x2,...,x10 = binary for decision to use box
y1,y2,...,y10 = number of items taht will fit in each of 10 boxes

Obj func Min c1.n1.x1 + c2.n2.x2 +..... +c10.n10.x10

Constraints
x1,x2,...x10 = {0,1} 0 = do not use box, 1 = use box
x1 + x2 +... + x10 = 3 so only 3 box sizes are used
n1 + n2 +.... +n10 = 1000 so all items have boxes
n1 <= y1
n2 <= y1 + y2
.
.
.
.
n10 <= y1 + y2 +... +y10
x1,x2....,x10,y1,y2,...,y10,n1,n2,...,n10 >=0
Guest
 

Re: Optimization problem with box sizes

Postby Guest » Fri Jul 10, 2015 1:01 am

The problem says that the 1000 items are of different sizes. It will help to categorise these items by size, indicating also the number of items in each sizs. Then identify how many units of which sizes can be filled into each Box type.
For example, suppose that all items can be categorized into two sizes, P and Q, in the proportion 300 :700. Suppose further that Box type B1 can hold 4 units of P and 7 units of Q. Similar data will be needed for each Box size.
With this data, the Integer program can be defined.
Guest
 


Return to Programming and Algorithms



Who is online

Users browsing this forum: No registered users and 1 guest