Home Author
Author

Jack Simpson

Currently fascinated by energy markets and electrical engineering. In another life I was a beekeeper that did a PhD in computational biology writing image analysis software and using machine learning to quantify honeybee behaviour in the hive.

ContentFeaturedOptimisationResourcesTips & Tutorials

Solving the knapsack problem with Python and Gurobi

by Jack Simpson
written by Jack Simpson

During my PyCon presentation on Mathematical optimisation, I used the example of the knapsack problem to walk people through the structure of a linear program. I’ve had a number of people request access to this code, so I thought I’d write it up in a post so it could be more easily shared. This will be a relatively concise article so feel free to refer to the presentation for any additional context.

What is the knapsack problem?

  • You have a knapsack that can only carry so much weight (in our case 9 kg)
  • Every item you can place in the knapsack has a weight and a value
  • You want to maximise the value of the items you choose to put in the knapsack
  • What is the most valuable mix of items you can choose?

Why use this example?

I decided to use this particular example because I wanted to illustrate how mathematical optimisation is perfect for solving problems where you have a large number of granular decisions to make whilst subject to constraints. Many industries face some version of these problems. While machine learning is fantastic for prediction/classification problems, mathematical optimisation was developed specifically to solve complex decision problems.

Let’s solve it in Python

Step 1: Import libraries and initialise a model object.


import gurobipy as gp
from gurobipy import GRB

m = gp.Model("knapsack")

Step 2: Create the model decision variables. These are the binary decisions (0 or 1) that determine whether we are selecting this item to go into the knapsack.




gold = m.addVar(vtype=GRB.BINARY, name="gold")
diamond = m.addVar(vtype=GRB.BINARY, name="diamond")
coin = m.addVar(vtype=GRB.BINARY, name="coin")
statue = m.addVar(vtype=GRB.BINARY, name="statue")
brick = m.addVar(vtype=GRB.BINARY, name="brick")
feather = m.addVar(vtype=GRB.BINARY, name="feather")
ark = m.addVar(vtype=GRB.BINARY, name="ark")
book = m.addVar(vtype=GRB.BINARY, name="book")
necklace = m.addVar(vtype=GRB.BINARY, name="necklace")

Step 3: Create the weight constraint – in this case the backpack cannot hold more than 9 kg of objects.


backpack_max_weight = 9
m.addConstr(2 * gold +
     0.2 * diamond +
     0.3 * coin +
     6 * statue +
     2 * brick +
     0.1 * feather +
     15 * ark +
     1 * book +
     0.5 * necklace <= backpack_max_weight, 
     name="max_weight")

Step 4: Create the objective function of the model – we want to maximise the value of the objects we select.


m.setObjective(
    5000 * gold + 
    1500 * diamond + 
    2000 * coin + 
    8000 * statue + 
    3 * brick + 
    1 * feather + 
    1000000 * ark +
    2000 * book +
    3500 * necklace,
    GRB.MAXIMIZE)

Step 5: Run the model and extract the variables and their optimal values.


m.optimize()

for v in m.getVars():
    print(v.VarName, v.X)

0 comments
0 FacebookTwitterPinterestEmail
FeaturedOptimisationResources

Resources to learn mathematical optimisation

by Jack Simpson
written by Jack Simpson

When I was at PyCon, I had a number of people ask me what resources they could use to to learn more about mathematical optimisation. I thought I’d share my list in this article – if there’s any good content out there I may have missed, please reach out and I’d love to add it to this page!

Articles

Courses

Videos

Books

Python Libraries

To build a mathematical optimisation, you need to do two things: formulate the program, and then pass it to a solver program.

In terms of open source tools, I tend to formulate my model using Pyomo, developed by the National Renewable Energy Laboratory (NREL). You can then use the HiGHS solver (developed by the University of Edinburgh) to solve your model. Both of these libraries are easy to install via pip. Pyomo also has the advantage of allowing you to swap solvers without having to rewrite your program.

As I tend to build a lot of extremely large and complex models (especially ones with a lot of binary or integer variables), I end up using commercial solvers like Gurobi a fair bit. Gurobi has a lot of excellent Python libraries too like gurobipy and gurobipy-pandas.

0 comments
0 FacebookTwitterPinterestEmail
FeaturedOptimisationVideo

PyCon: why data scientists should learn mathematical optimisation

by Jack Simpson
written by Jack Simpson

In November I was fortunate to have the opportunity to present at PyCon AU in Melbourne, Australia. I was really excited to give a talk about why data scientists should be aware of the kinds of problems mathematical optimisation was really good at solving.

The recording of my presentation is below, but a few of my main points were:

  • There are three forms of analytics:
    • Descriptive
    • Predictive
    • Prescriptive
  • Machine learning falls into the predictive category, whereas mathematical optimisation falls into the prescriptive analytics category.
  • Machine learning and mathematical optimisation are enormously complementary – you’ll often take the predictions of a machine learning model and use them as the inputs to a mathematical optimisation which will tell you the optimal decisions you should make, while subject to constraints.
1 comment
0 FacebookTwitterPinterestEmail
ContentEnergyFeaturedLinksVisualisations

Exploring the impact of constraints on a solar farm in the National Electricity Market

by Jack Simpson
written by Jack Simpson

Earlier this week I came across an article about how New England Solar was planning to sell off its solar farms in Australia due to the impact of network congestion:

New Energy Solar’s CEO Liam Thomas said a flood of new projects had resulted in curtailment challenges spreading to other parts of the grid and cut the output of the Manildra solar farm by 40 per cent just as the company was looking for a buyer.

I thought that it would be interesting to dig into some of AEMO’s constraints data in order to investigate exactly how Manildra Solar Farm has been impacted by network congestion in FY-21.

Interestingly, it appears that the vast majority of the time a constraint impacted this solar farm, it could be attributed to a single factor: the 132 KV Molong to Orange North transmission line which you can see in the map below. This transmission line has a thermal limit that determines how much power can flow through it from generators in the area.

Continue Reading
0 comments
0 FacebookTwitterPinterestEmail
ContentEnergyFeaturedVisualisations

Big Battery Bidding and Rebidding!

by Jack Simpson
written by Jack Simpson

In the National Electricity Market (NEM), power stations can bid in their availability in 10 different pricing tranches. They’re able to rebid this availability right up until dispatch is run.

Recently, I was exploring this bidding data and thought I’d take a peak at what the bidding behaviour of the Hornsdale (Tesla) battery looked like in the energy market.

I’d known for a while that the big batteries did a lot of rebidding, but I was blown away by just how frequent it was! In a single day (2019-01-01) the battery made almost 13,500 rebids! In fact, for the first interval of the day, the battery made almost 300 rebids in the week leading up to dispatch.

I do find it interesting how they appeared to be doing so many identical rebids – I suspect there must be some automated process going on that will rebid in all markets regardless of whether the rebid in a particular market is any different to the bid that it replaced.

0 comments
0 FacebookTwitterPinterestEmail
ContentEnergyFeaturedVisualisations

How does a gigawatt of renewables disappear?

by Jack Simpson
written by Jack Simpson

One of the fun things about playing with hundreds of millions of rows of energy market data is that you can just go hunting through it for interesting anomalies. I recently found a fascinating anomaly exploring variable renewable energy (VRE – wind/solar farms) generation in Victoria on the 16th of November 2020

The figure below shows the combined output of every wind and solar farm in the state on a five minute basis between 11:30am and 3:30pm.

Continue Reading
0 comments
0 FacebookTwitterPinterestEmail
BloggingContentEnergyLinks

Virtual power plants, Texas ‘big freeze’ event, and grid visualisation tips video

by Jack Simpson
written by Jack Simpson

Here’s a few interesting pieces of energy-related content I’ve come across this week.

1. SolarQuotes have put up a video about their experience participating in a virtual power plant. In the video they cover:

  • How AGL was using their battery during the trial
  • Being aware of changes to feed in tariffs
  • The impact that electric vehicles can have on your consumption
Continue Reading
0 comments
0 FacebookTwitterPinterestEmail
ContentData ScienceFeaturedProgrammingTips & Tutorials

Data science tip: store constants in their own file

by Jack Simpson
written by Jack Simpson

Sometimes when you work on large projects, you can end up with code that looks like this:

if num_values < 15:
    do_thing()

Now, what does the 15 mean? Well, I’m sure you would have known when you first wrote the code, but what happens in 3 months when you try to modify it or pass it on to someone else in your team? Also, what happens if you determine that the number should actually be 16? Now you have to go through all your files and swap numbers in all the right places (and if you miss any you can introduce subtle bugs).

So what’s the solution? Well, what you really need is a single source of truth for your clearly defined constants, which you can:

  • Easily look up
  • Modify/update
  • Import into other code

Python makes this really easy – all you have to do is create a “constants.py” file in your project directory (I suppose you could call it whatever you like, but that’s beside the point). From here, you can import your variables as if you were importing a library:

from constants import NOM_FREQ_HZ, VALUES_IN_MIN

A screenshot of this file from a recent project looks a little like this:

constants code file

This approach helped me write much more readable code, when working with an extremely complicated dataset where numbers were used to represent different value categories.

Obviously for smaller scripts it might not be worth setting up a dedicated file, but for this project, my constants file ended up being a couple of hundred lines long, and is far easier to maintain than if they were defined multiple times across all the files in the project.

0 comments
0 FacebookTwitterPinterestEmail
Newer Posts
Older Posts