How can I use linear programming to distribute S into two bins?

[timeone]

I have a problem at work I'm trying to solve and I can't figure out a good way to do it, hoping someone might be able to help. I have put the relevant info in the below pastebin. Basically I want to distribute some amount of S into two bins, one of which is split into smaller bins, in such a way that the amount between the two is as close to some give ratio as it can be, and then the amount in the first larger bin is split as close as equally among the smaller bins inside of it.

I was thinking about the Simplex algorithm but not sure how well it would work...

http://pastebin.com/wsR86rev

 

[WWGD]

Sorry, I'm confused; seems you're defining $S_b$ in terms of itself?

 

[Mark44]

I have a problem at work I'm trying to solve and I can't figure out a good way to do it, hoping someone might be able to help. I have put the relevant info in the below pastebin. Basically I want to distribute some amount of S into two bins, one of which is split into smaller bins, in such a way that the amount between the two is as close to some give ratio as it can be, and then the amount in the first larger bin is split as close as equally among the smaller bins inside of it.

I was thinking about the Simplex algorithm but not sure how well it would work...

http://pastebin.com/wsR86rev

From Pastebin at the link above:

1.S_a = c_1 * I_1 + c_2 * I_2 + ... + c_n * I_n
2.S_b = c_Sb * I_Sb
3.S_total = S_a + S_b
4.0 <= I_i <= k_i
5.0.00 <= r <= 1.00
6.I_i is a positive integer for all i in {1..n}
7.sum(I_i for all i in {1..n})/I_Sb <= r/(1-r)

9.find all I_i, I_Sb

10.minimize |I_j - I_k| for all j,k in {1..n} and j != k and j,k != Sb (basically want as much of an even split as possible in S_a)

12.known constants: c_i, r, S_total, k_i

13.|x| is absolute value of x

This is gibberish until you tell us more clearly what you're trying to do.

 

[timeone]

Hi Mark,
Sorry for being too vague, I was trying to reduce it into a series of equations to make the linear algebra problem more clear. I'll give an example:

Suppose $S$ is the total budget say $100, $S$ should be split into two sub groups, $S_a$ and $S_b$. $S_a$ contains sub groups, $G_1$ through $G_n$, and $G_i$ = $c_i$*$I_i$. Think of $c_i$ as some fixed cost per item for a group of items $I_i$. The second top level group, $S_b$, is the spillover group. Give some percentage, say r=30%, I'd ideally like 30% of the items in group $S_a$ and 70% in group $S_b$. This doesn't necessarily mean the budget is split 30/70, just the items. Only so many items can fit in each sub-group( $I_i$ <= $k_i$ ). If not all the items can fit in $S_a$ , put them in the $S_b$ along with the other 70%.

Basically I'm trying to figure out how many items can go in each group, keeping the ratio of items between $S_a$ and $S_b$, keeping an even split of items between all sub-groups $G_i$, and having the sum of all groups equal the total budget.

 

[blue_raver22]

I understand the importance of finding efficient solutions to problems at work. In this case, it seems like a linear programming approach would be suitable for your problem. The Simplex algorithm is a commonly used method for solving linear programming problems and it may work well in this situation.

To start, you will need to formulate your problem into a linear programming model. This involves identifying the decision variables, objective function, and constraints. The decision variables in your case would be the amount of S in each bin. The objective function would be to minimize the difference between the two bins, and the constraints would include the given ratio and the requirement for the first larger bin to be split equally among the smaller bins.

Once you have your model, you can use the Simplex algorithm to find the optimal solution. This algorithm works by moving from one feasible solution to another in a way that improves the objective function. It may take some trial and error to set up the model and run the algorithm, but it should provide a good solution to your problem.

In addition to the Simplex algorithm, there are other methods for solving linear programming problems such as the interior-point method and the branch and bound method. It may be worth exploring these options as well to see which one works best for your specific problem.

I hope this helps and good luck with finding a solution to your problem!