FLIght SCheduling OPTimization - a simple optimization library for flight scheduling and related problems in the discrete domain

Overview

Fliscopt

Stars Forks License Issues made-with-python Open Source Love png1 Maintenance PRs Welcome PyPI Tweet Say Thanks!

image

FLIght SCheduling OPTimization πŸ›« or fliscopt is a simple optimization library for flight scheduling and related problems in the discrete domain. The library supports plotting, asynchronous multiprocessing, and unimodal optimization benchmarks. The following repository contains code for the paper "XYZ". The experiments were performed in PyPy3.7 and CPython 3.8.10.

Following algorithms have been implemented and test as of date:

Algorithms:

  • Hill Climbing
  • Random Search
  • Simulated Annealing
  • Genetic Algorithm
  • Genetic Algorithm in Reverse Mode
  • Genetic Algorithm with Reversals
  • Genetic Algorithm with Random Search as a Reversal/Reverse Process
  • Iterated Chaining

Take a look at the docs

Getting Started

Install the library using pip:

pip install fliscopt

Or for unreleased versions:

pip install 'git+https://github.com/Agrover112/fliscopt/[email protected]

Or for development:

git clone https://github.com/Agrover112/fliscopt.git
cd fliscopt
pip install .

Download the flights.txt file from the following link and add it to a data/ directory within your parent directory.

Checkout out the examples in the examples directory or run in Google Collab

For PyPy users

The instructions for setup are mentioned in the setup directory. Alternatively, you can set up using this bash script. A requirements file is provided just in case. The script creates and activates a PyPy Conda environment with all libraries and dependencies.

cd ./setup.sh
source setup.sh

Then install using:

pypy -mpip install fliscopt

Testing

After adding any new algorithm, you can run the tests to check if the code is working properly.

./run_tests.sh

Results

Experimental Results

Results were compared by using the same seeds. The following table shows the results of the experiments. (Will be shortly added)

Accessing results

After running the experiments, the results are stored in the results directory. The results are stored in the following format in subdirectories:

.
β”œβ”€β”€ multi_proc
β”‚   β”œβ”€β”€ ackley_N2
β”‚   β”‚   β”œβ”€β”€ genetic_algorithm_results.csv
β”‚   β”‚   β”œβ”€β”€ genetic_algorithm_reversed_results.csv
β”‚   β”‚   β”œβ”€β”€ genetic_algorithm_with_reversals_results.csv
β”‚   β”‚   β”œβ”€β”€ hill_climb_results.csv
β”‚   β”‚   β”œβ”€β”€ random_search_results.csv
β”‚   β”‚   └── simulated_annealing_results.csv
β”‚   β”œβ”€β”€ booth/...
|   |
|   |
β”‚   └── zakharov
β”‚       β”œβ”€β”€ genetic_algorithm_results.csv
β”‚       β”œβ”€β”€ genetic_algorithm_reversed_results                  
β”‚       β”œβ”€β”€ genetic_algorithm_with_reversals_results.csv
β”‚       β”œβ”€β”€ random_search_results.csv
β”‚       └── simulated_annealing_results.csv
β”œβ”€β”€ plots
β”‚   β”œβ”€β”€ ackley_N2
β”‚   β”œβ”€β”€ fitness_function
β”‚   β”‚   β”œβ”€β”€ hill_climb.png
β”‚   β”‚   └── random_search.png
β”‚   β”œβ”€β”€ flight_scheduling
β”‚   β”‚   β”œβ”€β”€ simulated_annealing.png
β”‚   β”‚   β”œβ”€β”€ sol_chaining.png
β”‚   β”‚   └── sol_chaining_a1.png
β”‚   └── griewank

References

Read the following for detailed understanding of our project.

[1] Alicea B., Grover A., Lim A. ,Parent J, Unified Theory of Switching. Flash Talk to be presented at: 4th Neuromatch Conference; December 1 - 2, 2021

Contributing Guidelines

Refer Contributing.md and Project Board for mode details. This repository follows conventional commits!

Comments
  • Add message for failed unittests.

    Add message for failed unittests.

    A message indicating a failure for each unit-test, should give the user a small idea of what went wrong in the test. ex: self.assertEqual ( f(values), 0, msg ='HEURISTIC MESSAGE INDICATING WHY TEST CASE FAILED')

    good first issue Hacktoberfest Hacktoberfest-accepted 
    opened by Agrover112 12
  • fix:Add docstrings for each algorithm file.

    fix:Add docstrings for each algorithm file.

    Fixing Issue #27 , Please check the added docstrings and if the format is correct, if wrong please help me to correct the mistakes because I am a complete beginner to Google Docstrings and even large Python Codebases. Thank you and have a great day!

    Hacktoberfest Hacktoberfest-accepted 
    opened by subhamgcon 11
  • Add docstrings for each algorithm file.

    Add docstrings for each algorithm file.

    There are few files which contain implementation of the algorithms: [**sa,ga,hc,chaining,rs].py** you need to write the docstring for the classes present in each file using Google Docstring Convention. Refer: algorithms.py on how to write docstrings for functions and similarily refer THIS and THIS link for on getting started on how to write docstrings for the classes. PS : Google Style Guide

    • [ ] chaining.py
    • [ ] ga.py
    • [ ] rs.py
    • [ ] sa.py
    • [ ] hc.py
    documentation good first issue Hacktoberfest 
    opened by Agrover112 6
  •  #10 Upload docs & set up wrangler for vercel @agrover112 @gizmotronn

    #10 Upload docs & set up wrangler for vercel @agrover112 @gizmotronn

    Creating pr to reference #10

    Docs should also be accessible in main branch (aka master) imo, we can autogenerate docs based on markdown files @Agrover112 inside the module/library

    E.g. let's say you create a doc page in /docs branch called "Why bees can't fly" with the meta tag for doc-tag being bees

    We can setup a script in main branch that when using module in ide, user can type /fliscopt help bees and will find the "intro" meta about the bees entry in the markdown file in /docs branch, as well as a link to view the documentation site

    documentation enhancement 
    opened by Gizmotronn 5
  • Add an Pull Request template

    Add an Pull Request template

    πŸ‘Ž Actual Behavior

    A template for raising a Pullreq.

    πŸ‘ Expected behavior

    same as above

    ✍️ Suggestions to rectify this issue

    Create a .yml template for creating a PR template.

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    good first issue Hacktoberfest Hacktoberfest-accepted 
    opened by Agrover112 5
  • fix(readme): Add graphic

    fix(readme): Add graphic

    Closes #11 @Agrover112 I have added a graphic and a logo file in the project, and updated the readme file. I have referred to the above mentioned graphics. Please mention any suggestion or changes to the graphic/logo file. I will look into it and make the necessary changes.

    enhancement Hacktoberfest Hacktoberfest-accepted 
    opened by Anik-Bardhan 5
  • Comparing differences between config files -> #10

    Comparing differences between config files -> #10

    Seems like it's a plugin dependancy issue that's causing the build issues. @Agrover112 Docs should be ready to go, I haven't been able to get the lightweight CMS editor working BUT I'd advise setting this up with GitHub pages by tomorrow and then logging in with prose.io for now UNTIL I can fix the plugin issue

    gem bundle build is the worst thing I can imagine rn.

    bug documentation 
    opened by Gizmotronn 2
  • πŸ› Bug Report: GA Reversals wrong number of reversals

    πŸ› Bug Report: GA Reversals wrong number of reversals

    πŸ‘Ÿ Reproduction steps

    Just use the api normally and enter any combination of n_k and number_generations.

    πŸ‘ Expected behavior

    The number of reversals would be = iter/n_k

    πŸ‘Ž Actual Behavior

    Only 1 reversal process takes place , as seen due to default parameters, thus entered parameters are not registering.

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    bug 
    opened by Agrover112 2
  • Add an Pull Request template #39

    Add an Pull Request template #39

    Closes #39

    Renamed PULL_REQUEST.md to to pull_request_template.md following these instructions https://docs.github.com/en/communities/using-templates-to-encourage-useful-issues-and-pull-requests/creating-a-pull-request-template-for-your-repository

    This has been tested as shown in the screenshot. image

    opened by LittleBigProgramming 2
  • Merge this

    Merge this

    What does this PR do?

    Updates README.md with some missing information wrt Results tables.

    Test Plan

    (Write your test plan here. If you changed any code, please provide us with clear instructions on how you verified your changes work.)

    Related PRs and Issues

    (If this PR is related to any other PR or resolves any issue or related to any issue link all related PR and issues here.)

    Have you read the Contributing Guidelines on issues?

    (Write your answer here.)

    opened by So-bonkers 1
  • Add PyPy tests.

    Add PyPy tests.

    Current ./run_tests.sh due to oversight were written and run using python filename.py. In order to appropriately test it , it needs yo be replaced by: pypy filename.py

    opened by Agrover112 1
  • Github Sync Fork action not working

    Github Sync Fork action not working

    πŸ‘Ž Actual Behavior

    Failed to create or merge pull request: HttpError: Validation Failed: {"resource":"PullRequest","field":"head","code":"invalid"}

    πŸ‘ Expected behavior

    Should technically sync forks?

    ✍️ Suggestions to rectify this issue

    I'm currently using secrets.TOKEN, a token which I use for the repo with public_repo permissions enabled. Not sure what is going wrong really. image

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    bug help wanted Hacktoberfest Hacktoberfest-accepted 
    opened by Agrover112 0
  • πŸ“‹General Issues: Exception handling

    πŸ“‹General Issues: Exception handling

    πŸ‘Ž Actual Behavior

    The Error isn't handled properly.

    πŸ‘ Expected behavior

    Should raise a particular Error (exception) when unintended input is passed to the given fn,etc.

    ✍️ Suggestions to rectify this issue

    Add exception handling for each of the core functions and algorithms

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    bug 
    opened by Agrover112 0
  • Fix #FIX-NEEDED

    Fix #FIX-NEEDED

    πŸ‘Ÿ Reproduction steps

    Implemented in: mulit_mutattion in ga_utils.py Can be tested by replacing mutation with multi_mutation in ga.py.

    πŸ‘ Expected behavior

    Mulit_mutattion in ga_utils.py should change N bits as selected. [1,2,3,4] for 2 bits could be: [1,3,3,5]

    πŸ‘Ž Actual Behavior

    Mulit_mutattion in ga_utils.py doesn't work as expected. Gives an Index Error when used , since the implementation is not correct.

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    bug help wanted good first issue Hacktoberfest 
    opened by Agrover112 5
  • Add more problem functions in fitness.py

    Add more problem functions in fitness.py

    Add more problems rel to current flightscheduling problem. (No matrix problems) Only problems whose solution is of the form: [1,2,3,4] OR [x1,z2..........xn] and corresponding domain : [(-a,b),(-c,-d).......nth-tuple]. Refer fitness.py for existing problems and cost functions and their domains.

    Ideally the isse requires you to add a sample cost function to solve a particular problem, whose inputs are of form 1*n

    enhancement help wanted good first issue Hacktoberfest 
    opened by Agrover112 7
Releases(v0.4.1)
Owner
Humans trying to understand machines...
An implementation of ordered dithering algorithm in python as multimedia course project

One way of minimizing the size of an image is to simply reduce the number of bits you use to represent each pixel.

7 Dec 02, 2022
Apriori - An algorithm for frequent item set mining and association rule learning over relational databases

Apriori Apriori is an algorithm for frequent item set mining and association rul

Mohammad Nazari 8 Jan 10, 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
causal-learn: Causal Discovery for Python

causal-learn: Causal Discovery for Python Causal-learn is a python package for causal discovery that implements both classical and state-of-the-art ca

589 Dec 29, 2022
A simple python application to visualize sorting algorithms.

Visualize sorting algorithms A simple python application to visualize sorting algorithms. Sort Algorithms Name Function Name O( ) Bubble Sort bubble_s

Duc Tran 3 Apr 01, 2022
How on earth can I ever think of a solution like that in an interview?!

fuck-coding-interviews This repository is created by an awkward programmer who always struggles with coding problems on LeetCode, even with some Easy

Vinta Chen 613 Jan 08, 2023
A minimal implementation of the IQRM interference flagging algorithm for radio pulsar and transient searches

A minimal implementation of the IQRM interference flagging algorithm for radio pulsar and transient searches. This module only provides the algorithm that infers a channel mask from some spectral sta

Vincent Morello 6 Nov 29, 2022
FLIght SCheduling OPTimization - a simple optimization library for flight scheduling and related problems in the discrete domain

Fliscopt FLIght SCheduling OPTimization πŸ›« or fliscopt is a simple optimization library for flight scheduling and related problems in the discrete dom

33 Dec 17, 2022
Implementation of core NuPIC algorithms in C++

NuPIC Core This repository contains the C++ source code for the Numenta Platform for Intelligent Computing (NuPIC)

Numenta 270 Nov 19, 2022
TikTok X-Gorgon & X-Khronos Generation Algorithm

TikTok X-Gorgon & X-Khronos Generation Algorithm X-Gorgon and X-Khronos headers are required to call tiktok api. I will provide you API as rental or s

TikTokMate 31 Dec 01, 2022
Esse repositΓ³rio tem como finalidade expor os trabalhos feitos para disciplina de Algoritmos computacionais e estruturais do CEFET-RJ no ano letivo de 2021.

Exercícios de Python 🐍 Esse repositório tem como finalidade expor os trabalhos feitos para disciplina de Algoritmos computacionais e estruturais do C

Rafaela Bezerra de Figueiredo 1 Nov 20, 2021
HashDB is a community-sourced library of hashing algorithms used in malware.

HashDB HashDB is a community-sourced library of hashing algorithms used in malware. How To Use HashDB HashDB can be used as a stand alone hashing libr

OALabs 216 Jan 06, 2023
Optimal skincare partition finder using graph theory

Pigment The problem of partitioning up a skincare regime into parts such that each part does not interfere with itself is equivalent to the minimal cl

Jason Nguyen 1 Nov 22, 2021
Nature-inspired algorithms are a very popular tool for solving optimization problems.

Nature-inspired algorithms are a very popular tool for solving optimization problems. Numerous variants of nature-inspired algorithms have been develo

NiaOrg 215 Dec 28, 2022
Xor encryption and decryption algorithm

Folosire: Pentru encriptare: python encrypt.py parola fiΘ™ier pentru criptare fiΘ™ier encriptat(de tip binar) Pentru decriptare: python decrypt.p

2 Dec 05, 2021
Tic-tac-toe with minmax algorithm.

Tic-tac-toe Tic-tac-toe game with minmax algorithm which is a research algorithm his objective is to find the best move to play by going through all t

5 Jan 27, 2022
So far implements A* will add more later

Pathfinding_Visualization Finds the shortest path between two nodes. The light blue path is the shortest path. The black nodes are barriers. Created i

Lukas DeLoach 1 Jan 18, 2022
Implementation of Apriori algorithms via Python

Installing run bellow command for installing all packages pip install -r requirements.txt Data Put csv data under this directory "infrastructure/data

Mahdi Rezaei 0 Jul 25, 2022
RRT algorithm and its optimization

RRT-Algorithm-Visualisation This is a project that aims to develop upon the RRT

Sarannya Bhattacharya 7 Mar 06, 2022
Cormen-Lib - An academic tool for data structures and algorithms courses

The Cormen-lib module is an insular data structures and algorithms library based on the Thomas H. Cormen's Introduction to Algorithms Third Edition. This library was made specifically for administeri

Cormen Lib 12 Aug 18, 2022