How I Optimized My Leaf Raking Strategy Using Linear Programming

, and it’s formally leaf-raking season. As I engaged on this tedious job, I noticed it’s mainly one huge optimization downside.

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

As I labored, I started to marvel: 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? Possibly 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 usually missed software in knowledge science circles now dominated by machine studying. Don’t get me fallacious, machine studying is nice, however generally I feel it may be simple to overlook the environment friendly answer (optimization algorithms) and soar proper to the enjoyable one (ML methods).

Hopefully, after studying this, you’ll assume that optimization could be enjoyable, too. I do know that once I first discovered 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 could 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 Drawback

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

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

Choice Variables: The choice variables are the elements of the issue which you can 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 situated, and which leaves are raked into every of these piles.

Constraints: We even have some which might be out of our management. After we decide constraints, we’re asking, “What components are past my management?” or “What are the principles?” Normally, there are a variety of these. In relation to 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, and so they can solely be raked to a location the place a pile has already been began. This additionally implies that we can not have an infinite variety of piles (perhaps we might, 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 similar to that, we now have the essential components of a linear program.

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

As a result of the mannequin employs binary variables to pick open piles and integer variables to characterize 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 break up between a number of piles, it turns into a blended integer linear program (MILP).

Parameters and Assumptions

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

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

A Fast Conceptual Experiment

If I had been to calibrate this, I’d rake a 100-ft part, mark each 10 ft, and report break up occasions to estimate how raking velocity adjustments 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 ft.

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

I didn’t really time myself doing these duties. As an alternative, I made tough estimates. The purpose isn’t to attain good numbers, however to reveal 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, similar to yard size, yard width, the dimensions of a aspect 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 course, 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 could 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 web site 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 total 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 entire mass of leaves assigned to pile j:

mⱼ = ∑ᵢ mᵢ xᵢⱼ

3. Choice Variables

Now, we now have all the 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 could be raked and bagged. Let’s transfer on to our choice variables: raking (assigning) leaves to piles, opening piles, and the variety of luggage used.

Task variables

To find out which leaves will probably 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 choice 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 should be absolutely assigned to precisely one pile (through the xᵢⱼ’s), and bag counts nⱼ should be ample 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 might both be assigned to a pile j or it might not, every pile might both be in a single cell or it might not, and the variety of luggage used to bag all leaves in pile j should be an integer better than zero.

Bear in mind, i represents the leaves within the yard and j represents the placement 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:

# Choice 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 depends upon mass and distance; bagging time depends upon 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 similar, 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 clear up the complete downside.

(C1) Task

Every cell’s leaves should 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

Complete 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 characterize 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 entire 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 complete 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 realize it or not.

To test the worth added by optimization, I in contrast the ILP to a few 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 couple of massive piles in central spots.

Every heuristic returns a set of pile facilities primarily based 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. Word that underneath the optimization, the raker can rake leaves to a pile even when that pile is just not 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 commonly very useful.

Beneath is an instance snippet displaying how the “micro-piles” heuristic initializes and refines facilities primarily based 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()
    ok = 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 break 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: Complete time taken to rake the yard by every technique

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

Discover that there isn’t any huge 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 for example the efficiency of that heuristic methodology.

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

Conclusion

In lots of conditions, computing the complete linear program is simply 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 lower the solver off after it reached an optimality hole of 5% from the decrease certain. 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 purposes, nevertheless, a couple of hours (or days) of math and code can save a number of weeks, or tens of millions of {dollars}. Suppose, for instance, of the money and time saved by bettering the routing of planes to numerous airports all over the world, or vehicles across the nation.

These kinds of issues are throughout us, even when we don’t clear up 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 should: 1) Establish the discrete and steady selections 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 so on), and 5) Formulate and clear up 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].

Writer notice

In case you loved this, I write about analytical reasoning, choice science, optimization, and knowledge science.