How to optimally empty your bucket?

Introduction

This is an IBM Ponder This Challenge .

The Bucket Empty Sequence (BES) problem is a type of mathematical optimization problem that can be formulated as a Mixed Integer Linear Programming (MILP) problem. In this problem, we are given a set of buckets, each with a certain capacity, and a sequence of tasks, each requiring a certain amount of fluid to be poured into or out of a specific bucket. The objective of the problem is to find a sequence of tasks that will empty all/some/any buckets.

Consider N buckets, there are ni balls in backet i. The goal is to empty any of the backets, but we can only perform one type of move: Choose two backets,  p and m transfer balls from p to m until the total balls in m is doubled.

For example: assume the initial content of the buckets is [3, 4, 8]

Step --> Bucket content ,

1 [3, 4, 8] 
2 [6, 1, 8] 
3 [6, 2, 7] 
4 [4, 4, 7] 
5 [0, 8, 7]         

For a given initial content find the required steps to empty one bucket.

Looks easy ? if Yes then do the formulation by yourself and then you can compare it with mine.

If not, let's investigate the required model altogether.

There are different things which should be formulated.

1- What to calculate ?

• The required move at each step
• When to stop ?

2- What is the objective function?

• Finish time

Model development

Let's do some math:

We need:

• a real variable stating the content of each bucket at time t -----> v[i,t]
• a binary variable indicating if the content of bucket i is moved to bucket j at time t -----> U[i,j,t]
• a real variable indicating how much the content of bucket i is moved to bucket j at time t -----> move[i,j,t] and move[i,j,t] <= M* U[i,j,t]
• a binary variable stating the content of each bucket is empty at time t --> P[i,t]
• a binary variable indicating if the search should continue at time t --> z[i,t]

• Updates the content of bucket i based on the movements to/from bucke j at t
• if U_ijt=1 then move_ijt can take non-zero value
• 3-4 will make sure if the move is made then 'double content rule' is satisfied
• 5,8 if the bucket i at t is full P =1 then stop the search z=0
• 6 find a bucket i at any time t and make sure it is empty
• 7 don't allow move between buckets i-j if z =0

Pyomo code Github code

Results:

Let's try it for a bigger number of buckets N = 8:

[319, 980, 986, 570, 949, 153, 979, 308, 780]        

The algorithm decided to empty the bucket 9 to minimize the required time.

Now let's try to empty a specific bucket 1-->5 (what should be changed in the model?) :

Applications:

Practical applications of the Bucket Empty Sequence problem include:

1. Chemical Engineering: In chemical plants, a variety of liquids need to be mixed in different proportions. The Bucket Empty Sequence problem can be used to optimize the order of pouring different chemicals into a container to achieve the desired mixture.
2. Resource Allocation: In industries such as manufacturing and logistics, resources such as machines, labor, and storage capacity need to be allocated efficiently. The Bucket Empty Sequence problem can be used to optimize the order in which different jobs are assigned to available resources.
3. Scheduling: In the scheduling of tasks, the Bucket Empty Sequence problem can be used to determine the optimal order of executing different tasks, where each task requires a certain amount of resources and must be completed within a certain time frame.
4. Production Planning: In production planning, the Bucket Empty Sequence problem can be used to determine the optimal order of producing different products, where each product requires a certain amount of raw materials and must be produced within a certain time frame.
5. Inventory Management: In inventory management, the Bucket Empty Sequence problem can be used to optimize the order in which different items are picked from inventory to fulfill customer orders, where each item has a certain quantity available and must be picked within a certain time frame.

Don't forget to subscribe to the github channel and Optimization in Open-source

You may also contact me !

PyomoChannel تلگرام