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/fliscopt@branchname

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...
null
A raw implementation of the nearest insertion algorithm to resolve TSP problems in a TXT format.

TSP-Nearest-Insertion A raw implementation of the nearest insertion algorithm to resolve TSP problems in a TXT format. Instructions Load a txt file wi

sjas_Phantom 1 Dec 2, 2021
Algorithms-in-Python - Programs related to DSA in Python for placement practice

Algorithms-in-Python Programs related to DSA in Python for placement practice CO

MAINAK CHAUDHURI 2 Feb 2, 2022
Algorithmic trading backtest and optimization examples using order book imbalances. (bitcoin, cryptocurrency, bitmex)

Algorithmic trading backtest and optimization examples using order book imbalances. (bitcoin, cryptocurrency, bitmex)

null 172 Dec 21, 2022
RRT algorithm and its optimization

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

Sarannya Bhattacharya 7 Mar 6, 2022
A Python Package for Portfolio Optimization using the Critical Line Algorithm

A Python Package for Portfolio Optimization using the Critical Line Algorithm

null 19 Oct 11, 2022
Dynamic Programming-Join Optimization Algorithm

DP-JOA Join optimization is the process of optimizing the joining, or combining, of two or more tables in a database. Here is a simple join optimizati

Haoze Zhou 3 Feb 3, 2022
A simple library for implementing common design patterns.

PyPattyrn from pypattyrn.creational.singleton import Singleton class DummyClass(object, metaclass=Singleton): # DummyClass is now a Singleton!

null 1.7k Jan 1, 2023
zoofs is a Python library for performing feature selection using an variety of nature inspired wrapper algorithms. The algorithms range from swarm-intelligence to physics based to Evolutionary. It's easy to use ,flexible and powerful tool to reduce your feature size.

zoofs is a Python library for performing feature selection using a variety of nature-inspired wrapper algorithms. The algorithms range from swarm-intelligence to physics-based to Evolutionary. It's easy to use , flexible and powerful tool to reduce your feature size.

Jaswinder Singh 168 Dec 30, 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
Python based framework providing a simple and intuitive framework for algorithmic trading

Harvest is a Python based framework providing a simple and intuitive framework for algorithmic trading. Visit Harvest's website for details, tutorials

null 100 Jan 3, 2023
A simple python implementation of A* and bfs algorithm solving Eight-Puzzle

A simple python implementation of A* and bfs algorithm solving Eight-Puzzle

null 2 May 22, 2022
Minimal pure Python library for working with little-endian list representation of bit strings.

bitlist Minimal Python library for working with bit vectors natively. Purpose This library allows programmers to work with a native representation of

Andrei Lapets 0 Jul 25, 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 9, 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 1, 2022
This python algorithm creates a simple house floor plan based on a user-provided CSV file.

This python algorithm creates a simple house floor plan based on a user-provided CSV file. The algorithm generates possible router placements and evaluates where a signal will be reached in every room of the floor plan.

Joshua Miller 1 Nov 12, 2021
Wordle-solver - A program that solves a Wordle using a simple algorithm

Wordle Solver A program that solves a Wordle using a simple algorithm. To see it

Luc Bouchard 3 Feb 13, 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

null 50 Dec 6, 2022
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 9, 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

null 4 Aug 4, 2022