5.1 Linear Programming

https://youtu.be/E72DWgKP_1Y?si=0zPhVmrar-x2I87L

Full credit to Tomáš Sláma

---

slama.dev §

• Home  - Reading  - CV  - Climbing  - Photos  - Videos

Linear Programming in Python §

YouTube , released 4. 7. 2023, updated 13. 9. 2023, Česká verze článku

• Introduction
• Practical examples
  • Farmer’s problem
  • Knapsack problem
  • Graph coloring
  • Traveling salesman problem
  • Bin packing
  • Partition problem
  • Maximum independent set
  • Minimum vertex cover
• Resources

Introduction §

This post contains additional materials to my newly released video about linear programming, namely a number of practical examples of how it can be used to solve a variety of problems using Python and its pulp package.

Practical examples §

Farmer’s problem §

With the planting season steadily approaching, your farmer friend presents you with the following problem.

You have 33 tons of potato seeds and 44 tons of carrot seeds. To grow the crops efficiently, you also have 55 tons of fertilizer, which has to be used when planting in a 1:11:1 ratio (i.e. 11 kilogram of potatoes or carrots requires 11 kilogram of fertilizer). The profit is 1.2$/kg1.2$/kg for potato seeds and 1.7$/kg1.7$/kg for carrot seeds.

How much potatoes and carrots should you plant to maximize your profit this season?

Source codeOutput

Knapsack problem §

Given nn items, each with weight wiwi​ and price pipi​, our task is to maximize the price of the items we take into our backpack without exceeding its carry weight MM.

Source codeOutput

Graph coloring §

We want to find a minimal kk such that a graph GG is vertex kk-colorable.

Source codeOutput

Traveling salesman problem §

Given a weighted oriented graph GG, we want to find the longest Hamiltonian cycle.

Source codeOutput

Bin packing §

Given nn items with weights w1,…,wnw1​,…,wn​ and an arbitrary number of bins with maximum carry weight CC, determine the lowest number of bins that can contain all the items without exceeding their carry weight.

Source codeOutput

Partition problem §

Given nn items with weights w1,…,wnw1​,…,wn​, split them into two parts such that the difference in their weights is minimized.

Source codeOutput

Maximum independent set §

Given a graph GG, find the largest set of vertices such that no two share an edge.

Source codeOutput

Minimum vertex cover §

Given a graph GG, find the smallest set of vertices that cover all edges.

Source codeOutput

Resources §

Here are all the resources I used for data and documentation:

• Hands-On Linear Programming: Optimization With Python
• PuLP documentation
• Dataset for TSP
• Dataset for knapsack
• Dataset for the partition problem

Maintained by Tomáš Sláma.
tomas [at] slama [dot] dev
source code | privacy policy | RSS | 🇺🇦 🇮🇱