How I Optimized My Leaf Raking Technique Utilizing Linear Programming

, and it’s formally leaf-raking season. As I engaged on this tedious activity, I noticed it’s principally one large optimization downside.

When raking my leaves, I made 4 piles: one on both facet of the tree, one close to the entrance, and one on the far facet of the yard to catch the sparsely distributed leaves that the wind had caught.

As I labored, I started to surprise: how removed from optimum was this? Would fewer piles be quicker as a result of I’d bag every part without delay? Or extra piles, so I wouldn’t should rake as far? Perhaps a single back-to-front cross would decrease complete time?

Determined to attenuate the time I spent raking, my mind stopped raking and began modeling.

Why Optimization Nonetheless Issues

Optimization is a robust but typically missed instrument in knowledge science circles now dominated by machine studying. Don’t get me flawed, machine studying is nice, however generally I believe it may be simple to overlook the environment friendly answer (optimization algorithms) and bounce proper to the enjoyable one (ML methods).

Hopefully, after studying this, you’ll suppose that optimization will be enjoyable, too. I do know that after I first realized it, I began to see it in every single place. It actually modified the best way I perceived the world round me.

On this article, I’ll present how a easy yard chore will be modeled as a linear programming downside. Alongside the best way, we’ll:

1) break down the formulation behind a linear program (LP),
2) examine the optimum plan to intuitive human methods, and
3) see how the identical reasoning scales to different real-world issues.

Defining the Downside

In defining any optimization downside, there are a number of key components:

Goal perform: Figuring out the target perform is solely figuring out the objective of the issue. The target perform is at all times designed to maximise or decrease some worth. On this downside, we’re minimizing the time spent raking and bagging leaves.

Resolution Variables: The choice variables are the components of the issue you could management. For our leaf raking downside, the choice variables are the variety of piles that the raker decides to make, the place these piles are positioned, and which leaves are raked into every of these piles.

Constraints: We even have some which can be out of our management. After we decide constraints, we’re asking, “What components are past my management?” or “What are the principles?” Often, there are quite a lot of these. In terms of raking leaves, there are guidelines that we are able to’t change to make sure the job is completed nicely. Each leaf must be raked right into a pile, they usually can solely be raked to a location the place a pile has already been began. This additionally signifies that we can not have an infinite variety of piles (perhaps we may, however that defeats the aim of consolidating leaves into piles earlier than bagging). Lastly, we’re constrained by the quantity of leaves we are able to match into every bag since they’ve a restricted capability.

And identical to that, we now have the essential components of a linear program.

These components are current in each linear program formulation, nevertheless it can be helpful to outline units and parameters at this stage. We’ll proceed to this within the subsequent sections.

As a result of the mannequin employs binary variables to pick out open piles and integer variables to signify the variety of luggage (with linear constraints and prices), we formulate it as an integer linear program (ILP). If the task of 1 cell to 1 pile is relaxed so {that a} cell could also be cut up between a number of piles, it turns into a blended integer linear program (MILP).

Parameters and Assumptions

At first I assumed I’d simply want my raking velocity and bagging time.

Nevertheless, that rapidly expanded into a brief listing, together with raking velocity, bagging time, leaf distribution, wind route, and yard slope. I additionally wanted a option to signify every location within the yard.

A Fast Conceptual Experiment

If I have been to calibrate this, I’d rake a 100-ft part, mark each 10 ft, and report cut up occasions to estimate how raking velocity modifications with density and distance. My hunch is that as I rake leaves a farther distance, I decelerate. Maybe I can rake a pound of leaves one foot in lower than half the time that I can rake a pound of leaves two toes.

Likewise, I may time bagging for piles of various sizes: ¼ bag, ½ bag, ¾ bag, and a full bag-sized pile. Then, I may match a perform to point out how bagging time grows with leaf quantity. I think that is roughly linear.

I didn’t truly time myself doing these duties. As a substitute, I made tough estimates. The objective isn’t to attain excellent numbers, however to display the construction and method of linear programming.

All knowledge on this article is simulated or estimated from my very own yard. No exterior datasets concerned.

The Full Mannequin

1. Representing the yard

To account for leaf density per sq. foot and which leaves to rake (or assign) to which pile, we discretize the yard right into a grid of cells.

Units:

• I: set of yard cells (grid cells), listed by i.
• J: set of candidate pile websites, listed by j.

We additionally outline different parameters, akin to yard size, yard width, the dimensions of a facet of the grid sq., the middle of the tree trunk (from which the leaf distribution is derived), the radius of the tree trunk, the wind route, ellipticity of the leaf distribution, the unfold of the leaves, the bottom density of the leaves, an accumulation parameter, and decay energy parameter. All of those components contribute to figuring out the place the leaves are set on the very starting of the issue and will be noticed with their default values in Desk 1.

Desk 1 – Parameters and their estimated values

From these parameters and the leaf-density mannequin, we get hold of:

• mᵢ: mass of leaves (in kilos) in cell i ∈ I.
• dᵢⱼ: distance from the middle of cell i to candidate pile website j.

These are computed numerically (in code) and handled as given constants within the optimization mannequin.

2. Further mannequin parameters (timing / capability)

• α > 0: raking-time scaling issue; a baseline for the way lengthy it takes to rake a small mass of leaves over a brief distance. Greater α corresponds to decrease general raking velocity.
• β > 0: distance scaling parameter that fashions how raking effort grows with distance (i.e., raking turns into slower as leaves are moved farther).
• b₀ ≥ 0: mounted setup time per bag (seconds per bag opened).
• b₁ ≥ 0: bagging time per pound of leaves (seconds per lb).
• C > 0: bag capability (lb per bag).
• Kₘₐₓ ∈ ℕ₀: most variety of piles that could be opened.

We additionally outline the derived pile mass mⱼ as the overall mass of leaves assigned to pile j:

mⱼ = ∑ᵢ mᵢ xᵢⱼ

3. Resolution Variables

Now, we now have the entire parameters that we have to create the illustration of leaves distributed throughout a yard, and the parameters outlined that govern the mechanics of how these leaves will be raked and bagged. Let’s transfer on to our determination variables: raking (assigning) leaves to piles, opening piles, and the variety of luggage used.

Project variables

To find out which leaves will likely be raked to which piles, we arrange an task as such:

xᵢⱼ ∈ {0, 1}

for all i ∈ I, j ∈ J: xᵢⱼ = 1 if cell i is raked to pile j, else 0.

Pile-open variables

To find out the place to rake leaves to, we outline a pile-opening determination variable:

yⱼ ∈ {0, 1}

for all j ∈ J: yⱼ = 1 if pile j is opened (used), else 0.

Bag-count variables

Lastly, to make sure that we now have sufficient luggage to carry the leaves at every pile, we now have a bag depend variable for every pile, outlined as:

nⱼ ∈ ℕ₀

for all j ∈ J: integer variety of luggage used at pile j.

Each cell’s leaves have to be totally assigned to precisely one pile (through the xᵢⱼ’s), and bag counts nⱼ have to be enough to carry the mass assigned to every open pile.

4. Integrality Situations

Subsequent, we declare the variable domains explicitly. That is set notation (additionally used above), however don’t be confused by the notation. All that is saying is that every yard grid with leaves in it could both be assigned to a pile j or it could not, every pile could both be in a single cell or it could not, and the variety of luggage used to bag all leaves in pile j have to be an integer larger than zero.

Bear in mind, i represents the leaves within the yard and j represents the situation of the piles.

xᵢⱼ ∈ {0, 1}, for all i ∈ I, j ∈ J
yⱼ ∈ {0, 1}, for all j ∈ J
nⱼ ∈ ℕ₀,  for all j ∈ J

In Python, we specify these as:

# Resolution variables 
x = [[pulp.LpVariable(f"x_{i}_{j}", cat="Binary") for j in range(m)] for i in vary(n)] 
y = [pulp.LpVariable(f"y_{j}", cat="Binary") for j in range(m)] 
B = [pulp.LpVariable(f"B_{j}", lowBound=0, cat="Integer") for j in range(m)]

5. Goal Perform

Raking time relies on mass and distance; bagging time relies on pile mass and variety of luggage.
We decrease complete time:

decrease over x, y, n:

∑ᵢ∈ᴵ ∑ⱼ∈ᴶ xᵢⱼ · α · mᵢ · dᵢⱼ^β + ∑ⱼ∈ᴶ ( b₀ · nⱼ + b₁ · mⱼ )

The primary time period approximates raking effort: mass × distance^β, scaled by α. The second time period provides bag setup time: b₀ occasions the variety of luggage nⱼ and bagging time proportional to pile mass mⱼ through b₁.

In code, that is applied as:

∑ᵢ,ⱼ xᵢⱼ ( α mᵢ dᵢⱼ^β + b₁ mᵢ ) + b₀ ∑ⱼ nⱼ,

which is algebraically an identical, since

∑ᵢ,ⱼ xᵢⱼ b₁ mᵢ = b₁ ∑ⱼ ∑ᵢ mᵢ xᵢⱼ = b₁ ∑ⱼ mⱼ.

6. Constraints

Now recall the constraints we mentioned earlier. All we’re doing right here is taking those self same constraints and defining them with formal math in order that we are able to formulate and resolve the total downside.

(C1) Project

Every cell’s leaves have to be assigned to precisely one pile:

∑ⱼ∈ᴶ xᵢⱼ = 1, for all i ∈ I.

for i in vary(n):
    prob += pulp.lpSum(x[i][j] for j in vary(m)) == 1

(C2) Linking: use a pile solely whether it is opened
The leaves in a cell can’t be assigned to a location with out an opened pile. We outline this constraint as:
xᵢⱼ ≤ yⱼ, for all i ∈ I, j ∈ J.

for i in vary(n): 
    for j in vary(m): 
        prob += x[i][j] <= y[j]

(C3) Bag capability

Whole mass assigned to pile $j$ should not exceed the capability of its luggage:

∑ᵢ∈ᴵ mᵢ xᵢⱼ = mⱼ ≤ C nⱼ, for all j ∈ J.

# On this occasion, I used B[j] to signify n_j 
for j in vary(m): 
    prob += pulp.lpSum(plenty[i] * x[i][j] for i in vary(n)) <= bag_capacity_lb * B[j]

(C4) Most variety of piles

We restrict the overall variety of piles that may be opened:
∑ⱼ∈ᴶ yⱼ ≤ Kₘₐₓ.

prob += pulp.lpSum(y[j] for j in vary(m)) <= K_max

The Full Mannequin

Placing all of it collectively, we get:

decrease over x, y, n:

∑ᵢ∈ᴵ ∑ⱼ∈ᴶ xᵢⱼ · α · mᵢ · d_ij^β + ∑ⱼ∈ᴶ ( b₀ · nⱼ + b₁ · mⱼ )

topic to:

∑ⱼ∈ᴶ xᵢⱼ = 1, for all i ∈ I.

xᵢⱼ ≤ yⱼ, for all i ∈ I, j ∈ J.

∑ᵢ∈ᴵ mᵢ xᵢⱼ = mⱼ ≤ C nⱼ, for all j ∈ J.

∑ⱼ∈ᴶ yⱼ ≤ Kₘₐₓ.

This completes the mannequin specification.

For the total implementation (calibration, solver setup, and plots) see the undertaking repository: Leaf-Raking Optimization Code.

Testing Easy Heuristics

A heuristic is a “rule of thumb” method to fixing downside. When most individuals rake their yards, they use a easy heuristic whether or not they comprehend it or not.

To verify the worth added by optimization, I in contrast the ILP to 3 easy heuristics:

• Entrance Sweep: steady rake from the again of the yard ahead.
• Micro-piles: many small piles close to leaf-dense areas.
• Again-Entrance-Facilities: a number of giant piles in central spots.

Every heuristic returns a set of pile facilities based mostly on easy guidelines. As soon as these piles are made, we assume that the raker will rake every cell of leaves to the closest pile. Notice that underneath the optimization, the raker can rake leaves to a pile even when that pile will not be the closest.

Formulating the issue as a linear program previous to creating formal heuristics is crucial to make sure that the values returned by heuristics are possible and align with the optimization goal.

Even when fixing for an optimization is impractical, formulating one is usually very useful.

Under is an instance snippet displaying how the “micro-piles” heuristic initializes and refines facilities based mostly on leaf density:

Instance: Micro-piles heuristic

def centers_micro(cells, plenty, bag_capacity_lb, seed=42):
    rng = np.random.default_rng(seed)
    M_total = plenty.sum()
    okay = max(1, int(spherical(M_total / (2 * bag_capacity_lb))))
    probs = plenty / (M_total + 1e-12)
    facilities = cells[ rng.choice(len(masses), size=k, replace=False, p=probs) ]
    # Iteratively cut up dense clusters
    for _ in vary(8): 
        ... 
    return facilities

Full implementations for all heuristics can be found within the repository underneath src/core/facilities.py and src/core/front_sweep.py.

Outcomes

Determine 1: Whole time taken to rake the yard by every technique

The answer discovered by the optimization identifies 5 piles which can be principally centered across the tree. Its enchancment over easy heuristics is notable however not dramatic.

Discover that there is no such thing as a large optimality hole between the micro-piles methodology and the optimized plan. This illustrates the ability of heuristic strategies, notably when examined towards an optimum answer as an instance the efficiency of that heuristic methodology.

Determine 2: Heatmap of heuristic vs optimum raking (picture by creator). Rendered GIF seen on GitHub.

Conclusion

In lots of conditions, computing the total linear program is just too computationally costly, so we should use a heuristic that’s “shut sufficient” to optimum. Even for a easy downside like this, I needed to minimize the solver off after it reached an optimality hole of 5% from the decrease sure. In actions as commonplace and trivial as raking leaves, we use heuristics on a regular basis. Maybe we lose round 2.5 minutes by raking suboptimally, however we save hours by not having to formulate and code a linear program.

In lots of different functions, nevertheless, a number of hours (or days) of math and code can save a number of weeks, or thousands and thousands of {dollars}. Assume, for instance, of the money and time saved by enhancing the routing of planes to numerous airports world wide, or vehicles across the nation.

All these issues are throughout us, even when we don’t resolve them with express optimization strategies. Optimization can function an efficient methodology for translating on a regular basis issues into a strong decision-making framework.

To summarize the method, you need to: 1) Determine the discrete and steady choices you management, 2) Decide what the parameters of the issue are, 3) Outline the target (what you decrease or maximize) clearly, 4) State constraints explicitly (capability, task, and many others), and 5) Formulate and resolve the issue.

When you internalize this course of, you’ll spot optimization alternatives in every single place.

References

[1] Leaf-raking optimization code and knowledge simulation (2025). GitHub repository: [https://github.com/Josiah-DeValois/Optimize-Leaf-Raking].

Creator word

Should you loved this, I write about analytical reasoning, determination science, optimization, and knowledge science.