Algorithm for Cutting Stock Problem using Google OR-Tools. Link to the tool:

Overview

Cutting Stock Problem

Cutting Stock Problem (CSP) deals with planning the cutting of items (rods / sheets) from given stock items (which are usually of fixed size).

New to Cutting Stock Problem? Understand Visually

Video Tutorial on Cutting Stock Problem

This implementation of CSP tries to answer

How to minimize number of stock items used while cutting customer order

while doing so, it also caters

How to cut the stock for customer orders so that waste is minimum

The OR Tools also helps us in calculating the number of possible solutions for your problem. So in addition, we can also compute

In how many ways can we cut given order from fixed size Stock?

Quick Usage

This is how CSP Tools looks in action. Click CSP Tool to use it CSP Tool

Libraries

Quick Start

Install Pipenv, if not already installed

$ pip3 install --user pipenv

Clone this project and install packages

$ git clone https://github.com/emadehsan/csp
$ cd csp
$ pipenv install

# activate env
$ pipenv shell

Run

If you run the stock_cutter_1d.py file directly, it runs the example which uses 120 as length of stock Rod and generates some customer rods to cut. You can update these at the end of stock_cutter_1d.py.

(csp) $ python csp/stock_cutter_1d.py

Output:

numRollsUsed 5
Status: OPTIMAL
Roll #0: [0.0, [33, 33, 18, 18, 18]]
Roll #1: [2.9999999999999925, [33, 30, 18, 18, 18]]
Roll #2: [5.999999999999993, [30, 30, 18, 18, 18]]
Roll #3: [2.9999999999999987, [33, 33, 33, 18]]
Roll #4: [21.0, [33, 33, 33]]```

Graph of Output

Using input file

If you want to describe your inputs in a file, infile.txt describes the expected format

(csp) $ python3 csp/stock_cutter_1d.py infile.txt

Thinks to keep in mind

  • Works with integers only: IP (Integer Programming) problems working with integers only. If you have some values that have decimal part, you can multiply all of your inputs with some number that will make them integers (or close estimation).
  • You cannot specify units: Whether your input is in Inches or Meters, you have to keep a record of that yourself and conversions if any.

Resources

The whole code for this project is taken from Serge Kruk's

Owner
Emad Ehsan
Overthinking about overthinking. Co-founded @Traverous | Google Developer Expert @googledevelopers | Top Trending Developer on GitHub
Emad Ehsan
A* (with 2 heuristic functions), BFS , DFS and DFS iterativeA* (with 2 heuristic functions), BFS , DFS and DFS iterative

Descpritpion This project solves the Taquin game (jeu de taquin) problem using different algorithms : A* (with 2 heuristic functions), BFS , DFS and D

Ayari Ahmed 3 May 09, 2022
A collection of design patterns/idioms in Python

python-patterns A collection of design patterns and idioms in Python. Current Patterns Creational Patterns: Pattern Description abstract_factory use a

Sakis Kasampalis 36.2k Jan 05, 2023
This is the code repository for 40 Algorithms Every Programmer Should Know , published by Packt.

40 Algorithms Every Programmer Should Know, published by Packt

Packt 721 Jan 02, 2023
Algoritmos de busca:

Algoritmos-de-Buscas Algoritmos de busca: Abaixo está a interface da aplicação: Ao selecionar o tipo de busca e o caminho, então será realizado o cálc

Elielson Barbosa 5 Oct 04, 2021
8 Puzzle with A* , Greedy & BFS Search in Python

8_Puzzle 8 Puzzle with A* , Greedy & BFS Search in Python Python Install Python from here. Pip Install pip from here. How to run? 🚀 Install 8_Puzzle

I3L4CK H4CK3l2 1 Jan 30, 2022
Provide player's names and mmr and generate mathematically balanced teams

Lollo's matchmaking algorithm Provide player's names and mmr and generate mathematically balanced teams How to use Fill the input.json file with your

4 Aug 04, 2022
marching Squares algorithm in python with clean code.

Marching Squares marching Squares algorithm in python with clean code. Tools Python 3 EasyDraw Creators Mohammad Dori Run the Code Installation Requir

Mohammad Dori 3 Jul 15, 2022
Supplementary Data for Evolving Reinforcement Learning Algorithms

evolvingrl Supplementary Data for Evolving Reinforcement Learning Algorithms This dataset contains 1000 loss graphs from two experiments: 500 unique g

John Co-Reyes 42 Sep 21, 2022
Pathfinding visualizer in pygame: A*

Pathfinding Visualizer A* What is this A* algorithm ? Simply put, it is an algorithm that aims to find the shortest possible path between two location

0 Feb 26, 2022
Exam Schedule Generator using Genetic Algorithm

Exam Schedule Generator using Genetic Algorithm Requirements Use any kind of crossover Choose any justifiable rate of mutation Use roulette wheel sele

Sana Khan 1 Jan 12, 2022
A Python implementation of Jerome Friedman's Multivariate Adaptive Regression Splines

py-earth A Python implementation of Jerome Friedman's Multivariate Adaptive Regression Splines algorithm, in the style of scikit-learn. The py-earth p

431 Dec 15, 2022
Python package to monitor the power consumption of any algorithm

CarbonAI This project aims at creating a python package that allows you to monitor the power consumption of any python function. Documentation The com

Capgemini Invent France 36 Nov 11, 2022
Algorithms and data structures for educational, demonstrational and experimental purposes.

Algorithms and Data Structures (ands) Introduction This project was created for personal use mostly while studying for an exam (starting in the month

50 Dec 06, 2022
This project is an implementation of a simple K-means algorithm

Simple-Kmeans-Clustering-Algorithm Abstract K-means is a centroid-based algorithm, or a distance-based algorithm, where we calculate the distances to

Saman Khamesian 7 Aug 09, 2022
Solving a card game with three search algorithms: BFS, IDS, and A*

Search Algorithms Overview In this project, we want to solve a card game with three search algorithms. In this card game, we have to sort our cards by

Korosh 5 Aug 04, 2022
A tictactoe where you never win, implemented using minimax algorithm

Unbeatable_TicTacToe A tictactoe where you never win, implemented using minimax algorithm Requirements Make sure you have the pygame module along with

Jessica Jolly 3 Jul 28, 2022
A Python library for simulating finite automata, pushdown automata, and Turing machines

Automata Copyright 2016-2021 Caleb Evans Released under the MIT license Automata is a Python 3 library which implements the structures and algorithms

Caleb Evans 219 Dec 12, 2022
Primedice like provably fair algorithm

Primedice like provably fair algorithm

Ryu juheon 3 Dec 02, 2022
Python Sorted Container Types: Sorted List, Sorted Dict, and Sorted Set

Python Sorted Containers Sorted Containers is an Apache2 licensed sorted collections library, written in pure-Python, and fast as C-extensions. Python

Grant Jenks 2.8k Jan 04, 2023
Greedy Algorithm-Problem Solving

MAX-MIN-Hackrrank-Python-Solution Greedy Algorithm-Problem Solving You will be given a list of integers, , and a single integer . You must create an a

Mahesh Nagargoje 3 Jul 13, 2021