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 spotted it’s principally one large optimization drawback.

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 sooner as a result of I’d bag all the things without delay? Or extra piles, so I wouldn’t need to rake as far? Perhaps a single back-to-front go would decrease whole time?

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

Why Optimization Nonetheless Issues

Optimization is a strong but typically missed software in information science circles now dominated by machine studying. Don’t get me improper, 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 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 way in which I perceived the world round me.

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

1) break down the formulation behind a linear program (LP),
2) evaluate 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 drawback, there are a number of key parts:

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

Choice Variables: The choice variables are the components of the issue that you would be able to management. For our leaf raking drawback, 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. Once we decide constraints, we’re asking, “What components are past my management?” or “What are the principles?” Often, there are a number of these. With regards to raking leaves, there are guidelines that we will’t change to make sure the job is finished 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 signifies that we can not have an infinite variety of piles (possibly 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 will match into every bag since they’ve a restricted capability.

And similar to that, we have now the fundamental parts of a linear program.

These parts are current in each linear program formulation, however it will also 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 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 project of 1 cell to at least one pile is relaxed so {that a} cell could also be cut up between a number of piles, it turns into a combined 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 checklist, together with raking velocity, bagging time, leaf distribution, wind route, and yard slope. I additionally wanted a approach 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 file cut 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 toes.

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 think 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 realize good numbers, however to exhibit the construction and strategy of linear programming.

All information 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, reminiscent of 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 acquire:

• 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 a way lengthy it takes to rake a small mass of leaves over a brief distance. Increased α 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: fastened 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 full mass of leaves assigned to pile j:

mⱼ = ∑ᵢ mᵢ xᵢⱼ

3. Choice Variables

Now, we have now 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 resolution variables: raking (assigning) leaves to piles, opening piles, and the variety of luggage used.

Project variables

To find out which leaves might be raked to which piles, we arrange an project 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 resolution 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 have now sufficient luggage to carry the leaves at every pile, we have now a bag rely 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 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 could both be in a single cell or it might not, and the variety of luggage used to bag all leaves in pile j have to be an integer better than zero.

Keep 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 relies on mass and distance; bagging time relies on pile mass and variety of luggage.
We decrease whole 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 will formulate and clear up the complete drawback.

(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

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 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 full 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 mission repository: Leaf-Raking Optimization Code.

Testing Easy Heuristics

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

To verify 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 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 isn’t 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 exhibiting 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: Complete time taken to rake the yard by every technique

The answer discovered by the optimization identifies 5 piles which might be principally 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 in opposition to an optimum answer for example 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 complete linear program is just too computationally costly, so we should use a heuristic that’s “shut sufficient” to optimum. Even for a easy drawback 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}. Suppose, for instance, of the money and time saved by bettering the routing of planes to numerous airports world wide, or vehicles across the nation.

These kind 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 sturdy decision-making framework.

To summarize the method, you could: 1) Establish 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, project, and many others), 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 information simulation (2025). GitHub repository: [https://github.com/Josiah-DeValois/Optimize-Leaf-Raking].

Writer be aware

For those who loved this, I write about analytical reasoning, resolution science, optimization, and information science.