Cutting Stock Problem (1D) algorithms implemented with Python 3
The intent of this project is to code algorithm solutions the Cutting Stock Problem, an area of operations research.
In short, the Cutting Stock Problem is a problem where we have material (like a metal pipe, or wood boards) which needs to be cut into pieces. These pieces should be laid out, across several boards, such that we can minimize wasted material (bits to short to use).
Code should be correct, readable, easy to use, and well-commented.
Python 3.6
Clone repo into your project directory.
or
git install git+https://github.com/filipwodnicki/custo.gitcd custo
python -m unittest discover tests
custo/greedy.py
This is the first algorithm implemented, a "hello world" of sorts. The First-fit Algorithm is a type of greedy approximation algorithm. It's called "greedy" because it optimizes at each step of calculation without considering the solution as a whole. Furthermore, even as a greedy algorithm it's only an approximation of the optimal result. Namely, at each step it doesn't check which piece fits best, it's just first-come-first-served!
Here's how it works:
- Sort input pieces by size
- Initialize the first Board, which will be output
- Try to arrange the largest item on the Board
- If there is space, place the item
- If there is no space, take a new Board off the shelf and place the item on that new Board
- Repeat #3-5 for each item, then return solution.
Interestingly, Fit-first has been shown to always give results within 20-25% of the truly optimal solution.
from custo import greedy_algorithm
greedy_algorithm([450, 444, 436, 430, 389, 389, 386, 375, 362, 362, 261, 261, 261], 2050.)
Please email author if interested.
v0.1.1 (01-09-2018) Fix known bugs with import
v0.1.0 (31-08-2018) Project launch. Implement Greedy Algorithm with tests
MIT © Filip Wodnicki 2018